Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits

## Abstract

Abstract We study the optimal batch-regret tradeoff for batch linear contextual bandits. For both context-blind and context-aware settings, we design batch learning algorithms and prove that they achieve the optimal regret bounds (up to logarithmic factors) for
any batch number M 𝑀 M , number of actions K 𝐾 K , time horizon T 𝑇 T , and dimension d 𝑑 d . Therefore, we establish the full-parameter-range (almost) optimal batch-regret tradeoff for the batch linear contextual bandit problem. Compared to the recent work (Ruan et al., 2021 ) which showed that M = O ​ ( log ⁡ log ⁡ T ) 𝑀 𝑂 𝑇 M=O(\log\log T) batches (in the context-blind setting) suffice to achieve the asymptotically minimax-optimal regret without the batch constraints, our algorithm is simpler and easier for practical implementation. Furthermore, our algorithm achieves the optimal regret for all T ≥ d 𝑇 𝑑 T\geq d , while (Ruan et al., 2021 ) requires that T 𝑇 T greater than an unrealistically large polynomial of d 𝑑 d . Along our analysis, we also prove a new matrix concentration inequality with dependence on their dynamic upper bounds, which, to the best of our knowledge, is the first of its kind in literature and maybe of independent interest.

## 1 Introduction

Online learning and decision-making is an important aspect of machine learning. In contrast to the traditional batch machine learning where the learner only passively observes the data, an online learner may interact with the data collection process by deciding on which data point to query about. On one hand, sequentially making active queries may fully utilize the power of adaptivity based on the observed data and help to achieve better data efficiency. On the other hand, in many practical scenarios, it is also desirable to limit these queries to a small number of rounds of interaction, which helps to increase the parallelism of the learning process, and reduce the management cost and the total time span. In light of this, the *batch online learning* model, which is a combination of the two major aspects of machine learning, has recently attracted much research attention. It has been shown that for many popular online learning tasks, a very small number of batches may achieve nearly minimax-optimal learning performance, and therefore it is possible to enjoy the benefits of both adaptivity and parallelism.

To understand the impact of the batch constraint to online learning and decision-making problems, in this paper, we study the optimal batch algorithms for the *linear contextual bandit* problem, where the latter is a central problem in online learning literature. In a linear contextual problem, the learning algorithm observes a *context* (also referred to as a *context set* as we usually have one context vector for each candidate action) at the beginning of each time period, and the expected reward of each candidate action is determined by a hidden linear function of the context. The learning algorithm has to learn the linear function and maximize its total reward overall all time periods. The readers may refer to Section [2](#S2) for the detailed problem definition. The linear contextual bandit problem is widely studied due to its simplicity and abstraction (via the context) for the personalized treatment in decision-making, enabling plenty of real-world applications such as advertisement selection, recommendation systems, and clinical trials.

##### Context-blind Batch Learning.

One practical reason that calls for the batch online learning model is due to the *expensive policy deployment and communication cost*. Large-scale online advertisement or recommendation systems (Li et al., ) may have to take a long time or pay an expensive overhead cost to update their policies. In many distributed or offline scenarios (such as designing and updating the policy for autonomous vehicles or robotic arms), such an overhead cost becomes even more significant. During the execution of the policy, we usually may not be able to monitor the process (e.g., the data collected from the environment) in real time, due to the high communication cost and latency in the distributed (or large-scale) system. In such cases, the learning algorithm seeks to minimize the number of policy updates. In the batch online learning model, we refer to the time of each policy update as the beginning of a *batch*. The learning algorithm may decide the policy only based on the data collected from the previous batches, and the data collected from the current batch may only be available at the end of the batch. Due to the non-real-time natural, the learning algorithm also has to decide the length of each batch when the batch begins, without any information from the current batch.

We formalize the above intuition and define the context-blind batch complexity of the linear contextual bandit problem as follows. Note that the *context-blind setting* means that the policy of each batch may not depend on the contexts observed in the same batch, due to the communication cost and latency.

###### Definition 1 (Batch complexity in the context-blind setting) .

We first formally define that a *policy* $\pi$ is a mapping from the context space to the set of the distributions over all candidate actions. To *execute* a policy $\pi$ at time step $t$ means to randomly sample and commit to an action from the distribution $\pi(X_{t})$ where $X_{t}$ is the context observed at time $t$.

For a linear contextual bandit problem with time horizon $T$, we say that the *batch complexity* of a learning algorithm is (at most) $M$ in the *context-blind setting*, if the learner decides $T_{1}$ and $\pi_{1}$ before the learning process starts, and executes $\pi_{1}$ in the first $T_{1}$ time steps (which corresponds the first batch).
Based on the data (context sets, played actions and the rewards) obtained from the first $T_{1}$ steps, the learner then decides $T_{2}$ and $\pi_{2}$, and executes $\pi_{2}$ for $T_{2}$ time steps (the second batch). The learner repeats the process for $M$ times/batches. In general, at the beginning of the $k$-th batch, the learner decides $T_{k}$ (the size of the batch) and $\pi_{k}$ based on the data collected from the first $(k-1)$ batches. The batch sizes should satisfy that $\sum_{k=1}^{M}T_{k}=T$.

###### Definition 1 (Batch complexity in the context-blind setting) .

##### Context-aware Batch Learning.

In many other practical scenarios, the batch online learning model is needed only because of the *delayed reward observation*. A typical example of batch online learning is clinical trials (Lei et al., ; Almirall et al., , ), as all clinical trials run in phases (which exactly correspond to the batches) in order to parallelize the time-consuming treatment experiments. Similar example arises in crowdsourcing where it takes significant time to interact with the crowd and the queries may be aggregated into a small number of batches for the crowd to answer so as to save the total time cost. In these examples, at the beginning of each batch, the learner may additionally observe the contexts of the current batch (in the clinical trial example, these contexts correspond to the information of the patients recruited in the current phase).
In light of this, we define the context-aware batch complexity where the learner may choose the policy based on this additional context information.

###### Definition 2 (Batch complexity in the context-aware setting) .

For a linear contextual bandit problem with time horizon $T$, we say that the *batch complexity* of a learning algorithm is (at most) $M$ in the *context-aware setting*, if at the beginning each batch $k\in\{1,2,\dots,M\}$, the learner decides the batch size $T_{k}$, and then observes the context sets of the future $T_{k}$ time steps. After that, the learner decides the policy $\pi_{k}$ based on the data obtained from the previous $(k-1)$ batches and the context sets of the future $T_{k}$ time steps, and executes $\pi_{k}$ at all these $T_{k}$ time steps. The batch sizes should satisfy that $\sum_{k=1}^{M}T_{k}=T$.

Naturally, there is a tradeoff between the batch complexity and the regret performance in batch online learning. There have been quite a few recent works studying such relationship for multi-armed bandits (Perchet et al., ; Gao et al., ; Esfandiari et al., ). In multi-armed bandits, because there is no context information, the context-blind and context-aware settings defined above are identical. Gao et al. () proved optimal regret bound for every number of batches and show that $M=O(\log\log T)$ batches suffice to achieve the minimax-optimal regret without the batch constraint.

Han et al. (); Ruan et al. () recently studied the batch algorithms for linear contextual bandits. While Han et al. () studied a special case of the problem where the contexts follow Gaussian-type distributions, Ruan et al. () provided an algorithm for all context distributions. In particual, Ruan et al. () showed that in the context-blind setting, $M=O(\log\log T)$ batches suffice to achieve the minimax-optimal regret without the batch constraint, which implies the same asymptotic bound for the context-aware setting.(^2^22Both the $O(\log\log T)$ bound in (Ruan et al., ) and our work (as well as (Han et al., )) focus on the *stochastic-context case* of linear contextual bandits, which is the most technically interesting and practically useful setting of batch linear contextual bandits. Please refer to Section [1.2.1](#S1.SS2.SSS1) for more discussion.)

While the exact batch-regret tradeoff for multi-armed bandits is relatively better understood (and arguably easier to study), the optimal tradeoff curve for linear contextual bandits is more challenging and remains open.

In this work, we address this question on the exact batch-regret curve and prove the optimal regret (up to logarithmic factors) for batch linear contextual bandits for the *full range* of the problem parameters in both context-blind and context-aware settings. Compared to previous work (Ruan et al., ), our algorithm is simpler to describe and therefore easier to be practically implemented. Our algorithm is optimal for all $M\geq 1$ and works for a much wider range of $T$, while in comparison, (Ruan et al., ) requires that $T$ greater than an impractically large polynomial of the dimension parameter $d$. Below, we provide a more concrete summary of our contributions and comparison with the related works.

###### Definition 2 (Batch complexity in the context-aware setting) .

### 1.1 Our Contributions and Technical Ingredients

#### 1.1.1 Optimal Context-blind Batch-Regret Tradeoff

We first study the optimal batch algorithm for stochastic linear contextual bandits in the context-blind setting.

Recall that Gao et al. () showed that for multi-armed bandits, the optimal regret using at most $M$ batches is at the order of $T^{\frac{1}{2-2^{-M+1}}}$ (ignoring the polynomial dependence on other problem parameters and the poly-logarithmic dependence on $T$). For batch linear contextual bandits in the context-blind, we establish a similar (but slightly trickier) tradeoff. More specifically, we design Algorithm [1](#alg1) (in Section [4](#S4)), and prove the following regret upper bound.

###### Theorem 1 .

Let $d$ be the dimension of the feature space and $K$ be the number of candidate arms.
For any $T\geq d$ and $M\geq 1$, Algorithm [1](#alg1) may use at most $M$ batches in the context-blind setting and its regret $R_{T}$ is bounded by(^3^33Throughout the paper, the $\tilde{O}(\cdot)$ and $\tilde{\Omega}(\cdot)$ notations hide the logarithmic factors of $T$, $d$, and $K$.)

$$ $\displaystyle R_{T}\leq\tilde{O}\left(\min\left\{T^{\frac{1}{2-2^{-M+2}}}d^{\frac{1-2^{-M+2}}{2-2^{-M+2}}},T^{\frac{1}{2-2^{-M+1}}}d^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}\min\{K,d\}^{\frac{2^{-M+1}}{2-2^{-M+1}}}\right\}\right).$ $$

Note that the regret upper bound in Theorem [1](#Thmtheorem1) takes the minimum between two terms. When $T$ is comparably large (e.g., $T\geq\tilde{\Omega}(d\min\{K,d\}^{2-2^{-M+2}})$, the second term in our upper bound is smaller, and its asymptotic dependence on $T$ matches the optimal bound for batch multi-armed bandits (Gao et al., ).(^4^44However, this does not mean that the batch linear contextual bandit problem is easier than batch multi-armed bandits, as the dependence on $K$ and $d$ is worse.) On the other hand, when $T$ is relatively small (e.g., $T\leq\tilde{O}(d\min\{K,d\}^{2-2^{-M+2}})$), a simpler analysis would kick in to give a better regret bound, which results as the first term.

When there are no constraints on the number of batches, it is well known that the minimax-optimal regret is $\sqrt{dT\log K}\times\mathrm{poly}\log T$ (see, e.g., (Dani et al., ; Chu et al., ; Li et al., )). Ruan et al. () showed that with only $M=\lceil\log\log T\rceil+1$ batches (the logarithms are of base 2), their batch algorithm may match the regret performance (up to logarithmic factors) as the no-batch-constraint setting. The following simple corollary of our Theorem [1](#Thmtheorem1) recovers the main result of (Ruan et al., ). Moreover, the batch algorithm in (Ruan et al., ) only works for $T\geq\tilde{\Omega}(d^{32})$, while in contrast, our Corollary [1](#Thmcorollary1) works for every $T\geq d$ (and note that $T<d$ is the trivial scenario).

###### Corollary 1 .

For $T\geq d$ and $M=\left\lceil\log\log(T)\right\rceil+1$, the expected regret of Algorithm [1](#alg1) is
$R_{T}\leq\tilde{O}(\sqrt{Td})$.

While the two-phase regret curve in Theorem [1](#Thmtheorem1) may seem completely due to technicality, it surprisingly turns out to be exactly optimal. In Section [7](#S7), we complement Theorem [1](#Thmtheorem1) with the following lower bound.

###### Theorem 2 .

Fix any $K\geq 2$, $T\geq d$, and any batch number $M\geq 1$. For any learning algorithm with batch complexity $M$ in the context-blind setting, there exists a linear contextual bandit problem instance with dimension $d$ and $K$ arms, such that the expected regret $R_{T}$ is at least

$$ $R_{T}\geq\tilde{\Omega}\left(\min\left\{T^{\frac{1}{2-2^{-M+2}}}d^{\frac{1-2^{-M+2}}{2-2^{-M+2}}},T^{\frac{1}{2-2^{-M+1}}}d^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}\min\{K,d\}^{\frac{2^{-M+1}}{2-2^{-M+1}}}\right\}\right).$ $$

We note that the above upper and lower bounds match (up to factors logarithmic in $T$, $d$, and $K$) for all $M\leq\lceil\log\log T\rceil$ and all non-trivial parameter settings for $T$, $d$, and $K$. When $M>\lceil\log\log T\rceil$, by Corollary [1](#Thmcorollary1), our Algorithm [1](#alg1) already achieves the unconstrained minimax-optimal regret (up to logarithmic factors). Therefore, we achieve near-optimal regret bounds for (context-blind) batch linear contextual bandits in the context-blind setting under all non-trivial parameter settings.

We also note that the regret lower bound established by Gao et al. () for $K$-arm $M$-batch multi-armed bandits is $\Omega(\sqrt{K}T^{\frac{1}{2-2^{-M+1}}})$ (which also matches their algorithm up to logarithmic factors). If we treat multi-armed bandits as a special case of linear contextual bandits with $K=d$ arms with orthogonal features, the lower bound for batch linear contextual bandits implied by (Gao et al., ) is weaker than our Theorem [2](#Thmtheorem2). This gap demonstrates that intrinsic additional difficulty of the context-blind batch linear contextual bandit problem when compared to its multi-armed bandit counterpart, marking a separation between the two problems.

###### Theorem 1 .

###### Corollary 1 .

###### Theorem 2 .

#### 1.1.2 Single-Batch Learning for the Exploration Policy

At the core of our main algorithm is a new single-batch (i.e., offline) procedure, named ExplorationPolicy, to learn an exploration policy to achieve the *distributional G-optimality* in experimental designs. Let $D$ be an unknown distribution over the context sets and given a set of $m$ independent samples drawn from $D$, the goal of our ExplorationPolicy is to compute a policy $\pi$, so that if one uses $\pi$ to collect $n$ more data points(^5^55Here, given a context $X\sim D$, a data point is collected by playing the action $\pi(X)$ and observing the reward. Please refer to Section [2](#S2) for the detailed formulation of linear contextual bandits.) and estimate the underlying linear model $\boldsymbol{\theta}$, the expected size of the largest confidence interval among the actions in a random context set will be small. Note that if the context set is deterministic, this objective corresponds to (the square root of) the G-optimality criterion in classical experimental designs (see, e.g., (Pukelsheim, ; Atkinson et al., )). For stochastic context sets, the objective was recently found closely related to linear contextual bandits and studied by (Ruan et al., ; Zanette et al., ).

Our ExplorationPolicy procedure is employed during each batch of the main algorithm to decide the policy used in the next batch. This procedure is very similar to Algorithm 2 in (Ruan et al., ). However, the difference is that Ruan et al. () only used their Algorithm 2 to prove the existence of a good exploration policy and designed several more complicated procedures (such as CoreLearning and CoreIdentification) for the policy learning. In contrast, thanks to a few new algorithmic techniques (e.g., the *scaled-and-clipped update rule* to be explained in Section [3.1](#S3.SS1)) and a new matrix concentration inequality (to be introduced in Section [1.1.3](#S1.SS1.SSS3)), our algorithm can directly learn the desired exploration policy with better performance, and is simpler to describe and implement.

We also note that in the concurrent work (Zanette et al., ), the authors studied a similar task to our ExplorationPolicy. In Section [3.1](#S3.SS1), we compare our performance guarantee and the results in (Zanette et al., ), and demonstrate the superiority of our procedure.

#### 1.1.3 A New Matrix Concentration Inequality with Dynamic Upper Bounds

Existing matrix concentration inequalities (see, e.g., (Tropp, )) play an important role in recent works on batch linear contextual bandits (Ruan et al., ; Zanette et al., ). For example, the proof techniques of Theorem 5.1 in (Tropp, ) may yield the following concentration bound in Proposition [1](#Thmproposition1) (and the upper bound on $\sum_{k}X_{k}$ may be similarly derived). Special cases of Proposition [1](#Thmproposition1) (taking $W=\mathbf{I}$ and $\epsilon=\mathrm{const.}$) includes Lemma 21 in (Ruan et al., ) and Lemmas 11 & 12 in (Zanette et al., ).

###### Proposition 1 .

Consider a sequence of independent PSD matrices $X_{1},X_{2},\ldots,X_{n}\in\mathbb{R}^{d\times d}$ such that $X_{k}\preccurlyeq W$ for a fixed PSD matrix $W$ and all $1\leq k\leq n$.
There exists a universal constant $c>0$ such that for every $\delta>0$ and $\epsilon\in(0,1)$, it holds that

$$ $\displaystyle\Pr\left[\sum_{k=1}^{n}X_{k}\preccurlyeq(1+\epsilon)\sum_{k=1}^{n}\mathbb{E}[X_{k}]+\frac{c\ln(d/\delta)}{\epsilon}W\right]\geq 1-\delta;$ (1) $\displaystyle\Pr\left[\sum_{k=1}^{n}X_{k}\succcurlyeq(1-\epsilon)\sum_{k=1}^{n}\mathbb{E}[X_{k}]-\frac{c\ln(d/\delta)}{\epsilon}W\right]\geq 1-\delta.$ (2) $$

However, to achieve the optimal batch-regret tradeoff in the context-blind setting, we need a stronger version of Proposition [1](#Thmproposition1) where the uniform upper bound matrix $W$ may be stochastic. In particular, we prove the following lemma as a crucial technical tool in our algorithm analysis (especially for the ExplorationPolicy procedure).

###### Lemma 1 .

Consider a sequence of stochastic PSD matrices $W_{1},X_{1},W_{2},X_{2},\dots,W_{n},X_{n}\in\mathbb{R}^{d\times d}$. Let $\mathcal{F}_{k}=\sigma(W_{1},X_{1},W_{2},X_{2},\dots,W_{k-1},X_{k-1})$ and $\mathcal{F}_{k}^{+}=\sigma(W_{1},X_{1},W_{2},X_{2},\dots,W_{k-1},X_{k-1},W_{k})$ be the natural filtration and $Y_{k}=\mathbb{E}[X_{k}|\mathcal{F}_{k}^{+}]$ for each $k\in\{1,2,\dots,n\}$. Suppose $W_{k}$ is PD and increasing in $k$ (with respect to the semidefinite order) and $X_{k}\preccurlyeq W_{k}$ for each $k$. For every $\delta>0$ and $\epsilon\in(0,1)$, we have that

$$ $\displaystyle\Pr\left[\sum_{k=1}^{n}X_{k}\preccurlyeq(1+\epsilon)\sum_{k=1}^{n}Y_{k}+\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}\ln((n+1)d/\delta)W_{n}\right]\geq 1-\delta;$ (3) $\displaystyle\Pr\left[\sum_{k=1}^{n}X_{k}\succcurlyeq(1-\epsilon)\sum_{k=1}^{n}Y_{k}-\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}\ln((n+1)d/\delta)W_{n}\right]\geq 1-\delta.$ (4) $$

In Lemma [1](#Thmlemma1), the stochastic matrix $W_{n}$ upper bounds all matrices in $\{X_{1},X_{2},\dots,X_{n}\}$. When it is fixed, the lemma reduces to Proposition [1](#Thmproposition1).(^6^66Indeed, we lose an additional $\ln(n+1)$ term in the $\ln(d/\delta)$ terms in Proposition [1](#Thmproposition1), and we do not know if this compromise is necessary.) There are also a few Freedman’s inequalities for matrix martingales (see, e.g., (Tropp, )). However, in these inequalities, while the quadratic variation $\mathbb{E}[X_{i}^{2}|\mathcal{F}_{i}^{+}]$ becomes dynamic, the uniform upper bound $W_{k}$ is still fixed.

We note that if an extra $\mathrm{poly}(d)$ factor were allowed in the $\pm\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}\ln((n+1)d/\delta)W_{n}$ terms, the lemma would easily follow from Proposition [1](#Thmproposition1) and an $\epsilon$-net argument. However, reducing these $\mathrm{poly}(d)$ factors is crucial to the *full parameter range* optimality analysis of our batch algorithm.

The full proof of Lemma [1](#Thmlemma1) is presented in Section [6](#S6).
We believe that Lemma [1](#Thmlemma1) is a non-trivial addition to the vast family of matrix concentration inequalities and may be of its own interest.

###### Proposition 1 .

###### Lemma 1 .

#### 1.1.4 Optimal Context-aware Batch-Regret Tradeoff

Note that any context-blind batch learning algorithm also meets the definition of the context-aware algorithm with the same batch complexity. However, the learning algorithm may take the advantage of the additional context information in each batch to improve the regret. Using the same techniques developed above, we prove the following regret upper bound for context-aware batch learning in Section [8](#S8).

###### Theorem 3 .

In the context-aware batch learning setting, for any $T\geq d$ and $M\geq 1$, Algorithm [3](#alg3) uses at most $M$ batches and its regret $R_{T}$ is bounded by

$$ $\displaystyle R_{T}\leq\tilde{O}\left(T^{\frac{1}{2-2^{-M+1}}}d^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}\right).$ $$

The regret upper bound in Theorem [3](#Thmtheorem3) is achieved by slightly adjusting our optimal algorithm for the context-blind case as well as the batch sizes. Also in Section [8](#S8), we prove that the batch-regret trade-off achieved in Theorem [3](#Thmtheorem3) is optimal.

###### Theorem 4 .

Fix any $K\geq 2$, $T\geq d$, and any batch number $M\geq 1$. For any learning algorithm with batch complexity $M$ in the context-aware setting, there exists a linear contextual bandit problem instance with dimension $d$ and $K$ arms, such that the expected regret $R_{T}$ is at least

$$ $R_{T}\geq\tilde{\Omega}\left(T^{\frac{1}{2-2^{-M+1}}}d^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}\right).$ $$

Theorem [4](#Thmtheorem4) is proved by a simple adaptation from the proof of the lower bound theorem for the context-blind setting (Theorem [2](#Thmtheorem2)). Comparing our bound with the optimal regret bound $\tilde{\Theta}(\sqrt{K}T^{\frac{1}{2-2^{-M+1}}})$ for $K$-arm $M$-batch multi-armed bandits (Gao et al., ), we see that the order on $T$ are the same. The different dependence on $K$ and $d$ is due to the slightly different problem setting – in (Gao et al., ), the expected rewards of the arms may be as large as $\sqrt{K}$ and in our paper we assume that they are bounded by $[-1,1]$.

###### Theorem 3 .

###### Theorem 4 .

### 1.2 Related Works

#### 1.2.1 Linear Contextual Bandits

The linear contextual bandit problem
(Abe and Long, ; Auer et al., ) studies the bandit problem where the actions are associated with (known) features and their mean rewards are defined by an (unknown) linear function of the associated features. Compared with the multi-armed bandit problem, the linear structure on features could help the learner to infer the mean reward of an action given the observation on the other actions, and therefore enables the possibility to achieve regret upper bounds independent from (or weakly dependent on) the number of actions.

There are generally two types of problem settings studied about linear contextual bandits: *non-adaptive contexts* and *adaptive contexts*. In the non-adaptive-context setting, the context sets are independent from all other randomnesses (including the randomnesses in rewards and used by the algorithm). One can also think of this as that the contexts are fixed (by an adversary) before the learning process starts. In this setting, the optimal minimax regret bound is $\Theta(\sqrt{dT\min\{d,\ln(K)\}})$ up to $\mathrm{poly}\ln(T)$ factors (Auer et al., ; Abe et al., ; Dani et al., ; Chu et al., ; Abbasi-Yadkori et al., ; Li et al., ). In the adaptive-context setting, the context sets are chosen by an adaptive adversarial, where the context sets at any time step may depend on the outcomes and the learner’s decisions in previous time steps. In this setting, the problem becomes harder for the learner. To the best of our knowledge, the state-of-the-art regret upper bound for the adaptive-context setting is $O(d\sqrt{T\ln(KT)})$ (Abbasi-Yadkori et al., ).

In this work (as well as the most related works (Han et al., ; Ruan et al., ; Zanette et al., ) on batch linear contextual bandits), we focus on a particularly useful case in the non-adaptive-context setting, namely the *stochastic contexts*. In this case, the context sets at each time step are independently generated from a pre-defined (but unknown) distribution $D$. In many real-world applications such as clinical trial and recommendation system, the patients or customers can often be viewed as independent samples from the population and therefore stochastic contexts are a natural abstraction of these practical scenarios. On the other hand, Han et al. () has shown that even in the non-adaptive-context setting, in the worst case, as many as $\Omega(\sqrt{T})$ batches are needed to achieve any $\sqrt{T}$-type regret, which is less useful in practice.

#### 1.2.2 Bandit Learning with Limited Adaptivity

Batch learning fits into the broader *learning with limited adaptivity* framework that recently attracts much research attention due to its potentially lower computational cost and close relation to distributed and parallel learning.

The number of batches is a natural measurement of the adaptivity needed by the learner. Besides the above mentioned works (Perchet et al., ; Gao et al., ) (for batch multi-armed bandits) and (Ruan et al., ) (for batch linear contextual bandits), Han et al. () studied batch linear contextual bandits with Gaussian-type features and Esfandiari et al. () studied batch adversarial multi-armed bandits.

Besides batch learning, another type of adaptivity measurement studied in literature is the policy switching cost, where the learner may monitor the sequential decisions but would like to change his/her decision policy as infrequently as possible. This is a comparably more lenient constraint, as a batch algorithm has a small number of policy switches equal to the number of batches. For the adversarial multi-armed bandit problem, Kalai and Vempala () and Geulen et al. () established a minimax regret bound of $\tilde{\Theta}(\sqrt{T})$ under the full information feedback; Dekel et al. () later showed that the minimax regret bound is $\Theta(T^{\frac{2}{3}})$ under the bandit feedback. Simchi-Levi and Xu () studied the switching cost of stochastic multi-armed bandits. For linear contextual bandits, it was shown that to achieve the $\sqrt{T}$-type regret, the optimal bound for switching cost is $d\log T$, up to $\mathrm{poly}\log(d\log T)$ factors (Abbasi-Yadkori et al., ; Ruan et al., ).

### 1.3 Organization

The rest of the paper is organized as follows. In Section [2](#S2) we introduce the batch linear bandit problem and some notations.
Then we introduce our main technical contributions and proof ideas in Section [3](#S3).
Section [4](#S4) is devoted to describing our main algorithm for the context-blind setting and the proof of its regret analysis (Theorem [1](#Thmtheorem1)). In Section [5](#S5), we describe the key procedure ExplorationPolicy and present its analysis. In Section [6](#S6), we prove our new matrix concentration inequality (Lemma [1](#Thmlemma1)). In Section [7](#S7), we present the proof of the lower bound for the context-blind setting (Theorem [2](#Thmtheorem2)). In Section [8](#S8), we extend our results and prove the regret upper and lower bounds for the context-aware setting (Theorem [3](#Thmtheorem3) and Theorem [4](#Thmtheorem4)). Finally, we conclude the paper in Section [9](#S9).

## 2 Preliminaries

##### Linear Contextual Bandits with Stochastic Context Sets.

We consider the linear contextual bandit problem with the hidden linear model described by the $d$-dimensional vector $\boldsymbol{\theta}:\|\boldsymbol{\theta}\|_{\infty}\leq 1$. There is also a distribution $D$ over the context sets hidden from the learner. Given the time horizon $T$, during each time step $t\in\{1,2,\dots,T\}$, a stochastic context set of $K$ feature vectors, $X_{t}=\{\boldsymbol{x}_{t,1},\boldsymbol{x}_{t,2},\dots,\boldsymbol{x}_{t,K}\}$ is drawn from $D$ and revealed to the learner. The feature vectors are in $\mathbb{R}^{d}$ and $D$ guarantees that $\forall i\in\{1,2,\dots,K\}:|\boldsymbol{x}_{t,i}^{\top}\theta|\leq 1$ almost surely.(^7^77Note that our formulation is more general than the usual linear contextual bandits setting where $\|\boldsymbol{\theta}\|_{2}\leq 1$ and $\|\boldsymbol{x}_{t,i}\|_{2}\leq 1$. It also includes $K$-armed multi-armed bandits as a special case.)

The learner has to choose and play an action (defined by its associated feature vector) $\boldsymbol{y}_{t}\in X_{t}$ and receives the reward $r_{t}=\boldsymbol{y}_{t}^{\top}\boldsymbol{\theta}+\epsilon_{t}$, where $\epsilon_{t}$ is an independent sub-Gaussian noise with zero mean and variance proxy bounded by $1$. The goal of the learner is to minimize the total (expected) regret

$$ $R_{T}:=\mathbb{E}\left[\sum_{t=1}^{T}\left(\max_{i}\{\boldsymbol{x}_{t,i}^{\top}\boldsymbol{\theta}\}-\boldsymbol{y}_{t}^{\top}\boldsymbol{\theta}\right)\right].$ $$

##### Batch Learning.

Given the batch complexity $M$, a batch learning algorithm aims at minimize the regret $R_{T}$ defined above, subject to the constraints in Definition [1](#Thmdefinition1) and Definition [2](#Thmdefinition2) for the context-blind and context-aware settings respectively.

##### Notations.

For any non-negative integer $N$, we let $[N]$ denote $\{1,2,\ldots,N\}$. We use $\mathbb{E}_{\mathcal{P}}[\cdot]$ and $\mathrm{Pr}_{\mathcal{P}}[\cdot]$ to denote the expectation and probability over the distribution $\mathcal{P}$ respectively. We use $\mathbf{I}$ to denote the $d$-dimensional identity matrix. We use $\log$ to denote the logarithm base $2$, and use $\ln$ to denote the logarithm base $e$. We also define $\mathcal{T}_{0}=T_{0}=0$ and $\mathcal{T}_{k}=\sum_{i=1}^{k}T_{i}$ for $1\leq k\leq M$.

## 3 Technical Overviews

### 3.1 Upper Bounds

Since our algorithms for the both context-blind and context-aware settings are similar and adopt the same techniques, we present the technical overview based on the context-blind version. Our algorithms are elimination-based, following (Ruan et al., ). At each time step $t$, give the set of context vectors $X_{t}=\{\boldsymbol{x}_{t,1},\boldsymbol{x}_{t,2},\ldots,\boldsymbol{x}_{t,K}\}$, we maintain a confidence interval $\mathcal{I}_{t,i}$ for $\boldsymbol{x}_{t,i}^{\top}\theta$ for each $i$. A candidate action $\boldsymbol{x}_{t,i}$ is eliminated when there exists another candidate action $\boldsymbol{x}_{t,i^{\prime}}$ such that $\mathcal{I}_{t,i^{\prime}}$ entirely lies above $\mathcal{I}_{t,i}$, meaning that the action $\boldsymbol{x}_{t,i}$ cannot be the optimal action. Then, the clever part of the policy is to decide a distribution over the remaining candidate actions and randomly choose one to commit to according to the distribution.

For the construction of the confidence intervals, we adopt the classical elliptical confidence intervals based on the regularized ordinary least-square (OLS) estimation (Chu et al., ). Given a group of context vectors that are played in history $\{\boldsymbol{y}_{\tau}\}_{\tau=1}^{t}$ and corresponding observed rewards $\{r_{\tau}\}_{\tau=1}^{t}$ (such that $r_{\tau}=\boldsymbol{y}_{\tau}^{\top}\boldsymbol{\theta}+\epsilon_{\tau}$ where $\epsilon_{\tau}$ is an $1$-subgaussian noise), we construct the confidence interval for any candidate action with context vector $\boldsymbol{x}$ to be

$$ $\displaystyle\mathcal{I}(\boldsymbol{x},\Lambda)=\left[\boldsymbol{x}^{\top}\hat{\boldsymbol{\theta}}-\alpha\sqrt{\boldsymbol{x}^{\top}\Lambda^{-1}\boldsymbol{x}},\boldsymbol{x}^{\top}\hat{\boldsymbol{\theta}}+\alpha\sqrt{\boldsymbol{x}^{\top}\Lambda^{-1}\boldsymbol{x}}\right]\bigcap[-1,1],$ (5) $$

with $\Lambda=\lambda\mathbf{I}+\sum_{\tau=1}^{t}\boldsymbol{y}_{\tau}\boldsymbol{y}_{\tau}^{\top}$ is the *regularized information matrix*, $\hat{\boldsymbol{\theta}}=\Lambda^{-1}\sum_{\tau=1}^{t}r_{\tau}\boldsymbol{y}_{\tau}$ is the regularized OLS estimation of the hidden vector $\boldsymbol{\theta}$, and $\alpha,\lambda$ are hyper-parameters satisfying that $\alpha=\Theta(\sqrt{\ln(KdT)}+\lambda\sqrt{d})$.

Define

$$ $w(\boldsymbol{x},\Lambda)=\min\left\{(\sqrt{\ln(KdT)}+\lambda\sqrt{d})\sqrt{\boldsymbol{x}^{\top}\Lambda^{-1}\boldsymbol{x}},1\right\}$ $$

to be the *width* of the confidence interval $\mathcal{I}(\boldsymbol{x},\Lambda)$. To reduce the regret, we would like to design policies to cleverly perform exploration in order to reduce the width of future estimations. Formally, we introduce the following problem which is the key to our optimal batch learning algorithm.

The Problem of Single-Phase Learning for Exploration Policy.
Fix $m,n\geq 0$. Let $\{X_{i}\}_{i=1}^{m},\{Y_{j}\}_{j=1}^{n}$ be two groups of *i.i.d.* context sets following the same unknown distribution $D$. After observing $\{X_{i}\}_{i=1}^{m}$, we are asked to design the parameter $\lambda$ and an exploration policy $\pi$ so as to minimize the following expected maximum width

$$ $\text{\rm EM-width}(D,\Lambda):=\mathop{\mathbb{E}}_{X\sim D}[\max_{\boldsymbol{x}\in X}w(\boldsymbol{x},\Lambda)],$ $$

where $\Lambda=\lambda\mathbf{I}+\sum_{j=1}^{n}\boldsymbol{y}_{j}\boldsymbol{y}_{j}^{\top}$ and $\boldsymbol{y}_{j}\sim\pi(Y_{j})$ for all $1\leq j\leq n$.

In our batch learning algorithm, we need to solve the above problem once during each batch. During the $k$-th batch, we let $D=D_{k}$ be the distribution of the set of the remaining context vectors after the elimination process based on the information learned for the first $(k-1)$ batches. $\{X_{i}\}_{i=1}^{m}$ is obtained from the $(k-1)$-th batch, and we solve the above problem for $\pi$ which serves as the exploration policy for the $k$-th batch. The minimization goal of the above problem helps to reduce the regret starting from the $(k+1)$-th batch.

To facilitate discussion, we use $\mathcal{W}(m,n)$ to denote the minimax optimum of expected maximum width achieved the best learning algorithm $\mathcal{G}$. That is, we let

$$ $\mathcal{W}(m,n)=\inf_{\mathcal{G}}\sup_{D}\mathop{\mathbb{E}}_{\{X_{i},Y_{j}\}\sim D^{\otimes(m+n)}}\mathop{\mathbb{E}}_{(\pi,\lambda)\sim\mathcal{G}(\{X_{i}\})}\left[\text{\rm EM-width}(D,\Lambda)\right],$ $$

where $\mathcal{G}$ is the single-phase learning algorithm to decide $\pi$ and $\lambda$ based on $\{X_{i}\}_{i=1}^{m}$.

In (Ruan et al., ), the authors showed the existence of a good policy $\pi$ and the choice of $\lambda$ so that the bound of the expected maximum width leads to the desired optimal regret for $M=\Theta(\log\log T)$ batches. Their constructive proof (given the distribution $D$) is based on a reward-free LinUCB algorithm (Algorithm 2 in their paper). However, to learn such a good policy based on $\{X_{i}\}_{i=1}^{m}$, the authors employed more complicated procedures (such as CoreLearning and CoreIdentification).

Both (Zanette et al., ) and our work are inspired by the reward-free LinUCB and find that one may leverage this algorithmic framework to design learning algorithms as well. The authors of (Zanette et al., ) worked on a similar task as the single-phase learning problem defined above and their result implies that $\mathcal{W}(m,n)\leq O\left(\mathrm{poly}\ln(mndT)\cdot\sqrt{\ln(K)}\cdot(\sqrt{d/n}+\sqrt{d/m})\right)$.(^8^88 We state this implication by making the “large $|\mathcal{S}\times\mathcal{A}|$” assumption in (Zanette et al., ).)

In comparison, in Section [5](#S5) we propose ExplorationPolicy to solve the single-phase learning problem. In Lemma [7](#Thmlemma7) we analyze our algorithm and show that

$$ $\displaystyle\mathcal{W}(m,n)\leq O\left(\mathrm{poly}\ln(mndT)\cdot\sqrt{\ln(K)}\cdot(\sqrt{d/n}+d/m)\right).$ (6) $$

Clearly, the performance of our ExplorationPolicy outperforms that the results in (Zanette et al., ) in terms of the dependence on $m$.
Note that in our batch learning algorithm, $m$ represents the number of samples in the previous batch, which is much smaller than the size of the current batch (represented by $n$). Therefore, the $d/m$ term in our bound usually dominates and it is crucial for us to make this $\sqrt{m}$-factor improvement to achieve the optimal regret in the batch learning model. Indeed, without this improvement, the result of (Zanette et al., ) does not even imply the desired optimal regret for $M=\Theta(\log\log T)$ batches (the result of (Ruan et al., )).

The proof of Lemma [7](#Thmlemma7) is based on the analyais of reward-free LinUCB, and involves a scaled-and-clipped update rule and a dynamic concentration inequality for PSD matrices. Below we present the high-level ideas.

##### Learning the Exploration Policy via Reward-free LinUCB.

In (Ruan et al., ), the authors showed that given $\{Y_{j}\}_{j=1}^{n}\sim D^{\otimes n}$, the reward-free LinUCB algorithm can produce $\{\boldsymbol{y}_{j}\}_{j=1}^{n}$ (and therefore also form a policy) such that

$$ $\displaystyle\text{\rm EM-width}(D,U)\leq O(\sqrt{d\ln(nd/\kappa)/n}),$ (7) $$

where $U=\kappa\mathbf{I}+\sum_{j=1}^{n}\boldsymbol{y}_{j}\boldsymbol{y}_{j}^{\top}$, and $\kappa>0$ is polynomially small (e.g., $\kappa=T^{-2}$) to make sure that $U$ is invertible while we do not lose much in ([7](#S3.E7)). In this work, our ExplorationPolicy algorithm cannot direct access $\{Y_{j}\}_{j=1}^{n}$ but has to learn the distribution $D$ and construct a policy $\pi$ based on a much smaller data set $\{X_{i}\}_{i=1}^{m}$. (^9^99Comparing ([6](#S3.E6)) and ([7](#S3.E7)), we also find that the cost we pay in the expected maximum width for learning is about $\tilde{O}(d/m)$.)

To make learning possible, we first notice that the original reward-free LinUCB in (Ruan et al., ) produces $\{\boldsymbol{y}_{j}\}_{j=1}^{n}$ by the so-called *argmax policy*: $\boldsymbol{y}_{j}=\pi_{j}(Y_{j}):=\arg\max_{\boldsymbol{y}\in Y_{j}}\{\boldsymbol{y}^{\top}W_{j}\boldsymbol{y}\}$, where $W_{j}=\kappa\mathbf{I}+\sum_{q=1}^{j}\boldsymbol{y}_{q}\boldsymbol{y}_{q}^{\top}$ is the regularized information matrix obtained from the samples before $j$.(^10^1010We warn the readers that this is an oversimplification of the algorithm by omitting a few important techniques such as the volume-based lazy update of the $W_{j}$ matrices. However, we choose to the current presentation to better motivate our technical contributions.) One may combine $\{\pi_{j}\}$ via carefully chosen probability weights to form a desired one-shot policy $\pi$ (the *mixed argmax policy*).

In our algorithm ExplorationPolicy, we observe that we may approximately learn the policy $\pi$ from $\{X_{i}\}_{i=1}^{m}$ as long as we are able to approximately construct $\{W_{j}\}$ based on the $\{X_{i}\}$ data set. I.e., for any $W=W_{j}$, we would like to construct $\check{W}$ as long as $\Omega(1)\cdot\check{W}\preccurlyeq W\preccurlyeq\tilde{O}(1)\cdot\check{W}$, and the key here is to lower bound $W$ by $\Omega(1)\cdot\check{W}$.

To illustrate the main technical challenge and our solution, let us consider the following task: let $\boldsymbol{x}_{i}\sim\pi(X_{i})$ and $\check{W}=\frac{n}{m}(\kappa\mathbf{I}+\sum_{i=1}^{m}\boldsymbol{x}_{i}\boldsymbol{x}_{i}^{\top})$, we would like to choose appropriate regularization parameter $\lambda>0$ so that with high probability (over the randomness of $\{X_{i}\}$ and $\{\boldsymbol{x}_{i}\}$) it holds that

$$ $\displaystyle\Omega(1)\cdot\check{W}\preccurlyeq n\left(\lambda\textbf{I}+\mathop{\mathbb{E}}_{X\sim D,\boldsymbol{x}\sim\pi(X)}\boldsymbol{x}\boldsymbol{x}^{\top}\right).$ (8) $$

We note that this task may seem a bit different from our goal: 1) $\pi$ is unknown to the learner, and cannot be used to construct $\check{W}$; 2) the upper bound is quite different from $W=\kappa\textbf{I}+\sum_{j=1}^{n}\boldsymbol{y}_{j}\boldsymbol{y}_{j}^{\top}$. Indeed, these issues may be (quite non-trivially) resolved by observing that 1) $\pi$ is a mixed policy and can be iteratively updated to its final form and 2) relate the Right-Hand-Side of ([8](#S3.E8)) to $W$ by another matrix concentration inequality.

We now focus on the task of ([8](#S3.E8)), which is equivalent to

$$ $\displaystyle\Omega(1)\cdot\left(\kappa\mathbf{I}+\sum_{i=1}^{m}\boldsymbol{x}_{i}\boldsymbol{x}_{i}^{\top}\right)\preccurlyeq m\left(\lambda\textbf{I}+\mathop{\mathbb{E}}_{X\sim D,\boldsymbol{x}\sim\pi(X)}\boldsymbol{x}\boldsymbol{x}^{\top}\right).$ (9) $$

Note that since $\boldsymbol{x}_{i}\sim\pi(X_{i})$ are *i.i.d.* random variables, standard matrix concentration inequalities would imply ([9](#S3.E9)) when $m\lambda\mathbf{I}$ upper bounds $\boldsymbol{x}_{i}\boldsymbol{x}_{i}^{\top}$ (up to logarithmic factors of the inverse of the failure probability) almost surely, i.e., $m\lambda\geq\tilde{\Omega}(1)\Leftrightarrow\lambda\geq\tilde{\Omega}(1/m)$. This choice of $\lambda$ would lead to a $d/\sqrt{m}$ term instead of the $d/m$ term in ([6](#S3.E6)).

##### The Scaled-and-Clipped Update Rule.

While it is not possible to establish ([6](#S3.E6)) (with high probability) for a smaller $\lambda$ (e.g., $\lambda=o(1/m)$), we introduce the *scaled-and-clipped update rule* in the reward-free LinUCB (Line [6](#alg2.l6) of Algorithm [2](#alg2)) which eventually leads to the improvement of $\lambda$.

More concretely, instead of working with $\check{W}=\frac{n}{m}(\kappa\mathbf{I}+\sum_{i=1}^{m}\boldsymbol{x}_{i}\boldsymbol{x}_{i}^{\top})$, we define the *scaled-and-clipped version* of $\boldsymbol{x}_{i}$ and the *scaled-and-clipped information matrix* $U_{i}$,(^11^1111The definition of $\tilde{\boldsymbol{x}}_{i}$ here is slightly different from the real algorithm (up to a logarithmic factor $L$). We make this simplification only to better explain the main algorithmic ideas.)

$$ $\tilde{\boldsymbol{x}}_{i}:=\min\left\{\sqrt{\frac{1}{\boldsymbol{x}_{i}^{\top}U_{i-1}^{-1}\boldsymbol{x}_{i}}},1\right\}\boldsymbol{x}_{i},\qquad U_{i}=\kappa\mathbf{I}+\sum_{p=1}^{i}\tilde{\boldsymbol{x}}_{p}\tilde{\boldsymbol{x}}_{p}^{\top}.$ $$

We will use $\{U_{i}\}$ to construct the mixed argmax policy instead of $W$’s. The downside of this new update rule is that we use shorter feature vectors $\{\tilde{\boldsymbol{x}}_{i}\}$ instead of the original ones, which leads to the slower growth of the information matrix. However, this slowing effect is not too bad – if we repeat each $\boldsymbol{x}_{i}$ by $\ln(1/\kappa)=O(\ln T)$ times, scaled-and-clipped information matrix $U_{i}$ would upper bound the original information matrix. Through a more rigorous analysis, we will see that this effect would only hurt the regret by a logarithmic factor.

On the other hand, the benefit of our scaled-and-clipped update rule is that instead of establishing ([9](#S3.E9)), we only need to lower bound the Right-Hand-Side of ([9](#S3.E9)) by the scaled-and-clipped information matrix, i.e., to prove that the following inequality holds with high probability.

$$ $\displaystyle\Omega(1)\cdot\left(\kappa\mathbf{I}+\sum_{i=1}^{m}\tilde{\boldsymbol{x}}_{i}\tilde{\boldsymbol{x}}_{i}^{\top}\right)\preccurlyeq m\left(\lambda\textbf{I}+\mathop{\mathbb{E}}_{X\sim D,\boldsymbol{x}\sim\pi(X)}\boldsymbol{x}\boldsymbol{x}^{\top}\right),$ (10) $$

where $\tilde{\boldsymbol{x}}_{i}=\min\left\{\sqrt{\frac{1}{\boldsymbol{x}_{i}^{\top}U_{i-1}^{-1}\boldsymbol{x}_{i}}},1\right\}\boldsymbol{x}_{i}$ as before and we assume that $\boldsymbol{x}_{i}\sim\pi(X)$ are *i.i.d.* (as we did in ([9](#S3.E9))).

Let $U=\kappa\mathbf{I}+\sum_{i=1}^{m}\tilde{\boldsymbol{x}}_{i}\tilde{\boldsymbol{x}}_{i}^{\top}$. To prove ([10](#S3.E10)), we only need to show that there exists constants $c_{2}>c_{1}>0$ such that

$$ $\displaystyle c_{2}U\preccurlyeq c_{1}U+m\lambda\textbf{I}+m\mathop{\mathbb{E}}_{X\sim D,\boldsymbol{x}\sim\pi(X)}\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top},$ (11) $$

which implies that

$$ $\displaystyle(c_{2}-c_{1})U\preccurlyeq m\lambda\mathbf{I}+\mathop{\mathbb{E}}_{X\sim D,\boldsymbol{x}\sim\pi(X)}\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}\preccurlyeq m\lambda\mathbf{I}+\mathop{\mathbb{E}}_{X\sim D,\boldsymbol{x}\sim\pi(X)}{\boldsymbol{x}}{\boldsymbol{x}}^{\top},$ $$

where the last inequality is due to the clipping operation in the update rule.

Now let us focus on the task of establishing ([11](#S3.E11)). Thanks to the definition of the scaled-and-clipped version $\tilde{\boldsymbol{x}}_{i}$, we have that $\tilde{\boldsymbol{x}}_{i}\tilde{\boldsymbol{x}}_{i}^{\top}\preccurlyeq U$ almost surely. Therefore, it is possible to establish ([11](#S3.E11)) as long as we choose $m\lambda\geq\Omega(\kappa)$ to cover the $\kappa I$ term in $U$ (which only requires that $\lambda\geq\Omega(\kappa/m)=\Omega(m^{-1}T^{-2})$, leading to the better $d/m$ error term in ([6](#S3.E6))). On the other hand, however, we note that $U$, while serving as an upper bound of the random matrices $\tilde{\boldsymbol{x}}_{i}\tilde{\boldsymbol{x}}_{i}^{\top}$, is also a random variable by itself. We do not find sharp matrix concentration inequalities in literature to fit our need, and we have to resort to the matrix concentration inequality with dynamic upper bounds proved in Lemma [1](#Thmlemma1). The formal version of ([11](#S3.E11)) is stated and proved in Lemma [9](#Thmlemma9).

##### Matrix Concentration with Dynamic Upper Bounds.

As stated above, our Lemma [1](#Thmlemma1) is crucial to the analysis of the scaled-and-clipped update rule. One simple approach to prove Lemma [1](#Thmlemma1) is to assume the upper bound matrix $W_{n}$ (correspondingly $U$ in ([11](#S3.E11))) were fixed, apply the ordinary matrix concentration inequality and finally take a union bound over an $\epsilon$-net of $W_{n}$. However, such an approach would introduce extra $\mathrm{poly}(d)$ factors in the bound and lead to sub-optimal regret bound for our batch learning algorithm.

Our proof of Lemma [1](#Thmlemma1) follows the classical exponential moment method. However, we analyze the exponential moment of a specially chosen matrix, namely $W_{n}^{-1/2}(\sum_{i=1}^{n}(X_{i}-(1+\epsilon)Y_{i}))W_{n}^{-1/2}$. To bound the trace of this exponential moment, we resort to some deep analysis about Lieb’s theorem on convex trace functions (Theorem [5](#Thmtheorem5) and Lemma [10](#Thmlemma10)). Besides, we also make the critical observation that the function $\mathrm{Tr}\left(\exp\left(U^{\top}AU\right)\right)$ is bounded by $\mathrm{Tr}(\exp(A))$ with an additive error at most $d$ for any $U$ such that $U^{\top}U\preccurlyeq\mathbf{I}$ and any symmetric $A$ (Lemma [13](#Thmlemma13)).

### 3.2 Lower Bounds

##### Context-blind Lower Bound.

To construct the lower bound instances, we first construct $M$ mutually independent sub-problems with dimension $d/M$. At each time step, a uniform random sub-problem (i.e., its context set) is selected and presented to the learner. To analyze the regret performance of any batch learning algorithm, we divide the time horizon $T$ into $M$ consecutive stages with properly chosen lengths $\{T_{k}\}_{k=1}^{M}$ for each stage. We will show that, for each $k\in\{1,2,\dots,M\}$, during the $k$-th stage, if the learner does not start a new batch and update its policy, then a large regret would incur for the $k$-th sub-problem in this stage.

Our construction for the sub-problems is as follows.
For each $k\in\{1,3,4,5,\dots,M\}$, we choose the sub-problem to be the hard instance for the $K$-armed linear contextual linear bandit problem with burn-in time $\tilde{\Theta}(T_{k-1})$. In other words, we construct the $k$-th sub-problem so that it is hard for the learner to find a good policy for the $k$-th problem during the first $\sum_{i\leq k-1}T_{i}$ time steps.

The most interesting sub-problem design is for $k=2$, which takes the advantage of the context-blind setting to force the learner incur more regret. In this sub-problem, we consider a linear contextual bandit problem $d/M$ arms (assuming that $K\geq d/M$). However, during each time step, only $(d/(2M)+1)$ arms are presented to the learner. In particular, we set the first $d/(2M)$ arms to be the *frequent* arms that always appear in the context set. For the rest $d/(2M)$ *infrequent* arms, we choose one of them uniformly randomly and include the chosen one in the context set at each time step. The best exploration strategy for the learner is to play the infrequent arm with a higher probability, e.g., $\frac{1}{2}$ and play the frequent arms with probability $\frac{M}{d}$. However, due to the context-blind setting, the learner can not tell whether an arm is frequent or infrequent with insufficient information, and his best strategy is to play the arms with the same probability. As a result, the infrequent arms are insufficiently explored, which leads to an extra $\tilde{\Theta}(\sqrt{d})$ factor in the regret.

##### Context-aware Lower Bound.

The construction of the lower bound instances for the context-aware setting is quite straightforward. We simply re-define the sub-problem for $k=2$ to be the hard instance for the $K$-armed linear contextual linear bandit problem (the same as $k\in\{3,4,5,\dots,M\}$ in the context-blind case) and re-design the stage lengths $\{T_{k}\}_{k=1}^{M}$ to achieve the optimal lower bound in this setting.

## 4 Context-blind Batch Learning: Algorithm and Regret Analysis

We now present our context-blind batch learning algorithm in Algorithm [1](#alg1). Given $T$ and $d$, we define $\tilde{d}:=d\ln(TKd/\delta)$. In the case $d\leq T\leq d\ln(K)$, the regret bound is exactly $\Theta(T)$, and in the case $d\ln(K)<T\leq\tilde{d}$, the regret lower bound is $\Omega(d\ln(K))$ and the upper bound is at most $O(T)\leq O(d\ln(KTd/\delta))$. Therefore, in the case $d\leq T<\tilde{d}$, the trivial upper bound $O(T)$ is optimal up to logarithmic factors in $T$ and $d$. Below we assume $T\geq\tilde{d}$.

Let the time schedule $\{T_{k}\}_{k=1}^{M}$ such that $\sum_{k=1}^{M}T_{k}\geq T$ to be determined later.
We can then accordingly calculate the end of each batch by

$$ $\displaystyle\mathcal{T}_{k}=\min\left\{\sum_{\ell=1}^{k}T_{k},T\right\}.$ (12) $$

In preparation for explaining the algorithm, we first introduce a few variables and notations used in the algorithm. During the $k$-th batch, the algorithm learns an estimation, namely $\hat{\boldsymbol{\theta}}_{k}$, of the hidden vector $\boldsymbol{\theta}$, as well as an information matrix $\Lambda_{k}$ that is used to construct the confidence interval for the estimated rewards based on $\hat{\boldsymbol{\theta}}_{k}$. More specifically, given the pair $(\Lambda_{k},\hat{\boldsymbol{\theta}}_{k})$, we set the confidence interval for the expected reward of any feature vector $\boldsymbol{x}$ to be $[\boldsymbol{x}^{\top}\hat{\boldsymbol{\theta}}_{k}\pm\alpha\sqrt{\boldsymbol{x}^{\top}\Lambda_{k}^{-1}\boldsymbol{x}}]$, where $[a\pm b]$ denotes the interval $[a-b,a+b]$ and we set

$$ $\displaystyle\alpha:=\sqrt{50\ln(KTd/\delta)}.$ (13) $$

Given the pair $(\Lambda_{k},\hat{\boldsymbol{\theta}}_{k})$, for any context set $X\subseteq\mathbb{R}^{d}$, we define the following natural elimination procedure based on the corresponding confidence intervals

$$ $\displaystyle\mathcal{E}(X;(\Lambda_{k},\hat{\boldsymbol{\theta}}_{k})):=\left\{\boldsymbol{x}\in X:\boldsymbol{x}^{\top}\hat{\boldsymbol{\theta}}_{k}+\alpha\sqrt{\boldsymbol{x}^{\top}\Lambda_{k}^{-1}\boldsymbol{x}}\geq\boldsymbol{y}^{\top}\hat{\boldsymbol{\theta}}_{k}-\alpha\sqrt{\boldsymbol{y}^{\top}\Lambda_{k}^{-1}\boldsymbol{y}},\forall\boldsymbol{y}\in X\right\}.$ (14) $$

In words, $\mathcal{E}(X;(\Lambda_{k},\hat{\boldsymbol{\theta}}_{k}))$ returns the set of the survived feature vectors, each of which remains possible to hold the highest expected reward when assuming all confidence intervals based on $(\Lambda_{k},\hat{\boldsymbol{\theta}}_{k})$ contains their estimation targets.

By the end of the $k$-th batch, the algorithm would have learned $k$ pairs $\{(\Lambda_{i},\hat{\boldsymbol{\theta}}_{i})\}_{i=1}^{k}$, and we naturally extend our elimination procedure to $\{(\Lambda_{i},\hat{\boldsymbol{\theta}}_{i})\}_{i=1}^{k}$ as follows.

$$ $\displaystyle\mathcal{E}(X;\{(\Lambda_{i},\hat{\boldsymbol{\theta}}_{i})\}_{i=1}^{k}):=\mathop{\cap}_{i=1}^{k}\mathcal{E}(X;(\Lambda_{i},\hat{\boldsymbol{\theta}}_{i})).$ (15) $$

When $X\sim D$ and given $\{(\Lambda_{i},\hat{\boldsymbol{\theta}}_{i})\}_{i=1}^{k}$, we denote the distribution of $\mathcal{E}(X;\{(\Lambda_{i},\hat{\boldsymbol{\theta}}_{i})\}_{i=1}^{k})$ by $D_{k+1}$.

Figure: Algorithm 1 Context-Blind Batch Learning

We now explain the key steps of the algorithm. For the first batch, we take actions according to the local optimal design policy $\pi^{\mathtt{G}}$, which is defined by the lemma below.

###### Lemma 2 (General Equivalence Theorem in (Kiefer and Wolfowitz, 1960 ) ) .

For any bounded subset $X\subset\mathbb{R}^{d}$, there exists a distribution $\mathcal{K}(X)$ supported on $X$, such that for any $\epsilon>0$, it holds that

$$ $\displaystyle\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}\left(\epsilon\mathbf{I}+\mathbb{E}_{\boldsymbol{y}\sim\mathcal{K}(X)}[\boldsymbol{y}\boldsymbol{y}^{\top}]\right)^{-1}\boldsymbol{x}\leq d.$ (16) $$

Furthermore, there exists a mapping $\pi^{\mathtt{G}}$, which maps a context $X$ to a distribution over $X$ such that

$$ $\displaystyle\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}(\epsilon\mathbf{I}+\mathbb{E}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}[\boldsymbol{y}\boldsymbol{y}^{\top}])^{-1}\boldsymbol{x}\leq 2d.$ (17) $$

In particular, when $X$ has a finite size, $\pi^{\mathtt{G}}(X)$ could be implemented within $\mathrm{poly}(|X|)$ time.

Clearly, the computation cost to find $\pi^{\mathtt{G}}(X_{t})$ is bounded by $\mathrm{poly}(|X_{t}|)=\mathrm{poly}(K)$.

For $k\geq 2$, at any time $t$ during the $k$-th batch, the algorithm observes the context set $X_{t}\sim D$, eliminates some of the sub-optimal arms in Line [11](#alg1.l11), and denote the set of the survived arms by $X_{t}^{(k)}$. By the definition above, the $X_{t}^{(k)}$ follows the distribution $D_{k}$ when conditioned on the first $(k-1)$ batches. The algorithm then uses an exploration policy $\pi_{k-1}$ to stochastically select and play an arm $\boldsymbol{y}_{t}\in X_{t}^{(k)}$.

At the end of the $k$-th batch, our algorithm divides the $T_{k}$ data points collected in the batch into two parts of the equal sizes. In Line [14](#alg1.l14), our algorithm calculates $\Lambda_{k}$ and $\hat{\boldsymbol{\theta}}_{k}$ using the standard ridge regression and the first part of the data points. In Line [16](#alg1.l16), the new exploration policy $\pi_{k}$ is learned by the $\mathtt{ExplorationPolicy}$ procedure using the context sets from the second part of the data points. Note that the context sets fed into $\mathtt{ExplorationPolicy}$ go through the elimination procedure based on $\{\Lambda_{i},\hat{\boldsymbol{\theta}}\}_{i=1}^{k}$, which depends on the first part of the data points. We will introduce our key procedure $\mathtt{ExplorationPolicy}$ in Section [5](#S5). For now, we treat it as a black box and prove our main theorem as follows.

###### Lemma 2 (General Equivalence Theorem in (Kiefer and Wolfowitz, 1960 ) ) .

### 4.1 The Regret Analysis: Proof of Theorem 1

We first define the following desired event where all the confidence intervals contains their estimation targets,

$$ $\displaystyle E:=\left\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\in[\boldsymbol{x}^{\top}\hat{\boldsymbol{\theta}}_{k}\pm\alpha\sqrt{\boldsymbol{x}^{\top}\Lambda_{k}^{-1}\boldsymbol{x}}],\forall k\in\{1,2,\dots,M\},\forall\boldsymbol{x}\in X_{t},\forall t\in\{1,2,\dots,T\}\right\}.$ (18) $$

By the analysis of the ridge regression (Lemma [19](#Thmlemma19), stated and proved in Appendix [B.1](#A2.SS1)) and the fact that $\alpha\geq\sqrt{\ln(KTd/\delta)}+\lambda\sqrt{d}$, via a union bound we have that $\Pr[E]\geq 1-MT\delta$. When $E$ holds, we know that the optimal arm at any time step will never be eliminated by the elimination procedure $\mathcal{E}$. Let $\mathbb{I}[E]$ be the indicator variable which takes value $1$ when $E$ holds and value 0 0 otherwise. We have the following upper bound for the expected regret of the algorithm.

$$ $\displaystyle R_{T}$ $\displaystyle\leq\sum_{k=1}^{M}\sum_{t=\mathcal{T}_{k-1}+1}^{\mathcal{T}_{k}}\mathop{\mathbb{E}}\left[\mathbb{I}[E]\left(\max_{\boldsymbol{x}\in X_{t}}\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\}-\boldsymbol{y}_{t}^{\top}\boldsymbol{\theta}\right)\right]+2T\Pr[\overline{E}]$ $\displaystyle\leq\sum_{k=1}^{M}\sum_{t=\mathcal{T}_{k-1}+1}^{\mathcal{T}_{k}}\mathop{\mathbb{E}}\left[\mathbb{I}[E]\left(\max_{\boldsymbol{x}\in X_{t}^{(k)}}\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\}-\min_{\boldsymbol{x}\in X_{t}^{(k)}}\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\}\right)\right]+2MT^{2}\delta.$ (19) $$

###### Lemma 3 .

For any time step $t$ during any batch $k$ ($k\geq 2$), define $X_{t}^{(k-1)}:=\mathcal{E}(X_{t},\{\Lambda_{i},\hat{\boldsymbol{\theta}}_{i}\}_{i=1}^{k-2})$ and we have that

$$ $\displaystyle\mathbb{E}\left[\mathbb{I}[E]\left(\max_{\boldsymbol{x}\in X^{(k)}_{t}}\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\}-\min_{\boldsymbol{x}\in X_{t}^{(k)}}\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\}\right)\right]\leq\mathbb{E}\left[\min\left\{4\alpha\max_{\boldsymbol{x}\in X_{t}^{(k)}}\sqrt{\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}},2\right\}\right].$ (20) $$

###### Proof.

When $E$ happens, for any $\boldsymbol{u},\boldsymbol{v}\in X_{t}^{(k)}$, we have $\boldsymbol{u}^{\top}\boldsymbol{\theta}\in[\boldsymbol{u}^{\top}\hat{\boldsymbol{\theta}}_{k-1}\pm\alpha\sqrt{\boldsymbol{u}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{u}}]$ and $\boldsymbol{v}^{\top}\boldsymbol{\theta}\in[\boldsymbol{v}^{\top}\hat{\boldsymbol{\theta}}_{k-1}\pm\alpha\sqrt{\boldsymbol{v}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{v}}]$. When this condition holds, we have that

$$ $\displaystyle\mathbb{I}[E]\left(\boldsymbol{u}^{\top}\boldsymbol{\theta}-\boldsymbol{v}^{\top}\boldsymbol{\theta}\right)$ $\displaystyle\leq\left(\boldsymbol{u}^{\top}\hat{\boldsymbol{\theta}}_{k-1}+\alpha\sqrt{\boldsymbol{u}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{u}}\right)-\left(\boldsymbol{v}^{\top}\hat{\boldsymbol{\theta}}_{k-1}-\alpha\sqrt{\boldsymbol{v}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{v}}\right)$ $\displaystyle=\left(\boldsymbol{u}^{\top}\hat{\boldsymbol{\theta}}_{k-1}-\alpha\sqrt{\boldsymbol{u}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{u}}\right)-\left(\boldsymbol{v}^{\top}\hat{\boldsymbol{\theta}}_{k-1}+\alpha\sqrt{\boldsymbol{v}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{v}}\right)+2\alpha\sqrt{\boldsymbol{u}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{u}}+2\alpha\sqrt{\boldsymbol{v}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{v}}$ $\displaystyle\leq 2\alpha\sqrt{\boldsymbol{u}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{u}}+2\alpha\sqrt{\boldsymbol{v}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{v}}$ (21) $\displaystyle\leq 4\alpha\max_{\boldsymbol{x}\in X_{t}^{(k)}}\sqrt{\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}}\leq 4\alpha\max_{\boldsymbol{x}\in X_{t}^{(k-1)}}\sqrt{\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}},$ $$

where the ([21](#S4.E21)) is because $\boldsymbol{v}$ survived from the elimination based on $(\Lambda_{k-1},\hat{\boldsymbol{\theta}}_{k-1})$, and the last inequality is because $X_{t}^{(k)}\subseteq X_{t}^{(k-1)}$.

Letting $\boldsymbol{u}=\arg\max_{\boldsymbol{x}\in X_{t}^{(k)}}\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\}$ and $\boldsymbol{v}=\arg\min_{\boldsymbol{x}\in X_{t}^{(k)}}\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\}$ and noting that $\boldsymbol{u}^{\top}\boldsymbol{\theta},\boldsymbol{v}^{\top}\boldsymbol{\theta}\in[-1,1]$, we have that

$$ $\displaystyle\mathbb{I}[E]\left(\max_{\boldsymbol{x}\in X^{(k)}_{t}}\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\}-\min_{\boldsymbol{x}\in X_{t}^{(k)}}\{\boldsymbol{x}^{\top}\boldsymbol{\theta}\}\right)\leq\min\left\{4\alpha\max_{\boldsymbol{x}\in X_{t}^{(k-1)}}\sqrt{\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}},2\right\}.$ (22) $$

Taking the expectation over ([22](#S4.E22)), we prove the lemma.
∎

###### Lemma 3 .

###### Proof.

#### 4.1.1 Regret in the First and Second Batches

The regret in the first batch is bounded by $T_{1}$ trivially. For the second batch,
we have the lemma below.

###### Lemma 4 .

With probability $1-\delta$, it holds that

$$ $\mathbb{E}_{X\sim D}\left[\max_{\boldsymbol{x}\in\mathcal{E}(X;(\Lambda_{1},\hat{\boldsymbol{\theta}}_{1}))}\min\left\{\sqrt{\boldsymbol{x}^{\top}\Lambda_{1}^{-1}\boldsymbol{x}},2\right\}\right]\leq O\left(\sqrt{\frac{\min\{K,d\}}{\mathcal{T}_{1}}\cdot\left(d\ln\left(\frac{\mathcal{T}_{1}}{\lambda}\right)+\ln(\mathcal{T}_{1}/\delta)\right)}\right).$ $$

###### Proof.

Recall the definition of $\boldsymbol{y}_{t}$ and $r_{t}$ in line [4](#alg1.l4), Algorithm [1](#alg1). Let $W_{t}$ denote $\lambda\mathbf{I}+\sum_{\tau=1}^{t}\boldsymbol{y}_{\tau}\boldsymbol{y}_{\tau}^{\top}$ for $0\leq t\leq\mathcal{T}_{1}/2$. By the Elliptical Potential Lemma (Lemma [20](#Thmlemma20), stated and proved in Appendix [B.2](#A2.SS2)), we have that

$$ $\displaystyle\sum_{t=1}^{\mathcal{T}_{1}/2}\min\{\boldsymbol{y}_{t}^{\top}W_{t-1}^{-1}\boldsymbol{y}_{t},1\}\leq O\left(d\ln\left(\frac{\mathcal{T}_{1}}{\lambda}\right)\right).$ $$

By Corollary [2](#Thmcorollary2) with $\epsilon=\frac{1}{2}$, we further have that with probability $1-\delta$, it holds that

$$ $\displaystyle\sum_{t=1}^{\mathcal{T}_{1}/2}\mathbb{E}_{X\sim D}\mathbb{E}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}\min\{\boldsymbol{y}^{\top}W_{t-1}^{-1}\boldsymbol{y},1\}$ $\displaystyle\leq 2\sum_{t=1}^{\mathcal{T}_{1}/2}\min\{\boldsymbol{y}_{t}^{\top}W_{t-1}^{-1}\boldsymbol{y}_{t},1\}+56\ln(\mathcal{T}_{1}/\delta)$ $\displaystyle\leq O\left(d\ln\left(\frac{\mathcal{T}_{1}}{\lambda}\right)+\ln(\mathcal{T}_{1}/\delta)\right).$ (23) $$

Noting that $W_{t-1}\preccurlyeq W_{t}$ for $1\leq t\leq\mathcal{T}_{1}$ and $\Lambda_{1}=W_{\mathcal{T}_{1}/2}$, by ([23](#S4.E23)) we have that

$$ $\displaystyle\mathcal{T}_{1}\mathbb{E}_{X\sim D}\mathbb{E}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}\min\{\boldsymbol{y}^{\top}\Lambda_{1}^{-1}\boldsymbol{y},1\}\leq O\left(d\ln\left(\frac{\mathcal{T}_{1}}{\lambda}\right)+\ln(\mathcal{T}_{1}/\delta)\right).$ (24) $$

###### Lemma 5 .

For any PSD matrix $w$ and context $X$, we have that

$$ $\displaystyle\max_{\boldsymbol{x}\in X}\{\boldsymbol{x}^{\top}W^{-1}\boldsymbol{x}\}\leq\min\{K,d\}\mathbb{E}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y}.$ (25) $$

###### Proof.

for any $x$, the confidence region is $\|xW^{-1/2}\|_{1}$. Also we have that $\|x\|_{W(x),2}\leq\sqrt{d}$. $W=\mathbb{E}[X]$ and we need to bound $\mathbb{E}[\mathrm{Tr}(\sqrt{XW^{-1})}\sqrt{d}]\leq d$. That is enough.

###### Lemma 6 .

For any $x$ such that $x^{\top}X^{-1}x\leq 1$, we have that $\|xW^{-1/2}\|^{2}_{1}\leq\mathrm{Tr}(XW^{-1})$.

###### Proof.

$\|xW^{-1/2}\|^{2}_{1}\sim\|yX^{1/2}W^{-1/2}\|^{2}_{1}\leq(|y_{1}v_{1}|+|y_{2}v_{2}|+...|y_{d}v_{d}|)^{2}\leq\sqrt{\sum_{i=1}^{d}\|v_{i}\|^{2}_{2}}$. Use the fact the $X$ and $W$ are PSD matrices.. Consider to use the engi-space of $X$ instead of $W$.
∎

By Lemma [2](#Thmlemma2), we have that

$$ $\displaystyle\max_{\boldsymbol{x}\in X}\{\boldsymbol{x}^{\top}W^{-1}\boldsymbol{x}\}\leq\min\{K,d\}\mathbb{E}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y}.$ (26) $$

In the case $\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}W^{-1}\boldsymbol{x}\leq 1$, we have that $\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y}\leq 1$ for any $y\in X$. It then holds that

$$ $\displaystyle\max_{\boldsymbol{x}\in X}\min\{\boldsymbol{x}^{\top}W^{-1}\boldsymbol{x},1\}\leq\min\{K,d\}\mathbb{E}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}\min\{\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y},1\}.$ $$

In the case $\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}W^{-1}\boldsymbol{x}>1$, we analyze as below.
When $\min\{K,d\}\mathrm{Pr}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}[\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y}>1]\geq 1$, it is trivial that

$$ $\displaystyle\min\{K,d\}\mathbb{E}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}\min\{\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y},1\}\geq 1.$ $$

Otherwise, we have that

$$ $\displaystyle\min\{K,d\}\mathbb{E}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}\min\{\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y},1\}$ $\displaystyle\geq\min\{K,d\}\mathbb{E}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y}-\min\{K,d\}\mathrm{Pr}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}[\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y}>1](\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}W^{-1}\boldsymbol{x}-1)$ $\displaystyle\geq\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}W^{-1}\boldsymbol{x}-\min\{K,d\}\mathrm{Pr}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}[\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y}>1](\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}W^{-1}\boldsymbol{x}-1)$ (27) $\displaystyle=1+(1-\min\{K,d\}\mathrm{Pr}_{\boldsymbol{y}\sim\pi^{\mathtt{G}}(X)}[\boldsymbol{y}^{\top}W^{-1}\boldsymbol{y}>1])(\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}W^{-1}\boldsymbol{x}-1)$ $\displaystyle\geq 1.$ $$

Here ([27](#S4.E27)) holds by Lemma [2](#Thmlemma2).
The lemma is proved.
∎

Setting $W=\Lambda_{1}$ in Lemma [5](#Thmlemma5), we have that

$$ $\displaystyle\mathbb{E}_{X\sim D}\max_{\boldsymbol{x}\in X}\min\{\boldsymbol{x}^{\top}\Lambda_{1}^{-1}\boldsymbol{x},1\}\leq\frac{\min\{K,d\}}{\mathcal{T}_{1}}\cdot O\left(d\ln\left(\frac{\mathcal{T}_{1}}{\lambda}\right)+\ln(\mathcal{T}_{1}/\delta)\right).$ (28) $$

Therefore,

$$ $\displaystyle\mathbb{E}_{X\sim D}\left[\max_{\boldsymbol{x}\in\mathcal{E}(X;(\Lambda_{1},\hat{\boldsymbol{\theta}}_{1}))}\sqrt{\min\{\boldsymbol{x}^{\top}\Lambda_{1}^{-1}\boldsymbol{x},1\}}\right]$ $\displaystyle\qquad\leq\sqrt{\mathbb{E}_{X\sim D}\left[\max_{\boldsymbol{x}\in X}\min\{\boldsymbol{x}^{\top}\Lambda_{1}^{-1}\boldsymbol{x},1\}\right]}\leq O\left(\sqrt{\frac{\min\{K,d\}}{\mathcal{T}_{1}}\cdot\left(d\ln\left(\frac{\mathcal{T}_{1}}{\lambda}\right)+\ln(\mathcal{T}_{1}/\delta)\right)}\right).$ $$

Lemma [4](#Thmlemma4) is proved.
∎

By Lemma [3](#Thmlemma3) and [4](#Thmlemma4), the regret in the second batch is bounded by

$$ $\displaystyle O\left(T_{2}\cdot\sqrt{\frac{\min\{K,d\}d}{T_{1}}\ln\left(\frac{T}{\lambda\delta}\right)}\right)+T\delta.$ (29) $$

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

###### Lemma 6 .

###### Proof.

#### 4.1.2 Regret in the k 𝑘 k -th Batch ( k ≥ 3 𝑘 3 k\geq 3 )

Let

$$ $\displaystyle L:=\frac{1}{200\ln(Td/\delta)}\qquad\text{and}\qquad\kappa:=\frac{1}{T^{2}}$ (30) $$

be the parameters to be used by $\mathtt{ExplorationPolicy}$.

In Section [5](#S5), we will introduce $\mathtt{ExplorationPolicy}$ and prove the following lemma.

###### Lemma 7 .

Let $\{Z_{u}\}_{u=1}^{m}$ be $m$ i.i.d. stochastic context sets following a distribution $D$. Let $\pi$ be the output by running $\mathtt{ExplorationPolicy}$ with the input $\{Z_{u}\}_{u=1}^{m}$. Let $\{\tilde{Z}_{u}\}_{u=1}^{n}$ be another group of i.i.d. stochastic context sets following the distribution $D$ (which is also independent from $\{Z_{u}\}_{u=1}^{m}$). Let $\boldsymbol{y}_{u}$ be independently sampled from $\pi(\tilde{Z}_{u})$ for each $u\in\{1,2,\dots,n\}$, and let $\Lambda=\sum_{u=1}^{n}\boldsymbol{y}_{u}\boldsymbol{y}_{u}^{\top}$. With probability $(1-3\delta)$, we have that

$$ $\displaystyle\mathop{\mathbb{E}}_{X\sim D}\left[\min\left\{\sqrt{\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}(\Lambda+\frac{n}{m}\kappa\mathbf{I})^{-1}\boldsymbol{x}},\sqrt{L}\right\}\right]\leq\sqrt{\frac{1}{n}}\cdot O\left(\sqrt{d\ln\left(\frac{md}{\kappa}\right)}\right)+\frac{\sqrt{L}}{m}\cdot O\left(d\ln\left(\frac{md}{\kappa}\right)\right).$ (31) $$

For the $k$-th batch ($k\geq 3$), we invoke Lemma [7](#Thmlemma7) with $m=T_{k-2}/2$, $\{Z_{u}\}_{u=1}^{m}=\{X_{t}^{(k-1)}\}_{t=\mathcal{T}_{k-3}+T_{k-2}/2+1}^{\mathcal{T}_{k-2}}$, $n=T_{k-1}/2$, $\{\tilde{Z}_{u}\}_{u=1}^{n}=\{X_{t}^{(k-1)}\}_{t=\mathcal{T}_{k-2}+1}^{\mathcal{T}_{k-2}+T_{k-1}/2}$, and $D=D_{k-1}$, we have that with probability $(1-3\delta)$, it holds that

$$ $\displaystyle\mathop{\mathbb{E}}_{X\sim D_{k-1}}\left[\min\left\{\sqrt{\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}\left(\sum_{t=\mathcal{T}_{k-2}+1}^{\mathcal{T}_{k-2}+T_{k-1}/2}\boldsymbol{y}_{t}\boldsymbol{y}_{t}^{\top}+\frac{T_{k-1}}{T_{k-2}}\kappa\mathbf{I}\right)^{-1}\boldsymbol{x}},\sqrt{L}\right\}\right]$ $\displaystyle\qquad\qquad\qquad\leq\sqrt{\frac{1}{T_{k-1}}}\cdot O\left(\sqrt{d\ln\left(\frac{T_{k-2}d}{\kappa}\right)}\right)+\frac{\sqrt{L}}{T_{k-2}}\cdot O\left(d\ln\left(\frac{T_{k-2}d}{\kappa}\right)\right).$ (32) $$

Note that $\frac{T_{k-1}}{T_{k-2}}\kappa\leq\lambda$ and therefore $(\sum_{t=\mathcal{T}_{k-2}+1}^{\mathcal{T}_{k-2}+T_{k-1}/2}\boldsymbol{y}_{t}\boldsymbol{y}_{t}^{\top}+\frac{T_{k-1}}{T_{k-2}}\kappa\mathbf{I})^{-1}\succcurlyeq\Lambda_{k-1}^{-1}$. Therefore ([32](#S4.E32)) implies that with probability $(1-3\delta)$,

$$ $\displaystyle\mathop{\mathbb{E}}_{X\sim D_{k-1}}\left[\min\left\{\sqrt{\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}},\sqrt{L}\right\}\right]\leq\sqrt{\frac{1}{T_{k-1}}}\cdot O\left(\sqrt{d\ln\left(Td\right)}\right)+\frac{\sqrt{L}}{T_{k-2}}\cdot O\left(d\ln\left(Td\right)\right).$ (33) $$

In other words, for each time step $t$ during the $k$-th batch, we have that

$$ $\displaystyle\mathop{\mathbb{E}}\left[\min\left\{\sqrt{\max_{\boldsymbol{x}\in X_{t}^{(k-1)}}\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}},\sqrt{L}\right\}\right]\leq\sqrt{\frac{1}{T_{k-1}}}\cdot O\left(\sqrt{d\ln\left(Td\right)}\right)+\frac{\sqrt{L}}{T_{k-2}}\cdot O\left(d\ln\left(Td\right)\right)+3\delta.$ (34) $$

###### Lemma 7 .

#### 4.1.3 Putting All Together

Combining ([19](#S4.E19)), Lemma [3](#Thmlemma3) and Lemma [4](#Thmlemma4), the total regret is bounded by

$$ $\displaystyle R_{T}$ $\displaystyle\leq 2T_{1}+2T_{2}\cdot\min\left\{\alpha\sqrt{\frac{2\min\{K,d\}d\ln\left(\frac{T}{\lambda\delta}\right)}{T_{1}}},1\right\}$ $\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{k=3}^{M}T_{k}\mathbb{E}\left[\min\left\{4\alpha\max_{\boldsymbol{x}\in X_{t}^{(k-1)}}\sqrt{\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}},2\right\}\right]+2MT^{2}\delta$ $\displaystyle\leq 2T_{1}+2T_{2}\cdot\min\left\{\alpha\sqrt{\frac{2\min\{K,d\}d\ln\left(\frac{T}{\lambda\delta}\right)}{T_{1}}},1\right\}$ $\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{k=3}^{M}4\alpha T_{k}\mathbb{E}\left[\min\left\{\max_{\boldsymbol{x}\in X_{t}^{(k-1)}}\sqrt{\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}},\sqrt{L}\right\}\right]+2MT^{2}\delta$ (35) $\displaystyle\leq 2T_{1}+2T_{2}\cdot\min\left\{\alpha\sqrt{\frac{2\min\{K,d\}d\ln\left(\frac{T}{\lambda\delta}\right)}{T_{1}}},1\right\}$ $\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{k=3}^{M}4\alpha T_{k}\mathbb{E}\left[\min\left\{\max_{\boldsymbol{x}\in X_{t}^{(k-1)}}\sqrt{\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}},\sqrt{L}\right\}\right]+2MT^{2}\delta,$ (36) $$

Here ([35](#S4.E35)) is because of $2\leq 4\alpha\sqrt{L}$.

Let $\tilde{d}:=d\ln(TdK/\delta)\cdot\ln\left(\frac{T}{\lambda\delta}\right)$.
Combining ([36](#S4.E36)) and ([34](#S4.E34)) (for $k\geq 3$), we have that

$$ $\displaystyle R_{T}\leq 2T_{1}+2T_{2}\cdot\min\left\{\alpha\sqrt{\frac{2\min\{K,d\}d\ln\left(\frac{T}{\lambda\delta}\right)}{T_{1}}},1\right\}$ $\displaystyle\qquad\qquad\qquad+4\alpha\sum_{k=3}^{M}\left({\frac{T_{k}}{\sqrt{T_{k-1}}}}\cdot O\left(\sqrt{d\ln\left(Td\right)}\right)+\frac{T_{k}\sqrt{L}}{T_{k-2}}\cdot O\left(d\ln\left(Td\right)\right)\right)+3T\delta+2MT^{2}\delta$ $\displaystyle\quad\leq 2T_{1}+2T_{2}\cdot\min\left\{\alpha\sqrt{\frac{2\min\{K,d\}d\ln\left(\frac{T}{\lambda\delta}\right)}{T_{1}}},1\right\}+O(\sqrt{\ln^{2}(Td/\delta)+\ln(K)\ln(Td/\delta)})\times\sum_{k=3}^{M}\frac{T_{k}\sqrt{d}}{\sqrt{T_{k-1}}}$ $\displaystyle\qquad\qquad\qquad+O\left(\sqrt{\ln(K)\ln^{2}(Td)+\ln^{3}(Td)}\right)\times\sum_{k=3}^{M}\frac{T_{k}d}{T_{k-2}}+O(MT^{2}\delta)$ $\displaystyle\quad\leq 2T_{1}+2T_{2}\cdot\min\left\{\sqrt{\frac{2\min\{K,d\}\tilde{d}}{T_{1}}},1\right\}+O(\ln(Td))\cdot\left(\sum_{k=3}^{M}\frac{T_{k}\sqrt{\tilde{d}}}{\sqrt{T_{k-1}}}+\sum_{k=3}^{M}\frac{T_{k}\tilde{d}}{T_{k-2}}\right)+O(MT^{2}\delta).$ (37) $$

When $T$ is small (i.e., $d\leq T<\tilde{d}$), Theorem [1](#Thmtheorem1) trivially holds because the regret is at most $O(\tilde{d})$, which is further bounded by

$$ $O\left(\mathrm{poly}\ln(Td)\min\left\{T^{\frac{1}{2-2^{-M+2}}}(d\ln(K))^{\frac{1-2^{-M+2}}{2-2^{-M+2}}},T^{\frac{1}{2-2^{-M+1}}}(d\ln(K))^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}\min\{K,d\}^{\frac{2^{-M+1}}{2-2^{-M+1}}}\right\}\right).$ $$

Suppose $T\geq\tilde{d}$. Let $h=\min\{K,d\}$.
We discuss the following two cases to design the batch schedule.

##### Case I: d ~ ≤ T ≤ d ~ ​ h 2 − 2 − M + 2 ~ 𝑑 𝑇 ~ 𝑑 superscript ℎ 2 superscript 2 𝑀 2 \tilde{d}\leq T\leq\tilde{d}h^{2-2^{-M+2}} .

In this case , we define $\gamma:=T^{\frac{1}{2-2^{-M+2}}}\tilde{d}^{\frac{1-2^{-M+2}}{2-2^{-M+2}}}\geq\tilde{d}$.

We let

$$ $\displaystyle T_{1}=\gamma,\quad T_{2}=\gamma,\quad T_{k}=\gamma\frac{\sqrt{T_{k-1}}}{\sqrt{\tilde{d}}},\forall 3\leq k\leq M.$ (38) $$

Then for $3\leq k\leq M$, by the iteration rule we have that $T_{k}=\gamma^{2-2^{-k+2}}\tilde{d}^{-1+2^{-k+2}}$. It is easy to verify that $\sum_{k=1}^{M}T_{k}\geq T_{M}=T$.

Now we verify that the regret for each batch is bounded by $O(\gamma)$.
Firstly we have that $T_{1},T_{2}\leq\gamma$. For $k=3$, we have that $\frac{T_{3}\sqrt{d}}{\sqrt{T_{2}}}=\gamma$ and $\frac{T_{3}\tilde{d}}{T_{1}}=\gamma^{\frac{1}{2}}\tilde{d}^{\frac{1}{2}}\leq\gamma$.
For $4\leq k\leq M$, noting that $\tilde{d}\leq\gamma$, we have that

$$ $\displaystyle\frac{T_{k}\sqrt{d}}{\sqrt{T_{k-1}}}=\gamma,\quad\quad\quad\frac{T_{k}d}{T_{k-2}}=\gamma^{2^{-k}-2^{-k+2}}\tilde{d}^{1-2^{-k}+2^{-k+2}}\leq\gamma.$ (39) $$

Therefore, the total regret in this case is bounded by

$$ $\displaystyle O\left(T^{\frac{1}{2-2^{-M+2}}}\tilde{d}^{\frac{1-2^{-M+2}}{2-2^{-M+2}}}\log\log(T)+MT^{2}\delta\right).$ (40) $$

##### Case II: T > d ~ ​ h 2 − 2 − M + 2 𝑇 ~ 𝑑 superscript ℎ 2 superscript 2 𝑀 2 T>\tilde{d}h^{2-2^{-M+2}} .

In this case, we define $\gamma:=T^{\frac{1}{2-2^{-M+1}}}\tilde{d}^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}h^{\frac{2^{-M+1}}{2-2^{-M+1}}}\geq\tilde{d}$. Let

$$ $\displaystyle T_{1}=\gamma,\quad T_{2}=\gamma\frac{\sqrt{T_{1}}}{\sqrt{\tilde{d}h}},\quad T_{k}=\gamma\frac{\sqrt{T_{k-1}}}{\sqrt{\tilde{d}}},\forall 3\leq k\leq M.$ (41) $$

By the iteration rule, we have that $T_{k}=\gamma^{2-2^{-k+1}}\tilde{d}^{-1+2^{-k+1}}h^{-2^{-k+1}}$. In particular,
$\sum_{k=1}^{M}T_{k}\geq T_{M}=\gamma^{2-2^{-M+1}}\tilde{d}^{-1+2^{-M+1}}h^{-2^{-M+1}}=T$.

By definition, we have that $T_{1}\leq\gamma$ and $T_{2}\frac{\sqrt{\tilde{d}h}}{\sqrt{T_{1}}}\leq\gamma$. For $k=3$, we have that

$$ $\displaystyle\frac{T_{3}\sqrt{\tilde{d}}}{\sqrt{T_{2}}}=\gamma,\quad\quad\quad\frac{T_{3}\tilde{d}}{T_{1}}=\gamma^{\frac{3}{4}}\tilde{d}^{\frac{1}{4}}h^{-\frac{1}{4}}\leq\gamma.$ $$

For $4\leq k\leq M$, we have that

$$ $\displaystyle\frac{T_{k}\sqrt{\tilde{d}}}{\sqrt{T_{k-1}}}=\gamma,\quad\quad\quad\frac{T_{k}\tilde{d}}{T_{k-2}}=\gamma^{2^{-k+3}-2^{-k+1}}\tilde{d}^{1+2^{-k+1}-2^{-k+3}}h^{2^{-k+3}-2^{-k+1}}\leq\tilde{d}\left(\frac{\gamma h}{\tilde{d}}\right)^{\frac{3}{8}}.$ (42) $$

So it suffices to verify $\tilde{d}h^{\frac{3}{5}}\leq\gamma$. In fact we have that

$$ $\displaystyle\gamma^{2-2^{-M+1}}=T\tilde{d}^{1-2^{-M+1}}h^{2^{-M+1}}\geq\tilde{d}^{2-2^{-M+1}}h^{2-2^{-M+2}+2^{-M+1}}\geq\tilde{d}^{2-2^{-M+1}}h^{\frac{3}{5}(2-2^{-M+1})},$ (43) $$

which implies that $\tilde{d}h^{\frac{3}{5}}\leq\gamma$.

Therefore, the total regret in this case is bounded by

$$ $\displaystyle O\left(T^{\frac{1}{2-2^{-M+1}}}\tilde{d}^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}h^{\frac{2^{-M+1}}{2-2^{-M+1}}}\log\log(T)+MT^{2}\delta\right).$ (44) $$

We now finish the discuss about the two cases and combine the two regret upper bounds ([40](#S4.E40)) and ([44](#S4.E44)). Noting that $T>\tilde{d}h^{2-2^{-M+2}}$ implies that

$$ $\displaystyle T^{\frac{1}{2-2^{-M+2}}}\tilde{d}^{\frac{1-2^{-M+2}}{2-2^{-M+2}}}>T^{\frac{1}{2-2^{-M+1}}}\tilde{d}^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}h^{\frac{2^{-M+1}}{2-2^{-M+1}}},$ (45) $$

we have that

$$ $\displaystyle R_{T}$ $\displaystyle\leq O\left(\min\left\{T^{\frac{1}{2-2^{-M+2}}}\tilde{d}^{\frac{1-2^{-M+2}}{2-2^{-M+2}}},T^{\frac{1}{2-2^{-M+1}}}\tilde{d}^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}h^{\frac{2^{-M+1}}{2-2^{-M+1}}}\right\}\cdot\log\log(T)+MT^{2}\delta\right).$ $$

Setting $\delta=1/T^{3}$, we obtain that

$$ $\displaystyle R_{T}$ $\displaystyle\leq O\Bigg{(}\mathrm{poly}\ln(Td)\min\Big{\{}T^{\frac{1}{2-2^{-M+2}}}(d\ln(K))^{\frac{1-2^{-M+2}}{2-2^{-M+2}}},$ $\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad T^{\frac{1}{2-2^{-M+1}}}(d\ln(K))^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}\min\{K,d\}^{\frac{2^{-M+1}}{2-2^{-M+1}}}\Big{\}}\Bigg{)}.$ $$

Theorem [1](#Thmtheorem1) is proven. ∎

## 5 Learning the Exploration Policy

In this section, we formally describe the $\mathtt{ExplorationPolicy}$ procedure by Algorithm [2](#alg2). Suppose there is an unknown distribution $D$ over the context sets. Given a set of $m$ independent samples $\{Z_{i}\}_{i=1}^{m}$ drawn from $D$, the goal of Algorithm [2](#alg2) is to learn an exploration policy $\pi$ so that if one uses $\pi$ to collect $n$ more data points (including context vectors and observed rewards) and estimate the linear model $\boldsymbol{\theta}$, the expected size of the largest confidence interval among all actions in a random context set (as characterized by the LHS of ([31](#S4.E31)) in Lemma [7](#Thmlemma7)) will be small.

We now briefly explain our Algorithm [2](#alg2). Given a group of context vectors $\{Z_{i}\}_{i=1}^{m}$, the algorithm simulates the reward-free linear bandit algorithms. In each time step, the algorithm first clip the context vectors according the current information matrix $W$, and then chooses the arm with clipped maximal variance. The information matrix is updated with doubling trick, which helps reduce both the number of updates and the complexity of the output policy.

Figure: Algorithm 2 $\mathtt{ExplorationPolicy}$

In the rest of this section, we will prove Lemma [7](#Thmlemma7) on the guarantee of $\mathtt{ExplorationPolicy}$. For the readers’ convenience, we re-state the lemma as follows.

Lemma [7](#Thmlemma7) (restated). Let $\{Z_{u}\}_{u=1}^{m}$ be $m$ i.i.d. stochastic context sets following a distribution $D$. Let $\pi$ be the output by running $\mathtt{ExplorationPolicy}$ with the input $\{Z_{u}\}_{u=1}^{m}$. Let $\{\tilde{Z}_{u}\}_{u=1}^{n}$ be another group of i.i.d. stochastic context sets following the distribution $D$ (which is also independent from $\{Z_{u}\}_{u=1}^{m}$). Let $\boldsymbol{y}_{u}$ be independently sampled from $\pi(\tilde{Z}_{u})$ for each $u\in\{1,2,\dots,n\}$, and let $\Lambda=\sum_{u=1}^{n}\boldsymbol{y}_{u}\boldsymbol{y}_{u}^{\top}$. With probability $(1-3\delta)$, we have that

$$ $\displaystyle\mathop{\mathbb{E}}_{X\sim D}\left[\min\left\{\sqrt{\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}(\Lambda+\frac{n}{m}\kappa\mathbf{I})^{-1}\boldsymbol{x}},\sqrt{L}\right\}\right]\leq\sqrt{\frac{1}{n}}\cdot O\left(\sqrt{d\ln\left(\frac{md}{\kappa}\right)}\right)+\frac{\sqrt{L}}{m}\cdot O\left(d\ln\left(\frac{md}{\kappa}\right)\right).$ $\displaystyle\eqref{eq:lemma-design}$ $$

### 5.1 Analysis: Proof of Lemma 7

As stated in Section [3](#S3),
the proof of Lemma [7](#Thmlemma7) utilizes similar ideas in the proof of Theorem 5 in (Ruan et al., ). The major difference is that their information matrix starts with $\Omega(1)\cdot\mathbf{I}$ when executing the output policy, while our information matrix could start with $\kappa\mathbf{I}$ with $\kappa=\frac{1}{T^{2}}$. As a result, it is harder for us to recover the information matrix $U_{m}$.

Let $D$ be the distribution defined in the statement of Lemma [7](#Thmlemma7), we first prove the following lemma.

###### Lemma 8 .

With probability $(1-\delta)$, it holds that

$$ $\displaystyle m\mathop{\mathbb{E}}_{X\sim D}\left[\min\{\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}U_{m}^{-1}\boldsymbol{x},L\}\right]\leq O(d\ln(md/\kappa)).$ (47) $$

###### Proof.

Let $\eta_{i}$ denote the index $\eta$ such that $i\in\tau_{\eta}$. Note that $i\in\tau_{\eta}$ implies that $\det(U_{i-1})\leq 2\det(W_{\eta})$, which further implies that $\det((W_{\eta}^{-\frac{1}{2}})^{\top}U_{i-1}(W_{\eta})^{\frac{1}{2}})\leq 2$. Because $U_{i-1}\succcurlyeq W_{\eta}$, we have that $(W_{\eta}^{-\frac{1}{2}})^{\top}U_{i-1}(W_{\eta})^{\frac{1}{2}}\succcurlyeq\mathbf{I}$. Therefore, the maximal eigenvalue of $(W_{\eta}^{-\frac{1}{2}})^{\top}U_{i-1}(W_{\eta})^{\frac{1}{2}}\succcurlyeq\mathbf{I}$ is at most $2$, where it follows that $U_{i-1}\leq 2W_{\eta}$.

Since $U_{m}\succcurlyeq W_{\eta}$ for all $\eta\geq 1$, we have that

$$ $\displaystyle m\mathop{\mathbb{E}}_{X\sim D}\left[\min\{\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}U_{m}^{-1}\boldsymbol{x},L\}\right]\leq\sum_{i=1}^{m}\mathop{\mathbb{E}}_{X\sim D}\left[\min\{\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}W_{\eta_{i}}^{-1}\boldsymbol{x},L\}\right].$ (48) $$

Invoking Corollary [2](#Thmcorollary2) with $\epsilon=1$ and noting that $\mathop{\mathbb{E}}[\min\{\tilde{\boldsymbol{z}}_{i}^{\top}W_{\eta_{i}}^{-1}\tilde{\boldsymbol{z}}_{i},L\}]=\mathop{\mathbb{E}}_{X\sim D}\left[\min\{\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}W_{\eta_{i}}^{-1}\boldsymbol{x},L\}\right]$ when conditioned on the first $(i-1)$ iterations in Algorithm [2](#alg2), we have with probability $(1-\delta)$, it holds that

$$ $\displaystyle\sum_{i=1}^{m}\mathop{\mathbb{E}}_{X\sim D}\left[\min\{\max_{\boldsymbol{x}\in X}\boldsymbol{x}^{\top}W_{\eta_{i}}^{-1}\boldsymbol{x},L\}\right]\leq 2\sum_{i=1}^{m}\min\{\boldsymbol{z}_{i}^{\top}W_{\eta_{i}}^{-1}\boldsymbol{z}_{i},L\}+20L\ln(1/\delta).$ (49) $$

By the definition of $\tilde{\boldsymbol{z}}_{i}$, we further have that

$$ $\displaystyle\sum_{i=1}^{m}\min\{\boldsymbol{z}_{i}^{\top}W_{\eta_{i}}^{-1}\boldsymbol{z}_{i},L\}=\sum_{i=1}^{m}\tilde{\boldsymbol{z}}_{i}^{\top}W_{\eta_{i}}^{-1}\tilde{\boldsymbol{z}}_{i}\leq 2\sum_{i=1}^{m}\tilde{\boldsymbol{z}}_{i}^{\top}U_{i-1}^{-1}\tilde{\boldsymbol{z}}_{i}\leq O(d\ln(md/\kappa)),$ (50) $$

where the second last inequality is by the fact that $U_{i-1}\preccurlyeq 2W_{\eta_{i}}$, and the last inequality is by a direct application of the Elliptical Potential Lemma (Lemma [20](#Thmlemma20), stated and proved in Appendix [B.2](#A2.SS2)) and the fact that $0<L<1$.
Combining ([48](#S5.E48)), ([49](#S5.E49)), ([50](#S5.E50)) and the definition of $L$, we prove the lemma.
∎

To proceed, we have the lemma below.

###### Lemma 9 .

Define $V:=\mathbb{E}_{X\sim D,i\sim\pi(X)}\left[\min\left\{\frac{L}{\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i}},1\right\}\boldsymbol{x}_{i}\boldsymbol{x}_{i}^{\top}\right]$.
With probability $1-\delta$,

$$ $\displaystyle V\succcurlyeq\frac{1}{6m}U_{m}-\frac{1}{3m}\kappa\mathbf{I}.$ (51) $$

###### Proof.

Recall that $\mathcal{F}_{m^{\prime}}=\sigma(X_{1},X_{2},\ldots,X_{m^{\prime}-1})$.
By the definition of $\pi$, and noting that $U_{m}\geq W_{\eta_{u}}$ implies that $\frac{L}{\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i}}\geq\frac{L}{\boldsymbol{x}_{i}^{\top}W_{\eta_{u}}^{-1}\boldsymbol{x}_{i}}$ for $1\leq u\leq m$, we have that

$$ $\displaystyle mV$ $\displaystyle\succcurlyeq\sum_{u=1}^{m}\mathbb{E}\left[\boldsymbol{z}_{u,i_{u}}\boldsymbol{z}_{u,i_{u}}^{\top}|\mathcal{F}_{u}\right].$ $$

Noting that $\boldsymbol{z}_{u,i_{u}}^{\top}W_{\eta_{u}}^{-1}\boldsymbol{z}_{u,i_{u}}\leq L$ implies $\boldsymbol{z}_{u,i_{u}}\boldsymbol{z}_{u,i_{u}}^{\top}\leq LW_{\eta_{u}}\leq LU_{m}$, by Lemma [1](#Thmlemma1) with $Z_{m}=LU_{m}$ and $\epsilon=2$, with probability $(1-\delta)$, we have that

$$ $\displaystyle mV\succcurlyeq\mathbb{E}\left[\boldsymbol{z}_{u,i_{u}}\boldsymbol{z}_{u,i_{u}}^{\top}|\mathcal{F}_{u}\right]$ $\displaystyle\succcurlyeq\frac{1}{3}\sum_{u=1}^{m}\boldsymbol{z}_{u,i_{u}}\boldsymbol{z}_{u,i_{u}}^{\top}-\frac{100L\ln(Td/\delta)}{3}U_{m}$ $\displaystyle=\frac{1}{3}\sum_{u=1}^{m}\boldsymbol{z}_{u,i_{u}}\boldsymbol{z}_{u,i_{u}}^{\top}-\frac{1}{6}U_{m}=\frac{1}{6}U_{m}-\frac{1}{3}\kappa\mathbf{I},$ $$

and the conclusion follows by dividing $m$ on both sides of the inequality.
∎

Recall that $\Lambda=\sum_{u=1}^{n}\boldsymbol{y}_{u}\boldsymbol{y}_{u}^{\top}$. Let

$$ $\displaystyle\tilde{\Lambda}:=\sum_{u=1}^{n}\min\left\{\frac{L}{\boldsymbol{y}_{u}^{\top}U_{m}^{-1}\boldsymbol{y}_{u}},1\right\}\boldsymbol{y}_{u}\boldsymbol{y}_{u}^{\top}.$ $$

By definition we have that $\Lambda\succcurlyeq\tilde{\Lambda}$.

Noting that for any $1\leq u\leq n$,

$$ $\displaystyle\mathbb{E}\left[\min\left\{\frac{L}{\boldsymbol{y}_{u}^{\top}U_{m}^{-1}\boldsymbol{y}_{u}},1\right\}\boldsymbol{y}_{u}\boldsymbol{y}_{u}^{\top}\right]=\mathbb{E}_{X\sim D,i\sim\pi(X)}\left[\min\left\{\frac{L}{\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i}},1\right\}\boldsymbol{x}_{i}\boldsymbol{x}_{i}^{\top}\right]=V$ $$

and $\min\left\{\frac{L}{\boldsymbol{y}_{u}^{\top}U_{m}^{-1}\boldsymbol{y}_{u}},1\right\}\boldsymbol{y}_{u}\boldsymbol{y}_{u}^{\top}\preccurlyeq LU_{m}$, by Corollary [2](#Thmcorollary2) with $W=LU_{m}$ and $\epsilon=\frac{2}{3}$, with probability $1-\delta$,

$$ $\displaystyle\tilde{\Lambda}\succcurlyeq\frac{n}{3}V-\frac{68L}{3}U_{m}.$ $$

By Lemma [9](#Thmlemma9), we further have that

$$ $\displaystyle\Lambda$ $\displaystyle\succcurlyeq\tilde{\Lambda}\succcurlyeq\frac{n}{3}V-\frac{68L}{3}U_{m}\succcurlyeq\frac{n}{3}V-\frac{1}{6}U_{m}\succcurlyeq\frac{n}{3m}\left(\frac{1}{6}U_{m}-\frac{1}{3}\kappa\mathbf{I}\right)-\frac{1}{6}U_{m}=\frac{n}{36m}U_{m}-\frac{n}{9m}\kappa\mathbf{I}.$ $$

Therefore, $\Lambda+\frac{n}{m}\kappa\mathbf{I}\geq\frac{n}{36m}U_{m}$.

In the case $n\geq m$, we have that

$$ $\displaystyle\mathbb{E}_{X\sim D}\left[\min\left\{\sqrt{\max_{i}\boldsymbol{x}_{i}^{\top}\left(\Lambda+\frac{n}{m}\kappa\mathbf{I}\right)^{-1}\boldsymbol{x}_{i}},\sqrt{L}\right\}\right]$ $\displaystyle\leq\sqrt{\frac{36m}{n}}\mathbb{E}_{X\sim D}\left[\min\left\{\sqrt{\max_{i}\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i}},\sqrt{Ln/m}\right\}\right]$ $\displaystyle\leq\sqrt{\frac{36m}{n}}\mathbb{E}_{X\sim D}\left[\min\left\{\sqrt{\max_{i}\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i}},\sqrt{L}\right\}\right]+\sqrt{\frac{36m}{n}}\cdot\sqrt{\frac{Ln}{m}}\cdot\mathrm{Pr}_{X\sim D}\left[\max_{i}\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i}\geq L\right]$ $\displaystyle\leq\sqrt{\frac{36m}{n}}\sqrt{\mathbb{E}_{X\sim D}\left[\min\left\{\max_{i}\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i},L\right\}\right]}+\frac{\sqrt{L}}{m}\cdot O\left(d\ln\left(\frac{md}{\kappa}\right)\right)$ $\displaystyle\leq\sqrt{\frac{1}{n}}\cdot O\left(\sqrt{d\ln\left(\frac{md}{\kappa}\right)}\right)+\frac{\sqrt{L}}{m}\cdot O\left(d\ln\left(\frac{md}{\kappa}\right)\right).$ $$

Here the second last inequality and last inequality are by Lemma [8](#Thmlemma8) and the fact that

$$ $\displaystyle\mathrm{Pr}_{X\sim D}\left[\max_{i}\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i}\geq L\right]\leq\mathbb{E}_{X\sim D}\left[\min\{\max_{i}x^{\top}U_{m}^{-1}x,L\}\right]\leq\frac{1}{m}\cdot O\left(d\ln\left(\frac{md}{\kappa}\right)\right).$ $$

In the case $n<m$, with similar arguments we have that

$$ $\displaystyle\mathbb{E}_{X\sim D}\left[\min\left\{\sqrt{\max_{i}\boldsymbol{x}_{i}^{\top}\left(\Lambda+\frac{n}{m}\kappa\mathbf{I}\right)^{-1}\boldsymbol{x}_{i}},\sqrt{L}\right\}\right]$ $\displaystyle\leq\sqrt{\frac{36m}{n}}\mathbb{E}_{X\sim D}\left[\min\left\{\sqrt{\max_{i}\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i}},\sqrt{Ln/m}\right\}\right]$ $\displaystyle\leq\sqrt{\frac{36m}{n}}\mathbb{E}_{X\sim D}\left[\min\left\{\sqrt{\max_{i}\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i}},\sqrt{L}\right\}\right]$ $\displaystyle\leq\sqrt{\frac{36m}{n}}\sqrt{\mathbb{E}_{X\sim D}\left[\min\left\{\max_{i}\boldsymbol{x}_{i}^{\top}U_{m}^{-1}\boldsymbol{x}_{i},L\right\}\right]}$ $\displaystyle\leq\sqrt{\frac{1}{n}}\cdot O\left(\sqrt{d\ln\left(\frac{md}{\kappa}\right)}\right)$ $\displaystyle\leq\sqrt{\frac{1}{n}}\cdot O\left(\sqrt{d\ln\left(\frac{md}{\kappa}\right)}\right)+\frac{\sqrt{L}}{m}\cdot O\left(d\ln\left(\frac{md}{\kappa}\right)\right).$ $$

The proof is completed.

###### Lemma 8 .

###### Proof.

###### Lemma 9 .

###### Proof.

## 6 Proof of the Matrix Concentration Inequality with Dynamic Upper Bounds (Lemma 1 )

In this section, we present the proof of our new matrix concentration inequality with dynamic upper bounds. For convenience, we first restate the inequality (Lemma [1](#Thmlemma1)) as follows.

Lemma [1](#Thmlemma1) (restated). Consider a sequence of stochastic PSD matrices $W_{1},X_{1},W_{2},X_{2},\dots,W_{n},X_{n}\in\mathbb{R}^{d\times d}$. Let $\mathcal{F}_{k}=\sigma(W_{1},X_{1},W_{2},X_{2},\dots,W_{k-1},X_{k-1})$ and $\mathcal{F}_{k}^{+}=\sigma(W_{1},X_{1},W_{2},X_{2},\dots,W_{k-1},X_{k-1},W_{k})$ be the natural filtration and $Y_{k}=\mathbb{E}[X_{k}|\mathcal{F}_{k}^{+}]$ for each $k\in\{1,2,\dots,n\}$. Suppose $W_{k}$ is PD and increasing in $k$ (with respect to the semidefinite order) and $X_{k}\preccurlyeq W_{k}$ for each $k$. For every $\delta>0$ and $\epsilon\in(0,1)$, we have that

$$ $\displaystyle\qquad\quad\quad\Pr\left[\sum_{k=1}^{n}X_{k}\preccurlyeq(1+\epsilon)\sum_{k=1}^{n}Y_{k}+\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}\ln((n+1)d/\delta)W_{n}\right]\geq 1-\delta;\qquad$ $\displaystyle\eqref{eq:con1}$ $\displaystyle\Pr\left[\sum_{k=1}^{n}X_{k}\succcurlyeq(1-\epsilon)\sum_{k=1}^{n}Y_{k}-\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}\ln((n+1)d/\delta)W_{n}\right]\geq 1-\delta.\qquad$ $\displaystyle\eqref{eq:con2}$ $$

Before we start the proof, we introduce some basic properties of PSD matrices as below, whose proof is deferred to Appendix [C.1](#A3.SS1).

###### Fact 1 .

For any two PD matrices $A$ and $B$, $A\preccurlyeq B$ is equivalent to each of the following inequalities,

$$ $\displaystyle B^{-1}$ $\displaystyle\preccurlyeq A^{-1},$ (52) $\displaystyle A^{1/2}B^{-1}A^{1/2}$ $\displaystyle\preccurlyeq\mathbf{I},$ (53) $\displaystyle B^{-1/2}AB^{-1/2}$ $\displaystyle\preccurlyeq\mathbf{I}.$ (54) $$

We now start to prove Lemma [1](#Thmlemma1), while the two helpful technical lemmas (Lemma [10](#Thmlemma10) and Lemma [11](#Thmlemma11)), are deferred to Section [6.1](#S6.SS1) and Section [6.2](#S6.SS2).

###### Proof of Lemma 1 .

We first prove Equation ([3](#S1.E3)).
For each $k\in\{0,1,2,\dots,n\}$, let $Z_{k}=\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}W_{k}$ and

$$ $E_{k}:=\mathrm{Tr}\left(\exp\left(Z_{k}^{-1/2}\left(\sum_{i=1}^{k}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{k}^{-1/2}\right)\right).$ $$

By Lemma [10](#Thmlemma10), we have that $\mathbb{E}[E_{n}]\leq(n+1)d$. Therefore, by Markov inequality,

$$ $\displaystyle\quad\Pr\left[\lambda_{\max}\left(Z_{n}^{-1/2}\left(\sum_{i=1}^{n}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{n}^{-1/2}\right)\geq C\right]$ $\displaystyle\leq\Pr\left[\mathrm{Tr}\left(\exp\left(Z_{n}^{-1/2}\left(\sum_{i=1}^{n}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{n}^{-1/2}\right)\right)\geq e^{C}\right]\leq\frac{\mathbb{E}[E_{n}]}{e^{C}}\leq(n+1)de^{-C},$ $$

which (by Fact [1](#Thmfact1)) means that

$$ $\displaystyle\Pr\left[\sum_{i=1}^{n}(X_{i}-(1+\epsilon)Y_{i})\preccurlyeq CZ_{n}\right]\geq 1-(n+1)de^{-C}.$ $$

Choosing $C=\ln((n+1)d/\delta)$ and recalling that $Z_{n}=\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}W_{n}$, we prove Equation ([3](#S1.E3)).

We then prove Equation ([4](#S1.E4)). First we define

$$ $\displaystyle E_{k}^{\prime}:=\mathrm{Tr}\left(\exp\left(Z_{k}^{-1/2}\left(\sum_{i=1}^{k}((1-\epsilon)Y_{i}-X_{i})\right)Z_{k}^{-1/2}\right)\right).$ $$

Similarly, by Lemma [11](#Thmlemma11), we have that $\mathbb{E}[E_{n}^{\prime}]\leq(n+1)d$ and

$$ $\displaystyle\quad\Pr\left[\lambda_{\max}\left(Z_{n}^{-1/2}\left(\sum_{i=1}^{n}((1-\epsilon)Y_{i}-X_{i})\right)Z_{n}^{-1/2}\right)\geq C\right]$ (55) $\displaystyle\leq\Pr\left[\mathrm{Tr}\left(\exp\left(Z_{n}^{-1/2}\left(\sum_{i=1}^{n}((1-\epsilon)Y_{i}-X_{i})\right)Z_{n}^{-1/2}\right)\right)\geq e^{C}\right]\leq\frac{\mathbb{E}[E^{\prime}_{n}]}{e^{C}}\leq(n+1)de^{-C},$ $$

which means that

$$ $\displaystyle\mathrm{Pr}\left[\sum_{i=1}^{n}\left((1-\epsilon)Y_{i}-X_{i}\right)\preccurlyeq CZ_{n}\right]\geq 1-(n+1)de^{-C}.$ $$

Choosing $C=\ln((n+1)d/\delta)$ we finish the proof.
∎

###### Corollary 2 .

Given a sequence of stochastic random variables $X_{1},X_{2},\ldots,X_{n}$ such that $0\leq X_{i}\leq W$ for any $1\leq i\leq n$ with probability $1$. Let $\mathcal{F}_{k}=\sigma(X_{1},X_{2},\dots,X_{k-1})$ and $Y_{k}=\mathbb{E}[X_{k}|\mathcal{F}_{k}]$
For every $\delta>0$ and $\epsilon>0$, we have that

$$ $\displaystyle\Pr\left[\sum_{k=1}^{n}X_{k}\leq(1+\epsilon)\sum_{k=1}^{n}Y_{k}+\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}\ln((n+1)/\delta)W\right]\geq 1-\delta;$ $\displaystyle\Pr\left[\sum_{k=1}^{n}X_{k}\geq(1-\epsilon)\sum_{k=1}^{n}Y_{k}-\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}\ln((n+1)/\delta)W\right]\geq 1-\delta.$ $$

###### Proof.

Letting $d=1$ and $W_{k}=W$ for $1\leq k\leq n$, by Lemma [1](#Thmlemma1) we finish the proof.
∎

###### Fact 1 .

###### Proof of Lemma 1 .

###### Corollary 2 .

###### Proof.

### 6.1 Statement and Proof of Lemma 10

###### Lemma 10 .

For each $k\in\{1,2,\dots,n\}$, we have that

$$ $\displaystyle\mathbb{E}\left[E_{k}|\mathcal{F}_{k}^{+}\right]\leq\mathbb{E}\left[E_{k-1}|\mathcal{F}_{k}^{+}\right]+d.$ $$

###### Proof.

Firstly, we introduce a deep theorem from Lieb (Theorem 6, (Lieb, )), which provides theoretical basis for a series of concentration inequalities on self-adjoint matrices.

###### Theorem 5 .

Fix a $d$-dimensional symmetric matrix $H$. The function $f(A):=\mathrm{Tr}(\exp(\log(A)+H))$ is concave on the $d$-dimensional positive definite cone.

Based on Theorem [5](#Thmtheorem5), (Tropp, ) derived the corollary below.

###### Corollary 3 .

Fix a self-adjoint matrix $H$. Let $X$ be stochastic symmetric matrix

$$ $\displaystyle\mathbb{E}\left[\mathrm{Tr}\left(\exp(X+H)\right)\right]\leq\mathrm{Tr}\left(\mathbb{E}[e^{X}]+H\right).$ (56) $$

Given Corollary [3](#Thmcorollary3) we continue the analysis as below.
Note that $\mathbb{E}\left[E_{k-1}|\mathcal{F}_{k}^{+}\right]$ is a deterministic value. Throughout this proof, we will condition on $\mathcal{F}_{k}^{+}$. We calculate that

$$ $\displaystyle\quad\mathbb{E}\left[E_{k}\right]$ $\displaystyle=\mathbb{E}\left[\mathrm{Tr}\left(\exp\left(Z_{k}^{-1/2}\left(\sum_{i=1}^{k}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{k}^{-1/2}\right)\right)\right]$ $\displaystyle=\mathbb{E}\left[\mathrm{Tr}\left(\exp\left(Z_{k}^{-1/2}\left(\sum_{i=1}^{k-1}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{k}^{-1/2}+Z_{k}^{-1/2}(X_{k}-(1+\epsilon)Y_{k})Z_{k}^{-1/2}\right)\right)\right]$ $\displaystyle\leq\mathrm{Tr}\left(\exp\left(Z_{k}^{-1/2}\left(\sum_{i=1}^{k-1}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{k}^{-1/2}+\ln\left(\mathbb{E}\left[\exp\left(Z_{k}^{-1/2}(X_{k}-(1+\epsilon)Y_{k})Z_{k}^{-1/2}\right)\right]\right)\right)\right)$ (57) $\displaystyle\leq\mathrm{Tr}\left(\exp\left(Z_{k}^{-1/2}\left(\sum_{i=1}^{k-1}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{k}^{-1/2}\right)\right)$ (58) $\displaystyle=\mathrm{Tr}\left(\exp\left(Z_{k}^{-1/2}Z_{k-1}^{1/2}Z_{k-1}^{-1/2}\left(\sum_{i=1}^{k-1}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{k-1}^{1/2}Z_{k-1}^{-1/2}Z_{k}^{-1/2}\right)\right)$ $\displaystyle\leq\mathrm{Tr}\left(\exp\left(Z_{k-1}^{-1/2}\left(\sum_{i=1}^{k}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{k-1}^{-1/2}\right)\right)+d$ (59) $\displaystyle=E_{k-1}+d.$ $$

Here ([57](#S6.E57)) is by Corollary [3](#Thmcorollary3),
([58](#S6.E58)) is by Lemma [12](#Thmlemma12) (stated and proved in Section [6.2](#S6.SS2)) and the monotonicity of trace exponential with respect to the semidefinite order (see (Petz, ), §2.2), and ([59](#S6.E59)) is by Lemma [13](#Thmlemma13) (stated and proved in Section [6.3](#S6.SS3), letting $U=Z_{k-1}^{1/2}Z_{k}^{-1/2}$ and $A=Z_{k-1}^{-1/2}\left(\sum_{i=1}^{k}(X_{i}-(1+\epsilon)Y_{i})\right)Z_{k-1}^{-1/2}$, and one can verify that $U^{\top}U=Z_{k-1}^{1/2}Z_{k}^{-1}Z_{k-1}^{1/2}\preccurlyeq\mathbf{I}$ by Fact [1](#Thmfact1)).
∎

Similarly, we may establish the following lemma, whose proof is deferred to Appendix [C.2](#A3.SS2).

###### Lemma 11 .

For each $k\in\{1,2,\dots,n\}$, we have that

$$ $\displaystyle\mathbb{E}\left[E^{\prime}_{k}|\mathcal{F}_{k}^{+}\right]\leq\mathbb{E}\left[E^{\prime}_{k-1}|\mathcal{F}_{k}^{+}\right]+d.$ $$

###### Lemma 10 .

###### Proof.

###### Theorem 5 .

###### Corollary 3 .

###### Lemma 11 .

### 6.2 Statement and Proof of Lemma 12

###### Lemma 12 .

For each $k\in\{1,2,\dots,n\}$, we have that

$$ $\mathbb{E}\left[\exp\left(Z_{k}^{-1/2}(X_{k}-(1+\epsilon)Y_{k})Z_{k}^{-1/2}\right)\Big{|}\mathcal{F}_{k}^{+}\right]\preccurlyeq\mathbf{I}.$ $$

###### Proof.

Throughout this proof, we will condition on $\mathcal{F}_{k}^{+}$. Let $U_{k}:=Z_{k}^{-1/2}X_{k}Z_{k}^{-1/2}$ and $V_{k}:=Z_{k}^{-1/2}Y_{k}Z_{k}^{-1/2}$. By the assumption in Lemma [1](#Thmlemma1) and our definition for $Z_{k}$, we have that $0\preccurlyeq U_{k}\preccurlyeq\frac{\epsilon}{4(\epsilon^{2}+2\epsilon+2)}\mathbf{I}$ and $\mathbb{E}[U_{k}]=V_{k}$. Therefore, $0\preccurlyeq V_{k}\preccurlyeq\frac{\epsilon}{4(\epsilon^{2}+2\epsilon+2)}\mathbf{I}$. We now compute that

$$ $\displaystyle\quad\mathbb{E}\left[\exp\left(Z_{k}^{-1/2}(X_{k}-(1+\epsilon)Y_{k})Z_{k}^{-1/2}\right)\right]$ $\displaystyle=\mathbb{E}\left[\exp\left(U_{k}-(1+\epsilon)V_{k}\right)\right]$ $\displaystyle=\mathbb{E}\left[\mathbf{I}+(U_{k}-(1+\epsilon)V_{k})+\frac{1}{2}(U_{k}-(1+\epsilon)V_{k})^{2}+\sum_{i\geq 3}\frac{1}{i!}(U_{k}-(1+\epsilon)V_{k})^{i}\right]$ (60) $\displaystyle\leq\mathbb{E}\left[\mathbf{I}+(U_{k}-(1+\epsilon)V_{k})+\frac{1}{2}(U_{k}-(1+\epsilon)V_{k})^{2}+\sum_{i\geq 3}\frac{1}{i!}(U_{k}-(1+\epsilon)V_{k})^{2}\right]$ (61) $\displaystyle\preccurlyeq\mathbb{E}\left[\mathbf{I}+(U_{k}-(1+\epsilon)V_{k})+2(U_{k}-(1+\epsilon)V_{k})^{2}\right]$ $\displaystyle\preccurlyeq\mathbb{E}\left[\mathbf{I}+(U_{k}-(1+\epsilon)V_{k})+4U_{k}^{2}+4(1+\epsilon)^{2}V_{k}^{2}\right]$ (62) $\displaystyle\preccurlyeq\mathbb{E}\left[\mathbf{I}+(U_{k}-(1+\epsilon)V_{k})+\frac{4\epsilon}{4(\epsilon^{2}+2\epsilon+2)}U_{k}+\frac{4(1+\epsilon)^{2}\epsilon}{4(\epsilon^{2}+2\epsilon+2)}V_{k}\right]$ (63) $\displaystyle=\mathbf{I}.$ $$

Here, ([60](#S6.E60)) is by Taylor series expansion, ([61](#S6.E61)) is by the fact that $-\mathbf{I}\preccurlyeq(U_{k}-(1+\epsilon)V_{k})\preccurlyeq\mathbf{I}$ and $X^{k}-X^{2}=X(X^{k-2}-\mathbf{I})X\preccurlyeq 0$ for $k\geq 2$ and $-\mathbf{I}\preccurlyeq X\preccurlyeq\mathbf{I}$. ([62](#S6.E62)) is because $4U_{k}^{2}+4(1+\epsilon)^{2}V_{k}^{2}-2(U_{k}-(1+\epsilon)V_{k})^{2}=2(U_{k}+(1+\epsilon)V_{k})^{2}\succcurlyeq 0$, and ([63](#S6.E63)) is by the fact that $\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}U_{k}^{2}-U_{k}=U_{k}^{1/2}\left(\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}U_{k}-\mathbf{I}\right)U_{k}^{1/2}\preccurlyeq 0$ and $\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}V_{k}^{2}-V_{k}=V_{k}^{1/2}\left(\frac{4(\epsilon^{2}+2\epsilon+2)}{\epsilon}V_{k}-\mathbf{I}\right)V_{k}^{1/2}\preccurlyeq 0$.
∎

###### Lemma 12 .

###### Proof.

### 6.3 Statement and Proof of Lemma 13

###### Lemma 13 .

Let $A$ be a real symmetric matrix. For any $U$ such that $U^{\top}U\preccurlyeq\mathbf{I}$, it holds that

$$ $\displaystyle\mathrm{Tr}(\exp(U^{\top}AU))\leq\mathrm{Tr}(\exp(A))+d.$ (64) $$

###### Proof.

We can assume without loss of generality that $A=\mathrm{diag}(\lambda_{1},\lambda_{2},\dots,\lambda_{d})$ and $\lambda_{d}\leq\lambda_{d-1}\leq\dots\leq\lambda_{\ell-1}<0\leq\lambda_{\ell}\leq\dots\leq\lambda_{1}$.

Let us write $U^{\top}=Q^{\top}L^{\top}$ to be its QR decomposition where $Q^{\top}$ is orthogonal and $L^{\top}$ is an upper triangular matrix (and therefore $L$ is a lower triangular matrix). We claim that

$$ $\displaystyle U^{\top}\mathbf{I}_{j}U\preccurlyeq Q^{\top}\mathbf{I}_{j}Q,$ (65) $$

where we define $\mathbf{I}_{j}:=\mathrm{diag}(0,\dots,0,1,\dots 1)$ to be a rank $j$ matrix. Note that $U^{\top}\mathbf{I}_{j}U=Q^{\top}L^{\top}\mathbf{I}_{j}LQ$. Therefore, to prove the claim, it suffices to show that $L^{\top}\mathbf{I}_{j}L\preccurlyeq\mathbf{I}_{j}$. Since $U^{\top}U\preccurlyeq\mathbf{I}$, we also have that $L^{\top}L=QU^{\top}UQ^{\top}\preccurlyeq\mathbf{I}$. Note that for any vector $x$, it holds that $x^{\top}(L\mathbf{I}_{j})^{\top}(L\mathbf{I}_{j})x=(\mathbf{I}_{j}x)^{\top}L^{\top}L(\mathbf{I}_{j}x)\leq x^{\top}\mathbf{I}_{j}x$. Therefore we conclude that $L^{\top}\mathbf{I}_{j}L=(L\mathbf{I}_{j})^{\top}(L\mathbf{I}_{j})\preccurlyeq\mathbf{I}_{j}$, where the first equality holds because $L$ is a lower triangular matrix.

Let $\tilde{\lambda}_{i}:=\lambda_{i}-\lambda_{i-1}\geq 0$ for each $i\in\{1,2,\dots,\ell-1\}$, $\tilde{\lambda}_{\ell}:=\lambda_{\ell}\geq 0$, and $\tilde{\lambda}_{j}:=0$ for each $j\in\{\ell+1,\ell+2,\dots,d\}$. By ([65](#S6.E65)), we then have that

$$ $U^{\top}AU\preccurlyeq\sum_{j=1}^{d}\tilde{\lambda}_{j}U^{\top}\mathbf{I}_{j}U\preccurlyeq\sum_{j=1}^{d}\tilde{\lambda}_{j}Q^{\top}\mathbf{I}_{j}Q.$ $$

By the monotonicity of trace exponential with respect to the semidefinite order (see, e.g. (Petz, ) §2.2), we have that

$$ $\displaystyle\mathrm{Tr}(\exp(U^{\top}AU))$ $\displaystyle\leq\mathrm{Tr}\left(\exp\left(\sum_{j=1}^{d}\tilde{\lambda}_{j}Q^{\top}\mathbf{I}_{j}Q\right)\right)$ $\displaystyle=\sum_{j=1}^{d}\exp\left(\sum_{i=j}^{d}\tilde{\lambda}_{i}\right)\leq\sum_{j=1}^{d}\exp(\lambda_{i})+d=\mathrm{Tr}(\exp(A))+d.$ $$

∎

###### Lemma 13 .

###### Proof.

## 7 Regret Lower Bound for Context-blind Batch Learning

In this section, we prove Lemma [14](#Thmlemma14), which implies the regret lower bound theorem (Theorem [2](#Thmtheorem2)).

###### Lemma 14 .

For any algorithm $\mathcal{G}$ with batch complexity $M$, assuming $T\geq d\log_{2}(K)$, the minimax regret is at least

$$ $\displaystyle\Omega\left(\frac{1}{\mathrm{poly}\ln(Td)}\min\left\{\begin{aligned} &T^{\frac{1}{2-2^{-M+1}}}(d\log_{2}(K))^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}\left(\frac{\min\{K,d\}}{\log_{2}(K)}\right)^{\frac{2^{-M+1}}{2-2^{-M+1}}}\\ &T^{\frac{1}{2-2^{-M+2}}}(d\log_{2}(K))^{\frac{1-2^{-M+2}}{2-2^{-M+2}}}\end{aligned}\right\}\right).$ $$

###### Proof.

Define $\bar{d}=d/M$ and $\tilde{h}=\frac{1}{2}\min\{K,\bar{d}\}$. Define $\check{d}=\frac{\bar{d}\log_{2}(K)}{M\ln(dM)}\leq d\log_{2}(K)\leq d$ and $\check{h}=\frac{\tilde{h}}{\log_{2}(K)}$.
When $\check{d}\leq T\leq\check{d}\check{h}^{2-2^{-M+2}}$, define
$\gamma:=T^{\frac{1}{2-2^{-M+2}}}\check{d}^{\frac{1-2^{-M+2}}{d^{2-2^{-M+2}}}}$. When $T>\check{h}^{2-2^{-M+2}}$, define $\gamma:=T^{\frac{1}{2-2^{-M+1}}}\check{d}^{\frac{1-2^{-M+1}}{2-2^{-M+1}}}\check{h}^{\frac{2^{-M+1}}{2-2^{-M+1}}}\geq\check{d}$. Given $\gamma$, we further define
$T_{1}=\gamma$, $T_{2}=\max\{\gamma,\gamma\cdot\sqrt{\frac{T_{1}\ln(dM)}{\bar{d}h}}\}$ and $T_{k}=\gamma\cdot\sqrt{\frac{MT_{k-1}\ln(dM)}{\bar{d}\log_{2}(K)}}$ for any $3\leq k\leq M$.
Let $\epsilon_{1}=\frac{1}{100}$, $\epsilon_{2}=\min\left\{\frac{1}{100}\sqrt{\frac{\bar{d}^{2}}{T_{1}\ln(dM)}},1\right\}$ and $\epsilon_{k}=\frac{1}{100}\sqrt{\frac{\bar{d}\log_{2}(K)}{MT_{k-1}\ln(dM)}}$ for $k=3,4,\ldots,M$.

Fix the algorithm $\mathcal{G}$. Below we assume the randomness of $\mathcal{G}$ is considered in the expectation operator $\mathbb{E}[\cdot]$ and probability operator $\mathrm{Pr}[\cdot]$. Let $\mathrm{Regret}_{\theta,D}(T)$ be the expected regret under $\mathcal{G}$ with hidden parameter as $\theta$ and context distribution as $D$. We aim to design $D$ and $\theta$ such that $\mathrm{Regret}_{\theta,D}(T)$ is large enough.

Without loss of generality, we assume $d/M$ is an integer. In the construction below, we divide $\mathbb{R}^{d}$ into $M$ subspaces, where for each subspace we construct a hard case.
We let $\mathbb{R}^{d}=\otimes_{i=1}^{M}\mathcal{U}^{i}$, where $U^{i}$ is the subspace spanned by $\{\mathbf{e}_{(i-1)d/M+j}\}_{j=1}^{d/M}$.
In each round the noise is set to be Gaussian with variance $1$.
The hidden parameter $\theta=\{\theta^{i}\}_{i=1}^{M}$ is chosen from the space $\mathcal{Y}=\otimes_{i=1}^{M}\mathcal{Y}^{i}$. The context distribution $D$ is given by the average of $\{D^{i}\}_{i=1}^{M}$. That is, in the $t$-th round, the environment first sample $u_{t}\sim\mathrm{Uniform}(\{1,2,\ldots,M\})$, and then sample $X$ according to $D_{u_{t}}$.
In words, we divide the original problem into $M$ independent sub-problems. For the $k$-th sub-problem is $d/M$, the dimension is $d/M$, the parameter space is $\mathcal{Y}^{k}$ and the context distribution is $D_{k}$.

We now define $\mathcal{Y}^{k}$ and $D_{k}$.
Let $\bar{d}=d/M$.
We have two cases: Case I: $k=2$; and Case II: $k=1$ or $3\leq k\leq M$.
Below we respectively define the parameter space $\mathcal{Y}^{k}$ for $\theta^{k}$ and the context distribution $D_{k}$.

###### Lemma 14 .

###### Proof.

##### Case I: k = 2 𝑘 2 k=2 .

Define $\mathcal{Y}^{2}=\left\{-\epsilon_{2},0,\epsilon_{2}\right\}^{\bar{d}}$. Recall that $\tilde{h}=\frac{1}{2}\min\{K,\bar{d}\}$. For $\mathcal{V}\subset[2\tilde{h}]$ with $|\mathcal{V}|=\tilde{h}$, we define the context distribution $D_{2}(\mathcal{V})$ by letting $\mathrm{Pr}_{X\sim D_{2}(\mathcal{V})}[X=\{\mathbf{e}_{j}\}_{j\in\mathcal{V}}\cup\{\mathbf{e}_{i}\}]=\frac{1}{\bar{d}-\tilde{h}}$ for any $i\in[\bar{d}]/\mathcal{V}$. In words, the sub-problem for the second batch is a contextual bandit problem with $\tilde{h}+1$ arms. Among the $h+1$ arms, there are $\tilde{h}$ arms which appear in each round, and the left arms appears with equal probability as $\frac{1}{\bar{d}-\tilde{h}}$.

In the case $K\gg\tilde{h}+1$, we simply repeat the first arm for $K-(\tilde{h}+1)$ times to construct the $K$-armed linear bandit problem.
Without loss of generality, we still use $D_{2}(\mathcal{V})$ to denote this context.
For fixed $\mathcal{V}$ and $\xi\in\{-1,1\}^{\bar{d}}$, we further define $\theta^{2}(\mathcal{V},\xi)$ by setting $\theta^{2}_{i}(\mathcal{V},\xi)=0$ for $i\in\mathcal{V}$ and $\theta^{2}_{i}(\mathcal{V},\xi)=\xi_{i}\epsilon_{2}$ for $i\in[\bar{d}]/\mathcal{V}$.

Since the sub-problem is a contextual bandit problem, we could view the context $X$ as a subset of $[\bar{d}]$.
Given a permutation $\sigma\in S_{\bar{d}}$ and a context $X\subset[\bar{d}]$, we define the context vector $\sigma(X)=\{\sigma(i)\}_{i\in X}$. With a slight abuse of notations, we use $D_{2}(\sigma)$ as the shorthand for $D_{2}(\sigma([1,2,\ldots,\tilde{h}]))$.

Let the policy $\pi_{1}$ be the policy for the first batch.
Clearly, $\pi_{1}$ is independent of the context distribution. Let the distribution of $\pi_{1}$ be $\Pi_{1}$. We then claim the following lemma.

###### Lemma 15 .

$$ $\displaystyle\min_{\sigma\in S_{\bar{d}}}\mathbb{E}_{\pi_{1}\sim\Pi_{1}}\mathbb{E}_{X\sim D(\sigma)}\left[\mathbb{I}\left[\pi_{1}(X)\notin\{\sigma(1),\sigma(2),\ldots,\sigma(\tilde{h})\}\right]\right]\leq\frac{1}{\tilde{h}+1}.$ $$

###### Proof.

Let $\mathcal{A}$ be the set of subsets of $[\bar{d}]$ with size $\tilde{h}+1$. Let $Z_{i}=\{1,2,\ldots,\tilde{h},\tilde{h}+i\}$ for $1\leq i\leq\bar{d}-\tilde{h}$.
Note that for any $1\leq i\leq\bar{d}-\tilde{h}$ and $\sigma\in S_{\bar{d}}$, $\pi(\sigma(Z_{i}))\notin\{\sigma(1),\sigma(2),\ldots,\sigma(\tilde{h})\}$ implies that $\pi(X)=\sigma(\tilde{h}+i)$. Then we have that

$$ $\displaystyle\sum_{\sigma\in S_{\bar{d}}}\frac{1}{\bar{d}!}\mathbb{E}_{\pi_{1}\sim\Pi_{1}}\mathbb{E}_{X\sim D_{2}(\sigma)}\left[\mathbb{I}\left[\pi_{1}(X)\notin\{\sigma(1),\sigma(2),\ldots,\sigma(\tilde{h})\}\right]\right]$ $\displaystyle=\frac{1}{\bar{d}!(\bar{d}-\tilde{h})}\sum_{X\in\mathcal{A}}\sum_{\sigma\in S_{\bar{d}}}\sum_{i=1}^{d_{1}}\mathbb{I}[\sigma^{-1}(X)=Z_{i}]\mathbb{E}_{\pi_{1}\sim\Pi_{1}}\left[\mathbb{I}\left[\pi_{1}(X)=\sigma(\tilde{h}+i)\right]\right]$ $\displaystyle=\frac{1}{\bar{d}!(\bar{d}-\tilde{h})}\sum_{X\in\mathcal{A}}\mathbb{E}_{\pi_{1}\sim\Pi_{1}}\left[\sum_{i=1}^{\bar{d}-\tilde{h}}\sum_{\sigma\in S_{\bar{d}}}\mathbb{I}[\sigma^{-1}(X)=Z_{i},\pi_{1}(X)=\sigma(h+i)]\right]$ $\displaystyle=\frac{1}{\bar{d}!(\bar{d}-\tilde{h})}\sum_{X\in\mathcal{A}}\mathbb{E}_{\pi_{1}\sim\Pi_{1}}\left[\sum_{i=1}^{d_{1}}\sum_{\sigma\in S_{\bar{d}},x\in X}\mathbb{I}[\sigma^{-1}(X)=Z_{i},\pi_{1}(X)=x,x=\sigma(\tilde{h}+i)]\right]$ $\displaystyle=\frac{1}{\bar{d}!(\bar{d}-\tilde{h})}\sum_{X\in\mathcal{A},x\in X}\mathrm{Pr}_{\pi_{1}\sim\Pi_{1}}\left[\pi_{1}(X)=x\right]\cdot\sum_{\sigma\in S_{\bar{d}}}\sum_{i=1}^{\bar{d}-\tilde{h}}\mathbb{I}[\sigma^{-1}(X)=Z_{i},x=\sigma(\tilde{h}+i)]$ $\displaystyle=\frac{\tilde{h}!(\bar{d}-\tilde{h}-1)!}{\bar{d}!}\sum_{X\in\mathcal{A},x\in X}\mathrm{Pr}_{\pi_{1}\sim\Pi_{1}}\left[\pi_{1}(X)=x\right]$ $\displaystyle=\frac{\tilde{h}!(\bar{d}-\tilde{h}-1)!}{\bar{d}!}\sum_{X\in\mathcal{A}}1$ $\displaystyle=\frac{\tilde{h}!(\bar{d}-\tilde{h}-1)!}{\bar{d}!}|\mathcal{A}|$ $\displaystyle=\frac{1}{\tilde{h}+1}.$ (66) $$

Then the conclusion follows easily.
∎

Without loss of generality, we suppose that the identical permutation satisfies the condition in Lemma [15](#Thmlemma15), i.e.,

$$ $\displaystyle\mathbb{E}_{\pi_{1}\sim\Pi_{1}}\mathbb{E}_{X\sim D_{2}([\tilde{h}])}\mathbb{I}\left[\pi_{1}(X)\notin\{1,2,\ldots,\tilde{h}\}\right]\leq\frac{1}{\tilde{h}+1}.$ (67) $$

Define $J=\{i\geq\tilde{h}+1|\mathbb{E}_{\pi_{1}\sim\Pi_{1}}\mathbb{E}_{X\sim D}\mathbb{I}[\pi(X)=i]\leq\frac{2}{(\tilde{h}+1)(\bar{d}-\tilde{h})}\}$, then by ([67](#S7.E67)) we have that $|J|\geq\frac{\bar{d}-\tilde{h}}{2}$. Without loss of generality, we assume $J=\{\tilde{h}+1,\tilde{h}+2,\ldots,\tilde{h}+\ell\}$ where $\ell\geq\frac{\bar{d}-\tilde{h}}{2}$ is the size of $J$.
Then the context distribution is fixed as $D_{2}=D_{2}([\tilde{h}])$.

###### Lemma 15 .

###### Proof.

##### Case II: k = 1 𝑘 1 k=1 or 3 ≤ k ≤ M 3 𝑘 𝑀 3\leq k\leq M .

We consider to construct the hard case for $K$-armed linear contextual bandit problem. We assume $a=\min\{\log_{2}(K),\bar{d}\}$ and $b=\bar{d}/a$ are both integers.
Define $\mathcal{Y}^{k}=\epsilon_{k}\cdot\{-1,1\}^{\bar{d}}$. The context distribution $D^{k}$ is defined as the uniform distribution over $X^{k,i}=\frac{1}{a}\cdot\{\boldsymbol{x}:\boldsymbol{x}_{i}=0,\forall i\notin[(i-1)a+1,ia],\boldsymbol{x}_{i}\in\{-1,1\},\forall i\in[(i-1)a+1,ia]\}$ for $1\leq i\leq b$.

Now we start to analyze the minimax lower bound over all $\theta\in\mathcal{Y}$ and the context distribution $D$ described above.
Let $\{t_{i}\}_{i=1}^{M}$ be the time schedule by running the algorithm $\mathcal{G}$. Then there exists $1\leq i\leq M$ such that $\sum_{j\leq i-1}t_{j}\leq\sum_{j\leq i-1}T_{j}<\sum_{j\leq i}T_{j}\leq\sum_{j\leq i}t_{j}$, where we define $T_{0}=t_{0}=0$.
Denote $\mathcal{E}_{i}$ be the event where $i$ is the smallest number such that $\sum_{j\leq i}t_{i}\leq\sum_{j\leq i}T_{i}<\sum_{j\leq i+1}T_{i+1}\leq\sum_{j\leq i+1}t_{i+1}$. Then it holds that $\sum_{i=1}^{M}\mathbb{I}[\mathcal{E}_{i}]=1$.

To proceed, we have the lemma as below.

###### Lemma 16 .

Let $\pi_{k}$ be the policy for the $k$-th batch and $\pi_{(t)}$ be the policy for the $t$-th step.
Fix $j\in[\tilde{h}+1,\tilde{h}+\ell]$. For $\theta\in\mathcal{Y}$, we define

$$ $\displaystyle R_{j}^{k}(\theta)=\left\{\begin{aligned} &\frac{1}{\bar{d}-\tilde{h}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\mathbb{E}_{\theta,\boldsymbol{x}\sim\pi_{(t)}([\tilde{h}]\cap\{\tilde{h}+j\})}\left[\mathbb{I}[\boldsymbol{x}=j,\theta_{j}^{2}<0]+\mathbb{I}[\boldsymbol{x}\neq j,\theta_{j}^{2}>0]\right]\cdot\epsilon_{2},\quad k=2;\\ &\frac{1}{\bar{d}}\sum_{t=\mathcal{T}_{k-1}+1}^{\mathcal{T}_{k}}\mathbb{E}_{\theta,\boldsymbol{x}\sim\pi_{(t)}(X^{k,\left\lceil j/a\right\rceil})}\left[\mathbb{I}[\boldsymbol{x}_{j}\theta^{k}_{j}<0]\right]\epsilon_{k},\qquad\qquad\quad\quad k=1\text{ or }3\leq k\leq M.\end{aligned}\right.$ (68) $$

and $R_{j}(\theta)=\sum_{k=1}^{M}R_{j}^{k}(\theta)$.
Then for any $\tilde{h}+1\leq j\leq\tilde{h}+\ell$, we have that

$$ $\displaystyle\frac{1}{|\mathcal{Y}|}\sum_{\theta\in\mathcal{Y}}R_{j}(\theta)\geq\frac{1}{8(M+1)}\min\left\{\min_{k\in[M],k\neq 2}\frac{T_{k}\epsilon_{k}}{\bar{d}},\frac{T_{2}\epsilon_{2}}{8\bar{d}}\right\}.$ $$

With Lemma [16](#Thmlemma16) in hand, noting that $\ell\geq\frac{\bar{d}-\tilde{h}}{4}\geq\frac{\bar{d}}{8}$, we obtain that

$$ $\displaystyle\frac{1}{|\mathcal{Y}|}\sum_{j=h+1}^{h+\ell}\sum_{\theta\in\mathcal{Y}}R_{j}(\theta)\geq\frac{1}{32(M+1)}\min\left\{\min_{k\in[M],k\neq 2}T_{k}\epsilon_{k},\frac{T_{2}\epsilon_{2}}{8}\right\}.$ $$

Noting that the expected regret under parameter $\theta$ is at least $\mathrm{Regret}_{\theta,D}(T)\geq\sum_{j=\tilde{h}+1}^{\tilde{h}+l}R_{j}(\theta)$, we learn that

$$ $\displaystyle\frac{1}{|\mathcal{Y}|}\sum_{\theta\in\mathcal{Y}}\mathrm{Regret}_{\theta,D}(T)$ $\displaystyle\geq\frac{1}{|\mathcal{Y}|}\sum_{j=\tilde{h}+1}^{\tilde{h}+\ell}\sum_{\theta\in\mathcal{Y}}R_{j}(\theta)\geq\Omega\left(\gamma/M\right)$ (69) $$

Then there exists some $\theta^{*}\in\mathcal{Y}$ such that $\mathrm{Regret}_{\theta^{*},D}(T)\geq\Omega(\gamma/M)$. The proof is completed by definition of $\gamma$.

∎

It remains to prove Lemma [16](#Thmlemma16).

###### Proof of Lemma 16 .

Recall the definition of $\mathcal{E}_{k}$ for $1\leq k\leq M$. We further define $\mathcal{H}_{k}$ as below.

- •
$\mathcal{H}_{1}=\bar{\Omega}$, where $\bar{\Omega}$ is the entire probability space;
- •
$\mathcal{H}_{2}=\{n_{j}\leq\max\{\frac{6T_{1}}{(h+1)(\bar{d}-h)M},6\ln(dM)\},\forall h+1\leq j\leq h+l\}$, where $n_{j}$ denotes the number of times the $j$-th arm is taken in the first batch;
- •
$\mathcal{H}_{k}=\{n^{k}_{i}\leq\max\{\frac{6MT_{k-1}}{b},6\ln(dM)\},\forall 1\leq i\leq b\}$ for $3\leq k\leq M$, where $n^{k}_{i}=\sum_{t=1}^{\mathcal{T}_{k-1}}\mathbb{I}[X_{t}=X^{k,i}]$, i.e., the number of times when the context is $X^{k,i}$.

Since the $\pi^{1}$ is independent of $\theta$, then $\{\mathcal{H}_{k}\}_{k=1}^{M}$ is also independent of $\theta$. Using Lemma [18](#Thmlemma18), it is easy to show that $\mathrm{Pr}_{\theta}[\mathcal{H}_{k}]\geq 1-\frac{1}{10M}$ for any $1\leq k\leq M$ and any $\theta\in\mathcal{Y}$.

Let $p_{j}^{k}(\theta)=\mathbb{E}_{\theta,\boldsymbol{x}\sim\pi_{k}(X^{k,\left\lceil j/a\right\rceil})}\left[\mathbb{I}[\boldsymbol{x}_{j}\theta^{k}_{j}<0]|\mathcal{E}_{k}\cap\mathcal{H}_{k}\right]$ for $k=1$ or $3\leq k\leq M$. For $k=2$, we define $p_{j}^{k}(\theta)=\mathbb{E}_{\theta,\boldsymbol{x}\sim\pi_{2}([\tilde{h}]\cap\{\tilde{h}+j\})}\left[\mathbb{I}[\boldsymbol{x}=j,\theta_{j}^{2}<0]+\mathbb{I}[\boldsymbol{x}\neq j,\theta_{j}^{2}>0]|\mathcal{E}_{2}\cap\mathcal{H}_{2}\right]$.

Recall that $\mathcal{F}_{t}$ denotes the event field over the first $t$ steps.
For fixed $\theta\in\mathcal{Y}$, we denote $\theta^{k}_{j}$ be the vector in $\mathcal{Y}$ by reflecting the $j$-th dimension of $\theta^{k}$. Using Pinsker’s inequality (Lemma [17](#Thmlemma17)), and noting that $\mathcal{E}_{k}\cap\mathcal{H}_{k}$ are measurable with respect to $\mathcal{F}_{\mathcal{T}_{k-1}}$.

$$ $\displaystyle p_{j}^{k}(\theta)+p_{j}^{k}(\theta^{k}_{j})\geq 1-\sqrt{\frac{1}{2}D_{\mathrm{KL}}\left(\mathrm{Pr}^{\mathcal{T}_{k-1}}_{\theta}[\cdot|\mathcal{E}_{k}\cap\mathcal{H}_{k}],\mathrm{Pr}^{\mathcal{T}_{k-1}}_{\theta^{k}_{j}}[\mathcal{E}_{k}\cap\mathcal{H}_{k}]\right)}$ $$

for $k=1$ or $3\leq k\leq M$, where $\mathrm{Pr}^{t}[\cdot]$ denotes probability distribution over the first $t$ steps. By definition of $\mathcal{E}_{k}$ and $\mathcal{H}_{k}$, we have that

$$ $\displaystyle D_{\mathrm{KL}}\left(\mathrm{Pr}^{\mathcal{T}_{k-1}}_{\theta}[\cdot|\mathcal{E}_{k}\cap\mathcal{H}_{k}],\mathrm{Pr}^{\mathcal{T}_{k-1}}_{\theta^{k}_{j}}[\mathcal{E}_{k}\cap\mathcal{H}_{k}]\right)\leq\max\left\{\frac{6MT_{k-1}}{b},6\ln(dM)\right\}\frac{4\epsilon_{k}^{2}}{a^{2}}\leq\frac{1}{8}.$ $$

As a result, we have that

$$ $\displaystyle p_{j}^{k}(\theta)+p_{j}^{k}(\theta^{k}_{j})\geq\frac{3}{4}.$ (70) $$

Using similar arguments, and noting that $n_{j}\leq\max\{\frac{6T_{1}}{(\tilde{h}+1)(\bar{d}-\tilde{h})M},6\ln(dM)\}$ conditioned on $\mathcal{H}_{2}$, we have that

$$ $\displaystyle p_{j}^{2}(\theta)+p_{j}^{2}(\theta_{j}^{k})\geq 1-\sqrt{\frac{1}{2}D_{\mathrm{KL}}(\mathrm{Pr}^{T_{1}}_{D_{2},\theta)}[\cdot|\mathcal{H}_{2}\cap\mathcal{E}_{2}],\mathrm{Pr}^{T_{1}}_{D_{2},\theta^{2}_{j}}[\cdot|\mathcal{H}_{2}\cap\mathcal{E}_{2}])}\geq\frac{3}{4}.$ (71) $$

Let $\zeta_{k}=\frac{1}{\bar{d}}T_{k}\epsilon_{k}$ for $k=1$ or $3\leq k\leq M$ and $\zeta_{2}=\frac{1}{8\bar{b}}T_{2}\epsilon_{2}$.
By the definition of $R_{j}(\theta)$, and noting that $\ell\geq\frac{\bar{d}}{8}$, we have that

$$ $\displaystyle R_{j}(\theta)\geq\sum_{k=1}^{M}\mathrm{Pr}_{\theta}[\mathcal{E}_{k}\cap\mathcal{H}_{k}]p_{j}^{k}(\theta)\zeta_{k}$ $\displaystyle R_{j}(\theta^{k}_{j})=\sum_{k=1}^{M}\mathrm{Pr}_{\theta^{k}_{j}}[\mathcal{E}_{k}\cap\mathcal{H}_{k}]p_{j}^{k}(\theta_{j}^{k})\zeta_{k}.$ $$

using Pinsker’s inequality (Lemma [17](#Thmlemma17)), for any $1\leq k\leq M$, it holds that

$$ $\displaystyle\left|\mathrm{Pr}_{\theta}[\mathcal{E}_{k}\cap\mathcal{H}_{k}]-\mathrm{Pr}_{\theta_{k}^{j}}[\mathcal{E}_{k}\cap\mathcal{H}_{k}]\right|\leq\sqrt{\frac{1}{2}D_{\mathrm{KL}}\left(\mathrm{Pr}^{\mathcal{T}_{k-1}}_{\theta}[\cdot|\mathcal{E}_{k}\cap\mathcal{H}_{k}],\mathrm{Pr}^{\mathcal{T}_{k-1}}_{\theta^{k}_{j}}[\mathcal{E}_{k}\cap\mathcal{H}_{k}]\right)}\leq\frac{1}{2M}.$ $$

Therefore, we have that

$$ $\displaystyle R_{j}(\theta)+\sum_{k=1}^{M}R_{j}(\theta_{j}^{k})\geq\sum_{k=1}^{M}\max\left\{\frac{3}{4}\mathrm{Pr}_{\theta}[\mathcal{E}_{k}\cap\mathcal{H}_{k}]-\frac{1}{2M},0\right\}\zeta_{k}\geq\frac{1}{8}\min_{k}\zeta_{k}.$ (72) $$

Taking sum over $\mathcal{Y}$, we have that

$$ $\displaystyle\frac{1}{|\mathcal{Y}|}\sum_{\theta\in\mathcal{Y}}\sum_{k=1}^{M}\mathrm{Pr}_{\theta}[\mathcal{E}_{k}\cap\mathcal{H}_{k}]p_{j}^{k}(\theta)T_{k}\epsilon_{k}\geq\frac{1}{8(M+1)}\min_{k}\zeta_{k}.$ $$

The proof is completed.

∎

###### Lemma 16 .

###### Proof of Lemma 16 .

## 8 Extension to the Context-Aware Case

### 8.1 The Batch Learning Algorithm

In the context-aware case, we can observe the context before determining the policy. For each $1\leq k\leq M$ we can learn $\pi^{k}$ using $\{X_{t}\}_{t=\mathcal{T}_{k-1}+1}^{\mathcal{T}_{k}}$. In particular, by observing the context of the first batch, we can learn a design policy which is better than $\pi^{\mathtt{G}}$. As a consequence, the final regret upper bound would be smaller than the context-blind case.

The algorithm is presented in Algorithm [3](#alg3). At the start of the $k$-th batch, we observe the context $\{X_{t}\}_{t=\mathcal{T}_{k-1}+1}^{\mathcal{T}_{k}}$ and then play elimination by previous information to get the eliminated context $\{X_{t}^{(k)}\}_{t=\mathcal{T}_{k-1}+1}^{\mathcal{T}_{k}}$ . After that, we run $\mathtt{ExplorationPolicy}$ with input as $\{X_{t}^{(k)}\}_{t=\mathcal{T}_{k-1}+1}^{\mathcal{T}_{k}}$ to search the near-optimal design policy. Since the $\{X_{t}\}_{t=\mathcal{T}_{k-1}+1}^{\mathcal{T}_{k}}$ is independent of all the histories before the $k$-th batch, there is no need to break the samples in the $k$-th batch to two parts to keep the independence.

Figure: Algorithm 3 Context-Aware Batch Learning

##### Regret Analysis.

Following similar arguments in Section [4.1](#S4.SS1), we have that:

###### Theorem 6 .

Let $h=\min\{d,K\}$. For any $T\geq d$ and $M\geq 1$, Algorithm [3](#alg3) may use at most $M$ batches and its regret is bounded by

$$ $\displaystyle R_{T}\leq O\left(\mathrm{poly}\ln(Td)T^{\frac{1}{2-2^{-(M-1)}}}\cdot(d\log_{2}(K))^{\frac{1-2^{-(M-1)}}{2-2^{-(M-1)}}}\right).$ (73) $$

###### Proof.

We follow the notations in Section [4.1](#S4.SS1).
Invoking Lemma [7](#Thmlemma7) with $m=n=T_{k-1}$ for $2\leq k\leq M$, we have that

$$ $\displaystyle\mathop{\mathbb{E}}\left[\min\left\{\sqrt{\max_{\boldsymbol{x}\in X_{t}^{(k-1)}}\boldsymbol{x}^{\top}\Lambda_{k-1}^{-1}\boldsymbol{x}},\sqrt{L}\right\}\right]\leq\sqrt{\frac{1}{T_{k-1}}}\cdot O\left(\sqrt{d\ln\left(Td\right)}\right)+\frac{\sqrt{L}}{T_{k-1}}\cdot O\left(d\ln\left(Td\right)\right)+3\delta.$ $$

As a result, the expected regret of the $k$-th batch is bounded by

$$ $\displaystyle\sqrt{\ln(TKd/\delta)}\cdot O\left(\sqrt{\frac{T_{k}^{2}}{T_{k-1}}}\cdot O\left(\sqrt{d\ln\left(Td\right)}\right)+\frac{\sqrt{L}T_{k}}{T_{k-1}}\cdot O\left(d\ln\left(Td\right)\right)+T_{k}\delta\right).$ $$

Besides, the regret in the first batch is simply bounded by $O(T_{1})$. Let

$$ $\gamma=T^{\frac{1}{2-2^{-(M-1)}}}\cdot(d\ln(KTd)\ln(Td))^{\frac{1-2^{-(M-1)}}{2-2^{-(M-1)}}}.$ $$

By setting that $\delta=\frac{1}{T^{3}}$, $T_{1}=\gamma$ and

$$ $\displaystyle T_{k}=\sqrt{T_{k-1}}\cdot\frac{\gamma}{\sqrt{d\ln(KTd)\ln(Td)}}$ (74) $$

for $2\leq k\leq M$, we finish the proof.

∎

###### Theorem 6 .

###### Proof.

### 8.2 The Lower Bound

We present a nearly matching lower bound as below.

###### Theorem 7 .

Fix any $K\geq 2$, $T\geq d$, and any batch number $M\geq 1$. For any learning algorithm with batch complexity $M$, there exists a linear contextual bandit problem instance with dimension $d$ and $K$ arms, such that the expected regret $R_{T}$ is at least

$$ $\displaystyle\Omega\left(\frac{1}{\mathrm{poly}\ln(Td)}T^{\frac{1}{2-2^{-(M-1)}}}\cdot(d\ln(K))^{\frac{1-2^{-(M-1)}}{2-2^{-(M-1)}}}\right).$ $$

###### Proof sketch..

This theorem could be proved using the same arguments as in proof of Theorem [2](#Thmtheorem2). In particular, we only use the Case II construction. Below we present the value $\{T_{k}\}_{k=1}^{M}$ and $\{\epsilon_{k}\}_{k=1}^{M}$, and the detailed proof is omitted.

Define $\gamma=T^{\frac{1}{2-2^{-(M-1)}}}\cdot\left(\frac{d\log_{2}(K)}{M\ln(dM)}\right)^{\frac{1-2^{-(M-1)}}{2-2^{-(M-1)}}}$. Let $T_{1}=\gamma$ and $T_{k}=\gamma\cdot\sqrt{\frac{T_{k-1}M\ln(dM)}{d\log_{2}(K)}}$ for $2\leq k\leq M$.
Let $\epsilon_{1}=\frac{1}{100}$ and $\epsilon_{k}=\sqrt{\frac{d\log_{2}(K)}{MT_{k-1}\ln(dM)}}$ for $2\leq k\leq M$. Following the analysis in Section [7](#S7), that the minimax regret is at least $\Omega(\gamma/M)$, and the conclusion follows.
∎

###### Theorem 7 .

###### Proof sketch..

## 9 Conclusion

In this paper, we study the batch linear contextual linear bandit problem with stochastic context. When the number of batches is limited by $M$, for any $T$ and $d$, we achieve matching upper and lower bounds for the regret (up to logarithmic factors) in both context-blind and context-aware settings. We adopt the reward-free LinUCB proposed in (Ruan et al., ) to achieve our learning goal. In the algorithm design and analysis, we highlight two key techniques: the scaled-and-clipped update rule and the matrix concentration inequality with dynamic upper bounds. We believe these techniques could help design and analyze batch algorithms for other online learning and decision-making problems with linear reward structures (e.g., the linear Markov Decision Processes).

## Acknowledgement

The authors would like to thank Joel A. Tropp for the helpful discussions on matrix concentration inequalities.

## Appendix A Technical Lemmas

###### Lemma 17 (Pinsker’s Inequality) .

Let $D_{\mathrm{KL}}(P||Q)$ denote the KL-divergence between $P$ and $Q$. Let $D_{1}(P,Q):=|P-Q|_{1}$ denote the $L_{1}$ distance between $P$ and $Q$.
For any two distribution $P,Q$, we have that

$$ $\displaystyle\int|dP-dQ|\leq\min\{\sqrt{\frac{1}{2}D_{\mathrm{KL}}(P\|Q)},\sqrt{\frac{1}{2}D_{\mathrm{KL}}(Q\|P)}\},$ (75) $$

where $D_{\mathrm{KL}}$ denotes the KL-divergence.

###### Lemma 18 .

Let $X_{1},X_{2},\ldots$ be a sequence of random variables taking value in $[0,l]$. Define $\mathcal{F}_{k}=\sigma(X_{1},X_{2},\ldots,X_{k-1})$ and $Y_{k}=\mathbb{E}[X_{k}|\mathcal{F}_{k}]$ for $k\geq 1$. For any $\delta>0$, we have that

$$ $\displaystyle\mathbb{P}\left[\exists n,\sum_{k=1}^{n}X_{k}\leq 3\sum_{k=1}^{n}Y_{k}+l\ln(1/\delta)\right]\leq\delta$ $\displaystyle\mathbb{P}\left[\exists n,\sum_{k=1}^{n}Y_{k}\geq 3\sum_{k=1}^{n}X_{k}+l\ln(1/\delta)\right]\leq\delta.$ $$

###### Proof.

Let $t\in[0,1/l]$ be fixed.
Consider to bound $Z_{k}:=\mathbb{E}[\exp(t\sum_{k^{\prime}=1}^{k}(X_{k^{\prime}}-3Y_{k^{\prime}}))]$. By definition, we have that

$$ $\displaystyle\mathbb{E}[Z_{k}|\mathcal{F}_{k}]$ $\displaystyle=\exp(t\sum_{k^{\prime}=1}^{k}(X_{k^{\prime}}-3Y_{k^{\prime}}))\mathbb{E}\left[t(X_{k}-3Y_{k})\right]$ $\displaystyle\leq\exp(t\sum_{k^{\prime}=1}^{k}(X_{k^{\prime}}-3Y_{k^{\prime}}))\exp(3Y_{k})\cdot\mathbb{E}[1+tX_{k}+2t^{2}X^{2}_{k}]$ $\displaystyle\leq\exp(t\sum_{k^{\prime}=1}^{k}(X_{k^{\prime}}-3Y_{k^{\prime}}))\exp(3Y_{k})\cdot\mathbb{E}[1+3tX_{k}]$ $\displaystyle=\exp(t\sum_{k^{\prime}=1}^{k}(X_{k^{\prime}}-3Y_{k^{\prime}}))\exp(3Y_{k})\cdot(1+3tY_{k})$ $\displaystyle\leq\exp(t\sum_{k^{\prime}=1}^{k}(X_{k^{\prime}}-3Y_{k^{\prime}}))$ $\displaystyle=Z_{k-1},$ $$

where the second line is by the fact that $e^{x}\leq 1+x+2x^{2}$ for $x\in[0,1]$.
Define $Z_{0}=1$
Then $\{Z_{k}\}_{k\geq 0}$ is a super-martingale with respect to $\{\mathcal{F}_{k}\}_{k\geq 1}$. Let $\tau$ be the smallest $n$ such that $\sum_{k=1}^{n}X_{k}-3\sum_{k=1}^{n}Y_{k}>l\ln(1/\delta)$.
It is easy to verify that $Z_{\min\{\tau,n\}}\leq\exp(tl\ln(1/\delta)+tl)<\infty$. Choose $t=1/l$.
By the optimal stopping time theorem, we have that

$$ $\displaystyle\mathbb{P}\left[\exists n\leq N,\sum_{k=1}^{n}X_{k}\geq 3\sum_{k=1}^{n}Y_{k}+l\ln(1/\delta)\right]$ $\displaystyle=\mathbb{P}\left[\tau\leq N\right]$ $\displaystyle\leq\mathbb{P}\left[Z_{\min\{\tau,N\}}\geq\exp(tl\ln(1/\delta))\right]$ $\displaystyle\leq\frac{\mathbb{E}[Z_{\min\{\tau,N\}}]}{\exp(tl\ln(1/\delta))}$ $\displaystyle\leq\delta.$ $$

Letting $N\to\infty$, we have that

$$ $\displaystyle\mathbb{P}\left[\exists n,\sum_{k=1}^{n}X_{k}\leq 3\sum_{k=1}^{n}Y_{k}+l\ln(1/\delta)\right]\leq\delta.$ $$

Considering $W_{k}=\mathbb{E}[\exp(t\sum_{k^{\prime}=1}^{k}(Y_{k}/3-X_{k}))]$, using similar arguments and choosing $t=1/(3l)$, we have that

$$ $\displaystyle\mathbb{P}\left[\exists n,\sum_{k=1}^{n}Y_{k}\geq 3\sum_{k=1}^{n}X_{k}+l\ln(1/\delta)\right]\leq\delta.$ $$

The proof is completed.
∎

###### Lemma 17 (Pinsker’s Inequality) .

###### Lemma 18 .

###### Proof.

## Appendix B Omitted Lemmas and Proofs in Section 4

### B.1 Statement and Proof of Lemma 19

The following lemma is a similar version of Lemma 31 in [Ruan et al., ] that analyzes the size of the confidence interval by the ridge regression. Note that since we only assume $\|\boldsymbol{\theta}\|_{\infty}\leq 1$ instead of the upper bound on the Euclidean norm, the calculation is slightly different.

###### Lemma 19 .

Given $\boldsymbol{\theta},\boldsymbol{x}_{1},\boldsymbol{x}_{2},\ldots,\boldsymbol{x}_{n}\in\mathbb{R}^{d}$
such that $\|\boldsymbol{\theta}\|_{\infty}\leq 1$ for all $i\in[n]$, let $r_{i}=\boldsymbol{x}_{i}^{\top}\boldsymbol{\theta}+\epsilon_{i}$ where $\{\epsilon_{i}\}_{i=1}^{n}$ are independent sub-Gaussian random variable with variance proxy $1$. Let $\Lambda=\lambda\mathbf{I}+\sum_{i=1}^{n}\boldsymbol{x}_{i}\boldsymbol{x}_{i}^{\top}$ and $\hat{\boldsymbol{\theta}}=\Lambda^{-1}\sum_{i=1}^{n}r_{i}\boldsymbol{x}_{i}$. For any $\boldsymbol{x}\in\mathbb{R}^{d}$ and any $\gamma>0$, we have that

$$ $\displaystyle\Pr\left[|\boldsymbol{x}^{\top}(\boldsymbol{\theta}-\hat{\boldsymbol{\theta}})|>(\gamma+\sqrt{d\lambda})\sqrt{\boldsymbol{x}\Lambda^{-1}\boldsymbol{x}}\right]\leq 2e^{-\frac{\gamma^{2}}{2}}.$ $$

###### Proof.

Direct computation gives that

$$ $\displaystyle|\boldsymbol{x}^{\top}(\boldsymbol{\theta}-\hat{\boldsymbol{\theta}})|$ $\displaystyle=\left|\boldsymbol{x}^{\top}\left(\Lambda^{-1}\sum_{i=1}^{n}\boldsymbol{x}_{i}(\boldsymbol{x}_{i}^{\top}\boldsymbol{\theta}+\epsilon_{i})-\boldsymbol{\theta}\right)\right|$ $\displaystyle=\left|\boldsymbol{x}^{\top}\left(\Lambda^{-1}\sum_{i=1}^{n}\boldsymbol{x}_{i}\epsilon_{i}+\Lambda^{-1}(\Lambda-\lambda\mathbf{I})\boldsymbol{\theta}-\boldsymbol{\theta}\right)\right|$ $\displaystyle=\left|\boldsymbol{x}^{\top}\Lambda^{-1}\left(\sum_{i=1}^{n}\boldsymbol{x}_{i}\epsilon_{i}-\lambda\boldsymbol{\theta}\right)\right|$ $\displaystyle\leq\lambda\left|\boldsymbol{x}^{\top}\Lambda^{-1}\boldsymbol{\theta}\right|+\left|\sum_{i=1}^{n}\boldsymbol{x}^{\top}\Lambda^{-1}\boldsymbol{x}_{i}\epsilon_{i}\right|.$ $$

For the first term, by Cauchy-Schwarz and noting that $\Lambda\succcurlyeq\lambda\mathbf{I}$, we have that

$$ $\displaystyle\lambda\left|\boldsymbol{x}^{\top}\Lambda^{-1}\boldsymbol{\theta}\right|\leq\lambda\sqrt{d}\cdot\sqrt{\boldsymbol{x}^{\top}\Lambda^{-2}\boldsymbol{x}}\leq\sqrt{\lambda d\boldsymbol{x}^{\top}\Lambda^{-1}\boldsymbol{x}}.$ (76) $$

For the second term, by sub-Gaussian concentration inequalities, we have that

$$ $\displaystyle\mathrm{Pr}\left[\left|\sum_{i=1}^{n}\boldsymbol{x}^{\top}\Lambda^{-1}\boldsymbol{x}_{i}\epsilon_{i}\right|>\gamma\sqrt{\boldsymbol{x}^{\top}\Lambda^{-1}\boldsymbol{x}}\right]\leq 2e^{\frac{-\gamma^{2}}{2}}.$ (77) $$

The conclusion follows by combining ([76](#A2.E76)) and ([77](#A2.E77)).
∎

###### Lemma 19 .

###### Proof.

### B.2 Statement and Proof of the Elliptical Potential Lemma

###### Lemma 20 .

Let $\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n}$ be a sequence of vectors in $\mathbb{R}^{d}$ such that $\|x_{i}\|_{2}\leq 1$. Let $\Lambda_{0}=A$ be a positively definite matrix and $\Lambda_{i}=\Lambda_{0}+\sum_{j=1}^{i}\boldsymbol{x}_{j}\boldsymbol{x}_{j}^{\top}$. If $\boldsymbol{x}_{i}^{\top}\Lambda_{i-1}^{-1}\boldsymbol{x}_{i}\leq 1$ for all $1\leq i\leq n$,
it then holds that

$$ $\displaystyle\sum_{i=1}^{n}\boldsymbol{x}_{i}^{\top}\Lambda_{i-1}^{-1}\boldsymbol{x}_{i}\leq 2\ln\left(\frac{\det(\Lambda_{n})}{\det(\Lambda_{0})}\right).$ $$

###### Proof.

Note that $\det(\Lambda_{i+1})=\det(\Lambda_{i})(1+\boldsymbol{x}_{i+1}^{\top}\Lambda_{i}^{-1}\boldsymbol{x}_{i+1})$. Since $\ln(1+x)\geq\frac{x}{2}$ when $0\leq x\leq 1$, we have that

$$ $\displaystyle\ln(\det(\Lambda_{i+1}))-\ln(\det(\Lambda_{i}))\geq\frac{1}{2}\boldsymbol{x}_{i+1}^{\top}\Lambda_{i}^{-1}\boldsymbol{x}_{i+1},$ $$

which implies that

$$ $\sum_{i=1}^{n}\boldsymbol{x}_{i}^{\top}\Lambda_{i-1}^{-1}\boldsymbol{x}_{i}\leq 2\ln\left(\frac{\det(\Lambda_{n})}{\det(\Lambda_{0})}\right).$ $$

∎

###### Lemma 20 .

###### Proof.

## Appendix C Omitted Proofs in Section 6

### C.1 Proof of Fact 1

###### Proof.

We first show that $A\preccurlyeq B$ implies ([53](#S6.E53)). By $A\preccurlyeq B$, we have that $B-A\succcurlyeq 0$. Therefore, $A^{-1/2}BA^{-1/2}-\mathbf{I}=A^{-1/2}(B-A)A^{-1/2}$ is PSD, which means that $A^{-1/2}BA^{-1/2}\succcurlyeq\mathbf{I}$. We then have $A^{1/2}B^{-1}A^{1/2}\preccurlyeq\mathbf{I}$. This is because if we let $M=A^{-1/2}BA^{-1/2}\succcurlyeq\mathbf{I}$ for convenience, for every vector $x$, it holds that

$$ $\displaystyle x^{\top}A^{1/2}B^{-1}A^{1/2}x=x^{\top}M^{-1}x=(M^{-1/2}x)^{\top}(M^{-1/2}x)\leq(M^{-1/2}x)^{\top}M(M^{-1/2}x)=x^{\top}x.$ $$

This proves ([53](#S6.E53)), assuming $A\succcurlyeq B$.

We then show that ([53](#S6.E53)) implies ([52](#S6.E52)). Note that $A^{1/2}B^{-1}A^{1/2}-\mathbf{I}\preccurlyeq 0$ implies that
$B^{-1}-A^{-1}=A^{-1/2}(A^{1/2}B^{-1}A^{1/2}-\mathbf{I})A^{-1/2}\preccurlyeq 0$, which leads to $B^{-1}\preccurlyeq A^{-1}$.

By symmetry, we can also prove that ([52](#S6.E52)) implies $A\preccurlyeq B$, and therefore establishing the equivalence condition for both ([52](#S6.E52)) and ([53](#S6.E53)).

Finally, $A-B\preccurlyeq 0$ is equivalent to that $\mathbf{I}-B^{-1/2}AB^{-1/2}=B^{-1/2}(B-A)B^{-1/2}$ is PSD, which is also equivalent to that $B^{-1/2}AB^{-1/2}\preccurlyeq\mathbf{I}$, proving the equivalence for ([54](#S6.E54)).
∎

###### Proof.

### C.2 Proof of Lemma 11

###### Proof.

Following the arguments in the proof of Lemma [10](#Thmlemma10), it suffices to prove that

$$ $\displaystyle\mathbb{E}\left[\exp\left(Z_{k}^{-1/2}((1-\epsilon)Y_{k}-X_{K})Z_{k}^{-1/2}\right)\Big{|}\mathcal{F}_{k}^{+}\right]\preccurlyeq\mathbf{I}$ $$

holds for each $1\leq k\leq n$. Recall the definition of $U_{k}$ and $V_{k}$ in Lemma [12](#Thmlemma12). In the analysis below, we will conditioned on $\mathcal{F}_{k}^{+}$. By the same arguments in the proof of Lemma [12](#Thmlemma12), and noting that $-\mathbf{I}\preccurlyeq(1-\epsilon)V_{k}-U_{k}\preccurlyeq\mathbf{I}$, we have that

$$ $\displaystyle\quad\mathbb{E}\left[\exp\left(Z_{k}^{-1/2}((1-\epsilon)Y_{k}-X_{k})Z_{k}^{-1/2}\right)\right]$ $\displaystyle=\mathbb{E}\left[\exp\left((1-\epsilon)V_{k}-U_{k}\right)\right]$ $\displaystyle=\mathbb{E}\left[I+((1-\epsilon)V_{k}-U_{k})+\frac{1}{2}((1-\epsilon)V_{k}-U_{k})^{2}+\sum_{i\geq 3}\frac{1}{i!}((1-\epsilon)V_{k}-U_{k})^{i}\right]$ $\displaystyle\leq\mathbb{E}\left[I+((1-\epsilon)V_{k}-U_{k})+\frac{1}{2}((1-\epsilon)V_{k}-U_{k})^{2}+\sum_{i\geq 3}\frac{1}{i!}((1-\epsilon)V_{k}-U_{k})^{2}\right]$ $\displaystyle\preccurlyeq\mathbb{E}\left[\mathbf{I}+((1-\epsilon)V_{k}-U_{k})+2((1-\epsilon)V_{k}-U_{k})^{2}\right]$ $\displaystyle\preccurlyeq\mathbb{E}\left[\mathbf{I}+((1-\epsilon)V_{k}-U_{k})+4U_{k}^{2}+4(1-\epsilon)^{2}V_{k}^{2}\right]$ $\displaystyle\preccurlyeq\mathbb{E}\left[\mathbf{I}+((1-\epsilon)V_{k}-U_{k})+\frac{4\epsilon}{4(\epsilon^{2}+2\epsilon+2)}U_{k}+\frac{4(1-\epsilon)^{2}\epsilon}{4(\epsilon^{2}+2\epsilon+2)}V_{k}\right]$ $\displaystyle\preccurlyeq\mathbf{I}.$ $$

The proof is completed.
∎

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. The algorithms are based on restarting Lin-UCB at every epoch. How does this relate to designing forgetting-based episodic RL algorithms?
soundness: 3
strengths: The contributions are: 
1. **Regret Bounds and Tradeoffs:** They analyze the regret, or performance loss, for different batch numbers and prove that their algorithms achieve nearly optimal regret bounds (up to logarithmic factors) across varying batch sizes. For instance, they demonstrate that as few as \(O(\log \log T)\) batches suffice to achieve nearly the minimax-optimal regret without constraints.

2. **Simplification of Algorithms:** Compared to prior work, such as Ruan et al. (2021), the authors propose a simpler algorithm that is more practical to implement and works for all time horizons \(T\) as long as \(T \geq d\) (where \(d\) is the context dimension). This represents an improvement over previous methods, which required large polynomial relations between \(T\) and \(d\).

3. **Matrix Concentration Inequality:** A significant technical contribution is a new **matrix concentration inequality** that depends dynamically on upper bounds, which is useful for the algorithm’s exploration policy. This inequality could be valuable for other research areas in machine learning due to its novel structure.

4. **Context-Aware Performance Gains:** In the context-aware setting, they show that observing the context allows the learning algorithm to achieve better regret bounds by taking advantage of additional information in each batch, demonstrating that optimal regret can be further improved compared to the context-blind setting.
summary: The paper addresses the problem of batch linear contextual bandits, a type of online learning model where decisions are made sequentially, balancing exploration and exploitation. The authors design algorithms for both context-blind and context-aware settings of the batch linear contextual bandit problem. In the context-blind setting, the learner cannot use current batch information to make decisions, while in the context-aware setting, the learner can observe the context in the current batch, allowing potentially more adaptive decisions.
weaknesses: 1. I believe $m$ and $n$ represent the same quantities (albeit separated by batch index). So I don’t see how this is an improvement over Zanette 2021. See lines~276-281.

---

confidence: 5
contribution: 4
initial_rating: 8
presentation: 3
questions: Could the authors include the computational complexity of the proposed algorithms as a function of K, d, T, M?
Could the authors add motivation for stochastic contexts as this is the main setting in the paper? e.g., what applications would satisfy the stochastic i.i.d. context assumption?
soundness: 4
strengths: The paper considers batch learning in stochastic contextual linear bandits which I believe is an important problem. It proves upper and lower bounds on the regret given number of batches M.
Exp-Policy (algorithm 2) is introduced to solve the distributional optimal design problem needed to design the policy in each batch. The algorithm is novel and simple unlike algorithms proposed in Ruan et al.
To the best of my knowledge multiple of the analysis techniques proposed are novel including the matrix concentration inequality in Lemma 20. 
The regret upper and lower bounds are nearly matching.

Overall, the paper introduces important algorithms and analysis techniques for contextual linear bandits, as well as being the first to prove the optimal regret bound dependency on the number of batches.
summary: The paper studies the number of batches vs regret tradeoff for contextual linear bandits. The authors propose an algorithm that achieves nearly optimal regret for a given number of batches M.
weaknesses: The computational complexity of the algorithms scale linearly with the number of actions which can be very large. However, this is justifiable since this is a challenging problem even without the batch learning constraints.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: See weaknesses.
soundness: 3
strengths: The theoretical strengths of the paper include providing a tight bound on the expected maximum width, $\mathcal{W}(m,n)$. This enhancement builds upon the results of Zanette et al. (2021) and mitigates the limitations identified in Ruan et al. (2021). Additionally, the matrix concentration inequality presented may be of independent interest.
summary: This research explores batched linear bandits, in which the learner decides the number of arms to pull in each batch, with rewards for the selected arms revealed only at the end of the batch.

The proposed algorithm functions within a predefined maximum number of batches denoted as $M$. It aims to minimize regret. Theorem 2 illustrates the balance between regret and $M$, indicating that the trade-off approaches a near-optimal order, as shown by Theorem 4. The findings suggest that $M = O(\log \log T)$ batches suffice to achieve asymptotically minimax optimal regret.
weaknesses: 1: Theorem 4 is compared with Gao et al. (2019), yet the more pertinent lower bound by Han et al. (2020) might provide a more relevant comparison. It is unclear why this comparison was omitted.

2: The paper overlooks several significant works on batched multi-armed bandits and linear bandits for asymptotic $T$. 

3: The paper often neglects to condition on $F_k$ throughout many parts of the proof. 

Additionally, a minor notational correction is recommended: "$\epsilon + t$" described as an independent sub-Gaussian noise with zero mean should be correctly noted as "$\epsilon_t$".

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 2
questions: - Could the authors consider including additional experiments in this section? Additionally, what would be the key challenges in implementing this algorithm?
- Could the authors provide more detail on the hidden constants in the upper and lower bounds? Specifically, what are their magnitudes, and what parameters do they depend on?
soundness: 3
strengths: The paper presents near-optimal results for this type of bandit problem, with matching upper and lower bounds that may represent a definitive solution in this area. Additionally, the authors introduce a novel concentration inequality tailored to this problem, which has the potential to be valuable for addressing other bandit problems as well.
summary: This paper studies the batch linear contextual bandits with stochastic contexts. They design some batch learning algorithms and prove that they achieve the optimal regret bounds up to some logarithmic factors for any batch number, number of actions, time horizon, and dimension. They also develop some new techniques which may be of independent interest.
weaknesses: It would be better if some numerical experiments were included.

Meta-review: A great paper that solves the remaining open problem left by Han 2020! Accept.

Decision: Accept (Poster)