Performative Reinforcement Learning with Linear Markov Decision Process
作者: Debmalya Mandal, Goran Radanovic
分类: cs.LG, cs.GT
发布日期: 2024-11-07 (更新: 2025-03-14)
备注: In AISTATS-2025
💡 一句话要点
针对线性MDP下的Performative强化学习，提出重复正则化优化方法并证明其收敛性。
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: Performative强化学习 线性MDP 正则化优化 对偶理论 原始-对偶算法
📋 核心要点
- 传统强化学习忽略了策略部署对环境的影响，Performative RL关注策略改变环境动态的场景，但现有方法在状态空间大时计算复杂度高。
- 本文针对线性MDP，通过重复优化正则化目标，证明了算法能够收敛到performatively稳定的策略，并利用对偶解的线性组合进行收敛性分析。
- 论文提出了基于经验拉格朗日函数的原始-对偶算法，并在有界覆盖条件下证明了其收敛性，为解决实际问题提供了理论保障。
📝 摘要（中文）
本文研究了performative强化学习，其中部署的策略会影响底层马尔可夫决策过程的奖励和转移。先前的工作已经在表格设置下解决了这个问题，并建立了重复训练的最后一次迭代收敛性，其迭代复杂度明确地取决于状态的数量。本文将结果推广到线性马尔可夫决策过程，这是大规模MDP的主要理论模型。线性MDP的主要挑战是正则化目标不再是强凸的，并且我们希望边界随特征的维度缩放，而不是可能无限的状态。我们的第一个结果表明，重复优化正则化目标会收敛到performatively稳定的策略。在缺乏强凸性的情况下，我们的分析利用了一种新的递归关系，该关系使用最优对偶解的特定线性组合来证明收敛性。然后，我们处理有限样本设置，其中学习者可以访问从当前策略中抽取的一组轨迹。我们考虑原始问题的重新参数化版本，并构建一个经验拉格朗日函数，该函数将从样本中进行优化。我们表明，在有界覆盖条件下，重复求解该经验拉格朗日函数的鞍点会收敛到performatively稳定的解，并且还构建了一种原始-对偶算法，可以有效地求解经验拉格朗日函数。最后，我们展示了performative RL通用框架的几个应用，包括多智能体系统。
🔬 方法详解
问题定义：论文旨在解决performative强化学习在线性马尔可夫决策过程（Linear MDP）中的应用问题。传统的强化学习方法通常假设环境是静态的，策略的改变不会影响环境的动态。然而，在许多实际场景中，策略的部署会反过来影响环境的奖励函数和状态转移概率，例如交通流量控制、推荐系统等。现有的针对performative RL的方法，如基于表格型MDP的方法，在状态空间较大时计算复杂度过高，难以应用于大规模问题。
核心思路：论文的核心思路是通过重复优化一个正则化的目标函数，使得策略能够收敛到一个performatively稳定的状态。Performatively稳定是指在该策略下，环境的动态不再发生显著变化，从而达到一个平衡状态。为了应对线性MDP中正则化目标函数非强凸的挑战，论文引入了一种新的递归关系，利用最优对偶解的线性组合来证明收敛性。
技术框架：论文的技术框架主要包含两个部分：理论分析和算法设计。首先，论文在理论上证明了重复优化正则化目标函数能够收敛到performatively稳定的策略。其次，论文针对有限样本的情况，提出了一个基于经验拉格朗日函数的原始-对偶算法。该算法通过求解经验拉格朗日函数的鞍点来更新策略，并在有界覆盖条件下证明了其收敛性。
关键创新：论文最重要的技术创新在于针对线性MDP，提出了一种新的收敛性分析方法。由于线性MDP中正则化目标函数不再是强凸的，传统的收敛性分析方法不再适用。论文通过引入最优对偶解的线性组合，构建了一种新的递归关系，从而成功证明了算法的收敛性。此外，论文还提出了一个基于经验拉格朗日函数的原始-对偶算法，该算法能够有效地利用有限样本数据来更新策略。
关键设计：论文的关键设计包括正则化项的选择、经验拉格朗日函数的构建以及原始-对偶算法的实现。正则化项用于约束策略的复杂度，防止过拟合。经验拉格朗日函数是基于有限样本数据对真实拉格朗日函数的近似，其构建需要仔细考虑样本的偏差和方差。原始-对偶算法的设计需要保证算法的收敛性和计算效率。
📊 实验亮点
论文在理论上证明了重复优化正则化目标函数能够收敛到performatively稳定的策略，并提出了一个基于经验拉格朗日函数的原始-对偶算法。虽然论文没有提供具体的实验数据，但其理论分析为解决实际问题提供了重要的指导。
🎯 应用场景
该研究成果可应用于多智能体系统、推荐系统、交通流量控制等领域。在多智能体系统中，每个智能体的策略都会影响其他智能体的行为和环境的动态，因此需要考虑performative RL。在推荐系统中，推荐策略会影响用户的偏好和行为，从而改变推荐环境。在交通流量控制中，交通信号灯的控制策略会影响车辆的行驶速度和路线选择，从而改变交通流量的分布。
📄 摘要（原文）
We study the setting of \emph{performative reinforcement learning} where the deployed policy affects both the reward, and the transition of the underlying Markov decision process. Prior work~\parencite{MTR23} has addressed this problem under the tabular setting and established last-iterate convergence of repeated retraining with iteration complexity explicitly depending on the number of states. In this work, we generalize the results to \emph{linear Markov decision processes} which is the primary theoretical model of large-scale MDPs. The main challenge with linear MDP is that the regularized objective is no longer strongly convex and we want a bound that scales with the dimension of the features, rather than states which can be infinite. Our first result shows that repeatedly optimizing a regularized objective converges to a \emph{performatively stable policy}. In the absence of strong convexity, our analysis leverages a new recurrence relation that uses a specific linear combination of optimal dual solutions for proving convergence. We then tackle the finite sample setting where the learner has access to a set of trajectories drawn from the current policy. We consider a reparametrized version of the primal problem, and construct an empirical Lagrangian which is to be optimized from the samples. We show that, under a \emph{bounded coverage} condition, repeatedly solving a saddle point of this empirical Lagrangian converges to a performatively stable solution, and also construct a primal-dual algorithm that solves the empirical Lagrangian efficiently. Finally, we show several applications of the general framework of performative RL including multi-agent systems.