Research map / Bandits and online learning / Online convex optimization and games
Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies policy regret for learning in two-player Markov games against adaptive adversaries, proves statistical hardness results for unbounded, memory-bounded, and large-policy-class settings, and gives sqrt(T) algorithms (OPO-OMLE, APE-OVE) under a consistent-adversary assumption.
Problem
Learning in Markov games against adaptive opponents whose responses depend on the learner's past policies; external regret is inadequate, and policy regret is statistically hard in general.
Approach
Introduce policy regret for Markov games and a "consistent" adversary assumption (similar learner policies induce similar opponent responses), which makes sqrt(T) policy regret achievable via optimistic MLE for estimating the opponent's response and policy elimination with optimistic value estimation.
Key results
- Unbounded-memory adversaries force linear policy regret Omega(T), and m-memory bounded oblivious adversaries force Omega(sqrt(T (SA/L)^L)) regret.
- For 1-memory stationary consistent adversaries, OPO-OMLE achieves regret O~(H^3 S^2 AB + sqrt(H^5 S A^2 B T)).
- For general fixed memory m, APE-OVE achieves O~(sqrt(T)) policy regret scaling with m, H, S, A, B and the minimum positive visitation probability d*.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow the adversary unbounded memory | Learning in Markov games · Markov games with adaptive adversaries | policy regret: regret is $\Omega(T)$ | Hurt |
| Restrict the adversary to be m-memory-bounded | Learning in Markov games · Markov games, m-memory-bounded adversary | policy regret: $\Omega(\sqrt{T (SA)^H})$ | Hurt |
| Require the adversary to be stationary while memory-bounded | Learning in Markov games · Markov games with m-memory-bounded, stationary adversaries | policy regret: $\Omega \left(\min \{T, |\Pi|\}\right)$ | Hurt |
| Require the adversary to be consistent in addition to memory-bounded and stationary | Learning in Markov games · 1-memory-bounded adversary | policy regret: $\tilde{\gO}(H^3 S^2 AB + \sqrt{H^5 SA^2 B T})$ | Helped |
| Require the adversary to be consistent in addition to memory-bounded and stationary | Learning in Markov games · m-memory-bounded adversary (m ≥ 1) | policy regret: $\tilde{\gO} \left( (m-1) H^2 SAB + \sqrt{H^3 S AB} (SAB(H+\sqrt{S}) + H^2) \sqrt{\frac{T}{ d^*}} \right)$ | Helped |
Surprising findings
- Even memory-0 (oblivious) adversaries with a small policy set make learning statistically hard in Markov games, unlike in bandits.
- Policy-revealed setting, which permits no-external-regret learning, does not help with policy regret.
Limitations
- Algorithms are computationally inefficient, requiring enumeration of the exponentially large deterministic policy set.
- Bounds scale polynomially with state and action space cardinalities and depend on minimum positive visitation probability d*.
- Consistency assumption is a structural restriction; necessary and sufficient learnability conditions are open.
Experimental setup
Metrics: policy regret
Baselines: Q-ol V-learning bandit algorithms over policy set
Builds on: optimistic value iteration adaptive policy elimination policy regret in online learning latent MDP lower bounds
Closest papers by meaning
- Policy-Regret Minimization in Markov Games with Function Approximation (ICML 2025 · similarity 0.93)
- Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits (ICML 2022 · similarity 0.93)
- Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · similarity 0.89)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.89)
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.88)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.