Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm

📄 arXiv: 2410.23498v1 📥 PDF

作者: Sattar Vakili, Julia Olkhovskaya

分类: cs.LG, cs.AI, stat.ML

发布日期: 2024-10-30

备注: 38th Conference on Neural Information Processing Systems (NeurIPS 2024)

💡 一句话要点

提出基于核函数的平均奖励强化学习乐观无悔算法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 强化学习 平均奖励 核方法 函数逼近 无悔学习

📋 核心要点

  1. 现有强化学习方法在处理连续状态空间时面临挑战，需要有效的函数逼近方法。
  2. 论文提出一种基于核函数的乐观强化学习算法，利用核岭回归预测期望价值函数。
  3. 该算法在平均奖励强化学习环境中实现了无悔性能，并推导了新的置信区间。

📝 摘要（中文）

本文研究了基于核岭回归的强化学习方法，用于预测期望价值函数，该方法具有强大的表征能力。我们考虑了无限视界平均奖励强化学习（也称为无折扣设置）中基于核函数的函数逼近。我们提出了一种乐观算法，类似于bandit算法中基于采集函数的算法。在基于核函数的建模假设下，我们为该算法建立了新的无悔性能保证。此外，我们还推导了一种新的基于核函数的期望价值函数预测的置信区间，适用于各种强化学习问题。

🔬 方法详解

问题定义：论文旨在解决无限视界平均奖励强化学习问题，即在没有折扣因子的情况下，最大化长期平均奖励。现有方法在处理大规模状态空间时，计算复杂度高，难以保证收敛性和无悔性。核方法虽然具有强大的函数逼近能力，但在平均奖励强化学习中的应用还不够成熟。

核心思路：论文的核心思路是利用核岭回归来逼近期望价值函数，并结合乐观策略选择，以探索未知的状态-动作空间。通过构建置信区间，算法能够平衡探索和利用，从而实现无悔学习。乐观策略鼓励算法选择那些具有较高期望价值，但同时不确定性也较高的动作。

技术框架：该算法主要包含以下几个阶段：1) 使用核岭回归估计期望价值函数；2) 基于估计的期望价值函数和置信区间，计算每个动作的乐观价值；3) 选择具有最高乐观价值的动作；4) 观察奖励和下一个状态，并更新价值函数估计。整个过程迭代进行，直到达到收敛或达到预定的迭代次数。

关键创新：论文的关键创新在于：1) 提出了适用于平均奖励强化学习的基于核函数的乐观算法；2) 推导了基于核函数的期望价值函数预测的新的置信区间，该置信区间考虑了平均奖励设置的特殊性；3) 证明了该算法在核函数建模假设下具有无悔性能，即算法的累积遗憾随着时间增长的速度低于线性增长。

关键设计：算法的关键设计包括：1) 核函数的选择，例如高斯核或多项式核，影响了函数逼近的精度和泛化能力；2) 正则化参数的选择，控制了模型的复杂度，避免过拟合；3) 置信区间的计算方式，影响了探索和利用的平衡；4) 学习率的设置，影响了价值函数估计的收敛速度。

📊 实验亮点

论文提出了基于核函数的平均奖励强化学习算法，并证明了其无悔性能。通过构建新的置信区间，算法能够有效地平衡探索和利用。虽然论文中没有提供具体的实验数据，但理论分析表明该算法在核函数建模假设下具有良好的性能。

🎯 应用场景

该研究成果可应用于各种需要长期决策的场景，例如机器人导航、资源管理、推荐系统等。通过学习最优策略，智能体能够在复杂环境中实现长期目标的优化。该方法尤其适用于状态空间连续且难以精确建模的场景，例如自动驾驶和金融交易。

📄 摘要（原文）

Reinforcement learning utilizing kernel ridge regression to predict the expected value function represents a powerful method with great representational capacity. This setting is a highly versatile framework amenable to analytical results. We consider kernel-based function approximation for RL in the infinite horizon average reward setting, also referred to as the undiscounted setting. We propose an optimistic algorithm, similar to acquisition function based algorithms in the special case of bandits. We establish novel no-regret performance guarantees for our algorithm, under kernel-based modelling assumptions. Additionally, we derive a novel confidence interval for the kernel-based prediction of the expected value function, applicable across various RL problems.