Achieving Near Instance-Optimality and Minimax-Optimality
in Stochastic and Adversarial Linear Bandits Simultaneously

We consider the linear bandit problem with a finite and fixed action set. In this problem, the learner repeatedly selects an action from the action set and observes her loss whose mean is the inner product between the chosen action and an unknown loss vector determined by the environment. The goal is to minimize the regret, which is the difference between the learner’s total loss and the total loss of the best action in hindsight. Two standard environments are heavily-studied in the literature: the stochastic environment and the adversarial environment. In the stochastic environment, the loss vector is fixed over time, and we are interested in instance-optimal regret bounds of order $o(T^{\epsilon})$ for any $\epsilon>0$, where $T$ is the number of rounds and $o(\cdot)$ hides some instance-dependent constants. On the other hand, in the adversarial environment, the loss vector can be arbitrary in each round, and we are interested in minimax-optimal regret bound $\widetilde{\mathcal{O}}(\sqrt{T})$, where $\widetilde{\mathcal{O}}(\cdot)$ hides the problem dimension and logarithmic factors in $T$.

While there are many algorithms obtaining such optimal bounds in either environment (e.g., (Lattimore & Szepesvari, 2017) in the stochastic setting and (Bubeck et al., 2012) in the adversarial setting), a natural question is whether there exists an algorithm achieving both guarantees simultaneously without knowing the type of the environment. Indeed, the same question has been studied extensively in recent years for the special case of multi-armed bandits where the action set is the standard basis (Bubeck & Slivkins, 2012; Seldin & Slivkins, 2014; Auer & Chiang, 2016; Seldin & Lugosi, 2017; Wei & Luo, 2018; Zimmert & Seldin, 2019). Notably, Zimmert & Seldin (2019) developed an algorithm that is optimal up to universal constants for both stochastic and adversarial environments, and the techniques have been extended to combinatorial semi-bandits (Zimmert et al., 2019) and finite-horizon tabular Markov decision processes (Jin & Luo, 2020). Despite all these advances, however, it is still open whether similar results can be achieved for general linear bandits.

On the other hand, another line of recent works study the robustness of stochastic linear bandit algorithms from a different perspective and consider a corrupted setting where an adversary can corrupt the stochastic losses up to some limited amount $C$. This was first considered in multi-armed bandits (Lykouris et al., 2018; Gupta et al., 2019; Zimmert & Seldin, 2019, 2021) and later extended to linear bandits (Li et al., 2019) and Markov decision processes (Lykouris et al., 2019; Jin & Luo, 2020). Ideally, the regret of a robust stochastic algorithm should degrade with an additive term $\mathcal{O}(C)$ in this setting, which is indeed the case in (Gupta et al., 2019; Zimmert & Seldin, 2019, 2021; Jin & Luo, 2020) for multi-armed bandits or Markov decision processes, but is not achieved yet for general linear bandits.

In this paper, we make significant progress in this direction and develop algorithms with near-optimal regret simultaneously for different environments. Our main contributions are as follows.

• •

  In Section 4, we first introduce Algorithm LABEL:alg:REOLB, a simple algorithm that achieves $\mathcal{O}(c(\mathcal{X},\theta)\log^{2}T+C)$ regret with high probability in the corrupted setting,¹¹1In the texts, $\mathcal{O}(\cdot)$ often hides lower-order terms (in terms of $T$ dependence) for simplicity. However, in all formal theorem/lemma statements, we use $\mathcal{O}(\cdot)$ to hide universal constants only. where $c(\mathcal{X},\theta)$ is an instance-dependent quantity such that the instance-optimal bound for the stochastic setting (i.e. $C=0$) is $\Theta(c(\mathcal{X},\theta)\log T)$. This result significantly improves (Li et al., 2019) which only achieves $\mathcal{O}\big{(}\frac{d^{6}\log^{2}T}{\Delta_{\min}^{2}}+\frac{d^{2.5}C\log T}{\Delta_{\min}}\big{)}$ where $d$ is the dimension of the actions and $\Delta_{\min}$ is the minimum sub-optimality gap satisfying $c(\mathcal{X},\theta)\leq\mathcal{O}\big{(}\frac{d}{\Delta_{\min}}\big{)}$. Moreover, Algorithm LABEL:alg:REOLB also ensures an instance-independent bound $\widetilde{\mathcal{O}}(d\sqrt{T}+C)$ that some existing instance-optimal algorithms fail to achieve even when $C=0$ (e.g., (Jun & Zhang, 2020)).

• •

  In Section 5, based on Algorithm LABEL:alg:REOLB, we further propose Algorithm 1 which not only achieves nearly instance-optimal regret $\mathcal{O}(c(\mathcal{X},\theta)\log^{2}T)$ in the stochastic setting, but also achieves the minimax optimal regret $\widetilde{\mathcal{O}}(\sqrt{T})$ in the adversarial setting (both with high probability). To the best of our knowledge, this is the first algorithm that enjoys the best of both worlds for linear bandits. Additionally, the same algorithm also guarantees $\widetilde{\mathcal{O}}\big{(}\frac{d\log^{2}T}{\Delta_{\min}}+C\big{)}$ in the corrupted setting, which is slightly worse than Algorithm LABEL:alg:REOLB but still significantly better than (Li et al., 2019).

• •

  Finally, noticing the extra $\log T$ factor in our bound for the stochastic setting, in Appendix D we also prove that this is in fact inevitable if the same algorithm simultaneously achieves sublinear regret in the adversarial setting with high probability (which is the case for Algorithm 1). This generalizes the result of (Auer & Chiang, 2016) for two-armed bandits.

At a high level, Algorithm LABEL:alg:REOLB utilizes a well-known optimization problem (that characterizes the lower bound in the stochastic setting) along with a robust estimator to determine a randomized strategy for each round. This ensures the near instance-optimality of the algorithm in the stochastic setting, and also the robustness to corruption when combined with a doubling trick. To handle the adversarial setting as well, Algorithm 1 switches between an adversarial linear bandit algorithm with high-probability regret guarantees and a variant of Algorithm LABEL:alg:REOLB, depending on the results of some carefully-designed statistical tests on the stochasticity of the environment.

Let $\mathcal{X}\subset\mathbb{R}^{d}$ be a finite set that spans $\mathbb{R}^{d}$. Each element in $\mathcal{X}$ is called an arm or an action. We assume that $\|x\|_{2}\leq 1$ for all $x\in\mathcal{X}$. A linear bandit problem proceeds in $T$ rounds. In each round $t=1,\ldots,T$, the learner selects an action $x_{t}\in\mathcal{X}$. Simultaneously, the environment decides a hidden loss vector $\ell_{t}\in\mathbb{R}^{d}$ and generates some independent zero-mean noise $\epsilon_{t}(x)$ for each action $x$. Afterwards, the learner observes her loss $y_{t}=\langle x_{t},\ell_{t}\rangle+\epsilon_{t}(x_{t})$. We consider three different types of settings: stochastic, corrupted, and adversarial, explained in detail below.

In the stochastic setting, $\ell_{t}$ is fixed to some unknown vector $\theta\in\mathbb{R}^{d}$. We assume that there exists a unique optimal arm $x^{*}\in\mathcal{X}$ such that $\langle x^{*},\theta\rangle<\min_{x^{*}\neq x\in\mathcal{X}}\langle x,\theta\rangle$, and define for each $x\in\mathcal{X}$, its sub-optimality gap as $\Delta_{x}=\langle x-x^{*},\theta\rangle$. Also denote the minimum gap $\min_{x\neq x^{*}}\Delta_{x}$ by $\Delta_{\min}$.

The corrupted setting is a generalization of the stochastic setting, where in addition to a fixed vector $\theta$, the environment also decides a corruption vector $c_{t}\in\mathbb{R}^{d}$ for each round (before seeing $x_{t}$) so that $\ell_{t}=\theta+c_{t}$.²²2In other words, the environment corrupts the observation $y_{t}$ by adding $\langle x_{t},c_{t}\rangle$. The setting of (Li et al., 2019) is slightly more general with the corruption on $y_{t}$ being $c_{t}(x_{t})$ for some function $c_{t}$ that is not necessarily linear. We define the total amount of corruption as $C=\sum_{t}\max_{x\in\mathcal{X}}|\langle x,c_{t}\rangle|$. The stochastic setting is clearly a special case with $C=0$. In both of these settings, we define the regret as $\text{\rm Reg}(T)=\max_{x\in\mathcal{X}}\sum_{t=1}^{T}\langle x_{t}-x,\theta\rangle=\sum_{t=1}^{T}\Delta_{x_{t}}$.

Finally, in the adversarial setting, $\ell_{t}$ can be chosen arbitrarily (possibly dependent on the learner’s algorithm and her previously chosen actions). The difference compared to the corrupted setting (which also has potentially arbitrary loss vectors) is that the regret is now defined in terms of $\ell_{t}$: $\text{\rm Reg}(T)=\max_{x\in\mathcal{X}}\sum_{t=1}^{T}\langle x_{t}-x,\ell_{t}\rangle$.

In all settings, we assume $\langle x,\theta\rangle,\langle x,c_{t}\rangle,\langle x,\ell_{t}\rangle$ and $y_{t}$ are all in $[-1,1]$ for all $t$ and $x\in\mathcal{X}$. We also denote $\langle x,\ell_{t}\rangle$ by $\ell_{t,x}$ and similarly $\langle x,c_{t}\rangle$ by $c_{t,x}$.

It is known that the minimax optimal regret in the adversarial setting is $\Theta(d\sqrt{T})$ (Dani et al., 2008b; Bubeck et al., 2012). The instance-optimality in the stochastic case, on the other hand, is slightly more complicated. Specifically, an algorithm is called consistent if it guarantees $\mathbb{E}[\text{\rm Reg}(T)]=o(T^{\epsilon})$ for any $\theta$, $\mathcal{X}$, and $\epsilon>0$. Then, a classic lower bound result (see e.g., (Lattimore & Szepesvari, 2017)) states that: for a particular instance $(\mathcal{X},\theta)$, all consistent algorithms satisfy:³³3The original proof is under the Gaussian noise assumption. To meet our boundedness assumption on $y_{t}$, it suffices to consider the case when $y_{t}$ is a Bernoulli random variable, which only affects the constant of the lower bound.

where $c(\mathcal{X},\theta)$ is the objective value of the following optimization problem:

and $H(N)=\sum_{x\in\mathcal{X}}N_{x}xx^{\top}$ (the notation $\|x\|_{M}$ denotes the quadratic norm $\sqrt{x^{\top}Mx}$ with respect to a matrix $M$). This implies that the best instance-dependent bound for $\text{\rm Reg}(T)$ one can hope for is $\mathcal{O}(c(\mathcal{X},\theta)\log T)$ (and more generally $\mathcal{O}(c(\mathcal{X},\theta)\log T+C)$ for the corrupted setting). It can be shown that $c(\mathcal{X},\theta)\leq\mathcal{O}\left(\frac{d}{\Delta_{\min}}\right)$ (see Lemma 16), but this upper bound can be arbitrarily loose as shown in (Lattimore & Szepesvari, 2017).

The solution $N_{x}$ in the optimization problem above specifies the least number of times action $x$ should be drawn in order to distinguish between the present environment and any other alternative environment with a different optimal action. Many previous instance-optimal algorithms try to match their number of pulls for $x$ to the solution $N_{x}$ under some estimated gap $\widehat{\Delta}_{x}$ (Lattimore & Szepesvari, 2017; Hao et al., 2020; Jun & Zhang, 2020). While these algorithms are asymptotically optimal, their regret usually grows linearly when $T$ is small (Jun & Zhang, 2020). Furthermore, they are all deterministic algorithms and by design cannot tolerate corruptions. We will show how these issues can be addressed in the next section.

In this section, we focus on the corrupted setting (hence covering the stochastic setting as well). We introduce a new algorithm that achieves with high probability an instance-dependent regret bound of $\mathcal{O}(c(\mathcal{X},\theta)\log^{2}T+C)$ for large $T$ and also an instance-independent regret bound of $\widetilde{\mathcal{O}}(d\sqrt{T}+C)$ for any $T$. This improves over previous instance-optimal algorithms (Lattimore & Szepesvari, 2017; Hao et al., 2020; Jun & Zhang, 2020) from several aspects: 1) first and foremost, our algorithm handles corruption optimally with extra $\mathcal{O}(C)$ regret, while previous algorithms can fail completely due to their deterministic nature; 2) previous bounds only hold in expectation; 3) previous algorithms might suffer linear regret when $T$ is small, while ours is always $\widetilde{\mathcal{O}}(d\sqrt{T}+C)$ for any $T$. The price we pay is an additional $\log T$ factor in the instance-dependent bound. On the other hand, compared to the work of (Li et al., 2019) that also covers the same corrupted setting and achieves $\mathcal{O}\left(\frac{d^{6}\log^{2}T}{\Delta_{\min}^{2}}+\frac{d^{2.5}C\log T}{\Delta_{\min}}\right)$, our results are also significantly better (recall $c(\mathcal{X},\theta)\leq\mathcal{O}(d/\Delta_{\min})$), although as mentioned in Footnote 2, their results hold for an even more general setting with non-linear corruption.

Our algorithm is presented in Algorithm LABEL:alg:REOLB, which proceeds in blocks of rounds whose length grows in a doubling manner ($2^{0},2^{1},\ldots$). At the beginning of block $m$ (denoted as $\mathcal{B}_{m}$), we compute a distribution $p_{m}$ over actions by solving an optimization problem OP (Figure LABEL:fig:_op) using the empirical gap $\widehat{\Delta}_{m,x}$ estimated in the previous block (Line LABEL:line:_solving_OP_in_alg_1). Then we use $p_{m}$ to sample actions for the entire block $m$, and construct an unbiased loss estimator $\widehat{\ell}_{t,x}$ in every round for every action $x$ (Line LABEL:line:_construct_loss_estimator_alg_1). At the end of each block $m$, we use $\{\widehat{\ell}_{\tau,x}\big{\}}_{\tau\in\mathcal{B}_{m}}$ to construct a robust loss estimator $\text{Rob}_{m,x}$ for each action (Line LABEL:line:_construct_robust_alg_1), which will then be used to construct $\widehat{\Delta}_{m+1,x}$ for the next block. We next explain the optimization problem OP and the estimators in detail.

OP is inspired by the lower bound optimization (Eq. (1) and Eq. (2)), where we normalize the pull counts $N$ as a distribution $p$ over the arms such that for a large $m$, $p_{m,x}\approx\frac{N_{x}}{2^{m}}$ holds for $x\neq x^{*}$. One key difference between our algorithm and previous ones (Lattimore & Szepesvari, 2017; Hao et al., 2020; Jun & Zhang, 2020) is exactly that we select actions randomly according to these distributions, while they try to deterministically match the pull count of each arm to $N$. Our randomized strategy not only prevents the environment from exploiting the knowledge on the learner’s choices, but also allows us to construct unbiased estimator $\widehat{\ell}_{t,x}$ (Line LABEL:line:_construct_loss_estimator_alg_1) following standard adversarial linear bandit algorithms (Dani et al., 2008b; Bubeck et al., 2012). In fact, as shown in our analysis, the variance of the estimator $\widehat{\ell}_{t,x}$ is exactly bounded by $\|x\|_{S_{m}^{-1}}^{2}$ (for $t\in\mathcal{B}_{m}$), which is in turn bounded in terms of the sub-optimality gap of $x$ in light of the constraint Eq. (LABEL:eqn:_opt-2-constraint). The similar idea of imposing explicit constraints on the variance of loss estimators appears before in for example (Dudik et al., 2011; Agarwal et al., 2014) for contextual bandits. Finally, we point out that OP always has a solution due to the additive term $4d$ in Eq. (LABEL:eqn:_opt-2-constraint) (see Lemma 11), and it can be solved efficiently by standard methods since Eq. (LABEL:eqn:_opt-2-constraint) is a convex constraint.

Another important ingredient of our algorithm is the robust estimator $\text{Rob}_{m,x}$, which is a clipped version of the Catoni’s esimator (Catoni, 2012) constructed using all the unbiased estimators $\{\widehat{\ell}_{\tau,x}\}_{\tau\in\mathcal{B}_{m}}$ from this block for action $x$ (Figure LABEL:fig:catoni). From a technical perspective, this avoids a lower-order term in Bernstein-style concentration bounds and is critical for our analysis. We in fact also believe that this is necessary since there is no explicit regularization on the magnitude of $\widehat{\ell}_{t,x}$, and it can indeed have a heavy-tailed distribution. While other robust estimators are possible, we use the Catoni’s estimator which was analyzed in (Wei et al., 2020) for non-i.i.d. random variables (again important for our analysis).

The following theorem summarizes the nearly instance-optimal regret bound of Algorithm LABEL:alg:REOLB.

The dominating term of this regret bound is thus $\mathcal{O}(c(\mathcal{X},\theta)\log^{2}T+C)$ as claimed. The definition of $M^{*}$ can be found in the proof (Appendix B) and is importantly independent of $T$. In fact, in Theorem 19, we also provide an alternative (albeit weaker) bound $\mathcal{O}(\frac{d^{2}(\log T)^{2}}{\Delta_{\min}}+C)$ for Algorithm LABEL:alg:REOLB without the dependence on $M^{*}$.

The next theorem shows an instance-independent bound of order $\widetilde{\mathcal{O}}(d\sqrt{T}+C)$ for Algorithm LABEL:alg:REOLB, which previous instance-optimal algorithms fail to achieve as mentioned.

We emphasize that Algorithm LABEL:alg:REOLB is parameter-free and does not need to know $C$ to achieve these bounds. In the rest of the section, we provide a proof sketch for Theorem 1 and Theorem 2. First, we show that the estimated gap $\widehat{\Delta}_{m,x}$ is close to the true gap $\Delta_{x}$ with a constant multiplicative factor and some additive terms that go down at the rate of roughly $1/\sqrt{t}$ up to the some average amount of corruption.

As mentioned, the proof of Lemma 3 heavily relies on the robust estimators we use as well as the variance constraint Eq. (LABEL:eqn:_opt-2-constraint). Next, we have the following lemma which bounds the objective value of OP.

Combining Lemma 3 and Lemma 4, we see that in block $m$, the regret of Algorithm LABEL:alg:REOLB can be upper bounded by

where in the first equality we use Lemma 3 and in the second equality we use Lemma 4 with the fact that $p_{m}=\textbf{OP}(2^{m},\widehat{\Delta}_{m})$. Further summing this over $m$ and relating $\sum_{m}2^{m}\rho_{m-1}$ to $C$ proves Theorem 2.

In addition, based on Lemma 3, we show that when $t\in\mathcal{B}_{m}$ is larger than $\Omega(C/\Delta_{\min})$ plus some problem-dependent constant, the estimated gap $\widehat{\Delta}_{m,x}$ becomes $\Theta(\Delta_{x})$. Therefore, the solution $\{p_{m,x}\}_{x\in\mathcal{X}\setminus\{x^{*}\}}$ from OP is very close to $\{\frac{N_{x}}{2^{m}}\}_{x\in\mathcal{X}\setminus\{x^{*}\}}$, where $N_{x}$ is the optimal solution of Eq. (1) and Eq. (2), except that we have an additional $\log(2^{m}|\mathcal{X}|/\delta)$ factor in the constraint (coming from $\beta_{2^{m}}$). Therefore, the regret is bounded by $\mathcal{O}(c(\mathcal{X},\theta)\log(T)\log(T|\mathcal{X}|/\delta))$ for large enough $T$. Formally, we have the following lemma.

Finally, to obtain Theorem 1, it suffices to apply Theorem 2 for the regret before round $T^{*}$ and Lemma 5 for the regret after.

In this section, building on top of Algorithm LABEL:alg:REOLB, we develop another algorithm that enjoys similar regret guarantees in the stochastic or corrupted setting, and additionally guarantees $\widetilde{\mathcal{O}}(\sqrt{T})$ regret in the adversarial setting, without having any prior knowledge on which environment it is facing. To the best of our knowledge, this kind of best-of-three-worlds guarantee only appears before for multi-armed bandits (Wei & Luo, 2018; Zimmert & Seldin, 2019) and Markov decision processes (Jin & Luo, 2020), but not for linear bandits.

Our algorithm requires a block-box access to an adversarial linear bandit algorithm $\mathcal{A}$ that satisfies the following:

Eq. (5) states that the regret of $\mathcal{A}$ against action $x$ is bounded by a $\sqrt{t}$-order term minus the deviation between the loss of $x$ and its estimator. While this might not seem intuitive, in fact, all existing linear bandit algorithms with a near-optimal high-probability bound satisfy Assumption 1, even though this may not have been stated explicitly (and one may need to slightly change the constant parameters in these algorithms to satisfy the conditions on $C_{1}$ and $C_{2}$). Below, we give two examples of such $\mathcal{A}$ and justify them in Appendix E.

• •

  A variant of GeometricHedge.P (Bartlett et al., 2008) with an improved exploration scheme satisfies Assumption 1 with ($\delta^{\prime}=\delta/(|\mathcal{X}|\log_{2}T)$)

  $$C_{1}=\Theta\left(d\,{\log(T/\delta^{\prime})}\right),\ \ L_{0}=\Theta\left(d\,{\log^{2}(T/\delta^{\prime})}\right).$$

• •

  The algorithm of (Lee et al., 2020) satisfies Assumption 1 with ($\lg=\log(dT)$, $\delta^{\prime\prime}=\delta/(|\mathcal{X}|T)$)

  $$C_{1}=\Theta\left(d^{6}\lg^{8}{\log(\lg/\delta^{\prime\prime})}\right),\ \ L_{0}=\Theta\left(\log(\lg/\delta^{\prime\prime})\right).$$

With such a black-box at hand, our algorithm BOTW is shown in Algorithm 1. We first present its formal guarantees in different settings.

Therefore, Algorithm 1 enjoys the nearly instance-optimal regret $\mathcal{O}(c(\mathcal{X},\theta)\log^{2}T)$ in the stochastic setting as Algorithm LABEL:alg:REOLB⁴⁴4Note that when we choose $\mathcal{A}$ as the variant of GeometricHedge.P, $\frac{C_{1}\sqrt{\log T}}{\Delta_{\min}}=\mathcal{O}\left(\frac{d}{\Delta_{\min}}\log^{\frac{3}{2}}T\right)$ which is dominated by the term $\mathcal{O}(c(\mathcal{X},\theta)\log^{2}T)$ when $T$ is sufficiently large., but slightly worse regret $\mathcal{O}(\frac{d\log^{2}T}{\Delta_{\min}}+C)$ in the corrupted setting (recall again $c(\mathcal{X},\theta)\leq d/\Delta_{\min}$). In exchange, however, Algorithm 1 enjoys the following worst-case robustness in the adversarial setting.

The dependence on $T$ in this bound is minimax-optimal as mentioned, while the dependence on $d$ depends on the coefficient $C_{1}$ of the black-box. Note that because of this adversarial robustness, the $\log^{2}T$ dependence in Theorem 6 turns out to be unavoidable, as we show in Theorem 27. In addition, Theorem 7 also works for the stochastic setting, which implies a regret bound of $\mathcal{O}(\sqrt{dT}\log(T|\mathcal{X}|\log_{2}T/\delta))$. This is a factor of $\sqrt{d}$ better than the guarantee of Algorithm LABEL:alg:REOLB shown in Theorem 2.

Next, in Section 5.1, we describe our algorithm in detail. Then in Section 5.2 and Section 5.3, we provide proof sketches for Theorem 7 and Theorem 6 respectively.

In this work, we make significant progress on improving the robustness and adaptivity of linear bandit algorithms. Our algorithms are the first to achieve near-optimal regret in various different settings, without having any prior knowledge on the environment. Our techniques might also be useful for more general problems such as linear contextual bandits.

In light of the work (Zimmert & Seldin, 2019) for multi-armed bandits that shows a simple Follow-the-Regularized-Leader algorithm achieves optimal regret in different settings, one interesting open question is whether there also exists such a simple Follow-the-Regularized-Leader algorithm for linear bandit with the same adaptivity to different settings. In fact, it can be shown that their algorithm has a deep connection with OP in the special case of multi-armed bandits, but we are unable to extend the connection to general linear bandits.

We thank Tor Lattimore and Julian Zimmert for helpful discussions. HL thanks Ilias Diakonikolas and Anastasia Voloshinov for initial discussions in this direction. The first four authors are supported by NSF Awards IIS-1755781 and IIS-1943607.