# An Online Convex Optimization Approach to Blackwell's Approachability

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2015.

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

- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [Pseudonorm Approachability and Applications to Regret Minimization](https://mlsanity.com/paper/2302.01517/) (2023)
- [Rate-Preserving Reductions for Blackwell Approachability](https://mlsanity.com/paper/2406.07585/) (2024)
- [Sparsity-Based Interpolation of External, Internal and Swap Regret](https://mlsanity.com/paper/2502.04543/) (2025)
- [Time-Dependent Blackwell Approachability and Application to Absorbing Games](https://mlsanity.com/paper/2303.04956/) (2023)
- [Blackwell's Approachability with Approximation Algorithms](https://mlsanity.com/paper/2502.03919/) (2025)
- [Playing Markov Games Without Observing Payoffs](https://mlsanity.com/paper/2509.00179/) (2025)
- [Blackwell Approachability and Gradient Equilibrium are Equivalent](https://mlsanity.com/paper/2606.27315/) (2026)
- [From Approachability Residuals to Anytime-Valid Evidence: The Online Convex Geometry of Testing by Betting](https://mlsanity.com/paper/2608.09450/) (2026)

## Abstract (arXiv)

The notion of approachability in repeated games with vector payoffs was introduced by Blackwell in the 1950s, along with geometric conditions for approachability and corresponding strategies that rely on computing em steering directions as projections from the current average payoff vector to the (convex) target set. Recently, Abernethy, Batlett and Hazan (2011) proposed a class of approachability algorithms that rely on the no-regret properties of Online Linear Programming for computing a suitable sequence of steering directions. This is first carried out for target sets that are convex cones, and then generalized to any convex set by embedding it in a higher-dimensional convex cone. In this paper we present a more direct formulation that relies on the support function of the set, along with suitable Online Convex Optimization algorithms, which leads to a general class of approachability algorithms. We further show that Blackwell's original algorithm and its convergence follow as a special case.