Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity
Authors: Emmeran Johnson
Ciara Pike-Burke
Patrick Rebeschini
Venue: ICLR 2024 poster (2024)
Keywords: RL Theory
Low adaptive RL
Linear RL
Multi-Batch RL
Primary area: reinforcement learning
TL;DR: We show that dimension-dependent adaptivity is necessary for sample efficiency in linear RL.

Abstract: We theoretically explore the relationship between sample-efficiency and adaptivity in reinforcement learning. An algorithm is sample-efficient if it uses a number of queries $n$ to the environment that is polynomial in the dimension $d$ of the problem. Adaptivity refers to the frequency at which queries are sent and feedback is processed to update the querying strategy. To investigate this interplay, we employ a learning framework that allows sending queries in $K$ batches, with feedback being processed and queries updated after each batch. This model encompasses the whole adaptivity spectrum, ranging from non-adaptive `offline' ($K=1$) to fully adaptive ($K=n$) scenarios, and regimes in between. For the problems of policy evaluation and best-policy identification under $d$-dimensional linear function approximation, we establish $\Omega(\log \log d)$ lower bounds on the number of batches $K$ required for sample-efficient algorithms with $n = O(poly(d))$ queries. Our results show that just having adaptivity ($K>1$) does not necessarily guarantee sample-efficiency. Notably, the adaptivity-boundary for sample-efficiency is not between offline reinforcement learning ($K=1$), where sample-efficiency was known to not be possible, and adaptive settings. Instead, the boundary lies between different regimes of adaptivity and depends on the problem dimension.

Published as a conference paper at ICLR 2024
SAMPLE-EFRICIENCY IN MULTI-BATCH REINFORCE- MENT LEARNING: THE NEED FOR DIMENSION-
DEPENDENT ADAPTIVITY
Emmeran Johnson Ciara Pike-Burke
Department of Mathematics, Imperial College London, United Kingdom {emmeran. johnson17, c. tipkee-eie bikkeburke] imperial ac. uk
Patrick Rebeschini
Department of Statisties, University of Oxford, United Kingdom patrick.rebesccee weweschini@staateeeeee. ox. ac
ABSTRACT
We theorctically explore the relationship between sample-efficiena and adaptiv- ity in reinforcement learning. An algorithm is sample-efficient if it uses number queries n to the environment that is polynomial in the dimension d of the prob- lem. Adaptivity refers to the frequency at which queries sent and feedback is processed to update the querying strategy. To investigate this interplay, we employ learning framework that allows sending queries in K batches, with feedback be- ing processed and queries updated after each batch. This model encompasses the whole adaptivity spectrum, ranging from non non-adaptive 'offline' (K 1) fully adaptive (K = 71) scenarios, and regimes in between. For the problems of policy evaluation and best-policy identification under d-dimensional linear funetion ap- proximation, we establish Q(log log d) lower bounds on the number of batches K required for sample-efficient algorithms with n = Oppoy((d) queries. Our results show that just having adaptivity (K > 1) does not necessarily guarantee sample- efficiency. Notably, the haatiivtty-boundat for cumple-efficieng is not between offline reinforcement learning (K 1). where sample-efficiency was known not be possible, and adaptive settings. Instead, the boundary lies between different regimes of adaptivity and depends the problem dimension.
INTRODUCTION
Data collection in Reinforcement Learning (RL) usually falls into two main paradigms: online and offline. An online learner interacts with the environment, immediately receiving feedback and adapt- ing its decisions in real-time. In contrast in offline RI., the dataset is collected in single batch prior to observing any feedback. Many practical applications consider RL algorithms with limited adap- tivity, which fall between online and offline RL. For example, in clinical trials, groups of patients undergo multiple treatments simultancously and the treatment allocations are only be updated once the outcomes of the all the previous group have been observed (Yu et al. 2021). Similar settings with parallelized data-collection include marketing, advertising and numerical simulations (Esfan-) diari et al. 202T). There are also applications where the data collection needs to be validated prior to deployment by human due to concerns of safety (Dann et al.) 2019) and fairness (Koenecke al.) 2020), which with large scale data collection, is not feasible to have at every data point.
This motivates considering the multi-batch learning model (Perchet et al. 2015) where data-set of size n is collected in K batches, and feedback from within a batch is only observed at the end of batch. This means only data from previous batches be used select how the next batch is collected. This is also known as growing batch RL (Lange et al. 2012)). We refer to as multi-bateh RL to avoid any confusion with offline RL, also called batch RL, which considers single batch.
The multi-batch setting covers different levels of adaptivity to feedback, which refers to how fre- quently the learner can process feedback and use it update its data collection strategy. We measure

---

Published as a conference paper at ICLR 2024
it by the number of batches K. At one extreme, all the data is collected in a single batch (K 1, offline-RL. no adaptivity). At the other extreme, each batch contains a single data-point (K = n, full adaptivit We say learner is adaptive when K 1. In some of the applications that parallelize data-collection mentioned above, algorithms with low-adaptivity where K is as small as possible of interest since there may be cost associated to unifying and processing the parallelized data.
We study adaptivity in infinite-horiin horizon discounted Markov Decision Processes (MDPs). We focus on 1) the policy evaluation (PE) problem, where the learner is tasked with estimating the value of a target policy, and 2) the best policy identification (BPI) problem. where the learner is tasked with finding a near-optimal policy. desirable property of the learner that it is sample-efficien,, i.e. only needs a dataset size that is polynomial in the dimension of the problem (c.g. state space size). We aim to understand the minimum level of adaptivity necessary for sample efficient learning.
Linear Function Approximation: MDPs faced in practice often have state spaces S or action spaces A that are infinite or too large to handle directly (Silver et al. (016). Function approximation is used to reduce the learning problem to a smaller set of parameters that leverage structure in the problem. We consider a form of linear function approximation (Bellman et al.) 1963) that assumes the (action)-value of policy is linear combination of known features of the state-action pair with an unknown parameter, each of dimension d. The sample complexity of algorithms is then measured with respect to the smaller dimension d' instead of the dimensions of the MDP ((S),
Adaptive vs Non-Adaptive: It is known there is a sample-efficiency separation between offline RL (K' = 1) and fully-adaptive RL (K n) under linear function approximation. Algorithms have been shown to be sample-efficient in the assumptions in the offline setting (Duan et al. 2020 Xie & Jiang] 2020). Without assumptions in the offline setting, it has been shown information theoreetcclrrrrlllyyyooo that no sample-efficient algorithms can solve the PE or BPI problem (Zanette 202I) even under the best possible offline dataset, showing the separation. However, the MDP constructions of Zanette (202I) are easily solved with algorithms using K 2 batches (see proofs of their Theorems I and 3), suggesting that the boundary of this separation may be between offlin RL. (K" = 1) and RL with adaptivity (K" > 1). This motivates studying the values of K where sample-efficiens
setting (Lattimore et al.) (2200) and under various
not possible and asking the following questions:
Does the boundary of sample-efficienc, under linear function approximation lie between offline RL (K = 1) and RL with adaptivity (K 1)? If not, is the boundary dimension-ddependen!
In this paper, we establish an Mlog log d) lower-bound on the number of adaptive updates, K, required to solve both PE and BPI problems sample-efficiently. This answers the first question neg- atively and the second positively. This is achieved through non-trivial extension of the framework of (Zanette, 2021) for the offline setting to the multi-batch setting, which we describe next.
When faced with an unknown MDP within a known class of MDPs, we consider a learner over K rounds. In a round, the learner chooses a set of state-action queries with knowledge of the feedback from previous rounds. The following characteristics strengthen our lower bounds:
Learning Process:
Exact feedback: the feedback for a state-action query is the reward and transition functions, not a single sample. This makes query equivalent to observing infinite samples from the reward and transition functions if these are stochastic and removes any hardness due to uncertainty.
We consider two ways for the learner to specify the set of queries. The first (policy-induced) is through trajectories induced by chosen policies. The second (policy-free) explicitly specifies the state-action queries. Our results hold for any such set of queries whose size is polynomial in d. Realizability: the MDPs considered satisfy the linear representation of the action-values.
Tabular and horizooorizon MDPs and linear bandits are casily solved in the offline setting (K 1) under this framework but infinite- soniitehoriioon discounted MDPs are not (Zanette) (02I). Our work studies what happens beyond the offline setting (K > 1) for infinite-horizon discounted MDPs.
Contributions: Our results show that a number of batches K constant with respect to the dimension d is not enough to solve PE or BPI problems sample-effiiienlly Specifically, we show that if we restrict the total number of queries (over all batches) to be polynomial in d (sample-efficiency) then
Typically, online refers to setting with full- adal-adaptivity along a single trajectory (sequence of transitions from starting state, potentially with restarts). Our notion of full-adaptivity covers this, but is more general since we allow settings with generative model where samples from any state-action pair can he drawn.
2

---

Published as a conference paper at ICLR 2024
there are PE problems that require K = 2l log d) to be solved arbitrary accuracy. with only policy-free queries, there are PE and BPI problems that require (o log d) to be solved to arbitrary accuracy, even if all policies satisfy linear realizability of their action-values.
These results show that adaptivity (K > 1) does not guarantee sample-efficiency The level of adaptivity, or number of batches K, needed guarantee sample-efficiency scales with the dimension d of the linear representation. In particular, the boundary of sample-efficiency does not lie between offline RL (K 1) and adaptive RL (K > 1). Instead this boundary must lie within a regime of adaptivity scaling with dimension: 22(log log d) < K < n.
Interestingly, the class of MDPs considered in Zanette (2021) can be solved with d + queries and K = 2 batches (observing feedback from the first batch is enough to select queries in the second that fully solve the MDPs) (Zanette| (202T). Theorem 4]. Our results show that this is not possible in general and that the class of MDPs use for our results is fundamentally harder. From technical perspective, our work uses tools from the theory of subspace packing with chordal distance (Soleymani & Mahdavifar 202I). This enables the environment to erase information across multiple dimensions (m-dimensional subspaces, see Section (5) in response to queries, instead of a single direction as in Zanette 2021), which ultimately allows to achieve lower-bounde for K > 1.
PRELIMINARIES
Markov Decision Process (MDP) (Puterman, 1994) is a discrete-time stochastic process com- prised of set of states S, set of actions A bes((,,) where A, is the action space in state s E and, for each state-action pair (8, a) E A., next-state transition function given by measure p(-|s, a) and (deterministic) reward function r(s, a) E [-1,1] (in fact, even the value functions defined below are in [-1, 1] for our constructions). a state s, an agent chooses an action receives reward r(s, a) and transitions to new state according to a(-ls,a). Once in the new state, the process continues. The actions chosen by an agent are formalised by policies. A deter- ministic policy S A is mapping from state following policy chooses action (Ts) Ag. We do not consider stochastic policies.
action. In each state E S, an agent
In this work, for a discount factor 7 [0, 1), we consider 7-discounted infinite-horizon MDPs. We measure the performance of a policy π with respect to the value function V :S - IR,
(s) = Σ (rr(s,,,T())) (alss,((s) ((S))) =
where St, 0g are the state and action in time-step and the expectation with respect to the random- ness in the transitions. This is notion of long-term reward that describes the discounted rewards accumulated over future time-steps when following policy æ and starting in state s. We consider ? as fixed throughout. It is also useful to work with the action-value function Q" S A - R.
(=(,,a) = E Σ r/r(s,, (8))), 8,00
=a
which is similar to V", with the additional constraint of taking action a in the first time-step. For a policy æ, define the Bellman evaluation operator T for action-value functions as:
(T (s, r(s.a) a) + p((l [Q(s', m(s))].
The action-value Q of policy is the unique fixed- point of the Bellman evaluation operator T
Under certain conditions on the state and action space, it is known that there exists a deterministic policy that simultaneously maximises V/ and Q" for all states and actions [Puterman (1994), The- orem 6.2.12]. We call such policy an optimal policy and denote it by π² We will also denote V= = V* and Q=" = Q". Given an MDP M, we will sometimes write V to denote the value of policy in the MDP M (similarly for V Q Qi Qir.PM, Ty)) We denote the unit Euclidean ball in ddd by B {x Rd |æ|| & 1) and its boundary by AB {I Rd ||2||2 = 1}. For n tors ..... Un E ²B, we denote the subspace spanning the vectors by (V,.... Un). >. For two positive
functions f and g, say ((x) ((g(x)) if Fc 0, N such that for all x N. f(x) t cg(x).
3

---

Published as a conference paper at ICLR 2024
3 PROBLEM SETTING
In this section, we formally define the RL problems and the learning model we consider. We borrow the framework from the work of Zanette (00T)) and extend it beyond the offine RL setting.
3.1 POLICY EVALUATION (PE)
Let M be a class of MDPs with the same S and A. For M E MM, let IIM be a set of (deterministic) policies and 11 {MlM] Mc.. PE problem defined by (M,11) consists of:
1. An instance (3, M,, TM II), where M E M is an MDP, E II is target policy and a starting state. M, and are known but M and RM are unknown.
2. An interaction procedure with the MDP M collect dataset 'D (see Section 3.3
3. An objective: Following the collection of the dataset D, the target policy TM becomes known to the learner. Based D and T,M the learner produces output QD(3, estimating the action- value Q (8 of the target policy Tas- The performance of the learner evaluated by the accuracy of the output any instance, formalized as(c, 8) soundnnss (Definition 3.1).
Definition 3.1. A learner is (s, 5)-suund for PE problems characterised by (M, 11) ffr all M M, TM M. the learner faced with instance (3, M, TM, III outputs QD that is e-accurate
with probabiliry at least 1 - 6, i.e. it satisfies P supae IQ (3,a) QD(5, a)l < <E) 11-8.
3.2 BEST POLICY IDENTIFICATION (BPI)
Let M be a class of MDPs with the same and A. BPI problem defined by M consists of:
1. An instance (s, M, M)) where M E MM is an MDP in M and 3 S is starting state. M and are known but M is unknown.
An interaction procedure with the MDP M collect a dataset D (see Section 3.3
3. An objective: Based on D, the learner produces output ीD of near-optimal policy for M. The performance of the learner is evaluated by (s. 6)-sunndsess (Definition 3.2). i.c. the sub- optimality of the output policy on any instance (see 1.).
Definition 3.2. A learner is (æ, 8)-suund for BPI problems characterised by M for all M e M. the learner faced with instance (3, M, M,) outputs To that is e-optimal with probabiliry at least
1 6, i.e. it satisfies P (V V (3) <E) 1-
3.3 MULTI-BATCH LEARNING MODEL
We define some important notions related to our learning model. A query is state-action pair as x As that submitted the unknown MDP M and for which feedback is returned. A query formalises how the learner interacts with an MDP, the feedback received is defined next.
Definition 3.3 -Query-Feedback). In return for a query (s, a) the environment provides feedback to the learner. For BPI, the feedback is the reward T' (s and the transition function pM [-]s, a... For PE, the learner also receives evaluations of the target policy TM for all states in the support of Pas p-s(-ss, a), i.e. {TM(('') s' S s.f. Pas(st (ss(ss a) 0}.
Remark 3.4. The learner receives the transition, fonsition,uunction PMr(-s, a) for a query (s, a), instead of sample from pMr(-s,,)) This removes any statistical uncertainty and is equivalent to observing finite samples, which strengthens any houer-bounds proven under this frame-work The evaluations of the target policy aM are motivated by giving partial information about RM to the learner.
We summarise the learning model in Algorithm I We consider two mechanisms for the learner to specify the set of queries 14g round (line 4). For both, we denote nış | the number of queries at round & and n >>= 74 the total number of queries.
"There is randomness in the feedback of the dataset D (see Section 3.3 the probabilities with respect randomness arising from the learner's query selection output strategies.
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 Multi-Baich Learning Model
(Input) PE BPI problem and number of batches K.
2: Initialise Do = Ø
3: for k 1..... do
4: (Query Selection) With knowledge of D learner chooses set of queries pk--
5: (Data Collection) Environment receives queries μag and returns to learner Dr (set of queries
+ feedback for all queries in Mk= see Definition 3.3 Learner updates Dr = - Dj.
6: Set D Dx U 1 Dj (and for PE, aM becomes known).
7: (Output) Learner returns QD (PE) or ue (BPI).
1. Policy-Free Queries: In the first mechanism, the learner explicitly selects the set of queries pk by selecting set of state-action pairs. The learner has access to the dataset Dx-1, which contains the feedback of the queries from the previous rounds from the MDP M the learner is faced with. Let M& .M be the set of MDPs in M that would produce exactly the feedback in dataset D given the queries in the previous rounds. Given the queries this is deterministic since there is no randomness in the feedback of a query (see Definition 3.3). The learner can use Mr. in the selection of the queries at round k but the specific MDP it is interacting with remains unknown if [Mxl > 1.
2. Volicy-Inducee Queries: The second mechanism produces queries indirectly by selecting poli- cies and using the queries along trajectories induced by these policies interacting with the MDP M. Stochastic transitions imply different realizations of trajectory for a policy from same starting- state. We allow the queries to be the state-actions pairs along all realizations of the trajectories.
Definition 3.5 (Policy- Induced Queries (Zanette| (202I), Definition 2)). Fix set T. [s T.. (e,c)) ) of K& triplets, each containing a starting state she a deterministic policy कद and a trajectory length c;. Then the query set μa induced by Ty is defined as
U
Reach(so: 80, nT
(BD,3,c)ETT
where Reach( so: n. = a))at C.t. P((s;, at) = (s, TT) > 0}
are the state-action pairs reachable in e or less time-steps from So using policy и. Note (st, ai) is the random state-action pair encountered at time-step t upon following x from Sp-
The learner specifies a set T' from which set of queries μa is induced Similarly to policy-free queries, the learner can use M₁ in the selection of Ti at round k but the specific MDP is interacting with remains unknown if |M&l 1.
Remark 3.6. Policy-induced queries include policy-free queries as special case (c = 1). How- ever, the dynamics of all MDPs in the class M are the same, then policy-induced queries are also policy free because the learner knows the dynamics of the MDP it is interacting with. So it knows exactly the queries that any set Tg will induce and can specify these as policy-free queries. If the dynamics of all MDPs in the class M are not the same, then policy-induced queries can reveal more information because a trajectory guided by the dynamics of the MDP while policy-free queries only reveal information about individual distinct transitions. Because of this, we will obtain slightly stronger results for policy-free queries in Section f
Adaptivity:
The multi-batch learning model encompasses different levels of adaptivity to feedback, which is measured by the number of batches K:
For K = 1, the learner is non-adaptive and the dataset D is collected in a single batch. This is the model considered by Zanette (2021) for offline RL that we extend for general K.
For K > 1, the learner is adaptive and the dataset 'D is collected in multiple batches. Queries for a batch are selected based on feedback from previous batches.
For K (i.e. each batch contains single data-point), the learner is fully-adaptive. The queries are selected sequentially and depend on the feedback from previous queries.
'A sample-efficiee learner requires |px| to be polynomial in d but the learner does not directly select For example, if the transition function is stochastic it is possible that Tj induces H with |/4/| 30 or non-polynomial in dimension. The MDPs consider all have deterministic transitions so this is issue.
5

---

Published as a conference paper at ICLR 2024
4 MAIN RESULTS
In this section, we present our main results: lower-bounds on the number of rounds K for sample- efficient algorithms. First, we state some assumptions. We assume 7 > V 3/4. We also consider a linear representation of the action-values for a known feature map of state-action pairs. This is form of linear function approximation that is strictly more general than linear MDPs (Zanette et al., 2020), which assume the reward and transition functions are linearly representable. Specifically:
Assumption 4.1 -0i-Realizability (Zanette (202I), Assumption 1)). Given any PE problem in- stance (5, M, M, M IT,, there exists a known feature map & A Rdd s.t. (0(,)) & and there exists 0 e B such that for all (s, a) E S x A.
QT (s, ols a(s,a)"071
Assumption 4.2 Rea-ieaiizabilityy for every policy ZZanette 2021), Assumption 3)). Given any BPI (8, M) or PE (x, M,M, TM, II) problem instance, there exists a known feature map & S A Rd |Ø( 2l2 and for any policy π there exists 03s B s.t. for all (s, a) A,
@))(s, ((,a)" a
This first assumption is used for PE problems. The second is stronger as it concerns the action-value of every policy (not just policies in II) and in particular it holds for Q" We assume the learner is aware when these assumptions hold. Finally, we formally define a sample-efficient learner:
Definition 4.3. A learner for PE or BPI problems under Assumptions 4.1 or 4.2 is cample-efficiee if its total number of queries n = Ek=1 ng is polynomial in d.
4.1 POLICY-INDUCED QUERIES
We first present result for PE under policy-induced queries. Since all MDPs in the class used in the proof share the same dynamics, policy-induced queries equivalent policy-free queries (see Remark 3.6) and the result holds for both. The full proof can be found in Appendix
Theorem 4.4. Fix d sufficiently large. There exists a class of MDPs M and policies 11 defining PE problems (s. M,M, TM, II) satisfying Assumption such that any sample-efficient learner better than (1, sound using policy-induce or policy-free queries requires K 2ilog log d).
In the class of MDPs used for Theorem 4.4 we can hide information about M E M in the target- policy for PE but cannot for BPI. Instead, we could hide information in the transitions but this can be revealed by following policy trajectories (policy-inducee queries) in our constructions. In the next section, we restrict the learner policy-free queries and provide results for both PE and BPI. Note that a (1, sound learner performs poorly since the MDP class has value functions in [-1,1].
4.2 POLICY-FREE QUERIES
We now consider only policy-fire queries, which gives the environment freedom to hide information in the transition function of the MDP and leads to lower-bounds for PE and BPI that hold for the stronger Assumption 4.2 of all-policy realizability. The full proof can be found in Appendix F
Theorem 4.5, Fix sufficiently large. There exists a class of MDPs M and policies defining prob- lems for PE (5, M, M, TM, 11) and BPI (3, M,) satisfying Assumption 4.2 such that any sample- efficient learner better than (1, (1,1/2)-sound, using policy-free queries requires 2(log log d).
4.3 DISCUSSION
The results indicate that K 2(log log d) batches are necessary for solving PE or BPI tasks sample- efficiently under realizable linear function approximation. Beyond the exact dependence d, the significance of these results that just having K is insufficient. particular, more adaptivity is needed the dimension of the linear representation increases. These results demonstrate that sam- ple efficiency is impossible not only in offline RL, but also in settings with some level adaptivity (K o(log log d)). Therefore, the boundary at which sample-efficiency becomes impossible is at

---

Published as a conference paper at ICLR 2024
dimension-deppen dependent level of adaptivity between offline and full-adaptivity. This leaves interesting open directions on the existence of a sample-efficient algorithm using K = O(log log d) batches.
Our lower-bounds no longer hold if the action space A is finite with coverage assumptions on the collected data (for BPI). While it may be necessary to have coverage assumptions in an offline setting, this assumption need not be made when data is collected adaptively, as in our setting.
Furthermore, in Appendix B we provide results for the fully adaptive setting where the number of batches K is equal to the number of total queries n (i.e. each batch contains a single query). We show that if the feature-space covers B. there is a learner that solves any realizable (Assumption [ PE problem in d queries. Assuming known target policy æ, linear dependence on d was already known to be possible using roll-outs from π (Lattimrre et al. 2020), however the dependence on d was coupled with other quantities such as the effective horizon 1/(1-?) and desired accuracy E. Our result states that d-queries are sufficient to find Q exactly (c = 0), independently of y. Our result relies heavily on the condition that the learner observes the transition function Pas (-|s, a) rather than sample s' ~ (-1s, a) for a query (s, a) (see Section 3.3). though our result under this condition is strong since using this condition with the roll-outs from т would not give exact convergence in d-queries. We also provide matching lower-bound (that also holds for BPI). These results serve to illustrate the trade-off between comple-efficienge and low-adaptivity for PE under our framework. Full-adaptivity allows low sample-complexig while reducing adaptivity below K o(log log d) comes at the cost of high sample-complexity (losing sample-effiiiency)
4.4 RELATED WORKS
The works discussed below are for
discounted MDPs unless stated otherwise.
Tabular MDPs (IA4,, [S] are "small") can be solved in the offline setting under policy-free queries:
model-based approaches (Li et al. 2020 AAarwal et al. 2020) under a generative model minimax-optimal (Azar et al. (2033) with sample-complexity linear in the dimension of the MDP |A| x (S). These methods estimate the MDP by sampling equally from all state-action pair and then use dynamic programming approaches on the estimated MDP. In particular, all the samples are drawn in a single-batch. Beyond the generative model and under a restricted form of our policy- induced queries (Definition 3.5). tabular offline RL is no longer sample efficient (Xiao et al. 2022) and requires a number of samples exponential in |S] or 1/(1- ())
Linear Function Approximation: In the offline setting, there are lower-bounds showing OPE or BPI is not possible with samples polynomial in the effective horizon 1/(1 - 7) or the linear dimen-
sion (Amortila et al., 2020; Chen et al. 2021 Zanette 2021). The bound of /Zanette (202T) is the strongest as it holds for any data-distribution. These exponential lower-bounds can be overcome with assumptions such as low-distribution shift (Chen et al.) 202T), low inherent Bellman-error (Xie) & Jiang, 2020 Duan et al. 2020) or low local inherent Bellman error (Zanette (023). We refer the reader the work of Zanette (202T) for more in depth discussion of offline RL. In the fully- adaptive setting, there are sample-efficient algorithms under all-policy realizability (Lattimore et al.) 2020), under V"*-realzzability only (Weisz et al. (021) (if the action space is finite) and under linear MDPs Taupin et al. 2023 Kitamura et al. 2023).
The multi-batch learning model has been studied extensively for bandit algorithms (Perchet al. 2015 et al. [2016] Gao et al. 2019 [sfandiari et al.] 2021 Duchi et al. 2018 Han et al. 2020 Ruan et al. (021). In RL, it has been studied in the regret-minimisation setting for finite-horizon tabular Zihan et al. 2022) and linear MDPs (Wang et al. 202T) and MDPs under general function approximation (Xiong et al. 2023). closely related notion is deployment efficiency (Matsushimal ett al. 2021), which constrains batches to be of a fixed size consisting of trajectories from a single policy. In finite-horizon linear MDPs, has been shown that BPI can be solved to arbitrary accuracy with number of deployments independent of the dimension d (Huang al. 2022, Qiao & Wang, 2023) where the deployed policy is a finite mixture of deterministic policies. Our results suggest that infinite-horizon discounted MDPs under more general linear representation of action- are fundamentally harder since the number of deployments must scale with dimension.
Please refer to Appendix A Affor discussion of works related to low-switching cost (Qiao et al. 2022
Bai et al. 2019) Zhang et al.) 2020; Gao et al. 2021 Wang et al. 2021 Qiao & Wang 2023
Qiao
al. 2023) and policy fine-tuning (Xie al." 2021 Zhang & Zanette 2023).
7

---

Published as a conference paper at ICLR 2024
5 PROOF SKETCH
We extend the ideas of Zanette (202T) beyond offline RL multi-batch problem (see the end of this section for comparison). We consider the PE problem with policy-free queries under Assumption for feature vectors o(-, covering the unit Euclidean ball B (see Figure D.. The intuition for Theorem 4.5 is closely related.
In this section, we provide intuition for the proof of Theorem 4.4
Consider the first batch of data with na queries and let (&t, ai) be the i-th query and (s (x()) the corresponding (assumed deterministic) successor state and target policy evaluation. Define
0( a1 )²
r(s1,a))
o(st, "Nf
+
-=
x+
(8n1 4ng
L (n))
Since QTM is the fixed point the Bellman evaluation operator: QTM (sM(s, (T* (FM"T)))ss and by Assumption 4.1 there exists 05 such that QTw (s, a) o(s, a) 0T for any as, the learner aims to find a solution satisfying the (local) Bellman equation
40 = 7
@ - + =
- is not full-rank, this equation does not have unique solution. The learner only chooses Φb The environment, with knowledge of Φ, can pick o+ maximise the dimension of null-space" of X, which can be viewed as erasing information along many directions (see Figure llftt. This phenomenon where the value of a policy in a state depends on the same value in the successor states is known as bootstrapping and is the mechanism inducing hardness in setting allows the environment to choose these successor states adversarially to erase information.
N
41
d2
Figure 1: Left: Information can be erased in multiple directions: Consider the setting where information is being erased along the pink plane N: the learner's queries Φ(st, a;) are shown in blue and the environment's 's responses ",,(s," (s;") )) are shown in black. The rows of X, a.) r0(s," (s,")) (blue + black vectors) all lie on the yellow line so the learner acquires no information in the directions of the pink subspace N,, the null-space of X. Right: Information cannot be erased in all directions: Consider the opposite setting where information is being erased along the pink line N. Because of the constraint [[o(s, a) & and 7 1, a query Φ1 (in blue) in the pink cap cannot have Φ1 - PΦt (blue + black vector) projected back onto the yellow plane (unless T 2 > 7 = | > 1). Despite the environment not being able to erase information in certain directions, if the number of queries is "small", it can always find directions to erase.
Although the learner can prevent the environment from erasing information along certain directions (see Figure [igureTrrghtt right), since n, is polynomial in d this only prevents the environment from erasing in- formation in a limited number of directions. Specifically, we show that if n, is less than exponential in dz/4 then there subspace of dimension d/2/4 that can be included in the null-space of X.
Prior to choosing n2 queries for the 2nd batch, the learner observes the feedback from the first batch. It becomes aware of the directions of the null-space and can focus its queries for the next round these directions. However, the null-space still at least d' dimensiionl and the same
By the rank-nullity theorem, this is equivalent minimising the rank of X.
8

---

Published as a conference paper at ICLR 2024
reasoning as in the first round can be applied where the original dimension is now d//4. So if m2 is less than exponential in d1/16 then there is a subspace of dimension d1/16 that can be included in the null-space of the new local Bellman equation that includes the data from the 1st and 2nd batch.
After l: rounds if the number of queries at round k, n& is less than exponential in d²/1", then the null-
space of the local Bellman equation is still at least d'/4** -dimensional. If exp(d2/44) ) is more than polynomial in d, the sample-efficient learner cannot prevent a non-zero null-space and the problem cannot be solved. The learner must reach a round K where exp(d2/4*) becomes polynomial in d, requiring K (log log d) rounds, from which we get our lower-bound.
Description of the MDP construction for which the learner cannot do better than 11,1/2)- soundness. Consider an MDP class M with S A B and a feature map such that ø(s. a) = a. The successor state of (s, a) is deterministic and is the action a. Fix w E 0B and consider two MDPs: Mw,t and M We denote the reward function for either MDP with the same subscript:
if a C,(w)) Cy(- ( 7)1 otherwise,
10.
for 1 (+.
Mw,s:
(3,
where (w) = f B: 2" carefully designed target policy Tw. we show that Assumption holds. We also show with the reasoning described above that if = (d) for all k and K ollog log d), then none of the learner's 's queries are in (w) U (-(-)) Therefore the feedback observed contains no information about the sign of the rewards in (w) (-w). Mw,+ is indistinguishable from Ma.... Since QTr,.. (8, w) = 1 and Q (3, w) = 11 the learner must incur an error of 1 with probability at least 1/2. All the details are in Appendix E including further illustrations in Appendix E.5 The construction for Theorem 4.5 is similar but the transitions differ across MDPs (see Appendix
z"w//l ww/l wl2 > 7} is the 7-hyperspherical cap of w. For a w E ²B and
To improve the lower-bound with the current construction, we require the existence of a sub- space packing (of size exponential in d and subspace dimension ed (instead of dd11),, for some c < 1) with minimal chordal distance (see Appendix D) between subspaces dmin(() >> Vd- (272 1)2.
After k rounds, information would be missing along a subspace of dimension c* d, (instead of d2/4²) from which we could get a log d lower-bound. As far as we are aware, such result is not available in the literature, nor is subspace covering result that would rule out the possibility of such a pack- ing. We highlight that our MDP construction can be combined with any subspace packing result, paving the way for improved oower-bounds should new subspace packing procedures be developed.
Comparison to Zanette (2021): The work of Zanette (021) erases information along 1- dimensional subspace (X is of rank d - 1). Therefore after having observed one round of feed- back, single additional query is sufficient to distinguish the MDP and solve the problem. Our constructions erase information along m-diimensional subspaces where we attempt to maximise m so that even after having observed feedback revealing this subspace, polynomial number of queries remains insufficient to distinguish the MDP, more adaptive rounds are needed.
CONCLUSION
In this work, we have studied the connection between adaptivity and sample-efficiency for RL al- gorithms solving PE and BPI problems under d-dimensional linear function approximation. For multi-batch learning, we have established 2(log log d) lower-bounds on the number of batches K needed to solve the RL problems sumple-efficient
(number of queries polynomial in d). In particu- lar, having adaptivity (K 1) does not guarantee sample-efficiene
Consequently the boundary of sample efficiency must not lie between batch RI. (K 1) and adaptive RI. (K > 1) but rather within a regime of adaptivity scaling with dimension. These insights contribute to a deeper understanding of the trade-offs and possibilities in designing sample-efficient RL algorithms with low-adaptivity.
remains unclear if the log log d dependence on d tight, An upper-bound similar to the one we have given for the aully-adaptive PE problem in B be established by developing new tools in the theory of subspace covering. These would formalise the number directions for which the learner can prevent information erasure. It is also unclear if Theorem 4.4 under policy-induced queries also holds for BPI or if the samplc-efficiency of BPI-algorithms in low- adaapivvv settings differs for policy-ing induued and policy-free queries. We leave these as future work.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
EJ is funded by EPSRC through the Modern Statistics and Statistical Machine Learning (StatML) CDT (grant no. EP/S023151/1 1///I) and thanks G-Research for partly funding attendance to ICLR 2024.
We would like to thank the reviewers and meta-reviewers for their time and feedback, which led to better version of this paper. We would also like to thank Nathan Mankovich and Hugo Chu for helpful discussions.
REFERENCES
Alckh Agarwal, Sham Kakade, and Lin F. Yang. Model-based reinforcement learning with gener- ative model minimax optimal. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 67-83. PMLR, 2020.
Philip Amortila, Nan Jiang, and Tengyang Xie. A variant the wang-foster-aakade lower bound for the discounted setting. 2020. Preprint, arXiv: 2011.01075.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with generative model. Machine Learning, (3): 925-349, 2013.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, volume 32, 2019.
Richard Bellman, Robert Kalaba, and Bella Kotkin. Polynomial approximation-a a new computa- tional technique in dynamic programming: Allocation processes. Mathematics of Computation, 17(82):155-161, 1963.
Lin Chen, Bruno Scherrer, and Peter L. Bartlett. Infinite-horizon offline reinforcement learning with linear function approximation: Curse of dimensionality and algorithm. 2021. Preprint, arXiv: 2103.09847.
John H. Conway, Ronald H. Hardin, and Neil A. Sloane. Packing lines, planes, etc.: packings in Grassmannian spaces. Experimental Mathematics, 5(2):139 - 159, 1996.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards account- able reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 1507-1516. PMLR, 2019.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear func- tion approximation. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2701-2709. PMLR, 2020.
John Duchi, Feng Ruan, and Chulhee Yun. Minimax bounds on stochastic batched convex optimiza- tion. In Proceedings of the 31 Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 3065-3162. PMLR, 2018
Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for batched bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 3580)7334- 2021.
Minbo Gao. Tianle Xie, Simon Du, and Lin F Yang. provably efficient algorithm for linear markov decision process with low switching cost. 2021. Preprint, arXiv: 2101 .00494.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. In Advances in Neural Information Processing Systems, volume 32, 2019.
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye. Sequential batch learning in finite-action action linear contextual bandits. 2020. Preprint, arXiv: 2004.06321.
10

---

Published as a conference paper at ICLR 2024
Jiawei Huang, Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie- Yan Liu. Towards deployment- efficient reinforcement learning: Lower bound and optimality. In International Conference on Learning Representations, 2022.
Zeyu Jia, Randy Jia, Dhruv Madeka, and Dean Foster. Linear reinforcement learning with ball structure action space. In International Conference on Algorithmic Learning Theory, pp. 755- 775. PMLR, 2023.
Kwang-Sung -ung Jun, Kevin Jamieson, Robert Nowak, and Xiaojin Zhu. Top arm identification in multi-armed bandits with batch arm pulls. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pp. 139 148. PMLR, 2016.
Toshinori Kitamura, Tadashi Kozuno, Yunhao Tang, Nino Vieillard, Michal Valko, Wenhao Yang, Jincheng Mei, Pierre Ménard, Mohammad Gheshlaghi Azar, Rémi Munos, Olivier Pietquin, Matthieu Geist, Csaba Szepesvári, Wataru Kumagai, and Yutaka Matsuo. Regularization and variance-weighhed regression achieves minimax optimality in linear MDPs: Theory and practice. 2023. Preprint, arxiv: 2305.13185.
Allison Koenecke, Andrew Nam, Emily Lake, Joe Nudell, Minnie Quartey, Zion Mengesha, Connor Toups. John R. Rickford, Dan Jurafsky, and Sharad Goel. Racial disparities in automated speech recognition. Proceedings of the National Academy of Sciences, 117(14):7684-7633 2020.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch Reinforcement Learning, pp. 45-73. Springer, 2012.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in RL with a generative model. In Proceedings of the 37th International Conference on Machine Learning, volume 119 Proceedings of Machine Learning Research, pp. 5662- 5670. PMLR, 2020.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. In Advances in Neural Information Processing Systems, volume 33, 2020.
Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, and Shixiang Gu. Deployment- efficient reinforcement learning via model-based offline optimization. In International Confer- ence on Learning Representations, 2021.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit prob- lems. In Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1456-1456. PMLR, 2015.
Martin L. Puterman, Markov decision processes: discrete stochastic dynamic programming. Wiley- Interscience, 1994.
Dan Qiao and Yu-Xiang Wang. Near-optimal deployment efficiency in reward-free reinforcement learning with linear function approximation. In The Eleventh International Conference on Learn- ing Representations, 2023.
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog(T) switching cost. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 18031-18061. PMLR, 2022.
Dan Qiao, Ming Yin, and Yu-Xiang Wang. Logarithmic switching cost in reinforcement learning beyond linear MDPs. 2023. Preprint, arXiv: 2302. 12456.
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distri- butional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 74-87, 2021.
11

---

Published as a conference paper at ICLR 2024
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Mahdi Soleymani and Hessam Mahdavifar. New packings in grassmannian space. In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 807-812, 2021.
Jérôme Taupin, Yassir Jedra, and Alexandre Proutiere. Best policy identification in discounted linear MDPs. In Sixteenth European Workshop on Reinforcement Learning, 2023.
Tianhao Wang. Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. In Advances in Neural Information Processing Systems, volume 34, 2021.
Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi- Yadkori, Nan Jiang, and Csaba Szepesvari. On query-efficient planning mdps under linear realizability of the optimal state- value function. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 4355 4385. PMLR, 2021.
Chenjun Xiao, Ilbin Lee, Bo Dai, Dale Schuurmans, and Csaba Szepesvari. The curse of passive data collection in batch reinforcement learning. In Proceedings of The 25th International Con- ference on Artificial Intelligence and Statistics, volume 151 Proceedings of Machine Learning Research, pp. 8413 8438. PMLR, 2022.
Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, pp. 550-559. PMLR, 2020.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, 2021.
Nuoya Xiong, Zhaoran Wang, and Zhuoran Yang. A general framework for sequential decision- making under adaptivity constraints. 2023. Preprint, arXiv: 2306. 14468.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: A survey. ACM Comput. Surv. 55(1):1-36, 2021.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be expo- nentially harder than online rl. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12287-12297. PMLR, 2021.
Andrea Zanette. When is realizability sufficient for off-policy reinforcement learning? In Proceed- ings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 40637-40668. PMLR, 2023.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In Proceedings of the 37th International Con- ference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp- 10978-10989. PMLR, 2020.
Ruiqi Zhang and Andrea Zanette. Policy finetuning in reinforcement learning via design of experi- ments using offline data. 2023. Preprint, arXiv: 2307.04354.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-ad vantage decomposition. In Advances in Neural Information Processing Systems, vol- ume 33, 2020.
Zhang Zihan, Yuhang Jiang, Yuan Zhou, and Xiangyang Ji. Near-optimal regret bounds for multi- batch reinforcement learning. In Advances in Neural Information Processing Systems, 2022.
12

---

Published as a conference paper at ICLR 2024
A FURTHER RELATED WORKS
The works discussed below are for infinite-horizon discounted MDPs unless stated otherwise.
Low-Switching Cost: Limited adaptivity in RL has mostly been studied in the context of regret- minimisation algorithms with low-switching cost for finite-horizon episodic MDPs, i.c. minimising the number of times the policy used changes from episode to the next. These works are not directly comparable because they study regret-minimisation for finite-horizon MDPs and we study
BPI and PE in the discounted setting. Nevertheless, there are works tabular MDPs (Qiao al., 2021 Qiao 2023
2022 Bai et al. 2019 Zhang et al. 2020), linear MDPs (Gao et al. 2021 1
Wang et al.
& WWnn 2023) and MDPs with a linear representation for the action values QQiao al.
The policy finetuning setting assumes access to an offline dataset that can be complemented with online trajectories (Xie et al., 202T) but is different from setting since there is no adaptivity constraint in the online algorithm, i.c. once the initial dataset has been collected, the query selection strategy can be updated after each new observation (or episode in the episodic setting). However, if the additional trajectories are collected using non-adaptive policy instead of an online algorithm, batches. This is studied by Zhang Zanette (2023) who
we can recover our setting with K show that for finite-horizon tabular MDPs, K = 2 is enough to solve the BPI problem to arbitrary accuracy. Our results rule out achieving a similar result for anfnite-hhrizon discounted MDPs under policy-free queries and linear function approximation.
B BOUNDS FOR THE FULLY ADAPTIVE SETTING
In this section, show upper-bound result for the fully adaptive setting (K see Section 3.3). In this setting, the oracle selects one query in each round or batch of data, so chooses (8k, ag) round & with knowledge of the feedback from queries up time k 1. The number of rounds K coincides with the number of queries n (each batch contains one query). In particular, since is one query at time, there is difference between policy-induced or policy-free queries. The upper bound we show relies on the following assumptions on the feature space:
Assumption B.1 (Feature Map). Fix feature map d. Given any orthonormal set of vectors {ui.-.. Un with n < d, it is possible to choose a state-action pair (s, a) such that Φss, a) (ul Un) and [[o(s, (s, a)ll2 1
The superscript 1 on a subspace refers to the orthogonal complememnt of the subspace.
Theorem B.2. Fix d > O. Consider any PE problem M, M, 11) satisfying Assumptions 4.1 and for the same feature map o. then there exists a fully-adaptive learner that solves the PE problem exactly in most d queries.
We complement our upper-bound with a matching lower-bound, which holds for both PE and BPI.
Theorem B.3. Fix d > 0. There exists a class of MDPs M and target policies II characterising PE problems (8, M, TM, II) and BPI problems (8, M, M) that satisfy Assumption an2 share the same & and M such that any fully-adaptive learner that is better than (1, 1/2) sound requires K = n 2 d.
Theorem B together with Theorem B.3 shows that exactly d queries are optimal for solving a PE be expected because
problem under our feedback model and Assumption The bower-boundl the learner is operating in d-dimensional feature space so has to learn in d directions. However, is interesting that the structure imposed by Assumption B.T on the learner's capacity to explore the feature space is sufficient for the learner to fully solve the problem in only d queries. A similar assumption was studied by Jia et al. (2023) to obtain a sample-effiiiet algorithm for BPI in finite- horizon MDPs. We can obtain this result for PE with simple analysis because the learner can exploit that the action-value of a policy is the fixed point a linear operator, the Bellman evaluation operator. An equivalent approach does not work for BPI since the action-valle value of the optimal policy is not the fixed point of a linear operator.
The proofs of the theorems in this section can be found in Appendix G
13

---

be close to the boundary of B. It is two sided meaning that if æ C.)(H), then - that the subspace H is defined on I but C. (H) B. Published as a conference paper at ICLR 2024
C HYPER-SPHERICAL CAPS AND SECTORS FOR SUBSPACES
Recall that B {x E R |0:|2 & 1 is the d-dimensional unit hyper-sphere.
Definition C.I. Fix w E B. Define the 7-hyperspherical cap of w as:
x
(y(w) =f
|
A vector is in the 7-hyperspherical cap of w if the angle 0 between and satisfies
|| cos 0 = B < arccos
2
With y close 1, these represent a vectors in the hyper-cone around that close the boundary of B (see Tigure[rriee riihht). The key property that motivates considering vectors in this set is that they require a vector of norm greater than 7 to be projected in direction orthogonal to w. We extend the notion of 7- 7-hyperspherical caps to subspaces of multiple dimensions.
Definition C.2. Fix a subspace of TR.. Define the --hyperspherical sector of H as
xf
(H) E 30 s.l.
7)
||||||20
See Figure for an illustration.
H
H
Illustration of hyperspherical sector of 1-dimensional subspace (left) and 2- dimensional subspace (right all vectors whose direction is within the two pink bands). In both cases, the subspace H/ is in yellow.
Figure 2:
Beyond the extension to subspaces multiple dimensions, Definition C.2 differs from Definition C.1 in ways. is hyper-spherical sector rather than cap, which does restrict the vectors to A C (H)). Note
Similar the intuition in the 1-dimensional case, vector is in (H) if there is vector in И whose angle with x is "small". It is equivalent to taking the unions of the 1-dimensional 7- hyperspherical sectors of all the vectors H. Again, the key property that motivates considering vectors in this set is that they require a vector of norm greater than y to be projected in direction orthogonal H.
We also note that vector is not in (H) if the subspace H does intersect (x)) the 7-hyperspherical sector of (x). This allows us to work with the 7-hyperspherical sectors of one dimensional subspaces (span of single vector) instead of subspaces of multiple dimensions, We
will also abuse notation and write (x) instead of C (()))
14

---

Published as a conference paper at ICLR 2024
D SUBSPACE PACKING
D.1 PRELIMINARIES
Denote the set of all m-dimensional subspaces of _2 as (m,a(B), which called the Grassmannian space. An element A (m.)(R) an m-dimensional subspace of Rd.
We present a measure of distance between subspaces known as the chordal distance Conwwy et al. 1996.. Fix two subspaces A, B (m, The principal angles 01,.... 6m [0, x between A and B are defined as
cos 0; max b
a bj.
asA B |a||2|6||
for I, ..., m such that ||a:|22 16:12 a" c"'a, 0, b² 0 for jijjj-i- distance de is then defined as
The chordal
d)
V sin 0, sin" 02 sin Om-
We define the notion of subspace packing, which is the usual notion of a packing where the is the Grassmanian space Gm (BR and the distance is the chordal distance.
Definition D.1. A subspace packing C of (R) is set of n-dimensional subspuces in IRd of size [C], ie, a subset of ((R). The minimum distance between elements of measured by the chordal distance and is denoted
dinnn (C) =
min 4cAABB)
ABB
D.2 A SUBSPACE PACKING BOUND
Lemma D.2 Soleymani & Mahdavifar 2021
Theorem 4). Fix d 2N for some N N and integers k < and m < d. There exists a packing in Gm, size size |C| = [k/2| d 8.1
m(k 1)²
dmin (C) > V vmyl
d
Theorem 4 from Soleymani & Mahdavifar 2021) is presented for packings in Gm (CC) but they give
(in Remark 1) mapping trom a packing in Gm/2.4/((C) to a packing in Gm.d (R) that preserves the normalized distance dg (= (Cmi(()) /m) between the elements of the packing, giving the result presented above.
D.3 EXISTENCE OF AN ISOLATED SUBSPACE
The following lemma the key result for the construction of the class of MDPs used in the proof of main results. It establishes that if number of points is "small", then for any points there exists a subspace whose 7-sector contains none of the n points. The environment can erase
A information along this subspace (see Scction 5). See Appendix C for the definition of (H)) for subspace H. The proof is given in Appendix D.3.2
Throughout, we will use g(7) = 2?2
Lemma D.3. Fix d N for some N > 8. Consider D {yy "..,,...,.0 Mn., set of n. points s.t. yi for all e [m]. If
( (0(7))444
n 1
then there exists a subspace A E G2IN:4 (R) of dimension 2|1/4| s.L.
Vre D,
$ (A).
15

---

Published as a conference paper at ICLR 2024
D.3.1 PRELIMINARY LEMMAS
The proof of Lemma D.3 relies on the following lemmas. See Appendix D for the definition of ((,)(R) and the definition of a subspace packing C.
Lemma D.4. Fix d 2 for some N If there exists a packing C a of size [C] > n+1 s.f. 4mii(()) 3 vm - 9()), then given a set fy1.....y... of n queries s.t. yi E B for all e [n]]
there exists subspace H e Gm.((R) of dimension s.t. $ (A) for all i.
This lemma establishes that if + 1 subspaces sufficiently far in terms of chordal distance, then for any n points there is a subspace whose y-sector does not contain any of the n points. The proof is given in Appendix D.3.3
Lemma D.5. Consider (n 1) subspaces Al...., An+1 of dimension m s.t. for any i j.
x²=
g(7).
SEAL.
1 |
Given n. vectors y,, Un E B (w.l.ogg all unit norm), then there is a subspace H E s.t. for all y E (y1.... Mn3.
H (Ai,..., An+1)
Y W
max
E 7
2
meaning yi C.y (H) (H) for I....,
This lemma similar Lemma D.4 but uses more explicit notion of distance between subspaces. The proof is given in Appendix D.3.4
D.3.2 PROOF OF LEMMA D.3
To prove Lemma D.3
we show the existence of subspace packing C in (m,)(I)) (with m 244144) The subspace packing must satisfy two conditions:
and use Lemma D.4
|C| [C 1.
dmmii (C) /
To show the existence of suitable subspace packing, we use Lemma D.2 with & 1867) /d 1|
sfa) vd-1
(< d). Lemma D.2 gives packing C of size |C|
s.t
dmin(() (C) v m g(7)²
Substituting in N/44 into the lower-bound on the size of C gives
slviad -1 =
d
d
3/4
269)
2/2-181111
23/4
|23N/4|
d
2
d
260
4//4
2
2
23N/4
2
2
where we used
> N/4 1 because [x]
23/4|238/4
if N 2.
23N/4
2/1)2//1
2 N/4 Nf and 7 v3/4.
Since the condition given in the statement of the lemma is
n 1+15 d
aíx) 21/4
$ [c,
the packing satisfies |C] > n + and dmin (C)
2
V m - - By Lemma D.4 there exists a
subspace A E (T))(RR of dimension = 2[N/4| s.t.
A
vr D.
$ CA()).
which concludes the proof of the lemma.
16

---

Published as a conference paper at ICLR 2024
D.3.3 PROOF OF LEMMA D.4
Consider distinct A, B C, i. A, B are subspaces of dimension m
do(A,B) m - m-g(()²
Now letting 0 01 E ... On & n/2 be the principal angles between A and B (see Appendix D). we have
dc(H, A) = (01) + (0m) & V + sin 0,
Combining with the inequality above,
v m n g(7)² & m 1+ +innsnn 01 sin?(01) > 1 --)()))
The first principal angle 01 arccos ab where A, b E B are unit vectors chosen s.t.
x² y
a= b
aE AEE
So we have
x
a b cos O1
V sin²(0:) g(7)-
AEE.
x 22222222
Since this applies arbitrary distinct A, B C, there are (n + 1) subspaces Al,.., Ant1 C of dimension m s.t. for any * j.
x²z
max ze 2
|
((7)) = -2-²
By Lemma D.5 there exists a subspace in {AI, Ant13 s.t. for all E (Mi,..., Bn).
y w
max H
& 7
wll2
ie. $ (1) for i I,...,,, which concludes the proof.
D.3.4 PROOF OF LEMMA D.5
Recall that we consider (n 1) subspaces A1...., An+1 of dimension s.t. for any i * j.
x g(7) 2n² - 1.
max sEA,,
|
Identify each y to the subspace An(i) that closest to y terms of inner product or angle, formally
h( arg max vf u/ w//lu
wEA,
Since there are n vectors yr. there will be least one subspace in {AI..., An-1) 1) that not associ- ated to any of the y.s. Call this subspace H.
We show that for any y E f max
7
Fix E {ud and let A be its corresponding subspace An(i)- Let
y TTu' w/
argmax, wel
ww
y a'
a = argmax d'
1a'||2
Assume both and of unit norm w.l.o.g. We know:
17

---

Published as a conference paper at ICLR 2024
1. w E a"y from the definition of h()).
2. w a < (()) from
Let wta
w the average of w and a, with ||w + all2 www + 2a w + a a 2 2a w
2(1 + w).
Claim: w² & w x (intuition: y is "closer" to than so w should be "closer" to average of and w than y).
Proof of claim: Assume w" > w² x. From 1. this implies a" > w" x. Now
w x w T
w +
w w T a
1 + w a aaa + w
a x.
W a
0/2
| al2 w 0|2
So we have a y > a= 0. Combining:
a
(y-x) > O. From the initial assumption we also have J (y-z)-
(w + a)² (y x>> >
1² 0
s'y-r' y'y-1>0
d'y11.
which is contradiction since both x and y are of unit-norm. End proof of claim. We now show w" & 7. Using 2.,
n 1 w vf+a
V1 (1+
-1+272
27
V272
=
w al2
V2
v2
v2
v2
Combining with the claim we have that w²th & 7. have shown
Given the definition of w and that was arbitrary,
y W
arg max max w
E 7/
which concludes the proof.
18

---

Published as a conference paper at ICLR 2024
E PROOF OF THEOREM 4.4
E. MDP CLASS
The PE problems used in the proof of Theorem 4.4 are characterised by class of MDPs M and target policies II. In this section, we define the class MDPs M. All MDPs M E M in the class share the same state-space S, action space A, feature map and transition function p but differ in the reward function F' and target policy тм- This class of MDPs the same as the one used by Zanette 2222 the proof of their Theorem 1. Our constructions differ the set of target policies M which are defined in Appendix E.2
State-space: S = B and the starting state is the origin 0 B.
Action-space: For all 8 S. .A.
Feature-map: The feature map maps state-action pair a) to the action i.e. (ss a), ((8 a) a. Since a B, the feature space is the unit-hypersphere and [(((, ll & holds for all inputs.
Transition-function: The successor state state-action pair (s, a) is deterministic and is the action This is well-defined because both the action and state space are B. This only depends on the chosen action (and not the current state), so we will denote the unique successor state when taking action a by st
a.
The MDP class M is known the learner (see Section B). Therefore the learner knows the transition function and that all MDPs share it. Therefore only the feedback of the reward function and target policy is useful to the learner, as both of these are unknown. We define them in the following section.
E.2 INSTANCE OF CLASS
Every MDP M E .M is fully characterised by vector w E OB and a sign + or Hence, they are denoted by Mar, + or M and the reward function associated to either MDP will denoted with the same subscript. Specifically it is defined as follows:
0,
if a C,(w) u C-(w). otherwise.
on M..+
Tw, (s =
((1 --)aaam
0, Tw.- (w.- a) = (-(1-
if Cw(w) U (-w)).
on Mw,-:
otherwise.
See Appendix for the definition of hyper-spherical caps (z). Note that the transition function is the same for all MDPs in the class M and is defined in Appendix E.I In particular, the two MDPs Mw,+ or M only differ in their reward functions, which are opposite.
Target policy: The set of target policies 11 for MDP M E M depends on the vector AB that partially characterises the MDP but not on the sign t. The set of target policies is therefore the same for M and Mp.-.
Fix K 0 and consider sequence of K nested (not necessarily strictly) subspaces of Rd:
Bx = BK-1 = C B2 c B = Bo Rdd s.t. dim Bx 0 and BR. Set BK+1 (w). Let H [BI. Bx. BK+1 } denote the set nested subspaces (including (w)). This is not defined as an ordered set, but for notational purposes the order always be recovered since the sequence must be nested. If A is subspace of Rdd let proj (x:) denote the orthogonal projection of x onto A. See Appendix for the definition
of hyper-spherical caps C. (w) and sectors C, (H). A target policy tH.., is specified by the set of nested subspaces H., and is defined as:
if e A & if (B (CC,-)))) if E C, (w) (-w-
} proj pa ( (s),
for k = O.... UC,(-w)).
TH (s)
1 proj (8),
8,
19

---

Published as a conference paper at ICLR 2024
The target policy is defined for all E B:
K A C, (BW) (B.t)) BK,, J. Uc,(-w)) Uc, ((() Uc,(ww) = è (B,)
[U k=0
= Bv
= B.
and the pair-wise intersections are all empty (so they form partition). The actions taken are also well-defined:
A (x+1). (Bx+1) then s $ C (Bx+1) and from Definition C.2
For l = O,... K, if & (B.) this means that for any u E BR+1, ju s//|2/2/s/2 & y. Denoting x = pro]BB+1 Bu+1 (s) Bx+1,
x²x
|
E >|| En |012
|
meaning that proo BeL1 (s) E B.
If s (Bx u (w)), then s $ (c,(w) u C. (-w) and from Definition
C.1 this means that Iw" s| & Denoting I = proj (8) E BK+1.
xxxxx |
1x" s|
|a||2 7
|
meaning that t (s) B.
The set target policies MI for the MDP Mw.+ is the set of (deterministic) policies TH,,, for any sequence of nested subspaces H. satisfying the above conditions (w E Bx). We sometimes use a w, + subscript to refer to both MDPs simultancously.
Crucially observing actions (B,)C, for k & K may not reveal w. Without the knowl- edge of w, the reward function is unknown and even with the knowledge of or the target policy reward function not fully identified, in which case M and M cannot be distinguished.
E.3 REALIZABILITY:
We show that the action-valus of any target policy for any MDP M M can be linearly represented with the feature map defined in Appendix [E.] The action-value of a target policy π n.. only depends on w and the sign of the reward function of the MDP, the sequence of nested subspace does matter beyond w. Lemma E.1 (Q" Realizability). For any w E dB Qu.t and Qu, the action-value functions of any π M...: (a target policy) on Mw,+ and M respectively. Then it holds that
(w,, a) = + on M (s, a) on Mw.-.
V(s,a),
Consider Mw.+ and set a) o(s, a) w. We will show that Q satisfies the Bellman evaluation equations for ı at all state-actions pairs, which will imply that ((s,a) Qu.+ (s, Apply T M... to Q at (s, a):
Proof:
Th... (Q)(s,))= = Tw, (s, + 7(s (a), a(s (a)))
= Tw. (8, a) + Q(aa T()),
since st s*(a) = is the successor state of (s, a). We consider the RHS of the above for all possible cases.
20

---

Published as a conference paper at ICLR 2024
A Case 1: If (Bx) (Bx+1) for some k E [0,
1 rw.+ a) + 7Q(a, x m(a)) = 0 + 7Q(a, , proj proj Be-1 (a))
?
1 -áb(, 7 proi proiiatt Bats (a)) w
" pro.proja... (a)w
proj (a)w.
However, recall that E BR+1- Since pr (a) is the orthogonal projection of a: w' p (a) = wTa. a. Plugging into the above, we have: Tw,+(s, as + 7Q(a, I(a)) = d"w a(s,a)" w a)s,a), which satisfies the Bellman evaluation equation.
Case 2: Ifa E č, (BK+)) u C,(-w)) as above (recalling Bx+1 = (w))
Tw, (s.+( = 0 + 7Qaa, proj Bx (4))
> 7 proi (a))
proiixx.. (a)w
1
= projiEx.1 (a)w
au'"aaw"ur = Q(s,a),
which satisfies the Bellman evaluation equation.
Case 3: If a E (w) U C,( (-w,, the reward is no longer and we have:
(8, a) (Q,a, (a))
(1 1->)a" w + a))
(1 7) 7)a? w + 70(a,a)
(1 7)a² w + 7a" Tww w
a" w ((s,a) Q(s,a),
which satisfies the Bellman evaluation equation.
For all cases, Q satisfies the Bellman evaluation equations, so it is the fixed point of the Bellman evaluation operator. In particular, it is the action-value of the target policy π on M
Now consider Mw.- and set Q(s, a) = -0(s, a) w. We will show that Q satisfies the Bellman evaluation equations for π at all state-actions pairs, which will imply that Q(s, a) Qu,-(s, a). As above, apply Ti._.. at (s, a) to Q:
T (Q) a) = (s, + 7Q(a,
and consider the RHS of the above for all possible cases.
A C, (Bx) C, (Br+1) for some k E [o, KJ: 1
Case 1: Ifa E
Tw. (x, a) + 7Q(a, (()) = 0 7Q,a, - -roj Bets (a))
--yóaa 7
proj (a)) w
1
- (a)w
-projj (a)w
-aT b(s a) T Q(s.a).
21

---

Published as a conference paper at ICLR 2024
A Case 2: If (B u C-(w))) as above:
1 = 0+ >QQa(a, -proj Bx++ (a))
Tw
=ProjBN:1
~ ?
proj Bx:1 (a)) w
proji (a)w
= -Proj (a)w
(w" aoo"a)w""n -waa -d(s,a) Q(s,a).
Case 3: a E (w) Cy(-w), the reward no longer and have:
Fwr (8, ~ x(a)) = =-11 (1-7)a" w + (Q(a,
=-(1 7)a² 70(a, aF
-(1 7)a² w ya y
Tw -aa O(s a) T ((s,a),
which satisfies the Bellman evaluation equation.
For all cases, Q satisfies the Bellman evaluation equations, it is the fixed point of the Bellman evaluation operator. In particular, it is the action-value the target policy т on M.,-.
E.4 PROOF OF THEOREM 4.4
Consider the MDP class described Appendix and Appendix F.2 First, we know from Lemma (Q Realizabilitt) that all instances of the PE problem characterised by the MDP class M and target policies II satisfy Assumption 4.1 (QT is Realizable) with the feature map o(-.-) defined in
Appendix E
The dynamics of the MDPs in the class M are the same, which as discussed in Remark 3.6 means that pndicy-induced and policy-free queries equivalent. We provide proof for policy-fred -frce-free queries.
We specify the instance with MDP M M and target policy RM II according to the queries selected by the learner. Fix K > 0. Recall that n& is the number of queries made by the learner at round ls and n Σk= 72 is the total number of queries. Let Aş be the set of actions queried by the learner at round (i.e. |Agl ng). Set A U A to be the set of all actions queried up to round k.
The learner is sample-efficient so n is polynomial in d. Specifically, there exists some constant > 0 and some integer 7 such that & ad! Consider N e N s.t. 2 & d < N and set d, N Note that d_ > d/2. Fix W = exp( ( 1/4%, cannot solve the PE problem. Consider both cases:
If & W, we can show the learner
22

---

Published as a conference paper at ICLR 2024
E.4.1 CASE
Suppose W < n, then
W <
W ad
9(7) d/1*** loogadd))
8
9(1)
8 (d/2) 1/4 <log(ad")
using that d+
d
2
(d/2) 1/4 (d/2)1/4*
8
log(ad")
g(7)
1
4k log(d/2) log
log(ad")
g(7)
log(d/2)
4
log
((1)) log(ad?))
1
log(d) d/22
log
< K
log 4
log
[(7) log(ad?))
K c' log log d
for constant d' > and d sufficiently large.
E.4.2 CASE
n < W = n & exp()g(7)d for = L.... K. We inductively define the sequence of nested subspaces Bx = C B1 characterising w Bx) and used by the target policy TM s.t. for
k 1..... K, dim B₁ 2|N/441 2 and
Va As, a a CBC.....
Proof of existence of nested subspaces:
We proceed by induction. Let Bı C ... Bj be arbitrary sequence of subspaces and w e BroB arbitrary. We will define these but for now consider the target policy л.. (see Appendix E.2 with Hip {w),, Bx..., Bi).
Base Case: round A the learner has observed no feedback and chooses set of action queries A A₁ (we ignore the queried states since the reward and transitions functions only depend on the action) such that:
AA n1 < expl
(2
(if d4 > 12),
so by Lemma D.3 there exists a subspace G2INNA (R) of dimension 2|N/4| (> d'/4) such that
Vx A AT
C (H).
Set Bi = H. The learner then observes the feedback for A (The state s in the reward does not matter):
((rm, a), TH. (s+ (a))))))) a A1).
Not having fixed B2, BR. w does not cause problems with the feedback even though ~.... and Tw.t depend them since the feedback of A₁ only depends B₁: the learner only observes the projection of the actions in A, into Bi.
A a C,,(Br
V A
Va Ai.
THe (s (a)))
-TH (a) proj (a), (w, 0.
23

---

Published as a conference paper at ICLR 2024
In partieular, there is dependence B1++ B1 for i > 1, which can be arbitrary and fixed in later rounds.
Inductive Step: Suppose that at round k. there exists sequence of nested subspaces BB ... B1 used by the target policy hHw for 1,,. dim B, 2| 2 and
A Va E A., $ CB.).
Bk+1 need be fixed yet since the feedback of A only depends on B ......: Bg:
VaE Ak: a (Bx)
Va Ak:
TH (s (a)) TH (a) proj (a) for some j & k
(s,
The learner only observes the projection of actions in A& into B1, B2.... Bg. Note that the only constraint M up this step is E Bk-
Now By is such that Væ AR, & (BB) with d2 = dim By 2|N/441 learner has observed the feedback from A& and chooses set of action queries A&+1 such that
> d > 2 The
|AR+1] 14+1 & exp( @xp(= (
de
dx 1o()))
(if d, 12).
Then we know that the number of those queries that are in B3 is also less than
Therefore by Lemma D.3 there exists a subspace H Bg of dimension 2[[N/41/4
d++1
2 (can reduce the dimension if they do not match, removing dimensions will not add queries
A to C. (H) such that
Vx ARt1,
$ (H).
In particular, A can be entirely contained in B₁ or depend Bg,.., Bi in any arbitrary way. Set B2+1 H. We know that Vx 2g, $ (B,) and Be+1 Bg have
A x (Bx+1))
Vx AR+1
The learner then observes the feedback for Ag+1 (The state in the reward does not matter):
((rw. (s, TH. (a))) : Ast1)-
Not having fixed Bk+2, BR. w does not cause problems with the feedback even though лH... and Fw, depend them since the feedback observed up this round of A only depends on B1 .... B the learner only observes the projection of the actions in A into B1, B
A a (Bx+1)
Vas A
1
= Vae A (s (a)) TH. (a) p (a)
for some j < + 1,
(s, 0.
In particular, there is no dependence w or B B8+1 for i 2 1, which can be arbitrary and fixed in later rounds.
We remark Lemma D.3 establishes the existence of a subspace in 92traa .d (R) where the am- bient space is d instead of Rd. Any da di-dimensional subspace of Rd is isomorphic to Rd so we consider Bg, project the points of Aş+1 into B₁, apply Lemma D.3 to get H within Bg, and extend H to be defined in Rdd We omit these steps here for clarity but detail them fully in Appendix E.4.3 This also holds for the base case (where d, is used as the ambient dimension instead of d)
24

---

Published as a conference paper at ICLR 2024
When applying Lemma D.3 with ambient dimension dR 2[,4441, require [N/44] > 8. Since du i d+ and d+ > d/ 2, it is enough to have
log d 2
(d/2) > 2
K
log
log 4
log
K & c clog log d,
for constant and sufficiently large. If this condition on K does not hold, then
K c logloog d.
(2)
Suppose it does hold. Then the steps above go through and we have the existence of our nested subspaces. We also have dy 3 2 for all k l... K, which was needed some steps.
End of proof of existence of nested subspaces.
now fully specify M. The complete set of queried actions by the learner is Ag. and
A a (Bxk....
Va Ak₁
Since dim Bx > 2 > O, we can pick some w E BR OB and let H. = [B..... Bx. Bx+1 +1} with Bx+1 (w). From the proof of the existence nested spaces, we can consider the PE problem instances with MDPs Mw,+ and Mw,- and TH. as target policy. The transition function and target policy are the same on Mw,+ and Mw.-. Since Va E A,, a (w) C,(- because
& (BR), the reward function for any query Ax is 0. Thus, the learner cannot distinguish MM.+ between M from the submitted queries.
The learner has to produce an estimate of T (3. for g 0. But from Lemma E.1
The w) (65,w) TTww (8, = - (3, w) ) w w²
w
M
on M
If the learner predicts positive value for Q (5, w) will incur an error greater than 1 on M and similarly for Mw.+ if it predicts negative value. Even if it randomizes between both, with probability least 1/2 will incur an error of least one of the MDPs. Therefore, the learner can be at most (1, -ouudd.
Therefore, to be more than (1, 1/2)-od we must either be in Case or be in Case and satisfy condition 2 In either case, we have the condition
> c clog log d,
for some constant e and sufficiently large, which gives K 22oog log d), showing the result.
25

---

Published as a conference paper at ICLR 2024
E.4.3 DEALING WITH SWITCHES IN AMBIENT SPACE
In this section we write the missing details of the proof of Theorem 4.4 in Appendix E.4 In particular, assuming the condition on 71+11 is satisfied, we show that we can use Lemma D.3 for the existence of subspace H Bg R of dimension dx+1 s.t.
Vx E Ag+1:
$ (H)
(3)
Fix E 10,1, K 13 and set do d+ and Bg to any d4-dimensional subspace of Rd. Picking
up the proof of in Appendix E.4 the condition on nt+11 | 1| for Lemma D.3 is satisfied.
B& E ( a de-dimensional subspace within R We find an orthonormal basis for Bx:
30,, dd E Rd s.t. BB = (UI,,.., Usa) and of v, = 1, uf V/ = 0 for i + j.
Any vector in Bg can be written as Edet 2m=1 um for some (am) ) Bg is isomorphic to Rd through the linear transformation T' Bx Rd (which can be shown be a bijection) defined as
dg T(
Olm Um)
[an,-.. Oddy Bdd
m==
Letting projn, (x) denote the orthogonal projection of Idd onto Bg, consider
Af+ (T(projB, (æ)) A&+1) Rd
The size of Ab.41 1.4 t1l & |A++1| 1 1 so we can apply Lemma D.3 there exists subspace H dd (I2) s.t.
Vx E A
I
c$C,
Recall de = 2|N/441 and the lemma gives subspace of dimension 211N/41/4 > dx+1 = 2|N/4 but we can reduce the dimension if they do not match.
HP E Ideti.de d. (R) is a 1 dimeensnnsi subspace within Rdd, We find an orthonormal basis for HP:
Buf uoee E RR s.t. HP = (uh, ... up den and (u²) = 1, (uf) = 0 for i *
Define
H (T
Im uf (m) um B& = ERd so c By- We use the notation stm) for vector I to refer the m-th coordinate of a. Since (Ul, Ude. an orthonormal set:
Remark that (w?)
(T (w)) (v5) Σ (m)))(((m) (uf)T 1, i 0, if j.
de
So (v), }} is orthonormal basis for H. which means H Gá, (R) is d++1 dimensional subspace within Rd H is the subspace we are trying to show the existence of, it remains verify the condition 3). The following claim concludes this section.
Claim: Vx A (H).
Proof of Claim: Suppose not: Ex A stt. x (H). Then there exists unit-normed E H B₁ such that h y. Since h BR, we also have proje, (x) v. h, projo, (2)) are both in B3 so
E Od, E R. S.L.
Omy Vras
de >
38,,..,,oe 3d, S.t. proje,
Bm Vmn
26

---

Published as a conference paper at ICLR 2024
and we have
de
projen (1)
Om Bm > 7
Tprojja (T)h) > 7
T(projB E (H")),
since T(h) E HP as h E H. But T(projn (x)) A which contradicts the definition of H?. 0
27

---

Published as a conference paper at ICLR 2024
E.5 ILLUSTRATION MDP CONSTRUCTION
In this section, we provide a high-level illustration of how the hard instance M E M is constructed when 3 and the learner makes three queries per round. The reward vector of the MDP is
0 everywhere except in the 7-hypee-spheriial sector (wr) (see Appendix C of vector B, which is unknown to the learner. The target policy will be constructed in such way that (s, [ aa² w. If the learner can identify w and make query in its hyper-spherical sector (to distinguish between the + and the -), then it can fully solve the PE problem. Therefore the aim of the learner in choosing its queries to identify this vector w.
Round d1 = 3
A
B1
B
D
Figure 3: Round
Round (Figure
A: Three queries 0; ((ss;,,) = a, (i 1,2, 3) are made by the learner.
A B: The three queries with their hyper-spherical sectors (6.) (i 1,2,3) (we only show one side of the sector for clarity).
C: There exists a 2-dimensional subspace Bi that does not intersect the hyper-spherical sectors of the queries which the environment can use to further hide w if B3 does not intersect the y hyper-spherical sectors of the queries, then the queries d; will not be in the y hyper-spherical sector of any point in Bi (in particular wr and cannot identify the + or in the reward).
D: The target-policy मм is constructed in such way that realizability is satisfied with w E B In particular, TM (s;") prooj (s,+) prooj g (a:) is valid because B, does not intersect the sectors of the queries (see Appendix E.2 This choice allows the component of ø the direction of to grow by 1/7 in this will cancel with the ?
discount in the bellman equation and is a key step in satisfying realizability.
Since the orthogonal projection is the same for all vectors in Bi, this definition of the target-policy (allowing realizability to be satisfied see Appendix (E.3) does not reveal any additional information about other than B₁. In addition, or the actions taken by the policy within B, do not need to be specified yet and can depend on queries made by the learner in later rounds.
28

---

Published as a conference paper at ICLR 2024
Since 05-70;" a, -.:,pmu p, (a:) is orthogonal to B1, this construction admits the interpre- tation erasing information along the directions of the subspace B1. Hence, this provides the intuition discussed in Section vector within the subspace B1.
S but is in fact exactly what is required to hide the w
Round 2 d
96
94
B2 (w)
((w) #1
-79
Figure Round
Round 2 (Figure 4). Without loss of generality, we assume the queries made by the learner are within B1 (the MDP is fully identified outside B₁ so the learner can gain no further information from queries outside of B1) and only visualise B₁ circle embedded in the sphere from Figure
E: Three queries 0(s;, a.) a; 4, 5, 6) made by the learner.
F: The three queries with their (2-dimensional) hyper-spherical sectors (á,) 4, 5, 6).
G: There exists 1 1-dimensional subspace Bg (w) that does not intersect the hyper- spherical sectors of the queries. As in C above, if (w) does not intersect the y hyper- spherical sectors of the queries, then the queries Φ; will be in the y hyper-spherical sector of w.
H: Similar to D, the target-policy RM is constructed within B, such a way that realiz- ability is satisfied. particular, TM (s prooj (xt) = = a.) is valid because
B2 (w) does not intersect the sectors of the queries. The reward inside (w)) is char- A
acterised by sign + No queries have been made inside C.(ww) and third round is required to identify the sign + or
This illustration uses three queries per round. In the proof, we formally show that if the number of queries in the first round is polynomial in d, then there always exists a subspace dimension 1//4 that does not intersect the sectors of the queries in the first round. We make similar argument for later rounds to show log log d rounds are required to identify the vector w. See the earlier sections for all the details.
29

---

Published as a conference paper at ICLR 2024
F PROOF OF THEOREM 4.5
F.I MDP CLASS
The BPI and PE problems used in the proof of Theorem 4.5 are characterised by class of MDPs M and target policies II. In this section, we define the class of MDPs M. All MDPs M E M in the class share the same state-space S, action space A, feature map and target policy (for the PE problem) but differ in the transition function PM and reward function ra-- This class of MDPs is similar the one used by Zanette (2021) in the proof of their Theorem 3. Our construction differs in the transition functions which are defined in Appendix F.2
State-space: S {5) UB where 8 is the starting state disjoint from B (i.e. {5) n B Ø).
Action-space: Each state has a single action (which we denote by the state itself for con- venience) other than the starting state 5 which can take actions in B. Formally:
B
if = 8.
A(s)
{8}
i B.
This notation enables that Vs E S(A(s c B.
Feature-map: The feature map maps state-action pair (s,a) to the action a, i.e. V(s,a) a), ((8. a) = a. Since a E B, the feature space is the unit-hypersphere B and [lo(,-))l2 & 1 holds for all inputs.
Target policy: For the PE problem, the target policy æ is the same for all MDPs in the class: it takes action 0 in the starting state and in the other states, there is single action. In particular al = {T) for all M E M.
F.2 INSTANCE OF THE CLASS
Fix K and consider sequence of K nested subspaces of Rd.
Bк Bx-1 C B2 c B1 c Bu R
s.t. dim Bx 0 and fix some w E BR ²B. Set BK+1 (w). Let H (B,..., BK+1} denote the set of nested subspaces (including (w)). This not defined as an ordered set, but for notational purposes the order can always be recovered since the sequence must be nested.
Every MDP M e M is fully characterised by the sequence of nested subspaces H. and a sign + or Hence, they are denoted by MH or MH....
Reward function: The reward function only depends on the vector w and the sign + but we denote
them with the same subscript as the MDP. Specifically it is defined follows: if a & (w) u C-(-w). otherwise.
0,
on M
TH (8.0) =
++(1- y)a w.
0, - 1(1-7)a"
if & (w) u (-w) otherwise.
on M TH. (8, a)
See Appendix C for the definition of hyper-spherical caps C. (w). We sometimes use a w, + sub- script to refer to both MDPs simultaneously.
Transition Function: The transition function for an MDP M .M depends on the sequence of nested subspaces H but not the sign +. The transition function is therefore the same for M and MH.... - If A is subspace of Rd let (T) denote the orthogonal projection of onto A.
See Appendix C for the definition of hyper-spherical caps (w) and sectors (H). The successor state of a state-action pair (8, a) is deterministic and only depends on the chosen action (and not the current state), so we will denote the unique successor state when taking action a by 8 H (a) a, which is defined as:
A if e (B,)) for k = O....,
Proj B (a),
H (a)
/ Aprojew..(0) (a),
if (BxL))((C C,(-w)).
if E (w) u C-w-).
30

---

Published as a conference paper at ICLR 2024
Note that the starting state is not successor state policy trajectory never return to 8. Showing that the transition function and successor states are well defined follows the same steps as showing the target policy is well defined in the proof of Theorem 4.4 in Section E.2
Crucially actions queried in (B&)) C,, for l & K may not reveal Without the knowl- edge of w, the reward function unknown and even with knowledge w the reward function is not fully identified, in which case Mr and MH cannot be distinguished.
F.3 REALIZABILITY
We show that the action-value of any policy (not just the target policy) for any MDP M E M can be linearly represented with the feature map defined in Appendix F.I The action-value of policy ı only depends on w and the sign i of the reward function the MDP, the sequence of nested subspace does not matter beyond
Lemma F.1 (Realizability). For any w ²B and sequence of nested subspaces Hw satisfying the construction from Appendix F.2 let Qh and QH... be the action-value functions of an arbitrary policy πt on M and H respectively. Then it holds that
@H.. (s, + (s. (s. a
Mi
V(s,a),
on M
Proof: Consider Ma,+ and set (s, ({8, aT w. We will show that Q satisfies the Bellman evaluation equations for all state-actions pairs, which will imply that Q(s,a) Qi... (s.
Apply TM Hu to Q at (s, a):
Th (s, TH (s, + 7Q(* (a), n ( (a))).
We consider the RHS of the above for all possible cases.
A
Case 1: If a (B, for some ke e [o, K1, SH... (a) , proj Be-1 (a). Furthermore, must return the only action available in the successor state (and the successor state never 8), so ( H.. (a)) $ (a) and we have:
(1,.+((,00) + 7Q(# (() (a))) 1Q# (a), st. (a))
=ols (a), (a))
ys (a)Tw
r -..prooj (a)w
proj (a)w.
However, recall that w Bk+1- Since proj (a) the orthogonal projection of a: wn projo (a) = w a. Plugging into the above, we have: TMA... (s) = a" w Ø(s, a)T w (s,,)), which satisfies the Bellman evaluation equation.
A Case 2: If E (BK
C.(-))), $t. (a) 1. (a), and before the policy can only take the only action available there, giving:
T h (s, + 2Q (a), m( (a))) = + 105# (a), s (a))
= (a), st (a)) -nst. (a)
- (a)w
projf (a)w
a" Φ(s, Tw Q(s,a),
31

---

Published as a conference paper at ICLR 2024
which satisfies the Bellman evaluation equation.
Case 3: a E (,(w) u C,CCC,))) (-w), the reward is no longer and HH (a) a, and again as before the
policy only take the only action available there so we have:
T TH Q (o), (a)))
+(1 7) w (Q(a, a)
= (1 7)a w + (M(a, a)
(1 7)a w + ra w
a w Φ(s
Q(s,a),
which satisfies the Bellman evaluation equation.
For all cases, Q satisfies the Bellman evaluation equations, so it is the fixed point of the Bellman evaluation operator. In particular, it is the action-value of the policy on MH The argument is identical for M with Q(s, a) -08 a)"
F.4 PROOF OF THEOREM 4.5
First, we know from Lemma ET that all instances of the BPI and PE problem characterised by the MDP class M and target policies satisfy Assumption 4.2 (Q" is realizable for every т) with the feature map d(:;;)) defined
Consider the MDP class described in Appendix F.I and Appendix F.2
in Appendix F.1 The proof follows the same reasoning as in Appendix E.4 We consider policy-free
queries.
We specify the instance with MDP M .M according to the queries selected by the learner. Fix K O. Recall that ny is the number of queries made by the learner round k and _ Ti the total number queries. Let Ag be the set of (policy-free) actions queried by the learner at round k (i.e. [A&] = nz)). Set A& = U A& to be the set of all actions queried up to round k.
The learner is sample-efficient so n is polynomial d. Specifically, there exists some constant > 0 and some integer T such that & ad! Consider N E N s.t. 2 & d < 2 and set d, 2N Note that d_ > d/2. Fix W = exp( (()))" If n & W, we can show the learner cannot solve the PE or BPI problems. Consider both cases:
F.4.1 CASE 1
Suppose W n, then following the same steps in E.4.1
W Wene K K= c' log log
for constant d' >> 0 and d sufficiently large.
(4)
F.4.2 CASE 2
n < W =
& exp(3g(7)d for = 1,..., K. Using the same steps as in E.4.2 in the proof of Theorem 4.4 but with TH, HH, (a)) replaced by $ (a). we can inductively define the sequence of nested subspaces BR c... B₁ characterising wt (E Bx) and used in the successor
state function $ s.t. for k = l,... K, dim B₁ = 21N/111 > 2 and
Ya As,
$ (BR)..
We now fully specify M. The complete set of queried actions by the learner is Ag. and
A (Bx).
Ya Ak.
a
Since dim Bx 2 28 > 0. we can pick
Bx 0B and let H (B1, [B...... Bx. BK41) with Bx+1 = (w). From the proof of the existence nested spaces, we can consider the BPI and PE problem instances with MDPs M and MH - The transition function is the same on M
32

---

Published as a conference paper at ICLR 2024
A and M Since Va E Ak. a $ (w) u C-(-w) because a $ C,( the reward function for any queried action a E Ax is O. Thus, the learner cannot distinguish M M between M - from the submitted queries.
For PE, the learner has to produce an estimate of (3, But
(²) of w)w w w" w
on M
Q= w) ((, ") w w wuTw w-
M
If the learner predicts positive value for (8, w). it will incur an emor greater than on Mr.;:" and similarly for Mr...++ if it predicts a negative value. Even if randomizes between both, with probability least 1/2 will incur an error of at least on of the MDPs.
Similarly for BPI, the learner has to produce a near-optimal policy in the starting state s. But
V Hwst (8) = QM (3, w) = ( (5, w) w w" w
VM H (5) Q.H... (5, w) (5, w) TT) w ww
If the learner outputs policy taking action s.t. a w > 0, it will incur an error greater than on M and similarly for MH
produces an action a s.t. a & 0. Even randomizes between both, with probability at least 1/2 it will incur error of at least 1 on one of the MDPs.
Therefore, to be more than (1, 1/2)-sod,, we must either in Case or be Case and satisfy condition (4) In either case, have the condition
K > c clog log d,
for some constant c > and sufficiently large, which gives K 22 log d), showing the result.
33

---

Published as a conference paper at ICLR 2024
G PROOFS FOR FULLY-ADAPTIVE SETTING
G.1 PROOF OF THEOREM B.2
Fix an unknown MDP M. Consider learning algorithm with the following procedure:
The leamer selects an arbitrary query (s1, a1) s.t. llo(s1, 01)ll2 = (possible by Assumption B.I. The learner receives from the environment the reward rar ($1, a1), the transition function
Step 1:
Par (-s), a1) and evaluations of the target policy Tar for all states in the support of the transition function par( (1).
Step k & d: For i < k. let (8i, az) be the query at round i. Define ei y (a Ta (s')]. Select the query (sk: 0&) s.t
((8;; 0z)
0(sk, ax) (UI, ....... 1)-1) and | = 1.
The feedback to the learne up to round & means the learner has access to Ui.... Pk-1- This together with Assumption B. ensures the query-choice possible.
Denote Uk Φ(8L, ak) T. - parl- and [6(s' AM (s')).
Claim: en $ Uk-1)>
Proof. Suppose the claim is not true, then un E (b-1)) and of (sk, as) = since ((sk;up) ux) (Vi, 1-- Using this,
( [ [ [0(s' (5))))]
72 (ok $(5k, ax)) +(5), (1k d(sk,
1o% Us - 20 osk: ax) + Φ(sk. ax) olkk 0x))
73
(1v 1 1)
7
1
>
which is not possible since o(s, B for all state-actions pairs (s, a), and by Jensen's inequality
( [o(s', (s')) & E (y (s))aal & 1.
This proves the claim.
The claim implies that (oif/e is a linearly independent set vectors. To see why this is the case, suppose it is not true:
H(ar s.t. one of them is non-zero and
Σ
a,44 0.
Let j be the largest index s.t. aj * 0, then
(Eavs) e (Vi, ug-1); 1 aj
which contradicts the claim. So (o.)/_ linearly independent set of vectors.
Under realizability, must have QTN (s; ax) o(s TTT for some 07 and since it is the fixed point the Bellman evaluation operator we also have
Q (si, a;) = r(si, ai) + partt (QTM (8', (s)))
((81,a1)
E, Ex [8((s TM (s)))
Let &+ =
-r=
and +
(5))
(rM(ss,
F Ry (l [0(s (s))))
34

---

Published as a conference paper at ICLR 2024
Combining the realizability assumption with the Bellman fixed point equation with the above nota- tion we have:
( (
Noticing that u; is the ith of Φ - and using that they are all linearly independent, - a square full rank matrix and is thus invertible, giving the unique solution the policy evaluation problem M in terms of quantities known the learner at the d-th round.
G.2 PROOF OF THEOREM B.3
G.2.1 MDP CLASS
We consider the same MDP class for Theorem see Appendix F.1
G.2.2 INSTANCE OF THE CLASS
Consider sequence of d strictly nested subspaces of Rdd
Ba-1 C Ba-1 ... B2 c B1 Bo R
s.t. dim B₁ d k. Since dim Ba-1 1, there is
BR BB s.t. Ba-1 (w)) Let Hw [B,,... BB-1) } denote the set of nested subspaces. Every MDP M M is fully characterised by the sequence of subspaces H. and a sign or Hence, they are denoted by Mr MH
Reward function: The reward function only depends on the vector w and the sign + but we denote them with the same subscript as the MDP. Specifically it is defined
0,
if $ (w(w) (-w)). otherwise.
on MH
TH. (8. =
+(11 - ->)a²
[0,
if a $ (.(w) (-w))
on MH..-: (H,,-(s;a)) 1-(1- - --(1-))a"m w.
otherwise.
See Appendix C for the definition of hyper-spherical caps (w))
Transition Function: The transition function for an MDP M M depends on the sequence of nested subspaces H but not on the sign +. The transition function is therefore the same for MH and _ If A is subspace of Rd, let , (1) denote the orthogonal projection of a onto A.
See Appendix C for the definition of hyper-spherical caps (w) and sectors (H). The successor state of state-action pair (s, a) is deterministic and only depends on the chosen action (and not the
current state), so we will denote the unique successor state when taking action a by s (a) a, which is defined as:
proj (a), 1 proj (a), a
if C, (B&) (Bk+a)) for l 0,...,
H (a)
if (Bx- (1, u (-w))
if C, u (-ww
This is defined in the same way in the proof of Theorem we refer the reader to Appendix F. for an explanation of why this definition is well defined.
Crucially actions queried in C. (B&) (Bx+1) for & & does not reveal w. Without the knowledge of w. the reward function is unknown and even with the knowledge of w the reward function is not fully identified, in which case M and MH... cannot be distinguished.
G.2.3 PROOF OF THEOREM B33
Consider the MDP class described in Appendix G.2.1 and Appendix G.2.2 First, we know from Lemma FT that all instances of the BPI and PE problem characterised by the MDP class M and
35

---

Published as a conference paper at ICLR 2024
target policies II satisfy Assumption 4.2 (Q is realizable for every π) with the feature map o(+,)) defined in Appendix
Defining the subspaces in Hw: Denote the first d queries chosen by the learner by (31, 01 ai)...., ($g-1, ad-1). ) In the feature space, these are 01 ad-1- Let Be the orthogonal complement of (01:-., ak), i.e.
B& (an.... an) {xr =
Va (ai,..., maa.aaa)))))
and Bd-1- The definition of Bş is well defined since the feedback of {a1 ..., ax-1) 1 only depends on Bı...., Bx-1: for = 1,.... 1, SH (a,) p.roj (a;), Tw, (s, = 0. The learner only observes the projection of actions in {a1, -.., ak-1) into B1, B2, ...... B In particular, B₁ can be fixed as any subspace nested B once the learner has chosen the action-query ag at round.
In Appendix G.2.2, we fixed dim Bg - k. If 01 ag are not linearly independent, the di- mension of B3 may be greater than d - k. In this case, we just restrict B& arbitrarily such that the sequence remains nested. In particular, we have dim Ba-1 = 1 and BB-1 (w) for some w E ΔB. Let Hw = [Bi,... Ba-1). Consider the BPI and PE problem instances with MDPs MH and MH..-. The transition function is the same on M M and MH..-.
A
By construction a; $ (Ba-B) for all & d - 1. In particular, a; $ (w) (C,(-w) for i & d-1 and the reward function for any queried action is Thus, the learner cannot distinguish MH... between MH from the submitted queries.
For PE, the learner has to produce an estimate of (*, But
(" = ((,, (" w) - 0(3 w) w -w" - =- on M M
w) w = w²'
"== =
on M
the learner predicts a positive value for Q" (8, w), will incur an error greater than on MH.,- and similarly for M M.. if it predicts negative value. Even if randomizes between both, with probability at least 1/2 it will incur an eтror of at least on one of the MDPs.
Similarly for BPI, the learner has produce near-optimal policy in the starting state s. But
VM M QiH... (5, w) ((5, w) T w w w
Mine-- QiHn.. (5, w) 08,, () TT w
If the learner outputs a policy taking action s.t. a² w > O. it will incur an error greater than on MH..- and similarly for MH..+ it produces action a s.I. at w 0. Even if it randomizes between both, with probability at least 1/2 it will incur an eтror of at least 1 on one of the MDPs.
Therefore, the learner can be at most (1, 1/2)-sood sound for both PE and BPI problems with K &
d - 1 queries. To be more than (1, 1/2))ouu,,,,, n = K > d queries are required.
36


Reviews:
[{"review_id": "mUxTyMrLcJ", "reviewer": "Reviewer_7s3L", "summary": "This paper studies multi-batch reinforcement learning, where the learner is allowed to query the oracle multiple times and adaptively adjust the policies. The goal is to evaluate a policy/identify the best policy. For this problem, the authors show that to achieve sample efficiency, the number of batches K has to grow at least on the order of loglog d.", "questions": "Questions:\n\nSection 4: “we assume gamma\\geq sqrt{3/4}”. Can the authors provide some justification/context for this assumption? It is purely an assumption to make the analysis work?     \n\n\nThe proof of Theorem 4.4 (Appendix D) and that of Theorem 4.5 (Appendix E) seem very similar, in particular, some subsections, such as D.4.1 and E.4.1, seem to be exactly the same. So I was wondering what is the relationship between the two proof? Is one proof just an simple extension of another? \n\nEither way, I suggest the authors avoid copy-past proof so that the proof can be shorter. \n\n\nFor, Theorems 4.4 and 4.5, does the conclusion only holds for a particular pair of epsilon, delta, e.g., 1, 1/2, or the a more general conclusion can be easily obtained?\n\nI don’t quite understand the second paragraph of Section 4, partly because it is a short paragraph with lots of information. In particular, the authors mentioned the established a *matching* lower bound for some problem while the upper bound is d. How is this lower bound relates to the main result?\n\nAt the beginning of Section 5, the authors mentioned that their proof extends that in Zanette (2021). However this paper is not mentioned at all in the rest parts of this Section. It would be great if the authors can compare the idea here with Zanette (2021) in the proof sketch section.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Significance of the contribution: This paper provides a novel lower bound for the number of batches needed to achieve sample efficiency for the multi-batch reinforcement learning problem, which is an excellent contribution. This lower bound shows that this number increases with loglogd, so a constant number is not enough, which is a very meaningful result. It also indicates that, adaptivity is necessary for achieving sample efficiency, and the dependence on d is not negligible. Finally, this result is also inspiring and leaves many questions open, such as whether this lower bound is tight, or how to obtain matching lower bound. \n\nNovelty of the method: The lower bound is constructed based on extending the proof techniques in Zanette (2021), but with novel tools such as subspace packing with chordal distance.\n\nPresentation: this paper is in general well-written and easy to read. I in particular appreciate the proof sketch section, which helps the reader understand the general proof idea.", "weaknesses": "As mentioned before, the paper provides a lower bound for K, but it is not clear whether it is tight.  loglogd is also sometime  considered as a constant is some works, since lnln 10^9 is only approximately 3. \n\nI have some questions on some details of the paper, which is listed in the next section.", "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": "", "extra_scores": {}}, {"review_id": "A9gqxxccq8", "reviewer": "Reviewer_XsoY", "summary": "This paper studies sample efficiency in offline reinforcement learning with linear function approximation. In detail, it shows a sample efficiency separation gap between the adaptive setting (where the data is obtained in multiple batches, and the data obtained later is selected based on the information of the reward or transition induced by previous data) and the non-adaptive setting (where the data can only be obtained based on the linear feature itself, not on the unknown environment). The authors claimed that when the number of batches is less than $\\log\\log d$ where $d$ is the dimension of the linear feature, for any reasonable learner, there always exists a hard environment can not be learned by it efficiently.", "questions": "See Weaknesses section.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The presentation of this paper is clear. \n\nThe theoretical proof is technically sound.", "weaknesses": "The importance of the proposed problem setting is unclear to me. Overall the problem setting tries to suggest that if number of adaptivity is too small (less than $\\log\\log d$), then the $d$ dimension feature space can not be fully spanned by given features induced by the data obtained so far, and the solution $\\theta$ which admits the value function (either optimal value function or value function associated with the target policy need to be evaluated) is not unique, which gives a large value gap when we consider the worst state-action pair we want to evaluate. However, it seems that such a separation gap becomes not important if we admit\n1.  A regret guarantee instead of a worst-case evaluation error guarantee (as defined in Def 3.1). For the regret guarantee, since we only care about the value gap over \\bf{existing} state-action pairs (due to the definition of regret) rather than the state-action pair that achieves the maximum which we may never faced before (again, due to Def 3.1), the nonuniqueness of $\\theta$ will not affect the regret as it affects the policy evaluation error. Is it true that such a lower bound does not hold if we slightly revise the definition of Def 3.1 from $P(\\sup_{a \\in \\mathcal{A}}(\\cdots))$ to $P(\\mathbb{E}_{a \\sim \\mu}(\\cdots))$ where $\\mu$ is some distribution over $\\mathcal{A}$?\n2. Any limitation for the value gap (e.g., the sub optimality gap defined in [1]) or the size of action space $|\\mathcal{A}$, or some coverage assumption which assumes that the obtained data can cover the target policy. To me it seems that if any of the above assumptions hold, then the separation gap does not hold either. Meanwhile, since these assumptions are also considered as mild assumptions (which hold in many settings), the proposed result in this paper is less interesting. \n\n[1] He, Jiafan, Dongruo Zhou, and Quanquan Gu. \"Logarithmic regret for reinforcement learning with linear function approximation.\" International Conference on Machine Learning. PMLR, 2021.\n\nMeanwhile, the problem setting and the hard instance construction are also very similar to that in Zanette 2021, which dwarfs the technique contribution in this work. More comparison between the technique difficulty faced in this work and that in Zanette 2021 are welcomed.", "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": "", "extra_scores": {}}, {"review_id": "cO2za11VXg", "reviewer": "Reviewer_ycxM", "summary": "This paper studies how many rounds $K$ of adaptive queries $n$ are required to learn MDPs with linear function approximation in $d$ dimensions, with 1 round corresponding to offline/batch setting, and $K = n$ corresponding to an online (or more accurately, generative access) setting. \n\nThey provide a lower bound and show that any algorithm which makes poly(d) total queries must use at least $\\Omega(\\log \\log d)$ rounds. In particular, the number of rounds for sample efficient algorithms must depend on the dimension. The proof leverages some recent results in subspace covering (Soleymani & Mahdavifar, '21).", "questions": "1. It wasn't obvious to me why finite horizon linear MDPs can be solved with number of deployments independent of $d$. More generally, is the gap really between finite horizon vs infinite horizon, or between linear MDPs and your $Q^\\pi$ realizability assumptions (4.1 and 4.2)?\n2. Do you expect to be able to improve the lower bound significantly? Perhaps, to log d or even some polynomial in d?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The paper is well written and easy to digest. The results / contributions are easy to pick out, and the proof sketch clearly captures the high-level intuition. The paper also makes clear the relationship to prior / related work.\n- The paper asks an important and interesting question about adaptivity, and the contribution is solid.", "weaknesses": "- In the later version, it would be nice to have diagrams illustrating the hyperspherical cap / sector as well as the policy class considered in the lower bound. \n- I still lack some intuition for how the policy class is constructed, and why it is hard to learn.\n- Perhaps some discussion on whether the lower bound can be improved, i.e., what sort of technical results are needed in order for the current construction to strengthen the lower bound.\n\nMinor typo: on page 21, the definition of $W$ needs to have \\exp. Also, where is $g(\\gamma)$ defined? I see it used in Lemma C.5, but I wasn't sure if it was properly defined anywhere.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)