Research map / Bandits and online learning / RL theory and MDPs
Towards General Function Approximation in Zero-Sum Markov Games
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 |
|---|---|---|---|
| Use ONEMG with Minimax Eluder dimension to select optimistic value functions and eliminate hypotheses with large Bellman error | Decoupled zero-sum Markov games · Decoupled zero-sum Markov games | regret: \Tilde{O}(H\sqrt{K \mathrm{dim}_{\mathrm{ME}}(\mathcal{F},\sqrt{1/K}) \log [\mathcal{N}({\mathcal{F}},1/K) / p]}) | Helped |
| Use the specialized linear-function ONEMG instead of the previous linear-function algorithm | Decoupled linear-function Markov games · Decoupled linear-function Markov games | regret dependence on feature dimension: d^{3/2} -> d; improves [the previous result] by a \sqrt{d} factor | Helped |
| Use AOME with alternate optimistic model elimination and witness-rank complexity | Coordinated zero-sum Markov games · Coordinated zero-sum Markov games | sample complexity: \Tilde{O}(\frac{H^3W_\kappa^2|\mathcal{A}|}{\kappa^2 \epsilon^2} \log(T|\mathcal{G}||\mathcal{M}|/p)) | Helped |
| Use AOVE with alternate optimistic value elimination and a policy class | Coordinated zero-sum Markov games · Coordinated zero-sum Markov games with policy class Π | regret: \Tilde{O}\left( H\sqrt{K d_{\mathrm{ME'}} \log [\mathcal{N}(\mathcal{F}, 1/K) \mathcal{N}(\Pi, 1/K) / p]} \right) | Helped |
| Apply global optimism at the initial state rather than adding optimistic bonuses at every state-action pair | ONEMG · Decoupled zero-sum Markov games | sample complexity | Helped |
| Use alternate optimism to address distribution shift between behavior and target policies | AOME and AOVE · Coordinated zero-sum Markov games | duality gap | Helped |
Closest papers by meaning
- Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games (ICML 2024 · similarity 0.92)
- Learning Two-Player Markov Games: Neural Function Approximation and Correlated Equilibrium (NeurIPS 2022 · similarity 0.91)
- Representation Learning for Low-rank General-sum Markov Games (ICLR 2023 · similarity 0.91)
- Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions (ICML 2021 · similarity 0.91)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.90)
- Approximate State Abstraction for Markov Games (AAAI 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.