Research map / Bandits and online learning / Online convex optimization and games
Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reveal the opponent's policy after each episode instead of revealing only actions | Learning Markov games with adversarial opponents and a finite baseline policy class · Markov games | regret: \Omega(\min\{K, 2^H\}/H) -> \tilde{\mathcal{O}}(\sqrt{H^4 S^2AK}) | Helped |
| Use adaptive OP-EXP3 when the opponent's finite policy class is unknown | Markov games with general baseline policies · Markov games, revealed-policy feedback | regret: \tilde\mathcal{O} (\sqrt{H^4S^2AK}+\sqrt{|\Psi^\star|SAH^3K} +\sqrt{|\Psi^\star|^2H^2K}) | Helped |
| Compete with general rather than Markov baseline policies when the opponent has a large policy class | Markov games with revealed opponent policies · Markov games, large baseline and opponent policy classes | regret: \Omega(\min\{K, 2^H\}) | Hurt |
| Require sublinear regret even with a known model and a small, known opponent policy class | Markov-game learning algorithms · Markov games, revealed-policy feedback | computational complexity: {\rm poly}(S,A,H)\cdot K^{1-c} | Hurt |
Closest papers by meaning
- Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.93)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.92)
- Policy-Regret Minimization in Markov Games with Function Approximation (ICML 2025 · similarity 0.91)
- Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · similarity 0.91)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.90)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.89)
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.