# Time-Dependent Blackwell Approachability and Application to Absorbing Games

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 58 references that are in the map.
- First posted on arXiv 9 Mar 2023.

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

- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications](https://mlsanity.com/paper/2108.03837/) (2021)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Approachability, Regret and Calibration; implications and equivalences](https://mlsanity.com/paper/1301.2663/) (2013)
- [Blackwell Online Learning for Markov Decision Processes](https://mlsanity.com/paper/2012.14043/) (2020)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [An Online Convex Optimization Approach to Blackwell's Approachability](https://mlsanity.com/paper/1503.00255/) (2015)
- [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)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)
- [A Zero-Sum Stochastic Game with Compact Action Sets and no Asymptotic Value](https://mlsanity.com/paper/1301.4540/) (2013)
- [Zero-sum repeated games: Counterexamples to the existence of the asymptotic value and the conjecture operatornamemaxmin=operatornamelimvn](https://mlsanity.com/paper/1305.4778/) (2013)
- [A Primal Condition for Approachability with Partial Monitoring](https://mlsanity.com/paper/1305.5399/) (2013)
- [Approachability of convex sets in generalized quitting games](https://mlsanity.com/paper/1609.08870/) (2016)

## Abstract (arXiv)

Blackwell's approachability (Blackwell, 1954, 1956) is a very general online learning framework where a Decision Maker obtains vector-valued outcomes, and aims at the convergence of the average outcome to a given ``target'' set. Blackwell gave a sufficient condition for the decision maker having a strategy guaranteeing such a convergence against an adversarial environment, as well as what we now call the Blackwell's algorithm, which then ensures convergence. Blackwell's approachability has since been applied to numerous problems, in regret minimization and game theory, in particular. We extend this framework by allowing the outcome function and the inner product to be time-dependent. We establish a general guarantee for the natural extension to this framework of Blackwell's algorithm. In the case where the target set is an orthant, we present a family of time-dependent inner products which yields different convergence speeds for each coordinate of the average outcome. We apply this framework to absorbing games (an important class of stochastic games) for which we construct varepsilon-uniformly optimal strategies using Blackwell's algorithm in a well-chosen auxiliary approachability problem, thereby giving a novel illustration of the relevance of online learning tools for solving games.