Research map / Bandits and online learning / Online convex optimization and games
Best of Both Worlds: Regret Minimization versus Minimax Play
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.
Shows that bandit-feedback online learning can guarantee O(1) regret against a full-support comparator (e.g., the min-max strategy) and rate-optimal sqrt(T) regret against any fixed strategy, via phased-aggression importance-weighted OMD, for normal-form and extensive-form zero-sum games.
Problem
In repeated fair zero-sum games under bandit feedback, a player wants to never lose more than O(1) relative to minimax play while still exploiting suboptimal opponents at a rate of Theta(T) when possible, i.e., O(1) regret vs a safe comparator and tilde-O(sqrt(T)) regret vs any fixed strategy.
Approach
Adapts the full-information Phased Aggression template to bandit feedback by mixing a no-regret OMD iterate with the comparator strategy, using importance-weighted cost estimators, doubling the mixing weight on the iterate at phase restarts; extended to treeplexes with dilated KL for extensive-form games. A matching lower bound shows the 1/delta dependence on the comparator's minimum probability i
Key results
- For normal-form games with comparator of minimum probability delta, the algorithm achieves R(mu^c) <= 1 and max regret tilde-O(delta^{-1} sqrt(T)) under bandit feedback.
- A lower bound shows that any algorithm with R(mu^c) <= O(1) must suffer max regret Omega(sqrt(delta^{-1} T) - delta^{-3/4} T^{1/4}) in NFGs.
- In Kuhn poker experiments, the proposed algorithm never loses to min-max or OMD-style play in the symmetric setting and exploits BluffJ/RaiseKQ-type opponents near-optimally after an initial conservative phase.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Phased Aggression with Importance-Weighting instead of Min-Max play | Kuhn Poker · All vs BluffJ | units won | Helped |
| Use Phased Aggression with Importance-Weighting instead of Min-Max play | Kuhn Poker · All vs RaiseKQ | units won | Helped |
| Use Phased Aggression with Importance-Weighting instead of OMD | Kuhn Poker · All vs BluffJ and All vs RaiseKQ | units won | Helped |
| Use Phased Aggression with Importance-Weighting instead of Min-Max play | Kuhn Poker · All vs RandMinMax | units won | Helped |
| Use OMD instead of Min-Max play | Kuhn Poker · All vs All | units won | Hurt |
Surprising findings
- Under bandit feedback, O(1) regret against a single deterministic comparator forces Omega(AT) regret elsewhere, so a full-support comparator assumption is needed to circumvent this.
- OMD loses a similar amount against the proposed algorithm as it does against minimax play in the symmetric Kuhn poker experiment, so the no-regret component does not lose less than expected.
Limitations
- Requires the comparator to be bounded away from the boundary (full support); the guarantee degrades with 1/delta, and non-full-support equilibria need a restricted action set.
- Results are for oblivious opponents; adaptive opponents in zero-sum games are left open.
Experimental setup
Benchmarks: Kuhn poker
Metrics: cumulative units won vs opponents regret
Baselines: Min-Max equilibrium play OMD with dilated KL Exp3
Builds on: Phased Aggression online mirror descent Exp3
Closest papers by meaning
- Minimizing Regret on Reflexive Banach Spaces and Nash Equilibria in Continuous Zero-Sum Games (NeurIPS 2016 · similarity 0.92)
- Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes (NeurIPS 2019 · similarity 0.91)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.91)
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.90)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.90)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (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.