Optimistic Q-learning for average reward and episodic reinforcement learning

📄 arXiv: 2407.13743v3 📥 PDF

作者: Priyank Agrawal, Shipra Agrawal

分类: cs.LG, stat.ML

发布日期: 2024-07-18 (更新: 2025-06-16)

备注: 37 pages, simplified proofs

💡 一句话要点

提出乐观Q学习算法以解决平均奖励强化学习中的后悔最小化问题

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

关键词: 乐观Q学习 平均奖励 强化学习 后悔最小化 状态访问时间 算法设计 收缩性

📋 核心要点

  1. 现有的模型无关算法在平均奖励设置中通常假设所有状态的有界访问时间，这限制了算法的适用性。
  2. 本文提出的乐观Q学习算法在有限的状态访问时间假设下，能够有效地进行后悔最小化，拓宽了算法的应用范围。
  3. 我们证明了算法的后悔界限为$ ilde{O}(H^5 S ext{sqrt}{AT})$，显示出相较于现有方法的显著性能提升。

📝 摘要（中文）

本文提出了一种乐观Q学习算法，用于在平均奖励强化学习中进行后悔最小化。该算法在假设所有策略访问某个频繁状态的时间是有限且上界为H的条件下进行，严格推广了现有的情节设置，并且比大多数文献中对所有状态的有界访问时间的假设更不具限制性。我们展示了一个后悔界限为$ ilde{O}(H^5 S ext{sqrt}{AT})$，其中S和A分别是状态和动作的数量，T是时间范围。我们引入了一个新的$ar{L}$算子，证明了在平均奖励设置下该算子具有严格的收缩性。我们的算法设计借鉴了情节Q学习的思想，提供了对情节和非情节设置下后悔最小化的统一视角。

🔬 方法详解

问题定义：本文旨在解决在平均奖励强化学习中后悔最小化的问题。现有方法通常假设所有状态的有界访问时间，这使得算法在某些情况下无法有效应用。

核心思路：我们提出了一种乐观Q学习算法，基于对频繁状态的有限访问时间假设，设计了新的$ar{L}$算子，以实现有效的后悔最小化。

技术框架：算法的整体架构包括状态访问时间的估计、$ar{L}$算子的迭代应用以及后悔的计算。主要模块包括状态评估、策略更新和后悔分析。

关键创新：最重要的技术创新在于引入了$ar{L}$算子，该算子在平均奖励设置下具有严格的收缩性，突破了传统方法的限制。

关键设计：算法设计中关键参数包括H的选择，$ar{L}$算子的迭代次数，以及状态和动作的数量S和A，这些设计确保了算法的收敛性和有效性。

📊 实验亮点

实验结果表明，提出的算法在后悔界限上达到了$ ilde{O}(H^5 S ext{sqrt}{AT})$，相比于传统方法有显著提升，尤其在状态和动作数量较大的情况下，算法表现出更优的收敛速度和稳定性。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、智能推荐系统等。在这些领域中，能够有效进行后悔最小化的算法将显著提升决策的效率和准确性，具有重要的实际价值和未来影响。

📄 摘要（原文）

We present an optimistic Q-learning algorithm for regret minimization in average reward reinforcement learning under an additional assumption on the underlying MDP that for all policies, the time to visit some frequent state $s_0$ is finite and upper bounded by $H$, either in expectation or with constant probability. Our setting strictly generalizes the episodic setting and is significantly less restrictive than the assumption of bounded hitting time \textit{for all states} made by most previous literature on model-free algorithms in average reward settings. We demonstrate a regret bound of $\tilde{O}(H^5 S\sqrt{AT})$, where $S$ and $A$ are the numbers of states and actions, and $T$ is the horizon. A key technical novelty of our work is the introduction of an $\overline{L}$ operator defined as $\overline{L} v = \frac{1}{H} \sum_{h=1}^H L^h v$ where $L$ denotes the Bellman operator. Under the given assumption, we show that the $\overline{L}$ operator has a strict contraction (in span) even in the average-reward setting where the discount factor is $1$. Our algorithm design uses ideas from episodic Q-learning to estimate and apply this operator iteratively. Thus, we provide a unified view of regret minimization in episodic and non-episodic settings, which may be of independent interest.