Design of Experiments for Stochastic Contextual Linear Bandits
Authors: Andrea Zanette
Kefan Dong
Jonathan Lee
Emma Brunskill
Venue: NeurIPS 2021 Poster (2021)
Keywords: Linear bandits
design of experiments
stochastic linear bandits

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.

Design of Experiments for Stochastic Contextual Linear Bandits
Andrea Zanette" EECS Department University of California, Berkeley Berkeley, CA zanette@berkaley. edu
Kefan Dong"
Jonathan Lee"
Department of Computer Science
Department of Computer Science
Stanford University
Stanford University
Stanford, CA kef aeefanddnsstaannn taaf ord. edu
Stanford, CA jn1 in1@stanfom edu
Emma Brunskill
Department of Computer Science
Stanford University Stanford, CA ebrunêcs stanford. edu
Abstract
In the stochastic linear contextual bandit setting there exist several minimax pro- cedures for exploration with policies that are reactive to the data being acquired. In practice, there can be a significant engineering overhead to deploy these algo- rithms, especially when the dataset is collected human in the loop is needed to implement a different policy. Exploring with sin- gle non-reactive policy is beneficial in such cases. Assuming some batch contexts are available, we design a single stochastic policy to collect good dataset from which near-optimal policy can extracted. We present a theoretical analysis as well numerical experiments both synthetic and real-world datasets.
distributed fashion or when a
1 Introduction
Many settings may substantially benefit from data-driven contextualized decision policies that opti- mize the desired expected outcome. Online machine learning methods like multi-armed bandits and reinforcement learning, that adaptively change interventions in response to outcomes in closed loop process (see Figure Lap. may not yet be practical for all domains due to the expertise and in- frastructure needed. However running experiment with fixed decision policy to identify good personalized policy is likely to be both simple logistically (since currently such decision policies 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. email and
For example, education startups, political campaigns, and governmental agencies
authors contributed equally. The work was fully completed while Andrea Zanette was PhD Candidate in the Institute for Computational and Mathematical Engineering at Stanford University. Future revision of this article will be made available at https: http:://axvvvvva/ org/ abs/
"The
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

text messages to provide targeted information and opportunities, such as information to encourage vaccination, or tips 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 practically desirable (1) whenever multiple agents collect data asynchronously and com- munication to update their policy is difficult or impossible, and (2) whenever changing the policy requires 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 complex- ity impact (Han et al. 2020 Ruan et al.) 2020, Ren et al. [0200] Bai et al.) 2019) Wang et al. (021)) Motivated by the above settings, we look for single, nonadaptive policy for data collection.
Setting and goal We consider the linear stochastic contextual bandit setting where each context 8 E S is sampled from distribution and a context-dependent action set A, is made available to the learner. The bandit instance defined by a feature extractor Φ(s, a) E Rd and some unknown param- eter 0* E IRd. Upon choosing an action a E As, the linear reward function r(s, a) = dbss, a) 0- + n is revealed to the learner corrupted by mean zero 1-subGaussian noise Our goal is to construct an exploration policy ne to gather 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 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 [Jdra and Proutiere, 2020) or design of experiments that produces a nonadaptive policy for data collection (Kiefer and Wol- fowitz, 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 are interested in identifying near-optimal context-specific decision policies. The closest related work (Ruan et al. (0200) investigates our task as subtask for online regret learning, but requires an amount of data that scales as ()d which is impractical in applications with even moderate df
Without any apriori information, no algorithm can do much better than deploying a random policy, which can require amount of data that scales exponentially in d. see appendix G.1 However, in many common applications, prior data about the context distribution ju(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 The initially available state contexts referred 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 nonadaptive policy Tee to collect new, online data where reward feedback is observed (see Figure [b], and uses the resulting dataset D' to learn near-optimal highlight that the algorithm does not get to adjust the exploratory policy ne while the online data is being collected.
average decision policy म for future use. We
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 compute context-dependent decision policy that is near-optimal in expectation across the contexts with high probability, for future use.
To identify an e-optimal policy, our algorithm achieves the minimax lower bound Ammin log E. Ae, (e)e) on the number of online samples (ignoring log and constants), while keeping the number of offline state contexts required polynomially small (O(22/2) or Odd /e)).
NNote that the number of offline data in (Ruan al. 2020 is independent of l/c. But for most of the practical settings, our bound d² /e2 can be much smaller than th
"I other words, given set of previously observed states $ SM. and a known state aatiinction representa- tion G. for any potential action a, can compute the resulting representation o(s, a).
2

---

(A Ann
Traditional online RL framework
(b) Design of experiment with online and offiine componcnt
Figure 1: Comparison between the traditional RL setting and design of experiments
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.
2
Related Work
Most linear bandit papers focus on online regret. Research on sample complexity results has focused primarily adaptive algorithms for non-contextual bandits with a simple vectored action space (Soare et al.] 2014 Tao et al., 2018: Xu et al.] 2018, Fiez et al. 2019 [Jdra and Proutiere] [2020] Degenne al. 2020). Their sample complexity bounds depend the suboptimality gap of the action set, and are therefore, instance-dependent. The design of experiments literature (Kiefer and Wolfowitz 1960 Esfandiari al. 2019; Lattimore and Szepesvari [020 Ruan al., (020) has also focused on non-contextual bandits, but in designing non-adaptive policy such that the resulting dataset can be used identify an optimal arm with high probability.
A few recent papers consider learning the optimal policy for contextual bandits in the pure ex- ploration setting (Deshmukh et al., 2018 Ruan al.) 2020). Deshmukh et al. (2018) propose 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 nonadaptive policies for linear contextual bandits.
There has been recent interest 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. 22200'ss algorithm is similar in structure to our's and could likely be adapted to the offline, bandit setting, but they focus tabular domains. Note for simple contextual multi-armed bandits (tabular states, no shared structure, Jin et al.'s setting with H=l), a good strategy the non-adaptive setting to simply sample actions uniformly; indeed this is optimal given the lack of shared information between acttinnc No sophisticated algorithm needed in that case.
For linear bandits, the closest reward-free work we are aware of is work on RL. with linear function approximatior Wang et al. (2020)). While their algorithm can be specialized the linear bandit setting and modified to match our algorithm by using offline data, the theoretical analysis would need to very different from that in (ann et al., (020bb 's paper (and thus it would not yield the results presented in our paper). A key challenge in case is to compute 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 simulated adaptive policy. This issue does not arise in (Wang et al. 2020b because they focus on reactive policies F
The most related paper to this work is by Ruan et al. (2020). The main focus Ruan et al. (2020) 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. 2200)) yields a Ö(d /e") online sample com- plexity and O6) offline sample complexity. Their offline sample complexity is independent of e. As trade-off, Ruan et al. (2020) have a highly suboptimal dependence on which leads burn- in phase too large to be practically useful; their algorithm also suffers from high computational complexity. Note their work is focused on a different objective than our's.
*In particular, we will shortly introduce planner-sampe two stage algorithm. We decouple the planner from the sampler to identify a nea-reaetive 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.

---

3 Setup
We consider the stochastic linear contextual bandit model with stochastic contexts. A bandit instance characterized by a tuple (S, A, r) where S is the context space and is the context distribution. For context & E S, the action space is denoted by A,. The feature map Φ : (8, a) + o(s, a) Rd assumed to be known and defines the linear reward model r(s, a) = Φ(s, a) 0+ + v) for some 0* _ parameter and some mean-zero I-subgaussian random variable 1).
We occasionally use the Ô notation suppress polylog factors of the input parameters d, A,A, We write f - 9 if f Ogg), and f Σ if f = Ögg). We say f = (hgg) if there exists positive constant e such that f 2 cg. For positive semi-definite matrix E Rdxd and a vector I' R",
let ||>/|= = Vx Lr. For two symmetric matrices A, B, we say A B if B - A is positive semi-definite.
Our analysis consists of an offline and online component. We often add to indicate the online quan- tities, e.g., denote with $1, $2.... the offline contexts and with s s2.... the online contexts.
3.1 Objective and Error Decomposition
As depicted in Figure I our approach is leverage offline state contexts {si..... .MM where ~ to design single stochastic policy to acquire data from an online data stream C" = {s] f NN). This generates dataset D' = {((s a/n, r))) where s jr, a/, ~ Te (s())) and r, = ((s),,')))) Using D', the least-square predictor and the corresponding greedy policy π can be extracted
N ØlS'n d')'''n
0 (E'N)~~1 Σ
((s) = arg max ((s, a) a aEA,
(1)
where y = Eww= o( d'))((s'n a/2) +>regl) +
is the empirical cumulative covariance matrix with regularization level Xreg- The quality of the dataset D' (and of the whole two-step procedure) measured by the suboptimality of the extracted policy मे obtained after data collection:
E Exppi [max ((s, a) 6 (s)) 8*).
Note that Eq. 22 measures the expectation over the contexts of the suboptimality between the result- ing decision policy से and the optimal policy. This is a looser criteria than a maximum norm bound which evaluates the eиror over any possible context s: in general this latter error may not be easily reduced certain directions 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 8 have
Eanp max
-0 s vB Bs-a max [|o (()c,)))
(3)
where
VB min
{
1 2 Σ Aol + In 8¹ 2 2d 6 + in 1
v >Dreg 110
(4)
Large E, A.
Rogularization Effect
Small Σ, A.
The above expression assumes that the Pate-action-reward (s/,, dh are drawn i.i.d. from a fixed distribution. This is satisfied in our setting as the data-collection policy is nonadaptive to the online data. The parameter 3 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. 33) can be used bound the suboptimal gap of the greedy Therefore to obtain good performance, it is sufficient to bound Egsy max, [|o(s, a) ()( This can be achieved by designing an appropriate sampling policy Te to yield a set of (6 2n rh) tuples whose empirical cumulative covariance matrix Σ is as
policy (Eq. (2).
'large" as possible.

---

4 Algorithms
Reward-free LINUCB First, assume it is acceptable to have algorithm that updates its policy reactively. In order to reduce Egzy max, [] (t,aa)llee ()(())))- we could use an algorithm that, every time a context 8 ~ f1 is observed, chooses the action arg ma [ d)llez,)- where the norm []o((, (EX))= 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 línear bandits (i.e., Lattimore and Szepesvari (2020)). Algorithmically, it corresponds to running the LIN- UCB algorithm (Abbasi- Yadkori 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 not actively played. One can show that after = d² /e² iterations the uncertainty v //Eer max, ||o(s, ())) S c; 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 = d² d²/c²) e-optimal (cf. Eqs. ( desired.
Unfortunately we cannot run this reward-free algorithm online, as its policy is reactive to the online stream of observed online contexts and selected actions a, while we want nonadaptive policy.
Algorithm PLANNER (Reward-free LINUCB)
1: Input: Contexts C = .M.....))....... reg. Areg
Algorithm SAMPLER
2: 2i = =Areg=
1: Input: Te = { TM) reg. Xreg
3: =1
2: Set D' 0)
4: for m = =1, 1.2,.... M do
3: for n ===11 1,,,,.....N do
5:
if dctt(Emm)) 2 det(Em) or = then
4: Receive context 8/ ~
6:
I + m
5: Sample m E [M] uniformly at random
7:
Σ Σm
6: Select action d', = Tm mm((
8:
end if
7: Receive feedback reward T
9:
Define Tm 8 arg max || a>lا>=
8: Store feedback D' DD (8% dn r
10: Em+1= = Em amm TT dm @(sm: Tm (5m))
9: end for
11: end for
return dataset D'
12: return policy mixture ne of { (TI...., TM)
Our algorithm leverages this idea and consists of two subroutines: 1) the planner (Alg. D which operates on offline contexts and identifies mixture policy Te (this is the exploratory policy ne mentioned in the introduction) 2) the sampler (Alg. [ which runs ae online to finally gather the dataset. This way, Te is nonadaptive to the online data.
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 the current offline context 8m that maximizes the uncertainty encoded in [|o(sm, a) |>ل where En is 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 {TI...., }.). }. The variable m indicates the last doubling update before iteration m.
Planner
A key choice is the parameter a E (0, 1] in the cumulative covariance matrix update. The rationale is that when a < 1 each rank-one update T to the cumulative covariance gets discounted. The smaller a is, the more offline samples the planner needs to get to a sufficiently positive definite covariance matrix EM.. 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 sequence of policies T....., TM. Now consider the average policy म. every time an action is needed, म. samples one index m E [M] uniformly at random and plays 7.- This is the policy that the sampler (Alg. ( implements for N aM < M fresh online contexts. Intuitively, executing the mixture policy ne in the online phase produces the same covariance matrix as EM (in expectation).
5

---

Sample Complexity Bounds
Small A.
Large
As
Large
2 A
Offline Data
M
/ (d
d=/e"
d²
Online Data
N Areg
Σ, [
d//c2
d2 12/12
Regularization
Table 1:
Sample complexity bounds (ignoring constants and log terms) to obtain an e-optimal policy
Upon playing Tm in state sy,, the corresponding reward is observed and the tuple (15', dn b is stored. Since We is the average policy played by the planner, expect that running Te the online dataset produces a covariance matrix Σny similar to the planner's ΣM- In a sense, the covariance matrix is 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 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.
Main Result
Theorem 1. Fix c O, and consider running Alg. for M = = >mug(z) iterations and Alg. 2 for
N = 2005 df) iterations with regularization Xreg E (2((m)d/5)) d). Let 0, â be as in Eq. 1 For
any 1, with probability at least 1 - 5 the expected maximum uncertainry
E Egwp max (o(x, a) ( (0 θ) S
(5)
nEA,
and the suboptimality of the greedy policy ā satisfies
Esnyy max (Ø(s, a) - ((s)) 0 s 2c. aEA,
(6)
In Table I we instantiate the bounds from Theorem in different settings, ignoring constants and log terms. This highlights different tradeoffs between the regularization Xreg and the number of offline contexts (M N/a) needed to achieve the online minimax sample complexity lower bound ao min In E. Ag x d/e² (Chu et al. 2011 Abbasi- Yadkori et al. (011)). In the large action regime In E. A.l & d, a regularizatio level Areg R= d gives the optimal online sample complexity 1).
N d2 while requiring context dataset of the same size (M de df/e², by choosing
More often, a lower level regularization can be preferable to introduce less bias. For example Xreg is common choice in linear bandits (Abbasi- Yadkori al.) 201T| 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
accurately estimated, which is achieved by setting M = N/a & dN (i.e., s 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 adap- tive policies, the best known minimax upper bound is dl Yubbasi-Yadkony et al. 2011 Chu et al., 2011). Although Chu et al. (20IT); Abbasi- Yadkori al. (2011) consider regret minimization in- stead of sample complexity. But their results can be easily translated to sample complexity bounds (See Lemma in Appendix A.2 and also JJin et al. (2018 Section 3.1)). However, the optimal rate of the number offline data is unclear. We believe our results can be improved by new tools in matrix concentration, and leave this direction for future work. Interestingly, in experiments the algorithm performed well numerically even when Xreg < and a =
'The minimax lower bounds in the literature are stated for the regret setting, but can nonetheless be adapted derive sample complexity results. See Appendix A. for detailed discussion.

---

More generally, the amount of regularization should be set following the classical tradeoff; its choice is mostly a statistical learning question, and its optimal value normally problem dependent. As result, the problem dependent tradeoff between different values of Xreg is not reflected our minimax analyses but can be appreciated in our numerical experiments on the real world dataset.
6
Proof Sketch
We give 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 EM step m for the planner and the cumulative covariance 2n for the sampler at step n:
m-
Em
E Ø( a(3),,))((55, + Aregt, j=1
Σn Σ E Ó( d()(s/,)) + Aee
(7)
where the planner's j actions is a, = (53)) and likewise the sampler's j actions is dj Te(s)).
Uncertainty Stochastic Process We represent the value of the uncertainty though stochastic pro- cess. Let us define the filtration for the planner Fm = a(s1..... $m-1) at stage m and for the sampler F, (8),....... SM, si,....... 11 at stage to represent the amount of information avail- able. Let us also define the observed uncertainty Um for the planner and likewise U", for the sampler:
Um
max oEA.
[1 a) ((E))) 1,
U
def
max aEA...
|10(5 ())(
(8)
We ultimately want to bound E", U" = E Fi] i... the average uncertainty at the end, see Section Likewise, let us define Em Um EIUmm
Egwy max, [|o(s, (s, a) ()(1) when N,
Fml E,n, max, [[o(s, a) ((E..)...
We show that Ey U is minimized in two steps: 1) we show that the planner's uncertainty Ey UM can be bounded 2) since the sampler implements the planner's average policy, F'y U/y cannot be too far from EM UM.
We highlight that M 2 N in general, i.c., the stochastic processes proceed at different speed. In fact, the planner needs more data than the sampler (M 2 NN) as the planner's policy is reactive to the offline contexts; this forces to use more data-intensive concentration inequalities for the planner.
6.1 Offline Uncertainty
The next lemma formally presented Lemma Jnnd and reduction in the planner's 's expected uncertainty EM UM- Lemma (Offline Expected Uncertainty). With high probability we have
Lemma 7 in the appendix and examines the
M
M
EM UM S
Σ m=1
Em
Um
Σ
Un
M
M
aM
Proof sketch. We start by modifing a result from the classical bandit literature (e.g., Abbasi-Yadkori al. (20TT) to bound the average realized uncertainty Um while accounting for the extra scaling factor contained in the covariance matrix ΣMi
M
M
d 11@(sm am All) 2 aM
Σ 1==1
Un
Σ
M
M
m=
The parameter a on the right hand side above arises from its inclusion in the definition of cumulative covariance Eq. This justifies the last inequality in the lemma's 's statement.
While we bounded M Em=z Un. need to bound the average conditional expectations X ΣM Em Um. Bernstein's 's inequality would bound the actual deviation Σm Um by the con- ditional variances (or expectations Em 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 Em Um $ SMM Um with high probability to conclude.
7

---

6.2 Online Uncertainty
In the prior section we showed that the planner would be successful in reducing its final uncertainty Ea UM if it was collecting reward information; moreover, its sequence of policies xi..... TMs only depends on the observed contexts. Because of this, if the sampler runs the planner's average policy we would expect similar reduction in the uncertainty Ex U after N aM iterations (the factor simply arises because the planner's information are discounted by o). The argument formalized in [emma [Relations between Offline and Online Uncertainty] in the appendix, which
we preview here. We let be the number of policy switches by the sampler which is bounded by K & d in in 16 Number of Switches in appendix.
Lemma 2 (Relations between Offline and Online Uncertainty). If Xveg 22(In f) and M
Ω
KNN In dNK upon termination of Alg. I and it holds with high probability that Avey Arey8)
E'y UN S EM UM-
Proof. Let di, d1...., ......dy. das be the conditional distributions of the feature vectors sampled at timesteps
1,..., M Alg. after the algorithm has terminated. Conditioned on FM. , the d; 's are non-random. Then the conditional expected covariance matrix given Fas can be defined
M
E
a
E Egnd oØ T + Areg
(9)
Now, our argument relies on some matrix concentration inequalities which hold if
Xveg 2(1 d 8 =
K Areg
dNK Xveg
In
(10)
Precisely, from Lemma 14 (Marrix Upper Bound Offiine Phasel and Lemma 13 Matrix Upper
Bound Online Phasel] with high probability we have that
Yz, ||>||| 1 1:
||>||(=))) 2 ||=||-- and || x
| (11)
In words, we can relate the planner's (random) scaled covariance EM to its conditional expectation Σ, with the guarantee that it won't be very different from the sampler's covariance 2n (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 -., (s) = arg max (lo(s, Under the event in Eq. (11)
write
E'y UNy def Egnu max [|oss, a))oo)))- = EaNg 1 x'y (5)()))) Eorn (lo(s, T'y (s)) aEA,
< E Egny (1o(s, 1' (s))
Eana max | a) a)m Es UM.
6.3 Conclusion and Tradeoffs
We can now tune the parameters a, Areg- Starting from Eq.
3). we can write
3d
Bd
Exnn max (ss, (0" - VBE UN S VBEM
UM S aM
V
(12)
N
Thus, the rate-optimal online sample complexity N different number of offline contexts depending on the regularization that we want to adopt. Since K E d, the reader can verify that if Xreg ss d then the preconditions in Eq. (TO) are verified with M ~ N, so a ze 1. If a lower value for the regularization = is desired, M = dN would be required (thus x A).
Rd 2
always suffices. However, need
The reason why we might need M 2 N (i.e., & S 1) is that the planner's policy adaptive to the observed offline contexts. This means that the planner's cumulative covariance ΣM is not sum of i.i.d. rank-one random matrices; in this case, we need either a more data-hungry concentration inequality heavier regularization, leading to the the precondtion on in Eq. (10).
8

---

7 Experiments
We now study the empirical properties of the planner and sampler in a synthetic setting and a real- world 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.
7.1
Synthetic setting
Algerithm Comparison
Nggrlttm Comparison
40
0.8
Randor
Fatg/
0.6-
frectueryy
0.4
20
Random
10
Norm
20
60
100
10
samples
(a)
(b)
Figure 2: Synthetic Setting, the left figure, the policy value of the campler-planne (S-P) compared with a random algorithm (Random), a largest norm algorithm (Norm), and an algorithm that always chooses the same single action (Single). Supervised learning (SL) represents an approximate upper bound; however, we don't 't expect the algorithms to be able to reach the SI. performance as they all receive handit feedhack compared the full feedback availahle SI. (10,000 samples). In the right figure, the empirical distributions over the actions chosen by the algorithms are compared, with the exception Single, which always chooses action 1.
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 and A {1,.... . 10). At each time, features were generated randomly through the following proce- dure. A category is sampled uniformly from the set {1, 2, 3). For actions a = 1, 2, 3 and categories i E {1, 2. 3). we defined diagonal covariance matrices Σg, E Rddd such that Σa, has a single co- ordinate (determined by the pair (a. i)) along the diagonal equal to while others are equal to 10-9. Given the category I, features are distributed as ø(s, a) ~ ~N(0, E..1). 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 dently. The last coordinate has large variance regardless of the other actions. Other actions yield features that are zero. The first d - coordinates of 0 were chosen randomly from 1- and the d-th coordinate is zero.
o0s, a) NO, diag(10 ..... 10 10-9, 5) indepen-
We considered four algorithms: (1) 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-p sampler-planner algorithm. The planner uses an independent context- only dataset of the same size as the one 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 held-out test set. Policy value is defined as E, 6, á (s)) T O* where स is the learned policy for given algorithm. All algorithms used À 1 and the planner used a as these worked well. See appendix for more À settings.
Figure D 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 0 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.
7.2 Learning to rank dataset
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, 2, 3. 4). Each datapoint is also associated with a single context, termed 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 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, iee. it does not exactly follow linear model. To reduce the computational burden, we randomly subsampled coordinates of the original 700- -i00nsnnnni features down to 500-dimensional features. We then normalized them 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 a random algorithm and a supervised learning ora- cle that observes all the context-action features and relevance scores, which is 200,000 training samples in total. To simulate streaming the data online the algorithms, we sequentially iterate through the contexts and present the associated features to the leamer 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 max- imum number of distinet contexts we can iterate over is about 3000. The resulting policies are evalu- ated on the full test set after every 20 training ob- servations. This experiment was repeated with varying values of the regularization parameter E {0.1, 1, 10}. The planner uses a = 1; we did not find significant improvements with a < 1. Additional values for are reported in the supplementary material.
Regularization Comparison
1.9
Relevance store
1.7
1.6
fand
SP1
Rand
1.5
500
1000
1500
2000
2500
3000
Online samples
Figure 3: The sampler-planner (S-P) pair is com- pared with random sampler (Rand) with varying levels of regularization A. The supervised learn- ing oracle (SL), which observes state-action pairs in the training set, is shown as baseline.
Each point/band on Figure 3 represents the mean/standard deviation of 10 independent trials. Ran- domness is due only to internal randomness in the algorithms and the randomized order in which the contexts are revealed. The sampler-planne 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 A. For = 0.1 the curves appear to catch up as more data is gathered; it is possible that they would outperform larger value of regularization if more samples were available. The optimal choice for A depends on the bias-variance tradcoff. De- sampler-planner approach consistently matches or significantly exceeds
spite misspecification, the performance of the baseline approach, particularly when the number of samples is small.
8 Conclusion
Assuming access to 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 good policy, perhaps through instance-dependent bounds that quantify the benefit of particular prior context-action-rewarr 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.
Acknowledgments
This work is supported in part by NSF Grant #21 #2112926 and GFRP (to JI.), and Toyota gift.
10

---

References
Abbasi-Yadkont Y., Pal. D., and Szepesvari, C. (2011). Improved algorithms for linear stochastic bandits. In Advunces Neural Information Processing Systems (NIPS).
Bai, Y., Xie, T., Jiang, N., and Wang. Y. X. (2019). Provably efficient q-learning with switching cost. Advances in Neural Information Processing Systems, 32.
Beygelzimer, A., Langford, J., Li, I.., Reyzin, I.,, and Schapire, R. (2011). Contextual handit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings.
Chapelle, O. and Chang, Y. (2011). Yahoo! learning rank challenge overview. In Proceedings of the learning to rank challenge, pages 24. PMLR.
Chu. W. Li, L., Reyzin, L., Schapire, R. (2011). Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statisticx, pages 208- 214. JMLR Workshop and Conference Proceedings.
Degenne, R., Ménard, P., Shang. X., and Valko, M. (2020). Gamification of pure exploration for linear bandits. In International Conference Machine Learning, pages 2432-2442. PMLR.
Deshmukh, A. A., Sharma, S., Cutler, J. W. Moldwin, M., and Scott, C. (2018). Simple regret minimization for contextual bandits. arXiv preprint arXiv:1810.07377
Esfandiari, H., Karbasi. A., Mehrabian, A., and Mirrokni, V. (2019). Regret bounds for batched bandits. arXiv preprint arXiv:1910.04959.
Fiez, T., Jain, I.., Jamieson, K., and Ratliff, I.. (2019). Sequential experimental design for transductive linear bandits. arXiv preprint urXiv:196.008300
Foster, D., Agarwal, A., Dudik, M., Luo, H., and Schapire, R. (2018). Practical contextual bandits with regression oracles. In International Conference Machine Learning, pages 1539-1548. PMLR.
Han, Y., Zhou, Z., Zhou, Z., Blanchet, J., Glynn, P. W., and Ye, Y. (2020). Sequential batch learning in Unite-action linear contextual bandits. arXiv preprint arXiv:2004.03321.
Jedra, and Proutiere, A. (2020). Optimal best-arm identification linear bandits. Advances in Neural Information Processing Systems, 33.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873.
Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, T. (2020). Reward-free exploration for reinforeement learning. In International Conference Machine Learning (ICML).
Kiefer, J. and Wolfowitz, J. (1960). The equivalence of extremum problems. Canadian Journal of Mathe- maticx, 12:363-366.
Lattimore, Szepesvári, (2020). Bandit Algorithms. Cambridge University Press.
Lattimore, T. and Szepesvari, C. (2020), Learning with good feature representations in bandits and in with a generative model. In International Conference on Machine Learning (ICML).
Mannor, S. and Tsitsiklis, J. N. (2004). The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 50mn):623-488.
Ren, Z., Zhou, Z., and Kalagnanam, J. R. (2020). Batched learning in generalized lincar contextual bandits with general decision sets. IEEE Control Systems Letters.
Ruan. Y. Yang, J., and Zhou. (2020). Linear bandits with limited adaptivity and learning distributional optimal design. arXiv preprint arXiv:2007.01990
Soare, M., Lazaric, A., and Munos, R. (2014). Best-arm identification in lincar bandits. In Advances Neural Information Processing Systems (NIPS), pages 828-836.
Tao, C., Blanco, S. and Zhou. Y. (2018). Best arm identification in linear bandits with linear dimension dependency. In International Conference Machine Learning, pages 4877-4886. PML..
11

---

Tropp. J. (2012). User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-434.
Wang. R., Du, S. S., Yang, I. F., and Salakhutdinov, R. R. (2020a). On reward-free reinforcement learning with linear function approximation. In Larochelle, H., Ranzato, M., Hadsell. R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems 33; Annual Conference Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual.
Wang, R., Salakhutdinov, R., and Yang. L. F. (20206). Provably efficient reinforcement learning with general value function approximation.
Wang, T., Zhou, D., and Gu, Q. (2021). Provably efficient reinforvement learning with linear function approx- imation under adaptivity constraints. arXiv preprint arXiv:2101.0211
L., Honda, J., and Sugiyama, (2018). fully adaptive algorithm pure exploration in linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 843-851. PMLR.
Zanelte, A., Cheng, C.-A., and Agarwal, A. (2021). Cautiously optimistic policy optimization exploration with linear function approximation. arXiv preprint arXiv:2103. 12923..
12


Reviews:
[{"review_id": "qBWTumINbw", "reviewer": "Reviewer_SJn5", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written. Although I didn't carefully check all the proofs, the theoretical results intuitively make sense to me. \n\nThe problem can be viewed as a reward-free exploration in linear contextual bandits. My main concern is regarding the significance of the problem studied, given existing work on reward-free RL, i.e., see Jin et al 2020, \"Reward-Free Exploration for Reinforcement Learning\" and many follow-up works (some of them also study the case with linear function approximation, e.g., Wang et al 2020, \"On reward-free reinforcement learning with linear function approximation\"). Since contextual bandit can be viewed as a special case of RL by setting horizon H=1, I wonder if the results presented in this paper can be directly obtained from these existing results. Discussions/comparisons with respect to reward-free RL are missing in the paper.\n\nAnother question is with respect to Ruan et al 2020. The author mentioned that similar results can be derived from their Thm 6 and offline complexity O(d^{16}). I agree that d^16 is high-suboptimal. However, it seems that the more important parameter is 1/\\epsilon. Their results completely get rid of dependence on 1/\\epsilon. Results derived in this paper have 1/\\epsilon^2 dependence, which looks suboptimal to me. \n\n====after rebuttal====\n\nI have read the rebuttal and would like to keep my score at 5. I suggest a major revision of the current submission to include a detailed discussion of the reward-free RL literature, e.g., what can be directly obtained from existing results and what are the new results in the current submission. Personally, I would not take the problem setting as a main/novel contribution of this paper due to its similarity to existing papers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See section 8.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "T1h6R0g4Xo2", "reviewer": "Reviewer_UR5r", "summary": "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.\n\nThe 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.\n\nSample complexity bounds and bounds on the performance of the final policy are derived. The algorithm is also compared with other strategies in numerical experiments.\n\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the setting studied by the authors is motivated by applications of policies in real life problems and such studies are missing from the literature. Therefore this could be a relevant contribution to the community.\n\nThe paper is well-written. Although the main ideas and algorithms are clear, some parts would benefit from more explanations, clarifications.\n\nMajor comments:\n- please clarify the objective in the introduction: minimize the number of samples required to achieve a tolerance error of $\\varepsilon$?\n- the authors say that they apply LinUCB with an empirical reward function set to 0. Although I understand the algorithm, I am not sure to understand the part about setting the empirical reward function to 0.\n- I would like the authors to elaborate on the necessity of using a mixture of policies.\n-line 167 \"in the presence of reward signal\": I am confused because the reward is not used here by the fixed policy, it is just stored to build $\\hat \\pi$. I think the important thing is that the policy is fixed and non-reactive. It could be reactive by using the contexts only. The sentence used by the authors appear to be misleading here.\n- Section 6: lots of typos, this section should be proof read. examples: through (line 201), at different speeds (line 211), missing or added $'$ at wrong places  (equation (9) and line 205), Lemma 2 (line 230).\n- Experiments: can the author define \"policy value\"? The description of the synthetic dataset (lines 265-274) is hard to follow/understand. When the authors write \"In category $i$, the action $a=i$\", does $i$ belong to $\\{1, 2, 3\\}$. In Figure 2.(b), action 6 and 7 appear important while from the explanations and the setup it seems to me it should be action 5 and 6. For the learning to rank experiments, except for S-P 10 the result does not appear to be significant compared to the random strategy given the error bars. How are the error bars defined?\n- Although the action space is state dependent $\\mathcal{A}_s$ in the introduction, is it assumed in the bounds that we in fact have a product $\\mathcal{S} \\times \\mathcal{A}$?\n- How does the bounds/results compare with a strategy that would be able to update a policy online? the reactive policy could use the rewards and thus explore and reduce uncertainty where it is potentially useful for the reward. Whereas here we explore so as to reduce a global uncertainty not in the important directions? I think this is briefly mentionned in the conclusion, where such reward information could be used additionally to the contexts.\n\nMinor comments:\n- There is an issue with the biblio. 2 papers appear twice in the references. The issue is coming from \"Szepesvári\" vs \"Szepesvari\"\n- line 35: a context-dependent action set $a \\in \\mathcal{A}_s$ -> although understandable this is not completely rigorous to put the $a$ here as you introduce a \"set\" in the text. please reformulate.\n- Introduction: $d$ and $\\epsilon$ are used at several places but are not defined.\n- section 3. please define $\\Omega$ notation.\n- line 134: please explain the uncertainty (related to the G criterion from optimal design literature: minimizes the worst possible predicted variance).\n- using both $\\pi_e$ and $\\pi_{mix}$ is confusing.\n- Theorem 1: $\\varepsilon$ should be defined at the beginning of the statement (\"Let $\\varepsilon \\leq 1$) as it is used in $M$ and $N$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "6xs_Lxw12yw", "reviewer": "Reviewer_tDzP", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think that the setting is original and is convincingly related to practice and I consider it a contribution in and of itself. The algorithm is interesting, especially the application of reward-free LinUCB in the planner phase. Section 6 is helpful and clarifies the main steps in the argument. The experiments demonstrate the usefulness of the algorithm.\n\nThe authors claim that the algorithm achieves the minimax lower bound on the number of online samples, but do not state a bound or give a reference for this. This would be helpful to clarify. It is also not clear whether the number of offline contexts is optimal. Can something be said about this? A discussion would be helpful.\n\nIt seems that while the planner never uses either the rewards or the actions available in the offline. A discussion might be helpful highlighting this. Is there any reason to believe that these could be used in an algorithm to achieve improved performance? In practice, does one ever have only the contexts and not the rewards or actions?\n\nAfter discussion: the algorithm seems useful, but the novelty of the setting and the technical contribution seem more limited than I originally thought. I think a detailed discussion of the connection to the reward-free RL literature would be helpful. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. They discuss using an algorithm that is robust to all values of regularization and the issue of the offline and online distributions potentially differing.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "4vEI_CJkli", "reviewer": "Reviewer_mozb", "summary": "[summary]\n\nThis 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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\nOriginality 4/5: I think the problem is novel.\n\nQuality 4/5: It's fine for the first paper on this problem.\n\nClarity 3/5: There are some typos in important places, but I am sure they are addressable.\n\nSignificance 3/5: this is hard to say, but I don't see an immediate clear application (see below for my comments)\n\nOverall, the problem is novel, but I'd like to see a more specific scenarios where it make sense. Otherwise, the contribution seems solid as a first solution on this problem, modulo some details as I describe below.\n\nI'd like to see a former argument on the lower bound. It's not immediately obvious how Chu'11 and Abbasi-Yadkori'11 would lead to the stated bound in line 179 (although I am convinced that the stated rate should be the right one).\n\nI'd like to see some discussions on the tightness of M >= d^3/\\eps^2 for small $S\\times A$. Is it a technical difficulty or is it unimprovable?\n\nPlease identify the actual application of the proposed problem. The proposed problem is not reward maximization but policy identification, so I don't think one would like to use it for recommendation systems becuase it will not maximize the cumulative reward. It will have to be like $\\epsilon$ greedy where one uses this sampler for $\\epsilon$ portion of the traffic. Otherwise, there are pure exploration problems like A/B testing.\n\nre: Eq (5).  consider the arm set consists of canonical vectors (e_1, ..., e_d) and when we pull arm $e_i$ like $N_i$ times and use the MLE to estimate $\\hat\\theta$. Consider that the context space is a singleton, so that $|S|\\times|A|=d$. Then, we have \n$$\\\\|\\hat\\theta-\\theta^*\\\\|^2_{\\Sigma} = \\sum_{i=1}^d N_i  (\\hat{\\theta}_i - \\theta^\\*_i)^2  \\lessapprox \\sum_i N_i \\frac{1}{N_i} = d$$\n, which I believe is not improvable. This seems to conflict Eq. (5) which implies that we should get $\\log(d)$ instead of $d$. \n\n* reading the proof in later sections, I realized that perhaps the LHS of Eq (5) is a typo, and in the derivation one should not apply the cauchy-schwarz in Eq. (3) & (4).\n\nThe description of $\\alpha$ is confusing because it was not explicitly defined in the main text (my apologies if I missed it). Although it was impilcitly mentioned in line 163, L155 says 'a key choice is the parameter $\\alpha$...', which will confuse readers.  Theorem 1 should also explicitly state what  $\\alpha$ one has to use.\n\n[minor comments]\n\n* why say 'nonreactive' rather than 'nonadaptive', which is the standard terminology..? \n* I would increase the resolution of Figure 1 for better readability.\n* L199: \\Sigma_M => \\Sigma_m??\n* L203: remove prime from U'_m\n* Proof of Theorem 1\n  * Eq (15): why do we have \\log(N) instead of \\sqrt{\\log(N)}??\n* experiments\n  * clarification: for each trial, the arms are drawn and then fixed throughout, right?\n  * L269-271: explanation here can be improved. It starts by 'in category i', but then it uses \\Sigma_1 in the normal distribution. I would assume that it was meant to be \\Sigma_i.\n  * please define `policy value' mathematically.\n* figure 2: (b) it sems like S-P would pull arm 6 and 7 for some time, but the description from the main text (L272) indicate that they should be 5 and 6. There seems to be a bug/typo here?\n\n----\n**after rebuttal**\nI am satisfied with the rebuttal. I will keep the score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the following variant of the linear contextual bandit problem: Given historical data, design a non-reactive policy that can be used on future gather data that can be used to learn a near-optimal policy. The reviews felt that the problem is well-motivated, and that the problem setting and techniques both have some novelty. However, concerns were raised regarding the overlap between the algorithmic ideas used here and in previous work on reward-free exploration in RL; this should be addressed in the final version of the paper.
Decision: Accept (Poster)