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) primal argument stability bound up to optimization error and an O(1/n) statistical complexity for the soft BRM objective under the stated sampling conditions.
Figures & tables
Work
Hypothesis Class
Estimator
Key assumptions
Rate
Maillard et al. (2010)
linear
Oracle
generative model
O(n−1/2)
Dai et al. (2018)
general
Oracle
β -mixing path
O~(n−1/2)
Chen and Jiang (2019)
finite
Oracle
realizability, completeness
O~(n−1) †
Duan et al. (2021)
general
Oracle
completeness
O(n−1/2) ‡
Hu et al. (2025)
linear
Oracle
completeness, feature cov.
O~(n−1) †
Wang et al. (2022)
general
SGDA
convex–strongly concave
O~(n−1/2)
Table 1: Statistical rates for prior works. BRM rates concern squared Bellman error or the corresponding population objective, subject to the qualifications below. The row of Wang et al. (2022) concerns general excess primal population risk. Oracle means the analysis assumes the exact empirical (ERM or minimax) solution is available. SGDA means it bounds the output of stochastic gradient descent–ascent.
Figure 1: Primal argument stability, function-space stability and excess population MSBE of the SGDA output against n (log–log), averaged over 50 repetitions. Solid lines: i.i.d. data; dashed: a single trajectory; dotted: exact empirical minimizer. Grey guides show slopes −1 and −1/2 .
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Meaning
S
State space
A
Action space
P(⋅∣s,a)
Transition kernel over the next state from the state-action pair (s,a)
r:S×A→R
Deterministic reward function
ΔAS
Set of stationary Markov policies
π∈ΔAS
Policy
Appendix
Table 2: Notations
Work
Geometry
Setting
Stat. Rate
Opt. Rate
This paper
Primal/dual PL
Offline BRM
O(1/n)
O(1/T)
Wang et al. [2022]
Convex-concave
minimax
O(1/n)
O(1/T)
Appendix
Table 3: Comparison with prior work. Our statistical rate uses independent observations or a controlled stationary covariance factor. Markov update indices and dependent training observations are distinct settings. Table 4 gives the detailed assumptions and metrics.
Convex–concave (Thm. 10: population inner strong concavity)
ΔPD (Thm. 9); R(w)−R(w⋆) (Thm. 10)
O(n−1/2)
Appendix
Table 4: Detailed comparison of the statistical bounds in Table 1 . The notes below the table explain the risk measures, the rates, and the data assumptions.
i.i.d. data
single trajectory
n
H=8
H=16
H=32
H=16
100
16.54±2.93
8.95±1.38
5.93±0.65
9.93±1.20
200
11.88±1.33
7.74±0.57
7.18±0.61
7.70±1.06
400
13.13±2.93
8.38±0.78
7.39±0.65
6.77±0.55
800
8.45±0.56
6.72±0.59
6.27±0.44
6.58±0.68
1600
8.84±0.73
6.95±0.62
5.59±0.55
7.20±0.53
Appendix
Table 5: n times the primal argument stability εTw (mean ± standard error over 50 repetitions, T=40,000 ). A constant column corresponds to an n−1 rate. The last two rows give the fitted slope of logεTw against logn and its 95% bootstrap interval.
i.i.d. data
single trajectory
exact empirical
n
H=8
H=16
H=32
H=16
minimizer (i.i.d.)
100
0.480±0.035
0.834±0.127
0.508±0.036
0.819±0.274
0.672
200
0.457±0.031
0.440±0.039
0.448±0.025
0.461±0.038
0.436
400
0.447±0.037
0.393±0.020
0.446±0.025
0.411±0.026
0.391
800
0.420±0.026
0.412±0.022
0.391±0.021
0.430±0.029
0.404
1600
0.433±0.029
0.385±0.020
0.383±0.020
0.375±0.022
0.358
Appendix
Table 6: n times the excess population MSBE of the SGDA output (mean ± standard error), and of the exact empirical minimizer on the datasets of the i.i.d. H=16 runs.
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 π⋆ 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.
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 ε-optimal policy with O(SA(1−γ)−3ε−2log(SA/δ)) samples, where 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/δ)) and O(SADε−2log(SA/δ)) complexities, respectively, where H upper-bounds the optimal bias span and D 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.
Matthew Zurek, Yudong Chen
Department of Computer Sciences, University of Wisconsin–Madison
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), where n 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.