← 研踪 PaperTrailarXiv:2611.19566 · v1
Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL
首次提交 2026-11-15 02:57
版本更新 2026-11-15 02:57
雷达观测 2026-11-17 12:06
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-15 02:57 · 最新观测版本
Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL
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.
查看此版本解读 →查看此版本原文 ↗