Online Learning with Predictable Sequences

Introduction

No-regret methods are studied in a variety of fields, including learning theory, game theory, and information theory . These methods guarantee a certain level of performance in a sequential prediction problem, irrespective of the sequence being presented. While such “protection” against the worst case is often attractive, the bounds are naturally pessimistic. It is, therefore, desirable to develop algorithms that yield tighter bounds for “more regular” sequences, while still providing protection against worst-case sequences. Some successful results of this type have appeared in within the framework of prediction with expert advice and online convex optimization.

In , a general game-theoretic formulation was put forth, with “regularity” of the sequence modeled as a set of restrictions on the possible moves of the adversary. Through a non-constructive theoretical analysis, the authors of pointed to the existence of quite general regret-minimization strategies for benign sequences, but did not provide a computationally feasible method. In this paper, we present algorithms that achieve some of the regret bounds of for sequences that can be roughly described as

This paper focuses on the setting of online linear optimization. The results achieved in the full-information case carry over to online convex optimization as well. To remind the reader of the setting, the online learning process is modeled as a repeated game with convex sets $\mathcal{F}$ and $\mathcal{X}$ for the learner and Nature, respectively. At each round $t=1,\ldots,T$, the learners chooses $f_{t}\in\mathcal{F}$ and observes the move $x_{t}\in\mathcal{X}$ of Nature. The learner suffers a loss of $\left\langle f_{t},x_{t}\right\rangle$ and the goal is to minimize regret, defined as

There are a number of ways to model “more regular” sequences. Let us start with the following definition. Fix a sequence of functions $M_{t}:\mathcal{X}^{t-1}\mapsto\mathcal{X}$, for each $t\in\{1,\ldots,T\}\triangleq[T]$. These functions define a predictable process

If, in fact, $x_{t}=M_{t}(x_{1},\ldots,x_{t-1})$ for all $t$, one may view the sequence $\{x_{t}\}$ as a (noiseless) time series, or as an oblivious strategy of Nature. If we knew that the sequence given by Nature follows exactly this evolution, we should suffer no regret.

Suppose that we have a hunch that the actual sequence will be “roughly” given by this predictable process: $x_{t}\approx M_{t}(x_{1},\ldots,x_{t-1})$. In other words, we suspect that the sequence is described as predictable process plus adversarial noise. Can we use this fact to incur smaller regret if our suspicion is correct? Ideally, we would like to “pay” only for the unpredictable part of the sequence.

Let us spend a minute explaining why such regret bounds are information-theoretically possible. The key is the following observation, made in . The non-constructive upper bounds on the minimax value of the online game involve a symmetrization step, which we state for simplicity of notation for the linear loss case with $\mathcal{F}$ and $\mathcal{X}$ being dual unit balls:

If we instead only consider sequences such that at any time $t\in[T]$, $x_{t}$ and $x^{\prime}_{t}$ have to be $\sigma_{t}$-close to the predictable process $M_{t}(x_{1},\ldots,x_{t-1})$, we can add and subtract the “center” $M_{t}$ on the left-hand side of the above equation and obtain tighter bounds for free, irrespective of the form of $M_{t}(x_{1},\ldots,x_{t-1})$. To make this observation more precise, let

be the set of allowed deviations from the predictable “trend”. We then have a bound

on the value of the game against such “constrained” sequences, where the constant $c$ depends on the smoothness of the norm. This short description only serves as a motivation, and the more precise statements about the value of a game against constrained adversaries can be found in .

The development so far is a good example of how a purely theoretical observation can point to existence of better prediction methods. What is even more surprising, for most of the methods presented below, the individual $\sigma_{t}$’s need not be known ahead of time except for their total sum $\sum_{t=1}^{T}\sigma_{t}^{2}$. Moreover, the latter sum need not be known in advance either, thanks to the standard doubling trick, and one can obtain upper bounds of

on regret, for some problem-dependent constant $c$.

Let us now discuss several types of statistics $M_{t}$ that could be of interest.

are known as path length bounds . Such bounds can be tighter than the pessimistic $O(\sqrt{T})$ bounds when the previous move of Nature is a good proxy for the next move.

are known as variance bounds . One may also consider fading memory statistics

or even plug in an auto-regressive model.

If “phases” are expected in the data (e.g., stocks tend to go up in January), one may consider

for some phase length $k$. Alternatively, one may consider averaging of the past occurrences $T_{j}(t)\subset\{1,\ldots,t\}$ of the current phase $j$ to get a better predictive power:

The use of a predictable process $(M_{t})_{t\geq 1}$ can be seen as a way of incorporating prior knowledge about the sequence $(x_{t})_{t\geq 1}$. Importantly, the bounds still provide the usual worst-case protection if the process $M_{t}$ does not predict the sequence well. To see this, observe that the bounds of the paper scale with $\sqrt{\sum_{t=1}^{T}\|x_{t}-M_{t}\|_{*}^{2}}\leq 2\max_{x\in\mathcal{X}}\|x\|\sqrt{T}$ which is only a factor of $2$ larger than the typical bounds. However when $M_{t}$’s do indeed predict $x_{t}$’s well we have low regret, a property we get almost for free. Notice that in all our analysis the predictable process $(M_{t})_{t\geq 1}$ can be any arbitrary function of the past.

The predictable process $M_{t}$ has been written so far as a function of $x_{1},\ldots,x_{t-1}$, as we assumed the setting of full-information online linear optimization (that is, $x_{t}$ is revealed to the learner after playing $f_{t}$). Whenever our algorithm is deterministic, we may reconstruct the sequence $f_{1},\ldots,f_{t}$ given the sequence $x_{1},\ldots,x_{t-1}$, and thus no explicit dependence of $M_{t}$ of the learner’s moves are required. More generally, however, nothing prevents us from defining the predictable process $M_{t}$ as a function

where $I_{s}$ is the information conveyed to the learner at step $s\in[T]$ (defined on the appropriate information space ${\mathcal{I}}$) and $q_{s}$ is the randomized strategy of the learner at time $s$. For instance, in the well-studied bandit framework, the feedback $I_{s}$ is defined as the scalar value of the loss $\left\langle f_{s},x_{s}\right\rangle$, yet the actual move $x_{s}$ may remain unknown to the learner. More general partial information structures have also been studied in the literature.

When $M_{t}$ is written in the form (3), it becomes clear that one can consider scenarios well beyond the partial information models. For instance, the information $I_{s}$ might contain better or complete information about the past, thus modeling a delayed-feedback setting (see Section 6.1). Another idea is to consider a setting where $I_{s}$ contains some state information pertinent to the online learning problem.

The paper is organized as follows. In Section 2, we provide a number of algorithms for full-information online linear optimization, taking advantage of a given predictable process $M_{t}$. These methods can be seen as being “optimistic” about the sequence, incorporating $M_{t+1}$ into the calculation of the next decision as if it were the true. We then turn to the partial information scenario in Section 3 and show how to use the full-information bounds together with estimation of the missing information. Along the way, we prove a bound for nonstochastic multiarmed bandits in terms of the loss of the best arm – a result that does not appear to be available in the literature. In Section 4 we turn to the question of learning $M_{t}$ itself during the prediction process. We present several scenarios which differ in the amount of feedback given to the learner. Finally, we consider delayed feedback and some other scenarios that fall under the general umbrella.

We remark that most of the regret bounds we present in this paper are of the form $A\eta^{-1}+B\eta\sum_{t=1}^{T}\|x_{t}-M_{t}\|_{*}^{2}$. If variation around the trend is known in advance, one may choose $\eta$ optimally to obtain the form in (2). Otherwise, we employ the standard doubling trick which we provide for completeness in Section 8. The doubling trick sets $\eta$ in a data-dependent way to achieve (2) with a slightly worse constant.

We use the notation $y_{t^{\prime}:t}$ to represent the sequence $y_{t^{\prime}},\ldots,y_{t}$. We also use the notation $x[i]$ to represent the $i^{th}$ element of vector $x$. We use the notation $x[1:c]$ to represent the $c$-dimensional vector $(x,\ldots,x[c])$. $D_{R}(f,f^{\prime})$ is used to represent the Bregman divergence between $f$ and $f^{\prime}$ w.r.t. function $R$. We denote the set $\{1,\ldots,T\}$ by $[T]$.

Full Information Methods

In this section we assume that the value $M_{t}$ is known at the beginning of round $t$: it is either calculated by the learner or conveyed by an external source. The first algorithm we present is a modification of the Follow the Regularized Leader (FTRL) method with a self-concordant regularizer. The advantage of this method is its simplicity and the close relationship to the standard FTRL. Next, we exhibit a Mirror Descent type method which can be seen as a generalization of the recent algorithm of . Later in the paper (in Section 5) we also present full-information methods based on the idea of a random playout, developed in for the problem of regret minimization in the worst case. To the best of our knowledge, these results are the first variation-style bounds for Follow the Perturbed Leader (FPL) algorithms.

For all the methods presented below, we assume (without loss of generality) that $M_{1}=0$. Since we assume that $M_{t}$ can be calculated from the information provided to the learner or the value of $M_{t}$ is conveyed from outside, we do not write the dependence of $M_{t}$ on the past explicitly.

Optimistic Follow the Regularized Leader Input: $\mathcal{R}$ self-concordant barrier, learning rate $\eta>0$. Initialize $f_{1}=\arg\min_{f\in\mathcal{F}}\mathcal{R}(f)$. At $t=1,\ldots,T$, predict $f_{t}$, observe $x_{t}$, and update $f_{t+1}=\arg\min_{f\in\mathcal{F}}~{}\eta\left\langle f,\sum_{s=1}^{t}x_{s}+M_{t+1}\right\rangle+\mathcal{R}(f)$

We notice that for $M_{t+1}=0$, the method reduces to the Follow the Regularized Leader (FTRL) algorithm of . When $M_{t+1}\neq 0$, the algorithm can be seen as “guessing” the next move and incorporating it into the objective. If the guess turns out to be correct, the method should suffer no regret, according to the “be the leader” analysis.

The following regret bound holds for the proposed algorithm:

as long as $\eta\|x_{t}-M_{t}\|_{t}^{*}<1/4$ for all $t$.

By the argument of , at the expense of an additive constant in the regret, the comparator $f^{*}$ can be taken from a smaller set, at a distance $1/T$ from the boundary. For such an $f^{*}$, we have $\mathcal{R}(f^{*})\leq\vartheta\log T$ where $\vartheta$ is a self-concordance parameter of $\mathcal{R}$.

2 Mirror-Descent algorithm

The next algorithm is a modification of a Mirror Descent (MD) method for regret minimization. Let $\mathcal{R}$ be a $1$-strongly convex function with respect to a norm $\|\cdot\|$, and let $D_{\mathcal{R}}(\cdot,\cdot)$ denote the Bregman divergence with respect to $\mathcal{R}$. Let $\nabla\mathcal{R}^{*}$ be the inverse of the gradient mapping $\nabla\mathcal{R}$. Let $\|\cdot\|_{*}$ be the norm dual to $\|\cdot\|$. We do not require $\mathcal{F}$ and $\mathcal{X}$ to be unit dual balls.

Such a two-projection algorithm for the case $M_{t}=x_{t-1}$ has been exhibited recently in .

where $R_{\max}^{2}=\max_{f\in\mathcal{F}}\mathcal{R}(f)-\min_{f\in\mathcal{F}}\mathcal{R}(f)$.

As mentioned before, the sum $\sum_{t=1}^{T}\|x_{t}-M_{t}\|_{*}^{2}$ need not be known in advance in order to set $\eta$, as the usual doubling trick can be employed. Both the Optimistic MD and Optimistic FTRL work in the setting of online convex optimization, where $x_{t}$’s are now gradients at the points chosen by the learner. Last but not least, notice that if the sequence is not following the trend $M_{t}$ as we hoped it would, we still obtain the same bounds as for the Mirror Descent (respectively, FTRL) algorithm, up to a constant.

The Optimistic Mirror Descent on the probability simplex enjoys, for any $f^{*}\in\mathcal{F}$,

as long as $\eta\|x_{t}-M_{t}\|_{\infty}\leq 1/4$ at each step.

Methods for Partial and Bandit Information

We now turn to the setting of partial information and provide a generic estimation procedure along the lines of . Here, we suppose that the learner receives only partial feedback $I_{t}$ which is simply the loss $\left\langle f_{t},x_{t}\right\rangle$ incurred at round $t$. Once again, we suppose to have access to some predictable process $M_{t}$. Note the generality of this framework: in some cases we might postulate that $M_{t}$ needs to be calculated by the learner from the available information (which does not include the actual moves $x_{t}$); in other cases, however, we may assume that some statistic $M_{t}$ (such as some partial information about the past moves) is conveyed to the learner as a side information from an external source. For the methods we present, we simply assume availability of the value $M_{t}$.

Hazan and Kale observed that the above algorithm can be modified by adding and subtracting an estimated mean of the adversarial moves at appropriate steps of the method. We use this idea with a general process $M_{t}$:

The analysis of the method is based on the bounds for full information predictable processes $M_{t}$ developed earlier, thus simplifying and generalizing the analysis of .

Hence, for any full-information statistic $M^{\prime}_{t}=M^{\prime}_{t}(x_{1},\ldots,x_{t-1})$,

Effectively, Hazan and Kale show in that for the full-information statistic $M^{\prime}_{t}(x_{1},\ldots,x_{t-1})=\frac{1}{t-1}\sum_{s=1}^{t-1}x_{s}$, there is a way to construct $M_{t}=M_{t}(I_{1},\ldots,I_{t-1},f_{1},\ldots,f_{t-1},q_{1},\ldots,q_{t-1})$ in such a way that the third term in (6) is of the order of the second term. This is done by putting aside roughly $O(\log T)$ rounds in order to estimate $M^{\prime}_{t}$, via a process called reservoir sampling. However, for more general functions $M^{\prime}_{t}$, the third term might have nothing to do with the second term, and the investigation of which $M^{\prime}_{t}$ can be well estimated by $M_{t}$ is an interesting topic of further research.

Learning The Predictable Processes

So far we have seen that the learner with an access to an arbitrary predictable process $(M_{t})_{t\geq 1}$ has a strategy that suffers regret of $O\left(\sqrt{\sum_{t=1}^{T}\|x_{t}-M_{t}\|_{*}^{2}}\right)~{}.$ Now if the predictable process is a good predictor of the sequence, then the regret will be low. This raises the question of model selection: how can the learner choose a good predictable process $(M_{t})_{t\geq 1}$? Is it possible to learn it online as we go, and if so, what does it mean to learn?

To formalize the concept of learning the predictable process, let us consider the case where we have a set $\Pi$ indexing a set of predictable processes (strategies) we are interested in. That is, each $\pi\in\Pi$ corresponds to predictable process given by $(M^{\pi}_{t})_{t\geq 1}$. Now if we had an oracle which in the start of the game told us which $\pi^{*}\in\Pi$ predicts the sequence optimally (in hindsight) then we could use the predictable process given by $(M^{\pi^{*}}_{t})_{t\geq 1}$ and enjoy a regret bound of

However we cannot expect to know which $\pi\in\Pi$ is the optimal one from the outset. In this scenario one would like to learn a predictable process that in turn can be used with algorithms proposed thus far to get a regret bound comparable with regret bound one could have obtained knowing the optimal $\pi^{*}\in\Pi$.

To motivate this setting better let us consider an example. Say there are $n$ stock options we can choose to invest in. On each day $t$, associated with each stock option one has a loss/payoff that occurs upon investing in a single share of that stock. Our goal in the long run is to have a low regret with respect to the single best stock in hindsight. Up to this point, the problem just corresponds to the simple experts setting where each of the $n$ stocks is one expert and on each day we split our investment according to a probability distribution over the $n$ options. However now additionally we allow the learner/investor access to prediction models from the set $\Pi$. These could be human strategists making forecasts, or outcomes of some hedge-fund model. At each time step the learner can query prediction made by each $\pi\in\Pi$ as to what the loss on the $n$ stocks would be on that day. Now we would like to have a regret comparable to the regret we can achieve knowing the best model $\pi^{*}\in\Pi$ that in hind-sight predicted the losses of each stock optimally. We shall now see how to achieve this.

The proof of the following lemma relies on a particular regret bound of [7, Corollary 2.3] for the exponential weights algorithm that is in terms of the loss of the best arm. Such a bound is an improvement over the pessimistic regret bound when the loss of the optimal arm is small.

where $R_{\max}^{2}=\max_{f\in\mathcal{F}}\mathcal{R}(f)-\min_{f\in\mathcal{F}}\mathcal{R}(f)$.

Once again, let us discuss what makes this setting different from the usual setting of experts. The forecast given by prediction models is in the form of a vector, one for each stock. If we treat each prediction model as an expert with the loss $\|x_{t}-M^{\pi}_{t}\|_{*}^{2}$, the experts algorithm would guarantee that we achieve the best cumulative loss of this kind. However, this is not the object of interest to us, as we are after the best allocation of our money among the stocks, as measured by $\operatorname*{\vphantom{p}inf}_{f\in\mathcal{F}}\sum_{t=1}^{T}\left\langle f,x_{t}\right\rangle$.

The algorithm can be seen as separating two steps: learning the model (that is, predictable process) and then minimizing regret given the learned process. This is implemented by a general idea of running another (secondary) regret minimizing strategy where loss per round is simply $\left\|M_{t}-x_{t}\right\|_{*}^{2}$ and regret is considered with respect to the best $\pi\in\Pi$. That is, regret of the secondary regret minimizing game is given by

In general, the experts algorithm for minimizing secondary regret can be replaced by any other online learning algorithm.

In the previous section we considered the full information setting where on each round we have access to $x_{t}$ and for each $\pi$ we get to see (or compute) $M_{t}^{\pi}$. However one might be in a scenario with only partial access to $x_{t}$ or $M_{t}^{\pi}$, or both. In fact, there are quite a number of interesting partial-information scenarios, and we consider some of them in this section.

In this setting at each time step $t$, we only observe the loss $\left<f_{t},x_{t}\right>$ and not all of $x_{t}$. However, for each $\pi\in\Pi$ we do get access to (or can compute) $M^{\pi}_{t}$ for each $\pi\in\Pi$. Consider the following algorithm:

The following lemma upper bounds the regret of this algorithm. The proof once again uses a regret bound in terms of the loss of the best arm [7, Corollary 2.3].

2.2 Partial Information about Predictable Process

Now let us consider the scenario where on each round we get to see $x_{t}\in\mathcal{X}$. However, we only see $M_{t}^{\pi_{t}}$ for a single $\pi_{t}\in\Pi$ we select on round $t$. This scenario is especially useful in the stock investment example provided earlier. While $x_{t}$ the vector of losses for the stocks on each day can easily be obtained at the end of the trading day, prediction processes might be provided as paid services by various companies. Therefore, we only get to access a limited number of forecasts on each day by paying for them. In this section, we provide an algorithm with corresponding regret bound for this case.

Due to the limited information about the predictable processes, the proofs of Lemmas 7 and 8 below rely on an improved regret bound for the multiarmed bandit, an analogue of [7, Corollary 2.3]. Such a bound is proved in Lemma 13 in Section 7.

where $R_{\max}^{2}=\max_{f\in\mathcal{F}}\mathcal{R}(f)-\min_{f\in\mathcal{F}}\mathcal{R}(f)$.

2.3 Partial Information about both Loss and Predictable Process

In the third partial information variant, we consider the setting where at time $t$ we only observe loss $\left\langle f_{t},x_{t}\right\rangle$ we suffer at the time step (and not entire $x_{t}$) and also only $M^{\pi_{t}}_{t}$ corresponding to the predictable process of $\pi_{t}\in\Pi$ we select at time $t$. This is a blend of the two partial-information settings considered earlier.

Randomized Methods and the Follow the Perturbed Leader Algorithm

The central object in the algorithmic development of is the notion of a relaxation. We now present this notion in the context of a constrained adversary in order to develop randomized methods that attain bounds in terms of the sizes $\sigma_{t}$ of deviations from the trend $M_{t}$. The downside of the methods we present in this section is that individual deviations $\sigma_{t}$ need to be known in advance by the learner. We believe that this requirement can be relaxed, and this will be added in the full version of this paper.

A relaxation $\mathbf{Rel}$ is a sequence of functions $\mathbf{Rel}_{T}\left(\mathcal{F}\middle|x_{1},\ldots,x_{t}\right)$ for each $t\in[T]$. We shall use the notation $\mathbf{Rel}_{T}\left(\mathcal{F}\right)$ for $\mathbf{Rel}_{T}\left(\mathcal{F}\middle|\{\}\right)$. For the problem of a constrained sequence, with constraints given by the sequence of $C_{1},\ldots,C_{T}$ (see Eq. (1)) a relaxation will be called admissible if for any $x_{1},\ldots,x_{T}\in\mathcal{X}$,

If $C_{t+1}(x_{1},\ldots,x_{t})=\mathcal{X}$ for all $t\in[T]$, we recover the setting of an unconstrained adversary studied in .

Any choice $q$ that ensures (10) for an admissible relaxation guarantees (irrespective of the strategy of the adversary) that

a fact that is easy to prove. It is shown in that for many problems of interest, when searching for a computationally feasible relaxation, one may start with the conditional sequential Rademacher complexity and find a computationally attractive upper bound. For the case of constrained adversaries, this complexity becomes (for the case of $\mathcal{F}$ being a unit ball)

Here, one may think of the adversary as choosing the $z_{t}$’s as small deviations from the predictable process $M_{t}$. The following step is a key idea: since the computation of the interleaved supremum and expectations is difficult, we might be able to come up with an almost-as-difficult distribution and draw $z_{t}$’s i.i.d. The following is an assumption that is easily verified for many symmetric distributions .

To satisfy this assumption, one may simply take one of the distributions in for the unconstrained case, and scale it by $\sigma_{t}$.

For the distributions $D_{1},\ldots,D_{T}$ satisfying Assumption 1, the relaxation

is admissible and a randomized strategy that ensures admissibility is given by: at time $t$, draw $z_{t+1},\ldots,z_{T}$ and Rademacher random variables $\epsilon=(\epsilon_{t+1},\ldots,\epsilon_{T})$, and then define

The expected regret for the method is bounded by the classical Rademacher complexity

where each random variable $z_{t}$ has distribution $D_{t}$. For any smooth norm, the expected regret can be further upper bounded by $O\left(\sqrt{\sum_{t=1}^{T}\sigma_{t}^{2}}\right)$.

where the first sum is the cumulative cost vector, the second sum may be viewed as a random perturbation of the cumulative cost, and the final term is simply the predictable process at time $t$. We may rewrite (16) as

This is a general form of the randomized method for online linear optimization. As shown in , this form in fact reduces to the more familiar form of the FPL update in certain cases.

For the distributions $D_{1},\ldots,D_{T}$ satisfying Assumption 1, consider the randomized strategy that at time $t$, draws $z_{t+1},\ldots,z_{T}$ from $D_{t+1},\ldots,D_{T}$ respectively and Rademacher random variables $\epsilon=(\epsilon_{t+1},\ldots,\epsilon_{T})$, and then outputs

2 Randomized Algorithm for the Simplex

For the distributions $D_{1},\ldots,D_{T}$ satisfying Assumption 1, consider the randomized strategy that at time $t$, draws $z_{t+1},\ldots,z_{T}$ from $D_{t+1},\ldots,D_{T}$ respectively and Rademacher random variables $\epsilon=(\epsilon_{t+1},\ldots,\epsilon_{T})$, and then outputs

When the predictable sequence $M_{t}$ is zero, the algorithm reduces to $f_{t}=e_{j^{*}_{t}}$ with

which can be recognized as a Follow the Perturbed Leader type update with $\sum_{i=1}^{t-1}x_{i}$ being the cumulative loss and $\sum_{i=t+1}^{T}\epsilon_{i}z_{i}$ being a random perturbation.

Other Examples

We now provide a couple of examples and sketch directions for further research.

As an example, consider the setting where the information given to the player at round $t$ consists of two parts: the bandit feedback $\left\langle f_{t},x_{t}\right\rangle$ about the cost of the chosen action, as well as full information about the past move $x_{t-k}$. For $t>k$, let $M_{t}=M_{t}(I_{1},\ldots,I_{t-1})=\frac{1}{t-k-1}\sum_{s=1}^{t-k-1}x_{s}$. Then

where $M^{\prime}_{t}=\frac{1}{t-1}\sum_{s=1}^{t-1}x_{s}$ is the full information statistic. It is immediate from Lemma 4 that the expected regret of the algorithm is

This simple argument shows that variance-type bounds are immediate in bandit problems with delayed full information feedback.

2 I.I.D. Data

Taking the expectation over i.i.d. data, the first term in the above bound is variance $\sigma^{2}$ of the distribution under the given norm, while the third term disappears under the expectation. For the second term, we perform exactly the same quadratic expansion and obtain

The same argument works for the case of bandit information, given that $M_{t}$ can be constructed to estimate $M^{\prime}_{t}$ well (e.g. using the arguments of ).

Auxiliary Results: Improved Bounds for Small Losses

While the regret bound for the original SCRiBLe algorithm follows immediately from the more general Lemma 4, we now state an alternative bound for SCRiBLe in terms of the loss of the optimal decision. The bound holds under the assumption of positivity on the losses. Lemma 12 is of independent interest and will be used as a building block for the analogous result for the multi-armed bandit in Lemma 13. Such bounds in terms of the loss of the best arm are attractive, as they give tighter results whenever the loss of the optimal decision is small. Thanks to this property, Lemma 13 is used in Section 4 in order to obtain bounds in terms of predictable process performance.

Consider the case when $\mathcal{R}$ is a self-concordant barrier over $\mathcal{F}$ and sets $\mathcal{F}$ and $\mathcal{X}$ are such that each $\left<f,x\right>\in[0,s]$. Then for the SCRiBLe algorithm, for any choice of step size $\eta<1/(2sn^{2})$, we have the bound

We now state and prove a bound in terms of the loss of the best arm for the case of non-stochastic multiarmed bandits. Such a bound is interesting in its own right and, to the best of our knowledge, it does not appear in the literature.The bound of is in terms of maximal gains, which is very different from a bound in terms of minimal loss. To the best of our knowledge, the trick of redefining losses as negative gains does not work here. Our approach is to use SCRiBLe with a self-concordant barrier for the probability simplex, coupled with the bound of Lemma 12. (We were not able to make this result work with the entropy function, even with the local norm bounds).

Suppose that Nature plays a sequence $x_{1},\ldots,x_{T}\in[0,s]^{d}$. On each round, we chose an arm $j_{t}$ and observe $\left\langle e_{j_{t}},x_{t}\right\rangle$.

Suppose $x_{1},\ldots,x_{T}\in[0,s]^{d}$. For any $\eta<1/(4sd^{2})$ the expected regret of the SCRiBLe for multi-armed Bandit algorithm is bounded as :

Standard Doubling Trick

Suppose we have a randomized algorithm that takes a fixed $\eta$ as input and for some constant $A$ without a priori knowledge of $\tau$, for any $\tau>0$, guarantees expected regret of the form

where $\Psi$ satisfies the above stated requirements. Then using this algorithm as a black-box for any $T>0$, we can provide a randomized algorithm with a regret bound

The prediction problem is broken into phases, with a constant learning rate $\eta_{i}=\eta_{0}2^{-i}$ throughout the $i$-th phase, for some $\eta_{0}>0$. Define for $i\geq 1$

to be the start of the phase $i+1$, and $s_{1}=1$. Let $N$ be the last phase of the game and let $s_{N+1}=T+1$. Without loss of generality, assume $N>1$ (for, otherwise regret is at most $4A/\eta_{0}$). Then

where the last inequality follows because $\eta_{k}\Psi(I_{s_{k}:s_{k+1}-1},f_{s_{k}:s_{k+1}-1})\leq A\eta_{k}^{-1}$ within each phase. Also observe that

by the monotonicity assumption. Hence, regret is upper bounded by

Now, observe that the rule for stopping the phase can only be calculated after the first time step of the new phase. The easiest way to deal with this is to throw out $N$ time periods and suffer an additional regret of $sN$ (losses are bounded by $s$). Using $\eta_{0}=4A/s$ this leads to additional factor of $sN\leq s2^{N}=4A\eta_{0}^{-1}2^{N}\leq 8\sqrt{A\ \Psi(I_{1:T},f_{1:T})}$, which is a gross over-bound. In conclusion, the overall bound on regret is

We remark that while the algorithm may or may not start each new phase from a cold start (that is, forget about what has been learned), the functions $M_{t}$ may still contain information about all the past moves of Nature.

With this doubling trick, for any of the full information bounds presented in the paper (for instance Lemmas 1, 2, 3 and 5) we can directly get an algorithm that enjoys a regret bound that is a factor at most $8$ from the bound with optimal choice of $\eta$.

For Lemmas 4, 6, 7 and 8, we need to apply the doubling trick to an intermediate quantity, as the final bound is given in terms of quantities not computable by the algorithm. Specifically, the doubling trick needs to be applied to Equations (5), (7), (8) and (9), respectively, in order to get bounds that are within a factor $8$ from the bounds obtained by optimizing $\eta$ in the corresponding equations. We can then upper these computable quantities by corresponding unobserved quantities as is done in these lemmas. To see this more clearly let us demonstrate this on the example of Lemma 8. By Equation (9), we have that

Now note that $(\left\langle f_{t},x_{t}-M^{\pi_{t}}_{t}\right\rangle)^{2}$ is a quantity computable by the algorithm at each round. Also note that $2\eta n^{2}\sum_{t=1}^{T}(\left\langle f_{t},x_{t}-M^{\pi_{t}}_{t}\right\rangle)^{2}$ satisfies the condition on $\Psi$ required by Lemma 14, as the sum of squares is monotonic. Hence using the lemma we can conclude that

The following steps in Lemma 8 (see proof in the Appendix) imply that

Plugging the above in Equation 24 we can conclude that

This is exactly the inequality one would get if the final bound in Lemma 8 is optimized for $\eta$, with an additional factor of $8$. With similar argument we can get the tight bounds for Lemmas 4, 6 and 7 too, even though they are in the bandit setting.

Appendix A Appendix

Define $g_{t+1}=\arg\min_{f\in\mathcal{F}}~{}\eta\left\langle f,\sum_{s=1}^{t}x_{s}\right\rangle+\mathcal{R}(f)$ to be the (unmodified) Follow the Regularized Leader. Observe that for any $f^{*}\in\mathcal{F}$,

The base case $\tau=1$ is immediate since $M_{1}=0$. For the purposes of induction, suppose that the above inequality holds for $\tau=T-1$. Using $f^{*}=f_{T}$ and adding $\left\langle f_{T}-g_{T+1},M_{T}\right\rangle+\left\langle g_{T+1},x_{T}\right\rangle$ to both sides,

by the optimality of $f_{T}$ and $g_{T+1}$. This concludes the inductive argument, and from Eq. (25) we obtain

Define the Newton decrement for $\Phi_{t}(f)\triangleq\eta\left\langle f,\sum_{s=1}^{t}x_{s}+M_{t+1}\right\rangle+\mathcal{R}(f)$ as

On the other hand, any update of the form $a^{*}=\arg\min_{a\in A}\left\langle a,x\right\rangle+D_{\mathcal{R}}(a,c)$ satisfies for any $d\in A$ (see e.g. )

Using Equations (29), (32) and (31) in Equation (28) we conclude that

By strong convexity of $\mathcal{R}$, $D_{\mathcal{R}}(g_{t+1},f_{t})\geq\frac{1}{2}\left\|g_{t+1}-f_{t}\right\|^{2}$ and thus

Summing over $t=1,\ldots,T$ yields, for any $f^{*}\in\mathcal{F}$,

where $R_{\max}^{2}=\max_{f\in\mathcal{F}}\mathcal{R}(f)-\min_{f\in\mathcal{F}}\mathcal{R}(f)$. ∎

The proof closely follows the proof of Lemma 2 and together with the technique of . For the purposes of analysis, let $g_{t+1}$ be a projected point at every step (that is, normalized). Then we have the closed form solution for $f_{t}$ and $g_{t+1}$:

Now, since $\nabla^{2}\mathcal{R}$ is diagonal,

using the fact that both $f_{t}$ and $g_{t+1}$ are probability distributions. In view of (A),

The rest similar to the proof of Lemma 2. We have

Summing over $t=1,\ldots,T$ yields, for any $f^{*}\in\mathcal{F}$,

In view of Lemma 1, for any $f^{*}\in\mathcal{F}$

The second statement follows immediately. ∎

First note that by Lemma 2 we have that for the $M_{t}$ chosen in the algorithm,

where the last step is due to Corollary 2.3 of . Indeed, the updates for $q_{t}$’s are exactly the experts algorithm with pointwise loss at each round $t$ for expert $\pi\in\Pi$ given by $\left\|M^{\pi}_{t}-x_{t}\right\|_{*}^{2}$. Also as each $M^{\pi}_{t}\in\mathcal{X}$ the unit ball of dual norm, we can conclude that $\left\|M^{\pi}_{t}-x_{t}\right\|_{*}^{2}\leq 4$ which is why we have a scaling by factor $4$. Simplifying leads to the bound in the lemma. ∎

In view of Lemma 1, for any $f^{*}\in\mathcal{F}$

This proves the first inequality of the Lemma. Now by Jensen’s inequality, the above bound can be simplified as:

where the last step is due to Corollary 2.3 of . Indeed, the updates for $q_{t}$’s are exactly the experts algorithm with point-wise loss at each round $t$ for expert $\pi\in\Pi$ given by $(\left\langle f_{t},x_{t}-M^{\pi}_{t}\right\rangle)^{2}$. Also as each $M^{\pi}_{t}\in\mathcal{X}$ the unit ball of dual norm, hence we can conclude that $(\left\langle f_{t},x_{t}-M^{\pi}_{t}\right\rangle)^{2}\leq 4$ which is why we have a scaling by factor $4$. Further since $\|f_{t}\|\leq 1$ we can conclude that :

First note that by Lemma 2, since $M_{t}^{\pi_{t}}$ is the predictable process we use, we have deterministically that,

Hence we can conclude that expected regret is bounded as :

This proves the first inequality in the lemma. However note that the update for $q_{t}$’s is using SCRiBLe for multiarmed bandit algorithm where the pointwise loss for any $\pi\in\Pi$ at round $t$ given by $\left\|x_{t}-M_{t}^{\pi}\right\|_{*}^{2}$. Also note that maximal value of loss is bounded by $\max_{M_{t},x_{t}}\left\|x_{t}-M_{t}^{\pi}\right\|_{*}\leq 4$. Hence, using Lemma 13 with $s=4$ and step size $1/32|\Pi|^{2}$, we conclude that

In view of Lemma 1, for any $f^{*}\in\mathcal{F}$

We can bound expected regret of the algorithm as:

This gives the first inequality of the Lemma. However note that the update for $q_{t}$’s the distribution over set $\Pi$ is obtained by running the SCRiBLe for multi-armed bandit algorithm where pointwise loss for any $\pi\in\Pi$ at round $t$ given by $(\left<f_{t},x_{t}-M_{t}^{\pi}\right>)^{2}$. Also note that maximal value of loss is bounded by $4$. Hence using Lemma 13 with $s=4$ and step size $1/32|\Pi|^{2}$ we conclude by the regret bound in that lemma that

Plugging this back in Equation (40) we conclude that

To show admissibility using the particular randomized strategy $q_{t}$ given in the lemma, we need to show that

The distribution $q_{t}$ is defined by first drawing $z_{t+1}\sim D_{t+1},\ldots,z_{T}\sim D_{T}$ and $\epsilon_{t+1},\ldots\epsilon_{T}$ Rademacher random variables, and then calculating $f_{t}=f_{t}(z_{t+1:T},\epsilon_{t+1:T})$ as in (16). Hence,

for any given $z_{t+1:T},\epsilon_{t+1:T}$, we have

We can conclude that for this choice of $q_{t}$,

In the next to last step we appealed to the minimax theorem which by linearity of the expression in $g$ and the fact that $\mathcal{F}$ is a compact convex set; furthermore, the term in the expectation is linear in $p$. By triangle inequality,

where we introduced a Rademacher random variable $\epsilon_{t}$ via the standard symmetrization argument. We now introduce “centering” by $M_{t}(x_{1:t-1})$. The above expression is equal to

where in the last step we pass to the set of distributions on $C=\{z:\|z\|\leq\sigma_{t}\}$. By Assumption 1, the last expression is upper bounded by

where ${\mathcal{E}}_{t}$ is the event that the largest two coordinates of $R_{t}$ are separated by at least $4\sigma_{t}$.

Leaving out the $\left<f,M_{t}\right>$ term, we can further rewrite the above supremum as

By optimizing over coordinates $i\neq j$, this is equal to

Under the event $\mathcal{E}_{t}$, the maximum over $j$ will be achieved at $j^{*}_{t}$, thus yielding

while outside of $\mathcal{E}_{t}$ the above solution can be off by at most $4$. We may also write the above expression as

So, under the event $\mathcal{E}_{t}$, the minimum is attained at

On the other hand on the event $\mathcal{E}_{t}^{c}$,

From Lemma 9 we have that the randomized strategy which at time $t$, draws $z_{t+1},\ldots,z_{T}$ from $D_{t+1},\ldots,D_{T}$ respectively and Rademacher random variables $\epsilon=(\epsilon_{t+1},\ldots,\epsilon_{T})$, and then picks

However by Lemma 15, we have that for the randomized algorithm that at time $t$, draws $z_{t+1},\ldots,z_{T}$ from $D_{t+1},\ldots,D_{T}$ respectively and Rademacher random variables $\epsilon=(\epsilon_{t+1},\ldots,\epsilon_{T})$, and then picks

Hence as mentioned in Equation (11) we can conclude that the expected regret of the randomized strategy that plays $f_{t}(R_{t})$ on round $t$ is bounded as

Hence we have shown that the update in Equation (20) is admissible w.r.t. relaxation in Equation (42) and so enjoys the expected regret bound :

For the case when $\mathcal{F}$ is the simplex, since for each $f\in\mathcal{F}$ and each $i\in[d]$, $f[i]\geq 0$, if we add an arbitrary number $B$ to each coordinate of $x_{t}\in^{d}$, the regret remains unchanged, that is,

In view of Lemma 1, for any $f^{*}\in\mathcal{F}$

We are interested in solving the multi-armed bandit problem using the self-concordant barrier method so we can get a regret bound in terms of the loss of the optimal arm. We do this in two steps, first we provide an algorithm for linear bandit problem over the simplex. That is we provide an algorithm for the case when learner plays on each round $q_{t}\in\Delta([d])$, adversary plays loss vector $x_{t}\in[0,s]^{d}$ and learner observes $\left<q_{t},x_{t}\right>$ at the end of the round. Next we show that this bandit algorithm over the simplex can be converted into a multi-armed bandit algorithm. To this end let us first develop a linear bandit algorithm over the simplex based on self-concordant barrier algorithm (SCRiBLe).

Note that one can rewrite the loss of any $q\in\Delta([d])$ over any $x\in[0,s]^{d}$ as

Since the above we have for any distribution over the $d$ arms $q$, and any loss vector $x$, we see that solving the linear bandit problem where learner picks from simplex and adversary picks from $[0,s]^{d}$ is equivalent to the linear bandit game where learner picks vectors from set $\mathcal{F}^{\prime}$ and adversary picks vectors from set $\mathcal{X}^{\prime}$ where

Thus we have a linear bandit algorithm over the simplex with the bound given in Equation (43). Now we claim that this algorithm can be used for solving multi-armed bandit problem.

We claim that the algorithm we have developed for the simplex case can be used for the multi-armed bandit problem. To see this note first that for any choice of $q_{1},\ldots,q_{T}\in\Delta([d])$ and any choice of $x_{1},\ldots,x_{T}$,

Acknowledgements

We gratefully acknowledge the support of NSF under grants CAREER DMS-0954737 and CCF-1116928, as well as Dean’s Research Fund.

References