Research map / Bandits and online learning / RL theory and MDPs
Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions
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 fictitious-play policy optimization that incorporates the opponent's past policies and actions in policy evaluation | Policy optimization in zero-sum Markov games with factored independent transitions · Factored independent transition | regret upper bound: \tilde{\cO}(T^{2/3}) -> \tilde{\cO}(\sqrt{T}) | Helped |
| Use fictitious-play policy optimization that incorporates the opponent's past policies and actions in policy evaluation | Policy optimization in zero-sum Markov games with single-controller transitions · Single-controller transition | regret upper bound: \tilde{\cO}(T^{2/3}) -> \tilde{\cO}(\sqrt{T}) | Helped |
| Add UCB optimism to Q-function estimation for Player 1 | Optimistic FP policy optimization · Factored independent transition | model-prediction-error contribution to regret: \sum_{k=1}^K\err_k(\text{I.2}) \leq 0 | Helped |
| Add UCB optimism to Q-function estimation for Player 1 | Optimistic FP policy optimization · Single-controller transition | model-prediction-error contribution to regret: \sum_{k=1}^K\err_k(\text{II.2}) \leq 0 | Helped |
| Estimate the opponent's state reaching probability under the empirical transition model | Optimistic FP policy optimization for Player 1 · Factored independent transition | regret upper bound: \sum_{k=1}^K\err_k(\text{I.4}) \leq \tilde{\cO} ( H^2 |\cS_2| \sqrt{ |\cB| K} ) | Helped |
| Estimate Player 1's state reaching probability under the empirical transition model | Optimistic FP policy optimization for Player 2 · Single-controller transition | regret upper bound: \sum_{k=1}^K\err_k(\text{III.4}) \leq \tilde{\cO}(H^2|\cS|\sqrt{|\cA| K} ) | Helped |
| Omit transition-model estimation and use reward-only estimation | Optimistic FP policy optimization for Player 2 · Single-controller transition | regret upper bound: \Regret_2(K) \leq \tilde{\cO} ( C \sqrt{ T } ) | No clear effect |
Closest papers by meaning
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.92)
- Provable Self-Play Algorithms for Competitive Reinforcement Learning (ICML 2020 · similarity 0.91)
- Towards General Function Approximation in Zero-Sum Markov Games (ICLR 2022 · similarity 0.91)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.91)
- Policy-Regret Minimization in Markov Games with Function Approximation (ICML 2025 · similarity 0.89)
- Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · 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.