# Efficient Opportunistic Approachability

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

## Key facts

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

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

- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Near-Optimal Algorithms for Omniprediction](https://mlsanity.com/paper/2501.17205/) (2025)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [High dimensional online calibration in polynomial time](https://mlsanity.com/paper/2504.09096/) (2025)
- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games](https://mlsanity.com/paper/2412.20291/) (2024)
- [Faster Recalibration of an Online Predictor via Approachability](https://mlsanity.com/paper/2310.17002/) (2023)
- [Approachability in unknown games: Online learning meets multi-objective optimization](https://mlsanity.com/paper/1402.2043/) (2014)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Pseudonorm Approachability and Applications to Regret Minimization](https://mlsanity.com/paper/2302.01517/) (2023)

## Abstract (arXiv)

We study the problem of opportunistic approachability: a generalization of Blackwell approachability where the learner would like to obtain stronger guarantees (i.e., approach a smaller set) when their adversary limits themselves to a subset of their possible action space. Bernstein et al. (2014) introduced this problem in 2014 and presented an algorithm that guarantees sublinear approachability rates for opportunistic approachability. However, this algorithm requires the ability to produce calibrated online predictions of the adversary's actions, a problem whose standard implementations require time exponential in the ambient dimension and result in approachability rates that scale as T-O(1/d). In this paper, we present an efficient algorithm for opportunistic approachability that achieves a rate of O(T-1/4) (and an inefficient one that achieves a rate of O(T-1/3)), bypassing the need for an online calibration subroutine. Moreover, in the case where the dimension of the adversary's action set is at most two, we show it is possible to obtain the optimal rate of O(T-1/2).