Better Algorithms for Benign Bandits

By Elad Hazan, Satyen Kale. 2009

94 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

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

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Doubly Robust Policy Evaluation and Optimization (2014, background): “For benign bandits , Hazan and Kale (2009) construct algorithms which use reward estimators to improve regret bounds when the variance of actual re-wards is small.”
Doubly Robust Policy Evaluation and Learning (2011, background): “For benign bandits , Hazan & Kale (2009) construct algorithms which use reward estimators in order to achieve a worst-case regret that depends on the variance of the bandit rather than time.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, positive): “More precisely, based on the sparse planning idea of Kearns et al. [2002], Kocsis and Szepesvári [2006] introduced a new MCTS strategy called UCT (UCB applied to Trees) that led to a substantial advancement in Computer Go performance, see Gelly et al.”
Sparsity, variance and curvature in multi-armed bandits (2017, background): “4 Variation bound for multi-armed bandit We only give a brief sketch of proof of Theorem 2, as it is essentially a straightforward combination of the proof of Theorem 1 together with the arguments of Hazan and Kale (2009). In particular we ignore explicit numerical constants with the notation O.”
Contextual Bandits with Similarity Information (2009, methodology): “With this trick in mind, we will assume ﬁxed time horizon throughout this paper.”
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].”
Online Learning with Predictable Sequences (2012, methodology): “The same argument works for the case of bandit information, given that Mt can be constructed to estimate M ′t well (e.g. using the arguments of Hazan and Kale (2009)).”
Introduction to Multi-Armed Bandits (2019, background): “What if arms are not always available to be selected by the algorithm? The sleeping bandits model in Kleinberg et al. (2008a) allows arms to “fall asleep”, i.”
Regret bounded by gradual variation for online convex optimization (2014, methodology): “Similar to Hazan and Kale (2010), we aim to develop algorithms for online convex optimization with regret bounded by the variation in the cost functions.”