Refined approachability algorithms and application to regret minimization with global costs
Author:
Preprint
Abstract
Blackwell's approachability is a framework where two players, the Decision Maker and the Environment, play a repeated game with vector-valued payoffs. The goal of the Decision Maker is to make the average payoff converge to a given set called the target. When this is indeed possible, simple algorithms which guarantee the convergence are known. This abstract tool was successfully used for the construction of optimal strategies in various repeated games, but also found several applications in online learning. By extending an approach proposed by (Abernethy et al., 2011), we construct and analyze a class of Follow the Regularized Leader algorithms (FTRL) for Blackwell's approachability which are able to minimize not only the Euclidean distance to the target set (as it is often the case in the context of Blackwell's approachability) but a wide range of distance-like quantities. This flexibility enables us to apply these algorithms to closely minimize the quantity of interest in various online learning problems. In particular, for regret minimization with $\ell_p$ global costs, we obtain the first bounds with explicit dependence in $p$ and the dimension $d$.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Exponential Weight Approachability, Applications to Calibration and Regret MinimizationDynamic Games and Applications, 2014
- Regret minimization in repeated matrix games with variable stage durationGames and Economic Behavior, 2008
- Primal-dual subgradient methods for convex problemsMathematical Programming, 2007
- Learning Permutations with Exponential Weights2007
- Efficient algorithms for online decision problemsJournal of Computer and System Sciences, 2005
- Path Kernels and Multiplicative UpdatesLecture Notes in Computer Science, 2002
- A General Class of Adaptive StrategiesJournal of Economic Theory, 2001
- Calibrated Learning and Correlated EquilibriumGames and Economic Behavior, 1997
- Consistency and cautious fictitious playJournal of Economic Dynamics and Control, 1995
- Optimal strategies in repeated games with incomplete informationInternational Journal of Game Theory, 1975