arXiv:2511.07831stat.MLcs.LG2025-11AAAI被引 1

提出首个高效学习鲁棒多智能体博弈的算法,解决模拟到现实的性能下降问题。

Distributionally Robust Online Markov Game with Linear Function Approximation

  • 基于线性函数近似和分布鲁棒性,设计新算法DR-CCE-LSI
  • 在K次交互中实现ε-近似鲁棒粗相关均衡,遗憾上界为O(dH min{H,1/σ_i}√K)
  • 适用于大规模状态空间下的多智能体强化学习,适合实际部署场景

模拟到现实的差距是强化学习中的根本挑战:在仿真环境中训练的智能体在测试时性能显著下降。现有工作采用分布鲁棒强化学习框架,学习能在最坏环境变化下保持稳健的策略。本文目标是设计在交互数据收集和大状态空间下样本高效的算法。通过假设环境动态偏移满足d-矩形性,我们识别出在线马尔可夫博弈学习的根本困难,并通过最小值假设加以解决。为此,提出一种新型最小二乘值迭代算法DR-CCE-LSI,配备专为多智能体设计的探索奖励,以寻找ε-近似鲁棒粗相关均衡(CCE)。为实现样本高效学习,我们发现:当特征映射函数满足特定性质时,该算法在K次交互中能达到ε-近似CCE,且遗憾上界为O(dH min{H,1/σ_i}√K),其中K为交互轮数,H为决策步长,d为特征维度,σ_i表示第i个玩家的不确定性水平。本工作首次引入该设置下的样本高效算法,其性能匹配单智能体情形下的最优结果,并在特征维度d上达到极小极大最优样本复杂度。同时,通过仿真验证了算法在学习鲁棒均衡方面的有效性。

原文摘要 · Abstract (English)

The sim-to-real gap, where agents trained in a simulator face significant performance degradation during testing, is a fundamental challenge in reinforcement learning. Extansive works adopt the framework of distributionally robust RL, to learn a policy that acts robustly under worst case environment shift. Within this framework, our objective is to devise algorithms that are sample efficient with interactive data collection and large state spaces. By assuming d-rectangularity of environment dynamic shift, we identify a fundamental hardness result for learning in online Markov game, and address it by adopting minimum value assumption. Then, a novel least square value iteration type algorithm, DR-CCE-LSI, with exploration bonus devised specifically for multiple agents, is proposed to find an \episilon-approximate robust Coarse Correlated Equilibrium(CCE). To obtain sample efficient learning, we find that: when the feature mapping function satisfies certain properties, our algorithm, DR-CCE-LSI, is able to achieve ε-approximate CCE with a regret bound of O{dHmin{H,1/min{σ_i}}\sqrt{K}}, where K is the number of interacting episodes, H is the horizon length, d is the feature dimension, and \simga_i represents the uncertainty level of player i. Our work introduces the first sample-efficient algorithm for this setting, matches the best result so far in single agent setting, and achieves minimax optimalsample complexity in terms of the feature dimension d. Meanwhile, we also conduct simulation study to validate the efficacy of our algorithm in learning a robust equilibrium.

多智能体鲁棒学习强化学习线性近似

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。