Research map / Bandits and online learning / RL theory and MDPs
Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints
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.
Designs a policy-elimination algorithm for two-player zero-sum Markov games under batch (adaptivity) constraints, achieving near-optimal regret Õ(√(H²S²ABT)) with O(H+log log K) batches, plus bandit-game and reward-free extensions.
Problem
Multi-agent RL (two-player zero-sum Markov games) where policy deployments are costly, so the number of policy updates (batch complexity) must be minimized while keeping near-optimal regret.
Approach
Extends arm-elimination batch schedules to self-play: maintains a version space of max-player Markov policies, uses an absorbing Markov game with crude and fine exploration to estimate transitions uniformly, and eliminates policies by LCB-style value gaps over geometrically growing stages, achieving O(H+log log K) batches.
Key results
- Algorithm achieves regret Õ(√(H²S²ABT)) with batch complexity O(H+log log K) for two-player zero-sum Markov games.
- Batch complexity lower bound Ω(H/log_A K + log log K) for algorithms with Õ(√K) regret, matching the upper bound up to log factors.
- Reward-free exploration achieves Õ(H³S²AB/ε²) sample complexity with batch complexity H+2, improving over prior low-adaptive methods' H⁵ dependence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the policy elimination algorithm with low-adaptive exploration | Two-player zero-sum Markov games · Two-player zero-sum Markov games | regret | Helped |
| Extend the algorithm to the two-player bandit-game setting | Policy elimination algorithm · Bandit games | regret | Helped |
| Use the reward-free algorithm instead of previous low-adaptivity reward-free algorithms | Reward-free single-agent MDP · Reward-free single-agent MDP | sample complexity: \widetilde{O}(\frac{H^5 S^2 A}{\epsilon^2}) -> \widetilde{O}(\frac{H^3 S^2 A}{\epsilon^2}) | Helped |
Surprising findings
- Switching-cost (deterministic-policy) measures are inappropriate for Markov games because Nash policies may be stochastic, so batch complexity is used instead.
Limitations
- Regret has a gap of sqrt(S min{A,B}) relative to the information-theoretic lower bound.
- Main algorithm is not computationally efficient in general.
- Analysis is tabular; no function approximation.
Experimental setup
Metrics: regret batch complexity sample complexity
Baselines: VI-ULCB Nash VI Algorithm 1 in single-agent low-adaptive RL work BaSE VI-Explore LARFE
Builds on: batched multi-armed bandit arm elimination absorbing MDP exploration (single-agent low-adaptive RL) Nash value iteration VI-ULCB
Closest papers by meaning
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.89)
- Sample-Efficient Multi-Agent RL: An Optimization Perspective (ICLR 2024 · similarity 0.89)
- Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning (ICLR 2024 · similarity 0.89)
- Policy-Regret Minimization in Markov Games with Function Approximation (ICML 2025 · similarity 0.89)
- Offline Multi-Agent Reinforcement Learning via In-Sample Sequential Policy Optimization (AAAI 2025 · similarity 0.88)
- Learning Nash Equilibrium of Markov Potential Games with a Shared Constraint via Primal-Dual Optimization (AAAI 2025 · 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.