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.