Online Episodic Convex Reinforcement Learning

📄 arXiv: 2505.07303v1 📥 PDF

作者: Bianca Marin Moreno, Khaled Eldowa, Pierre Gaillard, Margaux Brégère, Nadia Oudjane

分类: cs.LG, stat.ML

发布日期: 2025-05-12

💡 一句话要点

提出在线情景凸强化学习算法，解决具有凸目标函数的MDP在线学习问题

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

关键词: 强化学习 在线学习 凸优化 马尔可夫决策过程 遗憾界

📋 核心要点

  1. 传统强化学习方法在处理具有凸目标函数的MDP时失效，因为CURL的非线性特性使得贝尔曼方程不再适用。
  2. 论文提出一种基于在线镜像下降的算法，结合变化的约束集和探索奖励，以实现近乎最优的遗憾界。
  3. 论文还首次研究了CURL的bandit版本，通过调整bandit凸优化技术，实现了次线性遗憾界。

📝 摘要（中文）

本文研究了具有凸目标函数的在线情景有限视界马尔可夫决策过程（MDP）中的在线学习问题，即凹效用强化学习（CURL）问题。这种设置将强化学习从线性损失推广到代理策略诱导的状态-动作分布上的凸损失。CURL的非线性使得经典的贝尔曼方程失效，并需要新的算法方法。我们提出了第一个算法，在没有关于转移函数的任何先验知识的情况下，实现了在线CURL的近乎最优的遗憾界。为了实现这一点，我们使用了一种具有变化的约束集和精心设计的探索奖励的在线镜像下降算法。然后，我们首次解决了CURL的bandit版本，其中唯一的反馈是代理策略诱导的状态-动作分布上的目标函数的值。通过将bandit凸优化技术应用于MDP设置，我们为这个更具挑战性的问题实现了次线性遗憾界。

🔬 方法详解

问题定义：论文旨在解决在线情景有限视界马尔可夫决策过程（MDP）中，目标函数为凸函数时的在线学习问题，即凹效用强化学习（CURL）问题。现有强化学习方法主要针对线性损失，无法直接应用于CURL，因为CURL的非线性特性使得经典的贝尔曼方程失效。这导致了探索-利用的权衡变得更加复杂，难以保证算法的收敛性和最优性。

核心思路：论文的核心思路是利用在线凸优化的框架来解决CURL问题。具体来说，将策略学习问题转化为一个在线凸优化问题，并使用在线镜像下降算法进行求解。为了平衡探索和利用，算法引入了变化的约束集和精心设计的探索奖励。通过这种方式，算法能够在没有关于转移函数的任何先验知识的情况下，实现近乎最优的遗憾界。对于bandit CURL，则借鉴bandit凸优化的思想，适应MDP环境。

技术框架：整体框架包括以下几个主要步骤：1）在每个episode中，agent根据当前的策略选择动作；2）环境返回状态转移和奖励；3）agent根据观测到的状态转移和奖励，更新策略。策略更新采用在线镜像下降算法，其中约束集和探索奖励会随着episode的进行而变化。对于bandit CURL，agent只能观察到目标函数的值，因此需要更精细的探索策略。

关键创新：论文的关键创新在于：1）提出了第一个针对在线CURL的算法，该算法能够在没有关于转移函数的任何先验知识的情况下，实现近乎最优的遗憾界；2）首次解决了CURL的bandit版本，并实现了次线性遗憾界；3）将在线镜像下降算法与变化的约束集和探索奖励相结合，有效地解决了探索-利用的权衡问题。

关键设计：算法的关键设计包括：1）约束集的设计：约束集用于限制策略的搜索空间，以保证算法的收敛性。约束集会随着episode的进行而变化，以适应环境的变化；2）探索奖励的设计：探索奖励用于鼓励agent探索未知的状态-动作对，以提高算法的探索能力。探索奖励的设计需要仔细权衡，以避免过度探索或探索不足；3）在线镜像下降算法的参数设置：在线镜像下降算法的参数设置会影响算法的收敛速度和性能。论文中对这些参数进行了仔细的调整和优化。

🖼️ 关键图片

img_0

📊 实验亮点

论文的主要实验结果表明，所提出的算法能够在在线CURL和bandit CURL问题上实现近乎最优的遗憾界和次线性遗憾界。具体来说，对于在线CURL，算法的遗憾界为O(sqrt(T))，其中T是episode的数量。对于bandit CURL，算法的遗憾界为O(T^(2/3))。这些结果表明，所提出的算法在理论上和实践上都具有优越的性能。

🎯 应用场景

该研究成果可应用于具有凸目标函数的强化学习任务，例如资源分配、风险管理和投资组合优化等领域。在这些领域中，目标函数通常是非线性的，传统的强化学习方法难以有效应用。该研究为解决这些问题提供了一种新的思路和方法，具有重要的实际应用价值和潜在的未来影响。

📄 摘要（原文）

We study online learning in episodic finite-horizon Markov decision processes (MDPs) with convex objective functions, known as the concave utility reinforcement learning (CURL) problem. This setting generalizes RL from linear to convex losses on the state-action distribution induced by the agent's policy. The non-linearity of CURL invalidates classical Bellman equations and requires new algorithmic approaches. We introduce the first algorithm achieving near-optimal regret bounds for online CURL without any prior knowledge on the transition function. To achieve this, we use an online mirror descent algorithm with varying constraint sets and a carefully designed exploration bonus. We then address for the first time a bandit version of CURL, where the only feedback is the value of the objective function on the state-action distribution induced by the agent's policy. We achieve a sub-linear regret bound for this more challenging problem by adapting techniques from bandit convex optimization to the MDP setting.