本文的重点是平均奖励强化学习算法的样本复杂度保证，这些算法比折扣奖励学习算法更难研究。据我们所知，我们提供了第一个已知的有限样本保证，使用恒定和递减步长（i）平均奖励TD（λ）和线性函数近似进行策略评估，以及（ii）在表格设置中的平均奖励Q-学习，以找到最优策略。一个主要的挑战是，由于值函数对加性常数是不可知的，因此相应的Bellman算子不再是任何范数下的压缩映射。我们通过在适当定义的子空间中工作来获得TD（λ）的结果，该子空间确保了解的唯一性。对于Q学习，我们利用Bellman算子的跨度半范数压缩性质，构造了一个新的Lyapunov函数，该函数是通过广义Moreau包络和集合的指示函数的内卷积获得的。
平均奖励设置是一种经典设置，用于在无限期马尔可夫决策过程（MDP）[1]中制定目标。在许多应用中，包括自动引导车辆调度[2]、供应链中的库存管理[3]、通信系统控制和路由[4]、多机器人协作学习[5]和排队网络控制[6]，都证明了最大化平均回报的必要性。在这些问题中，折扣奖励标准通常会导致长期绩效不佳，因为系统在较长时间内运行，目标是优化长期行为，而折扣目标会使最优政策偏向于选择导致短期绩效较高的行为。尽管有一个成熟的平均报酬MDPs理论[7，8，9]，但对平均报酬RL方法的理论理解仍然相当有限。大多数现有结果仅关注渐近收敛[10，11，12，13]。本文的重点是了解样本效率。需要多少数据才能保证给定的准确度？最近的文献通过开发新的分析技术获得了折扣奖励TD学习和Q学习算法的有限样本保证[14，15，16，17，18]。没有对平均RL算法进行这样的研究。对平均奖励RL算法的分析比对折扣奖励算法的研究更具挑战性。在折扣报酬问题的研究中所利用的关键性质是潜在Bellman算子的收缩性质。在平均报酬设置中，这种收缩性质在任何范数下都不成立，并且已知Bellman方程具有多个固定点。
Contributions and Summary of Our Techniques
我们利用线性函数近似和文献中的平均报酬表Q学习建立了平均报酬TD（λ）的第一个有限样本收敛保证。TD（λ）结果。我们研究了一般异步更新下线性函数近似下的平均报酬TD（λ）。我们给出了恒定步长和递减步长下的有限样本边界。在恒定步长的情况下，迭代以指数速率收敛到TD不动点集周围的小圆柱。在适当选择步长减小的情况下，迭代到TD不动点集的均方距离以O~1T速率收敛，这导致样本复杂度为O~12。我们的样本复杂度界还表明，中间值λ产生最佳性能。对有效视界的依赖性在折扣奖励RL算法的研究中起着关键作用[19，20]。在平均报酬问题中没有这样的有效视界，而适当定义的矩阵的频谱间隙起着关键作用。TD（λ）分析。分析中的一个主要挑战是，预测的贝尔曼算子在任何规范下都不是收缩。此外，即使投影的Bellman方程可以写成一组线性方程，它们也是欠定的。因此现有技术[14，15]不直接适用。由于该值函数在加性常数之前是唯一的，因此当被限制在适当定义的子空间时，我们得到了投影Bellman方程的唯一解。我们利用这一特性并在该子空间中工作，并使用二次李亚普诺夫函数来获得有限样本保证。Q学习结果。我们考虑一种J步同步Q学习算法。我们给出了恒定步长和递减步长的有限样本误差界。向量的跨度被定义为最大元素和最小元素之间的差值。由于最优作用值函数Q∗ , 在加性常数下是不可知的，我们表明，对于最多O（1/2）个样本，误差QT的预期跨度− Q∗ 对于减小步长和恒定步长，收敛到。Q学习分析。虽然相应的Bellman算子在任何范数下都不是收缩，但已知它在跨度半范数下是收缩。跨度半范数可以解释为`∞-到全一向量所跨越的子空间的距离。随机逼近的有限样本界`∞-在[18]中，利用广义Moreau包络作为光滑Lyapunov函数得到了范数压缩算子。在这里，我们推广了这一方法，并引入了一个新的Lyapunov函数来研究跨度半范数压缩算子。
