Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

Introduction

In the contextual bandit problem, an agent collects rewards for actions taken over a sequence of rounds; in each round, the agent chooses an action to take on the basis of (i) context (or features) for the current round, as well as (ii) feedback, in the form of rewards, obtained in previous rounds. The feedback is incomplete: in any given round, the agent observes the reward only for the chosen action; the agent does not observe the reward for other actions. Contextual bandit problems are found in many important applications such as online recommendation and clinical trials, and represent a natural half-way point between supervised learning and reinforcement learning. The use of features to encode context is inherited from supervised machine learning, while exploration is necessary for good performance as in reinforcement learning.

The choice of exploration distribution on actions is important. The strongest known results (Auer et al., 2002; McMahan and Streeter, 2009; Beygelzimer et al., 2011) provide algorithms that carefully control the exploration distribution to achieve an optimal regret after $T$ rounds of

with probability at least $1-\delta$, relative to a set of policies $\Pi\subseteq A^{X}$ mapping contexts $x\in X$ to actions $a\in A$ (where $K$ is the number of actions). The regret is the difference between the cumulative reward of the best policy in $\Pi$ and the cumulative reward collected by the algorithm. Because the bound has a mild logarithmic dependence on $|\Pi|$, the algorithm can compete with very large policy classes that are likely to yield high rewards, in which case the algorithm also earns high rewards. However, the computational complexity of the above algorithms is linear in $|\Pi|$, making them tractable for only simple policy classes.

A sub-linear in $|\Pi|$ running time is possible for policy classes that can be efficiently searched. In this work, we use the abstraction of an optimization oracle to capture this property: given a set of context/reward vector pairs, the oracle returns a policy in $\Pi$ with maximum total reward. Using such an oracle in an i.i.d. setting (formally defined in Section 2.1), it is possible to create $\epsilon$-greedy (Sutton and Barto, 1998) or epoch-greedy (Langford and Zhang, 2007) algorithms that run in time $O(\log|\Pi|)$ with only a single call to the oracle per round. However, these algorithms have suboptimal regret bounds of $O((K\log|\Pi|)^{1/3}T^{2/3})$ because the algorithms randomize uniformly over actions when they choose to explore.

The EXP4-family of algorithms (Auer et al., 2002; McMahan and Streeter, 2009; Beygelzimer et al., 2011) solve the contextual bandit problem with optimal regret by updating weights (multiplicatively) over all policies in every round. Except for a few special cases (Helmbold and Schapire, 1997; Beygelzimer et al., 2011), the running time of such measure-based algorithms is generally linear in the number of policies.

In contrast, the $\mathsf{Randomized\,UCB}$ algorithm of Dudík et al. (2011a) is based on a natural abstraction from supervised learning—the ability to efficiently find a function in a rich function class that minimizes the loss on a training set. This abstraction is encapsulated in the notion of an optimization oracle, which is also useful for $\epsilon$-greedy (Sutton and Barto, 1998) and epoch-greedy (Langford and Zhang, 2007) algorithms. However, these latter algorithms have only suboptimal regret bounds.

Another class of approaches based on Bayesian updating is Thompson sampling (Thompson, 1933; Li, 2013), which often enjoys strong theoretical guarantees in expectation over the prior and good empirical performance (Chapelle and Li, 2011). Such algorithms, as well as the closely related upper-confidence bound algorithms (Auer, 2002; Chu et al., 2011), are computationally tractable in cases where the posterior distribution over policies can be efficiently maintained or approximated. In our experiments, we compare to a strong baseline algorithm that uses this approach (Chu et al., 2011).

To circumvent the $\Omega(|\Pi|)$ running time barrier, we restrict attention to algorithms that only access the policy class via the optimization oracle. Specifically, we use a cost-sensitive classification oracle, and a key challenge is to design good supervised learning problems for querying this oracle. The $\mathsf{Randomized\,UCB}$ algorithm of Dudík et al. (2011a) uses a similar oracle to construct a distribution over policies that solves a certain convex program. However, the number of oracle calls in their work is prohibitively large, and the statistical analysis is also rather complex.The paper of Dudík et al. (2011a) is colloquially referred to, by its authors, as the “monster paper” (Langford, 2014).

Main contributions.

Preliminaries

In this section, we recall the i.i.d. contextual bandit setting and some basic techniques used in previous works (Auer et al., 2002; Beygelzimer et al., 2011; Dudík et al., 2011a).

Let $\mathcal{D}$ be a probability distribution over $X\times^{A}$, the joint space of contexts and reward vectors; we assume actions’ rewards from $\mathcal{D}$ are always in the interval $$. Let$\mathcal{D}_{X}$denote the marginal distribution of$\mathcal{D}$over$X$.

2 Inverse Propensity Scoring

An unbiased estimate of a policy’s reward may be obtained from a history of interaction records $H_{t}$ using inverse propensity scoring ($\mathsf{IPS}$; also called inverse probability weighting): the expected reward of policy $\pi\in\Pi$ is estimated as

Let $\pi_{t}:=\operatorname*{arg\,max}_{\pi\in\Pi}\widehat{}\mathcal{R}_{t}(\pi)$ denote a policy that maximizes the expected reward estimate based on inverse propensity scoring with history $H_{t}$ ($\pi_{0}$ can be arbitrary), and let $\widehat{}\operatorname{Reg}_{t}(\pi):=\widehat{}\mathcal{R}_{t}(\pi_{t})-\widehat{}\mathcal{R}_{t}(\pi)$ denote estimated regret relative to $\pi_{t}$. Note that $\widehat{}\operatorname{Reg}_{t}(\pi)$ is generally not an unbiased estimate of $\operatorname{Reg}(\pi)$, because $\pi_{t}$ is not always $\pi_{\star}$.

3 Optimization Oracle

One natural mode for accessing the set of policies $\Pi$ is enumeration, but this is impractical in general. In this work, we instead only access $\Pi$ via an optimization oracle which corresponds to a cost-sensitive learner. Following Dudík et al. (2011a), we call this oracle $\mathsf{AMO}$Cost-sensitive learners often need a cost instead of reward, in which case we use $c_{t}=\mathds{1}-r_{t}$..

4 Projections and Smoothing

In each round, our algorithm chooses an action by randomly drawing a policy $\pi$ from a distribution over $\Pi$, and then picking the action $\pi(x)$ recommended by $\pi$ on the current context $x$. This is equivalent to drawing an action according to $Q(a|x):=\sum_{\pi\in\Pi:\pi(x)=a}Q(\pi),\,\forall a\in A$. For keeping the variance of reward estimates from $\mathsf{IPS}$ in check, it is desirable to prevent the probability of any action from being too small. Thus, as in previous work, we also use a smoothed projection $Q^{\mu}(\cdot|x)$ for $\mu\in[0,1/K]$, $Q^{\mu}(a|x):=(1-K\mu)\sum_{\pi\in\Pi:\pi(x)=a}Q(\pi)+\mu,\,\forall a\in A$. Every action has probability at least $\mu$ under $Q^{\mu}(\cdot|x)$.

Algorithm and Main Results

Our algorithm ($\mathsf{ILOVETOCONBANDITS}$) is an epoch-based variant of the $\mathsf{Randomized\,UCB}$ algorithm of Dudík et al. (2011a) and is given in Algorithm 1. Like $\mathsf{Randomized\,UCB}$, $\mathsf{ILOVETOCONBANDITS}$ solves an optimization problem (OP) to obtain a distribution over policies to sample from (Step 7), but does so on an epoch schedule, i.e., only on certain pre-specified rounds $\tau_{1},\tau_{2},\ldots$. The only requirement of the epoch schedule is that the length of epoch $m$ is bounded as $\tau_{m+1}-\tau_{m}=O(\tau_{m})$. For simplicity, we assume $\tau_{m+1}\leq 2\tau_{m}$ for $m\geq 1$, and $\tau_{1}=O(1)$.

The crucial step here is solving (OP). Before stating the main result, let us get some intuition about this problem. The first constraint, Eq. (2), requires the average estimated regret of the distribution $Q$ over policies to be small, since $b_{\pi}$ is a rescaled version of the estimated regret of policy $\pi$. This constraint skews our distribution to put more mass on “good policies” (as judged by our current information), and can be seen as the exploitation component of our algorithm. The second set of constraints, Eq. (3), requires the distribution $Q$ to place sufficient mass on the actions chosen by each policy $\pi$, in expectation over contexts. This can be thought of as the exploration constraint, since it requires the distribution to be sufficiently diverse for most contexts. As we will see later, the left hand side of the constraint is a bound on the variance of our reward estimates for policy $\pi$, and the constraint requires the variance to be controlled at the level of the estimated regret of $\pi$. That is, we require the reward estimates to be more accurate for good policies than we do for bad ones, allowing for much more adaptive exploration than the uniform exploration of $\epsilon$-greedy style algorithms.

This problem is very similar to the one in Dudík et al. (2011a), and our coordinate descent algorithm in Section 3.1 gives a constructive proof that the problem is feasible. As in Dudík et al. (2011a), we have the following regret bound:

Assume the optimization problem (OP) can be solved whenever required in Algorithm 1. With probability at least $1-\delta$, the regret of Algorithm 1 ($\mathsf{ILOVETOCONBANDITS}$) after $T$ rounds is

We now present a coordinate descent algorithm to solve (OP). The pseudocode is given in Algorithm 2. Our analysis, as well as the algorithm itself, are based on a potential function which we use to measure progress. The algorithm can be viewed as a form of coordinate descent applied to this same potential function. The main idea of our analysis is to show that this function decreases substantially on every iteration of this algorithm; since the function is nonnegative, this gives an upper bound on the total number of iterations as expressed in the following theorem.

Algorithm 2 (with $Q_{\operatorname{init}}:={\bf 0}$) halts in at most $\frac{4\ln(1/(K\mu_{m}))}{\mu_{m}}$ iterations, and outputs a solution $Q$ to (OP).

2 Using an Optimization Oracle

We now show how to implement Algorithm 2 via $\mathsf{AMO}$ (c.f. Section 2.3).

Algorithm 2 can be implemented using one call to $\mathsf{AMO}$ before the loop is started, and one call for each iteration of the loop thereafter.

At the very beginning, before the loop is started, we compute the best empirical policy so far, $\pi_{t}$, by calling $\mathsf{AMO}$ on the sequence of historical contexts and estimated reward vectors; i.e., on $(x_{\tau},\hat{r}_{\tau})$, for $\tau=1,2,\ldots,t$.

Next, we show that each iteration in the loop of Algorithm 2 can be implemented via one call to $\mathsf{AMO}$. Going over the pseudocode, first note that operations involving $Q$ in Step 4 can be performed efficiently since $Q$ has sparse support. Note that the definitions in Step 3 don’t actually need to be computed for all policies $\pi\in\Pi$, as long as we can identify a policy $\pi$ for which $D_{\pi}(Q)>0$. We can identify such a policy using one call to $\mathsf{AMO}$ as follows.

First, note that for any policy $\pi$, we have

Since $2K+\frac{\widehat{}\mathcal{R}_{t}(\pi_{t})}{\psi\mu}$ is a constant independent of $\pi$, we have

3 Epoch Schedule

4 Warm Start

We now present a different technique to reduce the number of calls to $\mathsf{AMO}$. This is based on the observation that practically speaking, it seems terribly wasteful, at the start of a new epoch, to throw out the results of all of the preceding computations and to begin yet again from nothing. Instead, intuitively, we expect computations to be more moderate if we begin again where we left off last, i.e., a “warm-start” approach. Here, when Algorithm 2 is called at the end of epoch $m$, we use $Q_{\operatorname{init}}:=Q_{m-1}$ (the previously computed weights) rather than ${\bf 0}$.

5 Computational Complexity

6 A Lower Bound on the Support Size

An attractive feature of the coordinate descent algorithm, Algorithm 2, is that the number of oracle calls is directly related to the number of policies in the support of $Q_{m}$. Specifically, for the doubling schedule of Section 3.3, Theorem 3 implies that we never have non-zero weights for more than $\frac{4\ln(1/(K\mu_{m}))}{\mu_{m}}$ policies in epoch $m$. Similarly, the total number of oracle calls for the warm-start approach in Section 3.4 bounds the total number of policies which ever have non-zero weight over all $T$ rounds. The support size of the distributions $Q_{m}$ in Algorithm 1 is crucial to the computational complexity of sampling an action (Step 4 of Algorithm 1).

In this section, we demonstrate a lower bound showing that it is not possible to construct substantially sparser distributions that also satisfy the low-variance constraint (3) in the optimization problem (OP). To formally define the lower bound, fix an epoch schedule $0=\tau_{0}<\tau_{1}<\tau_{2}<\dotsb$ and consider the following set of non-negative vectors over policies:

The proof of the theorem is deferred to Appendix E. In the context of our problem, this lower bound shows that the bounds in Lemma 2 and Lemma 3 are unimprovable, since the number of calls to $\mathsf{AMO}$ is at least the size of the support, given our mode of access to $\Pi$.

Regret Analysis

In this section, we outline the regret analysis for our algorithm $\mathsf{ILOVETOCONBANDITS}$, with details deferred to Appendix B and Appendix C.

The rest of the analysis, which deviates from that of $\mathsf{Randomized\,UCB}$, compares the expected regret $\operatorname{Reg}(\pi)$ of any policy $\pi$ with the estimated regret $\widehat{}\operatorname{Reg}_{t}(\pi)$ using the variance constraints Eq. (3):

This lemma can easily be combined with the constraint Eq. (2) from (OP): since the weights $Q_{m-1}$ used in any round $t$ in epoch $m$ satisfy $\sum_{\pi\in\Pi}Q_{m-1}(\pi)\widehat{}\operatorname{Reg}_{\tau_{m}-1}(\pi)\leq\psi\cdot 2K\mu_{\tau_{m}-1}$, we obtain a bound on the (conditionally) expected regret in round $t$ using the above lemma: with high probability,

Summing these terms up over all $T$ rounds and applying martingale concentration gives the final regret bound in Theorem 2.

Analysis of the Optimization Algorithm

In this section, we give a sketch of the analysis of our main optimization algorithm for computing weights $Q_{m}$ on each epoch as in Algorithm 2. As mentioned in Section 3.1, this analysis is based on a potential function.

Since our attention for now is on a single epoch $m$, here and in what follows, when clear from context, we drop $m$ from our notation and write simply $\tau=\tau_{m}$, $\mu=\mu_{m}$, etc. Let ${{\cal U}_{A}}$ be the uniform distribution over the action set $A$. We define the following potential function for use on epoch $m$:

The function in Eq. (6) is defined for all vectors $Q\in\Delta^{\Pi}$. Also, $\operatorname{RE}\left({p}\|{q}\right)$ denotes the unnormalized relative entropy between two nonnegative vectors $p$ and $q$ over the action space (or any set) $A$:

This number is always nonnegative. Here, $Q^{\mu}(\cdot|x)$ denotes the “distribution” (which might not sum to $1$) over $A$ induced by $Q^{\mu}$ for context $x$ as given in Section 2.4. Thus, ignoring constants, this potential function is a combination of two terms: The first measures how far from uniform are the distributions induced by $Q^{\mu}$, and the second is an estimate of expected regret under $Q$ since ${b_{\pi}}$ is proportional to the empirical regret of $\pi$. Making ${\Phi_{m}}$ small thus encourages $Q$ to choose actions as uniformly as possible while also incurring low regret — exactly the aims of our algorithm. The constants that appear in this definition are for later mathematical convenience.

For further intuition, note that, by straightforward calculus, the partial derivative ${\partial{\Phi_{m}}}/{\partial Q(\pi)}$ is roughly proportional to the variance constraint for $\pi$ given in Eq. (3) (up to a slight mismatch of constants). This shows that if this constraint is not satisfied, then $\partial{\Phi_{m}}/\partial Q(\pi)$ is likely to be negative, meaning that ${\Phi_{m}}$ can be decreased by increasing $Q(\pi)$. Thus, the weight vector $Q$ that minimizes ${\Phi_{m}}$ satisfies the variance constraint for every policy $\pi$. It turns out that this minimizing $Q$ also satisfies the low regret constraint in Eq. (2), and also must sum to at most $1$; in other words, it provides a complete solution to our optimization problem. Algorithm 2 does not fully minimize ${\Phi_{m}}$, but it is based roughly on coordinate descent. This is because in each iteration one of the weights (coordinate directions) $Q(\pi)$ is increased. This weight is one whose corresponding partial derivative is large and negative.

To analyze the algorithm, we first argue that it is correct in the sense of satisfying the required constraints, provided that it halts.

If Algorithm 2 halts and outputs a weight vector $Q$, then the constraints Eq. (3) and Eq. (2) must hold, and furthermore the sum of the weights $Q(\pi)$ is at most $1$.

The proof is rather straightforward: Following Step 4, Eq. (2) must hold, and also the weights must sum to $1$. And if the algorithm halts, then ${D_{\pi}({Q})}\leq 0$ for all $\pi$, which is equivalent to Eq. (3).

What remains is the more challenging task of bounding the number of iterations until the algorithm does halt. We do this by showing that significant progress is made in reducing ${\Phi_{m}}$ on every iteration. To begin, we show that scaling $Q$ as in Step 4 cannot cause ${\Phi_{m}}$ to increase.

Let $Q$ be a weight vector such that $\sum_{\pi}Q(\pi)(2K+{b_{\pi}})>2K$, and let $c$ be as in Eq. (4). Then ${\Phi_{m}}(cQ)\leq{\Phi_{m}}(Q)$.

We consider ${\Phi_{m}}(cQ)$ as a function of $c$, and argue that its derivative (with respect to $c$) at the value of $c$ given in the lemma statement is always nonnegative. Therefore, by convexity, it is nondecreasing for all values exceeding $c$. Since $c<1$, this proves the lemma. ∎

Next, we show that substantial progress will be made in reducing ${\Phi_{m}}$ each time that Step 8 is executed.

Let $Q$ denote a set of weights and suppose, for some policy $\pi$, that ${D_{\pi}({Q})}>0$. Let $Q^{\prime}$ be a new set of weights which is an exact copy of $Q$ except that $Q^{\prime}(\pi)=Q(\pi)+\alpha$ where $\alpha={\alpha_{\pi}({Q})}>0$. Then

Proof sketch.

We first compute exactly the change in potential for general $\alpha$. Next, we apply a second-order Taylor approximation, which is maximized by the $\alpha$ used in the algorithm. The Taylor approximation, for this $\alpha$, yields a lower bound which can be further simplified using the fact that $Q^{\mu}(a|x)\geq\mu$ always, and our assumption that ${D_{\pi}({Q})}>0$. This gives the bound stated in the lemma. ∎

So Step 4 does not cause ${\Phi_{m}}$ to increase, and Step 8 causes ${\Phi_{m}}$ to decrease by at least the amount given in Lemma 7. This immediately implies Theorem 3: for $Q_{\operatorname{init}}={\bf 0}$, the initial potential is bounded by ${\tau\mu\ln(1/(K\mu))}/{(1-K\mu)}$, and it is never negative, so the number of times Step 8 is executed is bounded by $4\ln(1/(K\mu))/\mu$ as required.

1 Epoching and Warm Start

We now turn to warm-start approach of Section 3.4, where in each epoch $m+1$ we initialize the coordinate descent algorithm with $Q_{\operatorname{init}}=Q_{m}$, i.e. the weights computed in the previous epoch $m$. To analyze this, we bound how much the potential changes from ${\Phi_{m}}(Q_{m})$ at the end of epoch $m$ to ${\Phi_{m+1}}(Q_{m})$ at the very start of epoch $m+1$. This, combined with our earlier results regarding how quickly Algorithm 2 drives down the potential, we are able to get an overall bound on the total number of updates across $T$ rounds.

Let $M$ be the largest integer for which $\tau_{M+1}\leq T$. With probability at least $1-2\delta$, for all $T$, the total epoch-to-epoch increase in potential is

where $M$ is the largest integer for which $\tau_{M+1}\leq T$.

The potential function, as written in Eq. (6), naturally breaks into two pieces whose epoch-to-epoch changes can be bounded separately. Changes affecting the relative entropy term on the left can be bounded, regardless of $Q_{m}$, by taking advantage of the manner in which these distributions are smoothed. For the other term on the right, it turns out that these epoch-to-epoch changes are related to statistical quantities which can be bounded with high probability. Specifically, the total change in this term is related first to how the estimated reward of the empirically best policy compares to the expected reward of the optimal policy; and second, to how the reward received by our algorithm compares to that of the optimal reward. From our regret analysis, we are able to show that both of these quantities will be small with high probability. ∎

Experimental Evaluation

A natural solution is to use an online oracle that is stateful and accepts examples one by one. An online cost-sensitive classification (CSC) oracle takes as input a weighted example and returns a predicted class (corresponding to one of $K$ actions in our setting). Since the oracle is stateful, it remembers and uses examples from all previous calls in answering questions, thereby reducing the complexity of each oracle invocation to $O(1)$ as in supervised learning. Using several such oracles, we can efficiently track a distribution over good policies and sample from it. We detail this approach (which we call Online Cover) in the full version of the paper. The algorithm maintains a uniform distribution over a fixed number $n$ of policies where $n$ is a parameter of the algorithm. Upon receiving a fresh example, it updates all $n$ policies with the suitable CSC examples (Eq. (5)). The specific CSC oracle we use is a reduction to squared-loss regression (Algorithms 4 and 5 of Beygelzimer and Langford (2009)) which is amenable to online updates. Our implementation is included in Vowpal Wabbit.http://hunch.net/~vw. The implementation is in the file cbify.cc and is enabled using --cover.

Due to lack of public datasets for contextual bandit problems, we use a simple supervised-to-contextual-bandit transformation (Dudík et al., 2011b) on the CCAT document classification problem in RCV1 (Lewis et al., 2004). This dataset has $781265$ examples and $47152$ TF-IDF features. We treated the class labels as actions, and one minus 0/1-loss as the reward. Our evaluation criteria is progressive validation (Blum et al., 1999) on 0/1 loss. We compare several baseline algorithms to Online Cover; all algorithms take advantage of linear representations which are known to work well on this dataset. For each algorithm, we report the result for the best parameter settings (shown in Table 1).

$\epsilon$-greedy (Sutton and Barto, 1998) explores randomly with probability $\epsilon$ and otherwise exploits.

Explore-first is a variant that begins with uniform exploration, then switches to an exploit-only phase.

A less common but powerful baseline is based on bagging: multiple predictors (policies) are trained with examples sampled with replacement. Given a context, these predictors yield a distribution over actions from which we can sample.

LinUCB (Auer, 2002; Chu et al., 2011) has been quite effective in past evaluations (Li et al., 2010; Chapelle and Li, 2011). It is impractical to run “as is” due to high-dimensional matrix inversions, so we report results for this algorithm after reducing to $1000$ dimensions via random projections. Still, the algorithm required $59$ hoursThe linear algebra routines are based on Intel MKL package.. An alternative is to use diagonal approximation to the covariance, which runs substantially faster ($\approx$1 hour), but gives a worse error of 0.137.

Finally, our algorithm achieves the best loss of $0.0530$. Somewhat surprisingly, the minimum occurs for us with a cover set of size 1—apparently for this problem the small decaying amount of uniform random sampling imposed is adequate exploration. Prediction performance is similar with a larger cover set.

All baselines except for LinUCB are implemented as a simple modification of Vowpal Wabbit. All reported results use default parameters where not otherwise specified. The contextual bandit learning algorithms all use a doubly robust reward estimator instead of the importance weighted estimators used in our analysis Dudík et al. (2011b).

Because RCV1 is actually a fully supervised dataset, we can apply a fully supervised online multiclass algorithm to solve it. We use a simple one-against-all implementation to reduce this to binary classification, yielding an error rate of $0.051$ which is competitive with the best previously reported results. This is effectively a lower bound on the loss we can hope to achieve with algorithms using only partial information. Our algorithm is less than 2.3 times slower and nearly achieves the bound. Hence on this dataset, very little further algorithmic improvement is possible.

Conclusions

In this paper we have presented the first practical algorithm to our knowledge that attains the statistically optimal regret guarantee and is computationally efficient in the setting of general policy classes. A remarkable feature of the algorithm is that the total number of oracle calls over all $T$ rounds is sublinear—a remarkable improvement over previous works in this setting. We believe that the online variant of the approach which we implemented in our experiments has the right practical flavor for a scalable solution to the contextual bandit problem. In future work, it would be interesting to directly analyze the Online Cover algorithm.

We thank Dean Foster and Matus Telgarsky for helpful discussions. Part of this work was completed while DH and RES were visiting Microsoft Research.

References

Appendix A Omitted Algorithm Details

Algorithm 3 and Algorithm 4 give the details of the inverse propensity scoring transformation $\mathsf{IPS}$ and the action sampling procedure $\mathsf{Sample}$.

Appendix B Deviation Inequalities

The following form of Freedman’s inequality for martingales is from Beygelzimer et al. (2011).

B.2 Variance Bounds

Fix the epoch schedule $0=\tau_{0}<\tau_{1}<\tau_{2}<\dotsb$.

Define the following for any probability distribution $P$ over $\Pi$, $\pi\in\Pi$, and $\mu\in[0,1/K]$:

The proof of the following lemma is essentially the same as that of Theorem 6 from Dudík et al. (2011a).

Using the probabilistic method (for more details, we refer the reader to the proof of Theorem 6 from Dudík et al. (2011a)), it can be shown that for any probability distribution $P$ over $\Pi$, any $\pi\in\Pi$, any $\mu_{m}\in[0,1/K]$, and any $c_{m}>0$, there exists an $N_{m}$-point distribution $\widetilde{P}$ over $\Pi$ such that

where $\gamma_{N,\mu}:=\sqrt{(1-K\mu)/(N\mu)}+3(1-K\mu)/(N\mu)$.

Combining the displayed inequalities (using $c_{m}:=1/(1-(e-2)\lambda_{m}/\mu_{m})$) and rearranging gives

If $\mu_{m}\geq\sqrt{\ln(2|\Pi|m^{2}/\delta)/(K\tau_{m})}$ and $\tau_{m}\geq 4K\ln(2|\Pi|m^{2}/\delta)$, then $\mu_{m}^{2}\tau_{m}\geq\ln(|\Pi|)/K$ and $\mu_{m}\tau_{m}\geq\ln(2|\Pi|^{2}m^{2}/\delta)$, and hence

B.3 Reward Estimates

$Q_{m-1}\in\Delta^{\Pi}$ are the non-negative weights computed at the end of epoch $m-1$;

$\widetilde{Q}_{m-1}$ is the probability distribution over $\Pi$ obtained from $Q_{m-1}$ and the policy $\pi_{m-1}$ with the highest reward estimate through epoch $m-1$;

$\widetilde{Q}_{m-1}^{\mu_{m-1}}(\cdot|x_{t})$ is the probability distribution used to choose $a_{t}$.

where $Z_{i}:=\hat{r}_{i}(\pi(x_{i}))-r_{i}(\pi(x_{i}))$. Round $i$ is in epoch $m(i)\leq m$, so

Appendix C Regret Analysis

Throughout this section, we fix the allowed probability of failure $\delta\in(0,1)$ provided as input to the algorithm, as well as the epoch schedule $0=\tau_{0}<\tau_{1}<\tau_{2}<\dotsb$.

Recall that we assume $\tau_{m+1}\leq 2\tau_{m}$; thus ${\rho}\leq\sqrt{2}$.

C.2 Deviation Control and Optimization Constraints

Let $\mathcal{E}$ be the event in which the following statements hold:

Recall that $\psi=100$ (as defined in (OP), assuming ${\rho}\leq\sqrt{2}$). Define $\theta_{1}:=94.1$ and $\theta_{2}:=\psi/6.4$ (needed for the next Lemma 12). With these settings, the proof of Lemma 13 will require that $\theta_{2}\geq 8{\rho}$, and hence $\psi\geq 6.4\cdot 8{\rho}$; this is true with our setting of $\psi$ since ${\rho}\leq\sqrt{2}$.

C.3 Proof of Theorem 2

We now give the proof of Theorem 2, following the outline in Section 4.

The following lemma shows that if $\mathcal{V}_{t}(\pi)$ is large—specifically, much larger than $K$—then the estimated regret of $\pi$ was large in some previous round.

The probability distribution $\widetilde{Q}_{m}$ satisfies the inequalities

Above, the first inequality follows because the value of $\widehat{V}_{m}(Q_{m},\pi,\mu_{m})$ decreases as the value of $Q_{m}(\pi_{\tau_{m}})$ increases, as it does when going from $Q_{m}$ to $\widetilde{Q}_{m}$; the second inequality is the constraint Eq. (16) satisfied by $Q_{m}$. Combining the displayed inequalities from above proves the claim. ∎

Assume event $\mathcal{E}$ holds. Let ${c_{0}}:=4{\rho}(1+\theta_{1})$. For all epochs $m\geq m_{0}$, all rounds $t\geq t_{0}$ in epoch $m$, and all policies $\pi\in\Pi$,

The proof is by induction on $m$. As the base case, consider $m=m_{0}$ and $t\geq t_{0}$ in epoch $m$. By definition of $m_{0}$, $\mu_{m^{\prime}}=1/(2K)$ for all $m^{\prime}<m_{0}$, so $\mathcal{V}_{t}(\pi)\leq 2K$ for all $\pi\in\Pi$ by Lemma 12. By Eq. (14), which holds in event $\mathcal{E}$, for all $\pi\in\Pi$,

where we use the fact that $4Kd_{t}/t\leq 1$ for $t\geq t_{0}$. This implies

by the triangle inequality and optimality of $\pi_{t}$ and $\pi_{\star}$. Since $t>\tau_{m_{0}-1}$ and ${c_{0}}\geq 2\sqrt{6}{\rho}$, it follows that $|\widehat{}\operatorname{Reg}_{t}(\pi)-\operatorname{Reg}(\pi)|\leq 2\sqrt{6}{\rho}K\mu_{m_{0}}\leq{c_{0}}K\mu_{m_{0}}$.

For the inductive step, fix some epoch $m>m_{0}$. We assume as the inductive hypothesis that for all epochs $m^{\prime}<m$, all rounds $t^{\prime}$ in epoch $m^{\prime}$, and all $\pi\in\Pi$,

for all rounds $t$ in epoch $m$ and all $\pi\in\Pi$. So fix such a round $t$ and policy $\pi$; by Eq. (14) (which holds in event $\mathcal{E}$),

Above, the first inequality follows from the optimality of $\pi_{t}$. By Lemma 12, there exist epochs $i,j<m$ such that

Suppose $\mu_{i}<1/(2K)$, so $m_{0}\leq i<m$: in this case, the inductive hypothesis implies

where the second inequality uses the fact that $i\leq m-1$. Therefore,

Now suppose $\mu_{j}<1/(2K)$, so $m_{0}\leq j<m$: as above, the inductive hypothesis implies

since $\operatorname{Reg}(\pi_{\star})=0$. Therefore,

Combining Eq. (18), Eq. (19), and Eq. (20), and rearranging gives

Since $m\geq m_{0}+1$, it follows that $\mu_{m-1}\leq{\rho}\mu_{m}$ by definition of ${\rho}$. Moreover, since $t>\tau_{m-1}$, $(d_{t}/t)/\mu_{m-1}\leq K\mu_{m-1}^{2}/\mu_{m-1}\leq{\rho}K\mu_{m}$ Applying these inequalities to the above display, and simplifying, yields Eq. (17) because ${c_{0}}\geq 4{\rho}(1+\theta_{1})$ and $\theta_{2}\geq 8{\rho}$.

for all $\pi\in\Pi$. Again, fix an arbitrary $\pi\in\Pi$, and by Eq. (14),

where the first inequality follows from the optimality of $\pi_{\star}$. By Lemma 12, there exists an epoch $j<m$ such

Suppose $\mu_{j}<1/(2K)$, so $m_{0}\leq j<m$: in this case the inductive hypothesis and Eq. (17) imply

(the last equality follows because $\widehat{}\operatorname{Reg}_{t}(\pi_{t})=0$). Thus

Combining Eq. (22), Eq. (23), and Eq. (19) gives

Again, applying the inequalities $\mu_{m-1}\leq{\rho}\mu_{m}$ and $(d_{t}/t)/\mu_{m-1}\leq K\mu_{m}$ to the above display, and simplifying, yields Eq. (21) because ${c_{0}}\geq 4{\rho}(1+\theta_{1})$ and $\theta_{2}\geq 8{\rho}$. This completes the inductive step, and thus proves the overall claim. ∎

The next lemma shows that the “low estimated regret guarantee” of $Q_{t-1}$ (optimization constraint Eq. (15)) also implies a “low regret guarantee”, via the comparison of $\widehat{}\operatorname{Reg}_{t}(\cdot)$ to $\operatorname{Reg}(\cdot)$ from Lemma 13.

The first step follows from Lemma 13, as all rounds in an epoch $m\geq m_{0}+1$ satisfy $t\geq t_{0}$; the second step follows from the fact that $\widetilde{Q}_{m-1}$ is a probability distribution, that $\widetilde{Q}_{m-1}=Q_{m-1}+\alpha\mathds{1}_{\pi_{\tau_{m-1}}}$ for some $\alpha\geq 0$, and that $\widehat{}\operatorname{Reg}_{\tau_{m-1}}(\pi_{\tau_{m-1}})=0$; and the last step follows from the constraint Eq. (15) satisfied by $Q_{m-1}$. ∎

Finally, we straightforwardly translate the “low regret guarantee” from Lemma 14 to a bound on the cumulative regret of the algorithm. This involves summing the bound in Lemma 14 over all rounds $t$ (Lemma 15 and Lemma 16) and applying a martingale concentration argument (Lemma 17).

We break the sum over rounds into the epochs, and bound the sum within each epoch:

Above, the first step uses the fact that $m(1)=1$ and $\tau_{m(t)-1}+1\leq t\leq\tau_{m(t)}$. The second step uses the definition of $\mu_{m}$. The third step simplifies the sum over $t$ and uses the bound $d_{\tau_{m-1}}\leq d_{\tau_{m(T)}}$. The remaining steps use an integral bound which is then directly evaluated (recalling that $\tau_{0}=0$). ∎

Under the epoch schedule condition $\tau_{m+1}\leq 2\tau_{m}$, we have $\mu_{m(t)-1}\leq\sqrt{2}\mu_{m(t)}$ whenever $m(t)>m_{0}$; also, $\mu_{m(t)-1}\leq 1/(2K)$ whenever $m(t)\leq m_{0}$. The conclusion follows by applying Lemma 15. ∎

where ${C_{0}}:=(4\psi+{c_{0}})$ and ${c_{0}}$ is defined in Lemma 13.

with probability at least $1-\delta/2$. By Lemma 10, Lemma 11, and a union bound, the event $\mathcal{E}$ holds with probability at least $1-\delta/2$. Hence, by another union bound, with probability at least $1-\delta$, event $\mathcal{E}$ holds and the regret of the algorithm is bounded by

The double summation above is bounded by Lemma 14 and Lemma 16:

By the definition of $m_{0}$, $\tau_{m_{0}-1}\leq 4Kd_{\tau_{m_{0}-1}}$. Since $\tau_{m_{0}}\leq 2\tau_{m_{0}-1}$ by assumption, it follows that $\tau_{m_{0}}\leq 8Kd_{\tau_{m_{0}-1}}$. ∎

Theorem 2 follows from Lemma 17 and the fact that $\tau_{m(T)}\leq 2(T-1)$ whenever $\tau_{m(T)-1}\geq 1$.

There is one last result implied by Lemma 12 and Lemma 13 that is used elsewhere.

Assume event $\mathcal{E}$ holds, and $t$ is such that $d_{\tau_{m(t)-1}}/\tau_{m(t)-1}\leq 1/(4K)$. Then

Let $m^{\prime}<m(t)$ achieve the $\max$ in the definition of $\mathcal{V}_{t}(\pi_{\star})$. If $\mu_{m^{\prime}}<1/(2K)$, then $m^{\prime}\geq m_{0}$, and

for $c:=\theta_{1}+{c_{0}}/\theta_{2}$. Above, the second inequality follows by Lemma 13. If $\mu_{m^{\prime}}=1/(2K)$, then the same bound also holds. Using this bound, we obtain from Eq. (14),

where the last inequality follows from Lemma 13. The claim follows because $d_{t}/t\leq d_{\tau_{m(t)-1}}/\tau_{m(t)-1}$ and $\mu_{m(t)}\leq\mu_{m(t)-1}$. ∎

Appendix D Details of Optimization Analysis

Following the execution of Step 4, we must have

This is because, if the condition in Step 7 does not hold, then Eq. (24) is already true. Otherwise, $Q$ is replaced by $Q^{\prime}=cQ$, and for this set of weights, Eq. (24) in fact holds with equality. Note that, since all quantities are nonnegative, Eq. (24) immediately implies both Eq. (2), and that $\sum_{\pi}Q(\pi)\leq 1$.

Furthermore, at the point where the algorithm halts at Step 10, it must be that for all policies $\pi$, ${D_{\pi}({Q})}\leq 0$. However, unraveling definitions, we can see that this is exactly equivalent to Eq. (3). ∎

D.2 Proof of Lemma 6

To see the inequality in Eq. (26), let us fix $x$ and define $q_{a}=cQ(a|x)$. Then $\sum_{a}q_{a}=c\sum_{\pi}Q(\pi)\leq 1$ by Eq. (4). Further, the expression inside the expectation in Eq. (26) is equal to

Eq. (27) uses Jensen’s inequality, combined with the fact that the function $1/(1-K\mu+\mu/x)$ is concave (as a function of $x$). Eq. (28) uses the fact that the function $1/(1-K\mu+K\mu/x)$ is nondecreasing (in $x$), and that the $q_{a}$’s sum to at most $1$.

Thus, plugging Eq. (26) into Eq. (25) yields

by our definition of $c$. Since $g$ is convex, this means that $g$ is nondecreasing for all values exceeding $c$. In particular, since $c<1$, this gives

D.3 Proof of Lemma 7

We first compute the change in potential for general $\alpha$. Note that ${Q^{\prime}}^{\mu}(a|x)=Q^{\mu}(a|x)$ if $a\neq\pi(x)$, and otherwise

Thus, most of the terms defining ${\Phi_{m}}(Q)$ are left unchanged by the update. In particular, by a direct calculation:

Eq. (D.3) uses the bound $\ln(1+x)\geq x-x^{2}/2$ which holds for $x\geq 0$ (by Taylor’s theorem). Eq. (31) holds by our choice of $\alpha={\alpha_{\pi}({Q})}$, which was chosen to maximize Eq. (30). By assumption, ${D_{\pi}({Q})}>0$, which implies ${V_{\pi}({Q})}>2K$. Further, since $Q^{\mu}(a|x)\geq\mu$ always, we have

Plugging into Eq. (31) completes the lemma. ∎

D.4 Proof of Lemma 8

We break the potential of Eq. (6) into pieces and bound the total change in each separately. Specifically, by straightforward algebra, we can write

We assume throughout that $\sum_{\pi}Q(\pi)\leq 1$ as will always be the case for the vectors produced by Algorithm 2. For such a vector $Q$,

since $\tau_{m}\mu_{m}$ is nondecreasing. This means we can essentially disregard the change in this term.

Also, note that ${\phi_{m}^{b}}$ does not depend on $Q$. Therefore, for this term, we get a telescoping sum:

since $K\mu_{M+1}\leq 1/2$, and where $d_{T}$, used in the definition of $\mu_{m}$, is defined in Eq. (12).

Note that $C_{m}\geq C_{m+1}$ since $\mu_{m}\geq\mu_{m+1}$ and $-\ln Q^{\mu_{m}}(a|x_{t})\geq 0$. Thus,

Eq. (32) uses $Q^{\mu_{m+1}}(a|x)\geq\mu_{m+1}$, and also

using $\mu_{m+1}\leq\mu_{m}$. A sum over the two terms appearing in Eq. (32) can now be bounded separately. Starting with the one on the left, since $\tau_{m}<\tau_{m+1}\leq T$ and $K\mu_{m}\leq 1/2$, we have

For the second term in Eq. (32), using $\mu_{m+1}\geq\mu_{M+1}$ for $m\leq M$, and definition of $C_{m}$, we have

by Lemma 15. Combining Eqs. (32), (33) and (34) gives the statement of the lemma. ∎

Finally, we come to ${\phi_{m}^{d}}(Q)$, which, by definition of ${b_{\pi}}$, can be rewritten as

where $B_{1}=1/(2K\psi)$ and $\psi$ is the same as appears in optimization problem (OP). Note that, conveniently,

where $\widehat{\cal S}_{m}(\pi)$ is the cumulative empirical importance-weighted reward through round $\tau_{m}$:

We separately bound the two parenthesized expressions in Eq. (35) when summed over all epochs. Beginning with the first one, we have

But by Lemma 18 (and under the same assumptions),

where $D_{0}$ is the constant appearing in Lemma 18.

For the second parenthesized expression of Eq. (35), let us define random variables

Note that $Z_{t}$ is nonnegative, and if $m=\tau(t)$, then

The expectation that appears here can be computed to be

by Lemma 14 (under the same assumptions, and using the same constants). Thus, with high probability,

Combining the above bound with our earlier inequality Eq. (36), and applying the union bound, we find that with probability at least $1-2\delta$, for all $T$ (and corresponding $M$),

Combining the bounds on the separate pieces, we get the bound stated in the lemma.

D.5 Proof of Lemma 3

Appendix E Proof of Theorem 4

Recall the earlier definition of the low-variance distribution set

Below, we use a policy class $\Pi$ where every policy $\pi\in\Pi$ has no regret ($\operatorname{Reg}(\pi)=0$), in which case Lemma 13 implies

(to make $Q$ into a probability distribution $\widetilde{Q}$, the leftover mass can be put on any policy, say, already in the support of $Q$). That is, with high probability, for every relevant epoch $m$, every $Q\in\mathcal{Q}_{m}$ satisfies Eq. (37) for all $\pi\in\Pi$.

Next, we construct an instance with the property that these inequalities cannot be satisfied by a very sparse $Q$. An instance is drawn uniformly at random from $N$ different contexts denoted as $\{1,2,\ldots,N\}$ (where we set, with foresight, $N:=1/(2\sqrt{2}cK\mu_{M})$). The reward structure in the problem will be extremely simple, with action $K$ always obtaining a reward of 1, while all the other actions obtain a reward of 0, independent of the context. The distribution $\mathcal{D}$ will be uniform over the contexts (with these deterministic rewards). Our policy set $\Pi$ will consist of $(K-1)N$ separate policies, indexed by $1\leq i\leq N$ and $1\leq j\leq K-1$. Policy $\pi_{ij}$ has the property that

In words, policy $\pi_{ij}$ takes action $j$ on context $i$, and action $K$ on all other contexts. Given the uniform distribution over contexts and our reward structure, each policy obtains an identical reward

In particular, each policy has a zero expected regret as required.

Finally, observe that on context $i$, $\pi_{ij}$ is the unique policy taking action $j$. Hence we have that $\widetilde{Q}(j|i)=\widetilde{Q}(\pi_{ij})$ and $\widetilde{Q}^{\mu_{m}}(j|i)=(1-K\mu_{m})\widetilde{Q}(\pi_{ij})+\mu_{m}$. Now, let us consider the constraint Eq. (37) for the policy $\pi_{ij}$. The left-hand side of this constraint can be simplified as

If the distribution $\widetilde{Q}$ does not put any support on the policy $\pi_{ij}$, then $\widetilde{Q}^{\mu_{m}}(j|i)=\mu_{m}$, and thus

(since $N<1/(\sqrt{2}cK\mu_{M})$). Such a distribution $\widetilde{Q}$ violates Eq. (37), which means that every $Q\in\mathcal{Q}_{m}$ must have $\widetilde{Q}(\pi_{ij})>0$. Since this is true for each policy $\pi_{ij}$, we see that every $Q\in\mathcal{Q}_{m}$ has

Appendix F Online Cover algorithm

This section describes the pseudocode of the precise algorithm use in our experiments (Algorithm 5). The minimum exploration probability $\mu$ was set as $0.05\,\min(1/K,1/\sqrt{tK})$ for our evaluation.

Two additional details are important in Step 9:

We pass a cost vector rather than a reward vector to the oracle since we have a loss minimization rather than a reward maximization oracle.

We actually used a doubly robust estimate Dudík et al. (2011b) with a linear reward function that was trained in an online fashion.