Towards Minimax Policies for Online Linear Optimization with Bandit Feedback

By Sébastien Bubeck, Nicolò Cesa-Bianchi, Sham M. Kakade. 2012

175 citations recorded by the source corpus.

We address the online linear optimization problem with bandit feedback. Our contribution is twofold. First, we provide an algorithm (based on exponential weights) with a regret of order $\sqrt{d n \log N}$ for any finite action set with $N$ actions, under the assumption that the instantaneous loss is bounded by 1. This shaves off an extraneous $\sqrt{d}$ factor compared to previous works, and gives a regret bound of order $d \sqrt{n \log n}$ for any compact set of actions. Without further assumptions on the action set, this last bound is minimax optimal up to a logarithmic factor. Interestingly, our result also shows that the minimax regret for bandit linear optimization with expert advice in $d$ dimension is the same as for the basic $d$-armed bandit with expert advice. Our second contribution is to show how to use the Mirror Descent algorithm to obtain computationally efficient strategies with minimax optimal regret bounds in specific examples. More precisely we study two canonical action sets: the hypercube and the Euclidean ball. In the former case, we obtain the first computationally efficient algorithm with a $d \sqrt{n}$ regret, thus improving by a factor $\sqrt{d \log n}$ over the best known result for a computationally efficient algorithm. In the latter case, our approach gives the first algorithm with a $\sqrt{d n \log n}$ regret, again shaving off an extraneous $\sqrt{d}$ compared to previous works.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Statistical Learning Theory, Mathematical Optimization

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 Computer Networks and Communications

In Management Science and Operations Research

In Statistical Learning Theory

In Mathematical Optimization

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, background): “Keywords: Stochastic Convex Optimization; Derivative-Free Optimization; Bandit Convex Optimization; Regret”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “See [45] for the details of this transformation.”
Thompson Sampling for Contextual Bandits with Linear Payoffs (2012, methodology): “…(Woodroofe, 1979; Sarkar, 1991), associative reinforcement learning (Kaelbling, 1994), associative bandit problems (Auer, 2002; Strehl et al., 2006), bandit problems with expert advice (Auer et al., 2002), and linear bandits (Dani et al., 2008; Abbasi-Yadkori et al., 2011; Bubeck et al., 2012).”
Bandit Algorithms (2020, methodology): “Readers interested in an overview of online learning will like the short book by Hazan [2016] while the book by Cesa-Bianchi and Lugosi [2006] has a little more depth (but is also ten years older).”
Online Learning: A Comprehensive Survey (2018, background): “tter regret bound of O(ln(T)). The CUCB algorithm (Chen et al., 2016b) addresses the problem where the loss may be nonlinear. (Combes et al., 2015) provided a useful survey for closely related works (Bubeck et al., 2012; Cesa-Bianchi and Lugosi, 2012) and gave a novel algorithm with promising bounds”
Sparsity, variance and curvature in multi-armed bandits (2017, background): “Small variation bound for multi-armed bandit, Hazan and Kale (2009). Consider again the multi-armed bandit problem with the additional assumption that the loss sequence (`1, . . . , `T ) ∈ ([−1, 1]) has a small variation Q := ∑T t=1 ‖`t − 1 T ∑T s=1 `s‖(2)2 (note that Q ≤ nT ). The COLT 2011 open pr”
Contextual Bandits with Similarity Information (2009, methodology): “In particular, there exist algorithms with dY = 0 and cY = poly(d) (Dani et al., 2007; Abernethy et al., 2008; Bubeck et al., 2012).”
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms (2014, background): “In the context of adversarial bandits, several studies also consider combinatorial bandits (Cesa-Bianchi & Lugosi, 2009; Audibert et al., 2011; Bubeck et al., 2012).”