Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization

By Jacob D. Abernethy, Elad Hazan, Alexander Rakhlin. Annual Conference Computational Learning Theory, 2008

385 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/7aa0a143d8f2d89e8b71ead58a8f768716abbf81

How researchers see this paper

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

Citations in the corpus

Non-Stochastic Bandit Slate Problems (2010, methodology): “We are now able to formally state our main results: To compare, the best bounds obtained for the no-policies case using the more general algorithms [1] and [9] are O ( (cid:112) s 3 K ln( K/s ) T ) in the unordered slates problem, and O ( s 2 K ln( K ) T ) in the ordered slates problem.”
Online Multi-task Learning with Hard Constraints (2009, unknown): “Then our problem becomes an instance of an onlinelin-earoptimization problem studied by [AK04, MB04, GLLO07, DHK08, AHR08, BDH + 08, CBL09].”
Regret Bounds for Gaussian Process Bandit Problems (2010, unknown): “…of the classical framework (Robbins, 1952; Gittins and Jones, 1979; Berry and Fristedt, 1985; Auer et al., 2002; Cesa-Bianchi and Lugosi, 2006) have been developed (among many others, Abernethy et al., 2008; Slivkins and Upfal, 2008; Wang et al., 2008; Bubeck et al., 2008; Kleinberg et al., 2008b).”
A Modern Introduction to Online Learning (2019, methodology): “The INF algorithm was proposed by Audibert and Bubeck [2009] and re-casted as an OMD procedure in Audibert et al.”
Stochastic matrix games with bandit feedback (2020, background): “The main threads are (a) using the online convex optimisation view and modifying the regularizer [2, 10, 42], for example, and (b) modifying the loss estimates to obtain high probability regret or adaptive bounds [5, 20, 26, 1].”
Introduction to Online Convex Optimization (2016, methodology): “In the context of OCO, the term follow-the-regularized-leader was coined in (99; 96), and at roughly the same time an essentially identical algorithm was called “RFTL” in (2).”
Trading regret for efficiency: online convex optimization with long term constraints (2011, background): “We focus on the problem of online convex optimization, in which the goal is to achieve a low regret with respect to a fixed decision on a sequence of loss functions.”
Self-concordant analysis for logistic regression (2009, unknown): “Note that in the context of machine learning and statistics, self-concordant functions have been used for bandit optimization and online learning [18], but for barrier functions related to constrained optimization problems, and not directly for M-estimation.”
Partial Monitoring - Classification, Regret Bounds, and Algorithms (2014, background): “Various problems of interest can be modeled as partial monitoring instances, such as learning with expert advice [20], the multi-armed bandit problem [6], dynamic pricing [19], the dark pool problem [3], label efficient prediction [14], and linear and convex optimization with full or bandit feedback”
Towards Minimax Policies for Online Linear Optimization with Bandit Feedback (2012, methodology): “A similar regret bound can be obtained with a computationally efficient algorithm, using the technique developed by Abernethy et al. (2008). Here we show that in fact one can attain efficiently a regret of order √ dn log n using OSMD with the approriate regularizer F and random perturbation ãt.”
Online Learning with Predictable Sequences (2012, methodology): “Following Abernethy et al. (2008), at time t we define1 our randomized strategy qt to be a uniform distribution on the eigenvectors of ∇ 2R(ht) where ht ∈ F is given by a full-information procedure as described below.”
Better Algorithms for Benign Bandits (2009, methodology): “This regret degrades gracefully with increasing Q, and in the worst case, we recover the regret bound Õ( √ T ) of [1].”
Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization (2012, methodology): “, 2008; Abernethy et al., 2008) or Lipschitz-continous payoffs (Kleinberg et al., 2008), or bandits on trees (Kocsis & Szepesvári, 2006; Bubeck et al., 2008). The exploration-exploitation tradeoff has also been studied in Bayesian global optimization and response surface modeling, where Gaussian pro”
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.”
Sparsity, variance and curvature in multi-armed bandits (2017, background): “Since the groundbreaking work Abernethy et al. (2008) it has been realized that self-concordance (Nesterov and Nemirovski (1994)) exactly gives such a good conditioning for all directions.”
Online Learning: A Comprehensive Survey (2018, background): “In general, the lazy OMD has the same regret bound as FTRL.”