Pseudonorm Approachability and Applications to Regret Minimization

Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balubramanian Sivan

Research output: Contribution to journalConference articlepeer-review


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. Finally, we illustrate the benefits of our framework by applying it to several problems in regret minimization.

Original languageEnglish (US)
Pages (from-to)471-509
Number of pages39
JournalProceedings of Machine Learning Research
StatePublished - 2023
Event34th International Conference onAlgorithmic Learning Theory, ALT 2023 - Singapore, Singapore
Duration: Feb 20 2023Feb 23 2023


  • Blackwell’s approachability
  • regret minimization
  • swap regret

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Pseudonorm Approachability and Applications to Regret Minimization'. Together they form a unique fingerprint.

Cite this