Towards minimax policies for online linear optimization with bandit feedback

Introduction

In this paper we are interested in the dual setting, where the adversary plays on a dual action set, i.e., $\mathcal{A}$ and $\mathcal{Z}$ are such that $|a^{\top}z|\leq 1,\forall(a,z)\in\mathcal{A}\times\mathcal{Z}$.

In the full information case, the online optimization setting (for convex losses) was introduced by Zinkevich 2003. The specific online linear optimization problem with bandit feedback was first studied by McMahan and Blum 2004 and Awerbuch and Kleinberg 2004. Our first contribution to this problem is to complete the research program started by Dani et al. 2008 and Cesa-Bianchi and Lugosi 2011. In these papers the authors studied the exp2 (Expanded Exp) algorithm, also called Geometric Hedge, Expanded Hedge, or ComBand. This strategy applies to a finite set of actions; it assigns an exponential weight to each action, and then draws an action at random from the corresponding probability distribution. Using a basic estimation procedure (first used by Auer et al. 2002 for the basic multi-armed bandit problem), one can estimate the loss vector $z_{t}$. However, to control the range of the estimates, one has to mix the probability given by exp2 with an ”exploration distribution”. Dani et al. 2008 chose this distribution to be uniform over a barycentric spanner for the action set, while in (Cesa-Bianchi and Lugosi 2011) the distribution was uniform over all actions. Using ideas from convex geometry, we propose a new distribution that allows us to derive a minimax optimal regret bound. More precisely, we show that for any finite action set, exp2 with the exploration distribution given by John’s Theorem (see Theorem 3) attains a regret of order $\sqrt{dn\log N}$ for any set of $N$ actions. This improves by a factor $\sqrt{d}$ over previous works. Moreover this rate is optimal: there exists action sets (such as the hypercube) where the minimax rate is of order $d\sqrt{n}$ —see (Dani et al. 2008). Surprisingly, this result also shows that Exp2 with John’s exploration can be used for linear bandits with $N$ experts to obtain a regret of order $\sqrt{dn\log N}$, which is no worse than the minimax regret for the basic $d$-armed bandit with $N$ experts problem.

While these results show that, without further assumption on the set of action, the regret of exp2 is optimal, they do not say anything about optimality for a specific set of actions. In fact, it was proven by Audibert et al. 2011 that for some pair $(\mathcal{A},\mathcal{Z})$ the exponential weights is a provably suboptimal strategy (with a gap of order $\sqrt{d}$). To address this issue, another class of algorithms has been studied for online optimization: the Mirror Descent style algorithms of Nemirovski and Yudin 1983 —this class of algorithms was rediscovered in the learning community, see for example Kivinen and Warmuth 2001. In recent years the number of papers using Mirror Descent to solve problems in online optimization has been growing very rapidly. In the full information setting (when one observes $z_{t}$), we have a very good understanding of how to use Mirror Descent to obtain optimal regret bounds that adapt to the geometry of the problem —see (Rakhlin 2009; Hazan 2011; Bubeck 2011). In particular, a recent paper suggests that in this basic setting Mirror Descent is ”universal”, see (Srebro et al. 2011). On the other hand, in the limited feedback scenario the picture is much more scattered. In the particular cases of semi-bandit feedback —see (Audibert et al. 2011)— and two-points bandit feedback —see (Agarwal et al. 2010), we know how to use Mirror Descent to obtain optimal regret bounds. However, in both scenarios the feedback is much stronger than in the more fundamental bandit problem. In this latter case, there is only one paper that successfully applies Mirror Descent, namely the seminal work of Abernethy et al. 2008 —see also the follow-up paper Abernethy and Rakhlin 2009. Unfortunately, for a convex and compact set $\mathcal{A}$, this approach (which combines Mirror Descent with a self-concordant barrier for the action set) leads to a regret bound of order $d\sqrt{\theta n\log n}$ for any $\theta>0$ such that $\mathcal{A}$ admits a $\theta$-self concordant barrier. For example, in the case of the hypercube the best we know is $\theta=O(d)$, which results in the suboptimal $d^{3/2}\sqrt{n\log n}$ regret (compared to $d\sqrt{n}$ for exp2 with John’s ellipsoid). However, note that in this particular case it is not known if exp2 can be implemented efficiently, while Mirror Descent is polynomial time.

Our second main contribution is to propose an efficient algorithm based on Mirror Descent, with an optimal regret bound for two canonical pairs $(\mathcal{A},\mathcal{Z})$. Namely, the (hypercube, cross-polytope) pair, which corresponds to an $L_{\infty}/L_{1}$ type of constraints, and the (Euclidean ball, Euclidean ball) pair, which corresponds to an $L_{2}/L_{2}$ constraint. In the former case this results in the first computationally efficient algorithm with a regret of order $d\sqrt{n}$, while in the latter case it is the first efficient algorithm with a regret of order $\sqrt{dn\log n}$. Indeed, the approach of Abernethy et al. 2008 only gives $d\sqrt{n\log n}$ for the pair (Euclidean ball, Euclidean ball) since there exists a $O(1)$-self concordant barrier for the Euclidean ball. Note also that this specific example was studied in Abernethy and Rakhlin 2009, we discuss their result in Section 5.

2 Outline of the paper

The paper is organized as follows. In Section 2 we introduce the two algorithms discussed in the paper: Expanded Exp (exp2) and Online Stochastic Mirror Descent (osmd). In both cases we state a general regret bound. In Section 3 we detail our exploration strategy for exp2, and show the corresponding regret bound. We also discuss briefly the extension to linear bandits with expert advice. Then in Section 4 (respectively Section 5) we show how to use osmd to obtain a computationally efficient strategy with optimal regret for the hypercube (respectively for the Euclidean ball, up to a logarithmic factor).

Algorithms

We briefly describe here the two algorithmic templates that we shall use in this paper. First, exp2 is described in Figure 1. The general regret bound for this algorithm is the following. The proof of this result follows a standard argument, see for example [Chapter 7, Bubeck 2011].

Let $\mathcal{A}$ be a finite set of $N$ actions. For the exp2 strategy, provided that $\eta|a^{\top}\widetilde{z}_{t}|\leq 1,\forall a\in\mathcal{A},$ one has

Figure 2 describes osmd in the bandit setting. Note that step (c) can be written in several equivalent ways, such as a Follow The Regularized Leader equation, or a mirror gradient descent step if $F$ is a Legendre function. When written as a gradient descent step, one usually has to project back on $\mathcal{A}$ (using the Bregman divergence associated to $F$). Here the projection is implicit in the evaluation of $\nabla F^{*}$. The following theorem states a general regret bound for osmd. Recall that the Bregman divergence with respect to $F$ is defined as $D_{F}(x,y)=F(x)-F(y)-(x-y)^{\top}\nabla F(y)$, and the Legendre-Fenchel dual of $F$ is defined as $F^{*}(v)=\sup_{x\in\mathcal{A}}x^{\top}v-F(x)$. In the following, we write $x_{1}^{t}$ to denote $x_{1}+\cdots+x_{t}$.

Proof The proof is adapted from Kakade et al. 2010. Using Young’s inequality, one obtains $\forall a\in\mathcal{A}$

since $F^{*}(0)=-F(a_{1})$. This shows that:

Taking into account the randomness induced by $\widetilde{a}_{t}$ and $\widetilde{z}_{t}$ is then an easy exercise, see for example (Bubeck 2011, Chapter 7). This theorem proves to be particularly useful when applied with a Legendre function $F$ —see (Cesa-Bianchi and Lugosi 2006, Chapter 11) for the definition of a Legendre function. Indeed, in that case $F^{*}$ is differentiable if $F$ is differentiable, and moreover the corresponding gradient mappings are inverse of each other, which gives a simple way to do computations with the Bregman divergence $D_{F^{*}}$.

exp2 with John’s exploration

We propose here a new exploration distribution $\mu$ for the exp2 strategy, that allows us to derive the first $\sqrt{dn\log N}$ regret bound for online linear optimization with bandit feedback. We use the following result from convex geometry, see (Ball 1997) for a proof.

To use this theorem, we need to perform a preprocessing of the action set as follows:

We can now assume that we are playing on $\mathcal{A}^{\prime}=H^{-1}\mathcal{A}$, and the loss of playing $a^{\prime}\in\mathcal{A}^{\prime}$ when the adversary plays $z$ is $\langle a^{\prime},z\rangle$. Indeed: $\langle H^{-1}a,z\rangle=a^{\top}z$. Moreover, note that John’s ellipsoid for $Conv(\mathcal{A}^{\prime})$ is the unit ball for the inner product $\langle\cdot,\cdot\rangle$ because $\langle H^{-1}x,H^{-1}x\rangle=x^{\top}H^{-1}x$.

Find the contact points $u_{1},\ldots,u_{M}$ and $\mu\in\Delta_{M}$ that satisfy Theorem 3 for $Conv(\mathcal{A}^{\prime})$. Note that the contact points are in $\mathcal{A}^{\prime}$, thus they are valid points to play. We say that $\mu$ is John’s exploration distribution.

In the following we drop the prime on $\mathcal{A}^{\prime}$. More precisely. we play on a set $\mathcal{A}$ such that John’s ellipsoid for $Conv(\mathcal{A})$ is the unit ball for some inner product $\langle\cdot,\cdot\rangle$, and the loss is given by $\langle a,z\rangle$. Thus, we also need to slightly change the algorithm to account for the fact that the loss is now an arbitrary scalar product. Step (c) in Figure 1 is modified as:

Note that this matrix is invertible, since $\mathcal{A}$ is of full rank and ${p}_{t}(a)>0$, $\forall a\in\mathcal{A}$. The estimate for $z_{t}$ is given by:

Note that this is a valid estimate since $\left({a}_{t}\otimes{a}_{t}\right)z_{t}=\langle{a}_{t},z_{t}\rangle{a}_{t}$ and $P_{t}^{-1}$ are observed quantities. Moreover, it is also clearly an unbiased estimate. We can now prove the following result.

exp2 with John’s exploration and estimate (1) satisfies, for $\frac{\eta d}{\gamma}\leq 1$,

In particular with $\gamma=\eta d$ and $\eta=\sqrt{\frac{\log N}{3nd}}$ we have that

Now we use a spectral decomposition of $P_{t}$ in an orthonormal basis for $\langle\cdot,\cdot\rangle$ and write $P_{t}=\sum_{i=1}^{d}\lambda_{i}v_{i}\otimes v_{i}.$ In particular, we have $P_{t}^{-1}=\sum_{i=1}^{d}\frac{1}{\lambda_{i}}v_{i}\otimes v_{i}$ and thus:

where the last inequality follows from the fact that $\langle a,a\rangle\leq 1$ for any $a\in\mathcal{A}$, since $\mathcal{A}$ is included in the unit ball. Now to conclude the proof we need to lower bound the smallest eigenvalue of $P_{t}$. Using Theorem 3, one can see that $P_{t}\succeq\frac{\gamma}{d}I_{d}$, and thus $\lambda_{i}\geq\frac{\gamma}{d}$ concluding the proof. Using the discretization argument of Dani et al. 2008, exp2 with John’s exploration can be used to obtain a regret of order $\sqrt{dn\log n}$ for any compact set of action $\mathcal{A}$.

If $\mathcal{A}$ is given by a finite set of points, then Grötschel et al. 1993 give a polynomial time algorithm for computing a constant factor approximation to the John’s ellipsoid (and this approximate basis will provide the same order of regret). However, if $\mathcal{A}$ is specified by the intersection of half spaces, then Nemirovski 2007 shows that obtaining such a constant factor approximation to this ellipsoid is NP-hard in general. Here, it is possible to efficiently compute an ellipsoid where the factor of $d$ in Theorem 3 is replaced by $d^{3/2}$ —see (Grötschel et al. 1993), which leads to a slightly worse dependence on $d$ in the regret bound.

In special cases, we conjecture that the John’s ellipsoid may be computed efficiently, as for certain problems, there are efficient implementations of GeometricHedge that lead to optimal rates (such as shortest path problems and other settings where dynamic programming solutions exists).

2 Application to bandits with experts

One can use exp2 with John’s exploration to obtain a regret of order $\sqrt{dn\log N}$ for this problem. Indeed, it suffices at every turn to do the preprocessing step on $\mathcal{A}_{t}=\{a_{t}(1),\ldots,a_{t}(N)\}$ and to build the corresponding John’s exploration $\mu_{t}$, the straightforward details are omitted.

Computationally efficient strategy for the hypercube

together with the following perturbation of a point $a_{t}$ in the interior of $\mathcal{A}$:

With probability $\gamma$, play $\widetilde{a}_{t}$ uniformly at random from the canonical basis (with random sign). With probability $1-\gamma$, play $\widetilde{a}_{t}=\xi_{t}$ where $\xi_{t}(i)$ is drawn from a Rademacher with parameter $\frac{1+a_{t}(i)}{2}$.

It is easy to check that this perturbation is almost unbiased, indeed one has:

In particular, with $\gamma=2d\sqrt{\frac{\log 2}{3n}}$ and $\eta=\sqrt{\frac{\log 2}{3n}}$,

Remark that the regularizer (2) used here is in the class of Legendre functions with exchangeable Hessian. More precisely, following Audibert et al. 2011, (2) can be written (up to a numerical constant) as

This type of regularizer was first studied (implicitely) by Audibert and Bubeck 2009 and Audibert and Bubeck 2010.

For the first term it is easy to see that $F(a)-F(a_{1})\leq d\log 2$. For the term involving the Bregman divergence, using elementary computations one obtains

To prove (4) we need to show that $D_{F^{*}}(u,v)\leq\sum_{i=1}^{d}\bigl(1-\tanh^{2}(v_{i})\bigr)(u_{i}-v_{i})^{2}$. In fact, we prove that this inequality is true as soon as $\|u-v\|_{\infty}\leq\frac{1}{2}$. The fact that the property is satisfied for the pair $(u,v)=\bigl(-\eta\widetilde{z}_{1}^{t},-\eta\widetilde{z}_{1}^{t-1}\bigr)$ under consideration is established at the very end of the proof.

Using a basic hyperbolic identity, and the elementary inequalities $\exp(x)\leq 1+x+x^{2},\forall x:|x|\leq 1$ and $\log(1+x)\leq x$, one obtains

which concludes the proof of (4). Now for the proof of (5) we first compute the matrix $P_{t}$:

To conclude the proof it remains now to show that $\eta||\widetilde{z}_{t}||_{\infty}\leq\frac{1}{2}.$ First note that the smallest eigenvalue of $P_{t}$ is larger than $\gamma/d$, and thus:

where the penultimate inequality follows from $|e_{i}^{\top}\widetilde{a}_{t}|\leq 1$ and the last inequality follows from the assumption on $\eta$ and $\gamma$.

Improved regret for the Euclidean ball

Let $\xi_{t}$ be a Bernoulli of parameter $\|a_{t}\|$, let $I_{t}$ be drawn uniformly at random in $\{1,\ldots,d\}$, and let $\varepsilon_{t}$ be Rademacher with parameter $\frac{1}{2}$. If $\xi_{t}=1$, then play $\widetilde{a}_{t}=a_{t}/\|a_{t}\|$, else play $\widetilde{a}_{t}=\varepsilon_{t}e_{I_{t}}$.

Note that the problem studied in this section was also specifically considered in Abernethy and Rakhlin 2009, with an emphasis on high probability bounds. In this paper the authors used the self-concordant barrier $F(x)=-\log(1-\|x\|^{2})$ with a similar perturbation scheme to the one proposed above. They obtain suboptimal rates, but a more careful analysis (precisely slightly modifying Section V.B., step (E)) can actually yield the same rate than the one we obtain. The strength of our approach is that it is in a sense more elementary (e.g., we do not require any results from the Interior Point Methods literature), but on the other hand the result of Abernethy and Rakhlin 2009 holds with high probability (though it is not clear if it possible to get the rate $\sqrt{dn\log n}$ with high probability).

In particular, with $\gamma=\frac{1}{\sqrt{n}}$ and $\eta=\sqrt{\frac{\log n}{2nd}}$,

Proof First, it is clear that by playing on $\mathcal{A}^{\prime}$ instead of $\mathcal{A}$, one incurs an extra $\gamma n$ regret. Second, note that $F$ is stricly convex (it is the composition of a convex and nondecreasing function with the euclidean norm), differentiable, and

The first term is clearly bounded by $\tfrac{1}{\eta}\log\tfrac{1}{\gamma}$ (we use the fact that $a_{1}=0$). For the second term we need to do a few computations (the first one follows from (9) and the fact that $F$ is Legendre):

Let $\Theta(u,v)$ such that $D_{F^{*}}(u,v)=\frac{1}{1+\|v\|}\Theta(u,v)$. First note that

Thus, in order to prove (7) it remains to show that $\Theta(u,v)\leq\|u-v\|^{2}$, for $(u,v)=\bigl(-\eta\widetilde{z}_{1}^{t},-\eta\widetilde{z}_{1}^{t-1}\bigr)$. In fact we shall prove that this inequality holds true as soon as $\frac{\|u\|-\|v\|}{1+\|v\|}\geq-\frac{1}{2}.$ This is the case for the pair $(u,v)$ under consideration, since by the triangle inequality, equations (6) and (10), and the assumption on $\eta$:

Now using that $\log(1+x)\geq x-x^{2}$, $\forall x\geq-\frac{1}{2}$, we obtain that for $u,v$ such that $\frac{\|u\|-\|v\|}{1+\|v\|}\geq-\frac{1}{2}$,

which concludes the proof of (7). Now for the proof of (8) it suffices to note that:

The first author would like to thank Csaba Szepesvári for bringing to his attention the problem of optimal regret on the Euclidean ball, as well as Alexander Rakhlin for illuminating discussions regarding sampling schemes. He also thank Ramon Van Handel, Vianney Perchet and Philippe Rigollet for stimulating discussions on this topic.

References