The Price of Bandit Information for Online Optimization

By Varsha Dani, T. Hayes, Sham M. Kakade. 2007

243 citations recorded by the source corpus.

Subfields: Reinforcement Learning, Statistical Learning Theory

How researchers see this paper

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

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Off-policy evaluation for slate recommendation (2016, methodology): “At a technical level, the PI estimator has been used in online learning [7, 31, 11], but the analysis there is tailored to the specific data collection policies used by the learner.”
Introduction to Online Convex Optimization (2016, background): “Dani, Kakade and Hayes (33) gave an optimal regret algorithm up to constants depending on the dimension.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “[71] that for K = [−1,1]d the minimax regret in the full information setting is at least of order √ dn, while under bandit feedback it is of order d √ n.”
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting (2009, background): “Precisely, where The proof methodology follows Dani et al. (2007) in that we relate the regret to the growth of the log volume of the conﬁdence ellipsoid — a novelty in our proof is showing how this growth is characterized by the information gain.”
Minimax Policies for Combinatorial Prediction Games (2011, methodology): “Finally in the bandit game, EXP 2 corresponds to the strategy proposed by Dani et al. (2008) and also to the ComBand strategy, studied under the L ∞ assumption in Cesa-Bianchi and Lugosi (2009) and under the L 2 assumption in Cesa-Bianchi and Lugosi (2010).”
Online Learning and Online Convex Optimization (2012, methodology): “In particular, [15] gave a non efficient algorithm whose regret is O(poly(d) √ T ), and later on, [2] derived an efficient algorithm with a similar regret bound using self-concordant regularizers.”
Multi-armed bandits in metric spaces (2008, background): “While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with exponentially or infinitely large strategy sets are still a topic of very active investigation [1, 3, 4, 5, 6, 9, 10, 11, 12, 14, 15, 16, 17].”
Stochastic Linear Optimization under Bandit Feedback (2008, background): “In other words, what is the price of bandit information? For the full information case, Dani et al. [2008] showed the regret is O∗( √ nT ) (which is tight up to log factors).”
Regret bounded by gradual variation for online convex optimization (2014, methodology): “More recently, [10] proposed an inefficient algorithm for online bandit linear optimization with the optimal regret bound O(poly(d) √ T ) based on multi-armed bandit algorithm.”
Learning to Optimize via Information-Directed Sampling (2014, background): “[12] show this bound is order optimal, in the sense that for any time horizon T and dimension d if the actions set is A = {0, 1}d, there exists a prior distribution over p such that infπ E [Regret(T, π)] ≥ c0 √”
Towards Minimax Policies for Online Linear Optimization with Bandit Feedback (2012, methodology): “Moreover this rate is optimal: there exists action sets (such as the hypercube) where the minimax rate is of orderd √ n —see [Dani et al., 2008].”
Contextual Bandits with Similarity Information (2009, background): “The bandit problems with large arm sets have been studied in [7, 2, 4, 6, 20, 28, 21, 15, 12, 13, 14, 5, 19, 24].”
Learning Structured Predictors from Bandit Feedback for Interactive NLP (2016, background): “(2000), Joachims (2002), Freund et al. (2003), Cortes et al.”
Combinatorial Bandits (2012, methodology): “Dani, Hayes, and Kakade [7] were the first to prove an expected regret bound with the optimal √ n dependence on the time horizon.”
Efficient Tracking of Large Classes of Experts (2011, result): “We refer to [1], [16], [17], [24], [35]–[38] for an incomplete but representative list of papers.”