From External to Internal Regret

By Avrim Blum, Yishay Mansour. Journal of machine learning research, 2005

413 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/5f2f2c848397b4619eeaf61b649881f4df88cb9b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

On the Instability of Bitcoin Without the Block Reward (2016, methodology): “in a number of rounds sublinear in the number of possible strategies) [5, 6, 4, 14].”
Evolutionary Dynamics of Multi-Agent Learning: A Survey (2015, background): “(12) This form of regret, computed at each time step, is known as external regret, whereas internal regret is computed as the loss with respect to a policy that replaces a given action i with some other action j at each occurrence (Blum & Monsour, 2007).”
Efficient Tracking of Large Classes of Experts (2011, background): “1Other black-box reductions of forecasters for different notions of regret are available in the literature; for example, the conversion of forecasters achieving good external regret to ones achieving good internal regret [27], [28].”
Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals (2018, methodology): “ and the ﬁrst practical use for it, which may be of independent interest. Interestingly, the -player needs to only minimize the usual external regret, but the -player must minimize the swap regret (Blum and Mansour, 2007), a stronger notion of regret. While the resulting distribution is supported on”
Regret bounds for sleeping experts and bandits (2010, methodology): “Prediction with sleeping experts Freund et al. (1997) and Blum and Mansour (2005) have analyzed the sleeping experts problem in a different framework from the one we adopt here.”
A few good agents: multi-agent social learning (2008, background): “Consequently, the majority of existing MAL algorithms aim for convergence in self-play, particularly to NE [8, 5, 9, 14] or to a set of correlated equilibria (CE) [13, 3].”
On preserving non-discrimination when combining expert advice (2018, background): “We then suggest that the property of not performing better than the best predictor is also crucial; in particular, better algorithms that satisfy the stronger guarantee of low shifting regret [21, 6, 34] are also not able to guarantee this non-discrimination (Theorem 5).”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, background): “That is, to find x ∗ such that ( P ⊤ − I ) x ∗ = 0 , and Problem (12) is ubiquitous in science and machine learning, for example in online learning many algorithms require computing a stationary distribution of a Markov chain at each iteration(Greenwald et al., 2006; Blum & Mansour, 2007).”
Introduction to Multi-Armed Bandits (2019, background): “Swapping regret has been introduced (Blum and Mansour, 2007), who also provided an explicit transformation that takes an algorithm with a “standard” regret bound, and transforms it into an algorithm with a bound on swap regret.”
Prediction, learning, and games (2006, methodology): “The method of converting forecasters with small external regret into the ones with small internal regret described here was suggested by Stoltz and Lugosi [279] – see also Blum and Mansour [34] for a related result.”
Partial Monitoring - Classification, Regret Bounds, and Algorithms (2014, methodology): “The method is a two-level procedure motivated by Foster and Vohra [18], and Blum and Mansour [12].”
Multicalibration: Calibration for the (Computationally-Identifiable) Masses (2018, methodology): “Our algorithmic result for multicalibration bears similarity to works from the online learning literature (Blum & Mansour, 2007; Khot & Ponnuswami, 2008; Trevisan et al., 2009).”