Auction-Based Online Policy Adaptation for Evolving Objectives¶
会议: NeurIPS 2026
arXiv: 2604.02151
OpenReview: https://openreview.net/forum?id=OV5qcOHgej
领域: 强化学习
关键词: 多目标强化学习, 在线策略自适应, 拍卖机制, 马尔可夫博弈, 注意力池化
一句话总结¶
针对目标动态增删的多目标强化学习场景，本文提出一种基于拍卖机制的去中心化策略自适应框架，每个目标由自私局部策略维护并按紧迫度出价竞夺控制权，在无需重训的情况下实现了高效、即时且可解释的在线权衡。
研究背景与动机¶
在移动机器人配送、仓储分拣与动态路径规划等实际物理场景中，智能体往往需要同时响应多个在运行时动态涌现或失效的目标。例如，在流浪猫救助站中巡逻投喂食物的移动机器人，饥饿猫的进食请求会随时在不同地点随机出现，而未被及时响应的猫可能在离开后导致任务失效。由于实体执行机构在物理上往往同一时刻只能服务一个目标，处理当前目标必然延误其他目标的执行，系统必须在多个具有时效性的冲突目标之间做出动态、敏捷的调度与权衡。
然而，现有多目标强化学习（MORL）方法绝大多数依赖中心化的一体化单策略（Monolithic Policy）。这类方法将多个目标通过标量化权重相加或帕累托前沿拟合转化为单一决策流，存在两个根本性瓶颈：其一，一体化策略假定目标集合与其奖励维度在训练与部署期静态固定，一旦目标数量增加、减少或动态漂移，整体网络输入维度和决策分布随即失效，无法直接泛化；其二，由于多个目标在整个长轨迹中密集反馈正向奖励，中心化单策略在回传梯度时面临严重的信用分配（Credit Assignment）灾难，且设计兼顾全局与局部的密集距离塑形奖励极度困难。
针对这一困境，本文选择将复杂的多目标控制解耦为模块化的局部策略集合。由于同类任务中的目标往往属于同一任务族（如可达性目标），系统可以为每个活跃目标分配一个只关注自身利益的自私局部策略，并通过轻量级市场拍卖机制实现完全去中心化的运行时控制权仲裁。本文的核心 idea 是：将多目标控制建模为局部自私策略间的马尔可夫竞标博弈，策略根据当前紧迫度自主出价竞夺固定步长的执行权，并引入正比于出价的惩罚成本强制策略真实竞标，从而通过局部纳什均衡直接逼近具有理论保真度的全局贪心最优调度。
方法详解¶
整体框架¶
本文框架将包含 \(m\) 个同族目标的多目标马尔可夫决策过程（MO-MDP）诱导为一个多策略竞标的一般和马尔可夫博弈 \(\mathcal{G}_{\tau,\beta,\rho,\mathsf{P}}^{\mathcal{M}}\)。每个目标由一个独立的自私局部策略维护，这些策略不仅输出底层物理动作，还在每个决策周期提交一个代表紧迫度的非负出价。仲裁机制每隔固定时长 \(\tau\) 举行一次密封竞标，出价最高者赢得未来 \(\tau\) 个连续环境步的物理控制权。
整个决策流包含状态观测、注意力池化压缩、动作与竞标生成、胜者仲裁与环境步执行四个阶段。框架在目标动态到达或消除时，仅需即时增删对应的局部策略副本，无需任何网络重训。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["环境全局状态观测<br/>包含 m 个动态目标"] --> B["注意力池化特征压缩<br/>提取变长目标全局上下文"]
B --> C["局部自私策略并行决策<br/>分别输出动作与紧迫度出价"]
C --> D["密封拍卖仲裁机制<br/>最高出价者赢取控制权"]
D -->|结算竞标惩罚| E["Winner-Pays / All-Pay 扣除惩罚成本"]
D -->|授予执行权| F["环境连续执行胜者动作 tau 步"]
F -->|状态流转与目标增删| A关键设计¶
1. 局部自私策略与马尔可夫竞标博弈建模：以微观自私驱动宏观协调 传统单策略在面对动态增删目标时必须重建整个网络架构，而本文将状态空间拓展为 \(\hat{S} = S \times [1;m] \times [0;\tau-1]\)，其中 \(k \in [1;m]\) 记录当前拥有执行权的策略编号，\(q \in [0;\tau-1]\) 记录距离下一轮拍卖的剩余步数。当 \(q > 0\) 时，系统沿用策略 \(k\) 的动作执行；当 \(q = 0\) 时，系统触发新一轮竞标。每个策略 \(i\) 独立选择底层动作 \(a_i \in A\) 与出价 \(b_i \in [0; \beta]\)。令最高出价者集合为 \(W(\mathbf{b}) = \{i \mid b_i = \max_j b_j\}\)，系统在 \(W(\mathbf{b})\) 中等概率随机破平选出新控制者 \(k'\)。通过这种将时间分块（Action Window \(\tau\)）的离散博弈，避免了单步频繁切换导致的抖动，赋予策略在连续 \(\tau\) 步内完整推进自身子目标的能力。
2. 诚实竞标约束机制与纳什均衡保障：利用惩罚项对齐真实紧迫度 在自私竞标中，最核心的失效模式是策略为了垄断控制权而持续恶意虚报最高出价。为了解决虚假竞标问题，机制对提交的出价施加与出价大小成正比的惩罚 \(\rho b_i\)（\(\rho \in (0,1)\)）。在 Winner-Pays 模式下，仅获胜执行的策略支付惩罚；在 All-Pay 模式下，所有提交竞标的策略均无条件扣除惩罚。对于策略 \(i\)，定义其赢得竞标与失去竞标在未来 \(\tau\) 步及后续的最优延续价值分别为 \(\widetilde{V}_{i,t}^{\mathsf{win}}(s)\) 与 \(\widetilde{V}_{i,t}^{\mathsf{lose}}(s)\)，两者之差定义为控制增益（Control Gain）： $\(G_{i,t}(s) \coloneqq \widetilde{V}_{i,t}^{\mathsf{win}}(s) - \widetilde{V}_{i,t}^{\mathsf{lose}}(s)\)$ 该控制增益天然具备环境感知能力：若其他策略顺路执行的动作客观上有利于策略 \(i\)，其失去控制权的延续价值也会很高，导致 \(G_{i,t}(s)\) 自动降低，促使其主动让渡控制权。理论证明，在 Winner-Pays 设定下，只要最高控制增益策略 \(i^*\) 与次优策略的增益差满足 \(G_{i^*,t}(s) - \max_{j \neq i^*} G_{j,t}(s) > \rho\)，纯策略纳什均衡必然由控制增益最高的策略胜出；在 All-Pay 混合策略纳什均衡下，最高增益策略胜出的概率严格等于 \(1 - \frac{G_{j^*,t}}{2 G_{i^*,t}}\)，在数学上证明了局部自私竞争能够自发逼近全局紧急目标的优先调度。
3. 注意力池化动态编码架构：消除目标数量对网络结构的硬性绑定 为了让局部策略在做决策与出价时充分感知其他竞争目标的分布，策略必须以全局状态作为输入。然而直接拼接目标向量会导致输入维度随目标数量 \(m\) 动态变化。为此，本文设计了置换不变的注意力池化模块（Attention Pooling）。设活跃目标特征集合为 \((z_1, \ldots, z_m)\)，每个特征向量首先经由全连接网络 \(f_\psi\) 映射至隐空间 \(h_j = f_\psi(z_j)\)，随后通过可学习的全局查询向量 \(q\) 计算注意力权重并加权聚合： $\(\alpha_j = \frac{\exp(q^\top h_j)}{\sum_{\ell=1}^m \exp(q^\top h_\ell)}, \quad h_{\mathrm{pool}} = \sum_{j=1}^m \alpha_j h_j\)$ 每个局部策略将自身专用目标特征 \(z_i\) 与压缩后的定长上下文向量 \(h_{\mathrm{pool}}\) 拼接后送入 Actor-Critic 网络。该结构保证了无论运行时目标增加到多少个，策略输入维度均保持恒定，使在少量目标（如 7-8 个）下训练的模型能够零样本直接泛化部署至更多目标（如 14 个）的环境中。
损失函数 / 训练策略¶
在实现中，为了兼顾离散控制与高效学习，出价空间被离散化为若干固定档位（例如 Cat Feeder 设为 \(\{0, 1, \dots, 6\}\)），作为策略的额外分类输出头。由于同族目标具有高度对称性，所有局部策略共享同一套 Actor-Critic 网络参数，但在前向推理与梯度回传时分别输入自身专有的目标特征 \(z_i\) 并使用各自的局部回报进行更新。
网络采用多智能体并行 PPO（Proximal Policy Optimization）协同训练。为保证博弈环境中策略平稳收敛至纳什均衡，模型使用了较小的 PPO 剪切系数 \(\epsilon \sim 0.05\) 以及大规模并行采样环境（Cat Feeder 使用 4096 个并行环境，rollout 步长 256）。策略 \(i\) 的即时局部奖励由目标完成奖励、距离逼近塑形奖励、超时惩罚以及拍卖竞标成本联合构成： $\(\hat{r}_i = r_i^{\mathrm{reach}} + r_i^{\mathrm{dist}} + r_i^{\mathrm{expire}} - \rho b_i \cdot \mathbf{1}[q=0 \land (i=k' \lor \mathsf{P}=\textsf{All-Pay})]\)$
实验关键数据¶
主实验¶
论文在 3 个动态多目标环境中开展评测：包含 8 个移动目标的网格规划环境 Cat Feeder（得分 = 成功喂猫数 - 超时未喂数），以及基于对象级状态输入的两款经典 Atari 射击游戏 Assault 与 Air-Raid（得分 = 游戏得分）。对比基准包括单策略 PPO（包含无塑形、最近目标塑形、最早到期目标塑形三种变体）以及分布式多目标经典方法 Deep W-learning（DWN）。所有结果基于 10 个随机种子统计（均值与标准差）。
| 方法 | Cat Feeder (得分) | Atari Assault (得分) | Atari Air-Raid (得分) |
|---|---|---|---|
| Winner-Pays (本文) | 49.44 ± 4.19 | 556.05 ± 29.23 | 3902.55 ± 90.44 |
| Winner-Pays (无注意力池化) | 51.72 ± 3.97 | — | — |
| All-Pay (本文) | 72.52 ± 4.23 | 576.64 ± 43.19 | 3870.45 ± 76.72 |
| All-Pay (无注意力池化) | 37.72 ± 50.32 | — | — |
| Deep W-learning (DWN) | -10.27 ± 2.38 | 310.80 ± 159.54 | 2438.38 ± 625.97 |
| 单策略 PPO (无塑形) | -51.59 ± 5.33 | 358.60 ± 25.99 | 3549.33 ± 1170.14 |
| 单策略 PPO (最近目标塑形) | -14.15 ± 41.88 | — | — |
| 单策略 PPO (到期时间塑形) | -47.62 ± 1.52 | — | — |
消融实验¶
针对 Cat Feeder 环境，论文深入评估了出价上限 \(\beta\)、出价惩罚系数 \(\rho\) 以及注意力池化模块对于学习稳定性和泛化性能的控制作用。
| 配置 | Cat Feeder 得分 | 表现说明与机制分析 |
|---|---|---|
| All-Pay 完整模型 (\(\beta=6, \rho=0.1\)) | 72.52 ± 4.23 | 策略能够精细表达紧迫度梯度，兼顾高效抢权与适度让渡 |
| All-Pay (无注意力池化) | 37.72 ± 50.32 | 训练初期难以提取变长目标分布特征，收敛极度迟缓且方差巨大 |
| 极端出价上限：\(\beta = 1\) (单档出价) | 约 20.0 | 无法区分紧急与常规目标，竞标退化为接近均匀随机轮询 |
| 适度出价上限：\(\beta = 2\) | 约 65.0 | 仅需极少出价分级即可激活有效的优先级排序机制 |
| 零惩罚系数：\(\rho = 0.0\) | 约 35.0 | 缺乏成本惩罚，所有策略均顶格出价，破坏竞标真实性 |
| 过大惩罚系数：\(\rho \ge 0.5\) | < 10.0 | 出价惩罚压制了策略竞争动机，导致频繁出现消极弃标 |
关键发现¶
- 多目标信用分配优势显著：单策略 PPO 在 Cat Feeder 中即使用 Optuna 调优 40 次并结合距离塑形，得分依然为负（-14.15），原因在于轨迹中交替出现的多个正向奖励让单网络价值函数梯度互相抵消；而本文模块化策略每个网络只对自己的目标负责，大幅降低了信用分配难度。
- DWN 信号坍缩失效：DWN 依赖局部 Q 网络未能执行动作时的负 TD 误差来估计紧迫度，但在长时域对称目标场景中，各目标 Q 值极为相似，TD 误差接近于 0，无法提供有效的裁决差异；而本文主动式出价机制赋予了策略直接表征当前时空紧迫度的能力。
- 零样本跨目标数泛化表现优异：得益于注意力池化对置换不变性与变长输入的建模能力，在 8 个目标下训练的模型，直接在测试期扩展到 14 个目标并发时，整体投喂完成率保持平稳上升，完全无需参数微调。
亮点与洞察¶
- 将资源调度转化为市场竞标博弈：把强化学习中的动作调度权设计为可通过出价竞拍的商品，借助经济学惩罚项强制策略诚实反映控制增益，数学上完美连接了连续控制决策与经典离散最早截止时间优先（LSTF）调度启发式。
- 对称多策略共享与异构目标解耦的工程统一：通过为所有同族目标共享一套 Actor-Critic 权重，同时在输入端绑定独立的目标特征 \(z_i\) 与环境级注意力池化向量，兼顾了极高的采样更新效率与对多目标的独立追逐能力。
- 天生具备极高的白盒可解释性：在任意时刻，系统当前由哪个目标策略胜出接管完全公开，出价大小直观量化了该目标在当前时刻的危机程度，彻底摆脱了单策略黑盒难以追溯控制归因的弊病。
局限与展望¶
- 全局非协同的局部贪心陷阱：当前竞标机制以局部最紧急策略的增益为主导，可能陷入非最优调度。例如，当一个孤立目标极度濒临超时但位于偏远角落，而多个次紧急目标集中在相反方向时，系统仍会因最高出价选择追逐孤立目标，牺牲全局总收益。未来需引入群体投票或群体紧迫度聚合机制。
- 同族目标同质性假设：目前理论与实验假设所有目标属于同一任务族（均可通过同一套可达性奖励描述），无法直接处理安全约束、速度优化与路径跟踪等多类异构目标的层级优先级调度。
相关工作与启发¶
- vs 单策略多目标强化学习（Monolithic MORL）：传统方法通过标量化或拟合帕累托前沿训练单个全局网络，目标集合必须静态已知；本文采用去中心化竞标博弈，目标动态增删时仅需即时增删策略实例，具备天然的模块化即插即用特性。
- vs Deep W-learning (DWN)：DWN 采用被动估计未选中动作的负 TD 误差作为权重网络，在对称长程任务中容易面临信号梯度消失；本文直接将出价显式作为动作空间的一部分，通过端到端 PPO 策略梯度自主学会基于代价的紧迫度度量。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ [将多目标动态调度创新性地建模为带竞标惩罚的马尔可夫拍卖博弈，机制设计极其典雅]
- 实验充分度: ⭐⭐⭐⭐☆ [覆盖经典网格路径规划与两款 Atari 游戏，包含了详细的消融分析与超参敏感度剖析]
- 写作质量: ⭐⭐⭐⭐⭐ [理论推导严谨自洽，博弈论延续价值证明完备，图文与概念阐释清晰易懂]
- 价值: ⭐⭐⭐⭐☆ [为机器人动态多任务规划、物流调度等具备时效性目标演化场景提供了极具实用价值的工程框架]