Experimental Design for Regret Minimization in Linear Bandits

INTRODUCTION

Existing regret minimization algorithms for linear bandits suffer from several important shortcomings. First, they typically rely on naive union bounds, which yield regret guarantees scaling as either $\mathcal{O}(d\sqrt{T})$ or $\mathcal{O}(\sqrt{d\log(|\mathcal{X}|)T})$. Such union bounds ignore the geometry present in the problem and, as such, can be very wasteful. As the union bound often appears in the confidence interval within the algorithm, this is not simply an analysis issue—it can also affect real performance. Second, in the moderate, non-asymptotic time regime, existing algorithms tend to rely on the principle of optimism—pulling only the arms they believe may be optimal. Algorithms relying on this principle are very myopic, foregoing initial exploration which could lead to better long-term reward and instead focusing on obtaining short-term reward, leading to suboptimal long-term performance. This is a well-known effect in the bandit setting but, as we show, is also present in the semi-bandit setting.

In this paper, we develop an algorithm overcoming both of these shortcomings. Rather than employing a naive union bound, we appeal to tools from empirical process theory for controlling the suprema of a Gaussian process, allowing us to obtain confidence bounds that are geometry-dependent and potentially much tighter. In addition, our algorithm relies on careful planning to balance the exploration-exploitation tradeoff, taking into account both the potential information gain as well as the reward obtained when pulling an arm. This planning allows us to collect sufficient information for good long-term performance without incurring too much initial regret and, to the best of our knowledge, is the first planning-based algorithm in the linear bandit setting that provides finite-time guarantees.

We emphasize that we are interested in the non-asymptotic regime and aim to optimize the whole regret bound, including lower-order terms. While several recent works achieve instance-optimal regret, they suffer from loose lower-order terms which dominate the regret for small to moderate $T$. Our results aim to minimize such terms through employing tighter union bounds. We summarize our contributions:

We develop a single, general algorithm that achieves a state-of-the-art finite-time regret bound in stochastic linear bandits, in combinatorial bandits with bandit feedback, and in combinatorial bandits with semi-bandit feedback. In addition, our framework is general enough to extend to settings as diverse as partial monitoring and graph bandits.

We show that in the combinatorial semi-bandit regime, our algorithm is computationally efficient, relying only on calls to a linear maximization oracle, and state-of-the-art, yielding a significant improvement on existing works in the non-asymptotic time horizon regime.

We give the first example for combinatorial bandits with semi-bandit feedback that shows that optimistic strategies such as UCB and Thompson Sampling can do arbitrarily worse than the asymptotic lower bound, and show that our algorithm improves on optimism in this setting by an arbitrarily large factor.

As a corollary, we obtain the first computationally efficient algorithm for pure exploration in combinatorial bandits with semi-bandit feedback, and achieve a state-of-the-art sample complexity.

This work can be seen as obtaining problem-dependent minimax bounds—minimax bounds that depend on the arm set but hold for all values of the reward vector—and are similar in spirit to the bounds on regret minimization in MDPs given by Zanette and Brunskill (2019). For some favorable arm sets $\mathcal{X}$, our bounds are tighter than prior $\mathcal{X}$-independent minimax bounds by large dimension factors. To the best of our knowledge, we are the first to obtain such geometry-dependent minimax bounds for linear bandits.

PRELIMINARIES

Throughout, we assume that $\theta_{*}\in^{d}$. We consider two observation models: semi-bandit feedback and bandit feedback. In the bandit feedback setting, at every timestep we observe:

where $\eta_{t}\sim\mathcal{N}(0,1)$. In the semi-bandit feedback setting, we assume that our bandit instance is combinatorial, $\mathcal{X}\subseteq\{0,1\}^{d}$, and at every timestep we observe:

where $\eta_{t}\sim\mathcal{N}(0,I)$. Note that, while we assume Gaussian noise for simplicity, all our results will hold with sub-Gaussian noise (Katz-Samuels et al., 2020).

In the bandit setting, after $T$ observations, our estimate of $\theta_{*}$ will be the standard least squares estimate:

In the semi-bandit setting, we will estimate $\theta_{*}$ coordinate-wise, forming the estimate:

where $T_{i}$ is the number of times $x_{t,i}=1$. We denote:

In the combinatorial setting, $|\mathcal{X}|$ can often be exponentially large in the dimension, making computational efficiency non-trivial since $\mathcal{X}$ cannot be efficiently enumerated. As such, much of the literature on combinatorial bandits has focused on obtaining algorithms that rely only on an argmax oracle:

Efficient argmax oracles are available in many settings, for instance finding the minimum weighted matching in a bipartite graph and finding the shortest path in a directed acyclic graph.

MOTIVATING EXAMPLES

Before presenting our algorithm and main results, we present several examples that motivate the necessity of planning and the wastefulness of naive union bounds, and illustrate how our algorithm is able to make improvements in both these aspects.

and Algorithm 1 has expected regret bounded as, for any $T$:

Thus, treating $\epsilon$ as a constant, the asymptotic regret of the generic optimistic algorithm is loose by a square root dimension factor, and Algorithm 1 in the current paper improves over optimism by an arbitrarily large factor. As it also relies on the principle of optimism, albeit in a randomized fashion, Thompson Sampling will be suboptimal by this same factor on this instance. A similar instance can also be found in the bandit feedback setting. The improvement in Algorithm 1 is due to its ability to pull informative but suboptimal arms if the information gain outweighs the regret incurred, reducing the cumulative regret. Optimistic algorithms, in contrast, will only pull arms they believe may be optimal, and so do not effectively take into account the information gain which, in some cases, causes them to be very suboptimal.

To illustrate the improvement we gain by applying a less naive union bound, we will consider the following combinatorial class:

while algorithms employing naive union bounds will achieve regret bounds scaling at best as:

In the appendix we discuss in more detail how the regret scales for specific algorithms in this setting. The regret bound we present for our algorithm in Proposition 2 is in fact state-of-the-art—all other existing algorithms will incur the larger dimension dependence.

EXPERIMENTAL DESIGN FOR REGRET MINIMIZATION

Intuitively, $\bar{\gamma}(A_{\mathfrak{f}})$ is the largest Gaussian width of any subset of $\mathcal{X}$ formed by taking all $x\in\mathcal{X}$ with gap bounded by $\epsilon$. The following results are helpful in giving some sense of the scaling of $\bar{\gamma}(A_{\mathfrak{f}})$.

Note that these upper bounds are often loose. The following results shows that, in some cases, we pay a $d$ instead of $dk$.

The Gaussian width is critical in avoiding wasteful union bounds, allowing instead for geometry-dependent confidence intervals. The following confidence interval will form a key piece in our analysis.

2 Algorithm Overview

We next present our algorithm, RegretMED, in Algorithm 1. Inspired by several recent algorithms achieving asymptotically optimal regret (Lattimore and Szepesvari, 2017), at every epoch our algorithm finds a new allocation by solving an experimental design problem (2). This minimizes an upper bound on the regret incurred in the epoch while ensuring the allocation produced will explore enough to improve the estimates of the gaps for each arm, thereby balancing exploration and exploitation and allowing us to obtain a tight bound on finite-time regret. We apply the TIS inequality to bound the estimation error of our gaps, which motivates the constraint in (2). Critically, this yields a regret bound scaling with the Gaussian width of the action set.

Key Theoretical Tools: We briefly describe the key theoretical tools employed by RegretMED. First, we note that an experimental design based algorithm is novel in the setting of regret minimization. As we have shown, this approach allows us to perform properly on challenging instances by explicitly balancing the information gain and reward, while also yielding a computationally feasible solution in the semi-bandit regime. Our second innovation is the use of the TIS inequality to obtain tight concentration bounds. While we are not the first to utilize this in the linear bandit setting (Katz-Samuels et al., 2020), it previously was only utilized in the best arm identification setting, and our work therefore shows how it can be applied in the regret minimization setting as well. The use of the TIS inequality yields two important improvements over more naive union bounds. First, it provides tighter confidence intervals in the non-asymptotic time regime and therefore yields improved regret bounds. Second, as we will see, it allows us to write the constraint for our experiment design problem (2) in a form that is linear in the the decision variable. This allows us to reduce solving the optimization to calls of a linear maximization oracle, and is a key piece in showing our algorithm is computationally efficient.

3 Main Regret Bound

We now state our main regret bound. Define

for absolute constants $c_{1}$ and $c_{2}$.

4 Computationally Efficient Algorithm

While Algorithm 1 can be run in settings where $\mathcal{X}$ is enumerable, it becomes computationally infeasible for very large $\mathcal{X}$, as (2) cannot be solved via a linear maximization oracle. In place of (2), consider instead solving:

As we show in Theorem 4, we can solve this problem with a computationally feasible algorithm in the semi-bandit feedback regime. Running this modified version of Algorithm 1, we obtain the following regret bound.

and the minimax regret will be bounded as:

In the semi-bandit setting, we can apply Theorem 4 to compute an approximate solution to (3) in polynomial time, as described below. See Section 6 and Table 1 for an in-depth discussion of how our result compares to existing works.

5 Pure Exploration with Semi-Bandit Feedback

Although our algorithm is designed to minimize regret, a slight modification gives a computationally efficient algorithm for best arm identification in the semi-bandit feedback setting. In particular, instead of (2) consider solving:

Let $\delta\in(0,1)$. Run Algorithm 1 but replace (2) with (4) and omit the break on line 7. Invoke Theorem 4 to efficiently find an approximate solution to (4). Then, with probability $1-\delta$, the algorithm will terminate after collecting at most:

samples and we will have $\hat{x}=x_{*}$.

We state and prove a lower bound for this problem in the appendix, Theorem 6, which shows that this sample complexity is near-optimal. To the best of our knowledge, this is the first general, computationally efficient, and near optimal algorithm for pure exploration with semi-bandit feedback.

6 Optimization

The following result shows that there exists a polynomial-time algorithm that finds an approximately optimal solution, i.e., it is within a constant approximation factor of the optimal solution.

Let opt be the optimal value of (5). There exists an Algorithm that returns $(\bar{\tau},\bar{\lambda})$ such that $\bar{\lambda}\in\triangle_{\mathcal{X}}$, $\bar{\tau}\leq 2T$, and, with probability at least $1-\delta-\frac{1}{2^{d}}$:

Furthermore, the number linear maximization oracle calls is polynomial in $(d,\beta,T,\log(1/\delta))$.

which can be solved using only linear maximization oracle calls via the binary search procedure from Katz-Samuels et al. (2020). The proof of this result and full algorithm is given in Section D.

We prove this result and state how this rounded distribution can be computed in Appendix E.

EXPERIMENTAL RESULTS

We next present experimental results for RegretMED in both the semi-bandit and bandit feedback settings. Every point in each plot is the average of 50 trials. The error bars indicate one standard error.

We illustrate the result in Figures 3 and 3 for different values of $d$. In both cases, RegretMED yields a significant improvement over CTS-Gaussian and CombUCB1. Note that $|\mathcal{X}|$ is growing exponentially in $d$ and for $d=25$ we have $|\mathcal{X}|\approx 3\cdot 10^{7}$. In all experiments we set $\delta=1/T$.

As Figure 3 illustrates, the performance of RegretMED is almost unaffected by the choice of $\epsilon$, while the performance of both TS and LinUCB degrades significantly. Optimistic algorithms are suboptimal on this instance as they do not pull the suboptimal but informative arm, $e_{2}$. Our results indicate that RegretMED is able to overcome this difficulty by continuing to pull $e_{2}$ even when it has been determined suboptimal, recognizing the information gain outweighs the regret incurred.

DISCUSSION AND PRIOR ART

While prior algorithms have tended to be based on the principle of optimism (Kveton et al., 2015; Combes et al., 2015; Degenne and Perchet, 2016; Wang and Chen, 2018; Perrault et al., 2020a), we have shown that optimistic strategies are asymptotically suboptimal (see Proposition 1), motivating our planning-based algorithm. Additional work includes (Chen et al., 2016; Talebi and Proutiere, 2016; Perrault et al., 2020b). We summarize our results in Table 1.

Asymptotically Optimal Regret in Linear Bandits: Another related line of work focuses on asymptotic performance (Lattimore and Szepesvari, 2017; Combes et al., 2017; Hao et al., 2020; Degenne et al., 2020; Cuvelier et al., 2020). In the bandit setting asymptotic lower bounds have been shown to scale as:

While we do not claim RegretMED is asymptotically optimal, we note that the optimization we are solving (2) closely resembles the above optimization. Indeed, at the final epoch of RegretMED, our estimates of the gaps will be sufficiently accurate so as to ensure we are playing approximately the asymptotically optimal distribution. Furthermore, as Proposition 1 and Figure 3 show, RegretMED appears to be playing the asymptotically optimal strategy in situations where optimism fails. We leave a rigorous proof of the asymptotic qualities of RegretMED to future work.

Concurrent to this work, several works appeared which simultaneously achieve asymptotically optimal and sub-$\mathcal{O}(\sqrt{T})$ regret (Tirinzoni et al., 2020; Kirschner et al., 2020b). In particular, Tirinzoni et al. (2020) achieves instance-optimal $\log T$ regret in finite time. We remark that their regret bound contains large additive terms which will dominate the leading $\log T$ term for moderate time horizons. Our primary concern is in this non-asymptotic regime, where the union bound applied is still significant, and we therefore see our work as complementary, addressing issues they do not address.

Asymptotically optimal regret has been relatively unexplored in the semi-bandit setting. Following the acceptance of this work, a very recent work (Cuvelier et al., 2021) proposed a computationally efficient asymptotically optimal algorithm in the semi-bandit setting, which was the first of its kind. As with the bandit setting, our concern is with the non-asymptotic time regime, so this result is complementary to ours.

Stochastic Multi-Armed Bandits with Side Observations: In the stochastic multi-armed bandits with side observations problem, the agent is given a graph of $n$ nodes where each node is associated with an independent distribution. When the agent pulls a node $i$, she observes and suffers its stochastic reward and she also observes the stochastic reward of any node with an edge connected to node $i$. Caron et al. (2012) proposed a UCB-like algorithm and Buccapatnam et al. (2014) used a linear programming solution to show that the regret scales with the minimum dominating set.

Pure Exploration in Multi-Armed Bandits: There has not been a significant amount of previous work on pure exploration combinatorial bandits with semi-bandit feedback. Chen et al. (2020) provide a general framework that subsumes combinatorial bandits with semi-bandit feedback but their algorithm is non-adaptive and suboptimal. Several special cases of pure exploration combinatorial bandits with semi-bandit feedback have been studied. Best arm identification (where $\mathcal{X}=\{e_{1},\ldots,e_{d}\}$) has received much attention (Even-Dar et al., 2006; Jamieson et al., 2014; Karnin et al., 2013; Kaufmann et al., 2016; Chen and Li, 2015). The setting in Jun et al. (2016) subsumes the top-K problem, but their approach does not generalize to other combinatorial problem instances. Concurrent to this work, Jourdan et al. (2021) derived an asymptotically optimal best arm identification algorithm for the semi-bandit setting. We note that our result focuses on optimality in the finite-time regime, so our results our complementary.

Our algorithmic technique bridging empirical process theory and experimental design is inspired by the work on pure exploration combinatorial bandits in Katz-Samuels et al. (2020). The semi-bandit feedback setting in the present paper poses a new and non-trivial computational challenge since, unlike in Katz-Samuels et al. (2020), the number of variables in the optimization is potentially exponential in the dimension.

Acknowledgements

AW is supported by an NSF GFRP Fellowship DGE-1762114. JKS is supported by an Amazon Research Award. The work of KJ is supported in part by grants NSF RI 1907907 and NSF CCF 2007036.

References

Appendix A Action Elimination with Gaussian Width

We first state an algorithm inspired by Lattimore and Szepesvári and prove a regret bound. This algorithm, while naive, incorporates the TIS inequality to obtain regret scaling with the Gaussian width. Furthermore, the analysis is simple and helps aid in the intuition of the proof of our main theorems.

and $\sum_{x\in\mathcal{X}}\kappa_{x}=N$, so long as $N\geq q(\zeta)$. From Katz-Samuels et al. and Allen-Zhu et al. , we know such a rounding procedure exists and can be computed efficiently, and that it suffices to choose $q(\zeta)=O(d/\zeta^{2})$.

where $\mathcal{X}_{\epsilon}:=\{x\in\mathcal{X}\ :\ \Delta_{x}\leq\epsilon\}$.

with probability at least $1-\delta$ and minimax regret as:

with probability at least $1-\delta$. Here $c_{1},c_{2}$ are absolute constants.

We can now follow the same argument as Lemma 12 of Katz-Samuels et al. . Take $\mathcal{Y}\subseteq\mathcal{X}_{\epsilon}$ for some $\epsilon$ and let $\lambda_{1}\in\triangle_{\mathcal{Y}}$ be the distribution that minimizes:

and $\lambda_{2}\in\triangle_{\mathcal{Y}}$ the distribution that minimizes:

Let $\lambda=\frac{1}{2}(\lambda_{1}+\lambda_{2})$. Then we will have that:

where the last inequality holds by Kiefer-Wolfowitz and Proposition 9. Also:

Optimizing this over $\nu$ gives the final regret of:

and choosing $\nu=0$ gives the absolute regret bound. ∎

Appendix B Regret Bound Proofs

Let $\delta_{k}=\delta/(2k^{3})$ and define the events:

Proposition 6 gives that with probability at least $1-\delta/k^{3}$:

Estimation error: Henceforth we assume $\mathcal{E}$ holds. We proceed by induction to show that the gaps are always well-estimated. First we prove the base case. Let $k=1$ and consider any $x\in\mathcal{X}$. Then:

where $(a)$ follows by Proposition 7.5.2 of Vershynin and $(b)$ follows since $\tau_{1}$ is a feasible solution to (3).

For the inductive step, assume that, for all $x\in\mathcal{S}_{k}$:

Consider round $k+1$ and take $x\in\mathcal{S}_{k+1}^{c}$. There then exists some $k^{\prime}\leq k$ such that $x\in\mathcal{S}_{k^{\prime}}\backslash\mathcal{S}_{k^{\prime}+1}$. Then:

where $(a)$ follows by Proposition 7.5.2 of Vershynin , $(b)$ follows since $\Delta_{x}\geq\epsilon_{k+1}$ by virtue of the fact that $x\in\mathcal{S}_{k+1}^{c}$, so $\Delta_{x}\geq(\epsilon_{k+1}+\Delta_{x})/2$, $(c)$ follows since $\Delta_{x}\in[\epsilon_{k^{\prime}+1},\epsilon_{k^{\prime}}]$ and for any $z\in\mathcal{S}_{k^{\prime}}$, we will have theta $\Delta_{z}\leq\epsilon_{k^{\prime}}$, so $\epsilon_{k+1}+\Delta_{x}\geq\epsilon_{k+1}+\epsilon_{k^{\prime}+1}\geq\epsilon_{k+1}+\Delta_{z}/2$, $(d)$ holds by the inductive hypothesis and Lemma 1 of Katz-Samuels et al. and taking $\hat{\Delta}_{z}$ to be the estimate of $\Delta_{z}$ at round $k+1$, and $(e)$ holds since $\tau_{k+1}$ is a feasible solution to (3). We can perform a similar calculation to get the same thing for $x\in\mathcal{S}_{k+1}$, allowing us to conclude that, for all $x\in\mathcal{S}_{k+1}$:

Bounding the Round Regret: From the previous section, we know that on the good event all our gaps will be well-estimated. From (6), it follows that the constraint in (3) is tighter than the following constraint:

so any $\tau$ satisfying this inequality is also a feasible solution to (3).

where $(a)$ follows since we will always have:

where $(a)$ uses the fact that for all $x\in\mathcal{S}_{k}\backslash\mathcal{S}_{k+1}$, $\Delta_{x}\in[\epsilon_{k+1},\epsilon_{k}]$, and the last inequality follows as above. We therefore have that:

The first term can be bounded by the regret bounded given in Lemma 2:

is the only non-negative solution. It follows then that:

Finally, by Theorem 4 we can choose $\nu=4$, $\zeta=2$, and we will be able to compute the solution efficiently. ∎

The proof of this result is very similar to the proof of Theorem 2 but we include the points where it differs for the sake of completeness. Unless otherwise noted, all notation is defined as in the proof of Theorem 2.

Estimation error: Henceforth we assume $\mathcal{E}$ holds. We proceed by induction to show that the gaps are always well-estimated. First we prove the base case. Let $k=1$ and consider any $x\in\mathcal{X}$. Then:

where $(a)$ follows by Proposition 7.5.2 of Vershynin and $(b)$ follows since $\tau_{1}$ is a feasible solution to (2). For the inductive step, assume that, for all $x\in\mathcal{S}_{k}$:

Consider round $k+1$ and take $x\in\mathcal{S}_{k+1}^{c}$. There then exists some $k^{\prime}\leq k$ such that $x\in\mathcal{S}_{k^{\prime}}\backslash\mathcal{S}_{k^{\prime}+1}$. Then:

where $(a)$ follows by Proposition 7.5.2 of Vershynin , $(b)$ follows since $\Delta_{x}\geq\epsilon_{k+1}$ by virtue of the fact that $x\in\mathcal{S}_{k+1}^{c}$, so $\Delta_{x}\geq(\epsilon_{k+1}+\Delta_{x})/2$, $(c)$ follows since $\Delta_{x}\in[\epsilon_{k^{\prime}+1},\epsilon_{k^{\prime}}]$ and for any $z\in\mathcal{S}_{k^{\prime}}$, we will have theta $\Delta_{z}\leq\epsilon_{k^{\prime}}$, so $\epsilon_{k+1}+\Delta_{x}\geq\epsilon_{k+1}+\epsilon_{k^{\prime}+1}\geq\epsilon_{k+1}+\Delta_{z}/2$, $(d)$ holds by the inductive hypothesis and Lemma 1 of Katz-Samuels et al. and taking $\hat{\Delta}_{z}$ to be the estimate of $\Delta_{z}$ at round $k+1$, and $(e)$ holds since $\tau_{k+1}$ is a feasible solution to (3). We can perform a similar calculation to get the same thing for $x\in\mathcal{S}_{k+1}$, allowing us to conclude that, for all $x\in\mathcal{S}_{k+1}$:

From here the remaining calculations on the gap estimates performed in the proof of Theorem 2 hold almost identically.

Bounding the Round Regret: From (6), it follows that the constraint in (2) is tighter than the following constraint:

so any $\tau$ satisfying this inequality is also a feasible solution to (2).

From here we follow the same pattern as in the proof of Theorem 2. We handle each term in the constraint separately. For the second term, note that we can upper bound:

For the second term, by the Kiefer-Wolfowitz Theorem in the bandit case, and Proposition 9 in the semi-bandit case, we’ll have:

Following the same argument as in Theorem 2, it follows that:

From here the argument follows identically to the proof of Theorem 4, so we omit the remainder of the proof. ∎

We can think of this procedure as a deterministic variant of action elimination. We can bound the regret incurred as:

The results on the rounding procedure follow from Katz-Samuels et al. , Allen-Zhu et al. . ∎

Given a $T$, Algorithm 1 will run for at most:

rounds. Furthermore, regardless of $T$, Algorithm 1 will run for at most:

where $(a)$ follows by Proposition 7.5.2 of Vershynin , $(b)$ follows since for any $\lambda$:

Appendix C Pure Exploration Proofs

For the sake of clarity, we rewrite the pure exploration algorithm (see Algorithm 3).

Theorem (2) shows that we can solve (12) in polynomial-time, but note that it is easier to solve (12) approximately by calling stochastic Frank-Wolfe to solve

and the convergence rate shown in Lemma 5 applies.

The MINGAP subroutine (Algorithm 4), originally provided in Chen et al. , is a computationally scalable method to compute the empirical gap between the empirically best arm and the empirically second best arm. It uses at most $d$ calls to the linear maximization oracle.

We note that the correctness and sample complexity proofs are quite similar to the proof of Theorem in Katz-Samuels et al. , but we include it for the sake of completeness. The main contribution of our paper for the pure exploration problem is a computational method to solve (12) even when the number of variables $|\mathcal{X}|$ is exponential in the dimension.

Step 1: A good event and well-estimated gaps Using the identical argument to the first two steps of the proof of Theorem 2, we have that with probability at least $1-\delta$ at every round $k$, for all $x\in\mathcal{S}_{k}$:

For the remainder of the proof we suppose that this good event holds.

Step 2: Correctness. It is enough to show at round $k$, if $x_{k}\neq x_{*}$, then the Unique$(\mathcal{X},\widehat{\theta}_{k},\epsilon_{k})$ returns false. Inspecting Unique, a sufficient condition is to show that $(x_{k}-x_{*})^{\top}\widehat{\theta}_{k}-\epsilon_{k}\leq 0$. By (13) and (14), we have that

Thus, the sample complexity is upper bounded by

where we used the fact that the rounding procedure can use $O(d)$ points in the semi-bandit case. Thus, it suffices to upper bound the second term in the above expression. Fix $\lambda\in\triangle$. Then,

Fix $x_{0}\in\mathcal{X}\setminus\{x_{*}\}$. The first term is bounded as follows.

where we obtained line (16) using exercise 7.6.9 in Vershynin .

where line (18) follows since (13), (14), and Lemma 1 in Katz-Samuels et al. imply that $x_{k}\in S_{k+2}$.

In this section, we prove a lower bound for the combinatorial bandit setting with semi-bandit feedback. Fix a model $\theta$ and let $\nu_{\theta,i}$ denote the distribution of the observations when arm $i$ is pulled. In this setting, at each round $t$, $Z^{(t)}\sim N(\theta,I)$ is drawn and

We say that an Algorithm is $\delta$-PAC if for any instance $(\mathcal{X},\theta_{*})$, it returns $x\in\mathcal{X}$ with the largest mean with probability at least $1-\delta$.

Fix an instance $(\theta_{*},\mathcal{X})$ such that $\mathcal{X}\subset\{0,1\}^{d}$ and $x_{*}=\operatorname*{arg\,max}_{x\in\mathcal{X}}x^{\top}\theta$ is unique. Let $\mathcal{A}$ be a $\delta$-PAC algorithm and let $T$ be its total number of pulls on $(\theta_{*},\mathcal{X})$. Then,

The proof is quite similar to the proof of Theorem 1 in Fiez et al. .

For simplicity, label $\mathcal{X}=\{x_{1},\ldots,x_{m}\}$ and $x_{*}=x_{1}$. Define the set of alternative instances $\mathcal{O}=\{\theta:\operatorname*{arg\,max}_{x\in\mathcal{X}}x^{\top}\theta\neq x_{1}\}$. Let $T_{i}$ denote the random number of times that $x_{i}$ is pulled during the game. Then, noting that the standard transportation Lemma from Kaufmann et al. easily generalizes to semi-bandit feedback, we have that for any $\theta\in\mathcal{O}$,

By a standard argument (see for example Theorem 1 Fiez et al. ), this implies that

Let $\epsilon>0$. For each $k\neq 1$, define

showing that $\theta^{(k)}\in\mathcal{O}$. Note that using the identity for the KL-divergence for a multivariate Gaussian, we have that

Since $\epsilon>0$ was arbitrary, we may let $\epsilon\longrightarrow 0$, obtaining the result. ∎

Next, we state and prove a lower bound for the non-interactive MLE: it chooses an allocation $\{x_{I_{1}},x_{I_{2}},\dots,x_{I_{T}}\}\in\mathcal{X}$ prior to the game, then observes $y_{t,i}=\theta_{*,i}+\eta_{t,i},\forall i\in x_{I_{t}}$ where $\eta_{t}\sim\mathcal{N}(0,I)$, and forms the MLE $\hat{\theta}_{i}=\frac{1}{T_{i}}\sum_{t=1,x_{I_{t},i}=1}^{T}y_{t,i}$ and outputs $\widehat{x}=\operatorname*{arg\,max}_{x\in\mathcal{X}}z^{\top}\widehat{\theta}$. Since the non-interactive MLE may use knowledge of $\theta_{*}$ in choosing its allocation and the estimator and recommendation rules are very natural, we view the sample complexity of the non-interactive MLE as a good benchmark to measure the sample complexity of algorithms against. The following lower bound for the non-interactive MLE resembles Theorem 3 in Katz-Samuels et al. .

The proof is quite similar to the proof of Theorem 3 in Katz-Samuels et al. , so we merely sketch it here.

Theorem 3 in Katz-Samuels et al. shows that there exists a universal constant $c>0$ such that if $c\leq\gamma^{*}(I_{1},\ldots,I_{T^{\prime}})$ or $c\leq\log(1/\delta)\rho^{\ast}(I_{1},\ldots,I_{T^{\prime}})$, the with probability at least $\delta$, the oracle MLE makes a mistake.

Now, rearranging the above inequality,we have that

Note that the allocation $T\lambda$ for the semi-bandit problem specifies an allocation $I_{1},\ldots,I_{T^{\prime}}$ for the combinatorial bandit problem and the stochastic process (and non-interactive MLE algorithm) is the same on both problems. Thus, $\gamma^{*}(T\lambda)$ can be interpreted as $\gamma^{*}_{\text{combi}}(I_{1},\ldots,I_{T^{\prime}})$ in the combinatorial bandit protocol for some allocation $I_{1},\ldots,I_{T^{\prime}}$, and we may apply the proof of Theorem 3 to obtain that with probability at least $\delta$, the oracle MLE makes a mistake.

Appendix D Computational Complexity Results

Algorithm 5 is the main algorithm (see Theorem 8 for its guarantee); it essentially does a grid search over the time horizon variable, $\tau\in[T]$. Note that for a fixed $\tau\in[T]$, we have that for all $\lambda\in\triangle$

and thus we can ignore the term $\tau\beta$. Thus, Algorithm 5 calls Algorithm 6 to solve for a fixed $\tau\in[T]$ the following optimization problem.

and perform binary search over $\widehat{OPT}$. To solve each of these convex feasibility programs, we employ the Plotkin-Shmoys-Tardos reduction to online learning and apply Algorithm 7, a multiplicative weights update style algorithm. Lemmas 6 and 7 provide the guarantees for the multiplicative weights update algorithm and for the binary search procedure, respectively.

The Plotkin-Shmoys-Tardos reduction requires a method for solving for arbitrary $\kappa_{1},\kappa_{2}\in$:

See Lemma 5 for our convergence result on stochastic Frank-Wolfe.

Finally, we note that each of our algorithms uses a global variable tol, which for the theory we set to $\tfrac{(\sqrt{2}-1)C}{4}$. We note that $C$ scales as $\frac{1}{\sqrt{\log(\frac{1}{\delta})}}$ and thus a polynomial dependence on $1/\textsc{tol}$ results in a polynomial dependence on $\log(1/\delta)$.

Algorithm 9, originally provided in Katz-Samuels et al. , uses binary search and calls to the linear maximization oracle to compute

D.2 Main Optimization Proofs

Note these are polynomial in $(d,\beta,\psi,1/\textsc{tol},\log(1/\delta),1/\xi)$. Our algorithms share a global parameter tol; it suffices to set $\textsc{tol}=\tfrac{(\sqrt{2}-1)C}{4}$. Define

The following Lemma provides the convergence guarantee for stochastic Frank-Wolfe in the semi-bandit setting (see Algorithm 8).

Furthermore, with probability at least $1-\frac{c\xi}{2^{d}}$, the number of oracle calls is bounded by

For simplicity, we focus on the case where $\kappa_{1}=\kappa_{2}=1$ (the other cases are similar). We write $\mathcal{L}(\lambda)$ and $\mathcal{L}(\lambda;\eta)$ as abbreviations for $\mathcal{L}(\kappa_{1},\kappa_{2};\lambda)$ and $\mathcal{L}(\kappa_{1},\kappa_{2};\lambda;\eta)$.

Smoothness: $\left\lVert\nabla\mathcal{L}(\lambda)-\nabla\mathcal{L}(\lambda^{\prime})\right\rVert_{\infty}\leq L\left\lVert\lambda-\lambda^{\prime}\right\rVert_{1}$ for an appropriate choice of $L$

Small deviation with high probability: $p_{r}$ is chosen sufficiently large to ensure that with probability at least $1-\delta/r^{2}$

For the sake of abbreviation, define $g(\lambda):=\frac{\partial\mathcal{L}(\lambda)}{\partial\lambda_{i}}$. By Lemma 13, we have that $\mathcal{L}(\lambda)$ is twice differentiable and that

where we used Jensen’s inequality and $c>0$ is a universal constant.

Now, by the mean value theorem, there exists $s\in$ such that

where the second inequality follows by Holder’s Inequality. Thus,

For the sake of brevity, we write $L=\frac{1}{\beta\psi^{5/2}}d^{3/2}$ for the remainder of the proof.

Step 1.2: Small deviation with high probability. Now, we show that $p_{r}$ is chosen sufficiently large to ensure that with probability at least $1-\delta/r^{2}$

we then have that by Lemma 2.6.8 in Vershynin ,

Therefore, since $|\mathcal{X}|\leq 2^{d}$ and since $p_{r}=c\frac{\frac{1}{\beta^{2}\psi^{3}}d^{2}}{L^{2}q_{r}^{2}}$ for an appropriately chosen universal constant, by a standard sub-Gaussian tail bound (21) follows.

The following Lemma shows that the Multiplicative Weight Update algorithm (Algorithm 7) either finds an approximately feasible solution or if there is no approximately feasible solution, determines infeasibility.

Fix $\tau,\widehat{OPT}\geq 0$ and let $\delta\in(0,1)$. Define

With probability at least $1-\delta-\frac{1}{2^{d}M}$, if MW($\tau,\widehat{OPT}$) does not declare infeasibility, then MW($\tau,\widehat{OPT}$) returns $\bar{\lambda}\in P_{4\textsc{tol}}$ and if MW($\tau,\widehat{OPT}$) declares infeasibility, then $P_{0}$ is infeasible. Furthermore, on the same event, MW($\tau,\widehat{OPT}$) uses at most $\mathcal{C}(d,\beta,\psi,\textsc{tol},1/\delta,1/\xi)$ linear maximization oracle calls.

The algorithm uses the Plotkin-Shmoys-Tardos reduction to online learning and essentially runs the multiplicative weights update algorithm (see Arora et al. ) where there is an expert for each constraint. Define

At each round $r$, the algorithm chooses a distribution, $p_{1}^{(r)}$ and $p_{2}^{(r)}$, over the constraints and the adversary uses the stochastic Frank-Wolfe algorithm to find $\lambda^{(r)}$ such that

The reward for expert/constraint 1 is $h_{1}(\lambda^{(r)})$ and the reward for expert/constraint 2 is $\widehat{h}_{2}(\lambda^{(r)})$.

Let $\mathcal{E}_{r}$ denote the event that $\lambda^{(r)}=\text{SFW}(p_{1}^{(r)},p_{2}^{(r)},\frac{\delta}{2R})$ satisfies

uses at most $\mathcal{A}(d,\beta,\psi,\textsc{tol},1/\delta,1/\xi)$ linear maximization oracle calls. Define $\mathcal{E}=\cap_{r}\mathcal{E}_{r}$ Further, define the following events

By Lemmas 5 and 8 applied with $\xi=\frac{1}{RM}$ and the law of total probability, we have that

Now, for the remainder of the proof we assume that $\mathcal{E}\cap\mathcal{F}$ occurs.

Suppose that at some round $r\in[R]$ Algorithm 8 returns $\lambda^{(r)}$ such that $\widehat{h}^{(r)}(\lambda^{(r)})>2\textsc{tol}$. Then, since $\mathcal{F}$ implies that

we have that on $\mathcal{E}\cap\mathcal{F}$

Thus, the algorithm correctly declares infeasibility of the convex feasibility program.

where $\rho$ is defined in Algorithm 7. We have that

since $\bar{\tau}\leq T$, $\widehat{OPT}\geq 0$, and we assume that $\bar{\theta}^{\top}(\bar{x}-x)\leq 2d$. Furthermore,

for a suitably chosen constant $c>0$ where we used that fact that $\textsc{tol}=\frac{(\sqrt{2}-1)C}{4}$.

Thus, we have shown (22) and therefore may apply Theorem 9, which implies on $\mathcal{E}\cap\mathcal{F}$ that

Now, finally, applying Lemma 7, we have that

This shows that $\bar{\lambda}^{(R)}$ approximately satisfies one of the constraints; showing approximate satisfaction of the other constraint follows by a similar argument. Thus, we conclude that $\bar{\lambda}^{(R)}\in P_{4\textsc{tol}}$. ∎

The following Lemma shows that Algorithm 6 approximately solves the optimization problem (20).

Fix $\tau\in>0$ and let $\delta\in(0,1)$. Let $\widetilde{\textsc{opt}}_{\tau}$ be the value of

then with probability at least $1-\delta-\frac{1}{\log_{2}(T)2^{d}}$ Algorithm 6 declares the program infeasible. If

Furthermore, Algorithm 6 uses a number of oracle calls that is upper bounded by $\log_{2}(2Td/\textsc{tol})\cdot\mathcal{C}(d,\beta,\psi,\textsc{tol},1/\delta,1/\xi)$.

Algorithm 6 applies Algorithm 7 at most $\log_{2}(2Td/\textsc{tol})$ times on a using a predetermined set of values for $\widehat{OPT}\in[0,2Td]$, which we denote $\widehat{OPT}_{1},\ldots,\widehat{OPT}_{l}$. Define the event

where $P_{\epsilon}$ is defined in Lemma 6. Then, by the union bound, we have that $\Pr(\mathcal{E})\geq 1-\delta-\frac{1}{2^{d}\log_{2}(T)}$. Suppose $\mathcal{E}$ occurs for the remainder of the proof.

Then, on the event $\mathcal{E}$, we have that the Algorithm 6 declares infeasibility of the program.

Note that for any $\lambda\in\triangle$, we have that

and thus the objective does not depend on $\beta$ and $\beta$ can be dropped from the objective. Using the event $\mathcal{E}$, if

is empty, then Algorithm 7 declares the program infeasible; otherwise, Algorithm 7 finds $\bar{\lambda}\in Q(\widehat{OPT})$. Then, by a standard binary search argument, the result follows. ∎

The following Theorem establishes that Algorithm 5 approximately solves the main optimization problem (5). It directly implies Theorem 4.

Let $\delta\in(0,1)$. Suppose $\textsc{tol}=\frac{(\sqrt{2}-1)C}{4}$, $\psi=\min(\frac{1}{4d\Delta_{\max}T},\frac{1}{4d})$. Let opt be the value of

With probability at least $1-\delta-\frac{1}{2^{d}}$, Algorithm 5 returns $(\bar{\tau},\bar{\lambda})$ such that $\bar{\lambda}\in\triangle$, $\bar{\tau}\leq 2T$, and

Furthermore, Algorithm 5 uses a number of oracle calls that is polynomial in $(d,\beta,\psi,\log(1/\delta))$

Step 0. Let $\widetilde{\textsc{opt}}$ be the value of

and let $\widetilde{\textsc{opt}}_{k}$ be the value of

then $\text{binSearch}(\bar{\tau}_{k},\frac{\delta}{\log_{2}(T)})$ declares the program infeasible and if

then $\text{binSearch}(\bar{\tau}_{k},\frac{\delta}{\log_{2}(T)})$ returns $\bar{\lambda}_{k}$ that satisfies

Further, define $\mathcal{E}=\cap_{k}\mathcal{E}_{k}$. By Lemma 7 and a union bound, we have that $\Pr(\mathcal{E})\geq 1-\delta-\frac{1}{2^{d}}$. We suppose $\mathcal{E}$ holds for the rest of the proof.

Step 1. First, we show that Algorithm 5 returns $(\bar{\tau},\bar{\lambda})$ such that

By assumption the optimization problem in (5) is feasible and, hence, $\textsc{opt}\neq\infty$ and thus by the event $\mathcal{E}$, the algorithm finds at least one nearly feasible solution, i.e., $\textsc{feasible}_{k}$ is not False for all $k$. Let $(\tau_{*},\lambda_{*})$ attain the optimal value in the optimization problem (5). Let $k_{*}$ such that $\bar{\tau}_{k_{*}}\in[\tau_{*},2\tau_{*}]$. By event $\mathcal{E}$ $\text{binSearch}(\bar{\tau}_{k_{*}},\frac{\delta}{\log_{2}(T)})$ finds $\bar{\lambda}_{k_{*}}$ such that

Algorithm 5 outputs $(\bar{\tau},\lambda_{\widehat{k}_{*}})$, which satisfies by Lemma 7 and by construction,

where in the last line we used $\textsc{tol}=\frac{(\sqrt{2}-1)C}{4}\leq 1/8$, which bounds the objective value of $(\bar{\tau},\lambda_{\widehat{k}_{*}})$.

Next, we show feasiblity of $(\bar{\tau},\lambda_{\widehat{k}_{*}})$. Observe that

where we used the fact that $\bar{\tau}=2\bar{\tau}_{\widehat{k}_{*}}$ and $\textsc{tol}=\frac{(\sqrt{2}-1)C}{4}$.

Step 2: Relate $\widetilde{\textsc{opt}}_{k}$ to $\widetilde{\textsc{opt}}$. Next, we show that

Recall that we let $(\tau_{*},\lambda_{*})$ attain the optimal value in the optimization problem (5). Let $k_{*}$ such that $\bar{\tau}_{k_{*}}\in[\tau_{*},2\tau_{*}]$. Note that

Step 3: Relate $\widetilde{\textsc{opt}}$ to opt. Next, we show that

where in the last line we used $\psi=\min(\frac{1}{4d\Delta_{\max}T},\frac{1}{4d})$.

Step 4: Putting it together. Putting together (26), (25), (27), and (28), we have that Algorithm 5 returns $(\bar{\tau},\bar{\lambda})$ such that $\bar{\lambda}\in\triangle$, $\bar{\tau}\leq 2T$, and

D.3 Miscellaneous Optimization Lemmas

and the number of linear maximization oracle calls is bounded above by

The estimation results by applying a standard subGaussian tail bound. The bound on the number of oracle calls follows since Algorithm 9 is applied $O(\log(1/\delta)\frac{d}{\beta^{2}\psi\textsc{tol}^{2}})$ times and by Lemma 9 and a union bound. ∎

The following Lemma shows that the binary search procedure in Algorithm 9 is efficient with very high probability and it follows immediately from the proof of Lemma 2 of Katz-Samuels et al. .

Draw $\eta\sim N(0,I)$ and consider the optimization problem

Next, we describe a result on the multiplicative weights update algorithm that follows immediately from Corollary 4 in Arora et al. . Consider the experts problem. The set of events is denoted by $P$. Suppose there are $m$ experts. At each round $t$, the agent picks an expert $i\in[m]$ and the adversary picks an outcome $j^{t}\in P$ and the agent obtains reward $M(i,j^{t})$. The multiplicative weights update algorithm mains a distribution $D^{t}$ over the experts and chooses an expert randomly from $D^{t}$ (see Arora et al. for details on how this distribution is chosen). The adversary may have knowledge of the $D^{t}$ when choosing $j^{t}$. The following provides a lower bound on the expected reward obtained by the multiplicative weights update algorithm.

Let $\xi>0$ denote an error parameter. Suppose there are $m$ experts and $|M(i,j)|\leq\rho$. If the multiplicative weights algorithm sets the learning rate as $\epsilon=\min(\frac{\xi}{4\rho},\frac{1}{2})$, after $T=\frac{16\rho^{2}\ln(m)}{\xi^{2}}$, then the multiplicative weights algorithm achieves the following bound on its average expected reward: for any expert $i$,

D.4 Convergence Lemmas

The objective in semi-feedback is convex (by a similar argument to the proof in Katz-Samuels et al. ).

Fix $\lambda,\kappa\in\triangle^{|\mathcal{X}|}$ and $\alpha\in$. By matrix convexity,

Furthermore, since the above matrices are diagonal,

Then, by Sudakov-Fernique inequality (Theorem 7.2.11 in Vershynin ),

Next, we turn to analyzing stochastic Frank-Wolfe. Although a convergence result for stochastic frank wolfe is provided in Hazan and Luo , our setup is slightly different, so we include a convergence analysis for our setting for the sake of completeness. The proof is quite similar to the proof in Hazan and Luo .

Suppose that $\sup_{w,w^{\prime}\in\Omega}\left\lVert w-w^{\prime}\right\rVert\leq D$. Suppose that $f$ is convex, $\left\lVert\nabla f(x)-\nabla f(y)\right\rVert_{*}\leq L\left\lVert x-y\right\rVert$, and $p_{r}$ in Algorithm 11 is chosen such that with probability at least $1-\delta/r^{2}$

where $q_{r}=\frac{2}{k+1}$. Then, with probability at least $1-c\delta$,

The proof follows closely the analysis of SFW in Hazan and Luo but uses smoothness wrt $\left\lVert\cdot\right\rVert_{*}$. We have that

where line (29) uses smoothness (Lemma 11), line (30) uses the optimality of $v_{r}$, and line (31) uses the definition of the dual norm. Now, define the event

By hypothesis, $p_{r}$ is chosen such that with probability at least $1-\delta/r^{2}$, $\left\lVert\widetilde{\nabla}_{r}-\nabla f(w_{r-1})\right\rVert_{*}\leq\frac{LDq_{r}}{2}$. Therefore, we have that

The proof is concluded by simple induction. ∎

This follows by a straightforward case by case analysis. ∎

The following is standard smoothness Lemma from convex optimization.

D.5 Differentiability Lemmas

In this section, we show that $\mathcal{L}(\kappa_{1},\kappa_{2};\lambda)$ is twice-differentiable wrt $\lambda$. We set $\kappa_{1},\kappa_{2}=1$ for simplicity and write $\mathcal{L}(\lambda)$ instead of $\mathcal{L}(\kappa_{1},\kappa_{2};\tau;\lambda)$ for the sake of brevity. The following Lemma shows that $\mathcal{L}(\kappa_{1},\kappa_{2};\tau;\lambda)$ is differentiable wrt $\lambda$.

The calculation of $\frac{\partial\mathcal{L}(\lambda;\eta)}{\partial\lambda_{i}}$ follows by the chain rule.

Step 1: First, we show that $\mathcal{L}(\lambda;\eta)$ is Lipschitz with an absolutely integrable Lipschitz constant. Define

Since $\mathcal{L}(\lambda;\eta):=\max_{x\in\mathcal{X}}\mathcal{J}(\lambda;\eta;x)$ and the maximum of $C_{\eta}$-Lipschitz functions is $C_{\eta}$-Lipschitz, we have that

Step 2: Now, we show that the partial derivatives exist. Define the event

is distinct, if $\eta\sim N(0,I)$, then with probability $1$ $B_{\lambda}$ holds and $\mathcal{L}(\lambda;\eta)$ is differentiable at $\lambda$.

so the maximizer will be unique. As this is true for all $\eta\in B_{\lambda}$, it follows that $\lim_{n\rightarrow\infty}B_{\lambda^{(n)}}\subseteq B_{\lambda}$. An identical argument implies $B_{\lambda}\subseteq\lim_{n\rightarrow\infty}B_{\lambda^{(n)}}$, so $\lim_{n\rightarrow\infty}B_{\lambda^{(n)}}=B_{\lambda}$. Then, by the dominated convergence theorem,

The following Lemma shows that $\mathcal{L}(\kappa_{1},\kappa_{2};\tau;\lambda)$ is twice-differentiable wrt $\lambda$.

Thus, we may apply the dominating convergence theorem to obtain

for some constant $C>0$. Therefore, by the bounded convergence theorem for limits, we have that

However, $\sum_{n=0}^{\infty}c_{mn}=\lim_{N\rightarrow\infty}\sum_{n=0}^{N}c_{mn}$, so the above implies:

By construction, we have $\sum_{n=0}^{N}c_{mn}=a_{mN}$, which proves the result.

and $EY(h)<\infty$. Thus, by the dominating convergence theorem,

Step 4. Putting together (34), (35), and (36), we have shown that

Thus, we have that that the second order partial derivatives exist and derived an expression for them. Showing that the second order partial derivatives are continuous proceeds as in the proof of Lemma 12 (apply the dominating convergence theorem).

Appendix E Rounding

This is a standard result in convex geometry, see for instance Eggleston . ∎

Given any $\lambda\in\triangle_{\mathcal{X}}$, in the bandit setting, there exists a distribution $\lambda^{\prime}\in\triangle_{\mathcal{X}}$ that is $(d^{2}+d+1)$-sparse and:

In the semi-bandit setting, when $\mathcal{X}\subseteq\{0,1\}^{d}$, there exists a distribution $\lambda^{\prime}\in\triangle_{\mathcal{X}}$ that is $(d+1)$-sparse and:

Given some allocation $\tau$, let $\lambda$ the corresponding distribution, and $\bar{\tau}=\sum_{x\in\mathcal{X}}\tau_{x}$ (so $\tau=\bar{\tau}\lambda$).

Since we only care about the sparsity of $\lambda$, consider $\bar{\tau}$ fixed. Then, given a solution $\lambda$ to (2) or (3), the value of the constraint and objective the solution achieves achieves are fully specified by $A_{\mathfrak{f}}(\lambda)$ and $\sum_{x\in\mathcal{X}}\lambda_{x}x$. To see the latter, note that $\sum_{x\in\mathcal{X}}(\epsilon+\Delta_{x})\lambda_{x}=\epsilon+\sum_{x\in\mathcal{X}}\theta^{\top}(x_{*}-x)\lambda_{x}=\epsilon+\theta^{\top}x_{*}+\theta^{\top}\sum_{x\in\mathcal{X}}\lambda_{x}x$. Lemma 14 then implies that there exists a distribution $\lambda$ that is $(d^{2}+d+1)$-sparse in the bandit case and $(d+1)$-sparse in the semi-bandit case that achieves the same value of the constraint and objective of (2) or (3).

Appendix F Gaussian Width Results

This proof closely mirrors the proof of Theorem 21.1 of Lattimore and Szepesvári .

Note also that, by the identity above, for any $\lambda$:

Choosing $\lambda$ to be the distribution putting all its mass on $x$, we have:

To see the equality, note that the above implies:

Let $S=\{x\in\mathcal{X}:\Delta_{x}\leq\epsilon\}$ for some fixed $\epsilon>0$. Therefore, $x^{*}\in S$. Define

We begin by bounding the first term. Notice that $S_{1}\subset S$ since $S=\{x\in\mathcal{X}:\Delta_{x}\leq\epsilon\}$ for some fixed $\epsilon>0$ and thus if $x\in\{0,1\}^{m}\text{ s.t. there exists }x^{\prime}\in S\text{ s.t. }\Pi_{[m]}x^{\prime}=x$, then $(x,x^{*}_{m+1:n+m})\in S$. Furthermore, the span of the vectors in $S_{1}$ has dimension at most $m+1$ since for any $x_{1}\in S_{1}$, for all $i\geq m+1$, we have that

Thus, by the Kiefer-Wolfowitz Theorem Lattimore and Szepesvári :

To lower bound $|\mathcal{X}|$, note that:

For the regret bound of competing algorithms, LinUCB will scale as $\widetilde{\mathcal{O}}(d\sqrt{T})=\widetilde{\mathcal{O}}(m^{3/2}\sqrt{T})$. Given the above lower bound on $|\mathcal{X}|$, the regret of action elimination will scale as $\widetilde{\mathcal{O}}(m\sqrt{T})$. In the semi-bandit setting, Kveton et al. obtain a regret bound of $\widetilde{\mathcal{O}}(m\sqrt{T})$ and, ignoring logarithmic terms, Degenne and Perchet obtain the same bound. Other existing works [Combes et al., 2015, Perrault et al., 2020a] do not state minimax bounds but, using the standard analysis to obtain a minimax bound from a gap-dependent bound, their regret will also scale as $\widetilde{\mathcal{O}}(m\sqrt{T})$. Note that in this comparison we have ignored $\log(T)$ terms and have taken the dominate term to be the term with leading $m$ dependence that hits the $\sqrt{T}$. ∎

Taking the infimum over $\lambda\in\triangle_{\mathcal{X}}$, in the bandit feedback case Kiefer-Wolfowitz gives $\inf_{\lambda\in\triangle_{\mathcal{X}}}\max_{x\in\mathcal{X}}\|x\|_{A(\lambda)^{-1}}\leq\sqrt{d}$, and in the semi-bandit case, Proposition 9 gives the same result. Since $\mathcal{X}$ was chosen arbitrarily, it follows that $\bar{\gamma}(\mathcal{X})\leq d^{2}$.

For the second bound, Exercise 7.5.10 of Vershynin gives that:

from which the result follows immediately. ∎

If $\mathcal{X}\subseteq\{0,1\}^{d}$ and $k=\max_{x\in\mathcal{X}}\|x\|_{1}$, then $\mathcal{X}$ at most contains all subsets of size $k$ and less so:

where the last inequality follows since the gaussian complexity is within a constant of the Gaussian width when the set contains 0, by Exercise 7.6.9 of Vershynin . The result then follows by choosing $k=\sqrt{d}$. ∎

The proof in the bandit setting is identical to the proof given in Katz-Samuels et al. and we therefore omit it.

Appendix G Lower Bound for Semi-Bandit Feedback and Optimistic Strategies

A policy $\pi$ is consistent if for all $\theta$ and $p>0$, $R^{\pi}_{\theta}(T)=o(T^{p})$. Let $T_{x}$ denote the number of times that $x\in\mathcal{X}$ is pulled and $T_{i}$ the number of times that $i\in[d]$ is pulled.

We use a similar argument to the proof of Theorem 1 in Lattimore and Szepesvari . We construct an alternative instance $\theta^{\prime}$ to obtain an asymptotic lower bound. Let $P^{\prime}$ denote the probability measure of the associated instance (which we will specify shortly). We note that the Divergence Lemma (Lemma 15.1 Lattimore and Szepesvári ) is easily adapted to the semi-bandit feedback setting. Thus, by a standard argument that applies the Divergence Lemma and the Bretagnolle–Huber inequality (Theorem 14.2 in Lattimore and Szepesvári ), we have that

Let $R_{T}^{\prime}$ denote the regret of $\pi$ on the alternative instance $\theta^{\prime}$. Choose $E=\{T_{x_{*}}\leq\frac{T}{2}\}$. We have that

Then, inequalities (38) and (39) imply that

Dividing both sides by $\log(T)$, we have that

Consistency of the policy $\pi$ implies that

This establishes the first claim in the lower bound. The second claim follows by a similar argument to the argument in Corollary 2 of Lattimore and Szepesvari .

Proof of lower bound for optimism: Define the following problem instance

with $\mathcal{X}=\{\{1\},\ldots,\{m\},[2m+\sqrt{m}]\}$. Let $x^{(i)}=\{i\}$ for $i\leq m$ and $x^{(m+1)}=[2m+\sqrt{m}]$. Note that $\Delta_{i}=\epsilon$ if $i\leq m$ and $\Delta_{m+1}=\sqrt{m}+1$. Then, the optimization problem in Theorem 12 becomes

Consider the solution is $\tau_{m+1}=\frac{4}{\epsilon^{2}}$ and $\tau_{i}=0$ otherwise. This attains a value of

Now, consider the performance of the generic optimistic algorithm. Let $T_{i}$ denote the number of times that arm $i$ is chosen. Define the event

Suppose $\mathcal{E}$ holds. Now, suppose that $T_{m+1}=4\alpha\log(T)$. Then,

for all $i$, which together with (40) implies that

is sufficient. Since this is a feasible solution, we’ll then have that:

where the last inequality holds since $\sqrt{m}=\Delta_{\max}$. Ignoring $\log$ factors that do not involve $\delta$, and noting that there are at most $\log(\sqrt{m}/\epsilon)$ rounds, the total regret is bounded as:

Choosing $\delta=1/T$ completes the proof.

Failure of Thompson Sampling for semi-bandit feedback: We now provide a sketch as to why Thompson sampling fails on the instance in Proposition 1. Intuitively, Thompson Sampling is optimistic in a randomized fashion, so we would expect it to fail in the same way as optimistic algorithms. Slightly more formally, consider a typical version of Thompson sampling where at each round $t$, $\widetilde{\theta}_{t}\sim N(\widehat{\theta}_{t},(\sum_{s=1}^{t-1}\operatorname*{diag}(x_{s}x_{s}^{\top}))^{-1}))$ where $x_{s}$ is the arm chosen at time $s$ and $x_{t}=\operatorname*{arg\,max}_{x\in\mathcal{X}}x^{\top}\widetilde{\theta}_{t}$. Note that with high probability, we will have that:

so we will essentially only pull an arm when$\sqrt{\alpha\|x\|_{(\sum_{s=1}^{t-1}\operatorname*{diag}(x_{s}x_{s}^{\top}))^{-1}}^{2}\log(T)}>\Delta_{x}$. In the case of $\mathbf{1}$, we will have:

where $T_{m+1}$ are the total pulls of $\mathbf{1}$. Since $\Delta_{m+1}=\sqrt{m}$, the above inequality reduces to:

so arm $\mathbf{1}$ will only be pulled a logarithmic number of times in $T$, which, as with optimism, is not sufficient to achieve optimal regret.

Appendix H Additional Experimental Results

We remark that, when running RegretMED, we do not use the exact constants specified in the algorithm. These constants are likely somewhat loose due to looseness in our analysis. In addition, we do not run the computationally efficient procedure derived formally but instead found that a much simpler heuristic—running stochastic Frank-Wolfe on the Lagrangian relaxation—works well in practice. We also do not use the precise value of $\Delta_{\max}$, and instead use an upper bound that can be computed using only knowledge of the arms.

The algorithms we compare against do not contain significant hyperparameters, and we choose reasonable values for the parameters they do require. In particular, for LinUCB, we use the regularization $\lambda=1$.