Efficient Optimal Learning for Contextual Bandits

INTRODUCTION

The contextual bandit setting consists of the following loop repeated indefinitely:

The world presents context information as features $x$.

The learning algorithm chooses an action $a$ from $K$ possible actions.

The world presents a reward $r$ for the action.

The key difference between the contextual bandit setting and standard supervised learning is that only the reward of the chosen action is revealed. For example, after always choosing the same action several times in a row, the feedback given provides almost no basis to prefer the chosen action over another action. In essence, the contextual bandit setting captures the difficulty of exploration while avoiding the difficulty of credit assignment as in more general reinforcement learning settings.

The contextual bandit setting is a half-way point between standard supervised learning and full-scale reinforcement learning where it appears possible to construct algorithms with convergence rate guarantees similar to supervised learning. Many natural settings satisfy this half-way point, motivating the investigation of contextual bandit learning. For example, the problem of choosing interesting news articles or ads for users by internet companies can be naturally modeled as a contextual bandit setting. In the medical domain where discrete treatments are tested before approval, the process of deciding which patients are eligible for a treatment takes contexts into account. More generally, we can imagine that in a future with personalized medicine, new treatments are essentially equivalent to new actions in a contextual bandit setting.

In the i.i.d. setting, the world draws a pair $(x,\vec{r})$ consisting of a context and a reward vector from some unknown distribution $D$, revealing $x$ in Step 1, but only the reward $r(a)$ of the chosen action $a$ in Step 3. Given a set of policies $\Pi=\{\pi:X\rightarrow A\}$, the goal is to create an algorithm for Step 2 which competes with the set of policies. We measure our success by comparing the algorithm’s cumulative reward to the expected cumulative reward of the best policy in the set. The difference of the two is called regret.

All existing algorithms for this setting either achieve a suboptimal regret (Langford and Zhang, 2007) or require computation linear in the number of policies (Auer et al., 2002b; Beygelzimer et al., 2011). In unstructured policy spaces, this computational complexity is the best one can hope for. On the other hand, in the case where the rewards of all actions are revealed, the problem is equivalent to cost-sensitive classification, and we know of algorithms to efficiently search the space of policies (classification rules) such as cost-sensitive logistic regression and support vector machines. In these cases, the space of classification rules is exponential in the number of features, but these problems can be efficiently solved using convex optimization.

All previous regret-optimal approaches are measure based—they work by updating a measure over policies, an operation which is linear in the number of policies. In contrast, regret guarantees scale only logarithmically in the number of policies. If not for the computational bottleneck, these regret guarantees imply that we could dramatically increase performance in contextual bandit settings using more expressive policies. We overcome the computational bottleneck using an algorithm which works by creating cost-sensitive classification instances and calling an oracle to choose optimal policies. Actions are chosen based on the policies returned by the oracle rather than according to a measure over all policies. This is reminiscent of AdaBoost (Freund and Schapire, 1997), which creates weighted binary classification instances and calls a “weak learner” oracle to obtain classification rules. These classification rules are then combined into a final classifier with boosted accuracy. Similarly as AdaBoost converts a weak learner into a strong learner, our approach converts a cost-sensitive classification learner into an algorithm that solves the contextual bandit problem.

In a more difficult version of contextual bandits, an adversary chooses $(x,\vec{r})$ given knowledge of the learning algorithm (but not any random numbers). All known regret-optimal solutions in the adversarial setting are variants of the EXP4 algorithm (Auer et al., 2002b). EXP4 achieves the same regret rate as our algorithm: $O\left(\sqrt{KT\ln N}\right)$, where $T$ is the number of time steps, $K$ is the number of actions available in each time step, and $N$ is the number of policies.

Why not use EXP4 in the i.i.d. setting? For example, it is known that the algorithm can be modified to succeed with high probability (Beygelzimer et al., 2011), and also for VC classes when the adversary is constrained to i.i.d. sampling. There are two central benefits that we hope to realize by directly assuming i.i.d. contexts and reward vectors.

Computational Tractability. Even when the reward vector is fully known, adversarial regrets scale as $O\left(\sqrt{\ln N}\right)$ while computation scales as $O(N)$ in general. One attempt to get around this is the follow-the-perturbed-leader algorithm (Kalai and Vempala, 2005) which provides a computationally tractable solution in certain special-case structures. This algorithm has no mechanism for efficient application to arbitrary policy spaces, even given an efficient cost-sensitive classification oracle. An efficient cost-sensitive classification oracle has been shown effective in transductive settings (Kakade and Kalai, 2005). Aside from the drawback of requiring a transductive setting, the regret achieved there is substantially worse than for EXP4.

Improved Rates. When the world is not completely adversarial, it is possible to achieve substantially lower regrets than are possible with algorithms optimized for the adversarial setting. For example, in supervised learning, it is possible to obtain regrets scaling as $O(\log(T))$ with a problem dependent constant (Bartlett et al., 2007). When the feedback is delayed by $\tau$ rounds, lower bounds imply that the regret in the adversarial setting increases by a multiplicative $\sqrt{\tau}$ while in the i.i.d. setting, it is possible to achieve an additive regret of $\tau$ (Langford et al., 2009).

In a direct i.i.d. setting, the previous-best approach using a cost-sensitive classification oracle was given by $\epsilon$-greedy and epoch greedy algorithms (Langford and Zhang, 2007) which have a regret scaling as $O(T^{2/3})$ in the worst case.

There have also been many special-case analyses. For example, theory of context-free setting is well understood (Lai and Robbins, 1985; Auer et al., 2002a; Even-Dar et al., 2006). Similarly, good algorithms exist when rewards are linear functions of features (Auer, 2002) or actions lie in a continuous space with the reward function sampled according to a Gaussian process (Srinivas et al., 2010).

2 WHAT WE PROVE

In Section 3 we state the PolicyElimination algorithm, and prove the following regret bound for it.

For all distributions $D$ over $(x,\vec{r})$ with $K$ actions, for all sets of $N$ policies $\Pi$, with probability at least $1-\delta$, the regret of PolicyElimination (Algorithm 1) over $T$ rounds is at most

This result can be extended to deal with VC classes, as well as other special cases. It forms the simplest method we have of exhibiting the new analysis.

The new key element of this algorithm is identification of a distribution over actions which simultaneously achieves small expected regret and allows estimating value of every policy with small variance. The existence of such a distribution is shown nonconstructively by a minimax argument.

PolicyElimination is computationally intractable and also requires exact knowledge of the context distribution (but not the reward distribution!). We show how to address these issues in Section 4 using an algorithm we call RandomizedUCB. Namely, we prove the following theorem.

For all distributions $D$ over $(x,\vec{r})$ with $K$ actions, for all sets of $N$ policies $\Pi$, with probability at least $1-\delta$, the regret of RandomizedUCB (Algorithm 2) over $T$ rounds is at most

RandomizedUCB’s analysis is substantially more complex, with a key subroutine being an application of the ellipsoid algorithm with a cost-sensitive classification oracle (described in Section 5). RandomizedUCB does not assume knowledge of the context distribution, and instead works with the history of contexts it has observed. Modifying the proof for this empirical distribution requires a covering argument over the distributions over policies which uses the probabilistic method. The net result is an algorithm with a similar top-level analysis as PolicyElimination, but with the running time only poly-logarithmic in the number of policies given a cost-sensitive classification oracle.

Apart from a tractable algorithm, our analysis can be used to derive tighter regrets than would be possible in adversarial setting. For example, in Section 6, we consider a common setting where reward feedback is delayed by $\tau$ rounds. A straightforward modification of PolicyElimination yields a regret with an additive term proportional to $\tau$ compared with the delay-free setting. Namely, we prove the following.

For all distributions $D$ over $(x,\vec{r})$ with $K$ actions, for all sets of $N$ policies $\Pi$, and all delay intervals $\tau$, with probability at least $1-\delta$, the regret of DelayedPE (Algorithm 3) is at most

We start next with precise settings and definitions.

SETTING AND DEFINITIONS

Let $A$ be the set of $K$ actions, let $X$ be the domain of contexts $x$, and let $D$ be an arbitrary joint distribution on $(x,\vec{r})$. We denote the marginal distribution of $D$ over $X$ by $D_{X}$.

We denote $\Pi$ to be a finite set of policies $\{\pi:X\rightarrow A\}$, where each policy $\pi$, given a context $x_{t}$ in round $t$, chooses the action $\pi(x_{t})$. The cardinality of $\Pi$ is denoted by $N$. Let $\vec{r}_{t}\in^{K}$ be the vector of rewards, where $r_{t}(a)$ is the reward of action $a$ on round $t$.

In the i.i.d. setting, on each round $t=1\ldots T$, the world chooses $(x_{t},\vec{r}_{t})$ i.i.d. according to $D$ and reveals $x_{t}$ to the learner. The learner, having access to $\Pi$, chooses action $a_{t}\in\{1,\ldots,K\}$. Then the world reveals reward $r_{t}(a_{t})$ (which we call $r_{t}$ for short) to the learner, and the interaction proceeds to the next round.

We consider two modes of accessing the set of policies $\Pi$. The first option is through the enumeration of all policies. This is impractical in general, but suffices for the illustrative purpose of our first algorithm. The second option is an oracle access, through an argmax oracle, corresponding to a cost-sensitive learner:

The reason why the above can be viewed as a cost-sensitive classification oracle is that vectors of rewards $\vec{r}_{t^{\prime}}$ can be interpreted as negative costs and hence the policy returned by $\mathcal{AMO}$ is the optimal cost-sensitive classifier on the given data.

2 EXPECTED AND EMPIRICAL REWARDS

Let the expected instantaneous reward of a policy $\pi\in\Pi$ be denoted by

The best policy $\pi_{\max}\in\Pi$ is that which maximizes $\eta_{D}(\pi)$. More formally,

We define $h_{t}$ to be the history at time $t$ that the learner has seen. Specifically

where $p_{t^{\prime}}$ is the probability of the algorithm choosing action $a_{t^{\prime}}$ at time $t^{\prime}$. Note that $a_{t^{\prime}}$ and $p_{t^{\prime}}$ are produced by the learner while $x_{t^{\prime}},r_{t^{\prime}}$ are produced by nature. We write $x\sim h$ to denote choosing $x$ uniformly at random from the $x$’s in history $h$.

Using the history of past actions and probabilities with which they were taken, we can form an unbiased estimate of the policy value for any $\pi\in\Pi$:

3 REGRET

The goal of this work is to obtain a learner that has small regret relative to the expected performance of $\pi_{\max}$ over $T$ rounds, which is

We say that the regret of the learner over $T$ rounds is bounded by $\epsilon$ with probability at least $1-\delta$, if

where the probability is taken with respect to the random pairs $(x_{t},\vec{r}_{t})\sim D$ for $t=1\dotsc T$, as well as any internal randomness used by the learner.

We can also define notions of regret and empirical regret for policies $\pi$. For all $\pi\in\Pi$, let

Our algorithms work by choosing distributions over policies, which in turn then induce distributions over actions. For any distribution $P$ over policies $\Pi$, let $W_{P}(x,a)$ denote the induced conditional distribution over actions $a$ given the context $x$:

In general, we shall use $W$, $W^{\prime}$ and $Z$ as conditional probability distributions over the actions $A$ given contexts $X$, i.e., $W:X\times A\to$ such that $W(x,\cdot)$ is a probability distribution over $A$ (and similarly for $W^{\prime}$ and $Z$). We shall think of $W^{\prime}$ as a smoothed version of $W$ with a minimum action probability of $\mu$ (to be defined by the algorithm), such that

Conditional distributions such as $W$ (and $W^{\prime}$, $Z$, etc.) correspond to randomized policies. We define notions true and empirical value and regret for them as follows:

POLICY ELIMINATION

The basic ideas behind our approach are demonstrated in our first algorithm: PolicyElimination (Algorithm 1).

The key step is Step 1, which finds a distribution over policies which induces low variance in the estimate of the value of all policies. Below we use minimax theorem to show that such a distribution always exists. How to find this distribution is not specified here, but in Section 5 we develop a method based on the ellipsoid algorithm. Step 2 then projects this distribution onto a distribution over actions and applies smoothing. Finally, Step 5 eliminates the policies that have been determined to be suboptimal (with high probability).

We analyze PolicyElimination in several steps. First, we prove the existence of $P_{t}$ in Step 1, provided that $\Pi_{t-1}$ is non-empty. We recast the feasibility problem in Step 1 as a game between two players: Prover, who is trying to produce $P_{t}$, and Falsifier, who is trying to find $\pi$ violating the constraints. We give more power to Falsifier and allow him to choose a distribution over $\pi$ (i.e., a randomized policy) which would violate the constraints.

Let $\mathcal{C}$ be a compact and convex set of randomized policies. Let $\mu\in(0,1/K]$ and for any $W\in\mathcal{C}$, $W^{\prime}(x,a)\doteq(1-K\mu)W(x,a)+\mu$. Then for all distributions $D$,

everywhere defined: Since $W^{\prime}(x,a)\geq\mu$, we obtain that $1/W^{\prime}(x,a)\in[0,1/\mu]$, hence the expectations are defined for all $W$ and $Z$.

linear in $Z$: Linearity follows from rewriting $f(W,Z)$ as

convex in $W$: Note that $1/W^{\prime}(x,a)$ is convex in $W(x,a)$ by convexity of $1/(c_{1}w+c_{2})$ in $w\geq 0$, for $c_{1}\geq 0$, $c_{2}>0$. Convexity of $f(W,Z)$ in $W$ then follows by taking expectations over $x$ and $a$.

Hence, by Theorem 14 (in Appendix B), min and max can be reversed without affecting the value:

The right-hand side can be further upper-bounded by $\max_{Z\in\mathcal{C}}f(Z,Z)$, which is upper-bounded by

The set of distributions satisfying constraints of Step 1 is non-empty.

Given the existence of $P_{t}$, we will see below that the constraints in Step 1 ensure low variance of the policy value estimator $\eta_{t}(\pi)$ for all $\pi\in\Pi_{t-1}$. The small variance is used to ensure accuracy of policy elimination in Step 5 as quantified in the following lemma:

With probability at least $1-\delta$, for all $t$:

$\pi_{\max}\in\Pi_{t}$ (i.e., $\Pi_{t}$ is non-empty)

$\eta_{D}(\pi_{\max})-\eta_{D}(\pi)\leq 4b_{t}$ for all $\pi\in\Pi_{t}$

We will show that for any policy $\pi\in\Pi_{t-1}$, the probability that $\eta_{t}(\pi)$ deviates from $\eta_{D}(\pi)$ by more that $b_{t}$ is at most $2\delta_{t}$. Taking the union bound over all policies and all time steps we find that with probability at least $1-\delta$,

for all $t$ and all $\pi\in\Pi_{t-1}$. Then:

By the triangle inequality, in each time step, $\eta_{t}(\pi)\leq\eta_{t}(\pi_{\max})+2b_{t}$ for all $\pi\in\Pi_{t-1}$, yielding the first part of the lemma.

Also by the triangle inequality, if $\eta_{D}(\pi)<\eta_{D}(\pi_{\max})-4b_{t}$ for $\pi\in\Pi_{t-1}$, then $\eta_{t}(\pi)<\eta_{t}(\pi_{\max})-2b_{t}$. Hence the policy $\pi$ is eliminated in Step 5, yielding the second part of the lemma.

It remains to show Eq. (3.1). We fix the policy $\pi\in\Pi$ and time $t$, and show that the deviation bound is violated with probability at most $2\delta_{t}$. Our argument rests on Freedman’s inequality (see Theorem 13 in Appendix A). Let

Since $r_{t}\in$ and $W^{\prime}_{t}(a_{t})\geq\mu_{t}$, we have the bound

where Eq. (3.2) follows by boundedness of $r_{t}$ and Eq. (3.3) follows from the constraints in Step 1. Hence,

Since $(\ln t)/t$ is decreasing for $t\geq 3$, we obtain that $\mu_{t}$ is non-increasing (by separately analyzing $t=1$, $t=2$, $t\geq 3$). Let $t_{0}$ be the first $t$ such that $\mu_{t}<1/2K$. Note that $b_{t}\geq 4K\mu_{t}$, so for $t<t_{0}$, we have $b_{t}\geq 2$ and $\Pi_{t}=\Pi$. Hence, the deviation bound holds for $t<t_{0}$.

Let $t\geq t_{0}$. For $t^{\prime}\leq t$, by the monotonicity of $\mu_{t}$

Hence, the assumptions of Theorem 13 are satisfied, and

The union bound over $\pi$ and $t$ yields Eq. (3.1). ∎

This immediately implies that the cumulative regret is bounded by

For all distributions $D$ over $(x,\vec{r})$ with $K$ actions, for all sets of $N$ policies $\Pi$, with probability at least $1-\delta$, the regret of PolicyElimination (Algorithm 1) over $T$ rounds is at most

THE RANDOMIZED UCB ALGORITHM

PolicyElimination is the simplest exhibition of the minimax argument, but it has some drawbacks:

The algorithm keeps explicit track of the space of good policies (like a version space), which is difficult to implement efficiently in general.

If the optimal policy is mistakenly eliminated by chance, the algorithm can never recover.

The algorithm requires perfect knowledge of the distribution $D_{X}$ over contexts.

These difficulties are addressed by RandomizedUCB (or RUCB for short), an algorithm which we present and analyze in this section. Our approach is reminiscent of the UCB algorithm (Auer et al., 2002a), developed for context-free setting, which keeps an upper-confidence bound on the expected reward for each action. However, instead of choosing the highest upper confidence bound, we randomize over choices according to the value of their empirical performance. The algorithm has the following properties:

The optimization step required by the algorithm always considers the full set of policies (i.e., explicit tracking of the set of good policies is avoided), and thus it can be efficiently implemented using an argmax oracle. We discuss this further in Section 5.

Suboptimal policies are implicitly used with decreasing frequency by using a non-uniform variance constraint that depends on a policy’s estimated regret. A consequence of this is a bound on the value of the optimization, stated in Lemma 7 below.

Instead of $D_{X}$, the algorithm uses the history of previously seen contexts. The effect of this approximation is quantified in Theorem 6 below.

The regret of RandomizedUCB is the following:

For all distributions $D$ over $(x,\vec{r})$ with $K$ actions, for all sets of $N$ policies $\Pi$, with probability at least $1-\delta$, the regret of RandomizedUCB (Algorithm 2) over $T$ rounds is at most

The proof is given in Appendix D.4. Here, we present an overview of the analysis.

A key technical prerequisite for the regret analysis is the accuracy of the empirical variance estimates. For a distribution $P$ over policies $\Pi$ and a particular policy $\pi\in\Pi$, define

The first quantity $V_{P,\pi,t}$ is (a bound on) the variance incurred by an importance-weighted estimate of reward in round $t$ using the action distribution induced by $P$, and the second quantity $\widehat{V}_{P,\pi,t}$ is an empirical estimate of $V_{P,\pi,t}$ using the finite sample $\{x_{1},\dotsc,x_{t-1}\}\subseteq X$ drawn from $D_{X}$. We show that for all distributions $P$ and all $\pi\in\Pi$, $\widehat{V}_{P,\pi,t}$ is close to $V_{P,\pi,t}$ with high probability.

For any $\epsilon\in(0,1)$, with probability at least $1-\delta$,

for all distributions $P$ over $\Pi$, all $\pi\in\Pi$, and all $t\geq 16K\log(8KN/\delta)$.

2 REGRET ANALYSIS

Central to the analysis is the following lemma that bounds the value of the optimization in each round. It is a direct corollary of Lemma 24 in Appendix D.4.

If $\operatorname{OPT}_{t}$ is the value of the optimization problem (4.1) in round $t$, then

This lemma implies that the algorithm is always able to select a distribution over the policies that focuses mostly on the policies with low estimated regret. Moreover, the variance constraints ensure that good policies never appear too bad, and that only bad policies are allowed to incur high variance in their reward estimates. Hence, minimizing the objective in (4.1) is an effective surrogate for minimizing regret.

The bulk of the analysis consists of analyzing the variance of the importance-weighted reward estimates $\eta_{t}(\pi)$, and showing how they relate to their actual expected rewards $\eta_{D}(\pi)$. The details are deferred to Appendix D.

USING AN ARGMAX ORACLE

In this section, we show how to solve the optimization problem (4.1) using the argmax oracle ($\mathcal{AMO}$) for our set of policies. Namely, we describe an algorithm running in polynomial time independentOr rather dependent only on $\log N$, the representation size of a policy. of the number of policies, which makes queries to $\mathcal{AMO}$ to compute a distribution over policies suitable for the optimization step of Algorithm 2.

This algorithm relies on the ellipsoid method. The ellipsoid method is a general technique for solving convex programs equipped with a separation oracle. A separation oracle is defined as follows:

We now write a convex program whose solution is the required distribution, and show how to solve it using the ellipsoid method by giving a separation oracle for its feasible set using $\mathcal{AMO}$.

We claim that this program is equivalent to the RUCB optimization problem (4.1), up to finding an explicit distribution over policies which corresponds to the optimal solution. This can be seen as follows. Since we require $W\in\mathcal{C}$, it can be interpreted as being equal to $W_{P}$ for some distribution over policies $P$. The constraints (5.3) are equivalent to (4.1) by substitution $Z=W_{Q}$.

The above convex program can be solved by performing a binary search over $s$ and testing feasibility of the constraints. For a fixed value of $s$, the feasibility problem defined by (5.1)–(5.3) is denoted by $\mathcal{A}$.

We now give a sketch of how we construct a separation oracle for the feasible region of $\mathcal{A}$. The details of the algorithm are a bit complicated due to the fact that we need to ensure that the feasible region, when non-empty, has a non-negligible volume (recall the requirements of Lemma 8). This necessitates having a small error in satisfying the constraints of the program. We leave the details to Appendix E. Modulo these details, the construction of the separation oracle essentially implies that we can solve $\mathcal{A}$.

Before giving the construction of the separation oracle, we first show that $\mathcal{AMO}$ allows us to do linear optimization over $\mathcal{C}$ efficiently:

The sequence for $\mathcal{AMO}$ consists of $x_{t^{\prime}}\in\mathcal{X}_{t-1}$ and $\vec{r}_{t^{\prime}}(a)=w(x_{t^{\prime}},a)$. The lemma now follows since $w\cdot\pi=\sum_{x\in\mathcal{X}_{t-1}}w(x,\pi(x))$. ∎

We need another simple technical lemma which explains how to get a separating hyperplane for violations of convex constraints:

Let $g(x)=f(y)+\nabla f(y)\cdot(x-y)$. By the convexity of $f$, we have $f(x)\geq g(x)$ for all $x$. Thus, for any $x\in K$, we have $g(x)\leq f(x)\leq 0$. Since $g(y)=f(y)>0$, we conclude that $g(x)=0$ separates $y$ from $K$. ∎

Now given a candidate point $W$, a separation oracle can be constructed as follows. We check whether $W$ satisfies the constraints of $\mathcal{A}$. If any constraint is violated, then we find a hyperplane separating $W$ from all points satisfying the constraint.

First, for constraint (5.1), note that $\eta_{t-1}(W)$ is linear in $W$, and so we can compute $\max_{\pi}\eta_{t-1}(\pi)$ via $\mathcal{AMO}$ as in Lemma 9. We can then compute $\eta_{t-1}(W)$ and check if the constraint is satisfied. If not, then the constraint, being linear, automatically yields a separating hyperplane.

Next, we consider constraint (5.2). To check if $W\in\mathcal{C}$, we use the perceptron algorithm. We shift the origin to $W$, and run the perceptron algorithm with all points $\pi\in\Pi$ being positive examples. The perceptron algorithm aims to find a hyperplane putting all policies $\pi\in\Pi$ on one side. In each iteration of the perceptron algorithm, we have a candidate hyperplane (specified by its normal vector), and then if there is a policy $\pi$ that is on the wrong side of the hyperplane, we can find it by running a linear optimization over $\mathcal{C}$ in the negative normal vector direction as in Lemma 9.

If $W\notin\mathcal{C}$, then in a bounded number of iterations (depending on the distance of $W$ from $\mathcal{C}$, and the maximum magnitude $\|\pi\|_{2}$) we obtain a separating hyperplane. In passing we also note that if $W\in\mathcal{C}$, the same technique allows us to explicitly compute an approximate convex combination of policies in $\Pi$ that yields $W$. This is done by running the perceptron algorithm as before and stopping after the bound on the number of iterations has been reached. Then we collect all the policies we have found in the run of the perceptron algorithm, and we are guaranteed that $W$ is close in distance to their convex hull. We can then find the closest point in the convex hull of these policies by solving a simple quadratic program.

Define $f(Z)=\max\{4K,\beta_{t}(w\cdot Z-v)^{2}\}-u\cdot Z$. Note that $f$ is a convex function of $Z$. Finding a point $Z$ that violates the above constraint is equivalent to solving the following (convex) program:

To do this, we again apply the ellipsoid method. For this, we need a separation oracle for the program. A separation oracle for the constraints (5.5) can be constructed as in Step 2 above. For the constraints (5.4), if the candidate solution $Z$ has $f(Z)>0$, then we can construct a separating hyperplane as in Lemma 10.

Suppose that after solving the program, we get a point $Z\in\mathcal{C}$ such that $f(Z)\leq 0$, i.e. $W$ violates the constraint (5.3) for $Z$. Then since constraint (5.3) is convex in $W$, we can construct a separating hyperplane as in Lemma 10. This completes the description of the separation oracle.

Working out the details carefully yields the following theorem, proved in Appendix E:

There is an iterative algorithm with $O(t^{5}K^{4}\log^{2}(\frac{tK}{\delta}))$ iterations, each involving one call to $\mathcal{AMO}$ and $O(t^{2}K^{2})$ processing time, that either declares correctly that $\mathcal{A}$ is infeasible or outputs a distribution $P$ over policies in $\Pi$ such that $W_{P}$ satisfies

where $\epsilon=\frac{8\delta}{\mu_{t}^{2}}$ and $\gamma=\frac{\delta}{\mu_{t}}$.

DELAYED FEEDBACK

In a delayed feedback setting, we observe rewards with a $\tau$ step delay according to:

The learning algorithm chooses an action $a_{t}\in\{1,...,K\}$.

The world presents a reward $r_{t-\tau}$ for the action $a_{t-\tau}$ given the features $x_{t-\tau}$.

We deal with delay by suitably modifying Algorithm 1 to incorporate the delay $\tau$, giving Algorithm 3.

Now we can prove the following theorem, which shows the delay has an additive effect on regret.

For all distributions $D$ over $(x,\vec{r})$ with $K$ actions, for all sets of $N$ policies $\Pi$, and all delay intervals $\tau$, with probability at least $1-\delta$, the regret of DelayedPE (Algorithm 3) is at most

Essentially as Theorem 4. The variance bound is unchanged because it depends only on the context distribution. Thus, it suffices to replace $\sum_{t-1}^{T}\frac{1}{\sqrt{t}}$ with $\tau+\sum_{t=\tau+1}^{T+\tau}\frac{1}{\sqrt{t-\tau}}=\tau+\sum_{t=1}^{T}\frac{1}{\sqrt{t}}$ in Eq. (3.4). ∎

We thank Alina Beygelzimer, who helped in several formative discussions.

References

References

Appendix A Concentration Inequality

Appendix B Minimax Theorem

The following is a continuous version of Sion’s Minimax Theorem (Sion, 1958, Theorem 3.4).

Appendix C Empirical Variance Bounds

In this section we prove Theorem 6. We first show uniform convergence for a certain class of policy distributions (Lemma 15), and argue that each distribution $P$ is close to some distribution $\widetilde{P}$ from this class, in the sense that $V_{P,\pi,t}$ is close to $V_{\widetilde{P},\pi,t}$ and $\widehat{V}_{P,\pi,t}$ is close to $\widehat{V}_{\widetilde{P},\pi,t}$ (Lemma 16). Together, they imply the main uniform convergence result in Theorem 6.

For each positive integer $m$, let $\mathsf{Sparse}[m]$ be the set of distributions $\widetilde{P}$ over $\Pi$ that can be written as

(i.e., the average of $m$ delta functions) for some $\pi_{1},\dotsc,\pi_{m}\in\Pi$. In our analysis, we approximate an arbitrary distribution $P$ over $\Pi$ by a distribution $\widetilde{P}\in\mathsf{Sparse}[m]$ chosen randomly by independently drawing $\pi_{1},\dotsc,\pi_{m}\sim P$; we denote this process by $\widetilde{P}\sim P^{m}$.

Fix positive integers $(m_{1},m_{2},\dotsc)$. With probability at least $1-\delta$ over the random samples $(x_{1},x_{2},\dotsc)$ from $D_{X}$,

for all $\lambda>0$, all $t\geq 1$, all $\pi\in\Pi$, and all distributions $\widetilde{P}\in\mathsf{Sparse}[m_{t}]$.

We apply Bernstein’s inequality and union bounds over $\widetilde{P}\in\mathsf{Sparse}[m_{t}]$, $\pi\in\Pi$, and $t\geq 1$ so that with probability at least $1-\delta$,

all $t\geq 1$, all $\pi\in\Pi$, and all distributions $P\in\mathsf{Sparse}[m_{t}]$. The conclusion follows by solving the quadratic inequality for $V_{\widetilde{P},\pi,t}$ to get

and then applying the AM/GM inequality. ∎

Fix any $\gamma\in$, and any $x\in X$. For any distribution $P$ over $\Pi$ and any $\pi\in\Pi$, if

This implies that for all distributions $P$ over $\Pi$ and any $\pi\in\Pi$, there exists $\widetilde{P}\in\mathsf{Sparse}[m]$ such that for any $\lambda>0$,

where the third inequality follows from Jensen’s inequality, and the fourth inequality uses the AM/GM inequality in the denominator of the first term and the previous observations in the numerators. The final expression simplifies to the first desired displayed inequality by observing that $mz\exp(-mz/8)\leq 3$ for all $mz\geq 0$ (the maximum is achieved at $mz=8$). The second displayed inequality follows from the following facts:

Both inequalities follow from the first displayed bound of the lemma, by taking expectation with respect to the true (and empirical) distributions over $x$. The desired bound follows by adding the above two inequalities, which implies that the bound holds in expectation, and hence the existence of $\widetilde{P}$ for which the bound holds. ∎

(for some $\lambda\in(0,1/5)$ to be determined) and condition on the $\geq 1-\delta$ probability event from Lemma 15 that

for all $t\geq 2$, all $\widetilde{P}\in\mathsf{Sparse}[m_{t}]$, and all $\pi\in\Pi$. Using the definitions of $m_{t}$ and $\mu_{t}$, the second term is at most $(40/\lambda^{2})\cdot(1+1/\lambda)\cdot K$ for all $t\geq 16K\log(8KN/\delta)$: the key here is that for $t\geq 16K\log(8KN/\delta)$, we have $\mu_{t}=\sqrt{\log(Nt/\delta)/(Kt)}\leq 1/(2K)$ and therefore

Now fix $t\geq 16K\log(8KN/\delta)$, $\pi\in\Pi$, and a distribution $P$ over $\Pi$. Let $\widetilde{P}\in\mathsf{Sparse}[m_{t}]$ be the distribution guaranteed by Lemma 16 with $\gamma=\lambda$ satisfying

Substituting the previous bound for $V_{\widetilde{P},\pi,t}-(1+\lambda)\widehat{V}_{\widetilde{P},\pi,t}$ gives

This can be bounded as $(1+\epsilon)\cdot\widehat{V}_{P,\pi,t}+(7500/\epsilon^{3})\cdot K$ by setting $\lambda=\epsilon/5$. ∎

Appendix D Analysis of RandomizedUCB

First, we define the following constants.

$\epsilon\in(0,1)$ is a fixed constant, and

$\rho\doteq\frac{7500}{\epsilon^{3}}$ is the factor that appears in the bound from Theorem 6.

$\theta\doteq(\rho+1)/(1-(1+\epsilon)/2)=\frac{2}{1-\epsilon}\left(1+\frac{7500}{\epsilon^{3}}\right)\geq 5$ is a constant central to Lemma 21, which bounds the variance of the optimal policy’s estimated rewards.

It can be checked that $\mu_{t}$ is non-increasing. We define the following time indices:

$t_{0}$ is the first round $t$ in which $\mu_{t}=\sqrt{C_{t}/(2Kt)}$. Note that $8K\leq t_{0}\leq 8K\log(NK/\delta)$.

$t_{1}:=\lceil 16K\log(8KN/\delta)\rceil$ is the round given by Theorem 6 such that, with probability at least $1-\delta$,

for all $\pi\in\Pi$ and all $t\geq t_{1}$, where $W_{P,\mu}(x,\cdot)$ is the distribution over $A$ given by

The following lemma shows the effect of allowing slack in the optimization constraints.

If $P$ satisfies the constraints of the optimization problem (4.1) with slack $K$ for each distribution $Q$ over $\Pi$, i.e.,

Let $b\doteq\max\left\{4K,\frac{(t-1)\Delta_{t-1}(\pi)^{2}}{180C_{t-1}}\right\}$. Note that $\frac{b}{4}\geq K$. Hence $b+K\leq\frac{5b}{4}$ which gives the stated bound. ∎

Note that the allowance of slack $K$ is somewhat arbitrary; any $O(K)$ slack is tolerable provided that other constants are adjusted appropriately.

For any policy $\pi\in\Pi$, define, for $1\leq t\leq t_{0}$,

The $\bar{V}_{t}(\pi)$ bounds the variances of the terms in $\eta_{t}(\pi)$.

Assume the bound in (D.1) holds for all $\pi\in\Pi$ and $t\geq t_{1}$. For all $\pi\in\Pi$:

For the first claim, note that if $t<t_{0}$, then $\bar{V}_{t}(\pi)=K$, and if $t_{0}\leq t<t_{1}$, then

so $W_{t}^{\prime}(a)\geq\mu_{t}\geq 1/(4K)$.

For the second claim, pick any $t>t_{1}$, and note that by definition of $t_{1}$, for any $\pi\in\Pi$ we have

The stated bound on $\bar{V}_{t}(\pi)$ now follows from its definition. ∎

The following lemma gives a deviation bound for $\eta_{t}(\pi)$ in terms of these quantities.

Pick any $\delta\in(0,1)$. With probability at least $1-\delta$, for all pairs $\pi,\pi^{\prime}\in\Pi$ and $t\geq t_{0}$, we have

Fix any $t\geq t_{0}$ and $\pi,\pi^{\prime}\in\Pi$. Let $\delta_{t}:=\exp(-C_{t})$. Pick any $\tau\leq t$. Let

so $\eta_{t}(\pi)=t^{-1}\sum_{\tau=1}^{t}Z_{\tau}(\pi)$. It is easy to see that

Now, note that since $t\geq t_{0}$, $\mu_{t}=\sqrt{\frac{C_{t}}{2Kt}}$, so that $t=\frac{C_{t}}{2K\mu_{t}^{2}}$. Further, both $\bar{V}_{\max,t}(\pi)$ and $\bar{V}_{\max,t}(\pi^{\prime})$ are at least $K$. Using these bounds we get

for all $\tau\leq t$, since the $\mu_{\tau}$’s are non-increasing. Therefore, by Freedman’s inequality (Theorem 13), we have

The conclusion follows by taking a union bound over $t_{0}<t\leq T$ and all pairs $\pi,\pi^{\prime}\in\Pi$. ∎

D.3 Variance Analysis

We define the following condition, which will be assumed by most of the subsequent lemmas in this section.

The deviation bound (D.1) holds for all $\pi\in\Pi$ and $t\geq t_{1}$, and the deviation bound (D.2) holds for all pairs $\pi,\pi^{\prime}\in\Pi$ and $t\geq t_{0}$.

The next two lemmas relate the $\bar{V}_{t}(\pi)$ to the $\Delta_{t}(\pi)$.

Assume Condition 1. For any $t\geq t_{1}$ and $\pi\in\Pi$, if $\bar{V}_{t}(\pi)>\theta K$, then

By Lemma 18, the fact $\bar{V}_{t}(\pi)>\theta K$ implies that

Since $\bar{V}_{t}(\pi)>\theta K\geq 5K$, Lemma 17 implies that in order for $P_{t}$ to satisfy the optimization constraint in (4.1) corresponding to $\pi$ (with slack $\leq K$), it must be the case that

Assume Condition 1. For all $t\geq 1$, $\bar{V}_{\max,t}(\pi_{\max})\leq\theta K$ and $\bar{V}_{\max,t}(\pi_{t})\leq\theta K$.

By induction on $t$. The claim for all $t\leq t_{1}$ follows from Lemma 18. So take $t>t_{1}$, and assume as the (strong) inductive hypothesis that $\bar{V}_{\max,\tau}(\pi_{\max})\leq\theta K$ and $\bar{V}_{\max,\tau}(\pi_{\tau})\leq\theta K$ for $\tau\in\{1,\dotsc,t-1\}$. Suppose for sake of contradiction that $\bar{V}_{t}(\pi_{\max})>\theta K$. By Lemma 20,

However, by the deviation bounds, we have

The second inequality follows from our assumption and the induction hypothesis:

Since $\Delta_{D}(\pi_{t-1})\geq 0$, we have a contradiction, so it must be that $\bar{V}_{t}(\pi_{\max})\leq\theta K$. This proves that $\bar{V}_{\max,t}(\pi_{\max})\leq\theta K$.

It remains to show that $\bar{V}_{\max,t}(\pi_{t})\leq\theta K$. So suppose for sake of contradiction that the inequality fails, and let $t_{1}<\tau\leq t$ be any round for which $\bar{V}_{\tau}(\pi_{t})=\bar{V}_{\max,t}(\pi_{t})>\theta K$. By Lemma 20,

The parenthesized terms can be bounded using the deviation bounds, so we have

where the second inequality follows from the following facts: {enumerate*}

By induction hypothesis, we have $\bar{V}_{\max,\tau-1}(\pi_{\tau-1}),\bar{V}_{\max,\tau-1}(\pi_{\max}),\bar{V}_{\max,t}(\pi_{\max})\leq\theta K$, and $\bar{V}_{\tau}(\pi_{t})>\theta K$,

$\bar{V}_{\tau}(\pi_{t})\geq\bar{V}_{\max,t}(\pi_{t})$, and

since $\tau$ is a round that achieves $\bar{V}_{\max,t}(\pi_{t})$, we have $\bar{V}_{\tau}(\pi_{t})\geq\bar{V}_{\tau-1}(\pi_{t})$. This contradicts the inequality in (D.3), so it must be that $\bar{V}_{\max,t}(\pi_{t})\leq\theta K$. ∎

Immediate from Lemma 21 and the deviation bounds from (D.2). ∎

The following lemma shows that if a policy $\pi$ has large $\Delta_{\tau}(\pi)$ in some round $\tau$, then $\Delta_{t}(\pi)$ remains large in later rounds $t>\tau$.

Assume Condition 1. Pick any $\pi\in\Pi$ and $t\geq t_{1}$. If $\bar{V}_{\max,t}(\pi)>\theta K$, then

Let $\tau\leq t$ be any round in which $\bar{V}_{\tau}(\pi)=\bar{V}_{\max,t}(\pi)>\theta K$. We have

where the second inequality follows from Lemma 20 and the deviation bounds, and the third inequality follows from Lemma 21 and the facts that $\bar{V}_{\tau}(\pi)=\bar{V}_{\max,t}(\pi)>\theta K\geq\bar{V}_{\max,t}(\pi_{\max}),\bar{V}_{\max,\tau-1}(\pi_{\tau-1})$, and $\bar{V}_{\max,t}(\pi)\geq\bar{V}_{\max,\tau-1}(\pi)$. ∎

D.4 Regret Analysis

We now bound the value of the optimization problem (4.1), which then leads to our regret bound. The next lemma shows the existence of a feasible solution with a certain structure based on the non-uniform constraints. Recall from Section 5, that solving the optimization problem $\mathcal{A}$, i.e. constraints (5.1, 5.2, 5.3), for the smallest feasible value of $s$ is equivalent to solving the RUCB optimization problem (4.1). Recall that $\beta_{t}=\frac{t-1}{180C_{t-1}}$.

In particular, the value of the optimization problem (4.1), $\operatorname{OPT}_{t}$, is bounded by $8\sqrt{\frac{K}{\beta_{t}}}\leq 110\sqrt{\frac{KC_{t-1}}{t-1}}$.

Define the sets $\{\mathcal{C}_{i}:\ i=1,2,\ldots\}$ such that

where $\kappa=\sqrt{\frac{K}{\beta_{t}}}$. Note that since $\Delta_{t-1}(Z)$ is a linear function of $Z$, each $\mathcal{C}_{i}$ is a closed, convex, compact set. Also, define $\mathcal{C}_{0}=\{Z\in\mathcal{C}:\ \Delta_{t-1}(Z)\leq 4\kappa\}$. This is also a closed, convex, compact set. Note that $\mathcal{C}=\bigcup_{i=0}^{\infty}\mathcal{C}_{i}$.

Let $I=\{i:\ \mathcal{C}_{i}\neq\emptyset\}$.For $i\in I\setminus\{0\}$, define $w_{i}=4^{-i}$, and let $w_{0}=1-\sum_{i\in I\setminus\{0\}}w_{i}$. Note that $w_{0}\geq 2/3$.

By Lemma 1, for each $i\in I$, there is a point $W_{i}\in\mathcal{C}_{i}$ such that for all $Z\in\mathcal{C}_{i}$, we have

Here we use the fact that $K\mu_{t}\leq 1/2$ to upper bound $\frac{K}{1-K\mu_{t}}$ by $2K$. Now consider the point $W=\sum_{i\in I}w_{i}W_{i}$. Since $\mathcal{C}$ is convex, $W\in\mathcal{C}$.

Now fix any $i\in I$. For any $(x,a)$, we have $W^{\prime}(x,a)\geq w_{i}W^{\prime}_{i}(x,a)$, so that for all $Z\in\mathcal{C}_{i}$, we have

Finally, since for all $i\in I$, we have $w_{i}\leq 4^{-i}$ and $\Delta_{t-1}(W_{i})\leq 2^{i+2}\kappa$, we get

The value of the optimization problem (4.1) can be related to the expected instantaneous regret of policy drawn randomly from the distribution $P_{t}$.

Fix any $\pi\in\Pi$ and $t>t_{1}$. By the deviation bounds, we have

If $\bar{V}_{\max,t-1}(\pi)\leq\theta K$, then we have

where $\operatorname{OPT}_{t}$ is the value of the optimization problem (4.1). The conclusion follows from Lemma 24. ∎

We can now finally prove the main regret bound for RUCB.

The regret through the first $t_{1}$ rounds is trivially bounded by $t_{1}$. In the event that Condition 1 holds, we have for all $t\geq t_{1}$,

where the last inequality follows from Lemma 25. Summing the bound from $t=t_{1}+1,\dotsc,T$ gives

By Azuma’s inequality, the probability that $\sum_{t=1}^{T}r_{t}(a_{t})$ deviates from its mean by more than $O(\sqrt{T\log(1/\delta)})$ is at most $\delta$. Finally, the probability that Condition 1 does not hold is at most $2\delta$ by Lemma 19, Theorem 6, and a union bound. The conclusion follows by a final union bound. ∎

Appendix E Details of Oracle-based Algorithm

In order to use the ellipsoid algorithm, we need to relax the program a little bit in order to ensure that the feasible region has a non-negligible volume. To do this, we need to obtain some perturbation bounds for the constraints of $\mathcal{A}$. The following lemma gives such bounds. For any $\delta>0$, we define $\mathcal{C}_{\delta}$ to be the set of all points within a distance of $\delta$ from $\mathcal{C}$.

Let $\delta\leq b/4$ be a parameter. Let $U,W\in\mathcal{C}_{2\delta}$ be points such that $\|U-W\|\leq\delta$. Then we have

where $\epsilon=\frac{8\delta}{\mu_{t}^{2}}$ and $\gamma=\frac{\delta}{\mu_{t}}$.

Next, for any $Z\in\mathcal{C}_{1}$, we have

In the last inequality, we use the Cauchy-Schwarz inequality, and use the following facts (here, $Z(x,\cdot)$ denotes the vector $\langle Z(x,a)\rangle_{a}$, etc.): {enumerate*}

$\|Z(x,\cdot)\|\leq 2$ since $Z\in\mathcal{C}_{1}$,

$\|U^{\prime}(x,\cdot)-W^{\prime}(x,\cdot)\|\leq\|U(x,\cdot)-W(x,\cdot)\|\leq\delta$, and

$U^{\prime}(x,a)\geq(1-bK)\cdot(-2\delta)+b\geq b/2$, for $\delta\leq b/4$, and similarly $W^{\prime}(x,a)\geq b/2$. This implies (E.2). ∎

where $\epsilon$ and $\gamma$ are as defined in Lemma 26. Call this relaxed program $\mathcal{A}^{\prime}$.

We apply the ellipsoid method to $\mathcal{A}^{\prime}$ rather than $\mathcal{A}$. Recall the requirements of Lemma 8: we need an enclosing ball of bounded radius for the feasible region, and the radius of an enclosed ball in the feasible region. The following lemma gives this.

The feasible region for $\mathcal{A}^{\prime}$ is contained in $B(0,\sqrt{t}+\delta)$, and if $\mathcal{A}$ is feasible, then it contains a ball of radius $\delta$.

Note that for any $W\in\mathcal{C}_{\delta}$, we have $\|W\|\leq\sqrt{t}+\delta$, so the feasible region lies in $B(0,\sqrt{t}+\delta)$.

Next, if $\mathcal{A}$ is feasible, let $W^{\star}\in\mathcal{C}$ be any feasible solution to $\mathcal{A}$. Consider the ball $B(W^{\star},\delta)$. Let $U$ be any point in $B(W^{\star},\delta)$. Clearly $U\in\mathcal{C}_{\delta}$. By Lemma 26, assuming $\delta\leq 1/2$, we have for all $Z\in\mathcal{C}_{2\delta}$,

Thus, $U$ is feasible for $\mathcal{A}^{\prime}$, and hence the entire ball $B(W^{\star},\delta)$ is feasible for $\mathcal{A}^{\prime}$. ∎

We now give the construction of a separation oracle for the feasible region of $\mathcal{A}^{\prime}$ by checking for violations of the constraints. In the following, we use the word “iteration” to indicate one step of either the ellipsoid algorithm or the perceptron algorithm. Each such iteration involves one call to $\mathcal{AMO}$, and additional $O(t^{2}K^{2})$ processing time.

The harder constraints are (E.4) and (E.5). Recall that Lemma 9 shows that that $\mathcal{AMO}$ allows us to do linear optimization over $\mathcal{C}$ efficiently. This immediately gives us the following useful corollary:

This follows directly from the following fact:

Now we show how to use $\mathcal{AMO}$ to check for constraint (E.4):

Suppose we are given a point $W$. Then in $O(\frac{t}{\delta^{2}})$ iterations, if $W\notin\mathcal{C}_{2\delta}$, we can construct a hyperplane separating $W$ from $\mathcal{C}_{\delta}$. Otherwise, we declare correctly that $W\in\mathcal{C}_{2\delta}$. In the latter case, we can find an explicit distribution $P$ over policies in $\Pi$ such that $W_{P}$ satisfies $\|W_{P}-W\|\leq 2\delta$.

We run the perceptron algorithm with the origin at $W$ and all points in $\mathcal{C}_{\delta}$ being positive examples. The goal of the perceptron algorithm then is to find a hyperplane going through $W$ that puts all of $\mathcal{C}_{\delta}$ (strictly) on one side. In each iteration of the perceptron algorithm, we have a weight vector $w$ that is the normal to a candidate hyperplane, and we need to find a point $Z\in\mathcal{C}_{\delta}$ such that $w\cdot(Z-W)\leq 0$ (note that we have shifted the origin to $W$). To do this, we use $\mathcal{AMO}$ as in Lemma 9 to find $Z^{\star}=\arg\max_{Z\in\mathcal{C}_{\delta}}-w\cdot Z$. If $w\cdot(Z^{\star}-W)\leq 0$, we use $Z^{\star}$ to update $w$ using the perceptron update rule, $w\leftarrow w+(Z^{\star}-W)$. Otherwise, we have $w\cdot(Z-W)>0$ for all $W\in\mathcal{C}_{\delta}$, and hence we have found our separating hyperplane.

Now suppose that $W\notin\mathcal{C}_{2\delta}$, i.e. the distance of $W$ from $\mathcal{C}_{\delta}$ is more than $\delta$. Since $\|Z-W\|\leq 2\sqrt{t}+3\delta=O(\sqrt{t})$ for all $W\in\mathcal{C}_{\delta}$ (assuming $\delta=O(\sqrt{t})$), the perceptron convergence guarantee implies that in $O(\frac{t}{\delta^{2}})$ iterations we find a separating hyperplane.

If in $k=O(\frac{t}{\delta^{2}})$ iterations we haven’t found a separating hyperplane, then $W\in\mathcal{C}_{2\delta}$. In fact the perceptron algorithm gives a stronger guarantee: if the $k$ policies found in the run of the perceptron algorithm are $\pi_{1},\pi_{2},\ldots,\pi_{k}\in\Pi$, then $W$ is within a distance of $2\delta$ from their convex hull, $\mathcal{C}^{\prime}=\text{conv}(\pi_{1},\pi_{2},\ldots,\pi_{k})$. This is because a run of the perceptron algorithm on $\mathcal{C}^{\prime}_{2\delta}$ would be identical to that on $\mathcal{C}_{2\delta}$ for $k$ steps. We can then compute the explicit distribution over policies $P$ by computing the Euclidean projection of $W$ on $\mathcal{C}^{\prime}$ in $\text{poly}(k)$ time using a convex quadratic program:

Solving this quadratic program, we get a distribution $P$ over the policies $\{\pi_{1},\pi_{2},\ldots,\pi_{k}\}$ such that $\|W_{P}-W\|\leq 2\delta$. ∎