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

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

    May 18, 2025Zachary Roch, George Atia, Yue WangReinforcement LearningAverage-Reward RL