Abstract
A common technique in reinforcement learning is to evaluate the value function from Monte Carlo simulations of a given policy, and use the estimated value function to obtain a new policy which is greedy with respect to the estimated value function. A well-known longstanding open problem in this context is to prove the convergence of such a scheme when the value function of a policy is estimated from data collected from a single sample path obtained from implementing the policy (see page 99 of [Sutton and Barto, 2018], page 8 of [Tsitsiklis, 2002]). We present a solution to the open problem by showing that a first-visit version of such a policy iteration scheme indeed converges to the optimal policy provided that the policy improvement step uses lookahead [Silver et al., 2016, Mnih et al., 2016, Silver et al., 2017b] rather than a simple greedy policy improvement. We provide results both for the original open problem in the tabular setting and also present extensions to the function approximation setting, where we show that the policy resulting from the algorithm performs close to the optimal policy within a function approximation error.
Abstract (translated)
强化学习中常见的一种方法是从蒙特卡罗模拟中评估给定策略的价值函数,并使用估计的价值函数得到一个新的策略,该策略对估计的价值函数具有贪婪性质。该领域著名的长期开放性问题之一是证明这种方案的收敛性,当策略的价值函数通过从实施策略的单个样本路径收集数据进行估计(见Sutton和Barto(2018)页99和Tsitsiklis(2002)页8)时(见本报告的页眉)。我们提出了解决该开放性问题的方案,并通过证明这种方案的第一访问版本确实收敛到最优策略,只要策略改进步骤使用未来观察(Silver等,2016,Mnih等,2016,Silver等,2017b)而不是简单的贪婪策略改进。我们既提供了表格环境中的原始开放性问题的解,也提供了函数逼近环境中的扩展,在那里我们表明,算法的结果在函数逼近误差内与最优策略的性能相当。
URL
https://arxiv.org/abs/2301.09709
