放松了蒙特卡洛乐观策略迭代的收敛条件,让算法更实用。
Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates
- 只需在每状态内均匀更新动作,无需全局状态均匀采样
- 证明了初始访问版本的算法仍能收敛到最优策略
- 适合大规模或未知状态空间的实际强化学习场景
蒙特卡洛乐观策略迭代(MC-O-PI)的渐近行为长期悬而未决。当环境模型未知时,现有唯一能保证收敛到最优的条件不切实际——要求用于策略评估的轨迹在全状态-动作空间上均匀初始化。本文严格放宽此要求:证明了初始访问形式的MC-O-PI即使仅在每个状态内均匀更新动作,也能收敛至最优策略。这允许轨迹在不同状态下以任意频率启动,适用于状态空间大或未知但每状态动作空间可控的情况。传统分析依赖于状态更新频率一致的对易性假设,现已被打破。本文通过构建均值场动态,证明在动作内均匀更新下策略单调提升,并扩展联合稳定性-微分方程方法中的锁死论证,证明噪声无法持续阻碍改进。该方法为研究乐观策略迭代算法提供了新视角。
原文摘要 · Abstract (English)
The asymptotic behaviour of Monte Carlo optimistic policy iteration (MC-O-PI) is a long-standing open question. When the model of the environment is unknown, as is common in practice, the only known condition that guarantees convergence to optimality is impractical. In its canonical form, this condition requires that the episodes used for policy evaluation be initialised uniformly over the entire state-action space. This paper strictly relaxes that requirement. Specifically, we prove that initial-visit MC-O-PI converges to optimality even when updates are uniform only over the actions within each state. This allows episodes to start in different states at arbitrary frequencies; a realistic implementation when the state space is large or unknown but the action space in each state is manageable. The proof departs from the classical analysis of Tsitsiklis whose central commutativity argument no longer applies when states are updated at different frequencies. Instead, we first show that the mean-field dynamics of MC-O-PI generate monotonically improving policies when updates are uniform over the actions in each state, and then prove that noise cannot consistently prevent this improvement by extending the lock-in argument of the combined stability-ODE method. This approach suggests a new way to study optimistic policy-iteration algorithms in general.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。