# Pseudonorm Approachability and Applications to Regret Minimization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 60 references that are in the map.
- First posted on arXiv 3 Feb 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022)
- [A Simple Reward-free Approach to Constrained Reinforcement Learning](https://mlsanity.com/paper/2107.05216/) (2021)
- [Efficient Convex Optimization with Membership Oracles](https://mlsanity.com/paper/1706.07357/) (2017)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash Dynamics](https://mlsanity.com/paper/2210.07152/) (2022)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [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)
- [Refined approachability algorithms and application to regret minimization with global costs](https://mlsanity.com/paper/2009.03831/) (2020)
- [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, 5 of 5)

- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [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)
- [Efficient Opportunistic Approachability](https://mlsanity.com/paper/2602.21328/) (2026)

## Abstract (arXiv)

Blackwell's celebrated approachability theory provides a general framework for a variety of learning problems, including regret minimization. However, Blackwell's proof and implicit algorithm measure approachability using the ℓ2 (Euclidean) distance. We argue that in many applications such as regret minimization, it is more useful to study approachability under other distance metrics, most commonly the ℓ_∞-metric. But, the time and space complexity of the algorithms designed for ℓ_∞-approachability depend on the dimension of the space of the vectorial payoffs, which is often prohibitively large. Thus, we present a framework for converting high-dimensional ℓ_∞-approachability problems to low-dimensional pseudonorm approachability problems, thereby resolving such issues. We first show that the ℓ_∞-distance between the average payoff and the approachability set can be equivalently defined as a pseudodistance between a lower-dimensional average vector payoff and a new convex set we define. Next, we develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for ℓ2 and other norms, showing that it can be achieved via online linear optimization (OLO) over a convex set given by the Fenchel dual of the unit pseudonorm ball. We then use that to show, modulo mild normalization assumptions, that there exists an ℓ_∞-approachability algorithm whose convergence is independent of the dimension of the original vectorial payoff. We further show that that algorithm admits a polynomial-time complexity, assuming that the original ℓ_∞-distance can be computed efficiently. We also give an ℓ_∞-approachability algorithm whose convergence is logarithmic in that dimension using an FTRL algorithm with a maximum-entropy regularizer.