# Blackwell's Approachability with Approximation Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 15 references that are in the map.
- First posted on arXiv 6 Feb 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Approachability, Regret and Calibration; implications and equivalences](https://mlsanity.com/paper/1301.2663/) (2013)
- [Efficient Online Linear Optimization with Approximation Algorithms](https://mlsanity.com/paper/1709.03093/) (2017)
- [Online Improper Learning with an Approximation Oracle](https://mlsanity.com/paper/1804.07837/) (2018)
- [An Online Convex Optimization Approach to Blackwell's Approachability](https://mlsanity.com/paper/1503.00255/) (2015)

## Abstract (arXiv)

We revisit Blackwell's celebrated approachability problem which considers a repeated vector-valued game between a player and an adversary. Motivated by settings in which the action set of the player or adversary (or both) is difficult to optimize over, for instance when it corresponds to the set of all possible solutions to some NP-Hard optimization problem, we ask what can the player guarantee textitefficiently, when only having access to these sets via approximation algorithms with ratios αmX ≥ 1 and  1 ≥ αmY > 0, respectively. Assuming the player has monotone preferences, in the sense that he does not prefer a vector-valued loss ℓ1 over ℓ2 if ℓ2 ≤ ℓ1, we establish that given a Blackwell instance with an approachable target set S, the downward closure of the appropriately-scaled set αmXαmY-1S is textitefficiently approachable with optimal rate. In case only the player's or adversary's set is equipped with an approximation algorithm, we give simpler and more efficient algorithms.