Playing Markov Games Without Observing Payoffs¶

会议: NeurIPS 2026
arXiv: 2509.00179
领域: 学习理论
关键词: 马尔可夫博弈, 无收益学习, 对称博弈, Copycat策略, 在线凸优化

一句话总结¶

本文首次将无收益观测下的对称博弈在线学习拓展至马尔可夫序列决策，提出了逐状态局部模仿与期望收益重分配技术，在对手全知且转移未知的极端信息劣势下取得了与理论下界紧确匹配的亚线性后悔界。

研究背景与动机¶

在多智能体系统与竞争性在线决策中，面对高度不确定性或复杂陌生的对抗环境，模仿（Imitation）是一种极其自然且普遍的应对策略。例如在瞬息万变的在线广告竞价中，新成立的公司由于缺乏历史数据和测试预算，难以精确评估特定广告投放策略的实际收益，往往倾向于直接对标和跟拍经验丰富的行业巨头的投放行为。然而，这种盲目模仿往往暗藏极高风险：一旦模仿策略无法适应时序演化的底层机制，不仅可能造成资源浪费，更可能被拥有全局信息的对手诱入陷阱。因此，在不了解真实收益反馈的前提下，学习者能否仅凭观测对手的动作序列就立于不败之地，成为了在线学习与博弈论领域的关键理论难题。

以往理论研究中，Feldman、Kalai与Tennenholtz（2010）在有限双人零和对称矩阵博弈中证明了模仿的可行性：学习者在完全不观测收益矩阵、对手掌握全知先验信息的情况下，仅通过观测对手每轮动作并执行极小化极大“Copycat”策略，就能以 $O(n\sqrt{T})$ 的累积损失逼平对手。然而，现实中的决策往往具有长期延迟和状态转移特征，即当前的行动会深远改变未来的环境状态。在马尔可夫博弈（Markov Games）中，转移概率未知、状态时序耦合且收益信号隐匿，学习者面临严峻的信息劣势；而现有关于马尔可夫博弈的学习理论要么依赖显式的即时奖励反馈，要么假设博弈双方遵循相同的协调协议，或者要求转移矩阵具备严格的对称不变性。当转移规律完全未知、真实收益无法观测，且对手可能是能够利用时序转移恶意设局的全知对抗者时，学习者能否以及如何实现无悔学习，此前一直悬而未决。

解决该问题的核心挑战在于如何将静态博弈的“对称性”严格延拓至马尔可夫时序过程，并克服状态转移带来的动力学干扰。直观上，如果博弈角色互换、策略对调后双方期望收益正好互为相反数，博弈即具备全局对称性；但这种宏观对称性与微观状态的局部对称性之间存在复杂的时序纠缠。核心 idea：本文系统形式化了逐状态对称（SSG）、马尔可夫策略对称（MSG）与历史依赖策略对称（HSG）三重对称性定义，揭示了“宏观策略约束越严苛、时序博弈结构越简并”的反直觉难度层级，并证明无需估计任何转移规律，仅通过逐状态局部模仿和期望收益重分配（EPR）递归降维，就能以多项式时间算法迫使全知对手战平。

方法详解¶

整体框架¶

本文探讨的是有限阶段双人零和有限视野马尔可夫博弈 $(S, A, H, P, u)$ 的重复交互过程，总共进行 $T$ 轮片段（episodes）。状态空间按时间步划分为 $S = \bigsqcup_{h=1}^H S_h$，初态为 $S_1 = \{s_1\}$，动作集大小为 $|A|=n$。在每个片段 $t$ 中，学习者（Player 1）与对手（Player 2）分别选定策略并在各时间步 $h \in [H]$ 交互；转移概率 $P$ 和收益函数 $u: S \times A \times A \to [-1, 1]$ 保持固定。学习者处于极度严重的信息劣势：完全无法观测到任何数值收益反馈，且事先对状态转移核 $P$ 一无所知，仅能实时观测到自身所处的状态轨迹与对手选取的动作；而对手是全知的全知对抗者（Omniscient Adversary），完全知晓转移核 $P$ 与收益函数 $u$。

面对这一挑战，本文根据对称性的作用粒度提出了三种层级设定，并给出了统一的算法转化与求解管线。整体流程如下图所示：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["无收益观测零和马尔可夫博弈<br/>学习者仅观测状态轨迹与对手动作序列，P与u完全未知"] --> LayerJudge["对称性假设分层判定<br/>SSG (逐状态) / MSG (马尔可夫策略) / HSG (历史依赖策略)"]
    LayerJudge -->|Assumption 3.1: SSG| D1["逐状态独立Copycat与差异矩阵追踪<br/>各状态解耦维护斜对称频次差异矩阵Dt(s)"]
    LayerJudge -->|Assumption 3.2: MSG| D2["期望收益重分配递归降维<br/>引入基准动作(1,1)消除偏差，MSG严格等价为SSG"]
    LayerJudge -->|Assumption 3.3: HSG| D3["历史依赖价值冻结与单步矩阵博弈塌缩<br/>h≥2未来价值对任意策略恒定，等价为静态矩阵博弈"]
    D2 --> D1
    D1 --> D4["基于Blackwell可达性与OGD的通用虚拟博弈<br/>虚拟博弈者在线梯度下降更新收益，求解安全策略"]
    D3 --> Out1["超低遗憾界达成<br/>Regret = O(H n √T)"]
    D4 --> Out2["极值匹配遗憾界达成<br/>Regret = O(n √(T|S|H))，匹配理论下界"]

关键设计¶

1. 逐状态独立Copycat与差异矩阵追踪：解耦未知转移动态的局部模仿机制 在逐状态对称博弈（SSG）中，每一个状态 $s \in S$ 内部的局部矩阵博弈均满足斜对称性 $u(s, a^1, a^2) = -u(s, a^2, a^1)$。直觉上，由于对手的动作可能改变未来的状态访问分布，人们会担心全知对手通过操纵转移概率来诱导学习者频繁进入不利状态。然而，本文发现局部状态的斜对称结构足以将即时收益与转移过程彻底解耦。学习者只需对每个状态 $s$ 独立维护一个动作频次矩阵 $N_t(s, a^1, a^2)$（记录联合动作 $(a^1, a^2)$ 在状态 $s$ 出现的累积次数），并定义虚拟博弈的斜对称差异矩阵： $$D_t(s, a^1, a^2) \coloneqq N_t(s, a^2, a^1) - N_t(s, a^1, a^2)$$ 学习者在每个访问到的状态 $s_{h,t}$ 上，只需将 $D_t(s_{h,t}, \cdot, \cdot)$ 视为虚构收益矩阵，并求解该零和对称矩阵博弈的极小化极大混合策略（Max-min Mixed Strategy）。为了证明该局部策略在未知时序转移下的全局有效性，算法构造了基于差异平方和的全局势函数 $\beta_t^h = \sum_{s \in S_h} \sum_{a^1, a^2} (D_{T+1}(s, a^1, a^2))^2$。由于每个片段在每个阶段 $h$ 恰好只访问一个状态 $s_{h,t}$，且求解极小极大策略保证了期望虚拟收益 $\mathbb{E}[D_t(s_{h,t}, a^1_{h,t}, a^2_{h,t})] \ge 0$，势函数的单步期望变化严格满足 $\mathbb{E}[\sum_{h=1}^H (\beta_{t+1}^h - \beta_t^h)] \le 2H$。通过柯西-施瓦茨不等式望远求和，直接得到了 $O(n\sqrt{T|S|H})$ 的次线性累积收益界，完全摆脱了对转移概率 $P$ 的依赖。

2. 期望收益重分配递归降维：消除层间收益偏置并实现MSG到SSG的等价转化 当博弈条件放宽至仅要求对任意马尔可夫策略 $\pi^1, \pi^2 \in \Pi_M$ 满足价值函数反对称 $V^{\pi^1, \pi^2}(s_1) = -V^{\pi^2, \pi^1}(s_1)$（即 MSG 设定）时，单个状态内部的收益矩阵不再必然是斜对称的。此时局部极小极大策略的非负性假设失效，但 MSG 施加的全局不变性反过来强力约束了收益与转移函数的联合结构。为了剥离这种时序耦合，本文提出了期望收益重分配（Expected Payoff Redistribution, EPR）变换：对于任意阶段 $h < H$，选取基准动作对 $(1, 1)$，将阶段 $h+1$ 状态 $s'$ 上的基准收益 $u(s', 1, 1)$ 沿转移概率折算回溯至前一阶段 $h$ 的状态 $s$ 中： $$\hat{u}(s, a^1, a^2) = u(s, a^1, a^2) + \sum_{s' \in S_{h+1}} P(s' \mid s, a^1, a^2) u(s', 1, 1) \quad (\forall s \in S_h)$$ 同时扣除第 $h+1$ 阶段该状态的基准偏移 $\hat{u}(s', \cdot, \cdot) = u(s', \cdot, \cdot) - u(s', 1, 1)$。本文从理论上证明了 EPR 变换具有保值性（即对于任意马尔可夫策略对，初始状态价值严格守恒 $\hat{V}^{\pi^1, \pi^2}(s_1) = V^{\pi^1, \pi^2}(s_1)$），并且该变换能确保末端阶段 $H$ 的收益矩阵在去除基准偏移后完全变为严格的斜对称矩阵。因此，自底向上递归执行 $H-1$ 次 EPR 变换，可将任意原本复杂的 MSG 完美等价映射为一个纯粹的 SSG 实例，从而使学习者能够直接复用逐状态 Copycat 算法而无需改变任何执行逻辑。

3. 历史依赖价值冻结与单步矩阵博弈塌缩：极强对称约束下的时序自由度消除 当对称性要求进一步严苛至包含所有历史依赖策略 $\Pi_H$（即 HSG 设定）时，看似模型容量更大，实则导致博弈的序贯动力学彻底“退化”。由于历史依赖策略能够针对第 1 阶段发生的任意联合动作与到达状态实施高度敏感的分支响应，若第 2 阶段及之后的未来累积价值函数取决于后续采取的策略，全知对手便可构造不对称的触发策略使得价值和非零，破坏 HSG 假设。本文通过重构历史树状态空间并微调初始阶段的探测策略分布证明：对任意到达的历史 $z_2 = (s_1, a_1^1, a_1^2, s_2)$ 以及任意两组历史依赖策略对 $(\pi^1, \pi^2)$ 和 $({\pi^1}', {\pi^2}')$，其后继状态价值完全恒定： $$V^{\pi^1, \pi^2}(z_2) = V^{{\pi^1}', {\pi^2}'}(z_2) = \frac{1}{2} G(z_2)$$ 这意味着从第 2 步开始，博弈双方无论采取何种策略，期望收益均已被历史完全锁定，玩家在后续阶段没有任何改变胜负的有效控制权。因此，整个马尔可夫博弈彻底塌缩为一个单步等价矩阵博弈： $$u'(a^1, a^2) = u(s_1, a^1, a^2) + \sum_{s' \in S} P(s' \mid s_1, a^1, a^2) V^{\pi^*, \pi^*}((s_1, a^1, a^2, s'))$$ 学习者只需在首步动作空间上执行标准的单阶段 Copycat 策略，便能取得完全独立于状态数 $|S|$ 的 $O(H n \sqrt{T})$ 后悔界。

4. 基于Blackwell可达性与OGD的通用虚拟博弈：对抗性未知收益下的安全水平求解 除了针对具体对称类的解析规约，本文还将无收益观测学习问题统一形式化为向量收益的 Blackwell 可达性问题，进而等价映射至在线线性优化框架（Online Linear Optimization）。算法引入了一个“虚拟博弈者”（Virtual Player），其在每一轮 $t$ 选定一个候选收益张量 $u_t \in U \subset \mathbb{R}^{|S| \times n \times n}$。学习者根据该候选收益 $u_t$ 通过多项式时间动态规划求解马尔可夫安全策略（Safety-level Policy）$\pi_t^1 = \arg\max_{\pi^1} \min_{\pi^2} \mathbb{E}[u_t]$ 并执行；在观测到真实状态-动作轨迹后，将轨迹稀疏指示张量 $l_t$ 反馈给虚拟博弈者。虚拟博弈者采用在线梯度下降（OGD）结合欧氏投影迭代更新收益张量： $$u_{t+1}' = u_t - \eta l_t, \quad u_{t+1} = \Pi_U(u_{t+1}')$$ 利用 OGD 的无悔性质，算法在最坏可能收益函数下直接锁定了学习者的全局非负期望收益，为无需模型先验的多智能体鲁棒控制提供了普适的算法范式。

一个完整示例¶

为了具象化理解期望收益重分配（EPR）与逐状态 Copycat 的实际运作过程，考虑一个两阶段（$H=2$）、动作集 $A=\{1, 2\}$ 的对称决策系统： 1. 环境设定与初始偏差：阶段 1 具有单初始状态 $s_1$，转移规律确定；若阶段 1 产生非对角动作 $(1, 2)$，确定转移至状态 $s_2^A$；若产生对角动作 $(2, 1)$，转移至状态 $s_2^B$。末端状态 $s_2^A$ 与 $s_2^B$ 的原始收益矩阵由于历史反馈不同而含有常数偏移，并不满足局部的 $u(s, a^1, a^2) = -u(s, a^2, a^1)$，但全局价值函数满足 MSG 约束。 2. EPR 消除偏置：算法选取动作对 $(1, 1)$ 为锚点，计算 $u(s_2^A, 1, 1) = c_A$ 和 $u(s_2^B, 1, 1) = c_B$。EPR 机制将 $c_A$ 和 $c_B$ 沿转移逆向折叠进 $s_1$ 的收益矩阵中，修正后 $s_1$ 的等价收益为 $\hat{u}(s_1, 1, 2) = u(s_1, 1, 2) + c_A$；同时，将末端状态统一中心化 $\hat{u}(s_2^A, \cdot, \cdot) = u(s_2^A, \cdot, \cdot) - c_A$。此时，第 2 阶段各状态的等价矩阵强制化为严格的斜对称矩阵。 3. 逐状态频次追踪与决策生成：假设在前 10 轮中，状态 $s_1$ 下对手动作 2 对齐学习者动作 1 的频次为 $N_{10}(s_1, 1, 2) = 6$，反向频次 $N_{10}(s_1, 2, 1) = 3$。差异矩阵相应为 $D_{10}(s_1, 1, 2) = 3 - 6 = -3$。根据极小极大混合策略求解，学习者计算出增加动作 2 采样权重的概率分布，强制在后续轮次拉平联合动作的访问频次。 4. 终局收敛：随着片段数 $T$ 增长，每个状态的累积差异 $D_T(s)$ 被紧密约束在 $O(n\sqrt{T/|S|})$ 尺度内，全知对手通过诱导状态转移所能获取的收益增益被彻底消除。

损失函数 / 训练策略¶

在基于在线线性优化的通用框架（Algorithm 2）中，虚拟博弈者的目标是在紧凸集 $U$ 上最小化针对观测轨迹的线性损失。形式化设定如下： - 损失张量构建：设第 $t$ 轮片段生成的真实轨迹为 $\tau_t = (s_{1,t}, a_{1,t}^1, a_{1,t}^2, \dots, s_{H,t}, a_{H,t}^1, a_{H,t}^2)$。反馈给优化器的损失张量 $l_t \in \mathbb{R}^{|S| \times n \times n}$ 定义为状态-动作三元组的稀疏示性张量： $$l_t(s, a^1, a^2) = \begin{cases} 1, & \text{若存在 } h \in [H] \text{ 使得 } s = s_{h,t}, a^1 = a_{h,t}^1, a^2 = a_{h,t}^2 \\ 0, & \text{其他} \end{cases}$$ 该损失的弗罗贝尼乌斯范数上界为 $\|l_t\|_F \le \sqrt{H}$。 - 参数空间与更新步长：收益张量集合 $U$ 满足范数界 $\|u\|_F \le n\sqrt{|S|}$。采用在线梯度下降（OGD）更新收益预测，理论最优学习率设置为 $\eta = \frac{n\sqrt{|S|}}{\sqrt{H T}}$。 - 投影与策略求解策略：在获得临时收益矩阵 $u_{t+1}' = u_t - \eta l_t$ 后，将其欧氏投影回对称集合 $U$。学习者在每轮开始前，利用当前 $u_t$ 通过经典的 Shapley 递归在 $O(|S| \cdot n^3 \cdot H)$ 复杂度内求解单片段动态规划安全水平策略 $\pi_t^1$。

实验关键数据¶

主实验¶

本文属于纯理论奠基性研究，主要实验验证聚焦于不同对称性概念下的后悔界理论推导与复杂度分析。下表汇总了本文提出的三种对称性设定与经典矩阵博弈基准在无收益条件下的核心理论界及计算复杂度对比：

博弈类型	对称性约束范围	状态转移已知性	收益观测状态	学习者后悔界 (Regret Upper Bound)	理论匹配下界 (Matching Lower Bound)	单步时间复杂度
标准矩阵博弈 (Feldman et al.)	静态单状态	无转移 ($H=1$)	无收益观测	$O(n\sqrt{T})$	$\Omega(n\sqrt{T})$	$\mathrm{poly}(n, \log T)$
逐状态对称 (SSG, 本文)	逐状态局部斜对称	完全未知	无收益观测	$O(n\sqrt{T	S	H})$
马尔可夫策略对称 (MSG, 本文)	任意马尔可夫策略反对称	完全未知	无收益观测	$O(n\sqrt{T	S	H})$
历史依赖对称 (HSG, 本文)	任意历史策略反对称	完全未知	无收益观测	$O(H n\sqrt{T})$	$\Omega(H n\sqrt{T})$	$\mathrm{poly}(n, T)$
广义和逐状态对称 (General-Sum SSG)	逐状态斜对称化	完全未知	无收益观测	$\sqrt{\frac{1}{2} T	S	H n^2}$

消融实验¶

为明确不同对称性定义对游戏动态的简化程度，下表系统剖析了三种对称性假设在结构等价性、自由度抑制及对抗鲁棒性维度的退化机制对比：

对称性范式	形式化定义条件	结构等价转化目标	时序自由度	状态依赖性 ($\\|S\\|$)	关键技术支撑机制
SSG (Assumption 3.1)	$\forall s: u(s, a^1, a^2) = -u(s, a^2, a^1)$	独立解耦矩阵博弈	完全保留 (状态自由转移)	显式依赖 $\sqrt{\\|S\\|}$	逐状态势函数二次变分分析
MSG (Assumption 3.2)	$\forall \pi^1, \pi^2 \in \Pi_M: V^{\pi^1, \pi^2}(s_1) = -V^{\pi^2, \pi^1}(s_1)$	递归规约至 SSG	部分受限 (各层收益偏置消除)	显式依赖 $\sqrt{\\|S\\|}$	期望收益重分配 (EPR) 递归
HSG (Assumption 3.3)	$\forall \pi^1, \pi^2 \in \Pi_H: V^{\pi^1, \pi^2}(s_1) = -V^{\pi^2, \pi^1}(s_1)$	单步静态矩阵博弈	完全塌缩 ($h \ge 2$ 价值恒定)	完全独立 (无 $\\|S\\|$ 项)	历史敏感性反证与全价值均等引理

关键发现¶

对称性反直觉层级关系：表面上，允许历史依赖策略的 HSG 看起来比仅限当前状态的 MSG 更广泛，而 MSG 又看似概括了局部状态的 SSG。然而理论研究证实了相反的包含与退化关系：HSG $\subset$ MSG，且 MSG $\not\supset$ SSG（存在符合 SSG 却破坏 MSG 的反例，见原论文图 1）。策略级对称性要求太强，反而逼迫底层动力学丧失多样性。
下界紧确性验证：在 Appendix A 中构建的均匀转移反例证明，即使对手采取完全随机的探索策略，任何无收益算法也无法突破 $\Omega(n\sqrt{T |S| H})$ 的累积损失，表明逐状态独立 Copycat 算法在所有参数依赖（动作数 $n$、状态数 $|S|$、时序长度 $H$ 和轮数 $T$）上均达到了渐近最优。
广义和博弈镜像鲁棒性：在广义和（General-Sum）对称马尔可夫博弈中，即便博弈值不为 0，学习者通过斜对称化投影依然能够保证累积收益差距不超过 $\sqrt{\frac{1}{2} T |S| H n^2}$，这意味着学习者能够完全镜像对手的成败，彻底免疫恶意诱导。

亮点与洞察¶

反直觉的对称性降维视角：揭示了多智能体博弈中“全局对称性约束越强，环境时序复杂度越低”的深刻几何结构，为理解博弈论与强化学习中的不变性（Invariance）提供了全新理论视角。
完全解耦未知动力学：传统强化学习需要庞大的样本复杂度来构建转移模型 $\hat{P}$，而本文证明对于零和对称博弈的保底逼和任务，转移规律完全不需要被显式学习或逼近，直接消除维度诅咒。
可复用的 EPR 转化工具：期望收益重分配（EPR）技术提供了一种在多阶段博弈中沿时间反向剔除策略基准偏置的通用数学工具，未来可广泛迁移至多阶段机制设计与逆向强化学习中。

局限与展望¶

严格对称性假设的依赖：当前理论严格依赖于状态或策略层面的精确对称性；一旦现实环境中存在细微的非对称扰动（如微弱先手优势或非对称状态转移），算法的无悔界可能出现性能退化。
状态空间规模依赖：在 SSG 和 MSG 中，后悔界包含 $\sqrt{|S|}$ 因子，在连续状态或大状态空间强化学习中仍需要结合线性函数逼近或神经表示技术进行泛化。
未来方向：作者指出下一步重要课题是探索近似对称性（Approximate Symmetry）下的理论鲁棒性，以及如何将无收益模仿拓展至部分可观测 POMDP 与多于双人的博弈场景中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立无收益马尔可夫博弈学习理论，对称性反直觉层级发现极具颠覆性。
实验充分度: ⭐⭐⭐⭐⭐ 理论证明完整严密，涵盖紧确上下界、EPR规约证明与在线凸优化统一视角。
写作质量: ⭐⭐⭐⭐⭐ 逻辑层层推进，反例构建精准直观，数学推导极为优雅。
价值: ⭐⭐⭐⭐⭐ 彻底填补了非完全信息序贯博弈中经典模仿理论的空白，具有重大理论奠基价值。

博弈类型	对称性约束范围	状态转移已知性	收益观测状态	学习者后悔界 (Regret Upper Bound)	理论匹配下界 (Matching Lower Bound)	单步时间复杂度
标准矩阵博弈 (Feldman et al.)	静态单状态	无转移 (\(H=1\))	无收益观测	\(O(n\sqrt{T})\)	\(\Omega(n\sqrt{T})\)	\(\mathrm{poly}(n, \log T)\)
逐状态对称 (SSG, 本文)	逐状态局部斜对称	完全未知	无收益观测	$O(n\sqrt{T	S	H})$
马尔可夫策略对称 (MSG, 本文)	任意马尔可夫策略反对称	完全未知	无收益观测	$O(n\sqrt{T	S	H})$
历史依赖对称 (HSG, 本文)	任意历史策略反对称	完全未知	无收益观测	\(O(H n\sqrt{T})\)	\(\Omega(H n\sqrt{T})\)	\(\mathrm{poly}(n, T)\)
广义和逐状态对称 (General-Sum SSG)	逐状态斜对称化	完全未知	无收益观测	$\sqrt{\frac{1}{2} T	S	H n^2}$

对称性范式	形式化定义条件	结构等价转化目标	时序自由度	状态依赖性 (\(\\|S\\|\))	关键技术支撑机制
SSG (Assumption 3.1)	\(\forall s: u(s, a^1, a^2) = -u(s, a^2, a^1)\)	独立解耦矩阵博弈	完全保留 (状态自由转移)	显式依赖 \(\sqrt{\\|S\\|}\)	逐状态势函数二次变分分析
MSG (Assumption 3.2)	\(\forall \pi^1, \pi^2 \in \Pi_M: V^{\pi^1, \pi^2}(s_1) = -V^{\pi^2, \pi^1}(s_1)\)	递归规约至 SSG	部分受限 (各层收益偏置消除)	显式依赖 \(\sqrt{\\|S\\|}\)	期望收益重分配 (EPR) 递归
HSG (Assumption 3.3)	\(\forall \pi^1, \pi^2 \in \Pi_H: V^{\pi^1, \pi^2}(s_1) = -V^{\pi^2, \pi^1}(s_1)\)	单步静态矩阵博弈	完全塌缩 (\(h \ge 2\) 价值恒定)	完全独立 (无 \(\\|S\\|\) 项)	历史敏感性反证与全价值均等引理