High-Probability Regret Bounds for Bandit Online Linear Optimization

By Peter L. Bartlett, Varsha Dani, T. Hayes, Sham M. Kakade, Alexander Rakhlin, Ambuj Tewari. 2008

130 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, positive): “By (Bartlett et al., 2008, Lemma 2), we have, with probability at least 1− δ log2 T , v>V̂Tv = T∑ `=0 E`−1X` ≤ T∑ `=0 X` + √√√√16 log(1/δ) T∑ `=0 var`−1(X`) + 2B2 log(1/δ) (12) ≤ T∑ `=0 X` + √√√√64B2 log(1/δ) T∑ `=0 E`−1X` + 2B2 log(1/δ) (13) ≤ T∑ `=0 X` + 1 2 T∑ `=0 E`−1X` + 34B2 log(1/δ) (14) =…”
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2011, methodology): “Let V denote the sum of conditional variances, Then, for every a, v > 0 , The proof of the following lemma is taken almost verbatim from (Bartlett et al., 2008), with the only modiﬁcation being the use of Theorem 6 to avoid an unnecessary union bound.”
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations (2013, background): “In addition, although we present our results in the framework of stochastic optimization, our analysis also applies to (multi-point) bandit online convex optimization problems [3], [4], [8], where our results are the sharpest provided to date.”
Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit (2012, methodology): “One idea would be to use techniques developed for adversarial bandits (see (Abernethy et al., 2008; Bartlett et al., 2008; Cesa-Bianchi and Lugosi, 2009; Koolen et al., 2010; Audibert et al., 2011), but also (Flaxman et al.”
Contextual Bandit Algorithms with Supervised Learning Guarantees (2010, unknown): “[3].”
Maximin effects in inhomogeneous large-scale data (2014, methodology): “, Audibert, Bubeck and Lugosi (2014), Auer, Cesa-Bianchi and Fischer (2002), Bartlett et al. (2008), Foster and Vohra (1999), Lai and Robbins (1985)].”
Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback. (2010, methodology): “We begin our analysis by stating a general upper bound on the regret of Online Gradient Descent, due to Bartlett et al. (2008b).”
Online Convex Optimization with Stochastic Constraints (2017, unknown): “See for example [24], [25], [10].”
Non-Stochastic Bandit Slate Problems (2010, background): “Our problem is a special case of the more general online linear optimization with bandit feedback problem [1, 4, 5, 11].”