针对可自适应对手的马尔可夫博弈，提出新算法实现高效学习。
Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms
- 用策略后悔衡量学习效果，更适用于自适应对手场景。
- 对手记忆无限或非平稳时，样本高效学习不可能。
- 引入一致对手概念，算法在合理条件下达√T后悔率。
我们研究学习者与可自适应策略对手之间的动态环境建模，即马尔可夫博弈。现有工作多以外部后悔为学习目标，但在自适应对手下已不适用。本文聚焦于策略后悔——一种反事实指标，旨在与事后最优固定策略序列的回报相比较。我们证明：若对手具有无界记忆或非平稳性，则样本高效学习不可行；当学习者可行策略集呈指数级规模时，即使对手记忆有界且平稳，学习仍具统计困难。为保证可学习性，我们引入“一致”自适应对手的新概念：对手对相似策略作出类似响应。针对此类对手，我们设计算法，实现了√T级别的策略后悔率。
原文摘要 · Abstract (English)
We study learning in a dynamically evolving environment modeled as a Markov game between a learner and a strategic opponent that can adapt to the learner's strategies. While most existing works in Markov games focus on external regret as the learning objective, external regret becomes inadequate when the adversaries are adaptive. In this work, we focus on \emph{policy regret} -- a counterfactual notion that aims to compete with the return that would have been attained if the learner had followed the best fixed sequence of policy, in hindsight. We show that if the opponent has unbounded memory or if it is non-stationary, then sample-efficient learning is not possible. For memory-bounded and stationary, we show that learning is still statistically hard if the set of feasible strategies for the learner is exponentially large. To guarantee learnability, we introduce a new notion of \emph{consistent} adaptive adversaries, wherein, the adversary responds similarly to similar strategies of the learner. We provide algorithms that achieve $\sqrt{T}$ policy regret against memory-bounded, stationary, and consistent adversaries.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。