提出一种自适应求解函数逼近强化学习的新算法，样本效率更高。
Adaptive Resolving Methods for Reinforcement Learning with Function Approximations
- 基于线性规划重构，每轮迭代结合新数据重解优化问题。
- 在N组数据下，误差可降至约1/N，优于传统方法的1/√N。
- 适合数据丰富且结构有利的任务，尤其适用于在线决策场景。
强化学习（RL）在在线决策中具有基础性作用，常用于求解马尔可夫决策过程（MDPs）的最优策略。当状态-动作空间巨大或无限时，通常采用函数逼近。本文研究带有函数逼近的强化学习问题，提出一种新算法：基于线性规划（LP）重构，在每轮迭代中利用新增数据重新求解该LP。这种求解机制使得算法获得实例相关的样本复杂度保证——当有 $N$ 组数据时，输出策略的次优差距为 $ ilde{O}(1/N)$。相比此前文献中的 $O(1/ ext{√}N)$ 最坏情况保证，本方法在实例有利时更紧致。数值实验也验证了算法在实际中的高效表现。
原文摘要 · Abstract (English)
Reinforcement learning (RL) problems are fundamental in online decision-making and have been instrumental in finding an optimal policy for Markov decision processes (MDPs). Function approximations are usually deployed to handle large or infinite state-action space. In our work, we consider the RL problems with function approximation and we develop a new algorithm to solve it efficiently. Our algorithm is based on the linear programming (LP) reformulation and it resolves the LP at each iteration improved with new data arrival. Such a resolving scheme enables our algorithm to achieve an instance-dependent sample complexity guarantee, more precisely, when we have $N$ data, the output of our algorithm enjoys an instance-dependent $\tilde{O}(1/N)$ suboptimality gap. In comparison to the $O(1/\sqrt{N})$ worst-case guarantee established in the previous literature, our instance-dependent guarantee is tighter when the underlying instance is favorable, and the numerical experiments also reveal the efficient empirical performances of our algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。