# Solving optimization problems with Blackwell approachability

arXiv: https://arxiv.org/abs/2202.12277 · HTML: https://mlsanity.com/paper/2202.12277/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 68 references that are in the map.
- First posted on arXiv 24 Feb 2022.

## Builds on (most cited first, 21 of 21)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Scale-Free Algorithms for Online Linear Optimization](https://mlsanity.com/paper/1502.05744/) (2015)
- [Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions](https://mlsanity.com/paper/1910.10906/) (2019)
- [Scalable First-Order Methods for Robust MDPs](https://mlsanity.com/paper/2005.05434/) (2020)
- [Robust Markov Decision Process: Beyond Rectangularity](https://mlsanity.com/paper/1811.00215/) (2018)
- [Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games](https://mlsanity.com/paper/1809.03075/) (2018)
- [Revisiting CFR+ and Alternating Updates](https://mlsanity.com/paper/1810.11542/) (2018)
- [First-Order Methods for Wasserstein Distributionally Robust MDP](https://mlsanity.com/paper/2009.06790/) (2020)
- [Solving Large Sequential Games with the Excessive Gap Technique](https://mlsanity.com/paper/1810.03063/) (2018)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [Oracle-Based Robust Optimization via Online Learning](https://mlsanity.com/paper/1402.6361/) (2014)
- [Robust Policies For Proactive ICU Transfers](https://mlsanity.com/paper/2002.06247/) (2020)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [Computing large market equilibria using abstractions](https://mlsanity.com/paper/1901.06230/) (2019)

## Built on by (most cited first, 4 of 4)

- [Regret Matching+: (In)Stability and Fast Convergence in Games](https://mlsanity.com/paper/2305.14709/) (2023)
- [Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent](https://mlsanity.com/paper/2404.13891/) (2024)
- [Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games](https://mlsanity.com/paper/2311.00676/) (2023)
- [Time-Dependent Blackwell Approachability and Application to Absorbing Games](https://mlsanity.com/paper/2303.04956/) (2023)

## Abstract (arXiv)

We introduce the Conic Blackwell Algorithm^+ (CBA^+) regret minimizer, a new parameter- and scale-free regret minimizer for general convex sets. CBA^+ is based on Blackwell approachability and attains O(√T) regret. We show how to efficiently instantiate CBA^+ for many decision sets of interest, including the simplex, ℓp norm balls, and ellipsoidal confidence regions in the simplex. Based on CBA^+, we introduce SP-CBA^+, a new parameter-free algorithm for solving convex-concave saddle-point problems, which achieves a O(1/√T) ergodic rate of convergence. In our simulations, we demonstrate the wide applicability of SP-CBA^+ on several standard saddle-point problems, including matrix games, extensive-form games, distributionally robust logistic regression, and Markov decision processes. In each setting, SP-CBA^+ achieves state-of-the-art numerical performance, and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters.