Research map / Multi-agent systems and games / Games and equilibria
A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning
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.
Proposes a black-box reduction that turns stationary equilibrium learning and testing oracles into non-stationary MARL algorithms with bandit feedback, achieving Õ(Δ^{1/4}T^{3/4}) (known Δ) and Õ(Δ^{1/5}T^{4/5}) (unknown Δ) dynamic equilibrium regret.
Problem
Learning equilibria (NE, CE, CCE) in non-stationary multi-agent Markov games under bandit feedback, where the environment changes over episodes and the regret must track a time-varying equilibrium.
Approach
A black-box reduction: restarted explore-then-commit with PAC learning oracles, plus multi-scale randomized equilibrium testing (with a new test-scheduling scheme and CE testing via an extended-state MDP) that adaptively detects non-stationarity without knowing its budget.
Key results
- Achieves Õ(Δ^{1/4}T^{3/4}) dynamic equilibrium regret when total variation budget Δ is known, via restarted explore-then-commit.
- Achieves Õ(Δ^{1/5}T^{4/5}) regret for unknown Δ using multi-scale testing, and Õ(L^{1/4}T^{3/4}) for unknown switching number L.
- Shows testing CE costs a factor of A more samples than testing CCE, matching the √A gap between minimax swap and external regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multi-scale testing instead of fixed restarts when the total-variation budget is unknown | Black-box equilibrium learning · Non-stationary games with total variation Δ | dynamic equilibrium regret: \widetilde{O}\left(\Delta^{1/4}T^{3/4}\right) -> \widetilde{O}\left(\Delta^{1/5}T^{4/5}\right) | Hurt |
| Use multi-scale testing without knowing the switching number | Black-box equilibrium learning · Non-stationary games with switching number L | dynamic equilibrium regret: \widetilde{O}\Sp{L^{1/4}T^{3/4}} | No clear effect |
| Reduce the base algorithm's learning sample complexity exponent from α=-2 to α=-3 | Restart-based equilibrium learning · Non-stationary games with known total-variation budget Δ | dynamic equilibrium regret: \widetilde{O}\Sp{\Delta^{1/4}T^{3/4}} -> \widetilde{O}\Sp{\Delta^{1/5}T^{4/5}} | Hurt |
| Enlarge the state space by a factor of A to test correlated equilibrium rather than coarse correlated equilibrium | Black-box equilibrium testing · Markov games | testing sample complexity: A times larger | Hurt |
Surprising findings
- Standard multi-scale testing from single-agent bandits fails in games because re-running learning can converge to different equilibria, so replay-based tests are unreliable.
Limitations
- Assumes oracles may incur O(1) regret during learning/testing; no-regret oracles are open.
- Regret lower bounds for non-stationary MARL are unknown.
- Does not yet provide no-regret guarantees for each individual agent.
Experimental setup
Metrics: dynamic equilibrium regret
Builds on: MALG (multi-scale testing for non-stationary bandits) Bandit-over-RL EXP3
Closest papers by meaning
- Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes (NeurIPS 2019 · similarity 0.90)
- Decentralized Q-learning in Zero-sum Markov Games (NeurIPS 2021 · similarity 0.90)
- Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games (ICML 2023 · similarity 0.90)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.89)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · 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.