Design of Experiments for Stochastic Contextual Linear Bandits
Year: 2022

Abstract:
In the stochastic linear contextual bandit setting there exist several minimax procedures for exploration with policies that are reactive to the data being acquired. In practice, there can be a significant engineering overhead to deploy these algorithms, especially when the dataset is collected in a distributed fashion or when a human in the loop is needed to implement a different policy. Exploring with a single non-reactive policy is beneficial in such cases. Assuming some batch contexts are available, we design a single stochastic policy to collect a good dataset from which a near-optimal policy can be extracted. We present a theoretical analysis as well as numerical experiments on both synthetic and real-world datasets.

heading: 1 Introduction
text: Many settings may substantially benefit from data-driven contextualized decision policies that optimize the desired expected outcome. Online machine learning methods like multi-armed bandits and reinforcement learning, that adaptively change interventions in response to outcomes in a closed loop process (see Figure 1a), may not yet be practical for all domains due to the expertise and infrastructure needed. However running an experiment with a fixed decision policy to identify a good personalized policy is likely to be both simple logistically (since currently such decision policies are often specified by hand) and more easily accepted, since many areas (education, healthcare, social sciences) commonly deploy experiments across a few conditions to find the best approach. For example, education startups, political campaigns, and governmental agencies can use email and
∗The first three authors contributed equally. The work was fully completed while Andrea Zanette was a PhD Candidate in the Institute for Computational and Mathematical Engineering at Stanford University. Future revision of this article will be made available at https://arxiv.org/abs/2107.09912.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
text messages to provide targeted information and opportunities, such as information to encourage vaccination, or tips to parents to support their child’s developmental stage. Such organizations are familiar with standard experimental design, and but generally lack the infrastructure for continuous online contextual MAB learning. Experiments that involve deploying a nonadaptive policy that fit in with standard workflows but enable data-efficient learning of contextualized policies might offer substantial benefits over AB testing or relying on other segmentation methods that may not directly optimize desired outcomes.
For these reasons, a key opportunity is to design static or nonadaptive policies that can be used to gather data to identify optimal contextualized decision policies. Indeed a fixed data collection strategy is practically desirable (1) whenever multiple agents collect data asynchronously and communication to update their policy is difficult or impossible, and (2) whenever changing the policy requires a significant overhead either in the engineering infrastructure or in the training of human personnel. Several prior papers limit the number of policy switches with minimal sample complexity impact (Han et al., 2020; Ruan et al., 2020; Ren et al., 2020; Bai et al., 2019; Wang et al., 2021). Motivated by the above settings, we look for a single, nonadaptive policy for data collection.
Setting and goal We consider the linear stochastic contextual bandit setting where each context s ∈ S is sampled from a distribution µ and a context-dependent action setAs is made available to the learner. The bandit instance is defined by a feature extractor φ(s, a) ∈ Rd and some unknown parameter θ? ∈ Rd. Upon choosing an action a ∈ As, the linear reward function r(s, a) = φ(s, a)>θ?+η is revealed to the learner corrupted by mean zero 1-subGaussian noise η. Our goal is to construct an exploration policy πe to gather a dataset, such that after that dataset is gathered, we can extract a near optimal policy π̂ from it. In particular, we want to minimize the number of exploration samples.
Perhaps surprisingly, there has been relatively little work on this setting. Prior work on exploration to quickly identify a near-optimal policy focuses on best-arm identification using adaptive policies that react to the observed rewards (Soare et al., 2014; Tao et al., 2018; Jedra and Proutiere, 2020) or design of experiments that produces a nonadaptive policy for data collection (Kiefer and Wolfowitz, 1960; Esfandiari et al., 2019; Lattimore and Szepesvari, 2020); both lines of work assume that a single, repeated context with unchanging action set is presented to the learner. In contrast we are interested in identifying near-optimal context-specific decision policies. The closest related work (Ruan et al., 2020) investigates our task as a subtask for online regret learning, but requires an amount of data that scales as Ω(d16), which is impractical in applications with even moderate d.2
Without any apriori information, no algorithm can do much better than deploying a random policy, which can require an amount of data that scales exponentially in d, see appendix G.1. However, in many common applications, prior data about the context distribution µ(s) and the state–action feature representation φ is available. For example, an organization will often know information about its customers and specify the feature representation used for state–action spaces in advance.3 The initially available state contexts are referred to as offline (state) contexts data.
Our algorithm leverages historical context data to enable data efficient design of experiments for stochastic linear contextual bandits. It uses offline context-only data C to design a nonadaptive policy πe to collect new, online data where reward feedback is observed (see Figure 1b), and uses the resulting dataset D′ to learn a near-optimal on average decision policy π̂ for future use. We highlight that the algorithm does not get to adjust the exploratory policy πe while the online data is being collected.
Contributions We make the following contributions.
• Using past state contexts only, we design a single, nonadaptive policy to acquire online data that can be used to compute a context-dependent decision policy that is near-optimal in expectation across the contexts with high probability, for future use. • To identify an -optimal policy, our algorithm achieves the minimax lower bound Ω(min{d log ∑ sAs, d2)}/ 2) on the number of online samples (ignoring log and constants),
while keeping the number of offline state contexts required polynomially small (O(d2/ 2) or O(d3/ 2)).
2Note that the number of offline data in (Ruan et al., 2020) is independent of 1/ . But for most of the practical settings, our bound d3/ 2 can be much smaller than d16.
3In other words, given a set of previously observed states s1, . . . , sM , and a known state–action representation φ, for any potential action a, we can compute the resulting representation φ(s, a).
• Our experiments on a simulation and on a learning to rank Yahoo dataset show our strategic design of experiments approach can learn better decision policies with less exploration data compared to standard static exploration strategies that fail to exploit structure.

heading: 2 Related Work
text: Most linear bandit papers focus on online regret. Research on sample complexity results has focused primarily on adaptive algorithms for non-contextual bandits with a simple or vectored action space (Soare et al., 2014; Tao et al., 2018; Xu et al., 2018; Fiez et al., 2019; Jedra and Proutiere, 2020; Degenne et al., 2020). Their sample complexity bounds depend on the suboptimality gap of the action set, and are therefore, instance-dependent. The design of experiments literature (Kiefer and Wolfowitz, 1960; Esfandiari et al., 2019; Lattimore and Szepesvari, 2020; Ruan et al., 2020) has also focused on non-contextual bandits, but in designing a non-adaptive policy such that the resulting dataset can be used to identify an optimal arm with high probability.
A few recent papers consider learning the optimal policy for contextual bandits in the pure exploration setting (Deshmukh et al., 2018; Ruan et al., 2020). Deshmukh et al. (2018) propose an algorithm that yields an online reactive policy for when the reward is generated by a RKHS function on the input space: in contrast we focus on nonadaptive policies for linear contextual bandits.
There has been recent interest in reward-free reinforcement learning in Markov decision processes (e.g. (Jin et al., 2020; Wang et al., 2020a)). This work is focused on online adaptive policies. Jin et al. (2020)’s algorithm is similar in structure to our’s and could likely be adapted to the offline, bandit setting, but they focus on tabular domains. Note for simple contextual multi-armed bandits (tabular states, no shared structure, Jin et al.’s setting with H=1), a good strategy in the non-adaptive setting is to simply sample actions uniformly; indeed this is optimal given the lack of shared information between state-actions. No sophisticated algorithm is needed in that case.
For linear bandits, the closest reward-free work we are aware of is work on RL with linear function approximationWang et al. (2020a). While their algorithm can be specialized to the linear bandit setting and modified to match our algorithm by using offline data, the theoretical analysis would need to be very different from that in(Wang et al., 2020b)’s paper (and thus it would not yield the results presented in our paper). A key challenge in our case is to compute a non-adaptive policy for gathering data and be able to ensure the covariance matrix of the resulting data will be very similar to the covariance matrix that could result by a simulated adaptive policy. This issue does not arise in (Wang et al., 2020b) because they focus on reactive policies.4
The most related paper to this work is by Ruan et al. (2020). The main focus of Ruan et al. (2020) is to minimize the number of policy switches in the online phase while keeping the expected regret optimal. Directly applying Theorem 6 of Ruan et al. (2020) yields a Õ(d2/ 2) online sample complexity and Õ(d16) offline sample complexity. Their offline sample complexity is independent of . As a trade-off, Ruan et al. (2020) have a highly suboptimal dependence on d, which leads to burnin phase too large to be practically useful; their algorithm also suffers from a high computational complexity. Note their work is focused on a different objective than our’s.
4In particular, we will shortly introduce a planner-sampler two stage algorithm. We decouple the planner from the sampler to identify a non-reactive policy. Due to the decoupling, the planner needs to accurately predict what will happen when the sampler is run. To ensure this, a key challenge is to ensure that the planner inverse covariance matrix is very similar to the sampler inverse covariance matrix.

heading: 3 Setup
text: We consider the stochastic linear contextual bandit model with stochastic contexts. A bandit instance is characterized by a tuple 〈S,A, µ, r〉 where S is the context space and µ is the context distribution. For a context s ∈ S , the action space is denoted by As. The feature map φ : (s, a) 7→ φ(s, a) ∈ Rd is assumed to be known and defines the linear reward model r(s, a) = φ(s, a)>θ? + η for some θ? ∈ Rd parameter and some mean-zero 1-subgaussian random variable η.
We occasionally use the Õ notation to suppress polylog factors of the input parameters d, λ, 1δ . We write f . g if f = O(g), and f / g if f = Õ(g). We say f = Ω(g) if there exists a positive constant c such that f ≥ cg. For a positive semi-definite matrix Σ ∈ Rd×d and a vector x ∈ Rd, let ‖x‖Σ = √ x>Σx. For two symmetric matrices A,B, we say A 4 B if B − A is positive semi-definite.
Our analysis consists of an offline and online component. We often add ′ to indicate the online quantities, e.g., we denote with s1, s2, . . . the offline contexts and with s′1, s ′ 2, . . . the online contexts.

heading: 3.1 Objective and Error Decomposition
text: As depicted in Figure 1, our approach is to leverage offline state contexts C = {s1, . . . , sM} where sm ∼ µ to design a single stochastic policy πe to acquire data from an online data stream C′ = {s′1, . . . , s′N}. This generates a dataset D′ = {(s′n, a′n, r′n)}n=1,...,N where s′n ∼ µ, a′n ∼ πe(s′n) and r′n = r(s ′ n, a ′ n). Using D′, the least-square predictor θ̂ and the corresponding greedy policy π̂ can be extracted
θ̂ = ( Σ′N )−1 N∑
i=1
φ(s′n, a ′ n)r ′ n, π̂(s) = arg max a∈As φ(s, a)>θ̂ (1)
where Σ′N = (∑N n=1 φ(s ′ n, a ′ n)φ(s ′ n, a ′ n) >+λregI ) is the empirical cumulative covariance matrix with regularization level λreg . The quality of the dataset D′ (and of the whole two-step procedure) is measured by the suboptimality of the extracted policy π̂ obtained after data collection:
Es∼µ[max a
φ(s, a)>θ? − φ(s, π̂(s))>θ?]. (2)
Note that Eq. (2) measures the expectation over the contexts of the suboptimality between the resulting decision policy π̂ and the optimal policy. This is a looser criteria than a maximum norm bound which evaluates the error over any possible context s: in general this latter error may not be easily reduced if certain directions in feature space are rarely available.
A related objective is to minimize the maximum prediction error on the linear bandit instance. By least square regression analyses (Lattimore and Szepesvári, 2020), with probability at least 1− δ we have
Es∼µ max a |φ(s, a)>(θ? − θ̂)| ≤
√ β Es∼µ max
a ‖φ(s, a)‖(Σ′N )−1 , (3)
where √ β = min {√ 2 ln 2| ∑ s As|+ ln 1
δ︸ ︷︷ ︸ Small ∑ sAs
, 2 √ 2d ln 6 + ln 1
δ︸ ︷︷ ︸ Large ∑ sAs
} + √ λreg‖θ?‖2︸ ︷︷ ︸
Regularization Effect
. (4)
The above expression assumes that the state-action-rewards (s′n, a ′ n, r ′ n) are drawn i.i.d. from a fixed distribution. This is satisfied in our setting as the data-collection policy πe is nonadaptive to the online data. The parameter β governs the sample complexity as a function of the size of the state-action space and also highlights the impact of the regularization bias.
Small predictive error (Eq. (3)) can be used to bound the suboptimal gap of the greedy policy (Eq. (2)). Therefore to obtain good performance, it is sufficient to bound Es∼µ maxa ‖φ(s, a)‖(Σ′N )−1 . This can be achieved by designing an appropriate sampling policy πe to yield a set of (s′n, a ′ n, r ′ n) tuples whose empirical cumulative covariance matrix Σ ′ N is as ‘large’ as possible.

heading: 4 Algorithms
text: Reward-free LINUCB First, assume it is acceptable to have an algorithm that updates its policy reactively. In order to reduce Es∼µ maxa ‖φ(s, a)‖(Σ′n)−1 we could use an algorithm that, every time a context s ∼ µ is observed, chooses the action arg maxa∈As ‖φ(s, a)‖(Σ′n)−1 where the norm ‖φ(s, a)‖(Σ′n)−1 that represents the uncertainty is highest (cf. section 3.1). Such procedure is related (although not identical) to the well known globally optimal design of experiment applied to linear bandits (i.e., Lattimore and Szepesvari (2020)). Algorithmically, it corresponds to running the LINUCB algorithm (Abbasi-Yadkori et al., 2011) with the empirical reward function set to zero. In other words, the planner is essentially an offline, reward-free version of LINUCB. We emphasize that the associated non-stationary policy is generated offline and is not actively played. One can show that after≈ d2/ 2 iterations the uncertainty
√ β Es∼µ maxa ‖φ(s, a)‖(Σ′n)−1 ≤ ; if the algorithm stores
the observed reward r(s, a) in every visited context s and chosen action a, the greedy policy that can be extracted from this dataset (of size ≈ d2/ 2) is -optimal (cf. Eqs. (2),(3)), as desired. Unfortunately we cannot run this reward-free algorithm online, as its policy is reactive to the online stream of observed online contexts s and selected actions a, while we want a nonadaptive policy.
Algorithm 1 PLANNER (Reward-free LINUCB) 1: Input: Contexts C = {s1, . . . , sM}, reg. λreg 2: Σ1 = λregI 3: m = 1 4: for m = 1, 2, . . .M do 5: if det(Σm) > 2 det(Σm) or m = 1 then 6: m← m 7: Σm ← Σm 8: end if 9: Define πm : s 7→ arg maxa∈As ‖φ(s, a)‖Σ−1m 10: Σm+1 = Σm+αφmφ>m; φm = φ(sm, πm(sm)) 11: end for 12: return policy mixture πe of {π1, . . . , πM} Algorithm 2 SAMPLER 1: Input: πe = {π1, . . . , πM}, reg. λreg 2: Set D′ = ∅ 3: for n = 1, 2, . . . N do 4: Receive context s′n ∼ µ 5: Sample m ∈ [M ] uniformly at random 6: Select action a′n = πm(s ′ n) 7: Receive feedback reward r′n 8: Store feedback D′ = D′ ∪ {s′n, a′n, r′n} 9: end for 10: return dataset D′
Our algorithm leverages this idea and consists of two subroutines: 1) the planner (Alg. 1) which operates on offline contexts and identifies a mixture policy πe (this is the exploratory policy πe mentioned in the introduction) 2) the sampler (Alg. 2) which runs πe online to finally gather the dataset. This way, πe is nonadaptive to the online data.
Planner The purpose of the planner is to use past contexts to compute the exploratory policy. The planner runs the reward-free version of LINUCB on the offline context dataset C as described earlier in this section. This way, the planner selects the action a in the current offline context sm that maximizes the uncertainty encoded in ‖φ(sm, a)‖Σ−1m where Σm is a scaled, regularized, cumulative covariance over the contexts parsed so far and the actions selected. Note this procedure is possible since the state–action function φ(sm, a) is assumed to be known for any input (sm, a) pair, and no actual rewards are observed. The doubling schedule yields a short descriptor for the planner’s policies {π1, . . . , πM}. The variable m indicates the last doubling update before iteration m. A key choice is the parameter α ∈ (0, 1] in the cumulative covariance matrix update. The rationale is that when α < 1 each rank-one update φmφ>m to the cumulative covariance gets discounted. The smaller α is, the more offline samples the planner needs to get to a sufficiently positive definite covariance matrix ΣM . This choice effectively averages the updates and increases the estimation accuracy of the planner’s covariance with respect to its conditional expectation.
Sampler Upon termination, the planner identifies a sequence of policies π1, . . . , πM . Now consider the average policy πe: every time an action is needed, πe samples one index m ∈ [M ] uniformly at random and plays πm. This is the policy that the sampler (Alg. 2) implements for N = αM ≤ M fresh online contexts. Intuitively, executing the mixture policy πe in the online phase produces the same covariance matrix as ΣM (in expectation).
Upon playing πm in state s′n, the corresponding reward is observed and the tuple ({s′n, a′n, r′n}) is stored. Since πe is the average policy played by the planner, we expect that running πe on the online dataset produces a covariance matrix Σ′N similar to the planner’s ΣM . In a sense, the covariance matrix is a proxy for the amount of information acquired by the algorithm. This means the sampler acquires the same information that the planner would have acquired if it was acting online. Since the planner is the reward-free LINUCB algorithm, we expect its policy to efficiently reduce our uncertainty over the reward parameters and learn a near optimal policy; our analysis will make this intuition precise. Note the sampler’s policy is nonadaptive to the online stream of data.
Our work uses mixture policies; mixture policies are not essential, although they arise naturally from the way the algorithms are formulated.

heading: 5 Main Result
text: Theorem 1. Fix > 0, and consider running Alg. 1 for M = Ω̃( d 2β
λreg 2 ) iterations and Alg. 2 for
N = Ω̃(dβ 2 ) iterations with regularization λreg ∈ (Ω(ln(d/δ)), d]. Let θ̂, π̂ be as in Eq. (1). For any ≤ 1, with probability at least 1− δ the expected maximum uncertainty
Es∼µ max a∈As
|φ(s, a)>(θ? − θ̂)| ≤ (5)
and the suboptimality of the greedy policy π̂ satisfies
Es∼µ max a∈As
(φ(s, a)− φ(s, π̂(s)))> θ? ≤ 2 . (6)
In Table 1 we instantiate the bounds from Theorem 1 in different settings, ignoring constants and log terms. This highlights different tradeoffs between the regularization λreg and the number of offline contexts (M = N/α) needed to achieve the online minimax sample complexity lower bound ≈ min{d, ln ∑ s |As|} × d/ 2 (Chu et al., 2011; Abbasi-Yadkori et al., 2011). 5 In the large action
regime ln | ∑ sAs| ' d, a regularization level λreg ≈ d gives the optimal online sample complexity N ≈ d2/ 2 while requiring a context dataset of the same size (M ≈ d2/ 2, by choosing α = 1). More often, a lower level of regularization can be preferable to introduce less bias. For example λreg = 1 is a common choice in linear bandits (Abbasi-Yadkori et al., 2011; Chu et al., 2011). When the cumulative covariance matrix is less regularized, we may need to compensate with additional offline data to ensure the covariance matrices are accurately estimated, which is achieved by setting M = N/α ≈ dN (i.e., α ≈ 1/d). In this way, additional samples are collected by the planner to maintain its covariance estimation accuracy (and hence its planning accuracy) despite the lower regularization.
Note that our algorithm achieves optimal sample complexity for the online data. Even with adaptive policies, the best known minimax upper bound is d2/ (Abbasi-Yadkori et al., 2011; Chu et al., 2011). Although Chu et al. (2011); Abbasi-Yadkori et al. (2011) consider regret minimization instead of sample complexity. But their results can be easily translated to sample complexity bounds (See Lemma 3 in Appendix A.2, and also Jin et al. (2018, Section 3.1)). However, the optimal rate of the number of offline data is unclear. We believe our results can be improved by new tools in matrix concentration, and we leave this direction for future work. Interestingly, in our experiments the algorithm performed well numerically even when λreg < 1 and α = 1.
5The minimax lower bounds in the literature are stated for the regret setting, but can nonetheless be adapted to derive sample complexity results. See Appendix A.1 for detailed discussion.
More generally, the amount of regularization should be set following the classical bias-variance tradeoff; its choice is mostly a statistical learning question, and its optimal value is normally problem dependent. As a result, the problem dependent tradeoff between different values of λreg is not reflected in our minimax analyses but can be appreciated in our numerical experiments on the real world dataset.

heading: 6 Proof Sketch
text: We give a brief proof sketch where we ignore constants and log factors; the full analysis can be found in the appendix. First we introduce some notation. We define the scaled cumulative covariance ΣM at step m for the planner and the cumulative covariance Σ′n for the sampler at step n:
Σm = α m−1∑ j=1 φ(sj , aj)φ(sj , aj) > + λregI, Σ ′ n = n−1∑ j=1 φ(s′j , a ′ j)φ(s ′ j , a ′ j) > + λregI (7)
where the planner’s j actions is aj = πj(sj) and likewise the sampler’s j actions is a′j ∼ πe(s′j). Uncertainty Stochastic Process We represent the value of the uncertainty though a stochastic process. Let us define the filtration for the planner Fm = σ(s1, . . . , sm−1) at stage m and for the sampler F ′n = σ(s1, . . . , sM , s′1, . . . , s′n−1) at stage n to represent the amount of information available. Let us also define the observed uncertainty Um for the planner and likewise U ′n for the sampler:
Um def = max
a∈Asm ‖φ(sm, a)‖(Σm)−1 , U
′ n def = max a∈Asn ‖φ(s′n, a)‖(Σ′n)−1 . (8)
We ultimately want to bound E′n U ′n = E[U ′n | Fn] = Es∼µ maxa ‖φ(s, a)‖(Σ′n)−1 when n = N , i.e., the average uncertainty at the end, see Section 3. Likewise, let us define Em Um = E[Um | Fm] = Es∼µ maxa ‖φ(s, a)‖(Σm)−1 .
We show that E′N U ′N is minimized in two steps: 1) we show that the planner’s uncertainty EM UM can be bounded 2) since the sampler implements the planner’s average policy, E′N U ′N cannot be too far from EM UM . We highlight that M ≥ N in general, i.e., the stochastic processes proceed at different speed. In fact, the planner needs more data than the sampler (M ≥ N ) as the planner’s policy is reactive to the offline contexts; this forces us to use more data-intensive concentration inequalities for the planner.

heading: 6.1 Offline Uncertainty
text: The next lemma is formally presented in Lemma 5 and Lemma 7 in the appendix and examines the reduction in the planner’s expected uncertainty EM UM . Lemma 1 (Offline Expected Uncertainty). With high probability we have
EM UM ≤ 1
M M∑ m=1 Em Um / 1 M M∑ m=1 Um /
√ d
αM .
Proof sketch. We start by modifing a result from the classical bandit literature (e.g., Abbasi-Yadkori et al. (2011)) to bound the average realized uncertainty Um while accounting for the extra α scaling factor contained in the covariance matrix ΣM :
1
M M∑ m=1 Um = 1 M M∑ m=1 ‖φ(sm, am)‖Σ−1m / √ d αM .
The parameter α on the right hand side above arises from its inclusion in the definition of cumulative covariance Eq. 7. This justifies the last inequality in the lemma’s statement.
While we bounded 1M ∑M m=1 Um, we need to bound the average conditional expectations
1 M ∑M m=1 Em Um. Bernstein’s inequality would bound the actual deviation ∑M m=1 Um by the con-
ditional variances (or expectations ∑M m=1 Em Um given our boundness assumptions); here we need the opposite, and so we ‘reverse’ the inequality in Theorem 3 (Reverse Bernstein for Martingales) to claim ∑M m=1 Em Um / ∑M m=1 Um with high probability to conclude.

heading: 6.2 Online Uncertainty
text: In the prior section we showed that the planner would be successful in reducing its final uncertainty EM UM if it was collecting reward information; moreover, its sequence of policies π1, . . . , πM only depends on the observed contexts. Because of this, if the sampler runs the planner’s average policy πe, we would expect a similar reduction in the uncertainty E′N U ′N after N = αM iterations (the α factor simply arises because the planner’s information are discounted by α). The argument is formalized in Lemma 4 (Relations between Offline and Online Uncertainty) in the appendix, which we preview here. We let K be the number of policy switches by the sampler which is bounded by K / d in Lemma 16 (Number of Switches) in appendix. Lemma 2 (Relations between Offline and Online Uncertainty). If λreg = Ω(ln dδ ) and M = Ω ( KN λreg ln dNKλregδ ) , upon termination of Alg. 1 and 2 it holds with high probability that
E′N U ′N . EM UM .
Proof. Let d1, . . . , dM be the conditional distributions of the feature vectors sampled at timesteps 1, . . . ,M in Alg. 1 after the algorithm has terminated. Conditioned onFM , the di’s are non-random. Then the conditional expected covariance matrix given FM can be defined as
Σ = α M∑ i=1 Eφ∼di φφ> + λregI (9)
Now, our argument relies on some matrix concentration inequalities which hold if
λreg = Ω(ln d
δ ),
1 α = Ω
( K
λreg ln dNK λregδ
) . (10)
Precisely, from Lemma 14 (Matrix Upper Bound Offline Phase) and Lemma 15 (Matrix Upper Bound Online Phase) with high probability we have that
∀x, ‖x‖2 ≤ 1 : ‖x‖(Σ′N )−1 . ‖x‖Σ−1 and ‖x‖Σ−1 . ‖x‖Σ−1M . (11)
In words, we can relate the planner’s (random) scaled covariance ΣM to its conditional expectation Σ, with the guarantee that it won’t be very different from the sampler’s covariance Σ′N (which implements the planner’s policy). These concentration inequalities are key to the proof and are proved in the appendix.
Define the policy maximizing the online uncertainty π′n(s) = arg maxa∈As ‖φ(s, a)‖(Σ′n)−1 . Under the event in Eq. (11) we can write
E′N U ′N def = Es∼µ max
a∈As ‖φ(s, a)‖(Σ′N )−1 = Es∼µ ‖φ(s, π ′ N (s))‖(Σ′N )−1 . Es∼µ ‖φ(s, π ′ N (s))‖Σ−1
. Es∼µ ‖φ(s, π′N (s))‖Σ−1M ≤ Es∼µ maxa ‖φ(s, a)‖Σ−1M = EM UM .

heading: 6.3 Conclusion and Tradeoffs
text: We can now tune the parameters α, λreg . Starting from Eq. (3), we can write
Es∼µ max a
φ(s, a)>(θ? − θ̂) ≤ √ β E′N U ′N . √ β EM UM .
√ βd
αM =
√ βd
N . (12)
Thus, the rate-optimal online sample complexity N ≈ βd 2 always suffices. However, we need a different number of offline contexts depending on the regularization that we want to adopt. Since K / d, the reader can verify that if λreg ≈ d then the preconditions in Eq. (10) are verified with M ≈ N , so α ≈ 1. If a lower value for the regularization λ ≈ 1 is desired, M ≈ dN would be required (thus α ≈ 1d ). The reason why we might need M ≥ N (i.e., α ≤ 1) is that the planner’s policy is adaptive to the observed offline contexts. This means that the planner’s cumulative covariance ΣM is not a sum of i.i.d. rank-one random matrices; in this case, we need either a more data-hungry concentration inequality or heavier regularization, leading to the the precondtion on α in Eq. (10).

heading: 7 Experiments
text: We now study the empirical properties of the planner and sampler in a synthetic setting and a realworld dataset from the Yahoo! Learning to Rank challenge (Chapelle and Chang, 2011). We also analyze its sensitivity to regularization. Additional details are in the appendix.

heading: 7.1 Synthetic setting
text: We first conduct a synthetic validation experiment to verify our algorithms behave consistently with the intuition and theory previously described. We constructed a linear contextual bandit with d = 20 andA = {1, . . . , 10}. At each time, features were generated randomly through the following procedure. A category I is sampled uniformly from the set {1, 2, 3}. For actions a = 1, 2, 3 and categories i ∈ {1, 2, 3}, we defined diagonal covariance matrices Σa,i ∈ Rd×d such that Σa,i has a single coordinate (determined by the pair (a, i)) along the diagonal equal to 1 while others are equal to 10−9. Given the category I , features are distributed as φ(s, a) ∼ N (0,Σa,I). This ensures variance only in certain directions depending on the category sampled and action taken. Independent of the category, for actions a = 6, 7, features are distributed as φ(s, a) ∼ N (0,diag(10−9, . . . , 10−9, 5) independently. The last coordinate has large variance regardless of the other actions. Other actions yield features that are zero. The first d− 1 coordinates of θ were chosen randomly from {−1, 1}d−1 and the d-th coordinate is zero.
We considered four algorithms: (1) a random algorithm that chooses actions uniformly from A, (2) a largest norm algorithm that chooses the feature with the largest norm, (3) an algorithm that chooses action 1 and (4) our sampler-planner algorithm. The planner uses an independent contextonly dataset of the same size as the one to be used for training. All algorithms are then run in the online phase with reward feedback. The algorithms are evaluated based on their resulting policy values during the online phase on a held-out test set. Policy value is defined as Esφ(s, π̂(s))>θ? where π̂ is the learned policy for a given algorithm. All algorithms used λ = 1 and the planner used α = 1 as these worked well. See appendix for more λ settings.
Figure 2 shows the policy values plotted over the number of samples taken and also the action distributions of the algorithms. Each line/bar represents the mean/standard error of 20 trials. Most actions are designed to be uninformative in this setting and it is beneficial to select judiciously from actions {1, 2, 3, 6, 7}. A random algorithm should and does perform poorly.The largest norm algorithm also fails: while much is learned about the last coordinate of θ by typically taking actions {6, 7}, little is learned about the others which are necessary for making good decisions. Finally the single action algorithm fails to account for the categories.

heading: 7.2 Learning to rank dataset
text: We evaluate the planner-sampler performance on real-world data from the Yahoo! Learning to Rank challenge (Chapelle and Chang, 2011), which has been used previously (Foster et al., 2018).
The ranking dataset is structured as follows. Each datapoint (row) is a 700-dimensional feature vector associated with a ranking relevance score that takes on values in {0, 1, 2, 3, 4}. Each datapoint is also associated with a single context, termed a query. Multiple datapoints matched with the same query correspond to actions (documents) that the learner can choose when presented with that query. The dataset is already divided into training, validation, and testing data.
The objective is to choose actions, among those presented for a given query, that maximize the relevance scores. Unlike the previous synthetic dataset, the reward function here is misspecified, i.e., it does not exactly follow a linear model. To reduce the computational burden, we randomly subsampled coordinates of the original 700-dimensional features down to 300-dimensional features. We then normalized them to ensure the norms are at most 1. Similar to prior work, we also limit the number actions (documents) available at any given context to K = 20.
As before, we compare the planner-sampler pair to a random algorithm and a supervised learning oracle that observes all the context-action features and relevance scores, which is 200,000 training samples in total. To simulate streaming the data online to the algorithms, we sequentially iterate through the contexts and present the associated features to the learner as actions. During the offline phase, we run the planner on the validation set where none of the relevance scores are observed in order to generate the sampling policies. During the online phase, we run both the sampler and the random algorithm on the training data such that they observe the same contexts but may take different actions. The maximum number of distinct contexts we can iterate over is about 3000. The resulting policies are evaluated on the full test set after every 20 training ob-
servations. This experiment was repeated with varying values of the regularization parameter λ ∈ {0.1, 1, 10}. The planner uses α = 1; we did not find significant improvements with α < 1. Additional values for λ are reported in the supplementary material.
Each point/band on Figure 3 represents the mean/standard deviation of 10 independent trials. Randomness is due only to internal randomness in the algorithms and the randomized order in which the contexts are revealed. The sampler-planner outperforms the random algorithm in most regimes, including λ = 1 where the pinnacle performance of both algorithms is achieved. The gap between the algorithms is widened for larger choices of λ. For λ = 0.1 the curves appear to catch up as more data is gathered; it is possible that they would outperform a larger value of regularization if more samples were available. The optimal choice for λ depends on the bias-variance tradeoff. Despite misspecification, our sampler-planner approach consistently matches or significantly exceeds the performance of the baseline approach, particularly when the number of samples is small.

heading: 8 Conclusion
text: Assuming access to a set of offline contexts, we presents an algorithm to find a single stochastic policy to acquire data strategically. The procedure is validated by a theoretical analysis and by experiments, even when the reward model is not linear. In the future it would be interesting to create an algorithm that works across all values of regularization without impacting the amount of offline context data required, and to develop methods to incorporate prior reward data to reduce the sample complexity of the online data needed to learn a good policy, perhaps through instance-dependent bounds that quantify the benefit of particular prior context-action-reward data in a specific domain.
Our work presents little direct negative potential societal impacts though whether contextualized decision policies are beneficial or harmful depends on the setting and the reward function chosen.

heading: Acknowledgments
text: This work is supported in part by NSF Grant #2112926 and GFRP (to JL), and a Toyota gift.

Review summaries:
The authors propose a new setting for the stochastic contextual linear bandit problem: using past contexts only, design a non-reactive policy for future online data. They argue that this setting arises in practice since often it may be logistically too complicated to deploy an online machine learning algorithm. They measure the quality of the dataset by the performance of the greedy policy that uses the least-square predictor on the collected data in the online phase. They develop a new two-phase algorithm (a planner and a sampler) for this problem and provide sample complexity guarantees. They also demonstrate the performance of their algorithm empirically. 

[summary]  This paper considers the problem of efficient nonadaptive sampling to find the best bandit policy, given an offline context data is available. The authors propose an algorithm and provide its sample complexity analysis. Empirical results show the efficicay of the proposed method. 

This paper studies the experimental design for the contextual linear bandits. The goal of the problem is to collect a dataset for identifying a good policy (an estimation of the reward vector). This paper provides algorithms for their goal and theoretically analyzes the sample complexity. Experimental results are also provided.

This paper studies the setting where it is not possible (e.g. not allowed or difficult) to update a policy while it interacts with a system. The authors suggest to build, from a batch of historical contexts, an explorative policy, non-reactive, that is not updated online as it interacts with the system, to gather informative data that are finally used to build a near-optimal policy.  The explorative policy (Planner) consists in a mixture of policies built offline from the historical contexts so as to minimize the uncertainty. The main idea is that using this mixture of policies on the real system will also gather data so as to reduce the uncertainty.  Sample complexity bounds and bounds on the performance of the final policy are derived. The algorithm is also compared with other strategies in numerical experiments.