发现蒙特卡洛探索起点算法会收敛到次优解,提出用按状态更新频率调学习率的方法恢复最优性。
Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts
- 构造反例证明初始访问型MCES会陷入次优解
- 通过按状态更新频率倒数调整学习率,确保收敛到最优策略
- 适用于大规模问题,揭示学习率与探索平衡的关键作用
蒙特卡洛探索起点(MCES)的渐近行为在强化学习中长期悬而未决,即使在表格型设置下也是如此。本文通过构建反例,揭示了初始访问和首次访问两种形式的MCES均可能收敛至次优解。研究发现,即使贪心动作的更新频率高于非贪心动作,使用样本平均更新的初始访问型MCES仍可能出现稳定次优解。通过在状态层面将学习率反比于更新频率进行调整,可保证收敛至最优。该方法无需全局均匀化,适用于需要近似值函数的大规模问题。进一步扩展表明,样本平均首次访问型MCES也可能收敛至次优解。这基本解决了这一基础性开放问题,说明仅靠探索起点不足以保证最优性。更广泛而言,收敛性高度依赖于不同动作更新的相对大小与频率,学习率选择及探索-利用平衡成为分析MCES与实现可扩展蒙特卡洛控制的核心。
原文摘要 · Abstract (English)
The asymptotic behaviour of Monte Carlo Exploring Starts (MCES) is a long-standing open question in reinforcement learning, even in the tabular setting. We investigated the convergence properties of tabular MCES by constructing examples in which the algorithm converges to suboptimal solutions. This paper presents new counterexamples for both initial-visit and first-visit MCES and gives a convergence-restoring modification for the initial-visit case. We show that stable suboptimal solutions may exist for initial-visit MCES with sample-average updates even when greedy actions are updated more often than non-greedy actions on average. However, by scaling learning rates inversely to update frequencies on a state-by-state basis, convergence to optimality is guaranteed. Unlike previous uniformisation methods, this modification is applicable to large-scale problems that require approximating the estimated value function. We then extend the example to show that sample-average first-visit MCES may also converge to suboptimal solutions. This largely settles a fundamental open problem and shows that exploring starts alone do not guarantee convergence to optimality. More broadly, these results highlight that convergence depends critically on the relative size and frequency of updates applied to different actions, making the choice of learning rates and the balance between exploration and exploitation central to the analysis of MCES and the implementation of scalable Monte Carlo control methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。