Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL
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 -optimal policy with samples, where 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 and complexities, respectively, where upper-bounds the optimal bias span and 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
| Algorithm | Complexity | Range | Reference | Notes |
| Plug-in | Azar et al. (2012) | est. | ||
| Plug-in | Azar et al. (2013) | |||
| VRQVI | Sidford et al. (2018) | |||
| Plug-in | Agarwal et al. (2020) | |||
| Perturbed plug-in | Li et al. (2020) | |||
| Plug-in | Zurek and Chen (2025a) |
| Algorithm | Complexity | Reference | Notes |
|---|---|---|---|
| Discounted reduction | Wang et al. (2022) | ||
| Monotone Q-learning | Zhang and Xie (2023) | ||
| Discounted reduction | Zurek and Chen (2024) | ||
| Anchored plug-in | Zurek and Chen (2025a) | ||
| SAVIA | Lee et al. (2025) | ||
| Discounted reduction | Theorem 4.2 |
Reinforcement Learning
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
See all 1,847 papers