提出高效算法实现表格马尔可夫决策过程最优策略识别。
Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes
- 结合后验采样与在线学习引导探索
- 样本复杂度达到渐近最优，计算开销为每回合O(S²AH)
- 适用于需要高精度策略识别的强化学习场景
我们研究有限时长远期马尔可夫决策过程中的(ε, δ)-PAC策略识别问题。现有方法在近似设置（ε>0）下虽有有限时间保证，但计算成本高且对log(1/δ)的依赖次优。本文提出一种随机化、计算高效的最优策略识别算法，结合后验采样与在线学习以指导马尔可夫决策过程中的探索。该方法在样本复杂度上达到渐近最优，同时在后验收缩速率上也最优，每回合运行时间为O(S²AH)，与标准模型基方法相当。相较于MOCA和PEDEL等先前算法，本方法在渐近范围内仍保持有效保证，避免了对log(1/δ)的次优多项式依赖。结果既提供理论洞见，也为表格MDPs中的高效策略识别提供了实用工具。
原文摘要 · Abstract (English)
We study the $(\varepsilon, δ)$-PAC policy identification problem in finite-horizon episodic Markov Decision Processes. Existing approaches provide finite-time guarantees for approximate settings ($\varepsilon>0$) but suffer from high computational cost, rendering them hard to implement, and also suffer from suboptimal dependence on $\log(1/δ)$. We propose a randomized and computationally efficient algorithm for best policy identification that combines posterior sampling with an online learning algorithm to guide exploration in the MDP. Our method achieves asymptotic optimality in sample complexity, also in terms of posterior contraction rate, and runs in $O(S^2AH)$ per episode, matching standard model-based approaches. Unlike prior algorithms such as MOCA and PEDEL, our guarantees remain meaningful in the asymptotic regime and avoid sub-optimal polynomial dependence on $\log(1/δ)$. Our results provide both theoretical insights and practical tools for efficient policy identification in tabular MDPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。