Research map / Bandits and online learning / Online convex optimization and games
Learning Rationalizable Equilibria in Multiplayer 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 iterative empirical best responses to find one rationalizable action profile instead of identifying all rationalizable actions | Learning rationalizable action profiles · Rationalizable action profile | sample complexity: \Omega(A^{N-1}\Delta^{-2}) -> \widetilde{O}\left(\frac{LNA}{\Delta^2}\right) | Helped |
| Constrain Hedge learning to the rationalizable region using rationalizable initialization, correlated exploration, and clipping | Learning rationalizable ε-CCE · Rationalizable ε-CCE | sample complexity: \widetilde{O}\left(\frac{N\cdot A^N}{\Delta^2}+\frac{A}{\epsilon^2}\right) -> \widetilde{O}\left(\frac{LNA}{\Delta^2} + | Helped |
| Use adaptive Hedge rates and per-recommendation progress tracking to preserve rationalizability in the swap-regret reduction | Learning rationalizable ε-CE · Rationalizable ε-CE | sample complexity: \Tilde{O}\left(\frac{LNA}{\Delta^2}+\frac{NA^2}{\min\{\Delta^2,\epsilon^2\}}\right) | Helped |
| Apply the rationalizable CCE algorithm to a two-player zero-sum game | Rationalizable ε-Nash learning · Two-player zero-sum game | sample complexity: \Tilde{O}\left(\frac{A^3}{\Delta^4}+\frac{A}{\epsilon^2}\right) -> \widetilde{O}\left(\frac{LA}{\Delta^2} + \frac{A}{\ep | Helped |
| Use black-box equilibrium solvers with support expansion instead of the paper's specialized Hedge algorithms | Rationalizable CCE and CE learning · Rationalizable CCE and CE | sample complexity: \widetilde{O}\left(\frac{N^2A^2}{\min\{\epsilon^2,\Delta^2\}}\right); \widetilde{O}\left(\frac{N^2A^3}{\min\{\epsilon^2, | Mixed |
| Use correlated exploration, with one player exploring at a time | Rationalizable ε-CCE learning · Rationalizable ε-CCE | sample complexity: \widetilde{O}\left(\frac{A}{\epsilon^2}\right) -> \widetilde{O}\left(\frac{NA}{\epsilon^2}\right) | Hurt |
Closest papers by meaning
- When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? (ICLR 2022 · similarity 0.91)
- Learning to Correlate in Multi-Player General-Sum Sequential Games (NeurIPS 2019 · similarity 0.90)
- Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games (NeurIPS 2023 · similarity 0.90)
- Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.89)
- A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning (ICLR 2024 · similarity 0.89)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 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.