为蒙特卡洛探索起点算法提供有限样本收敛性分析，给出最优策略的采样复杂度上界。
Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
- 改进的蒙特卡洛探索起点算法用于随机最短路径问题
- 以至少1-δ概率，在约SAK³log³(1/δ)次采样后得到最优策略
- 适用于关心算法收敛速度的研究者或强化学习理论工作者
蒙特卡洛探索起点（MCES）是一种仅利用样本回报学习最优策略的简单自然算法，在多种条件下已被证明收敛。然而，针对此类算法的收敛速率分析——特别是以样本复杂度形式呈现——至今关注甚少。本文为一种修正版的MCES算法建立了有限样本上界，该算法解决随机最短路径问题。为此，我们证明了策略迭代算法的一个新收敛速率结果。该结果表明：以至少1-δ的概率，算法在经历$ ilde{O}(SAK^3\ ext{log}^3\frac{1}{δ})$次采样轨迹后返回最优策略，其中$S$和$A$分别为状态数与动作数，$K$为路径长度的代理变量，$ ilde{O}$隐藏了依赖于环境奖励的对数因子和常数，假设奖励已知。
原文摘要 · Abstract (English)
Monte Carlo Exploring Starts (MCES), which aims to learn the optimal policy using only sample returns, is a simple and natural algorithm in reinforcement learning which has been shown to converge under various conditions. However, the convergence rate analysis for MCES-style algorithms in the form of sample complexity has received very little attention. In this paper we develop a finite sample bound for a modified MCES algorithm which solves the stochastic shortest path problem. To this end, we prove a novel result on the convergence rate of the policy iteration algorithm. This result implies that with probability at least $1-δ$, the algorithm returns an optimal policy after $\tilde{O}(SAK^3\log^3\frac{1}δ)$ sampled episodes, where $S$ and $A$ denote the number of states and actions respectively, $K$ is a proxy for episode length, and $\tilde{O}$ hides logarithmic factors and constants depending on the rewards of the environment that are assumed to be known.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。