通过最优面的定价运动：非平稳对抗性MDP的法扇几何

# 通过最优面定价运动：非平稳对抗MDP的法扇几何
来源：https://arxiv.org/html/2606.29092

###### 摘要

在变化的决策问题中，标准的动态遗憾分析常将非平稳性的代价等同于损失移动的距离。然而，损失序列可能移动很远却保持相同的最优策略，也可能损失微小的移动就迫使最优策略完全改变。因此，通过损失变化、转移变化或比较器路径长度衡量的运动大小描述的是对手的运动，而不是这种运动对控制问题造成的代价。为了更准确地进行解析解释，本文为具有固定转移的有限时域对抗MDP开发了一种法扇几何。占据测度构成一个多面体，每个损失向量暴露该多面体的一个最优面。奖励的非平稳性因此是穿过法扇的一条路径，其中在一个锥体内的移动不改变最优面，而穿越一个“墙”可能带来遗憾。我们提出了“穿面价格”的概念，即在新损失下停留在先前最优面上所产生的最小遗憾。对于任何跟踪先前最优面的学习器，动态遗憾准确分解为内在的面运动价格加上面内选择误差。由此产生的理论将有害的非平稳性与无害的非平稳性区分开，其中损失变化在零价格下可以任意大，而相同的一坐标变化可能隐藏时域尺度的遗憾差异。

## 1 引言

考虑推荐系统(Schafer et al., 1999 (https://arxiv.org/html/2606.29092#bib.bib57))，它根据学习到的用户偏好向用户提供个性化推荐。用户与该系统的交互是顺序的，每次用户操作后，推荐系统决定推荐什么。我们可以将此问题建模为一个平稳马尔可夫决策过程(MDP) (Puterman, 2014 (https://arxiv.org/html/2606.29092#bib.bib36); Shani et al., 2015 (https://arxiv.org/html/2606.29092#bib.bib58))，试图学习用户偏好(rr)以及用户交互的演变规律(P(s′∣s,a)P(s^{\prime}\mid s,a))。然而，用户的偏好是在不断变化的，我们不能假设从一轮到下一轮相同的状态-动作会产生相同的奖励(Huleihel et al., 2021 (https://arxiv.org/html/2606.29092#bib.bib56))。

在固定转移的非平稳强化学习设置中，最优策略会随着奖励和损失的变化而漂移。现有的分析通过预算损失变化或比较器路径来限制动态遗憾(Besbes et al., 2015 (https://arxiv.org/html/2606.29092#bib.bib4); Zhao et al., 2024 (https://arxiv.org/html/2606.29092#bib.bib50); Fei et al., 2020 (https://arxiv.org/html/2606.29092#bib.bib13); Zhao et al., 2022 (https://arxiv.org/html/2606.29092#bib.bib48))，但这些度量是外在于控制问题的。也就是说，这样的预算仅捕捉变化的大小，而单凭这些大小并不能决定学习器所付出的代价。

举个例子，我们可以构造两个案例，其中损失位移与代价成反比。在一个案例中，损失移动很远，但最优策略保持不变，这意味着平稳学习器无需付出任何代价。在另一个案例中，一小步就跨越了决策边界，将最优策略翻转到问题的远端，导致平稳学习器付出量级为时域长度的遗憾。对于推荐系统案例，假设两个电影推荐策略具有相同的遗憾，一个推荐纪录片，一个推荐爱情喜剧。在“纪录片仍然最佳”区域内，最优策略不变，那里大的奖励移动几乎不产生代价。相反，微小的偏好变化可能将用户移过无差异边界，使得旧的“纪录片仍然最佳”策略系统性错误，如果学习器保持平稳，则会导致很大的遗憾。

MDP的占据表示提供了决策区域的几何形式化(Puterman, 2014 (https://arxiv.org/html/2606.29092#bib.bib36); Altman, 2021 (https://arxiv.org/html/2606.29092#bib.bib3))。对于固定的转移核，每个策略诱导一个占据测度，即状态-动作对上的期望访问频率向量。有几个性质使得占据测度成为解决上述变化差异问题的解。首先，共享同一占据测度的策略在每个损失下都达到相等的值Vπ(l)V^{\pi}(\ell)，使占据测度成为值的充分统计量。其次，期望损失是这个向量的线性函数。因此，策略集可以由一个凸占据多面体表示，并且使得给定策略是最优的损失区域是该多面体的一个法锥。当损失旋转时，最优面在法锥内保持不变，只有当损失穿过一个“墙”时才改变。这些锥的集合对应于占据多面体的所有唯一面，被称为法扇，它是将每个损失映射到其最优面的地图(Ziegler, 1995 (https://arxiv.org/html/2606.29092#bib.bib51); Rockafellar, 1970 (https://arxiv.org/html/2606.29092#bib.bib38); Lu and Robinson, 2008 (https://arxiv.org/html/2606.29092#bib.bib28))。

当损失保持在一个锥内且最优面固定时，持有该面的学习器无论损失变化如何都不会付出遗憾。只有当损失进入一个锥，其最优面排除了学习器的占据时，才会产生代价。在这种情况下，在新损失下持有先前的优化面，在其各点上达到最小遗憾。因此，通过搜索整个法扇，我们可以准确定价损失的运动。然而，这种搜索是一个组合问题，枚举起来不可行。在本文中，我们证明实际上不需要任何搜索。该价格等于当前损失下的期望最优Bellman优势，相对于该损失诱导的最优值函数。该优势沿着一轮前最优的策略累积。一次值备份就提供了这些优势，剩下的最小化只在先前最优面上进行，而学习器已经持有该面。

参见图说明图1：占据面和法锥。左图：占据多面体，其面是最优占据的候选集。右图：损失空间中的法扇，它根据每个损失选择的面将损失划分为锥体。在一个锥体内的损失路径不改变最优面且是免费的，而穿过一个墙的路径会改变最优面并且可能是昂贵的。

##### 贡献。

1. 1.我们定义了穿面价格，即在新损失下停留在先前最优面上的代价，并证明了对于持有该面的学习器，动态遗憾精确地分解为该价格和面内选择误差（定理1 (https://arxiv.org/html/2606.29092#Thmtheorem1)）。
2. 2.我们证明了在任何有限时域MDP中，该价格等于在一轮前最优的策略上的最小期望最优Bellman优势（定理3 (https://arxiv.org/html/2606.29092#Thmtheorem3)），因此对旧面进行一次值备份即可直接计算它。
3. 3.我们建立了三个推论。首先，损失变化在零价格下可以任意大，并且在固定变化下它可以隐藏因子HH（命题1 (https://arxiv.org/html/2606.29092#Thmproposition1)和定理2 (https://arxiv.org/html/2606.29092#Thmtheorem2)）。其次，在时域早期被迫的穿越比晚期穿越代价更高，因子为H−h+1H-h+1（推论1 (https://arxiv.org/html/2606.29092#Thmcorollary1)）。最后，退化最优面留下一个价格无法吸收的选择误差（命题7 (https://arxiv.org/html/2606.29092#Thmproposition7)）。

一个全信息锥检测器（命题4 (https://arxiv.org/html/2606.29092#Thmproposition4)）以及对镜像下降和信任区域更新作为法扇近似跟踪器的补充解读出现在附录中。我们在第7节 (https://arxiv.org/html/2606.29092#S7)中通过三个经验基准测试验证了我们的理论。

## 2 相关工作

##### 占据测度与控制几何。

在已知转移的情况下，占据测度将策略优化转化为多面体上的线性优化。这种对应关系源于动态规划的线性规划观点 (Puterman, 2014 (https://arxiv.org/html/2606.29092#bib.bib36); Altman, 2021 (https://arxiv.org/html/2606.29092#bib.bib3))。在线和对抗MDP算法直接利用这一观点，通过相对熵策略搜索和归约到多面体上的在线凸优化 (Even-Dar et al., 2009 (https://arxiv.org/html/2606.29092#bib.bib12); Neu et al., 2010 (https://arxiv.org/html/2606.29092#bib.bib33); Zimin and Neu, 2013 (https://arxiv.org/html/2606.29092#bib.bib52); Rosenberg and Mansour, 2019 (https://arxiv.org/html/2606.29092#bib.bib39))。另一条并行线研究这种表示在策略空间上施加的几何结构，通过值函数多面体 (Dadashi et al., 2019 (https://arxiv.org/html/2606.29092#bib.bib9))、约束和逆强化学习的凸分析结构 (Schlaginhaufen and Kamgarpour, 2023 (https://arxiv.org/html/2606.29092#bib.bib40))，以及演员-评论家方法的占据流形解读 (Milosevic and Scherf, 2025 (https://arxiv.org/html/2606.29092#bib.bib30); Müller and Montúfar, 2024 (https://arxiv.org/html/2606.29092#bib.bib31))。本文的几何结构旨在衡量这些暴露面如何移动以及其移动的代价。

##### 动态遗憾与非平稳性。

动态遗憾将学习器与移动的比较器进行比较，并将差距用比较器运动的一种度量来界定，这一思想源于在线凸优化 (Zinkevich, 2003 (https://arxiv.org/html/2606.29092#bib.bib54); Hall and Willett, 2013 (https://arxiv.org/html/2606.29092#bib.bib14); Jadbabaie et al., 2015 (https://arxiv.org/html/2606.29092#bib.bib18); Eshraghi and Liang, 2022 (https://arxiv.org/html/2606.29092#bib.bib11); Zhao et al., 2020 (https://arxiv.org/html/2606.29092#bib.bib49); 2024 (https://arxiv.org/html/2606.29092#bib.bib50)) 和非平稳随机优化 (Besbes et al., 2015 (https://arxiv.org/html/2606.29092#bib.bib4))。这一思想已被非平稳和对抗MDP所采用 (Cheung et al., 2020 (https://arxiv.org/html/2606.29092#bib.bib8); Fei et al., 2020 (https://arxiv.org/html/2606.29092#bib.bib13); Zhao et al., 2022 (https://arxiv.org/html/2606.29092#bib.bib48); Li et al., 2023 (https://arxiv.org/html/2606.29092#bib.bib25); 2024b (https://arxiv.org/html/2606.29092#bib.bib27); Dick et al., 2015 (https://arxiv.org/html/2606.29092#bib.bib10); Cardoso et al., 2019 (https://arxiv.org/html/2606.29092#bib.bib6))。这些结果通过比较器路径长度或奖励与转移变化来界定遗憾。与我们最接近的占据路径长度界限 (Zhao et al., 2022 (https://arxiv.org/html/2606.29092#bib.bib48); Li et al., 2024b (https://arxiv.org/html/2606.29092#bib.bib27)) 通过最优占据的运动来度量非平稳性，并支付一个Lipschitz因子将这种运动转化为遗憾。本文研究的价格将这种运动细化为按值度量的暴露面路径。对于持有先前最优面的学习器，该价格恰好等于实现的遗憾（定理1 (https://arxiv.org/html/2606.29092#Thmtheorem1)），而路径长度仅能界定它。

##### 法扇、多面体几何与策略更新。

多面体的法扇通过线性目标选择的面来划分目标空间——这是凸多面体几何中的标准构造 (Ziegler, 1995 (https://arxiv.org/html/2606.29092#bib.bib51); Rockafellar, 1970 (https://arxiv.org/html/2606.29092#bib.bib38); Lu and Robinson, 2008 (https://arxiv.org/html/2606.29092#bib.bib28); Paffenholz, 2010 (https://arxiv.org/html/2606.29092#bib.bib35); Tropp, 2022 (https://arxiv.org/html/2606.29092#bib.bib44))。我们将其墙解读为控制的决策边界。一旦先前最优面在新损失下获得正的Bellman优势，穿越就变得昂贵。墙周围的边距是线性规划的弱锐性常数 (Burke and Ferris, 1993 (https://arxiv.org/html/2606.29092#bib.bib5))。另外，镜像下降、自然梯度和信任区域方法在策略空间上施加了非欧几里得几何 (Nemirovskiĭ and IUdin, 1983 (https://arxiv.org/html/2606.29092#bib.bib32); Beck and Teboulle, 2003 (https://arxiv.org/html/2606.29092#bib.bib55); Kakade, 2001 (https://arxiv.org/html/2606.29092#bib.bib21); Kakade and Langford, 2002 (https://arxiv.org/html/2606.29092#bib.bib20); Schulman et al., 2017 (https://arxiv.org/html/2606.29092#bib.bib41); Tomar et al., 2021 (https://arxiv.org/html/2606.29092#bib.bib43); Lan, 2022 (https://arxiv.org/html/2606.29092#bib.bib23); Zhan et al., 2023 (https://arxiv.org/html/2606.29092#bib.bib46); Alfano et al., 2024 (https://arxiv.org/html/2606.29092#bib.bib2); Agarwal et al., 2020 (https://arxiv.org/html/2606.29092#bib.bib1); Kleuker et al., 2025 (https://arxiv.org/html/2606.29092#bib.bib22))。我们的解读将这些更新重新诠释为法扇的近似跟踪器，其中Bregman项将质量保持在不确定的墙附近，而大的优势将其推离明显次优的动作。Rakhlin和Sridharan (2014 (https://arxiv.org/html/2606.29092#bib.bib37)) 的乐观机制提供了这种跟踪所需的预测。

## 3 占据几何与法扇

### 3.1 占据多面体

考虑一个回合制MDP，具有时域HH，有限状态空间S\mathcal{S}，有限动作空间A\mathcal{A}，初始分布ρ\rho，以及转移核Ph(⋅∣s,a)P_h(\cdot\mid s,a)。我们假设转移已知且固定，并让损失lt={lt,h(s,a)}h,s,a\ell_t=\{\ell_{t,h}(s,a)\}_{h,s,a}在回合之间对抗性地变化。遵循标准的占据测度公式 (Puterman, 2014 (https://arxiv.org/html/2606.29092#bib.bib36); Altman, 2021 (https://arxiv.org/html/2606.29092#bib.bib3))，对于马尔可夫策略π\pi，占据测度记录访问频率：

qhπ(s,a)=Prπ(sh=s,ah=a).q_h^{\pi}(s,a)=\Pr_{\pi}(s_h=s,\,a_h=a).

令Q\mathcal{Q}表示所有马尔可夫策略可达到的占据测度的集合。它是以下非负性与流约束定义的多面体：

∑aq1(s,a)\displaystyle\sum_a q_1(s,a)=ρ(s),\displaystyle=\rho(s),∑aqh+1(s,a)\displaystyle\sum_a q_{h+1}(s,a)=∑s′,a′qh(s′,a′)Ph(s∣s′,a′),h=1,...,H−1.\displaystyle=\sum_{s',a'}q_h(s',a')\,P_h(s\mid s',a'),\qquad h=1,\ldots,H-1.

期望损失是占据的线性函数：Jt(π)=⟨qπ,lt⟩J_t(\pi)=\left\langle q^{\pi},\ell_t\right\rangle，并且第tt轮的最优占据集是暴露面：

Ft=argminq∈Q⟨q,lt⟩.F_t=\operatorname*{arg\,min}_{q\in\mathcal{Q}}\left\langle q,\ell_t\right\rangle.

对于一系列行动xt∈Qx_t\in\mathcal{Q}，相对于每轮最优的动态遗憾 (Zinkevich, 2003 (https://arxiv.org/html/2606.29092#bib.bib54); Hall and Willett, 2013 (https://arxiv.org/html/2606.29092#bib.bib14); Jadbabaie et al., 2015 (https://arxiv.org/html/2606.29092#bib.bib18)) 为：

DRegT=∑t=1T[⟨xt,lt⟩−minq∈Q⟨q,lt⟩].\operatorname{DReg}_T=\sum_{t=1}^T\left[\left\langle x_t,\ell_t\right\rangle-\min_{q\in\mathcal{Q}}\left\langle q,\ell_t\right\rangle\right].