{"id":"arxiv/2611.19566","url":"https://arxiv.org/abs/2611.19566","tags":["cs.LG","cs.IT","math.OC","math.PR","stat.ML"],"score":0,"title":"Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL","domain":"cs.LG","source":"arxiv","authors":["Matthew Zurek","Yudong Chen"],"reviews":0,"subject":"cs.LG","summary":"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} \\varepsilon^{-2} \\log(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\\varepsilon^{-2}\\log(SA/δ))$ and $O(SAD\\varepsilon^{-2}\\log(SA/δ))$ complexities, respectively, where $H$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-14","reactions":{}}