cs.LGNov 14, 2026

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

Authors: Matthew Zurek, Yudong Chen

Organizations: Department of Computer Sciences, University of Wisconsin–Madison

Abstract

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.

Figures & tables

Explore similar work

Nov 10, 2026

Sharp Sample Complexity of KL-Regularized Reinforcement Learning

KL-regularized reinforcement learning, the objective behind maximum-entropy RL and RL from human feedback, is variational inference in the graphical model of "control as inference": the regularized optimal policy is a posterior over trajectories, and the suboptimality of a policy is ββ times a KL divergence between path measures. However, it is not known how many samples it takes to learn this posterior, even with a generative model. Earlier 1/ε1/ε guarantees scale with H5H^5 in the effective horizon HH, and no lower bound for MDPs depends on the temperature ββ. In this work, we show that for a discounted MDP with KK state-action pairs, the plug-in estimator finds a policy that is εε-optimal from every initial state with O~(KH3/(εmax⁡{ε,β})+KH)\widetilde{O}(KH^3/(ε\max\{ε,β\}) + KH) samples, and that no algorithm, even one that chooses where to sample, can do with fewer when ε≲min⁡{H,H2/β}ε\lesssim \min\{H, H^2/β\}. For ε<βε< β this is a 1/ε1/ε rate with the same horizon dependence as unregularized RL. We also find the exact asymptotic constant of the plug-in estimator, a Fisher-weighted variance of the estimated soft Q-function. The estimator is locally asymptotically minimax among methods that sample every pair equally often, and we give the allocation of samples that is optimal among adaptive designs. Simulations on small MDPs match the rates and the constants.
May 18, 2025

Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

Robust reinforcement learning (RL) under the average-reward criterion is essential for long-term decision-making, particularly when the environment may differ from its training dynamics. However, most existing studies focus on model-based settings and provide only asymptotic guarantees, hindering their principled understanding and practical deployment, especially in data-limited scenarios. We aim to close this gap by proposing a model-free algorithm, Robust Halpern Iteration (RHI). We first design our algorithm based on a black-box sampling oracle, which can estimate the worst-case performance accurately. We then derive the finite sample complexity of RHI under the generative model setting, assuming the sampling oracle. To concretely design such an oracle, we propose a KK-order multi-level Monte-Carlo estimator, which is shown to have a lower bias compared to prior methods. We further instantiate our design for multiple uncertainty models, including KL and χ2χ^2 divergence sets, and show that our RHI algorithm achieves an ε\varepsilon-optimal robust policy with a sample complexity of O~(SAH2ε(2+o(1)))\tilde{\mathcal{O}}\left( \frac{SA\mathcal{H}^2}{\varepsilon^{(2+o(1))}}\right), where S,AS,A are the number of states and actions, and H\mathcal{H} is the robust optimal span. Our result asymptotically matches the best complexity in robust average reward RL.
Nov 3, 2026

Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models

In multi-objective reinforcement learning, preferences may be specified only after data collection, requiring one dataset to support a continuum of reward trade-offs. We study finite discounted Markov decision processes with unknown transitions, SS states, AA actions, and mm known reward functions taking values in [0,1][0,1], given access to a generative model. The learner must provide an ε\varepsilon-optimal policy for every convex combination of these rewards without further sampling, with a guarantee that holds simultaneously over all preferences and initial states. Writing H=(1−γ)−1H=(1-γ)^{-1}, we establish the constant-confidence minimax sample complexity Θ~ ⁣(SAH3ε2min⁡{S,log⁡(em)})\widetildeΘ\!\left( \frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\} \right), where the suppressed factors are logarithmic in S,A,H,ε−1S,A,H,\varepsilon^{-1} and the dependence on mm is explicit. Thus, up to these logarithmic factors, the worst-case statistical cost of supporting all preferences grows logarithmically with the number of objectives and saturates at the number of states. The upper bound uses uniform state--action sampling and empirical planning, with reward rounding in the logarithmic-objective regime. Its analysis chains optimal-value increments over covers of the reward hull. A one-sided Bellman variance bound controls signed value differences under a second transition kernel, preserving the H3ε−2H^3\varepsilon^{-2} dependence. A complementary uniform guarantee for all bounded rewards yields the state-dimension saturation. We establish lower bounds matching up to logarithmic factors through a rare-exit construction with subset rewards and action encoding. These bounds apply to adaptive simulator queries and arbitrary randomized history-dependent output policies, while the upper bounds are attained by deterministic stationary policies.