Computer Science Mathematics
Computer Science-2021.gz:143467
Computer Science
0d59d7a86c822a671e4ef1eabae0846e5f6edfb7
Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design

Motivated by practical needs such as large-scale learning, we study the impact of adaptivity constraints to linear contextual bandits, a central problem in online active learning. We consider two popular limited adaptivity models in literature: batch learning and rare policy switches. We show that, when the context vectors are adversarially chosen in $d$-dimensional linear contextual bandits, the learner needs $O(d \log d \log T)$ policy switches to achieve the minimax-optimal regret, and this is optimal up to $\mathrm{poly}(\log d, \log \log T)$ factors; for stochastic context vectors, even in the more restricted batch learning model, only $O(\log \log T)$ batches are needed to achieve the optimal regret. Together with the known results in literature, our results present a complete picture about the adaptivity constraints in linear contextual bandits. Along the way, we propose the distributional optimal design, a natural extension of the optimal experiment design, and provide a both statistically and computationally efficient learning algorithm for the problem, which may be of independent interest.


Introduction
Online active learning is a fundamental research direction in machine learning where the learner conducts sequential interactions, once per time step, with the environment in order to learn the optimal policies and maximize the total reward. To achieve optimal learning performance, the learner must seek a balance between exploration and exploitation, which is usually done by adaptively selecting actions based on all historical observations. However, full adaptivity at a per-time-step scale significantly sacrifices parallelism and hinders the large-scale deployment of learning algorithms. To facilitate scalable learning, it is worthwhile to study the following question: What is the minimum amount of adaptivity needed to achieve optimal performance in online active learning?
In this paper, we address the above question through studying the impact of two popular types of adaptivity constraints to the linear contextual bandits, a central problem in online learning literature. We prove tight adaptivity-regret trade-offs for two natural settings of the problem. Along the way, we make a new connection to optimal experiment design: we propose the natural distributional optimal design problem, prove the existence of parametric forms for the optimal design, and present sample-efficient algorithms to learn the parameters. Our proposed framework contributes a novel learning component to the classical field of experiment design in statistics, and may be of independent interest.
Linear Contextual Bandits. The linear contextual bandits (or linear bandits for short), also known as "associative reinforcement learning" [Abe and Long, 1999;Auer, 2002], are a generalization of the ordinary multi-armed bandits. While also encapsulating the fundamental dilemma of "exploration vs. exploitation" in online active learning, linear contextual bandits highlight the guidance of contextual information for decisions, enabling personalized treatments and recommendations in real-world applications such as clinical trial, recommendation systems, and advertisement selection.
In a bandit game, there are T time steps in total. At each time step t ∈ [T ], the learner has to make a decision among K candidate actions (a.k.a. arms in bandit literature). While in ordinary multi-armed bandits, the mean rewards of the actions have to be completely independent from each other, linear bandits allow a linear model for the mean rewards. More specifically, at time step t, each action i ∈ [K] is associated with a d-dimensional context vector x ti (a.k.a., the feature vector), and the context vectors are presented to the learner. The expected reward for the i-th action is θ ⊤ x ti , where θ ∈ R d is hidden from the learner. The goal is to gradually learn θ and maximize the cumulative expected reward, or equivalently, minimize the expected regret (i.e., the difference between the received rewards and the rewards of the best actions in hindsight, as later defined in (1)). For example, in clinical trial, the candidate actions correspond to the K involved treatments. At time step t, an individual patient arrives with the context vectors {x ti } k i=1 characterizing his/her response to the candidate treatments, and the recovery probability given treatment i is modeled by the linear function θ ⊤ x ti , which corresponds to the expected reward in linear bandits.
There are two natural settings of the linear bandits: adversarial and stochastic contexts. The first setting is harder for the learner, as the context vectors are chosen by an adversary and the learner has to minimize the regret in the worst case. In the second setting, in contrast, the sets of context vectors are independently drawn from an unknown distribution D (while correlation may still exist among the contexts during the same time step), and the learner aims at minimizing the expected regret over D. Note that in the clinical trial example, the individual patients can often be viewed as independent samples from the population which is characterized by D.
Limited Adaptivity Models: Batch Learning and Rare Policy Switches. We consider two popular models of adaptivity constraints. The first model is batch learning, where the time steps are grouped into pre-defined batches. Within a batch, the same (possibly randomized) policy is used to select actions for all data and the rewards are observed only at the end of the batch. The amount of adaptivity is measured by the number of batches, which is expected to be as small as possible. A notable example is designing clinical trials, where each phase (batch) of the trial involves simultaneously applying medical treatments to a batch of patients. The outcomes are observed at the end of the phase, and may be used for designing experiments in future phases. Finding the correct number and sizes of the batches may achieve optimal efficiency for the trial by creating sufficient intra-batch parallelism while still providing sufficient adaptivity at the inter-batch scale.
The other model is learning with rare policy switches, where the amount of adaptivity is measured by the number of times allowed for the learner to change the action-selection policy. For the same amount of adaptivity measure, this model can be viewed as a relaxation of the batch learning model, because the learner in the batch learning model can only change the policy at the pre-defined time steps.
Both of the above models are closely connected to parallel learning, as we will discuss at the end of Section 1.1. We also note that another natural limited adaptivity model is "batch learning with adaptive grid" [Gao et al., 2019]. This model allows the learner to adaptively decide the size of a batch at the beginning of the batch, which is a more relaxed constraint than batch learning with pre-defined batches (a.k.a., the static grid model) but more restricted than the rare policy switch model, given the same amount of adaptivity measure. 1 Simple arguments will show that the bounds for the adaptive grid model are the same as the static grid model in both linear bandit settings. Therefore, for succinct exposition, we omit further discussions about the adaptive grid model. 2 Optimal Experiment Design. Optimal experiment design seeks to minimize the estimation variances of parameters via intelligently choosing queries to the given set of data points. Among the multiple optimization criteria, the one most related to linear bandits is the G-optimality criterion which seeks to minimize the maximum estimation variance among the given data points. More precisely, given a set of data points X ⊆ R d that spans the full dimension, the goal is to find a distribution K supported on X, such that max x∈X x ⊤ ( Ey∼K yy ⊤ ) −1 x is minimized. Here, I(K) = Ey∼K yy ⊤ is the information matrix of the design K, and x ⊤ I(K) −1 x is the variance of the estimate for data point x. The General Equivalence Theorem of Kiefer and Wolfowitz [1960] implies that there always exists a design K such that max x∈X x ⊤ I(K) −1 x ≤ d and such designs have been used for linear bandits with fixed candidate action set (see Chapter 22 of [Lattimore and Szepesvári, 2020], and [Esfandiari et al., 2019]). However, to the best of our knowledge, traditional optimal design does not address the problem when the candidate action set X is stochastic. In this work, motivated by the algorithmic needs from batch linear bandits, we address this problem and develop a framework named distributional optimal design that runs at the core of our algorithm. We will introduce this framework in the next subsection.
1 Indeed, in the adaptive grid model, the time for a policy switch has to be decided when the previous policy switch happens, while in the rare policy switch model, the learner can freely switch the policy, as long as the total number of switches is limited.
2 A simple argument will prove the Ω( √ T ) batch lower bound for achieving the asymptotically minimax-optimal regret for the adaptive grid model with adversarial contexts, and the rest bounds can be derived by direct corollaries of this work and the existing results in [Gao et al., 2019;Han et al., 2020].

Our Contributions
Adaptivity constraints in online active learning have attracted much attention recently. It has been shown that multi-armed bandits only need O(log log T ) batches to achieve asymptotically minimaxoptimal regret [Perchet et al., 2016;Gao et al., 2019]. For linear contextual bandits with adversarial contexts, when ln K ≥ Ω(d), Abbasi-Yadkori et al. [2011] showed an optimal-regret algorithm with O(d log T ) policy switches. In contrast, for the batch model, Han et al. [2020] recently showed that as many as Ω( √ T ) batches are needed to achieve the optimal regret bound, implying that batch learning is significantly more restrictive than policy switch constraints for adversarial contexts.
In light of these partial results, quite a few questions are intriguing and remain to be explored -What makes the adaptivity requirements of linear contextual bandits fundamentally different from multi-armed bandits? What is the limitation for algorithms with rare policy switches, or in other words, can we extend the algorithm by Abbasi-Yadkori et al. [2011] to the full parameter range of K, and further improve the number of policy switches to O(log log T )? Do linear bandits with stochastic contexts require substantially less adaptivity than the adversarial setting? We address these questions and summarize our answers as follows.
(C1) (Contribution #1, informal statements of Theorem 8 and Theorem 9) For linear bandits with adversarial contexts, we show that d log T (up to poly(log d, log log T ) factors) is the tight amount of policy switches needed to achieve the minimax-optimal regret. To this end, we first extend the algorithm by Abbasi-Yadkori et al. [2011] to the case where ln K ≤ o(d).
Our algorithm achieves the asymptotically minimax-optimal regret with O(d log d log T ) policy switches. We then prove that our algorithm and the one by Abbasi-Yadkori et al. [2011] achieve the near-optimal policy switch vs. regret trade-off. In particular, Ω(d log T / log(d log T )) policy switches are needed to achieve any √ T -type regret.
(C2) (Contribution #2, an informal statement of Theorem 7) For linear bandits with stochastic contexts, even in the more restricted batch learning model, it is possible to achieve the asymptotically minimax-optimal regret using only O(log log T ) batches. Our algorithm can be easily adapted to use M batches and achieve √ d log KT 1 2(1−2 −M ) × poly log T regret, for any M .  [Han et al., 2020] LB: Ω( d log T log(d log T ) ) (by (C1)) Stochastic Contexts UB: O(log log T ) (by (C2)) UB: O(log log T ) (implied by (C2)) LB: Ω(log log T ) [Gao et al., 2019] 3 LB: Ω(log log T ) [Simchi-Levi and Xu, 2019] 4 Together with the known results in literature, we are able to present an almost complete picture about the adaptivity constraints for linear bandits in Table 1. Most interestingly, compared to ordinary multi-armed bandits, linear bandits exhibit a richer set of adaptivity requirements, and strong separations among different models and settings. We also find that adversarially chosen context vectors are the main source of difficulty for reducing adaptivity requirements.
Comparison of (C2) and [Han et al., 2020]. Compared to (C1), our result in (C2) requires substantially more technical effort and is also the main motivation for us to develop the framework of distributional optimal design (which will be elaborated soon). We note that Han et al. [2020] also studied batch learning for linear bandits with stochastic contexts and showed an algorithm with O(log log T ) batches. However, their results are for a special case of the problem with the following assumptions: the context vectors are drawn from a Gaussian distribution, the ratio between the maximum and minimum eigenvalues of the Gaussian co-variance matrix should be O(1), and the number of candidate actions K cannot be greater than a polynomial of d. The design and analysis of their algorithm crucially rely on these three assumptions and it seems not obvious that their result can be directly extended to the general context set distribution. Indeed, their algorithm can safely choose the action to maximize the estimated mean reward, thanks to the isotropic Gaussian assumption ensuring sufficient exploration towards other directions. In contrast, without these assumptions, much effort in our algorithm is spent on the careful design of the exploration policy using many candidate actions, which motivates the problem of distributional optimal design. Distributional Optimal Design. As mentioned above, to facilitate the algorithm for stochastic contexts, we have to extend the traditional experiment design results to the regime where the set X of contexts/data points is stochastic. Suppose that X follows the distribution D, the goal of our proposed distributional optimal design problem is to find a sample policy π that maps any set X to a probability distribution supported on X, so as to minimize the distributional G-variation, defined as EX∼D max x∼X x ⊤ I D (π) −1 x, where I D (π) = EX∼D E y∼π(X) yy ⊤ is the information matrix of sample policy π over D. 5 Note that the traditional G-optimal design is the special case of our problem when D is deterministic.
The first natural question about our proposed problem is on the existence of a good sample policy. Regarding this, we prove the following result.
(C3) (Contribution #3, an informal statement of Theorem 5) For any D, there exists a sample policy π such that the distributional G-variance is bounded by O(d log d). 6 Moreover, we can construct such a policy from the class of so-called mixed-softmax policies, which admits a succinct description using O(d 3 log d) real-valued parameters.
Since D is not known beforehand in linear bandits, we have to learn a good sample policy π via finite samples from D. Since even the input of π lie in a continuous space with dK dimensions, proving the existence of the succinct parametric form of π in (C3) is a good news to learning. However, we find that directly constructing a policy based on the uniform distribution over empirical samples does not generalize to the true distribution D. We will come up with a more careful learning procedure to achieve the following goal.
(C4) (Contribution #4, an informal statement of Theorem 6) For any D, we design an algorithm to learn a good mixed-softmax policy π using only poly(d) independent samples from D. 7 We remark that the introduction of the distribution D brings a unique learning challenge to optimal experiment design. It is hopeful that our results and the future study on other criteria in distributional optimal design may lead to broader applications in machine learning and statistics.
Implications for Collaborative and Concurrent Learning. The idea of letting multiple learning agents learn in parallel so as to save overall running time has been studied a lot recently in online active learning, which is also the main motivation of this study (as mentioned in the very beginning of the paper). Below we discuss the implications of our algorithmic results for a few parallel learning models. The first implication is for the collaborative learning with limited interaction model, which was recently studied for pure exploration (i.e., top arm(s) identification) in multi-armed bandits [Hillel et al., 2013;Karpov et al., 2020]. In this model, there are K learning agents, and the learning process is partitioned into rounds of pre-defined time intervals. During each round (which is also referred to as the communication round), each of the K agents learns individually like in the centralized model -image that there is a global buffer of the context vectors, and the agents repeatedly draw a set of context vectors from the buffer and make corresponding decisions. Each play of an arm takes one time step, and the agents may choose to skip a few time steps without playing. The agents can only communicate at the end of each round. The collective regret is defined to be the sum of the regret incurred by each agent. Suppose there are T sets of context vectors in the global buffer, the goal is to finish the game in O(⌈T /K⌉) time (i.e., achieving the full speedup), while minimizing the collective regret and the number of communication rounds R.
Observe that a batch learning algorithm with M batches can be easily transformed to a collaborative algorithm with R = M communication rounds, where in each round i, each agent uses the policy for the i-th batch to play for ⌊T i /K⌋ or ⌈T i /K⌉ times, where T i is the size of the i-th batch. The total running time for collaborative learning is at most T /K + M , achieving the full speedup when M ·K ≤ O(T ). Therefore, when K ≤ O(T / log log T ), our algorithmic result (C2) implies a collaborative algorithm for stochastic-context linear bandits with full speedup and minimax-optimal collective regret, using only O(log log T ) communication rounds.
The second implication is for the concurrent learning model which was recently studied in [Guo and Brunskill, 2015;Bai et al., 2019;. In this model, there is no limit on the number of communication rounds and the K learning agents may communicate at the end of every time step. By a simple reduction described in [Bai et al., 2019], any algorithm with at most M policy switches can be transformed to a K-agent concurrent learning algorithm with full speedup, and the collective regret is at most M · K plus the original regret bound. Therefore, our algorithmic result in (C1) implies a concurrent learning algorithm for adversarial-context linear bandits with full speedup and minimax-optimal collective regret, as long as K ≤ O( (T log K)/d).

Additional Related Works
The linear contextual bandit problem is a central question in online active learning, and its regret minimization task has been studied during the past decades [Auer, 2002;Abe et al., 2003;Dani et al., 2008;Rusmevichientong and Tsitsiklis, 2010;Chu et al., 2011;Abbasi-Yadkori et al., 2011;Li et al., 2019]. The minimax-optimal regret is proved to be dT min{log K, d} up to poly log T factors, which is also the target regret for our algorithms with limited adaptivity. When the candidate action set is fixed, the task of identifying the best action has also been studied [Soare et al., 2014;Tao et al., 2018;Xu et al., 2018], and many of these works borrow the idea of G-optimal design. Batch regret minimization for multi-armed bandits was introduced by Perchet et al. [2016] with 2 arms, and the K-arm general setting was recently studied by Gao et al. [2019]. Simchi-Levi and Xu [2019] studied the K-arm setting with the rare policy switch constraint and achieved comparable results. For batch linear bandits, Esfandiari et al. [2019] and Han et al. [2020] recently studied the problem with aforementioned additional assumptions. We note that another usage of batch learning (mainly in reinforcement learning) refers to learning from a fixed set of a priori-known samples with no adaptivity allowed, which is very different from the definition in our work.
For the rare policy switch model, Abbasi-Yadkori et al. [2011] showed a rarely switching algorithm for linear bandits. Rare policy switch constraints have also been studied for a broader class of online active learning problems, such as multinomial logit bandits [Dong et al., 2020] and Q-learning [Bai et al., 2019].
Under the broader definition of adaptivity constraints including batch learning and learning with low switching cost (which might not exactly align with the models defined in this work), many other online learning problems are studied, such as adversarial multi-armed bandits [Cesa-Bianchi et al., 2013;Dekel et al., 2014], the best (multiple-)arm identification problem [Jun et al., 2016;Agarwal et al., 2017], and convex optimization [Duchi et al., 2018].
The optimal design of experiments is a fundamental problem in statistics, with various optimality criteria proposed and many statistical models studied (see, e.g., [Pukelsheim, 2006;Atkinson et al., 2007]). When the sample budget is finite, finding the exact solutions to certain optimality criteria is NP-Hard [Welch, 1982;Ç ivril and Magdon-Ismail, 2009;Summa et al., 2014], thus a sequence of recent works have studied approximation algorithms for the problem [Wang et al., 2017;Singh and Xie, 2018;Madan et al., 2019;Nikolov et al., 2019;Allen-Zhu et al., 2020]. However, to the best of our knowledge, all previous works have considered the fixed set of all possible experiments. In contrast, we propose and study the distributional optimal design problem where the set of candidate experiments might be stochastic.

Batch Algorithms for Stochastic Contexts
As the main technical contribution, we first describe the techniques developed in Section 4, Section 5 and Section 6 for proving our algorithmic result (C2). Along the way, the proof techniques for (C3) and (C4) are also explained. In Section 7, we combine all these technical components and prove the main theorem.
The Batch Elimination Framework. All our algorithms are elimination-based: at each time step, the confidence intervals are estimated for each candidate action, and the actions whose confidence intervals completely fall below those of other actions are eliminated. All survived actions are likely to be the optimal one, and the learner has to design an intelligent sample policy π to select the action from the survived set. In such a way, the incurred regret can be bounded by the order of the length of the longest confidence interval in the survived set.
We note that this elimination-based approach is not new: it is adopted by the batch algorithms for multi-armed bandit (e.g., [Gao et al., 2019]) as well as the recent batch algorithm for linear bandits with fixed action set [Esfandiari et al., 2019]. However, thanks to the simple structures of the two problems, during each batch, both of their algorithms are able to construct confidence intervals for survived actions with a uniform length, so that the regret can be relatively more easily bounded. Indeed, although the algorithm by Han et al. [2020] does not explicitly eliminate actions, their analysis relies on the uniform estimation confidence for the actions (which requires the isotropic Gaussian assumption for context vectors). In contrast, we have to deal with confidence intervals with wildly different lengths because of the inherent non-uniformity of the probability mass assigned to each context direction in the general distribution D.
To deal with such non-uniformity, in Section 4, we provide an analysis framework to relate the regret bound to the distributional G-variation of π over D, as introduced in Section 1.1. In particular, we show that if we let π(X) = π G (X), which returns the G-optimal design of the input context set X (regardless of D), its distributional G-variation can be bounded by d 2 (for all D), leading to O(d √ T log K) × poly log T regret with O(log log T ) batches. This regret is √ d times greater than the minimax-optimal target. To achieve optimality, we need to improve the distributional G-variation to O(d) (up to logarithmic factors), which requires to optimize π specifically according to D.
Existence of Distributional Optimal Design and its Parametric Form. In Section 5, we show that, given D, there exists a sample policy π whose distributional G-variation is O(d log d).
Our proof is constructive and the algorithm involves an innovative application of the rarely switching linear bandit algorithm [Abbasi-Yadkori et al., 2011]. We consider a long enough sequence of independent samples from D: X 1 , X 2 , . . . , X N , and sequentially feed the context vector sets to the rarely switching algorithm. Instead of minimizing the regret (as the reward is undefined), the rarely switching algorithm selects the context vector x that maximizes the variance according to the delayed information matrix, and update the total information matrix by adding xx ⊤ to it.
Borrowing the regret analysis techniques in linear bandits literature, and together with an adapted form of the celebrated Elliptical Potential Lemma, we are able to prove that, with the proper configuration of the initial information matrix, the average maximum confidence interval length throughout the N time steps is O(d log d). Moreover, the rarely switching trick makes sure that the delayed information matrix switches for at most O(d log d) times. This allows us to extract O(d log d) (deterministic) sample policies {π j } from the execution trajectory of the algorithm, each of which chooses the variance maximizer according to a delayed information matrix in the trajectory. We also associate each π j with a probability mass p j , which is proportional to the number of time steps when the corresponding delayed information matrix is used in the trajectory. We can then construct a so-called mixed-argmax policy π as follows: with probability 1/2, π acts the same as π G ; otherwise, π acts the same as π j with probability p j .
We are then able to prove that the distributional G-variance of π over D is O(d log d). This is done mainly by showing that I D (π) is comparable to the final information matrix in the trajectory, so that the distributional G-variance of π can be bounded by the empirical average of the maximum confidence interval lengths. To lower bound I D (π) using the total information matrix in the trajectory, while the portion corresponding to the larger switching window (i.e., greater p j ) in the trajectory can be directly compared, the smaller switching window will be handled by the π G component in π. We note that the π G component is also crucial to configuring the "proper" initial information matrix in the rarely switching algorithm.
We finally observe that π can be characterized by O(d 3 log d) parameters, because each π j is parameterized by a d × d information matrix. Since the arg max operator could be very sensitive to noise when the top input elements are close, to facilitate learning, we will also work on the mixed-softmax policy where each π j uses the softmax operator instead.
CoreLearning for Distributional Optimal Design. It is tempting to build the natural learning algorithm that computes the distributional optimal design from the empirical samples, hope that the Lipschitz-continuity of the softmax policies provides a small covering of the policy space, which leads to uniform concentration results, and finally prove that the learned policy generalizes to the true distribution D. However, in Section 6, we construct an example to show that such an approach requires much higher sample complexity than we can afford.
To enable sample-efficient learning, we propose a new algorithm, CoreLearning, that first identifies a core set, which is a subset of the empirical samples, and then computes a mixedsoftmax policy from the core. To identify the core, we develop a novel procedure to iteratively prune away the sets that contain less explored directions among the empirical samples, so that the set of the remaining samples at the end of the procedure becomes the core. Via a volumetric argument, we show that the directions in the core can be sufficient explored even if only using the sets in the core, and the core is still overwhelmingly large. Both properties are crucially used in the CoreLearning algorithm.
The high-level idea behind CoreLearning is that, on one hand, we can prove fast uniform concentration for the information matrix if all directions are sufficiently explored, so that the directions spanned by the core can be handled. On the other hand, the directions not included in the core are infrequent in D (because the core is large enough), and can be dealt with by the π G component in the mixed-softmax policy.
Much technical effort is devoted to the analysis of CoreLearning because (1) it seems not quite obvious whether a core with the desired properties even exists, and (2) a careful analysis is needed when combining the analysis for sufficiently explored directions and infrequent directions, since the (possible) directions of the context vectors are continuous, and the boundary between the two types of directions may not be always clear. Please refer to Section 6 for more detailed explanation.

Policy Switch Bounds for Adversarial Contexts
The Algorithm with Rare Policy Switches. We first recall that Abbasi-Yadkori et al. [2011] proposed a determinant-based doubling trick that only updates the policy when the determinant of the associated information matrix doubles. When applying to the OFUL algorithm in [Abbasi-Yadkori et al., 2011], the doubling trick leads to O(d log T ) policy switches. However, due to technical difficulty, the state-of-the-art analysis for the OFUL algorithm shows the asymptotically minimax-optimal regret only for ln K ≥ Ω(d). While it is still an open question whether a simple adaptation of OFUL (such as LinUCB proposed in [Chu et al., 2011]) also achieves the asymptotically minimax-optimal regret for ln K ≤ o(d), the only known technique in literature to achieve the optimality is via building a more sophisticated "super algorithm" based on the idea of LinUCB (e.g., SupLinUCB [Chu et al., 2011] and SupLinRel [Auer, 2002]). There are Θ(log T ) information matrices maintained in these super algorithms, and therefore a naïve application of the determinant-based doubling trick to these super algorithms leads to O(d log 2 T ) policy switches.
To improve the number of policy switches, we adopt a simple combination of OFUL and SupLinUCB, so that only O(log d) information matrices are maintained, leading to O(d log d log T ) policy switches. Please refer to Section 8 for more detailed explanation.
The Lower Bound. In Section 9, we prove that to achieve any √ T -type regret in the adversarial context setting, the algorithm has to switch the policy for at least Ω(d log T / log(d log T )) times. We first observe that the classical hard instances for linear bandits in [Dani et al., 2008] cannot work for our goal since their context vector set does not change with time and therefore their instances can be solved by our algorithm for stochastic contexts using O(log log T ) batches. Instead, we divide the T time steps into stages of consecutive time periods, and design different context vectors for different stages. We will design a class of specially structured hard instances, where the hidden vector θ delicately matches with the context vectors in each instance. We then lower bound the average-case regret over the class for any rarely switching learner, which implies the worst-case regret lower bound.
At a higher level, our construction is more similar to the recent work by Li et al. [2019]. However, the difference is that, in their construction, the regret that can be incurred by the worst learner is no more than √ T (up to polynomial factors in d and log T ). In contrast, in our task, we need to show that the learner could easily incur T 1/2+Ω(1) regret when using few policy switches. To achieve this, we need to design a class of hidden vectors θ and context vectors {x ti } so that the mean rewards of the candidate actions are much more separated from each other, while we still have to make sure that a rarely switching learner cannot learn enough information.

Preliminaries
Notations. Throughout the paper, we denote [N ] def = {1, 2, . . . , N } for any integer N . We define log x def = log 2 x and ln x def = log e x. We use ½[·] to denote the indicator variable for a given event (i.e., the value of the variable is 1 if the event happens, and 0 otherwise). We use · to denote the 2-norm of matrices and vectors. Matrix and vector variables are displayed in bold letters. For any discrete set X, we use △ X to denote the set of all probability distributions supported on X.
Linear Contextual Bandits. There is a hidden vector θ ( θ ≤ 1). For a given time horizon where D t is the distribution for the context vectors at time step t. We assume x ti ≤ 1 for all i and t almost surely. Before the game starts, the learner only knows T .
At each time step of the game t = 1, 2, . . . , T , the learner has to first decide a policy χ t that maps any set of context vectors X to a distribution in △ X . The learner then observes X t = {x ti } K i=1 , samples an action i t from χ t (X t ), 8 plays arm i t , and finally receives the reward r t = θ ⊤ x t,it + ε t , where ε t is an independent sub-Gaussian noise with variance proxy at most 1.
The goal of the learner is to minimize the expected regret where the expectation is taken over D 1 ⊗ D 2 ⊗ · · · ⊗ D T , the noises, and the internal randomness of the learner. In our algorithmic results, we also prove (1 − δ)-high probability expected regret, In this definition, setting δ = O(1/T ) recovers the usual expected regret up to an additive error of O(1).

Settings of Adversarial and Stochastic Contexts.
In the setting of adversarial contexts, there are no additional constraints for the distributions {D t }. Note that this corresponds to the oblivious adversary in bandit literature, meaning that the adversary has to choose all context vectors beforehand. In contrast, the stronger non-oblivious adversary may adaptively choose context Algorithm 1: BatchLinUCB play arm i t ∼ Unif(A t ), and receive reward r t ; 11: vectors for any time step according to all game history before that time. Since we only prove lower bounds for the adversarial context setting in this work, dealing with a weaker adversary actually means a stronger lower bound result.
In the setting of stochastic contexts, we have the additional assumption that D = D 1 = · · · = D T . However, correlation may still exist among the contexts at the same time step.
Models for Limited Adaptivity. In the batch learning model, the learner has to first choose a grid , the i-th batch consists of the time steps t = T i−1 + 1, . . . , T i . During the i-th batch, the learner must choose the policy χ (i) at the beginning of the batch, and the same policy will be used throughout the batch. The amount of adaptivity is measured by M , the number of batches.
In the rare policy switch model, a policy switch occurs at time step t > 1 if χ t = χ t−1 , and there is always a policy switch at time step 1. The amount of adaptivity is measured by the number of policy switches.
As mentioned before, the goal for the learner is to achieve the target minimax-optimal regret dT min{log K, d} (up to poly log T factors) with as little adaptivity (measured in each specific model) as possible. We also remark that the rare policy switch model is a relaxation of the batch learning model, because the learner can decide whether to change the policy at any time step. Therefore, the amount of adaptivity needed in the rare policy switch model is always less than or equal to the batch model.

Batch Elimination Framework and the G-Optimal Design
As a warm-up, in this section, we first present BatchLinUCB (Algorithm 1) to illustrate the batch elimination framework for the linear bandit problem with stochastic contexts. Later in Section 4.1, we will introduce the G-optimal experiment design and show how it helps to reduce the regret bound of the algorithm. While the regret bound in Theorem 2 is improved, it still has an extra √ d factor compared to the optimal minimax regret bound (without adaptivity constraints). The quest for optimal regret will be addressed in the later sections.
We now introduce our first algorithm. BatchLinUCB (Algorithm 1) uses M = O(log log T ) batches and a pre-defined static grid T = {T 1 , T 2 , . . . , T M }. For each batch k, BatchLinUCB keeps an estimateθ k for the hidden vector θ, which is learned using the samples obtained in the batch. To decide an arm during any time t in the k-th batch, the algorithm first performs an elimination procedure that is based on the estimateθ κ and the corresponding confidence region for each previous batch κ ∈ {1, 2, . . . , k − 1}. Let A t be the set of survived arms after the elimination. The algorithm then plays a uniformly random arm from A t . The following theorem upper bounds the regret of BatchLinUCB.
To prove Theorem 1, we first introduce the following lemma that constructs the confidence intervals of the estimated rewards.
Lemma 1. Fix any batch k, for each time step t in batch k, with probability at least (1 − δ/T 2 ), for all κ ∈ {1, 2, . . . , k − 1} and all i ∈ A t , we have that ti .
The proof of Lemma 1 can be found in many papers in linear bandit literature (e.g., [Chu et al., 2011;Li et al., 2019]), and is included in Appendix B.2 for completeness.
We now start proving Theorem 1. Fix any batch k such that k ≥ 2, when conditioned on the first (k − 1) batches, we let D k be the distribution of the survived candidate arms X = {x ti : i ∈ A t } at any time t during the k-th batch. We also let D 0 = {x ti } be the distribution of all candidate arms at any time t.
Suppose that the desired event in Lemma 1 happens for every time step during the k-th batch (which happens with probability at least (1 − δT k /T 2 ) by a union bound), it is straightforward to verify that for each time t during the k-th batch, the optimal arm is not eliminated by the elimination procedure (Line 6 to Line 8) in BatchLinUCB. In other words, we have that i * t def = arg max i∈ [K] x ⊤ ti θ ∈ A t for each time step t in the k-th batch. Therefore, we can now upper bound the expected regret incurred during batch k as where (2) is due to the successful events of Lemma 1, the both inequalities in (3) are due to the elimination process and that i * t ∈ A t . By the definition of ω (k−1) ti and the definition of D k , we further have that We finally observe that X ∼ D k can be sampled by drawing an X ′ ∼ D k−1 and performing an elimination process usingθ k−1 as well as the corresponding confidence region for X ′ . We note that X ⊆ X ′ . Therefore, continuing with (4), we have that Now the goal is to upper bound EX∼D k−1 max x∈X x ⊤ Λ −1 k−1 x. The following lemma is a direct application of Lemma 21 in Appendix A.1.
Assuming that (6) holds for batch (k − 1), we have that Together with (5), and collecting the probabilities, we have that with probability at least Note that (7) also holds for k = 1 almost surely, because T 1 ≤ √ dT and the maximum regret incurred per time step is at most 1.
Finally, summing up the expected regret incurred across all batches and collecting the probabilities, we have that, with probability at least (1 − δ), the expected regret is bounded by This concludes the proof of Theorem 1.

Improved Regret via the G-Optimal Design
In this subsection, we show how a simple application of the G-optimal design can help to replace the K factor in Theorem 1 by (the usually smaller quantity) d. To achieve this, we first introduce the following lemma on G-optimal design, which is a direct corollary of the General Equivalence Theorem of Kiefer and Wolfowitz [1960].
Lemma 3. For any subset X ⊆ R d , there exists a distribution K X supported on X, such that for any ε > 0, it holds that Furthermore, if X has a finite support, one can find a distribution such that the right-hand side of (8) is relaxed to 2d in time poly(|supp(X)|).
We now describe the new BatchLinUCB-KW algorithm. It is almost the same as Batch-LinUCB, while the only difference is that at Line 10 of Algorithm 1, letting X = {x ti : i ∈ A t }, we compute a distribution K X satisfying (8) (up to the factor 2 relaxation) and randomly select the action For completeness, a full description of BatchLinUCB-KW is provided in Appendix B.1. We now prove the expected regret of BatchLinUCB-KW as follows.
Theorem 2. With probability at least (1 − δ), the expected regret of BatchLinUCB-KW is We now prove Theorem 2. Note that the analysis for BatchLinUCB also applies to BatchLinUCB-KW up to (5). Thus, we will focus on bounding Assuming that (10) where the inequality is Jensen. By Lemma 26 and (8) (up to the factor 2 relaxation), we have that Combining (11) and (12), we have that where the last inequality is due to (10). Combining (13) and (5), we have that with probability at Using the similar argument as the analysis for Algorithm 1, we have that with probability at least (1 − δ), the expected regret of BatchLinUCB-KW is at most proving Theorem 2.

Distributional G-Optimal Design: Existence & Parametric Forms
We now work towards removing the extra √ d factor in the regret of Theorem 2, so as to achieve the optimal √ dT -type regret. The high level idea is to use a difference sample policy other than uniform sampling over all (survived) candidate arms or the G-optimal-design-based π G .
Given a sample policy π that maps any set of arms (X ⊆ R d ) to a distribution in △ X , we will be interested in its performance, defined as follows.
Definition 1 (λ-distributional G-variation and information matrix). For any distribution D of the set of arms X ⊆ R d and any sample policy π, we define the λ-distributional G-variation, or λ-variation for short (λ > 0), of π over D as where we define the information matrix by D is non-increasing as λ grows, when the limit exists, we also define and set V (0) Indeed, the arguments in Section 4 imply the following lemma.
Lemma 4. For any distribution D on the context vectors of the K arms, we have that In light of Lemma 4, the question whether the regret of our algorithms can be improved to O( dT poly log(KT /δ)) boils down to whether one can find a sample policy π such that the bounds in (15) are improved to O(d) × poly log d. In this section, we will show that such policies not only exist, but also admit a succinct parametric form so that we can later study how to efficiently learn the relevant parameters.
To better explain our results, we first define the following class of parameterized sample policies.
Definition 2 (Argmax and mixed-argmax policies). Suppose we are given a positive semi-definite matrix V 0. We define the associated argmax policy by where in the arg max operator, ties are broken in a deterministic manner.
In this subsection, we use π G to denote a fixed policy with respect to (9) and satisfying (8) (up to the factor 2 relaxation). Suppose we are given a set V = {(p i , V i )} n i=1 such that p i ≥ 0 and p 1 + · · · + p n ≤ 1. We define the associated mixed-argmax policy by if det U t > 2 det W n then 8: The following theorem states that for any D, there exists a good mixed-argmax policy with only O(d log d) argmax policies in the mixture. 9 Theorem 3. Fix any distribution D = Unif(S) where S = {X 1 , X 2 , . . . , X Γ } (which may be a multiset) and any λ ∈ (0, 1). There exists a mixed-argmax policy with parameters Proof. We will assume Γ > λ −1 without loss of generality, as the properties to be proved do not depend of Γ and S is a multi-set so that we can always duplicate the elements by finitely many times. We prove the theorem constructively. We consider Algorithm 2, which is very similar to the linear bandits algorithms in literature. For N = Θ(d 2 log d), the algorithm creates ΓN times steps, which includes N blocks, each of which contains Γ consecutive time steps. In each block, the Γ sets of arms X 1 , . . . , X Γ are sequentially presented. The algorithm then simulates the linear bandit algorithms, where at each time step, the arm with the maximum variance (according to the information matrix W n ) is selected. Inspired by the rarely switching algorithm for linear bandits [Abbasi-Yadkori et al., 2011], the information matrix W n is only updated when its determinant doubles. This significantly reduces the number of updates and is crucial to upper bounding the number of individual argmax policies in the returned mixed-argmax policy. We refer to the consecutive time steps between two neighboring updates as a stage. Each of the information matrices in a stage corresponds to an individual argmax policy in the returned policy, and the corresponding probability weight is proportional to the length of the stage. The only exception is that we discard the stages that contain less than Γ time steps (i.e., the ones that are shorter than a block).

Proof of Item (a). Note that
By Lemma 26 and (8) (up to the factor 2 relaxation), for all t, we have that Combining (16) and (17), we have that and n ≤ log d 4d = 4d log d.
Proof of Item (b). Because we discard the stages whose lengths are less than Γ, for p i > 0, we have that Proof of Item (c). We finally upper bound the λ-variation of the returned policy π = π MA V . Note that where we let B be the set of time steps that are discarded in Line 9 of Algorithm 2. It remains to show that both terms are O(d log d). For the second term, we have where the inequality is because by definition of a mixed-argmax policy, with probability 1/2, π G is invoked, and therefore Continuing with (20), since B contains at most n stages that are shorter than a block, therefore, we have that where the second inequality is due to (14) and the monotonicity of V D . For the first term in (19), we claim that which will be established at the end of this proof. Once we have (22), also noting that I D (π) (1/2) I D (π G ) because of the 1/2 portion of π G in the definition of the mixed-argmax policy, we get that Therefore, where the first inequality in (24) is by Lemma 25, the first inequality in (25) is by the elliptical potential lemma (Lemma 29), 10 and the second inequality in (25) is due to (18). It remains to establish (22). Note that By (17), we have Therefore, continuing with (26), we have that which concludes the proof of the theorem.

The Mixed-Softmax Policies with More Robustness
To make the sample policy learnable, instead of the mixed-argmax policies, we will deal with the more robust mixed-softmax policies. To define this class of policies, we first define the softmax function as a distribution such that It is easy to check the following fact. Proof. Let i * be an index that maximizes s i . Note that for all j such that s j ≤ (1/2) × s i * , the probability mass that softmax put for j is at most (1/k) of that for i * . Therefore, Pr i∼softmaxα(s 1 ,...,s k ) and the fact follows.
We now define the class of mixed-softmax policies.
Definition 3 (Softmax and mixed-softmax policies). Fix α = log K (where K is the number of arms per time step). Suppose we are given a positive semi-definite matrix M 0. We define the softmax policy Suppose we are given a set M = {(p i , M i )} n i=1 such that p i ≥ 0 and p 1 + · · · + p n = 1. We define the mixed-softmax policy π MS M (X) = π G (X), with probability 1/2, π S M i (X), with probability p i /2. Similarly to Theorem 3, we prove the following theorem on the existence of good mixed-softmax policies.
Theorem 5. Fix any distribution D = Unif(S) where S = {X 1 , X 2 , . . . , X Γ } (which may be a multi-set) and any λ ∈ (0, 1). There exists a mixed-softmax policy π MS The proof of Theorem 5 is very similar to that of Theorem 3. Here we only point out the differences as follows.
First, at Line 5 of Algorithm 2, we let X t ← E x∼π S W −1 n (Xt) xx ⊤ , and at Line 6, we let U t ← U t−1 + X t . Note that Tr(X t ) ≤ 1. Let M be the output of the algorithm.
The proof of Items (a) and (b) remains the same except for the occurrences of x t x ⊤ t are replaced by X t in (16) and (17).
For the proof of Item (c), let π = π MS M , we still get (19), and the second term of (19) is bounded by the same way. For the first term, replacing x t x ⊤ t by X t in (22) (and its proof from (26) to (27)), we still get (23). Therefore, where the third inequality in (28) is by Theorem 4. Again, by Lemma 25 and the elliptical potential lemma (Lemma 29), we have that Combining the bounds on both terms of (19), we prove the theorem.

Learning the Distributional G-Optimal Design
In this section, we present an algorithm to learn a good mixed-softmax policy using only poly(d) log δ −1 samples with success probability at least (1 − δ).
The Natural Idea and its Counterexample. The most natural idea is to first draw γ independent samples X 1 , . . . , X γ ∼ D and form an empirical distribution S = Unif{X 1 , . . . , X γ }, learn a good policy π for S according to Theorem 5, and hope that π also works well for D (i.e., π generalizes to the true distribution). Unfortunately, such an approach is unlikely to work. Below we illustrate an example where, even when the number of samples γ is very large, a good policy for S still fails to generalize to D with significant probability.
be the set of canonical basis, and ε > 0 be a parameter to be determined later. Let , 3, . . . , d}. Consider D supported on {Y 1 , . . . , Y d } the probability mass for Y 1 is 1/(dγ) and the probability for Y i (i ≥ 2) is q = (1 − 1/(dγ))/(d − 1). If we make γ independent samples X 1 , . . . , X γ ∼ D, with probability Ω(1/d), we will see Y 1 once among the samples, and the probability mass of Y 1 in S becomes 1/γ, which is d times its true probability mass. Due to this discrepancy, we will show that a good sample policy for the empirical distribution S does not work as well on true distribution D.
We consider the sample policy π such that π(X) = e i when X = Y i . When the event above happens, we have that I S (π) = diag(1/γ, p 2 , . . . , p d ) where p i is the probability mass for Y i in S (for i ≥ 2). When ε = d/γ, we can verify that π is a good policy for the empirical distribution S since However, for the true distribution D, we have that I D (π) = diag(1/(dγ), q, . . . , q), and for any λ ∈ [0, 1/(dγ)), it holds that Note that in this example, the only constraint for γ is that 1/(dγ) > λ ⇔ γ < 1/(dλ). Therefore, we have illustrated that, even when γ is greater than an arbitrary polynomial of d, with probability Ω(1/d), a good policy for the empirical distribution S does not generalize to the true distribution D. 11 By adding more dimensions, we can even strengthen this counterexample so that the failure probability becomes (1 − o(1)). Using similar tricks, we can also show that a good mixed-softmax policy does not generalize well.
Our Algorithm: CoreLearning. The key message from the counterexample above is that if a context direction in R d appears with tiny probability in D, a limited amount of samples might greatly change its probability in the empirical distribution S, and fail the generalization argument. To address this issue, the idea of our new algorithm is to prune these infrequent context directions, learn a mixed-softmax policy over the remaining "core" directions, and finally argue that the infrequent directions can be properly handled by the π G component in the mixed-softmax policy.
In light of this idea, we propose CoreLearning (Algorithm 3). In this algorithm, instead of directly learn the policy from the whole set of samples, we first find a large enough core set C at Line 2, and then learn the mixed-softmax policy only using the samples in C. The key property of the core is specified by (29), which is a technical realization of our pruning idea. The property requires that every direction in C should be well explored by the π G policy and only the context vectors within C. To see how the core set helps to resolve the issue in our counterexample, we note that the infrequent set Y 1 is the main trouble-maker. However, even if Y 1 happens to appear among the samples {X 1 , . . . , X γ }, it will not be included in the core since its corresponding variation max y∈Y 1 y ⊤ (λI + I Unif(C) (π G )) −1 y ≥ (λ + 1/γ) −1 > d c when λ is sufficiently small and γ ≫ d c . Therefore, CoreLearning will learn a sample policy with Y 1 pruned away, and void our counterexample.

Algorithm 3: CoreLearning for the Distributional G-Optimal Design
Input: λ ∈ (exp(−d), 1), and S = {X 1 , . . . , X γ } Output: A mixed-softmax policy π 1: Set constant c = 6; 2: Find a core C ⊆ S = {X 1 , . . . , X γ } (using CoreIdentification (Algorithm 4), see Lemma 5) such that and which is at least 1/2 for sufficiently large d; 3: Compute the mixed-softmax policy π for the samples in C (according to Theorem 5) and return π; While the core set property (29) is much desirable, even whether such a core set with cardinality constraint (30) exists is not obvious. In Section 6.1, we prove Lemma 5 to show the its existence, and provide an efficient algorithm CoreIdentification to find one. The analysis of Algorithm 3 also relies on a few uniform concentration inequalities (Lemma 7 and Lemma 9) which are proved later in Section 6.2.
For now, assuming the lemmas introduced above, we prove the following main theorem of this section (the guarantee for Algorithm 3).
Theorem 6. Suppose that λ ∈ (exp(−d), 1). Let X 1 , . . . , X γ ∼ D be i.i.d. drawn from the distribution D. Let π be the returned policy of Algorithm 3. We have that where we define the λ-deviation of π over D by Note that we are only able to provide the upper bound for V (λ) D (π). However, this is still enough for our linear bandit application.
We now prove Theorem 6. For notation convenience, we define S def = Unif(S), C def = Unif(C), and we define the mollifier which is a continuous surrogate of the indicator function ½[x ≤ β].
We now condition on the successful events of the uniform convergence lemmas (Lemma 7 and Lemma 9), which, by a union bound, happens with probability Then, the proof of Theorem 6 consists of the following four steps.
Step I: Lower Bounding the Information Matrix. The goal of this step is to establish (33). Let U = λI + I C (π). Note that λI U (1 + λ)I. By the successful event in (59) of Lemma 9 (letting W = U ), we have that Since where the last inequality is for c ≥ 6.
Step II: Upper Bounding the Variation in the "Core Directions". Let W = λI +I S (π) 1 2 (λI +I C (π)). The goal of this step is to establish (38). By the successful event in (48) of Lemma 7, we have that

This implies that
Let ζ = 1 − |C|/|S| = 1 − |C|/γ ≤ O(d 3−c log(1/λ)). Note that For the first term in (35), by the guarantee of Theorem 5, we have For the second term in (35), by the variation bound for π G (Lemma 4), we have that where the first inequality is Jensen and the last inequality is for c ≥ 5. Combining (34), (35), (36), (37), we have that Step III: Upper Bounding the Variation in the "Infrequent Directions". The goal of this step is to establish (41). By the successful event in (49) of Lemma 7, we have that

This implies that
Here, (39) is due to Cauchy-Schwarz and the first inequality in (40) is by the variation bound for π G (Lemma 4). Altogether, we have that Step IV: Putting Things Together. Combining (38) and (41), we have By the definition of W , and together with (33), we have that proving Theorem 6.

Finding the Core
We now present our algorithm (CoreIdentification, Algorithm 4) to find the core, and prove the following lemma on its guarantee.
Lemma 5. Let S = {X 1 , . . . , X γ } be a sequence/multi-set of context sets. Algorithm 4 finds a cor set C ⊆ S in O(d log λ −1 ) iterations that satisfies (30) and We remark that (42) implies (29), because 1 Proof. For any iteration ξ, we denote We first claim that, for each ξ, either (a) C ξ+1 satisfies (42) (and thus the algorithm returns), or (b) det J ξ+1 ≥ 2 det J ξ . To see this, suppose that (a) does not hold. In this case, we have that there exists X i ∈ C ξ+1 and x i ∈ X i , such that Since X i ∈ C ξ+1 , by Line 4 of Algorithm 4, we know that Dividing (43) by (44), together with Lemma 25, we find that proving the claim. Now we prove the lemma. First, we prove that the algorithm returns after at most O(d log λ −1 ) iterations. Note that J 1 (1 + λ) −1 I. Furthermore, for every iteration ξ, we have that J ξ λ −1 I. Together with λ < 1, we have that det J ξ ≤ (2λ) −d det J 1 . By the claim established above in (45), we have that det J ξ ≥ 2 ξ−1 det J 1 so long as the algorithm does not return at iteration ξ. Thus we conclude that ξ ≤ O(d log λ −1 ) when the algorithm returns.
Let C = C ξ be the returned set. We also need to show that C satisfies (30). We claim that for each iteration j, which implies (30), because where the first inequality uses (46) and the second inequality uses ξ ≤ O(d log λ −1 ). Finally, we prove (46). We have that where the first inequality is by Markov's inequality and the second inequality uses the variation bound for π G (Lemma 4) on the distribution D = ½[X ∈ C] · X, where X ∼ Unif(S).

Uniform Concentration Lemmas
Fix λ < 1. We define the following set of positive semi-definite matrices Let X 1 , . . . , X γ be a sequence of sets of context vectors with norm at most 1. For any positive definite matrix W ∈ R d×d , we define the following functions.
Proof. By Lemma 28 (and that the context vectors have norm at most 1), for any X i , the function -Lipschitz, and this proves the lemma.
We now present our first uniform concentration lemma.
Lemma 7 (The first uniform concentration lemma). Let X 1 , . . . , X γ ∼ D be i.i.d. drawn from the distribution D. We have the following concentration properties, Pr sup For (48), we first consider a fixed matrix N ∈ V ε . For i ∈ [γ], let Then {Y i } are independent and bounded as |Y i | ≤ 8d c almost surely. Using Lemma 18 with δ = d 2 and R = 8d c , we have Pr Next we consider all N ∈ V ε . Using a union bound, we have that Finally, we choose ε = λ 3 d/4. By the Lipschitzness of f (W ) in Lemma 6, we have that Therefore, using (50), we have that where the last inequality uses the covering number bound in Lemma 27. For (49), we can prove it similarly as (48). The only differences are that 1) we need to apply Lemma 18 with δ = 1/(2d) and R = 1, and 2) we need to choose ε = λ 3 /(4d).
We define the policy class Π by and we define the following (matrix-valued) function on W ∈ W and π = π MS M ∈ Π, Lemma 8. We claim the following smoothness properties of the function F (W , M) on its parameters, (a) F (·, ·) is 3λ −3 -Lipschitz with respect to W ; (b) F (·, ·) is λ −2 -Lipschitz with respect to each p j ; (c) for any two parameters Proof. For item (a), we note that W −1/2 ≤ λ −1/2 , that W −1/2 is λ −3/2 -Lipschitz with respect to W by Lemma 28, and that I X i (π) ≤ Tr(I X i (π)) ≤ 1. Also, by the proof of Lemma 6, we have that ϕ 2d c (max x∈X i {x ⊤ W −1 x}) is λ −2 -Lipschitz with respect to W , that φ 2d c (·) ∈ (0, 1), and that max x∈X i {x ⊤ W −1 x} ∈ (0, λ −1 ). Therefore, we can prove this item. For item (b), we note that I X i (π MS M ) is 1-Lipschitz in each p j and we conclude by noting that For item (c), since a mixed-softmax policy is a mixture of softmax policies, in the remaining proof, we first analyze the information matrix of the softmax policies π S M j , π S M ′ j , and then analyze that of the mixed-softmax policies π MS where the second inequality in (53) uses M j d −1 I. Similarly, we can show Recall that α = ln K. For the softmax policy π S M ′ j and any vector x ∈ R d , we have that Similarly, we have Therefore, for any context set X, we have where the first inequality uses (54) and (55). As a direct corollary, for any context set X, we have Therefore, for the mixed-softmax policy, we have where the inequality uses (56). Swapping M j and M ′ j , we find Setting X = X i in (57) and (58), we establish (52).
We now present our second uniform concentration lemma.
Lemma 9 (The second uniform concentration lemma). Fix λ < 1. For any mixed-softmax policy π MS M with M ∈ M, and any positive semi-definite matrix W ∈ W (defined in (47)), we define the random function where the random function F is defined in (51), and the randomness is from the independent samples X 1 , . . . , X γ ∼ D. We then have that Proof. First, we consider fixed W , M. Using Lemma 23 with δ = 1/32 and R = 2d c , we have Second, we define the covering. Let We have where the last inequality uses that log K ≤ O(d).
Finally, we invoke the smoothness results from Lemma 8. Note that when the event in (60) holds, by item (c) of Lemma 8, we have Note that the Lipschitz constant of G(·, ·) is at most double of that of F (·, ·). By item (b) of Lemma 8, we have Finally, by item (a) of Lemma 8, we have that sup W ∈W sup π∈Π G(W , π) ≤ 1 5 + 2 · 3λ −3 · λ 3 120 = 1 4 .

Putting Everything Together: the Optimal Batch Algorithm
Our final algorithm with O(log log T ) static-grid batches and optimal minimax expected regret (up to poly log T factors) is presented in Algorithm 5. Compared with BatchLinUCB and BatchLinUCB-KW, the main difference here is the addition of from Line 11 to Line 16, which not only learns the new estimateθ k , but also the new sample policy π k . Learning of the two objects are done through disjoint sets of samples (A and B). This is because that D k depends onθ k (which is learned from A) and we have to make B disjoint from A so as to ensure elements in S are independently sampled from D k . The following theorem bounds the expected regret of Algorithm 5.

11:
Evenly divide {T k−1 + 1, . . . , T k } into two sets A, B; 12: 16: Use the context sets S = {{x τ,a | a ∈ A (k) τ }} τ ∈B and λ = 1/T as the input of Algorithm 3 and learn the sample policy π k ; by a simple ε-net argument, so that our regret bound becomes minimax-optimal for all K (up to poly log T factors).
We finally remark that we make no effort in optimizing the exponent in the constraint that T ≥ d O(1) . Some simple tricks may significantly reduce this exponent constant. For example, first running a revised version of BatchLinUCB-KW till time T /d and then switch to BatchLinUCB-DG would reduce the exponent to 17. A more careful analysis in the concentration lemmas in Section 6 may further substantially optimize the constant.
We now provide the proof of Theorem 7.
Proof of Theorem 7. We adopt the notations in Section 4. Conditioned on the batches 1, 2, . . . , k − 1, we can bound the expected regret incurred in batch k similarly as (5), and have that with probability at least (1 − δT k /T 2 ), Furthermore, similar to Lemma 2, we can show that for each batch k (k < M ), with probability (1 − δ/T 2 ), we have that Note that compared with (6), (62) has a worse constant 32 since A only contains half of the samples.

Rarely Switching Algorithm for Adversarial Contexts and ln K ≤ o(d)
Abbasi-Yadkori et al. [2011] showed an algorithm for adversarial contexts that achieves d √ T × poly log T regret for any K. The authors also propose a special doubling trick that only updates the policy when the determinant of the corresponding information matrix (i.e., λI + t x t,it x ⊤ t,it ) doubles. Using this trick, their algorithm only uses O(d log T ) policy switches, while still achieving the same order of regret. However, when log K ≪ d, there is a gap between the regret of their algorithm and the target minimax-optimal regret T min{d, log K} × poly log T . In this section, we propose an algorithm to close this gap, while still maintaining a small number of policy switches.
The Natural Approach and its Limitation. The most natural approach is to apply the determinant-based doubling trick to the minimax-optimal algorithms for fewer number of arms, such as SupLinUCB [Chu et al., 2011] and SupLinRel [Auer, 2002]. However, a direct implementation of such an approach would lead to O(d log 2 T ) policy switches. The reason is that, to replace an √ d factor by the √ log K factor in the algorithm by Abbasi-Yadkori et al. [2011], the state-of-the-art concentration inequalities have to crucially rely on the statistical independence between the noises and the context vectors of the played arms, which is not true in the plain LinUCB algorithm (and the OFUL algorithm in [Abbasi-Yadkori et al., 2011]). In contrast, the concentration inequality used in [Abbasi-Yadkori et al., 2011] does not require such strong independence, but loses a √ d factor when K is small.
To ensure the independence,  and Chu et al. [2011] came up with a more sophisticated layering trick, where each time step is assigned to one of the layers. The layers form a hierarchy and the observations from (the time steps in) each layer give more and more accurate estimates for the mean rewards, as the level of the layer increases. Meanwhile, it is possible to ensure the independence between the observations and the context vectors within each layer, so that the more accurate concentration inequality (e.g., Lemma 1 in this paper) can be applied. There are Θ(log T ) layers in SupLinUCB and SupLinRel, where each layer maintains a separate information matrix for the estimation. Therefore, if we directly apply the determinant-based doubling trick, there will be O(d log T ) updates in each layer, leading to O(d log 2 T ) policy updates in total.
Our Approach. Our approach is a simple combination of both types of algorithms mentioned above. Note that the estimation accuracy of the layers in SupLinUCB and SupLinRel starts from Ω(1) for the first layer, and halves as the level of the layer increases. Therefore, it takes Θ(log T ) levels to reach the sufficient accuracy of d/T . We also note that by the detailed analysis, if the accuracy provided by a layer is ̟, the regret incurred by the layer can be roughly bounded by d/̟ (up to poly-logarithmic factors).
To reduce the number of layers, in our algorithm, we introduce a special layer, namely layer 0, which helps to bootstrap the accuracy parameters. More precisely, at layer 0, we use the concentration inequality by Abbasi-Yadkori et al. [2011] (Lemma 24). Since such an inequality is not as efficient as Lemma 31, the regret incurred by layer 0 can only be bounded by d 2 /̟ 0 (up to poly-logarithmic factors), where ̟ 0 is the accuracy parameter for layer 0. However, since the inequality does not rely on the strong independence assumption, instead of starting from the Ω(1) accuracy, we may directly set ̟ 0 = d 1.5 / √ T , a much smaller value, while the incurred regret is still as desired. From layer 1, we go back to the normal layer settings as SupLinUCB and SupLinRel, and set ̟ κ = ̟ κ /2 for κ = 1, 2, . . .. Since the target accuracy is d/ √ T , we now only need κ 0 = O(log(̟ 0 /(d/ √ T ))) = O(log d) layers to achieve the minimax-optimal regret. Together with the determinant-based doubling trick, our algorithm uses only O(d log d log T ) policy switches.
Our RarelySwitch-SupLinUCB algorithm is formally presented in Algorithm 6. Note that the key difference from SupLinUCB is at Line 1 and Line 3, where α 0 and ̟ 0 are specially set. Also, at Line 7, a special elimination rule for layer 0 is implemented, which is different from the elimination rules for the rest of the layers at Line 12. We next formally analyze the algorithm.
Theorem 8. For any C ≥ 2, the number of policy switches made by Algorithm 6 is at most O(d log d log T / log C); with probability (1 − 2δ), the expected regret of the algorithm is at most O(C √ dT log d log T log(dKT /δ)).
Proof. We first upper bound the number of policy switches. Note that for each κ, we have that ln det Λ κ,T ≤ O(d log T ), and ln det Λ κ,0 = 0; therefore, ζ κ is updated at Line 17 by at most O(d log T / log C) times. Since the learning policy is completely decided by {Λ κ,ζκ , ξ κ,ζκ } κ 0 κ=0 , we conclude that the policy changes by at most (κ 0 + 1) · O(d log T / log C) = O(d log d log T / log C) times.
We next prove the regret of Algorithm 6. Note that when the event specified in Lemma 24 holds (which happens with probability at least 1 − δ), for any i ∈ [K] and any time step t ∈ [T ], we have where we use (86) and that λ = 1 in Algorithm 6.

15:
play arm i t and receive reward r t ; 16: } only depends on the context vectors which are independent from the noises, {r (κ ′ ) τ,i | τ < t, κ ′ < κ, i ∈ [K]} depends on the context vectors and the noises generated from time steps in Ψ t−1,0 ∪ · · · ∪ Ψ t−1,κ−1 , which is disjoint from Ψ t−1,κ . Thus, the procedure for generating Ψ t−1,κ does not use the noises in the time steps in Ψ t−1,κ , and therefore the noises are independent sub-Gaussian random variables even when conditioned on Ψ t−1,κ . Given this statistical independence property, by Lemma 1, we have that with probability at least 1 − δ, for any i ∈ [K], any time step t ∈ [T ] and any κ ∈ {1, 2, . . . , κ 0 }, it holds that Now, summarizing the discussion above, we define the desired event and have that Pr[E] ≥ 1 − 2δ. Below we will upper bound the expected regret incurred by the algorithm when conditioned on E.
For each layer κ ∈ {0, 1, 2, . . . , κ 0 }, we define the regret incurred during time steps that are assigned to layer κ as Since each time step will be assigned to exactly one layer κ ∈ {0, 1, . . . , κ 0 }, the total regret is We will use the following lemmas.

Proof of Lemma 10
The third bound |Ψ T,κ 0 | ≤ T is self-evident, so we only prove the first two bounds. By the elliptical potential lemma (Lemma 29), for every κ ∈ {0, 1, 2, . . . , κ 0 }, we have that which, together with the Cauchy-Schwarz inequality, implies that In the following, we use ζ κ,t to denote the value of ζ κ at Line 16 of Algorithm 6 during time step t. Note that we have ζ κ,t ≤ t − 1 for every κ.

Proof of Lemma 11
Lemma 11 is a direct corollary of the following two lemmas, which we prove separately in this subsection.
Theorem 9 shows that, even for K = 2, when T ≥ d 2 , in order to achieve √ dT × poly log T regret, M has to be Ω(d log T / log(d log T )). Note that on the upper bound side, our Algorithm 6 and the algorithm by Abbasi-Yadkori et al. [2011] achieves C times the target minimax-optimal regret (up to poly log T factors) with O((d log d log T )/ log C) policy switches, and our Theorem 9 shows that Ω( d log T log C+log(d log T ) ) policy switches are needed, almost matching the upper bound for every C.
To prove Theorem 9, we first prove the lower bound in the special case of d = 2 in Section 9.1. Then, in Section 9.2, we prove the theorem for general d using the special case as a building block.

Lower Bound for Constant-Dimension Special Case
Lemma 14. When K = d = 2, for sufficiently large T , suppose the expected number of policy switches made by the learner is at most M (40 ≤ M ≤ (ln T )/24), then there exist a bandit instance such that the learner's expected regret on the instance is at least T 1/2+1/(8M +2) /32.
To prove Lemma 14, we will construct a class of bandit problem instances B = {B (u) }, where each instance B (u) is parameterized by u ∈ {±1} L and L = 4M . For any fixed learner with no more than M policy switches, we will show that the regret averaged over the 2 L instances in B is large, and therefore there exists at least one instance in B that is bad for the learner.
For each B (u) , we assume that the noises are independent centered Gaussian with variance 1. We also need to define the hidden vector θ (u) and the context vectors {x t,2 } for every t). Before defining B, we first divide the time steps into stages, and define a few helpful notations.
We now start analyzing the constructed instances.
Suboptimal Action and its Regret. Since there are only two candidate actions during each time step, we refer to the one with smaller expected reward as the suboptimal action. The following lemma lower bounds the expected regret incurred by playing a suboptimal action.
Lemma 15. For any instance B (u) , and any time step t, the regret incurred by playing the suboptimal action at time step t is at least υ −1 /(2 √ T ).
Proof. Suppose that time step t is in stage j. The regret incurred by the suboptimal action is The Regret of a Rarely Switching Learner. For any learner who switches the policy for at most M times, let F j be the event that the policy is not switched during stage j. Let E j be the event that the learner's policy χ t places greater or equal to 1/2 probability mass on the suboptimal action at time t, where t = t j−1 + 1 is the first time step of stage j. By Lemma 15, the expected regret of the learner for bandit instance B (u) can be lower bounded by where E B (u) [·] denotes the expectation taken over the probability distribution induced by the learner and the bandit instance B (u) (and we similarly define where F j denotes the complement event of F j and the last inequality is because that the learner can switch in at most M stages (in expectation).
Probability of Playing a Suboptimal Action. By the discussion above, to lower bound the regret, we need to lower bound p (u) j . We first prove the following lemma.
Lemma 16. Consider any u = (u 1 , u 2 , . . . , u L ) ∈ {±1} L and u ′ = (u ′ 1 , u ′ 2 , . . . , u ′ L ) ∈ {±1} L . Suppose u = u ′ , let j be the smallest index such that u j = u ′ j . For any event E, we have Proof. Let t = t j−1 be the last time step before stage j. We will consider the sample space Ω t that consists of the trajectories (i 1 , r 1 , . . . , i t , r t ) and the internal randomness source s used by the learner. Now consider two probability distributions D and D ′ over Ω t , where D is induced by the learner and the instance B (u) , and D ′ is induced by the learner and B (u ′ ) . We will show that where KL(· ·) denotes the Kullback-Leibler (KL) divergence between the two distributions, so that we can prove the lemma by invoking Pinsker's inequality (Lemma 30). We now prove (75). Fix any s, let D s be D conditioned on s and let D ′ s be D ′ conditioned on s. Since D and D ′ share the same marginal distribution on s, to prove (75), we only need to show Let q(i 1 , r 1 , . . . , i t , r t ) and q ′ (i 1 , r 1 , . . . , i t , r t ) be the probability density functions for D and D ′ respectively. We have that and where i τ (i 1 , r 1 , . . . , i τ −1 , r τ −1 ; s) is the deterministic decision of the learner at time τ given the trajectory (i 1 , r 1 , . . . , i τ −1 , r τ −1 ) and s, and q (u) (r τ |i τ ) is the probability density function for the reward at time t, if playing action i τ in instance B (u) .
Since the second dimensions of θ (u) and θ (u ′ ) are the same, the difference of the mean reward at any time step in stage j ′ < j for the same action in B (u) and B (u ′ ) is either |ψ(u)z ′ j − ψ(u ′ )z ′ j | (if the first action is played) or 0 (if the second action is played, since ψ j−1 (u) = ψ j−1 (u ′ )). Since the rewards are Gaussian with variance 1, and the KL divergence between two variance-1 Gaussian variables with means µ 1 and µ 2 is (µ 1 − µ 2 ) 2 /2, for any τ ≤ t that is in stage j ′ and any i τ ∈ {1, 2}, we have that where the last inequality is because that j is the first index where u and u ′ differ and that υ ≤ 1/10. By (77), (78), (79), and the Chain Rule for KL divergence, we have that proving (76).
We now bound p (u) j by the following lemma.
Lemma 17. Consider any u = (u 1 , u 2 , . . . , u L ) ∈ {±1} L and u ′ = (u ′ 1 , u ′ 2 , . . . , u ′ L ) ∈ {±1} L . Suppose u = u ′ , let j be the smallest index such that u j = u ′ j . Then we have p Proof. Since j is the smallest index such that u j = u ′ j , by our construction, exactly one of ψ j (u) and ψ j (u ′ ) is greater than ψ j−1 (u), which means, at stage j, any action that is suboptimal for instance B (u) is optimal for instance B (u ′ ) , and vice versa. Let t = t j−1 + 1 be the first time step in stage j. Let E be the event that the learner's policy χ t for time step t assigns at least 1/2 probability mass to the suboptimal action for B (u) . Since B (u) and B (u ′ ) share the same context vector set at time step t (because ψ j−1 (u) = ψ j−1 (u ′ )), the complement event E is that χ t assigns at least 1/2 probability mass to the suboptimal action for B (u ′ ) . Invoking Lemma 16, we have that Putting Things Together and the Average Case Analysis. Note that where u ⊕j is the ±1 sequence derived by flipping the sign of the j-th element of u, and the inequality is due to Lemma 17. Therefore, there exists u * such that L j=1 p proving Lemma 14.

Proof of Theorem 9 for General Dimensions
We equally divide the T time steps into d/2 intervals. We construct the class of bandit instances, B from the class B constructed in the proof of Lemma 14 as follows. For each ℓ ∈ {1, 2, . . . , d/2}, we choose a bandit instance B ℓ from B, and construct the d-dimensional instance B. The hidden vector θ of B is derived by concatenating the hidden vectors of the d/2 smaller instances. During the ℓ-th interval of time, we use the context vectors in B ℓ in order: for each time step in the ℓ-th interval, we put the 2-dimensional context vectors in the corresponding time step in B ℓ at the (2ℓ − 1)-th and 2ℓ-th entries, while filling other entries with 0. B will consist of all possible instances that can be constructed in this way, and we have B = |B| d/2 . By our construction, the rewards from different time intervals are completely independent. Since the length of an interval is T /(d/2), if we let L = 4M/(d/2) and υ = T /(d/2) −1/(L+1) , we can prove similarly as Lemma 14 that where R ℓ is the regret incurred during the ℓ-th interval, and M B,ℓ is the expected number of policy switches made during the ℓ-th interval, when given instance B. Therefore, we have that which means that there exists at least one instance from B such that the learner incurs at least √ dT × 1 32d 2T d 1/(16M/d+2) expected regret, proving the theorem.

A.1 Concentration Inequalities
Lemma 18 (Hoeffding [1963]). Let X 1 , . . . , X n ∈ [0, R] be independent bounded random variables. Let X = 1 n n i=1 X i be their average. Then Lemma 19 (Tropp [2012], Theorem 1.1). Let X 1 , . . . , X n be a sequence of independent positive semi-definite random matrices in dimension d such that X i ≤ R almost surely (where · denotes the operator norm). Let X = n i=1 X i be their sum. Let µ min = λ min ( E X) and µ max = λ max ( E X). Then we have Lemma 20. Suppose x 1 , . . . , x n ∼ D are i.i.d. drawn from a distribution D and x ⊤ i x i ≤ 1 almost surely. Let λ = λ min ( Ex∼D xx ⊤ ) > 0 be the smallest eigenvalue of the co-variance matrix. We have that Proof. Let Σ = Ex∼D xx ⊤ and y i = Σ −1/2 x i for all i ∈ [n]. Note that y i y ⊤ i ≤ λ −1 almost surely, and that Ey i y i y ⊤ i = I. Therefore, by Lemma 19, we have that Lemma 21. Suppose x 1 , . . . , x n ∼ D are i.i.d. drawn from a distribution D and x ⊤ i x i ≤ 1 almost surely. For any cutoff level λ > 0, with probability at least (1 − 2d exp − λn 8 ), we have that , so that I = P + P − . Observe that the eigenvalues of Ex∼D P + xx ⊤ P ⊤ + are greater or equal to λ when restricted to the space spanned by the P + . Therefore, by Lemma 20, we have that with probability at least (1 − d exp(−λn/8)), 1 n n i=1 (P + x i )(P + x i ) ⊤ 1 2 E x∼D P + xx ⊤ P ⊤ + .
Note that where the first term is 1 4 Ex∼D P + xx ⊤ P ⊤ + by (83), the second term is a sum of positive semidefinite matrices, and for the third term, by Lemma 19, with probability is at least (1−d exp(−λn/3), we have that Therefore, continuing with (84), and collecting probabilities, we have that with probability at least (1 − 2d exp(−λn/8)), proving the lemma.
Lemma 22 (Vershynin [2018], Theorem 5.4.1). Let X 1 , . . . , X n ∈ R d×d be independent symmetric random matrices, such that E X i = 0 and X i ≤ R almost surely. Then Lemma 23. Let X 1 , . . . , X n ∈ R d×d be a sequence of i.i.d. positive semi-definite random matrices such that X i ≤ R almost surely. Let X = 1 n n i=1 X i be their average. Then we have Note that X i , X ≤ R almost surely, so Y i ≤ 2R/n almost surely. Furthermore, we have 4R 2 n 2 = 4R 2 n .
By Lemma 22, we have Lemma 24 (Abbasi-Yadkori et al. [2011], Theorems 1 and 2). Let {F i } ∞ i=0 be a filtration. Let {x i } ∞ i=1 be an R d -valued stochastic process such that x i is F i−1 -measurable and x i ≤ 1 almost surely. Let {ǫ i } ∞ i=1 be a real-valued stochastic process such that ε i is F i−1 -measurable and is sub-Gaussian with variance proxy 1 when conditioned on F i−1 . Fix θ ∈ R d such that θ ≤ 1. Let For every δ > 0, we have that where we define x Λ def = √ x ⊤ Λx. Furthermore, when the event specified in (85) holds, we have for every n ≥ 0 and any vector x ∈ R d that

A.2 Tools for Matrix Operations
Lemma 25 (Abbasi-Yadkori et al. [2011], Lemma 12). Given two positive semi-definite matrices A and B. Suppose that A B. Then we have that Lemma 26. Let A 0 be a positive semi-definite matrix. Suppose we are given a vector x ∈ R d such that x ⊤ A −1 x ≤ z, then we have zA xx ⊤ .

A.3 The Generalized Elliptical Potential Lemma
Below we prove a generalized version of the elliptical potential lemma. Compared to the usual version in literature (e.g., [Abbasi-Yadkori et al., 2011]), our versions works for positive semi-definite matrices X 1 , . . . , X n with traces upper bounded by 1 instead of just rank-1 positive semi-definite matrices. However, we also need the extra assumption that Tr X i V −1 0 ≤ 1 for all i ∈ [n].
Lemma 29 (Generalized Elliptical Potential Lemma). Suppose we are given a sequence positive semi-definite matrices X 1 , . . . , X n such that Tr(X i ) ≤ 1 for every i ∈ [n]. Let Λ 0 be a positive semi-definite matrix and let Λ i = Λ i−1 + X i for i ∈ [n]. When Tr X i V −1 0 ≤ 1 for i ∈ [n], we have n i=1 Tr X i Λ −1 i−1 ≤ 2 ln det Λ n det Λ 0 .

A.4 Pinsker's Inequality
Lemma 30. If P and Q are two probability distributions on a measurable space (X, Σ), then for any event A ∈ Σ, it holds that

B.2 Proof of Lemma 1 (Analysis of Linear Regression)
Lemma 1 can be proved by a straightforward union bound over all stages and candidate arms, and the application of the following lemma.