通过局部近似降低强化学习采样复杂度，提升学习效率。
Improving Reinforcement Learning Sample-Efficiency using Local Approximation
- 用局部状态子集构建小规模MDP，减少采样需求。
- 理论证明采样复杂度降至O(SA log A)步，对数级优化。
- 适用于状态相关性局部的无限时域强化学习任务。
本研究在无限时域马尔可夫决策过程（MDP）框架下，推导出强化学习（RL）渐近采样复杂度的更紧致的可能近似正确（PAC）界，优于现有文献。核心思想是：状态间转移距离越远，其值函数相关性越弱；且学习某一状态的ε-最优值所需样本量，与远离它的另一状态的学习样本量无关。相反，邻近状态的值相互依赖，需相近样本量学习。通过用原状态空间的子集构造更小的MDP，将采样复杂度降低一个对数因子至O(SA log A)时间步，其中S和A分别为状态空间和动作空间大小。进一步在无模型无限时域设置中，构造出具有上述复杂度的PAC-MDP算法。实验表明该方法相比以往工作有显著性能提升。
原文摘要 · Abstract (English)
In this study, we derive Probably Approximately Correct (PAC) bounds on the asymptotic sample-complexity for RL within the infinite-horizon Markov Decision Process (MDP) setting that are sharper than those in existing literature. The premise of our study is twofold: firstly, the further two states are from each other, transition-wise, the less relevant the value of the first state is when learning the $ε$-optimal value of the second; secondly, the amount of 'effort', sample-complexity-wise, expended in learning the $ε$-optimal value of a state is independent of the number of samples required to learn the $ε$-optimal value of a second state that is a sufficient number of transitions away from the first. Inversely, states within each other's vicinity have values that are dependent on each other and will require a similar number of samples to learn. By approximating the original MDP using smaller MDPs constructed using subsets of the original's state-space, we are able to reduce the sample-complexity by a logarithmic factor to $O(SA \log A)$ timesteps, where $S$ and $A$ are the state and action space sizes. We are able to extend these results to an infinite-horizon, model-free setting by constructing a PAC-MDP algorithm with the aforementioned sample-complexity. We conclude with showing how significant the improvement is by comparing our algorithm against prior work in an experimental setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。