在对手策略动态变化的不完全观测环境中，实现最优策略后悔率。
Minimax-Optimal Policy Regret in Partially Observable Markov Games
- 采用基于周期的乐观最大似然算法，逐周期更新策略并验证模型。
- 达到近似√T的策略后悔率，与问题参数和对手记忆长度相关。
- 适用于对抗性环境下的强化学习，尤其适合高动态博弈场景。
我们研究在对抗性、自适应对手存在的不完全可观测环境中进行序列决策，该问题建模为部分可观测马尔可夫博弈（POMGs）。核心挑战在于从部分观测中学习潜在动态，同时面对行为依赖于学习者策略的对手，使得标准后悔度量不适用。我们证明，一种基于周期的乐观最大似然算法在固定问题参数下可实现${\tilde{O}}(\sqrt{T})$的策略后悔率，其具体依赖于时域长度、对手记忆、置信半径以及可观测算子误差类的总埃尔德维维恩维度。该算法每周期部署一个策略，周期长度几何递增但有上限，置信集基于历史数据累积构建，并通过统计检验在模型被数据证伪时终止当前周期。我们还建立了匹配的下界，并将框架扩展至时域自适应保证和几何衰减对手记忆的情形。
原文摘要 · Abstract (English)
We study sequential decision-making in partially observable environments against strategic, adaptive opponents, modeled as partially observable Markov games (POMGs). The central challenge is to learn latent dynamics from partial observations while facing an adversary whose behavior depends on the learner's strategy, making standard regret notions inadequate. We prove that an epoch-based optimistic maximum-likelihood algorithm achieves ${\tilde{O}}(\sqrt{T})$ policy regret for fixed problem parameters, with explicit dependence on the horizon, adversary memory, confidence radius, and the aggregate Eluder dimension of the observable-operator error classes. The algorithm deploys one policy per epoch, with geometrically capped epoch lengths, confidence sets built cumulatively from past data, and a statistical termination test that ends an epoch as soon as the data refute the deployed optimistic model. We also prove a matching lower bound, and extend the framework to horizon-adaptive guarantees and geometrically fading adversary memory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。