无需预知最优偏差跨度，实现平均奖励强化学习最优样本复杂度。
Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL
- 通过自适应调节有效时域，结合折扣化归约与置信区间校准。
- 在固定数据集或固定误差下，达到最优的 ‘ ilde{O}(SAH/ε^2)’ 复杂度。
- 可自动识别低跨度近优策略，适合结构良好的环境使用。
我们研究了在生成模型下，寻找平均奖励马尔可夫决策过程（MDP）中 ε-最优策略的样本复杂度。已知最优的基于跨度的复杂度为 ‘ ilde{O}(SAH/ε^2)’，其中 H 为最优偏差函数的跨度，但此前仅能在已知 H 值的前提下实现。无先验知识的算法长期是研究重点，但多种自然方法被证明无法达成目标。本文首次提出无需 H 知识即可匹配最优复杂度的算法，适用于数据集大小固定或子优性水平 ε 固定的情形。核心技术结合折扣化归约与基于经验置信区间或性能下界的时域自动校准机制，称为时域校准。此外，我们还设计了一种受样本方差惩罚启发的实证跨度惩罚方法，满足一个奥拉克不等式性能保证；特别地，该算法在存在跨度远小于 H 的近优策略时，可超越最小最大复杂度。
原文摘要 · Abstract (English)
We study the sample complexity of finding an $\varepsilon$-optimal policy in average-reward Markov Decision Processes (MDPs) with a generative model. The minimax optimal span-based complexity of $\widetilde{O}(SAH/\varepsilon^2)$, where $H$ is the span of the optimal bias function, has only been achievable with prior knowledge of the value of $H$. Prior-knowledge-free algorithms have been the objective of intensive research, but several natural approaches provably fail to achieve this goal. We resolve this problem, developing the first algorithms matching the optimal span-based complexity without $H$ knowledge, both when the dataset size is fixed and when the suboptimality level $\varepsilon$ is fixed. Our main technique combines the discounted reduction approach with a method for automatically tuning the effective horizon based on empirical confidence intervals or lower bounds on performance, which we term horizon calibration. We also develop an empirical span penalization approach, inspired by sample variance penalization, which satisfies an oracle inequality performance guarantee. In particular this algorithm can outperform the minimax complexity in benign settings such as when there exist near-optimal policies with span much smaller than $H$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。