Research map / Bandits and online learning / Online convex optimization and games

Improved Sample Complexity for Markov Games via Variance-Aware Bandit Learning

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Last-iterate convergence in games

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Improves the sample complexity bound for learning epsilon-approximate CCE in multi-player general-sum Markov games in the simulator setting using variance-aware bandit learning.

Problem

Sample complexity of learning an epsilon-approximate coarse correlated equilibrium in multi-player general-sum Markov games with a simulator; the prior best bound was H^4 S sum A_i / epsilon^2 (Li et al., 2022).

Approach

Applies variance-aware bandit learning techniques to Markov games to tighten the dependence on horizon and state/action sizes in the sample complexity for CCE. Only the abstract was available, so the specific technique is not detailed.

Key results

• Prior best upper bound for epsilon-approximate CCE in the simulator setting is H^4 S sum_i A_i / epsilon^2 (Li et al., 2022); the paper claims an improvement over this bound (exact improved rate not stated in the provided abstract excerpt).

Limitations

• Only the abstract was available; the full technical details and final bound could not be verified.

Experimental setup

Metrics: sample complexity

Baselines: Li et al., 2022

Builds on: Li et al., 2022 (CCE sample complexity in Markov games)

Closest papers by meaning

• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? (ICLR 2022 · similarity 0.95)
• Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model (NeurIPS 2022 · similarity 0.91)
• Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games (NeurIPS 2022 · similarity 0.90)
• Optimal Sample Complexity for Average Reward Markov Decision Processes (ICLR 2024 · similarity 0.90)
• Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.90)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective (ICLR 2024 · similarity 0.89)