cs.LGAug 26, 2025

Statistical Complexity of Soft Bellman Residual Minimization

Authors: Enoch H. Kang, Kyoungseok Jang

Organizations: Chung-Ang University

Abstract

Offline reinforcement learning and offline inverse reinforcement learning aim to recover near-optimal value functions or reward models from a fixed batch of logged trajectories, yet current practice still struggles to enforce Bellman consistency scalably. Bellman residual minimization (BRM) has emerged as an attractive remedy. While globally convergent gradient-based soft (i.e., entropy-regularized) BRM methods for neural networks have recently been established, their statistical complexity under stochastic gradient descent remains largely unknown. In this paper, we address this theoretical gap for soft BRM. Through a Lyapunov-based analysis under a uniform PL condition in the auxiliary variable, we establish an O(1/n)\mathcal{O}(1 / n) primal argument stability bound up to optimization error and an O(1/n)\mathcal{O}(1 / n) statistical complexity for the soft BRM objective under the stated sampling conditions.

Figures & tables

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Dec 7, 2025

Statistical analysis of Inverse Entropy-regularized Reinforcement Learning

Inverse reinforcement learning aims to infer the reward function that explains expert behavior observed through trajectories of state--action pairs. A long-standing difficulty in classical IRL is the non-uniqueness of the recovered reward: many reward functions can induce the same optimal policy, rendering the inverse problem ill-posed. In this paper, we develop a statistical framework for Inverse Entropy-regularized Reinforcement Learning that resolves this ambiguity by combining entropy regularization with a least-squares reconstruction of the reward from the soft Bellman residual. This combination yields a unique and well-defined so-called least-squares reward consistent with the expert policy. We model the expert demonstrations as a Markov chain with the invariant distribution defined by an unknown expert policy π⋆π^\star and estimate the policy by a penalized maximum-likelihood procedure over a class of conditional distributions on the action space. We establish high-probability bounds for the excess Kullback--Leibler divergence between the estimated policy and the expert policy, accounting for statistical complexity through covering numbers of the policy class. These results lead to non-asymptotic minimax optimal convergence rates for the least-squares reward function, revealing the interplay between smoothing (entropy regularization), model complexity, and sample size. Our analysis bridges the gap between behavior cloning, inverse reinforcement learning, and modern statistical learning theory.
Nov 14, 2026

Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL

We study the sample complexity of the empirical planning or plug-in approach for reinforcement learning (RL) with a generative model. We show the discounted plug-in approach finds an ε\varepsilon-optimal policy with O(SA(1−γ)−3ε−2log⁡(SA/δ))O(SA (1-γ)^{-3} \varepsilon^{-2} \log(SA/δ)) samples, where S,A,γ,δS, A, γ, δ are the state and action sizes, discount factor, and failure probability, respectively. In the average-reward setting, we show that discounted plug-in and direct (undiscounted) plug-in achieve O(SAHε−2log⁡(SA/δ))O(SAH\varepsilon^{-2}\log(SA/δ)) and O(SADε−2log⁡(SA/δ))O(SAD\varepsilon^{-2}\log(SA/δ)) complexities, respectively, where HH upper-bounds the optimal bias span and DD is the diameter. Combining with our lower bounds for nonadaptive generative models, these results resolve the minimax sample complexity of discounted RL and average-reward RL --- in both the span- and diameter-based classes --- up to constant factors. Our main technical contribution is a novel Bellman residual bracketing technique which improves the efficiency of prior absorbing-MDP-based concentration analyses.
May 14, 2026

Fast Rates for Inverse Reinforcement Learning

We establish novel structural and statistical results for entropy-regularized min-max inverse reinforcement learning (Min-Max-IRL) with linear reward classes in finite-horizon MDPs with Borel state and action spaces. On the structural side, we show that maximum likelihood estimation (MLE) and Min-Max-IRL are equivalent at the population level, and at the empirical level under deterministic dynamics. On the statistical side, exploiting pseudo-self-concordance of the Min-Max-IRL loss, we prove that both the trajectory-level KL divergence and the squared parameter error in the Hessian norm decay at the fast rate O(n−1)\mathcal{O}(n^{-1}), where nn is the number of expert trajectories. Our guarantees apply under misspecification and require no exploration assumptions. We further extend reward-identifiability results to general Borel spaces and derive novel results on the derivatives of the soft-optimal value function with respect to reward parameters.