# Rate-Preserving Reductions for Blackwell Approachability

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 10 Jun 2024.

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

- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash Dynamics](https://mlsanity.com/paper/2210.07152/) (2022)
- [Selling to Multiple No-Regret Buyers](https://mlsanity.com/paper/2307.04175/) (2023)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces](https://mlsanity.com/paper/2310.19786/) (2023)
- [Approachability in unknown games: Online learning meets multi-objective optimization](https://mlsanity.com/paper/1402.2043/) (2014)
- [An Online Convex Optimization Approach to Blackwell's Approachability](https://mlsanity.com/paper/1503.00255/) (2015)
- [Strategizing against No-Regret Learners in First-Price Auctions](https://mlsanity.com/paper/2402.08637/) (2024)
- [Efficient Phi-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games](https://mlsanity.com/paper/2402.09670/) (2024)
- [Pseudonorm Approachability and Applications to Regret Minimization](https://mlsanity.com/paper/2302.01517/) (2023)
- [Refined approachability algorithms and application to regret minimization with global costs](https://mlsanity.com/paper/2009.03831/) (2020)
- [Robust Repeated Auctions under Heterogeneous Buyer Behavior](https://mlsanity.com/paper/1803.00494/) (2018)
- [A differential game on Wasserstein space. Application to weak approachability with partial monitoring](https://mlsanity.com/paper/1811.04575/) (2018)

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

- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Sparsity-Based Interpolation of External, Internal and Swap Regret](https://mlsanity.com/paper/2502.04543/) (2025)
- [Swap Regret Minimization Through Response-Based Approachability](https://mlsanity.com/paper/2602.06264/) (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)

Abernethy et al. (2011) showed that Blackwell approachability and no-regret learning are equivalent, in the sense that any algorithm that solves a specific Blackwell approachability instance can be converted to a sublinear regret algorithm for a specific no-regret learning instance, and vice versa. In this paper, we study a more fine-grained form of such reductions, and ask when this translation between problems preserves not only a sublinear rate of convergence, but also preserves the optimal rate of convergence. That is, in which cases does it suffice to find the optimal regret bound for a no-regret learning instance in order to find the optimal rate of convergence for a corresponding approachability instance? We show that the reduction of Abernethy et al. (2011) does not preserve rates: their reduction may reduce a d-dimensional approachability instance I1 with optimal convergence rate R1 to a no-regret learning instance I2 with optimal regret-per-round of R2, with R2/R1 arbitrarily large (in particular, it is possible that R1 = 0 and R2 > 0). On the other hand, we show that it is possible to tightly reduce any approachability instance to an instance of a generalized form of regret minimization we call improper φ-regret minimization (a variant of the φ-regret minimization of Gordon et al. (2008) where the transformation functions may map actions outside of the action set). Finally, we characterize when linear transformations suffice to reduce improper φ-regret minimization problems to standard classes of regret minimization problems in a rate preserving manner. We prove that some improper φ-regret minimization instances cannot be reduced to either subclass of instance in this way, suggesting that approachability can capture some problems that cannot be phrased in the language of online learning.