Research map / Bandits and online learning / Online convex optimization and games
Learning Not to Regret
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.
Meta-learns regret minimizers over a distribution of similar games, proposing Neural Predictive Regret Matching (NPRM), which converges an order of magnitude faster on river poker while retaining regret guarantees.
Problem
Equilibrium finding when a game is sampled from a distribution of similar games; existing regret minimizers are not tuned to the distribution, and learned neural update rules lack convergence guarantees.
Approach
Meta-learn a recurrent neural predictor inside predictive regret matching so that the regret minimizer is fast on the training distribution, while the bounded prediction keeps the O(sqrt(T)) regret guarantee for any game.
Key results
- On sampled river poker, NPRM reaches exploitability 0.02 in 118 steps versus 615 for RM and 793 for PRM, roughly an order of magnitude fewer.
- NPRM reduces exploitability roughly ten times faster than (P)RM on sampled river poker, and NPRM's advantage holds in wall-clock time (one minute for NPRM vs ~26 minutes for RM).
- On out-of-distribution uniform matrix games, NOA deteriorates significantly while NPRM keeps minimizing regret and even outperforms (P)RM.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Meta-learn NOA or NPRM instead of using RM or PRM | Regret minimization · river_poker (sampled) | steps to target exploitability: 615 -> 157; 793 -> 118 | Helped |
| Use NPRM instead of RM | Regret minimization · river_poker (sampled), target exploitability 2·10^{-2} | steps to target exploitability: 615 -> 118 | Helped |
| Use NPRM instead of PRM | Regret minimization · river_poker (sampled), target exploitability 2·10^{-2} | steps to target exploitability: 793 -> 118 | Helped |
| Train on rock_paper_scissors (sampled) and evaluate on uniform_matrix_game (sampled) | NOA · uniform_matrix_game (sampled) | regret | Hurt |
| Train on rock_paper_scissors (sampled) and evaluate on uniform_matrix_game (sampled) | NPRM · uniform_matrix_game (sampled) | regret | Helped |
| Add positive-part aggregation of instantaneous regrets (ablation) | NPRM · rock_paper_scissors (sampled) | convergence | Helped |
| Add positive-part aggregation of instantaneous regrets (ablation) | NOA · rock_paper_scissors (sampled) | convergence | Hurt |
| Use Hedge instead of regret matching to produce the strategy (ablation) | NPRM · rock_paper_scissors (sampled) | convergence | Hurt |
| Use Hedge instead of regret matching to produce the strategy (ablation) | Regret minimization algorithms · rock_paper_scissors (sampled) | convergence | Hurt |
Surprising findings
- RM performs similarly to PRM in the meta-learning setting, because the regret is minimized against an adversary/value function rather than self-play, where PRM's prediction advantage disappears.
- Meta-learned NOA, which is not guaranteed to be a regret minimizer, outperforms NPRM in the fixed-game setting, and NOA fails out of distribution.
Limitations
- NOA has no regret guarantee and degrades out-of-distribution.
- NPRM's performance is sensitive to the number of CFR+ iterations used in the value function, making evaluation partly out-of-distribution.
- Experiments are limited to a one-step lookahead on a single poker subgame and matrix games; self-play is not evaluated.
Experimental setup
Datasets: rock_paper_scissors (sampled) uniform_matrix_game (sampled) river_poker (sampled) river_poker (fixed)
Benchmarks: rock_paper_scissors (fixed) rock_paper_scissors (sampled) uniform_matrix_game (sampled) river_poker (sampled) river_poker (fixed)
Metrics: exploitability number of steps to target exploitability wall-clock time
Baselines: RM PRM CFR+ DCFR AutoCFR
Builds on: predictive regret matching regret matching CFR+ learning to learn
Closest papers by meaning
- Meta-Learning in Games (ICLR 2023 · similarity 0.91)
- ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret (ICLR 2023 · similarity 0.90)
- No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation (NeurIPS 2022 · similarity 0.89)
- Convergence of Regret Matching in Potential Games and Constrained Optimization (ICLR 2026 · similarity 0.89)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.89)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · 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.