Megadose The AI curve, compressed.

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

· ArXiv · AI/CL/LG ·
Planning from sampled models matches the paper’s reinforcement-learning lower bounds up to constant factors.

Matthew Zurek and Yudong Chen study plug-in planning with a generative model that supplies samples. They show that discounted planning finds an ε-optimal policy using O(SA(1−γ)⁻³ε⁻² log(SA/δ)) samples. For average reward, they establish corresponding bounds governed by either the optimal bias span or the model’s diameter. Their Bellman residual bracketing technique sharpens earlier concentration analyses; paired with lower bounds for nonadaptive sampling, the results establish minimax sample complexity in all three settings.

ArXiv · AI/CL/LG's note

score 5

Categories: Research