Experiment Planning with Function Approximation
Authors: Aldo Pacchiano
Jonathan Lee
Emma Brunskill
Venue: NeurIPS 2023 poster (2023)
Keywords: regret
model selection
planning
static
lower bound

Abstract: We study the problem of experiment planning with function approximation in contextual bandit problems. In settings where there is a significant overhead to deploying adaptive algorithms---for example, when the execution of the data collection policies is required to be distributed, or a human in the loop is needed to implement these policies---producing in advance a set of policies for data collection is paramount. We study the setting where a large dataset of contexts but not rewards is available and may be used by the learner to design an effective data collection strategy. Although when rewards are linear this problem has been well studied, results are still missing for more complex reward models. In this work we propose two experiment planning strategies compatible with function approximation. The first is an eluder planning and sampling procedure that can recover optimality guarantees depending on the eluder dimension of the reward function class. For the second, we show that a uniform sampler achieves competitive optimality rates in the setting where the number of actions is small. We finalize our results introducing a statistical gap fleshing out the fundamental differences between planning and adaptive learning and provide results for planning with model selection.

Experiment Planning with Function Approximation
Aldo Pacchiano Broad Institute & Boston University
Jonathan N. Lee Stanford University jul@stanford.edd
Emma Brunskill Stanford University ebrunêcs. stanford edu
spachhiebbraddnstiitee...m
Abstract
We study the problem of experiment planning with function approximation in contextual bandit problems. In settings where there is a significant overhead to deploying adaptive algorithms- example, when the execution of the data collection policies is required to be distributed, or human in the loop is needed to implement these
in advance a set of policies for data collection is paramount. We study the setting where a large dataset of contexts but not rewards is available and may be used by the learner design effective data collection strategy. Although when rewards are linear this problem has been well studied [ results still missing for more complex reward models. In this work we propose two experiment planning strategies compatible with function approximation. The first is eluder planning and sampling procedure that recover optimality guarantees depending on the eluder dimension (42) of the reward function class. For the second, show that uniform sampler achieves competitive optimality rates in the setting where the number of actions is small. We finalize our results introducing a statistical gap fleshing the fundamental differences between planning and adaptive learning and provide results for planning with model selection.
Introduction
Data-driven decision-making algorithms have achieved impressive empirical success in various domains such as online personalization [8 games [36 43 dialogue systems 32 and robotics 225
consider contextual information when making decisions. This recognition has sparked a growing interest in studying adaptive learning algorithms in the setting of contextual bandits 26 33 6 and reinforcement learning (RL) 46 Adaptive learning scenarios involve the deployment of data collection policies, where learners observe rewards or environment information and utilize this knowledge to shape subsequent data collection strategies. Nonetheless, the practical implementation of adaptive policies real- world experiments currently presents significant challenges. First, there is significant infrastructure requirements and associated overheads which require skills and resources many organizations lack. For example, while there end-user services that enable organizations to automatically send different text messages to different individuals, such services typically do not offer adaptive bandit algorithms. Second, the resulting reward signal may be significantly delayed. As an example, the effect of personalized health screening reminders on a patient making doctors appointments may take weeks. Therefore, while is increasingly recognized that there exist other settings where context- specific policies are likely to be beneficial, including behavioural science[8]. many organizations working in these settings may find it infeasible run experiments with adaptive policies. To bridge this gap, there is a need to explore the deployment of non-adapiin adaptive or static strategies that can effectively collect data with minimal or no updates. Surprisingly, limited research has been conducted to investigate this particular setting, highlighting the importance of further exploration in this area.
33 In many of these decision-making scenarios, it is often advantageous
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this work, we consider how to design a static experimental sampling strategy for contextual multi-armed bandit settings which, when executed, will yield dataset from which we can compute a near-optimal contextual policy (one with small simple regret). Our framework closely adheres to the experiment planning problem formulation originally introduced by [53]. The problem involves a learner interacting with a contextual bandit problem where the reward function is unknown. Our assumption is that the learner possesses a substantial offline dataset comprising of m sample contexts, none of which include reward information. The learner's objective is to utilize this data to design a static policy sequence of length T (where m > 7) that enables the collection of valuable reward information when deployed in the real world. The ultimate goal is to produce an almost optimal policy using the data gathered during deployment. To address this scenario, the authors of [+ propose a two-phase approach involving Planner and Sampler algorithms. In the planner phase, the learner employs the context data to generate a set of sampling policies, which are then utilized in the sampler phase. The primary focus of [53] lies in the analysis of the linear case, assuming the reward function to be a linear function of the context vectors. Their key algorithmic contribution is the linear Planner Algorithm, which encompasses a reward-free instance of LinUCB. The analysis presented in [53] demonstrates that the required number of samples under the static sampler to achieve an s-optimal policy (also referred to as simple regret) scales as O (df/ where d represents the dimension of the underlying space. This result matches the online minimax sample complexity for the simple regret problem
The algorithm proposed by [ effectively constructs a static policy sequence of adequate span, uti- lizing the linear structure of the problem. However, in many problem settings, lincarity alone may not be sufficient to capture the true nature of the underlying reward model. This limitation is particularly evident in scenarios such as genetic perturbation experimentation 44 other similar contexts. In such cases, the availability of algorithms that do not rely on linearity becomes crucial. Unfortunately, extending the results and techniques presented in is not straightforward.
the generic function approximation regime
Here we consider when the reward function is realized by unknown function f. belonging to known function class F (which can be more complex than linear).
Adaptive Learning with Function Approximation. In adaptive learning settings where a learner can change the data collection policies as it observes rewards and has much more flexibility than in experiment planning scenarios, various adaptive learning procedures compatible with generic function approximation have been proposed for contextual bandit problems. Among these, two significant methods relevant to our discussion are the Optimistic Least Squares algorithm (OptLS ) introduced by [42] and the SquareCB algorithm introduced by [I7]- Both of these methods offer guarantees for cumulative regret. Specifically, the cumulative regret of Opt.. scales as
(dydlluder lo)( while the cumulative regret of SquareCB scales as O (VI-A) [ (F))))
where A corresponds to the set of actions. The eluder dimensior I (deluder) is a statistical complexity measure introduced by [2], which enables deriving guarantees for adaptive learning algorithms based on the principle of optimism in the face of uncertainty in contextual bandits and reinforcement learning [ll [22] 37 9] By employing an muline-to-bated conversion strategy, these two methods imply that the number of samples required to achieve e-simple regret using an adaptive algorithm is at most O (deluder log( ())(( and O (IAA log(()))ee? respectively.
Contributions. In this paper, we address the function approximation setting within the contextual bandit (static) experiment planning problem. Although in experiment planning the data collection policies have to be produced before interacting with the environment, we establish that surprisingly the adaptive E-simple regret rates achieved by OptL. and SquareCB are also attainable by a static experiment sampling strategy. To achieve this, we introduce and analyze two experimental planning algorithms. The PlannerEluder algorithm (see Section 4 utilizes confidence intervals derived from least squares optimization to construct static set of policies be executed during the sampling phase. When the algorithm has access to a sufficient number of offline samples to generate T Z (deluder (og((())/s*)) static policies, the learner can produce an s-optimal policy denoted as कt thus matching the coline-to-batchh e-simple regret rates of OptLS. Since the eluder dimension of linear function classes of dimension d is uup to logarithmic factors- of order (d), our results
We formally introduce this quantity in Section Here we use simpler notation avoid confusion.
2

---

recover the linear experiment planning rates of [53] Additionally, in Section we demonstrate that collecting T S2 (I-A) log( (F)/=²) uniform samples sufficient obtain an e-optiaal policy Tr. This matches the online-to-batch e-simple regret rates of SquareCB. These two results yield conclusions similar to those known in the linear setting (53), but for general function classes.
These results prompt two important questions: (I) are existing adaptive cumulative regret algorithms already optimal for simple regret minimization, and (2) is static experiment planning sufficient to match the simple regret guarantees of adaptive learning for realizable contextual bandits?
we provide a negative answer to both questions. We present certain structured class of bandit problems where a different adaptive algorithm can require significantly less samples than that implied by the bounds from OptLS and SquareCB Our result is for the realizable setting 2
In Section 6
D1 where the true reward function f. belongs to a known function class F, where the true complexity of simple regret problems in adaptive learning scenarios has not be known known in this setting. This result complements recent results [2)) that mnline-to-batel strategies are suboptimal for minimizing simple regret in the agnostic contextual bandits setting 0
For the second question, our statistical lower bound shows that for this class of problems, a sig- nificantly smaller number of samples are needed to find an s-optimal policy when using adaptive learning, than when using a static policy. This result complements related work in reinforcement learning with realizable linear state-action value function approximation [52]
Finally, we address the problem model selection when the learner is presented with a family of reward function classes (Fi and is guaranteed that the true reward function f. belongs to F,,. where the index i, is unknown. We demonstrate that as long as 7 = Ω (IAA log M, [Fxx /)=²) uniform samples are available, is possible construct an e-optimal policy denoted as क.. Further details regarding these results can be found in Section 7
2 Further Related Work
Best Arm Identification and Design of Experiments. Previous work to efficiently produce an almost optimal policy for non-contextual linear and multi-armed bandits settings is based on best-arm identification procedures [16]
45 551. These are strategies that react adaptively to the collected rewards and achieve instance dependent sample complexity. Other papers in the design of 29,
20
13
4I introduce methods for designing a non-adaptive policy that can be used find an optimal arm with high probability in non-contextual scenarios.
experiments literature
[24] [5]
Safe Optimal Design. When safety concerns are imposed in the exploration policy, works such as [54] and 4 have studied the problem of producing safe and efficient static policy used to collect data that can then be used for policy evaluation the MAB and linear settings. This is in contrast with the unconstrained contextual function approximation scenario we study.
Reward Free Reinforcement Learning. In Reinforcement Learning settings a related line of research [21 50 I0 considers the problem of producing enough exploratory data to allow for policy optimization for all functions a reward class. These works allow for the learner to interact with the world for number of steps, enough collect data that will allow for zero-shot estimation of the optimal policy within a reward family. This stands in contrast with the experiment planning setup, where the objective is to produce sequence of policies for static deployment at test time with the objective of learning the unknown reward function.
3 Problem Definition
We study a two-phase interaction between learner and environment consisting of a Planning and a Sampling phase. During the planning phase the learner has access to m > T i.i.d. offline
"In the agnostic case the learner is instead presented with an arbitrary policy class 11 that may or may not be related to the mean reward function f.. In this setting a recent study by [44] introduces an algorithm that achieves sharp rates characterized in terms of quantity pn.

---

context sample from context distribution P supported context space A' as well as knowledge of reward function class where each element E JF has domain X' x A where the action set. During the sampling phase the learner interacts with a contextual bandit problem for T steps where at each time-step a context 2; ~ P revealed to the learner, the learner takes an action de and receives reward rt- We adopt the commonly used realizability assumption, which is widely employed in the contextual bandit literature 1
Assumption 3.1 (Realizabilitty. There exists a function f. F such that ri = fz at) + & where f. E F and & is a conditionally zero mean 1 1 subbaasssin random variable for all t E [T'] during the sampling phase.
During the planning phase the learner is required to build static policy sequence (T: (a policy a mapping from X' to A the set of distributions over actions) that, without knowledge of the reward, can be deployed to collect data during the sampling phase. In contrast with adaptive learning procedures, in the experiment planning problem the policies in {Te) have to be fully specified during the planning phase and cannot depend on the learner's observed reward values during the sampling phase. The learner's 's objective to use the reward data collected during the sampling phase to produce optimal policy रा such that,
Pa-Pa-rr (x) [f, a)] + max Bz-P,a (x.(xa))]
for suboptimality parameter E > 0. Because we have assumed realizability of the reward function, the optimal policy among all possible policies x. arg max, Ep-P,a><(s)) [ff. (z, a)] can be written as T. (x) arg max fx a) for all x X.
Throughout this work we make the following boundedness assumptions,
Assumption 3.2 (Bounded Function Range). The range of F is bounded, i.e. for all x, a X A. [f(z, a) & B for some constant B > 0.
Assumption 3.3 (Bounded Noise). The noise variables are bounded [Eel & B for all t e [T]
some constant B
Assumptions
3.2 and 3.3 imply [ry] < B + B for all E [T].
4 Planning Under the Eluder Dimension
The eluder dimension is a sequential notion of complexity for function classes that was originally introduced by [2]] The eluder dimension can be used bound the regret of optimistic least squares algorithms contextual bandits 42 [ and reinforcement learning (77] Informally speaking the eluder dimension is the length of the longest sequence of points one must observe to accurately estimate the function value at any other point. We use the eluder dimension definition from [42].
Definition 4.1. (E deedeeendence) Let 9 be scalar function class with domain and > 0. An element E Z c e-depnndent on {21.-.., ,Zn] C Z w.r.f. G if any pair of functions g. E g {² & also satisfies g(2) - g'(z) & E. Furthermore,
satisfying v VE- E>_((((z)) E- --idependentt of (z1.-.., 2nd w.r.t. G if it is not dedeendent on {21, (.n))
2 is
Definition 4.2. (8-eluder) The e- non monotone eluder dimension detuder (g, e) o is the length of the longest sequence of elements in 2 such that every element is e e-indeeendent of its predecessors. Moreover, we define the e-eluder dimension detuder (9,5) as (G, = max.' zs deluder (9, e).
By definition the e-eluder dimension increases as e is driven down zero. Let D be dataset of X, A pairs. For any f' with support X' x A we use the notation If - f''l to denote the data norm of the difference between functions ff and f":
1 - f
- (f(e,a)-f(zza))) (n.a)ED
Σ
V
'This assumption is based on the fact that gathering offline context samples can be significantly less costly compared to conducting multiple rounds of experimental deployment.

---

Algorithm EluderPlanner
1: Input: m > T samples (Ie P) function class F, confidence radius function By 1, R.
2: Initialize data buffer D =
3: for t== 1 ... do
4: For any X define the uncertainty radius of action a A as,
w(x, a, Di) s. 1tt.sl/ffllaa 1/-Pl
f(z,a) - f(
5: Define the policy as (T(x) = arg max w(x, D.) for all x X.
6: Update Di+1= D2 (x+)))
7: end for
The EluderPlanner algorithm takes as input m > i.i.d. samples from context distri- bution {æe Pl and a realizable function class F satisfying Assumption 3.T The learner iterates over I out of these samples in se- quential manner. We use the name Fe. to denote the f-th input sample and call na to the (de- terministic) exploration policies produced upon processing samples 1,....
Algorithm 2 Sampler
I: Input: number of time-steps T.
2: Initialize data buffer D Ø
3: for = .....
I do
4: Define deployment policy 7e as Tt.
5: Observe context ū; P.
6: Play action ài = (Tx) and receive re- ward Ft.
1. We use the notation D. = {(ze, Te(x)))) -- to denote the dataset composed of the first
7: Update Di+1 De u a(,
(ordered) samples from { and actions from policies (me)==]- We adopt the convention that D = Ø. The output of the EluderPlanner algorithm is the sequence of policies (m.))=1- Policy m. is defined as TT(I)) = arg max w(x, a, D.) such that w(x a, Dz) is uncertainty measure defined as,
8: end for
w(I, a, D.) 1.f'FF 15- (43)(1.)) f(z - f((z,)).
max
(1)
Where the confidence radius function (5 equals
[F] 8
3r(5,1) = C(B B)y log
for some universal constant C 0 defined in Proposition A.7 This is complexity radius im- plied by the guarantees of least squares regression (Lemma A.8p and constraints imposed by Lemma 4.6 See Appendix A. and Proposition A.7 for a detailed discussion about this defini- tion. We call the combination the PluderPlanner and Sampler as the eluder planning algorithm. Its performance guarantees obtained by relating the regret of constructed sequence of opti- mistic policies (#op6)7" Jt-1 based on the data collected by {m=)²=1 to the sum of uncertainty radii Ex, w(",, (1(r)), D.) of the context-actions collected during the planning phase. Using optimism when constructing this policy sequence is important. In contrast with the sequence of greedy policies greddy (.1xr) arg max fe(xz, a), where f. arg min JEF (r,, (fr a) - r)² resulting nt
from least squares over Dr, the sequence of optimistic policies satisfies regret bound. Thus, playing uniform policy from the sequence { JT_, satisfies simple regret guarantee. The sum of uncertainty radii ΣT= wxx, Te (It), D.) is bounded using Lemma borrow from M
Lemma 4.3. [Lemma from [9]] Let F be a function class satisfying Assumption with E-eluder dimension (etuder(F,s), For all T N and any dataset sequence {D:) with D, Ø and Dj (1Te, āt] of context-action pairs, the following inequality on the sum of the uncertainty radii holds,
T
w (Tr, āe, D.) & O (min BT, Bdetueter F,B/T) (x (T,5) 8) detuder (F,, B/TYT))
5

---

Extracting Policy रo from Data. At the end of the execution of the Sampler algorithm, the learner will have access to sequence of datasets {D 1=) of contexts, actions and reward triplets. The learner will use this sequence datasets to compute the sequence regression functions,
f arg min fEJ
2 (f(Ee, - 72)²²
(3)
Standard Least Squares (LS) results (see Lemma A.8) imply that 11 - fal & ((t, with high probability for all t E N. These confidence sets used to define sequence of optimistic (deterministic) policies ( J==1
7opt (x) = aig max
f(x,a) a)
max
asA
S.L f (t,
The candidate optimal policy का then defined as रा Uniform #1 . "
, *opt).
The main result
in this section is the following Theorem.
Theorem 4.4. Let
0. There exists a universal constant c O such that if
T max3( B, 1)dendder (F, B/T) log (1F1788)
(5)
22
then with probability least 1 the eluder planning algorithm's 's policy îo e-optimal.
Remark 4.5. The results of this section hold for the structured bandits setting 123 that is, scenarios where X' = }
Both sides the inequality defining T Theorem 4.4 depend on T. Provided detuder (F, FFBB/TT B) is sub- linear function of T, there exists finite value of I satisfying Equation 5 When deluder (F, 8)
deluder log (1/E) for some deluder and for all E > 0 setting > C maxx (B, B,
1. Dyderude (J Be) log( (ee)
enough guarantee the conditions of Theorem 4.4 are satisfied. Examples and from 12 show
the eluder dimension of linear or generalized linear function classes can be written in such way. In these cases dotuder is constant multiple of the underlying dimension of the space.
Using standard techniques, the results of Theorem 4.4 can be adapted to the case when the function class FF is infinite but admits metrization and has covering number. In this case the sample complexity will scale not with log([F)) but instead with the logarithm of the covering number of F. For example, in the l2 norm will scale as d, the ambient dimension of the space up to logarithmic factors of (see for example Lemma D.1 of [14] ). Plugging this into the sample guarantees of Theorem recovers the δ (d /E²) sample complexity for linear experiment planning from [53
of linear functions, the logarithm of the covering number of F under the
4.1 Proof Sketch of Theorem
Let ... .r be the sampler's context sequence. The proof works by showing that with probability (*)P*())) ()){_ sequence satisfies the regret bound
at least 1 - 8 the regret of the (
T Σ max (.,, (Tt, क. (G.)) & O ( B) deluder (F, B/T (og F(T/5) A
A key part of the proof involves relating the balls defined by the data norms of the planner datasets (D,)T_, and those induced by the data norms of the sampler datasets (D.)T=, The precise statement
of this relationship is provided in Lemma 4.6 and its proof can be found in Appendix C
Lemma 4.6. With probability at least 1
12a
((-f)) s.s. 1ff Ml,,, 23r ((S.)) s.t. III f'llD, & (t)
(6)
Simultaneously for all [T]. Where (De)T= is the dataset sequence resulting of the execution of FluderPlanner while { (De is the dataset sequence resulting of the execution of the Sampler and 85 t) is the confidence radius function defined in Equation 2

---

Let ft as in Equation and define & as the event where the Standard Least Squares results (see Lemma A.8) hold i.e. If fo B. 3, 8) for all E [2'] and also Equation 6 from Lemma 4.6
holds for all t [T]. The results of Lemmas A.8 and 4.6 4.6 imply P(E) 1
For context x and action let's denote by faia as function achieving the inner maximum in the definition of #1 (see Equation 4 When & holds the policies { are optimistic in the sense
(op (w) that ft 1 (I, =opt (a)) e max.eA fr a) and therefore,
max f. a) f. T.p aeA
20. (x) (Tx. t (+)) - fā -x)((())))
i
W
max f(e,, (5 (t,)) - f' #t (T=))
(.
[( म. (i.)) - ( 7, (+t)) = (+).
max ((,,D)
Where B,(r, if.f' E s.t. a consequence pn (x) .. E (2, when & holds since this case f-ll < 8r
s.t. llf -ff-f1l & (6, t)}. Inequality (i) follows by optimism, (ti)
and 1... Fr."""(() fills. < (t, 0), and (2it) follows because when & holds, Equation 6 Lemma 4.6
is satisfied and therefore (2, D.) = (4, Dr). The RHS (+) of theiequation above satisfies,
(+) 2 w 2opt (5t), $
max (Tt, a, De) aEA
w Te (Tt),
We relate the sum of uncertainty radii (wrtte क. (*,), DAY with those of the planner (wl (x)), Dol via Hoeffding Incquality (see Lemma A.1 and conclude that w.h.p.
Σ wwa m (m.)) D.) O (B (ByTTlog(1// (1/6))
max ()) f. #2 (3+)) (B:))
Lemma allows us to bound the sum of these uncertainty radii as
Σ wizz, (()) < O (min BT, Bdeluder Bde.ludde + detuder (F, (F,B/TTT)
and therefore w.h.p,
max (=(,, ff- 7,th (ā.)) & <0 (min [T, Bdatuder (F, B/T) (T(T, detaner (F, B/BT) A
Converting this cumulative regret bound into a simple regret one (Lemma B.I finalizes the result. A detailed version of the proof can be found in Appendix C.I
5 Uniform Sampling Strategies
In this section we show that a uniform sampling strategy can produce an E optimal policy with probability at least 8 after collecting O max"(B, Algl logl Fl/ed) samples. This procedure
achieves the same simple regret rate converting SquareCB 's cumulative regret into simple regre
In contrast with the eluder planning algorithm the uniform sampling strategy does not require planning phase. Instead it consists of running of the Sampler (Algorithm 2
setting मं Uniform(A))
for all j [T]. Given a dataset Dr of contexts, actions and rewards collected during the sampling phase, we solve the least squares problem:
Fr arg min fEF
Σ
(f( r2)
and define the policy कि as कo arg max A Fr(x,a) a). The main result of this section is,
"The regret bound of the SquareCB algorithm scales as O (v (VIAl log())))))))
7

---

Theorem 5.1. There exists a universal constant ē 0 such that if "_ (B, (B,B (og() then with probability at least the uniform planning algorithm's 's policy By is e e-optimal.
The proof of Theorem 5.1 can be found in Appendix D
Comparison Between OptLS and SquareCB. The regret rate after T' steps of the OptLS algo- rithm applied to contextual bandit problem with discrete function class F scale (up to logarithmic factors) as O (v
(v detuder (F, B/T)) log( F//o)T In contrast, the regret of the SquareCB algorithm
satisfies regret guarantee (up to logarithmic factors) of order (VIA) log([=1//8) where the eluder dimension dependence is substituted by polynomial dependence on the number of actions [A]. When the number of actions is small, even constant, the regret rate of SquareCB can be much smaller than that OptLS The opposite is true when the number of actions is large or infinite. Converting these cumulative regret bounds simple regret implies the number of samples required to produce an E optimal policy from the adaptive OptLS policy sequence scales as daluder B/T)) 18)()2"/ whereas for the adaptive SquareCB policy sequence it scales as [4 recover these rates the experiment planning setting.
The results of Theorems
Gap Between Experiment Planning and Adaptive Learning
The results of Sections and 5 imply planning bounds that are comparable to the corresponding online-to-balee botch guarantees for OptLS +p and SquareCB [77. The main result of this section Theorem 6. shows there are problems where the number of samples required for experiment planning can be substantially larger than the number of samples required of an adaptive learning algorithm. This result implies the suboptimality of algorithms such as SquareCB and OptL.S for adaptive learning.
In order to state our results we consider an action set Atree indexed by the nodes of height L binary tree defined here
as having L levels and 24 We call ay,: the i-th action of the 1-th level of the tree. For an example see Figure [ Let > 0. We define a function class Fuee indexed by paths from the root node to a leaf. For any such path { 02.6g. ,LLi the function f(P) equals,
nodes.
01,1
02,1
0,,2
if a = aL,o
(P)
1 2e
if E p\ Maaziz
03.1
03,2
03,3
03,4
12s
O.W.
Figure I: Binary Tree
The following result fleshes out a separation between planning and adaptive learning with action set Atree and function class Firee the setting where at time the learner will produce a guess for the optimal policy îि..
Theorem 6.1. Lets > 0, T N. Consider the action set Arree and function class Fuee and a reward noise process such that & 1N0, conditionally for all [T]. For any planning algorithm Alg there is function fa E Fure such that when T < get
22-5 and Alg interacts with f. then,
EAg., [Baat [f-(a)]]
max fa)
dE
Moreover, there an adaptive algorithm Algadaptive such that ifT 2L log(21/c)
Ellgadapiive
[En-ty [f(a)]] > max
f(a)
aEAuce
for all f f Frree. Where E NTe. I-] is the expectation over the randomness of Alg and the environment for target function f. and कe is the algorithm's final policy guess after the sampling phase.
'we obviate the I' dependence deluder for readability.

---

The main insight behind Theorem 6.1 is that adaptive strategies to find an optimal action in the Firee function class can make use of the conditional structure of the action space by trying to determine path of actions from the root to the leaf containing the optimal action. An adaptive strategy can determine this path by querying only nodes that are adjacent to In contrast, static experiment planning strategy cannot leverage this structure and has to query all leaf nodes. Theorem 6.1 implies gap between the adaptive and experiment planning problems. Moreover, since the eluder dimension of Fuee scales with 2 (see Lemma D.I OptLS and SquareCB are suboptimal adaptive algorithms for this model class. In contrast with the O
upper bound in Theorem 6.1 converting the
cummulative regret bounds of OptLS and SquareCB yield guarantees scaling as O 24 log Feree
7
Model Selection
In this section we consider a setting where the learner has access to Fi.... FM function (model) classes all with domain X' x A. The learner is promised there exists an index i, such that f. Fi.. The value of index i, is not known by the learner. We will show the uniform sampling strategy has sample complexity that scales logarithmically with the number of models and with the complexity of the optimal model class [. In this setting the Sampler will collect two uniform actions datasets (Dy (T(Traim) D(Test)) of size T/2 each. Using the "train" dataset Di D(Traiu) the learner computes
candidate reward models 7(0) for all E [M] by solving the least squares problems:
M
arg min feF.
Σ
a(),,,))-r. -
Using the "test" dataset the learner extracts guess for the optimal model class index by solving,
arg min ke[M]
Σ
( (1 a2)
(D
7 (xx a). Let's start by relating the The candidate policy कe is defined as (x(x) arg aa expected least squares loss of the candidate model P the size of the optimal model class [F.,)
Proposition 7.1. There exists universal constant >> 0 such that,
emax?
(m, (B, B) log(T max M, FF.
Ea-Paa- --
T
With probability at lest 5.
The proof of Proposition can be found in Appendix E.1 The uniform sampling model-sclection algorithm has the following performance guarantees,
Theorem 7.2. There exists universal constant č 0 s.t. ifT > C mmax² (B. log then with probability at least 8, the candidate policy कy of the uniform sampling model-selection algorithm is e optimal..
mast Maa(M.
2
Proof. Due to the realizability assumption (r; - fo ae) E.) the instantancous regret of रे on context E X' equals max, (a, a) fz (x)). Let n. (x) arg max f-(z, a). Just like in the proof of Theorem 5.1 (see Equation 25) we can relate the suboptimality of îor with the expected
least squares loss of f under the uniform policy,
Ex-P max aaA
-,, ((,,, I Pa Uniform(a)))
2 (IL(C,,)- (+ (z, a)
)
(8)
Finally Proposition
7.1 implies thre is universal constant e such that,
[ (1 )D (z, (o..a))) c( c(B² + B²) log max(M, (F.
Ex-P, Unifoo())))
T

---

with probability at least 1 - 8. Plugging this result back into Equation 8 Ty can be upper bounded as,
we see the suboptimality of
cB2 B²) log(T max (F..//)))
ExpP
max (1 - -+ (r())) & 2 aEA
T
Setting g(T) (LAI(B++B") log(T max M. 1//6)) Lemma A.6
implies there exists a universal
T
such that (TT) & e² for all T d max? (B, A)]A log Max(MM,17s.11
constant č
The results of Theorem 7.2 can be best understood by contrasting them to the uniform sampling algo- rithm with input model class equal the union of the function classes Fall FF Applying the results of Theorem 5.1 I to Fall yields sample complexity scaling with [MX log(1F).),
quantity that could be much larger than 1og([FF,) l). In contrast, the uniform sampling model-selection algorithm achieves sample complexity scaling with log ((F,,) at price logarithmic in the number of models classes M. This logarithmic dependence
M stands apart from model selection algorithms [38 [2 that
for cumulative regret scenarios such as Corral [ 39. ECE (30) and
instead have polynomial dependence nostic to the value of e. The results of Theorem 7.2 hold for any E. If e is known in advance the learner
M. The uniform sampling model-selection algorithm is ag-
can compute the model class index 7 arg min i [M]] s.t. T 3 ? (B, log((.F.1/56) and
e²
guarantees similar bounds to those of Theorem 7.2 Unfortunately in contrast with the uniform sampling model-sclection algorithm this method would be valid for single choice of E.
use the uniform sampling strategy for Fi- For this choice of e, Theorem 5.1
8 Conclusion
In this work we have introduced the first set of algorithms for the experiment planning problem for contextual bandits with general function approximation. We have developed the EluderPlanning algorithm that produces static policy sequence that after deployment can be used to recover an optimal policy. We showed it enough for the number of static policies and therefore samples during the sampling phase to be as large as the number of samples required from an adaptive procedure based on an online-to-batee conversion of the OptLS algorithm. Similarly we also demonstrated the uniform sampling strategy enjoys the same online-to coane-to-barte to--htchhbhhhhhte conversion sample complexity as the SquareCB algorithm. These results seemingly suggest that simple regret rates for adaptive learning may also be achieved in experiment planning scenarios. We show this is not the case. There exist structured bandit problems for which adaptive learning may require number of samples that is substantially smaller than the number of samples required by static policy sequence. This is significant because it implies the suboptimality of the rates achieved by existing adaptive learning algorithms such as OptLS and SquareCB and also because it draws clear distinction between adaptive learning and experiment planning. This implies these algorithms are either suboptimal or their upper bound analysis is not tight. We believe the first to be correct. This is an important open question we hope to see addressed in future research. We have also introduced the first model selection results for the experiment planning problem.
Many important questions remain regarding this setting. Chief among them to characterize the true statistical complexity of experimental design for contextual bandits with general function approximations. Our results indicate the eluder dimension is not the sharpest statistical complexity measure to characterize learning here. Developing more new form of complexity, as well as an accompanying algorithm that can achieve the true statistical lower bound for the problem of experiment planning remains an exciting and important open question to tackle in future research.
10

---

Acknowledgments and Disclosure of Funding
We thank Akshay Krishnamurthy for helpful discussions. Aldo Pacchiano would like to thank the support of the Eric and Wendy Schmidt Center at the Broad Institute of MIT and Harvard. This work was supported in part by funding from the Eric and Wendy Schmidt Center at the Broad Institute of MIT and Harvard. This work was supported in part by NSF grant #21 12926.
References
[1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2320, 2011.
[2] A. Agarwal, M. Dudík, S. Kale, J. Langford, and R. Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19-26. PMLR, 2012.
[3] A. Agarwal, D. Hsu, S. Kale, J. Langford, L. Li, and R. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
[4] A. Agarwal, S. Bird, M. Cozowicz, L. Hoang, J. Langford, S. Lee, J. Li, D. Melamed, G. Oshri, O. Ribas, et al. Making contextual decisions with low technical debt. arXiv preprint 1606::600.00366 2016.
[5] A. Agarwal, H. Luo, B. Neyshabur, and R. E. Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pages 12-38. PMLR, 2017.
[6] Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoff's. In International conference on machine learning, pages 127-135. PMLR, 2013.
[7] A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. Schapire. Contextual bandit algorithms the with supervised learning guarantees. In Proceedings of the Fourteenth International Confer-
on Artificial Intelligence and Statistics, pages 19-26 JMLR Workshop and Conference Proceedings, 2011.
[8] C. J. Bryan, E. Tipton, and D. S. Yeager. Behavioural science is unlikely to change the world without a heterogeneity revolution. Nature human behaviour, 5(8):980-989, 2021.
[9] J. Chan, A. Pacchiano, N. Tripuraneni, Y. S. Song, P. Bartlett, and M. I. Jordan. Parallelizing contextual bandits. arXiv preprint arXiv:2105. 10590, 2021.
[10] J. Chen, A. Modi, A. Krishnamurthy, N. Jiang, and A. Agarwal. On the statistical efficiency of reward-free exploration in non-linear rl. Advances in Neural Information Processing Systems, 35:20960-20973, 2022.
[11] W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214, 2011.
[12] A. Cutkosky, Dann, A. Das, Gentile, Pacchiano, and M. Purohit. Dynamic balancing for model selection in bandits and rl. In International Conference on Machine Learning, pages 2276-2283 PMLR, 2021.
[13] R. Degenne, P. Ménard, X. Shang, and M. Valko. Ganification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432-2442. PMLR, 2020.
[14] S. Du, S. M. Kakade, J. D. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization in rl. arXiv preprint arXiv:2103.1089) 2021.
[15] H. Esfandiari, A. Karbasi, A. Mehrabian, and V. Mirrokni. Regret bounds for batched bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7340-7348, 2021.
11

---

[16] T. Fiez, L. Jain, K. G. Jamieson, and L. Ratliff. Sequential experimental design for transductive linear bandits. Advances in neural information processing systems, 32, 2019.
[17] D. Foster and A. Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
[18] D. Foster, A. Agarwal, M. Dudik, H. Luo, and R. Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pages 1539-1548, PMLR, 2018.
[19] A. Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118. 1975.
[20] Y. Jedra and A. Proutiere. Optimal best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 1300077011117,, 2020.
[21] C. Jin, A. Krishnamurthy, M. Simchowitz, and T. Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870-4879, PMLR, 2020.
[22] C. Jin, Q Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficiett algorithms. Advances in neural information processing systems, 34: 13406-13418, 2021.
[23] K.-S. Jun and Zhang. Crush optimism with pessimism: Structured bandits beyond asymptotic optimality. Advances in Neural Information Processing Systems, 33:6366-6311 2020.
[24] Kiefer and J. Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[25] Kober, A. Bagnell, and J. Peters. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, 32(11): 2013.
[26] J. Langford and T. Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):66-1, 2007.
[27] T. Lattimore and R. Munos. Bounded regret for finite-armed structured bandits. Advances in Neural Information Processing Systems, 27, 2014.
[28) T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[29] T. Lattimore, Szepesvari, and G. Weisz. Learning with good feature representations in bandits and in rl with generative model. In International Conference on Machine Learning, pages 5662-5670. PMLR, 2020.
[30] J. Lec, A. Pacchiano, V. Muthukumar, W. Kong, and E. Brunskill. Online model selection for reinforcement learning with function approximation. International Conference on Artificial Intelligence and Statistics, pages 3340-3348 PMLR, 2021.
[31] G. P. Kamath, D. Foster, and N. Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 35:23737-23750, 2022.
[32] J. Li, W. Monroe, A. Ritter, M. Galley, J. Gao, and D. Jurafsky. Deep reinforcement learning for dialogue generation. arXiv preprint arXiv: 100.00544, 2016.
[33] L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670 2010.
[34] Li, L. Ratliff, K. G. Jamicson, L. Jain, et al. Instance-optimal pac algorithms for contextual bandits. Advances in Neural Information Processing Systems, 35:37590-37603 2022.
[35] T. P. Lillicrap, J. J. Hunt, A. Pritzel, Heess, T. Erez, Tassa, D. Silver, and Wierstra. Continuous control with deep reinforeement learning. arXiv preprint 17X1v1150..02971, 2015.
12

---

[36] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland. G. Ostrovski, et al. Human-level control through deep rein- forcement learning. nature, 518(7540):529 2015.
[37] I. Osband and B. Van Roy. Model- reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
[38] A. Pacchiano, C. Dann, C. Gentile, and Bartlett. Regret bound balancing and elimination for model selection in bandits and rl. arXiv preprint arXiv:2012. 13045, 2020.
[39] A. Pacchiano, M. Phan, Y. Abbasi Yadkori, A. Rao, J. Zimmert, T. Lattimore, and C. Szepesvari. Model selection in contextual stochastic bandit problems. Advances Neural Information Processing Systems, 33: 33:10328-1033 2020.
[40] A. Pacchiano, D. Wulsin, R. A. Barton, and L. Voloch. Neural design for genetic perturbation experiments. arXiv preprint arXiv:2207 12805, 2022.
[41] Y. Ruan, J. Yang, and Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 74-87, 2021.
[42] D. Russo and B. Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
[43] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser,
I. Antonoglou, V. Panneershelvam, M. Lanetot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016
[44] D. Simchi-Levi and Y. Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 2021.
[45] M. Soare, A. Lazaric, and R. Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
[46] R. S. Sutton. Introduction: The challenge of reinforcement learning. In Reinforcement Learning. pages 1-3. Springer, 1992.
[47] C. Tao, S. Blanco, and Y. Zhou. Best arm identification in linear bandits with linear dimension dependency. In International Conference on Machine Learning, pages 4877-4886. PMLR, 2018.
[48] A. Tewari and S. A. Murphy. From ads interventions: Contextual bandits in mobile health. Mobile Health: Sensors, Analytic Methods, and Applications, pages 495-517, 2017.
[49] R. Wan, B. Kveton, and R. Song. Safe exploration for efficient policy evaluation and comparison. In International Conference on Machine Learning, pages 22491-2222 225511. PMLR, 2022.
[50] R. Wang. S. S.S. Du, L. Yang, and R. Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 33: 17816-17826, 2020.
[51] L. Xu, Honda, and M. Sugiyama. A fully adaptive algorithm for pure exploration in linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 843-851. PMLR, 2018
[52] A. Zanette, Exponential lower bounds for batch reinforcement learning: Batch can be exponentially harder than online rl. In International Conference on Machine Learning, pages 12287-12297. PMLR, 2021.
[53] A. Zanette, Dong, J. N. Lee, and Brunskill. Design of experiments for stochastic contextual linear bandits. Advances in Neural Information Processing Systems, 34:22720-22731, 2021.
[54] R. Zhu and B. Kveton. Safe optimal design with applications in off-policy learning. In International Conference on Artificial Intelligence and Statistics, pages 2436-2447. PMLR, 2022.
13


Reviews:
[{"review_id": "ppr7S3hrwI", "reviewer": "Reviewer_aXBj", "summary": "We study the static experiment planning for policy learning problem in contextual bandits, with focus on the general realizable case. The paper first presents an algorithm using reward free, extending similar ideas in [37] and leveraging the  eluder dimension. The paper then shares a few theoretical results, including the competitive guarantee for uniform sampling policy, the gap between static and adaptive policies in a special case, and the results in model selection. \n", "questions": "1. It would be helpful to add outputs to your Algorithm tables\n2. In the main text, it would help to discuss the connection to [37] in terms of the reward-free emulation idea. \n3. \"Extracting Policy from Data\" - the intuition for this part is hard to understand. Why uniform sampling + optimistic, instead of just using the greedy (or pessimistic) policy? \n", "limitations": "Extensions to safe exploration and/or policy evaluation tasks would be meaningful and worthy some discussions. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is technically sound. \n* The writing is very clear.\n* The paper studies an important problem and the first proposed algorithm is useful.\n", "weaknesses": "Numerical results on the finite sample performance would be important to have. For example, although the asymptotic rate for uniform sampling is competitive and this fact might be surprising, it is expected that its finite-sample performance is worse. \n\nIt is also not fully clear how significant these theoretical findings are. For example, it is expected that there is some performance gap between adaptive and static policies, when the task is hard (though I appreciate formally proving it). \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "“Numerical results on the finite sample performance would be important to have” Although we wholeheartedly agree with the reviewer that an experimental evaluation of these algorithms would be of great interest, we consider the main contributions of this work to be theoretical. As such, and due to the plethora of results we have, we think adding additional content would obfuscate the main contributions of the current manuscript. We believe that a thorough empirical exploration of the problem of experiment planning with function approximation would be an important contribution in itself that we would love to see our work followed up by. One important roadblock that such work will have to overcome is that in general optimistic algorithms may be intractable under function approximation for general function classes. This is an exciting area of future research.\n\nThe reviewer raises a couple of good clarification points. If our work gets accepted at the conference we will make use of the extra space to better explain a few things. We will add a couple of explanations here to hopefully allay the reviewer’s concerns, we will add richer explanations in the final version of our manuscript. \n\n1. “It is also not fully clear how significant these theoretical findings are.” this is the first work to explore the setting of experiment planning with function approximation. We believe our manuscript has a couple of important results, for example a) Novel algorithms for Eluder Planning and Sampling and a thorough analysis of the Uniform Planner, B) the first lower bound drawing a gap between adaptive and static planning. We believe these contributions and in particular our lower bounds are of interest not only within the context of experiment planning but also more generally in the wider literature of bandits and reinforcement learning. \n\n2. “it would help to discuss the connection to [37] “ Our work subsumes that of [37] since in the linear case our Eluder Planner and Sampler procedures recover the same rates as [37]. We will make sure this is fully explained in the final version of our work. \n\n3. “Extracting Policy $\\hat{\\pi}_T$ from Data - the intuition for this part is hard to understand”. We prove the Eluder Sampler Planner procedure works by showing the simulated $\\widetilde \\pi_t^{\\mathrm{opt}}$ sequence (produced via optimistic evaluations) satisfies a regret bound. This implies that sampling a uniform policy can be used to turn this ‘online’ regret bound to a PAC guarantee. The same argument would not work under a greedy or pessimistic policy. This does not preclude it being possible to show either greedy or pessimistic policies would be appropriate choices, but it would require a whole set of different techniques to prove this. We agree this is an interesting follow up research question. \n\n4. “Extensions to safe exploration and/or policy evaluation tasks would be meaningful” The reviewer has identified another set of interesting follow up directions. The problem of experiment planning under constraints is an important and yet unexplored area of research. We would be really happy to see more research efforts being spent towards better understanding all facets of experiment planning.\n"}, {"review_id": "FlDPgOnVse", "reviewer": "Reviewer_qQSQ", "summary": "The study focuses on the experiment planning problem for contextual bandits with function approximation. \nThe paper gives two algorithms for the problem: (1) EluderPlanning algorithm whose sample complexity depends on the elder dimension of the function class and matches the sample complexity of OLS algorithm by a online-to-batch conversion.\n(2) It also suggest that simple uniform sampling is good when action space is small, and the sample complexity matches the SquareCB algorithm by online-to-batch conversion.\n\nThen, the paper suggest that there is an exponential gap between adaptive sampling and passive sampling (experimental planning) by finding a class of tree-structured function. Besides, for this class of function, the paper show that SquareCB and OLS (two adaptive sampling algorithm) have exponential large sample complexity while there exist an algorithm with reliability (called adaptive tree sampling in appendix) can achieve polynomial sample complexity in this tree-structured function class. This suggest the sub-optimality of SquareCB and OLS.\n\nFinally, address the problem of model selection when the learner is presented with a family of reward function classes and the true reward function is inside one of the reward function classes.", "questions": "(1) See weaknesses. If all problems can be correctly resolved, I would consider increasing the score.\n\n(2) There is a claim \"Our results indicate the eluder dimension is not the sharpest statistical complexity measure to characterize learning in this setting.\" in line 326, but I don't find any support to this claim.\n\n", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The tree-structured function class constructed in section 5 is interesting and elegant. \nWith this function class, the paper point out an exponential separation between adaptive sampling algorithm. \nAlso, it points out that in realisable setting, the online-to-batch conversion of SquareCB and OLS is suboptimal for simple regret minimization. ", "weaknesses": "(1) The proof of Lemma A.4 has a *major flaw*:\nin Line 439, it is not valid to choose $\\eta_t$ as a random variable that is dependent on the martingale difference sequence. \nThis is because the moment generating function (MGF) is required to derive lemma A.3 and thus also for lemma A.4.\nIt is valid only when the MGF coefficient $\\eta$ is a fixed value, which is also reflected in the claim of lemma A.3 (eta is fixed outside the probability bound). \nMore generally, MGF coefficient $\\eta$ can be a random variable that is independent of whole martingale difference sequence and then distribution of sum of martingale difference sequence is not affected by conditioning on $\\eta$.\n\n(2) Because of (1) and Lemma A.4 serves a fundamental step for most theoretical claims in appendix A, section 3 and section 6. All claims related to lemma A.4 may not be correct, including but not limited to Lemma A.5, Lemma A.7, Lemma A.8, Lemma 3.6, Theorem 3.4 and Proposition 6.1.\n\n(3) There are a few typos that would affect the understanding of the technical details.\n\n(4) Even if all claims can be corrected, the main contribution is not clean in the paper where too many issues are discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are extremely appreciative of the reviewer’s careful read of our manuscript. We are happy the reviewer identified the following strengths in our submission: this is the first work to explore the setting of experiment planning with function approximation and propose: a) Novel algorithms for Eluder Planning and Sampling and a thorough analysis of the Uniform Planner, B) the first lower bound drawing a gap between adaptive and static planning. We believe these contributions and in particular our lower bounds are of interest not only within the context of experiment planning but also more generally in the wider literature of bandits and reinforcement learning. The tree function class that forms the basis of our lower bound results shows how conditional structures embedded in adaptive learning problems are one of the components of what makes adaptive learning hard. The fact that existing adaptive learning algorithms based on for example the eluder dimension cannot give optimal rates in this example (as we show in this submission) implies the need for better more general algorithms for adaptive learning and a more complete treatment of the statistical complexity of this setting. We expect this insight to have wider consequences than what is contained in this submission. \n\nWe will now address the reviewer’s main concerns. We apologize for the source of confusion and will try our best to explain it. \n\nWe would like to start by noting the results of Lemma A.4 are true. An alternative proof of this results consists of modifying Theorem 2.2 from [“Bias no more: high probability data-dependent regret bounds for adversarial bandits and MDPs” ]. This result can be turned into an any-time bound by using a union bound over all $T \\in \\mathbb{N}$. Instead of applying the result with the probability level set to $\\delta$ we use $\\delta_T = \\frac{\\delta}{6*t^2}$. A union bound over all $T \\in \\mathbb{N}$ finalizes the result. \n\nThe misunderstanding regarding the correctness of this lemma is the result of us authors deciding to add a proof based on a support lemma (Lemma A.3) borrowed from Lemma 9 in the paper entitled “Taming the Monster: A fast and simple algorithm for contextual bandits”. In the notation from the Taming the monster paper, it was our understanding that this result was true uniformly over all lambda values (our eta) for any fixed delta. This is how the authors of the “Taming the monster” paper seem to use it in the proof of their Lemma 11. \n\nDue to the reviewer’s careful reading of our manuscript we dug deeper into the origins of Lemma A.3 (Lemma 9 in Taming the monster”) and discovered that in its original form (Beygelzimer et al. (2011) ), the result holds for a specific delta and gamma. Although this seems to imply the taming the monster paper has a slight error their results are still true. Had Lemma 9 in “taming the monster” held uniformly - as we initially thought-, we thought setting the eta value to a random variable to be well justified. As we have mentioned before there are many ways to fix this issue. As we have mentioned above in our case one way is to instead derive Lemma A.4 using a uniform version of Theorem 2.2 from “Bias no more”. An alternative proof avenue is by invoking the results from Howard [2018] “Time-uniform, nonparametric, nonasymptotic confidence sequences”, although using these methods require more technical jargon in the form of sub-psi processes that we wanted to avoid using in our manuscript. In the case of the “Taming the monster results”, we believe it is also possible to derive a uniform in lambda (our eta) version of Lemma 9 from that paper (our Lemma A.3) by taking a union bound over an exponential grid of the lambda space. It may be of interest to the community to make the authors of that work aware of this issue. \n\nWe again want to thank the reviewer for catching this and would really appreciate that in case this explanation has been found to be sufficient, if the reviewer could consider the technical merits of the remainder of the paper and raise their score if they think it to be appropriate. \n\nThe reviewer mentions the confusing nature of the claim “our results indicate eluder is not the sharpest statistical complexity measure to characterize learning in this setting”. In this case we were simply referring to the gap that exists between the eluder planner and sampler algorithms and the uniform sampling strategy. When the size of the action set is very small the uniform sampling strategy will yield a sharper upper bound than the eluder bound. A really exciting area of future research is to understand the tradeoffs that exist between these two settings and figuring whether there is a single algorithmic solution and a more nuanced notion of statistical complexity that can bridge the gap between them."}, {"review_id": "5ZEVV4dKU3", "reviewer": "Reviewer_ESHY", "summary": "The authors study the problem of planning for efficient data collection. Given initial data with a lot of contexts but no reward, the question is how do you devise a policy for data collection such that when executed in the real world, it learns the reward optimally to finally learn a policy with maximum rewards.\n\nThey propose two methods for it, i) eluder planning and a sampling procedure \nii) uniform sampler for the case when the number of actions is small", "questions": "Intuitively when is it possible to have $d_{eluder}(F, B/T)$ a sublinear function in T? \n\nI am not able to interpret theorem 4.1 properly, on what factors does $\\tilde{c}$ depends. Consider writing it as: let T be the smallest integer satisfying the $T\\geq....$, then \\for all $T' \\geq T$ $\\pi_{T'}$ is optimal?\n\nline 94,166: typos", "limitations": "no negative societal impact", "rating": 5, "confidence": 1, "soundness": 1, "presentation": 1, "contribution": 3, "strengths": "Proposed algorithms for experiment planning and theoretically analyze them. They also showed suboptimality of the existing adaptive learning algorithms which is interesting.\n\nLine 138-139, the intuition of the eluder dimension helps to understand its use case", "weaknesses": "The paper was hard for me to grab fully. Partially I lack background but majorly, I think it was the writing part. Some ideas to improve them:\n1) Either go with a short, vague intro or a precise long intro: currently, it is a long but vague intro since the problem setting was not defined early, and it becomes difficult to understand. I have seen theoretical papers which define problem statements in the intro, and then it's a precise long intro.\n\n2) Since you continuously refer to the sampling and planning phase, may be use a block diagram to represent them.\n\nIn general, I believe the writing style can be improved.\n\nSecondly, I was wondering if it would make sense to also add at least a preliminary experiment showcasing your theory? It is hard to get intuition on how tight the bounds are.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer’s comments. We will make sure the final version of our manuscript contains more detailed descriptions of the experiment planning setting early on in the introduction. We would like to remind the reviewer we are not the first to come up with this problem setting. The authors of [37] were the first to define the experiment planning problem. Our assumption is that drawing from the related literature while defining the problems we are studying is a valid choice. We will take the reviewer’s concern into account when writing the final version of this work and will make sure we carefully balance in our introduction the references to related work and what material to include in our own manuscript. We think the reviewer’s suggestion of including a block diagram showing the planning and sampling phases is a great idea. We will add a simple pictorial representation to the final version.\n\n\nAlthough we wholeheartedly agree with the reviewer that an experimental evaluation of these algorithms would be of great interest, we consider the main contributions of this work to be theoretical. As such, and due to the plethora of results we have, we think adding additional content would obfuscate the main contributions of the current manuscript. We believe that a thorough empirical exploration of the problem of experiment planning with function approximation would be an important contribution in itself that we would love to see our work followed up by. One important roadblock that such work will have to overcome is that in general optimistic algorithms may be intractable under function approximation for general function classes. This is an exciting area of future research.\n\nAnswers to miscellaneous questions\n\n\n1. “When is it possible to have $d_{\\mathrm{Eluder}}(F, B/T)$ to be a sublinear function in $T$?. In order to guarantee learnability the eluder dimension needs to scale sublinearly in $T$. This is the case for plethora of function classes such as linear classes and generalized linear models (where $d_{\\mathrm{Eluder}} (F, B/T) \\approx d \\log(B/T)$).\n\n2. “I am not able to interpret theorem 4.1 properly, on what factors does $\\tilde{c}$ depends”. We are somewhat confused at the reviewer’s comment here. The theorem statement specifies $\\widetilde{c}$ is a universal constant (i.e. independent of the algorithms, or function classes). The result simply states, if one wants to produce an $\\epsilon$-optimal policy $T \\geq $[expression in the paper] samples are sufficient. The expression to the right of $T$ is dependent only on $\\mathcal{F}, \\mathcal{A}, \\delta$ and $\\epsilon$. We would greatly appreciate if the reviewer could further expand on what aspect of this formulation is confusing. We would love to hear these to improve our work.\n\n"}, {"review_id": "xanH0hA0XW", "reviewer": "Reviewer_TWux", "summary": "The paper addresses the problem of experiment planning with function approximation in contextual bandit problems. \nIt is intended to solve the scenario that the datasets include a large amount of contexts while no rewards.\nThe authors propose two experiment planning strategies that are compatible with function approximation: an eluder planning and sampling procedure. The theoretical results guarantee that the policy converges to optimially under the time constrained by the eluder dimension.", "questions": "1. Is there a specific experiment to show the performance of the algorithm?", "limitations": "No. The paper could benefit from a more detailed discussion of the limitations of the proposed approach.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This algorithm achieves in this setting: the reward signal is not abundant while there are a large amount of the contexts. The uniform experiment planning algorithms help solve the setting. \n\nTwo important questions are answered in this problem:\n\n(1)are existing adaptive cumulative regret algorithms already optimal for simple regret minimization? \n\n(2) is static experiment planning sufficient to match the simple regret guarantees of adaptive learning for realizable contextual bandits?\n", "weaknesses": "1.The paper does not provide a detailed comparison with existing experiment planning algorithms to show the improvement of the algorithm, especially in the function approximation like linear function. Enough related works and comparisons are needed in this paper.\n\n2.The main results and the proof is lack of proof intuition to highlight the keypoint. The results need a clear and intuitive proof sketch to help readers follow the idea.\nThe results are lack of a lower bound to guarantee the optimality of the algorithm. A tight bound is needed. If not, the gap of the lower bound and the upper bound is needed to state.\n\n3.The paper could benefit from a more detailed discussion of the limitations of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for their comments. We would like to start by pushing back on the reviewers comment regarding the comparison with existing experiment planning algorithms (see Weaknesses issue 1). The setting of experiment planning was introduced first by [37]. The only existing results we are aware of are the linear algorithm of [37]. As we have explained in our manuscript, our eluder Planner and sampler algorithms recover and subsume the bounds of [37]. This is because the eluder dimension of a linear class agrees with the underlying dimension of the space. We will certainly add more explanation regarding this to the final version of the paper. \n\n“The main results and the proof is lack of proof intuition“ Thanks so much for pointing out useful suggestions on how to make our paper easier to read and understand by readers. We will make use of the extra page to make our explanations clearer to the reader.\n\n“The results are lack of a lower bound … “ we are somewhat baffled by this comment. Deriving lower bounds for the general function approximation regime is an extremely complex question. For example, such bounds are not fully understood for the setting of adaptive learning algorithms (bandits and RL), a vastly more developed area of research than the much more recently developed setting of experiment planning. We hope these has persuaded the reviewer that matching lower and upper bounds for the function approximation regime in experiment planning is an extremely unrealistic measuring rod and beyond the reasonable scope of a neurips submission. "}, {"review_id": "86b4c6F9GG", "reviewer": "Reviewer_xUKA", "summary": "The paper studies the problem of static experiment planning under the function approximation setting, which contrasts with the adaptive setting where the reward is not observable during the static planning phase. The paper proposes two static planning strategies: (1) EluderPlanner based on Eluder Dimension, and (2) Naive uniform sampler, and analyzes their regret, achieving a cumulative regret similar to the OLS and SquareCB algorithms in their adaptive counterparts.\n\nThe paper takes a step further by designing a special tree-structured function class that highlights the gap between the proposed static planning algorithms and the lower bound of adaptive learning in terms of regret.\n\nFinally, the paper addresses the problem of model selection and demonstrates the possibility of constructing an $\\varepsilon$-optimal policy.", "questions": "I am not familiar with Eluder dimension, but I find the construction of the function class in Section 5 extremely interesting. Will there be a similar gap for some of our familiar non-linear function classes, such as neural networks or kernel spaces, between static planning and adaptive learning?", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Clear motivation and good writing:\n- I enjoyed reading the motivational example in the introduction that explains why adaptive learning scenarios can be challenging.\n- All the problem setups and the relations with the related literature are clearly explained.\n- The structure of the paper is good and easy to follow.\n- Assumptions are well explained, and the definition of Eluder dimension is helpful.\n\nNovelty:\n- Combining Eluder dimension and static experiment planning appears to be a novel approach.\n- The lower bound construction in Section 5 is informative and demonstrates a fundamental gap between static planning and adaptive learning.\n\nTheoretical soundness:\n- I read through the main text, and all the derivations seem correct to me.", "weaknesses": "Related work on reward-free RL: I found reward-free RL to be closely related, especially [1], which also describes reward-free RL under function approximation. It would be good to have a short paragraph discussing reward-free RL in general.\n\n[1] Shuang Qiu, Jieping Ye, Zhaoran Wang, Zhuoran Yang. \"On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for their kind comments. A more in-depth discussion of the relationship between experiment planning and Reward-free RL is a great idea to improve our manuscript. We will use the extra page granted at camera ready time to achieve this. We will add the citation the reviewer has mentioned to the final version of our work. \n\n“Will there be a similar gap for some of our familiar non-linear function classes”. This is an extremely interesting question! We believe the conditional tree structured class can be embedded as a subclass of a linear or more complex kernel or NN class which would address this question. It is certainly a very interesting avenue for future research.\n"}]

Author rebuttal:

Meta-review: This paper studies experiment design with a general function approximation in the bandit setting. The design is a sequence of $T$ data logging policies, which are computed offline and then executed online. After I read all reviews, my overall perception of the paper was:

* **Theory:** The paper is quite theoretical and not easy to read. Intuitions for the proofs are missing.

* **Experiments:** None. While I understand that this is a theory paper, simple synthetic experiments would convince the reader that this paper can have impact on practice.

* **Lower bounds:** None. How else can we tell that the proposed solution is efficient?

On the top of this, the authors responded that lower bounds are hard and experiments are not needed. But how can we tell then that the algorithm design in this work is not highly suboptimal? To decide, I read the paper and my summary is below:

* **Section 3:** Eluder dimension with a known function class is used to design an experiment. A $T$-round static policy is computed in Algorithm 1 and executed in Algorithm 2. In Theorem 3.4, a well-known cumulative regret to simple regret reduction is used to get simple regret guarantees.

* **Section 4:** The same as Section 3 but with uniform sampling. At the end of the section, the authors argue that the proposed $T$-round policies are good, in the sense that a trivial cumulative regret to simple regret reduction applied to OLS and SquareUCB has the same guarantees.

* **Section 5:** A trivial cumulative regret to simple regret reduction applied to OLS and SquareUCB can be suboptimal.

* **Section 6:** Generalization to multiple function classes.

The main contribution of this work are non-adaptive policies with general function classes that are comparable to the adaptive ones, with a trivial cumulative regret to simple regret reduction. There are some obvious shortcomings:

* No comparison to any adaptive simple regret minimization algorithm from the best-arm identification (BAI) literature. This line of works started with [Best Arm Identification in Multi-Armed Bandits](http://certis.enpc.fr/~audibert/Mes%20articles/COLT10.pdf). The optimal rates in BAI are $\exp[- T]$ and there are also well-established lower bounds. Essentially all results in this work rely on a trivial cumulative regret to simple regret reduction, which is not optimal.

* Algorithm 1 is not computationally efficient unless the function class is simple (a finite set of known functions).

* The eluder dimension may not be the right metric. The reason is that adaptivity to rewards is clearly useful beyond linear models because their confidence intervals depend on the rewards, as in logistic models.

The authors also missed a few related works:

* [Safe Optimal Design with Applications in Off-Policy Learning](https://proceedings.mlr.press/v151/zhu22a.html)

* [Safe Exploration for Efficient Policy Evaluation and Comparison](https://proceedings.mlr.press/v162/wan22b.html)

Despite all shortcomings, I enjoyed reading this paper and support its acceptance. Please include all my suggestions in the next version of the paper.
Decision: Accept (poster)