Deployment Efficient Reward-Free Exploration with Linear Function Approximation
Authors: Zihan Zhang
Yuxin Chen
Jason D. Lee
Simon Shaolei Du
Lin Yang
Ruosong Wang
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement learning
linear MDP
deployment efficiency
Primary area: theory
TL;DR: We provide a computational efficient algorithm to achieve $O(H)$ deployment cost with polynomial sample complexity.

Abstract: We study deployment-efficient reward-free exploration with linear function approximation, where the goal is to explore a linear Markov Decision Process (MDP) without revealing the reward function, while minimizing the number of distinct policies implemented during learning. By ``deployment efficient'', we mean algorithms that require few policies deployed during exploration -- crucial in real-world applications where such deployments are costly or disruptive. We design a novel reinforcement learning algorithm that achieves near-optimal deployment efficiency for linear MDPs in the reward-free setting, using at most $H$ exploration policies during execution (where $H$ is the horizon length), while maintaining sample complexity polynomial in feature dimension and horizon length. Unlike previous approaches with similar deployment efficiency guarantees, our algorithm's sample complexity is independent of the reachability or explorability coefficients of the underlying MDP, which can be arbitrarily small and lead to unbounded sample complexity in certain cases -- directly addressing an open problem from prior work. Our technical contributions include a data-dependent method for truncating state-action pairs in linear MDPs, efficient offline policy evaluation and optimization algorithms for these truncated MDPs, and a careful integration of these components to implement reward-free exploration with linear function approximation without sacrificing deployment efficiency.

Deployment Efficient Reward-Free Exploration with Linear Function Approximation
Zihan Zhang 2 eihanz@cse, wus.uut.. hk HKUST
Yuxin Chen
puxincewhards upenn. edu University of Pennsylvania
Jason D. Lee j @esondlee88@gmel com
Simon S. Du sadu@cs washingt edu University of Washington
UC Berkeley
Lin F. Yang
Ruosong Wang ruosongwang@pku edu. en Peking University
1 linyanggee. uclu edu UCLA
Abstract
We study deployment-efficcnn effficeett reward-free exploration with linear function approx- imation, where the goal to explore a linear Markov Decision Process (MDP) without revealing the reward function, while minimizing the number of distinct policies implemented during learning. By "deployment efficient", we mean algo- rithms that require few policies deployed during exploration crucial in real-worke applications where such deployments are costly or disruptive. We design a novel reinforcement learning algorithm that achieves near-optimal deployment efficiency for linear MDPs in the reward-free setting, using at most / exploration policies during execution (where H is the horizon length), while maintaining sample com- plexity polynomial in feature dimension and horizon length. Unlike previous approaches with similar deployment efficiency guarantees, our algorithm's 's sample complexity is independent of the reachability explorability coefficients of the underlying MDP. which can be arbitrarily small and lead unbounded sample complexity in certain cases directly addressing open problem from prior work. Our technical contributions include a data-dependent method for truncating state- action pairs in linear MDPs, efficient offline policy evaluation and optimization algorithms for these truncated MDPs, and careful integration of these components to implement reward-free exploration with linear function approximation without sacrificing deployment efficiency.
Introduction
In real-world reinforcement learning applications, deploying policies often incurs significant cost. For example, robotics [Kober et al., 2013]. deploying new policy requires hardware-level operations, which can involve lengthy delays. In medical settings [Almirall et al., 2012, 2014, Lei et al., 2012], frequent policy changes are unrealistic, as each deployment typically requires separate approval process involving domain experts. Similarly, in recommendation systems [Thhochhrous et al., 2015], deploying a new policy can take weeks due to mandatory internal testing to ensure based
safety and effectiveness. all these scenarios, while switching policies on instantancous data, as standard RL algorithms require- is infeasible, it is often possible to run
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

many experiments in parallel once policy is deployed. This highlights the need for RL algorithms that learn effective policies while minimizing the number of policy deployments.
Empirically, the notion of deployment efficiency was first proposed by Matsushima et al. [2020]. while a formal definition of deployment complexity was recently introduced by Huang et al. [2022]. Intuitively, deployment complexity measures the total number of policy deployments by an RL algorithm, under the constraint that the interval between policy switches-i.. -ic, the number of tra- jectories collected before switching-is fixed in advance. Under this notion, a line of recent work has developed provably efficient RL algorithms [Huang et al., 2022, Qiao et al., 2022, Qiao and Wang, 2022] in various settings. In the tabular case where the state space is discrete and of small size, Qiao al. [2022] designed an RL algorithm with ((H) policy deployments, where H is the horizon length. Huang et al. [2022]. Qiao and Wang [2022] studied deployment complexity in the context of RI. with linear function approximation (i.e., linear MDP (Yang and Wang, 2019, Jin et al., 2023]). Specifically, their algorithms achieve sample complexity polynomial in the feature dimension and horizon length H, with deployment complexity of OdH)) or (H). Huang et al. [2022] further showed that any RL algorithm for linear MDPs must incur a deployment complexity of at least (H))
Although the aforementioned works provide important insights into the deployment complexity of reinforcement learning for linear MDPs, achieving the nearly optimal O(H) deployment complexity remains challenging. Existing algorithms that attain this guarantee either operate in the tabular setting [Qiao et al., 2022]-which is unsuitable for large or continuous state spaces- rely on strong assumptions such as the reachability assumption [Huang et al., 2022] or the explorability assumption [Qiao and Wang, 2022]. Roughly speaking, these assumptions require that all directions in the feature space can be explored by some policy. Such conditions are quite restrictive and significantly limit the applicability of these algorithms. In particular, they typically assume lower bound on reachability coefficient Umin, and the sample complexity of existing algorithms with O(H) deployment complexity depends polynomially on L In the tabular setting, this assumption is equivalent to requiring that every state can be reached with non-negligible probability by some policy. However, in general linear MDPs, the reachability coefficient can be arbitrarily small, rendering the sample complexity effectively infinite for such algorithms.
To address this limitation, we investigate the following fundamental question:
Is it possible to design RL algorithms for linear MDPs that achieve nearly optimal deployment complexity and polynomial sample complexity, without relying additional assumptions such reachability or explorability?
This question was explicitly raised in prior work [Huang et al., 2022, Qiao and Wang. 2022] and was left as an open problem. Huang et al. [2022] conjectured that achieving OHH) deployment complexity would necessarily require additional structural assumptions like reachability explorability.
Our Contribution. In this paper, we resolve the above question by designing new algorithm for linear MDPs with deployment complexity H. Our algorithm achieves polynomial sample complexity for any linear MDP and does not rely on additional assumptions such as reachability or explorability. Moreover, it operates in the reward-free exploration setting [Jin et al., 2020, Wang et al., 2020a, Chen et al., 2022, Wagenmaker al., 2022, Zhang et al., 202 Li et al., 2024, 2023], where the reward function is not revealed during the exploration phase. This reward-fir free property further enhances the practicality of our approach in settings where reward signals are unavailable or costly to obtain. An informal statement of our main theoretical guarantee is summarized in the following theorem.
Theorem (Informal version of Theorem 4). For reward-free exploration in linear MDPs, there is an algorithm (Algorithm 1) with deployment complexity H and sample complexity polynomial in d, H, 1/c, and log(1/5), such that with probability 1 8. for all linear reward functions, the algorithm returns policy with suboptimality most Here, d is the feature dimension and H. is the horizon length.
Combined with the existing hardness result from Huang et al. [2022], our new result in the above Theorem provides complete answer to the deployment complexity of RL for linear MDPs. It shows that additional assumptions such as reachability or explorability, previously conjectured to be necessary, are in fact not required to achieve nearly optimal deployment complexity.
Throuuhouu this paper, use Ô and ② suppress logarithmic factors.

---

Table 1: Comparison with the most related works.
Sample Complexity
Deployment Complexity
Huang et al. [2022]
poly d, H,
c 1og(
Maiin
Zhao et al. [2023]
Ô H
Õ(dH)
This work
2 1s
2
Related Work
There a large body of literature on the sample complexity of RI.. We refer readers to Agarwal et al. [2019), Chi et al. [2025] for more thorough reviews, and focus on the most relevant work here.
Deployment Efficiency and Other Notions of Adaptivity. The notion of deployment efficiency was first proposed in the empirical work [Matsushima et al., 2020], while its formal definition was first defined by Huang et al. [2022]. Under this notion, Huang et al. [2022], Qiao al. [2022], Qiao and Wang [2022] designed provably efficient RL algorithms in various settings. As mentioned calier, in order to achieve a nearly optimal deployment complexity, existing algorithms either work in the tabular setting, or rely on additional reachability assumption or explorability assumption which we strive to avoid in this work. Zhao et al. [2023] designed deployment efficient RI. algorithms for function classes with bounded eluder dimension. However, even for linear functions, the deployment complexity of the algorithm by Zhao et al. [2023] is Odd)), which is far from being optimal.
The notion of deployment efficiency is closely related to the low switching setting [Bai et al., 2019, Zhang et al., 2020c, Gao et al., 2021, Kong et al., 2021, Qiao et al., 2022, Wang et al., 2021]. We refer readers prior work [Huang al., 2022, Qiao al., 2022] for detailed comparison between these two different notions. Roughly speaking, in the low switching setting, the agent decides whether to update the policy or not after collecting each trajectory. On the other hand, the notion of deployment efficiency requires the interval between policy switching to be fixed, and therefore. deployment efficient RL algorithms are easier implement in practice. The low switching setting was also studied for other sequential decision-making problems including bandits [Abbasi-Yadkori Yadkori et al., 201 1, Bisa-Bianchi et al., 2013, Simchi-Lev and Xu, 2019, Ruan et al., 2021].
Reward-free Exploration. The notion of reward-free exploration was first proposed by Jin et al. [2020]. In this setting, the agent first collects trajectories from an unknown environment without any pre-specified reward function. After that, a specific reward function is given, and the goal is to use samples collected during the exploration phase to output a near-optimal policy for the given reward function. The sample complexity of reward- frre exploration was studied and improved in a line of work [Kaufmann et al., 2021, Ménard et al., 2021, Zhang et al., 2020b] A similar notion called task-agnostic exploration was consider by Zhang et al. [2020a]. Li et al. [2024, 2023]. For linear MDPs, the first polynomial sample complexity for reward-free free exploration was obtained by Wang et al. [2020a]. Later, the sample complexity was improved by Zanette et al. [2020]. Wagenmaker et al. [2022]. Reward- free exploration was also considered in other RL settings including linear mixture MDPs [Chen et al., 2022, Zhang et al., 2021a] and RL with non-linear function approximation [Chen et al., 2022).
Technical Comparison with Existing Algorithms. Finally, we compare our new algorithm with existing algorithms with (H) deployment complexity [Qiao al., 2022, Qiao and Wang, 2022] from a technical point of view. A more detailed overview of our new technical ingredients is given in Section 4. To achieve ((H) deployment complexity in the tabular setting, Qiao et al. [2022] applied absorbing MDP to ignore those "hard to visit" states. In this work, similar ideas are used, though we work in the linear MDP setting which is much more complicated and requires a more careful treatment. In order to design an algorithm with O deployment complexity in linear MDPs under the explorability assumption, Qiao and Wang [2022] showed how to solve a variant of G-optimal experiment design in an offline manner. In this work, we also use offline RL to build exploration policies in linear MDPs. However, the lack of the explorability assumption raises substantial more technical challenges which necessitates more involved algorithms and analysis.
3

---

3 Preliminaries
In this section, we introduce the basic definitions of MDPs and the assumptions used in our analysis. We use A(X) to denote the set of probability distributions over a set X, and [N] to denote the set {1,2. ................................ N for positive integer N.
Episodic MDPs. finite-horizon episodic Markov Decision Process (MDP) is defined by the tuple AS, P. H, Sini), where S x A denotes the state-action space, r S x A x [M]] - [0, 1] is the reward function, 2 P: P.S. A x [M] + A(S) is the transition kernel, is the episode horizon, and 8mi E S is the initial state."
policy π = { : + (A)) kー is a collection of mappings from the state space S to probability distributions over the action space A, one for each time step h E [H] We say that ı is deterministic policy if Tı (s) assigns probability one to a single action for all h and s.
In each episode, the learner starts from the initial state $1 Sini and proceeds as follows: at step 1, ... H, the learner observes the current state 8h, selects an action an according Ta (sk). receives reward rh- = Th (sh: an), and transitions to the next state 8h-1 according to the transition kernel (: (- 8h, a.)) Fixing policy æ, we define the Q-function and the value function as follows: (7. a) = B
a(s E S x A. h [H].
H Σ -h-=h
Σ Li/eh
The (sn, = (s, (0) (T(()) = Ex
Th
8h
The optimal Q-function and value function are defined by:
(s a) = max (7, a), Vis(s) := max max (s))
x
By the Bellman optimality conditions, have, V (s) = max Q% (%, = rn(s, a) + EP (
Linear Function Approximation. We assume that both the reward function and the transition kernel lie within a known low-dimensiona, subspace, setting commonly referred to linear MDP [Yang and Wang, 2019, Jin et al., 2023].
Assumption 2 (Linear MDP [Jin et al., 2023].. Let {Øx (..)) helu) be collection of known feature vectors such that maxs.a I (8, a)lla S 1. For each h [H], there exist vectors
0g E TRd and d measures th (phg ph..... (4) over the state space S, representing the reward and transition kernels respectively, such that:
rn(s, a) (du((, a), 0n), Pa..- a) (dn(s, (m(())
V(s,a) (5.a)E8x 8Sx A, (
(la)
(1b)
||0 l1 S Vd. Moreover, we assume W.ee ((s))pn(()) S Vd any mapping v from S to [-1,
(Ic)
Under Assumption 2, both the reward function and the transition kernel are linear in shared set of d-dimensional features. This structure enables effective dimensionality reduction, especially when d < SA.
Reward-free Exploration. We now introduce the framework of reward- -warrd-free exploration. This setting consists of two phases: the exploration phase (see Algorithm 1) and the planning phase (see Algorithm 5). In the exploration phase, the learner interacts with the environment-withhuu access any reward signal-to to collect a dataset D. In the planning phase, given any reward function (rr he[H] satisfying Assumption 2, the learner is required to output c-optimal policy with probability at least
1 - 6, where is the accuracy parameter and ò is the failure probability.
Deployment-efficcent Reward-free Exploration. We now present the definition of deployment complexity for reward-free exploration.
We assume the reward is deterministic for simplicity. 'W may also assume the initial state $1 is drawn from some fixed but unknown distribution dus, which can be modeled by setting the transition from Sini to follow diai.

---

Definition 3 (Huang et al. [2022]). An algorithm is said to have deployment complexity K in linear MDPs if the following holds: given an arbitrary linear MDP satisfying Assumption 2, and for any accuracy parameter > 0 and confidence level 8 (0,1) the algorithm performs at most K policy deployments and collects I. trajectories per deployment, subject to the following constraints:
(a) With probability at least 1 - 6. for any reward kernel {0h tee H) satisfying Assumption 2, the learner returns an e-optimal policy ι under this reward kernel, i.e,
H
H
E
Σ
Φb (8h. 0n
2
max E
Σ Lh=1
on (Sh, an on
-,
where the expectation B, is taken over trajectories (sh, an 1 generated by executing policy æ.
(b) The number of trajectories per deployment, It, is polynomial in the problem parameters, ie., I= poly (d. H, L 2, a)) Moreover, I. must be fixed a priori and cannot be adjusted adaptively between deployments.
Notations. For positive semidefinite (PSD) matrices and B, we write A 3 BitB is PSD, B dominates A. We define the truncation operator T(A, B) as
T(A == su - 1: (A:
(2)
which represents the largest scaling of A that is still dominated by B. For each h E [H] and v E RRS we define (v) := 1% v, where μı is the transition kernel. We also denote by 1, the I -iimennnail one-hot vector with a in the s-th position.
4 Technical Overview
In this section, we give overview of the technical challenges behind achieving Theorem 1, together our new ideas for tackling these challenges.
The Layer-by-layer Approach. Similar to existing algorithms with O(H) deployment complex- ity [Huang al., 2022. Qiao et al., 2022, Qiao and Wang. 2022], our new algorithm based on layer-by-layer approach. For each layer 1 < h < H, based on an offline dataset obtained during previous iterations, our algorithm designs an exploration policy (a mixture of deterministic policies) for layer h, collect an offline dataset using the exploration policy, and then proceed to the next layer. Since we only use a single exploration policy for each layer, and there are H layers, the deployment complexity would consequently be H. Following such an approach, datasets obtained for previous layers will be used for the purpose of policy optimization and policy evaluation for later layers, and therefore, the dataset should be able to cover all directions in the feature space. Therefore, must carefully design the exploration strategy, so that for any direction that can be reached by some policy, our exploration strategy could also reach that direction up an appropriate competitive ratio. By repeatedly sample trajectories following the exploration strategy, we would get a dataset that is sufficient for the purpose of policy optimization and policy evaluation for later layers.
Dealing with Infrequent Directions. The main technical issue associated with the above approach, is that there could be directions that cannot be reached frequently by any policy. In such a case, it is unrealistic to require such a direction to be reachable by the exploration policy. Existing algorithms with O(H) deployment complexity [Huang et al., 2022, Qiao and Wang, 2022] avoids such an issue by assuming that any direction can be reached sufficiently frequently by some policy, in which case designing an exploration policy that can reach any direction in the feature space is feasible. However, since we do not assume explorability or reachability of the underlying MDP as in prior work [Huang et al., 2022, Qiao and Wang, 2022], we must handle those infrequent directions carefully.
If one simply chooses to ignore such infrequent directions, the error accumulated for handling such directions would in fact blow up exponentially, rendering the final sample complexity exponential in the feature dimension d or the horizon length H. In fact, such an issue occurs even the simpler tabular setting. In the tabular setting, an infrequent direction is equivalent to state-action pair unreachable by any policy, and in order to handle such states, prior work [Qiao et al., 2022] applied absorbing MDP to ignore those "hard to visit" states. More specifically, once the algorithm detects
5

---

some state unreachable by any policy, that state would be directed to a dummy state in the absorbing MDP. Since we only direct states that are hard to visit dummy states, the error accumulated during the whole process would be additive as we have more layers, which gives a polynomial sample complexity. Indeed, this is a high-level approach of the algorithm in Qíao et al. [2022].
On the other hand, for the linear MDP setting without the reachability assumption, handling infrequent directions is much more complicated. In the tabular setting, designing exploration policies is relatively simple since we can simply plan a policy for each individual state. On the other hand, for the linear MDP setting, we need to build the exploration policy in an iterative manner. Given directions that can be reached by the current exploration policy, we need to set the reward function appropriately to encourage exploring currently unreachable directions. More concretely, suppose the A E 000 ] is the information matrix induced by the current exploration policy. for each state-action pair (s, a) with feature e(s, a), the reward function r(s, a) would be set to o(s, a) A "'ss a). We then plan a new policy for the current quadratic reward function, and test whether new policy can indeed reach some new direction, both by utilizing the offline dataset. We proceed to the next layer if the algorithm can no longer find any new reachable direction. The total number of directions found during the whole process can be shown to be small, using a standard potential function argument based on the determinant of the information matrix. To test whether the new policy can indeed reach some new direction, we need to estimate its information matrix A- = E J. again by using the offline dataset.
Note that by assuming reachability explorability of the feature space, we no longer need to build the exploration policy iteratively since the whole feature space can be reached and therefore one can resort approaches based on optimal experiment design. Indeed, this is the main idea behind previous work [Qiao and Wang, 2022]. However, such an approach critically relies on reachability or explorability of the feature space, which is one of the main technical challenges we aim to tackle.
Handling Bias Induced by Infrequent Directions. As mentioned, we heavily rely on the offline dataset obtained in previous layers for the purpose the offline policy optimization (planning for the quadratic reward function) and offline policy evaluations (for estimating the information matrix). Moreover, since we do not assume reachability of the feature space, there are always directions that cannot be reached by the exploration policy, and therefore, it is impossible for the offline dataset to cover the whole feature space. Imperfect coverage of the offline dataset will introduce additional error when conducting policy optimization and policy evaluation, due to the bias induced by infrequent directions. Although the error accumulated during offline policy optimization can be handle relatively easily, since a global argument based on comparing the groundtruth MDP and the MDP after ignoring infrequent directions would suffice, the error accumulated during offline policy evaluation is much more severe since the estimated information matrices would be used for deciding the next quadratic reward function. If not handled properly. the error will accumulate multiplicatively as we proceed to the next layer, rendering the final sample complexity exponential. Again, we note that by assuming reachability or explorability of the feature space as in prior work [Qiao and Wang, 2022], such an issue will not occur since the offline dataset would cover the whole feature space.
To handle such issue, our new idea is to make sure the error of offline policy evaluation for estimating information matrices is always multiplicative w.r.t the information matrix to be evaluated. More specifically, during the evaluation algorithm, if we encounter some state-action pair with feature o Φ(s, a), to ensure a multiplicative estimation error, we would add σó to the evaluation result A only when o A 4-1 " is small. However, this will introduce another chicken-and-egg situation: without knowing the groundtruth information matrix A, it is impossible to test whether Ø A - is small or not. To handle this, we use another iterative process to estimate the information matrix. Initially, the information matrix is set to be the identity matrix. In each iteration, in order test whether Φ A A- is small or not, we use the information matrix A obtained in the previous iteration, adding up pΦ T for those & that passed the test to form the new information matrix, and proceed to the next iteration. We stop the whole iteration process if the two information matrices obtained in two consecutive iterations are close enough in a multiplicative sense. By using another potential function argument based on the determinant of the information matrix, it can shown that the iterative process stops with small number of rounds. Such an idea is another major technical contribution of this paper.
Handling Dependency Issues by Independent Copies. As discussed ealier, our final algorithm involves two iterative processes, and since the results of different iterations all rely on the same offline dataset, these results are subtly coupled with each other. Fortunately, such dependency issues are relatively easy handle, as we can simply make independent copies of the offline dataset by

---

following the exploration policy and repeatedly sampling trajectories with fresh randomness. We denote each independent copy as a sub-dataset, which will be explained in more details in Section 5. Our final algorithm is a careful combination of all ideas mentioned above.
5 Algorithms
In this section, we describe our algorithms for achieving Theorem The parameter settings are postpone to Appendix A due space limitation.
Datapoint and Sub-dataset. The typical approach for handling linear MDPs is to treat {dx(s, a), 5} as datapoint, where for state s, & is the next state obtained by taking action at level h. In our algorithm, we further assign weight w each datapoint to balance its importance in the whole dataset. As a result, one datapoint in our algorithm has form (s, a), 3, w.. We remark that the weight w is determined immediately once {0r $} is collected.
In our algorithm, we conduct linear regression for multiple times, each time using group of N independent datapoints. Here, N is a parameter to be decided. We denote these N independent data- points as sub-dataset, which has form {Ør., = 0% (s,, a.), Sh,s, A ' To keep the statistical independence between different linear regression instances, we collect multiple independent copies of sub-datasets, so that the data used by different linear regression instances are independent.
Exploration phase: Algorithm 1. In the exploration phase, our algorithm collects samples in layer-by-laye manner, and each layer uses single deployment. In each layer, we assume that enough information about previous layers has been learned and focuse on learning the current layer. For the current layer, Pol cy Des gn. is called to design the exploration policy based on existing samples, and Policy-Executii on is called execute the exploration policy and collect new samples.
In each call of Pol volicy-Design. there are m offline policy optimization sub-problems (see Line of Algorithm 2) and offline policy evaluation sub-problems (see Line 11 of Algorithm 2). As mentioned, we collect multiple independent copies of datasets, and use a group of independent copies datasets solve each sub-problem. More precisely, we collect (2m² + 1) Hi independent copies for each dataset to solve the 2mH sub- aub-problems, where each dataset consists of N datapoints. Due to page limitation, the detail about how to collect samples is deferred to Algorithm 7 in the appendix.
Policy-Design (Algorithm 2). Given datasets in the first sider learning the h-th layer. The learner first designs reward function with form (s, <- min { oo (s,.)AAA1 (x,s a). 1}, where A is the current information matrix. We hope to update A as Anew Erroa [ + Aold:
layers, now we con-
where Told is a near-optimal policy w.r.t. the reward rold = min 00, A Φb, 1). By iteratively running this process, we will obtain some A so that max, E, [min[ A -b 1}] is small. However, as discussed in Section 4, due to the infrequent directions, it is inappropriate to add E.,.. [ to directly. Here, we need to truncate the infrequent directions in the distribution Vold and evaluate the truncated matrix with the offline datasets. Below we explain how to address this by Algorithm 3.
Matrix-Eval (Algorithm 3). In Algorithm the input is policy and group of datasets. The goal is to truncate the infrequent directions under æ, and evaluate the information matrix after the truncation. To describe the high-level ideas, we assume D is distribution over IRd and the goal is to truncated the infrequent direction under D. For simplicity, we assume that D is known, so that one can compute A- [o ] and those infrequent directions @ such that o A A is large. The next step is to re-seale Φ, i.e., replace & with w(Ø) such that w 2 (0)Ø T A & is small. However, after
truncation, the new information matrix would be Anew = Eg (())))))))) " 3 A, which means that a frequent direction under might turn to be an infrequent direction under Anew. A straightforward idea is to repeat this process until A converges to some fixed point. Let F(A) ESnD [T(oØ" ceA)] where C₁ is the threshold for truncation and T is the operator defined in (2). By iteratively applying F()) and noting that F(-) is non-increasing and the set of bounded PSD matrices is compact, the sequence (F(" truncation is needed and hence, infrequent directions no longer exist. One might be worried that the zero matrix is also fixed point of F-)) in which case the truncation is meaningless. Fortunately, (A*)-1
will converge to some A that F(A*) = A', in which case no more
by choose e₁ properly large, show that Pr ( 2 c1] O(e), where epsilon
7

---

is the desired accuracy. This means only small portion of directions are truncated. When D is unknown, we could draw samples from D estimate Ep|T(áø' process. Incorporating this idea with linear regression, we devise Algorithm 3 and 4 to evaluate the truncated information matrix efficiently.
(o)ooTTAA .A)] and run the same iterative
In the planning phase, we employ standard backward planning for linear MDPs (c.g., Algorithm Planning and Algorithm 6 slanningg-P See Appendix D for more details.
Computational Efficiency. We remark that the time complexity of our algorithm polynomial in d, H, 1/cc and the number of actions A. In comparison, the algorithm in Qiao and Wang [2022] computationally inefficient, and the algorithm in Huang et al. [2022] suffers time complexity depending the realization parameter. We refer the readers to Appendix E for more details.
Algorithm Exploration
1: Initialization: Dj + 0, An t for E [H];
2: for h 1,2, 1,,,...... do
3: {(74h)mm A, A Dalicy-Design (h, (i) 11 (Ar)re(-u)):
4: I/ Roll out the policy and collect the datapoints. Each (i) constructs sub- dataset for the
hithh layer;
5: (D) [1] + Pol Pollcc-Executal (h, pm An):
6: end for
7: return: (2m² + 1)} and hetan
Algorithm 2 Policy-Desige
Input: horizon [H]. block matrices (A, (A,rre/h-1)> sub-datasets &,,),, Ar,
for r E [h- 1] and j E [2m²]; Initialization: A% <I:
for 8 1,2,
do
(s, a) minf@a(s, a) - as, for all (s,
(s, 0 for h and all (s,a); = frtreem, (m,, + f), s,, + l), ,,,
(a of Planning-R(h,
[ (s (m, (Ar
11 Let V7,(a b) denote -- & boor 3, and 81;
fm), Ar, (01-(m(m-mm) 1)m-1 bm) (m)))mm())r((n-)) 11 Feed independent sub-datasets to Mat centrix-aa xitrix-Eval: (A An + Matrix Eval (h, (A brehh-1,, T D):
D k f0r,((ee (el=(((11))))) 111-1mmm11- 11: 6m), (,,((, 1)m
Af. A/ Ai.
end for
return: ( and Å < AT.
Algorithm 3 Matrixx-Eee
1: Input: horizon E [H], block matrices [Á, 1h-1 policy æ, sub-datasets
{Ør, 5 (f), (...
2: A +- I:
do 4: // Estimate the truncated matrix with independent sub-datasets;
3: for 1,22
5: Fo + T-Truncated-Maten Matrix Eval (h, n. [Ar 1h11 A, (0r,(i),8r,06) (.))))))))))))))e-eeee).))
6:
if F. 2z
SI A then
break and return Fo + 22 L
7:
8:
else
+ Po:
9:
10:
end if
end for

---

Algorithm 4 Trruncated-Matriiee Eval
1: Input: horizon h, policy N, block matrices [A,)+==) truncation matrix sub-datasets
{0r, (r,, 1r..)
2: Fs(() - [ Th. (T) (s. (s)),, for E (aM-))
3: for =
do
X, - --E:1 X D-,0 =
4:
5:
for (5r-i,ien do
6:
àt (s,
if 1 then
7:
8:
(+(5) 00:;
9:
else
(s) < TT X,
N2 ((11(,)) 2xA;
11: end if
12: end for
13:
end for
14: return: : Fo: Fi (sini):
Analysis
In this section, we present the formal version of the main theorem and sketch its proof. Theorem By running Algorithm 1, the learner collects samples so that with probability 1 for any reward kernel (0p [ satisfying Assumption 2, the learner can return an e-optimal policy π with Algorithmm 5, i.e.
H Σ Lh=1
H
th (sh, 0n
2 max E x/
Σ
oo (sh, az)
c.
1=11
Moreover, Algorithm uses O(H) deployments and Ô
8 g15
samples.
Although achieve reachability-indeeendee sample complexity, the current dependencies H and 1/c are far from being optimal, especially compared to the bound Qiao and Wang [2022]. The reason is that the technical difficulty changes significantly when allowing dependency reachability parameter. The core challenge in deployment-efffcien linear MDPs arises from the fact that the linear regression problem becomes ill-conditioned when the reachability parameter À is very small. In the reachabilityddeeeddent methods (e.g., Qiao and Wang [2022]). one can pay O(1/x*) episodes to collect samples {o: such that the information matrix Σ d. is cell-conditioned. Meanwhile, in the sachability-indepedder methods, need to identify the ill-conditioned directions and avoid these directions in linear regression. This step would be even harder given the constraint in deployments, which requires offline evaluation of the information matrix.
the
Proof of Theorem 4. We first analyze the deployment complexity and sample complexity.
Deployment complexity. For each h 1,2,..., H. there is one deployment in Line 5. Therefore, the number of deployments H.
Sample complexity. Algorithm calls Algorithm H times, each requiring (2m² + 1)N trajecto- ries, resulting in total sample complexity of H H (2m² + 1) Ô 1
To finish the proof, we use the following lemma to prove the optimality the learned policy. See full proof in Appendix C.9
Li
Lemma 5. With probability 5, for any reward kernel 0 E {0n) satisfying Assumption
Planning (0, (or. 8n.s, An. W (An hreH) (see Algorithm 5) returns an e-optimal policy, where ( Sha An, N Jhe(s) and (Án hreAH] is the output of Algorithm 1.

---

To prove Lemma 5, central lemma is introduced as follows, which states that the output sub-dataset of Algorithm 1 could efficiently cover all policies.
Lemma 6. Recall that A is the block matrix outpud by Pol Palicy-Desis gn in Line 3 in the 7-th iteration for r E [1. With probability 1 & à 2or any sub-dataset of Algorithm I for the h-th layer (oh,i, Sh,i, An.i)REIN) we have
1].
(i). max, PIæ 10% A Φh 1, A, o. 1,, [h 1]] 1 sir= for all h E [H]
(ii). Ei= or + =I N An all E [H];
8m
(ii). TT, on, S f1 for all E [H] and i [N].
In proving Lemma 6, we use induction to construct truncated MDP with information matrices [Ar1r21- The three conditions in Lemma 6 serve the following purposes:
(i). To properly bound the truncation probability.
(ii). To ensure each A, is well-covered.
(iii). To rescale each sample for compatibility with the current information matrix Äz
The proof of Lemma 6 is postponed to Appendix C.1 due to space limitation.
7 Conclusion
In this work, we design new RL algorithm whose sample complexity is polynomial in the feature dimension and horizon length, while achieving nearly optimal deployment complexity for linear MDPs. Moreover, our algorithm works under the reward-free exploration setting, and does not require any additional assumptions on the underlying MDP. our new algorithm and analysis, we propose new methods to truncate state-action pairs in data-dependent manner, and design efficient offline algorithms for evaluating information matrices. Given our new results, an interesting future direction to generalize new techniques to other RL problems. For example, for function classes with bounded eluder dimension [Wang et al., 2020b, Kong et al., 2021, Zhao et al., 2023]. would be interesting to design RL algorithm with nearly optimal ((H) deployment complexity and polynomial sample complexity without relying on any additional assumptions.
Acknowledgments
YC is supported in part by the Sloan Research Fellowship. the ONR grant N00014-22-1-2354 and the NSF grant CCF-2221009. JDL acknowledges support of Open Philanthropy, NSF I15-2407304, NSF CCF-2212262, ONR Young Investigator Award, NSF CAREER Award 2144994, and NSF CCF-2019844. SSD acknowledges the support of NSF 101700 NSF DMS-213411 NSF CCF-2212261, NSF IIS-2143493, NSF CCF-2019844, NSF IIS-2229881, and the Sloan Research Fellowship.
References
Yasin Abbasi-Yadkonf Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24, 2011.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle WA, USA, Tech. Rep, 32:96, 2019.
Daniel Almirall, Scott N Compton, Meredith Gunlicks-Stoesse Naihua Duan, and Susan A Murphy, Designing a pilot sequential multiple assignment randomized trial for developing an adaptive treatment strategy. Statistics in medicine, 31(17):187-1100, 2012.
Daniel Almirall, Inbal Nahum-Shani, Nancy E Sherwood, and Susan A Murphy. Introduction to smart designs for the development of adaptive interventions: with application to weight loss research. Translational behavioral medicine, 4(3):260-274, 2014. 2014.
10

---

Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances Neural Information Processing Systems, 32, 2019.
Nicolo Cesa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems, 26, 2013.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. On the statistical efficiency of reward-free exploration in non-linear rl. Advances in Neural Information Processing Systems, 35:20960-20973, 2022.
Yuejie Chi, Yuxin Chen, and Yuting Wei. Statistical and algorithmic foundations of reinforcement learning. arXiv preprint arXiv:2507. 2025.
Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost, arXiv preprint arXiv:2101. 00044,, 2021.
Jiawei Huang. Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie Yan Liu. Towards deployment- efficient reinforcement learning: Lower bound and optimality. arXiv preprint arXiv:2202.06450, 2022.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conferennee on Machine Learning, pages 4870-4879. PMLR, 2020.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Mathematics of Operations Research, 48(3):1496 1521, 2023.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865- 161-891. PMLR, 2021.
Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The 2013.
International Journal of Robotics Research,
Dingwen Kong, Ruslan Salakhutdinov, Ruosong Wang, and Lin F Yang. Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint arXiv:2106.07203, 2021.
Huitan Lei, Inbal Nahum-Shani, Kevin Lynch, David Oslin, and Susan A Murphy. A" smart" design for building individualized treatment sequences. Annual review of clinical psychology. 8(1):21-48, 2012.
Gen Li, Wenhao Zhan, Jason D Lee, Yuejie Chi, and Yuxin Chen. Reward-agnoste fine- tne-tuning: Provable statistical benefits of hybrid reinforcement learning. Advances Neural Information Processing Systems, 36:55582 36:55582-55615, 2023.
Gen Li, Yuling Yan, Yuxin Chen, and Jianqing Fan. Minimax-optimal reward-agnosicc exploration in reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory, pages 3431-3436. PMLR, 2024.
Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, and Shixiang Gu. Deployment- efficient reinforcement learning via model-based offline optimization. arXiv preprint 2042::20000036677, 2020.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Interna- tional Conference on Machine Learning, pages 7599-7608. PMLR, 2021.
Dan Qiao and Yu- Yu-Xiang Wang. Near-optimal deployment efficiency in reward-free reinforcement learning with linear function approximation. arXiv preprint 2101022200007011, 2022.
11

---

Dan Qiao, Ming Yin, Ming Min, and Yu- Yu-Xiang Wang. Sample-efiicient reinforcement learning with loglog (t) switching cost. In International Conference on Machine Learning, pages 18031-18061. PMLR, 2022.
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 74-87, 2021.
David Simchi-Levi and Yunzong Xu. Phase transitions and cyclic phenomena in bandits with switching constraints. Advances in Neural Information Processing Systems, 32, 2019.
Georgios Theocharous, Philip S Thomas, and Mohammad Ghavamzadeh. Ad recommendation systems for life-time value optimization. In Proceedings of the 24th international conference on world wide web, pages 1305-1310, 2015.
Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389 2012.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward- free rl is harder than reward-aware rl in linear markov decision processes. In International Conference on Machine Learning, pages 22430-22456 PMLR, 2022.
Ruosong Wang, Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 1777718667766, 2020a.
Ruosong Wang. Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6133 2020b.
Tianhao Wang. Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems, 34:13524-13533 2021.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International conference on machine learning, pages 6995-7004. PMLR, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33:1 1775--176666.1111111111111111111 1766, 2020.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-based reinforcement learning with linear function approximation. Advances Neural Information Processing Systems, 34: 1582-1593, 2021a.
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 33:111344 2020a.
Zihan Zhang, Simon S Du, and Xiangyang Ji. Nearly minimax optimal reward-free reinforcement learning. arXiv preprint arXiv:2010.05901, 2020b.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia seference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198 15207, 2020c.
International Conference Machine Learning, pages 12402-12412. PMLR, 202 Zihan Zhang, Simon Du, and Xiangyang Near optimal reward-free reinforcement learning. In
Heyang Zhao, Jiafan He, and Quanquan Gu. A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation. arXiv preprint arxhv:2311.15238, 2023.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main contribution of this work developing a deployment efficient algorithm for linear MDPs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the conclusion section, we have discussed the limitations of the work and possible future directions to overcome these limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification:
All assumptions are clearly discussed. Full proofs also provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA].
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA].
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: :etcps::/nieee //npss/iipp.././ cc/
publ c guides/ CodeSubmm ss onPol (iycyyyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. cc/ unips.ccppubicc. heabbicccgiidss CooeeeeeeSSeeeeee Sumeeuubmmii.. ssssnnooooo ooyicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA].
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttprrs///////ss///e//
Answer: [Yes]
Justification:
The research conforms with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: This work focuses on the fundamental aspects of reinforcement learning, and there is no foreseeable societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer:[NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer:[NA].
Justification:
This paper does not existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers' raw w thcode com/ dat tes has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /tteerrrss.cc//ooeeeeeeeeeeee Sacc/ooffeeeneees / 2025/ LLM) for what should should not described.
19

---

A
Additional Parameter Settings and Notations
Assume d, H 2 40,
S
40
1
Set x
10004-F1 H
fi
320dH
S
10000a f
loa H?2
2 H m 32000a' Hº
100000.2
10 a"
log
am
For a symmetric matrix and PSD matrix We also present a table of notations as follows.
B. we write
|A| 3 B iff
B
A 0 and B A z O.
Table 2: Additional Notations.
Notation
Comments
a))))
the transition probability for the triple (h, 8,
(s)
the reward expectation for the triple (h, s,a)
(1(8,a)
the d-dimensional feature vector for the triple (4, 81,8,0) a)
Ph
the probability transition kernel such that Pa("), 8.0) jaon (8.0)
(v)
the d-dimensional payoft vector defined as p4 v the truncation function
T(
N
the number of datapoints in one dataset sample from the 7-th layer
(0y, 8y, A}
(r, 87,ds Ar
independent dataset from the 7-th layer the regularization parameter
C
the discretization parameter
()
the concentration event for and value w.r.. independent dataset the concentration event for ø and matrix value f w.r.t. an independent dataset
B Technical Lemmas
Lemma (General Equivalence Theorem in Kiefer and Wolfowitz [1960]). For any bounded subset X Rdd there exists a distribution KC(X) supported on X, such that for any >> holds that
max ZEX
(CI+E, Exy+Exx)) lov 1) s.
Furthermore, there exists a mapping T., which maps a context X to a distribution over such that
T (cI+ Ey-rsx))lv 1)> - S 2d.
max
#EX
When supp(X) has finite size, (X) could be implemented within poly((supp(XX),, log(1/)))) time.
Lemma Assume 0 S x 0.1. Lei A ÇI. For each 1, let DP be a distribution over R&
satisfying that
BonDi [min {Trace (6o (A---1-1),
(4)
and
A > A + Eg (00
Then we have that
log(det(A")) log((ee(AA)) > nK
4
for any 1.
Proof. Fix i 2 1. Note that (4) is equivalent to
Eg [min (AA--1--1 16, 17} 2
20

---

Let W = Ba T(ØoT [(oo",A'-1) I EENDI [ By definition, it holds that W = A and
W + A 3 2
We then have that
log(det(A')) Log(det(A* 2 log(det(A + W)) log(det(A
log + (A (1
log (A+1 [T(dØ] T, , (1²-1)-1/2)
Bi
[Trace(T(oo)' T, , -A--)((-11)-1)
IV
The proof is completed by taking sum over i from to n.
B.1
Concentration Inequalities
Lemma 9. Let X1, X2,.., Xn be a group of zero-mean matrices such that -A 3 X; 3 with probability for all i E [N]. Let wi, w2, Wn. be a group of reals. With probability 1 5.
12
W - 22
Σ
w (log(d/88) maxx [uy log (2d/8)A
1
n
W;X,; 2
Σ
wf log log(2d/6)A + max |uo A)
Proof. Without loss of generality, we assume = I. For tt max; [wv] define
Σ w ))
Eg = E Trace
exp
t
WiY;;
28
1=1
1=1
Then we have that
E
Eu
X
11
&
<
E
Trace
exp
log ([]] + Σ
X; 212
Σ will
iml
2m1
E
Trace
exp
(og(Blexp(tuxxxx))XXXX) X1x 26
Σ X; 26
Σ
wil
k-1 W,X,
A-1
< E
Trace
21
FA-11
where the first inequality is by Lieb's inequality (see Theorem 3.2, Tropp [2012]) and the second inequality is by Fact 10, 11 and 12. As result, we learn that E[E,] < E[E,] = d, which means that with probability 1 8/2, the maximal eigenvalue of Σ W, is most 2 E wi 1og(2d/8)
2 max; [wm] log(2d/)) (). Similar arguments work for the other side. The proof is completed.
Fact 10. Assume X is a stochastic symmetric matrix and I x X < and E. X = 0. then holds that
E E((xp(tX)) - exp(2t²)I
for any 0 L.
21

---

Proof. By definition, we learn that
(tX)*
exp((X)
=
Σ
h!!
k=0
Taking expectation we learn that
E
X
t
E elexp(tX)]
I+
I+
exp(2t I.
k!
k!
k=
Fact 11. Assume X and Y are two positively definite matrices such that X Y. then holds that (Xg 3 lYg(Y).
Proof. Note that for any m 2 0, it holds that
m
log(X) = log( X + +m]]
(X + (+(I-=1 -dd,
-
0
log(Y) = log(Y' Y + +mI) Jo
(Y + tI] 'tdt.
Because X = Y, it holds that - -(X + tI) コ -YY + =I) for any t 2 O. Then for any m 2 0,
log(X) ) = log(T)) + log(Y + ml]) (X + ml).
Fix A 0 and choose m 2 X || We have that log(Y + mI) 3 log(m(1 + A))I and log(
ml) = log(mm( A))I. As result, for any À > O. we learn that
+ A T-x
log(X) log(Y) log
I,
which implies log(X)= N log(Y).
Fact 12. Let X,Y Y be two symmetric matrices and X It then holds that
Trace (exp(X + Y)) < Trace (exp(Y)).
Proof. It suffices to verify that Trace ((X y) < Trace(Y*)) for each & 2 which direct result from Löwner-Heinz theorem.
C Missing Lemmas and Proofs
C.1 Proof of Lemma
We will prove by induction over the layers. Fix h E [H] and assume the three conditions in Lemma holds for the first 1 layers. To facilitate the presentation of the proof, we first introduce the notion of truncated MDP.
We define the truncated MDP M,-1 by redirecting all state-action pairs (s, a) to a dummy state at level т if ot (s, a) T, (, a) > 1 for t E [/ 1]. More precisely, trajectory {[s,, a,) ) under the original MDP M is mapped to {(s ..... (Sk, ax), z.... under MR-1. Here A < h is the smallest integer such that of (sk, an))))) ax " (s ax) > and the dummy state. If oi (x), (Sk, a&) & for all k [/. 1). the trajectory is unchanged.
Truncated MDP.
In the following, we re-define [E[-] and Pr[-] to be the expectation and probability under M₁-1- We verify the three conditions follows.
22

---

Condition (). By Lemma 15, with probability 1
SH. max, Ex [min(o] A oh. 13] - sHz
which implies that max, Pr, [ A db 1] I 8#2 The proof is finished by noting the above inequality in the truncated MDP M,-1 1 is equivalent to (i).
Condition (ii). By Lemma 19, with probability 1 16 it holds that Σ OR + 2
N. An for all sub-datasets (øn,i, Sh,6 An, 1 8m
Condition
(iii). To verify the third condition, suffices to note the definition Anj
min
(See Algorithm 7).
The proof is finished.
C.2 Statement and Proof of Lemma 13
Lemma 13. Fix h [H]. Recall x 1008' 2 60v md mog
Define Fa(s)
N
Fa(s) = T(Øn(s, Th (8)) (a (1)) For h 1, 2,..., define F F5(s) EesNP.....Cs (1+1((s) 16 (s, (s))A, o(s (s)) - 1]] and Fo Fi(s1) (i
Let Fo be the output of the Algorithu with input A and a group of independent sub-datasets (0r,) Br,d, Ara)rejh-11)iE(N) have that
(1-3Hx)B. 3 Po = (1 3Hz) 4Hd
Proof. It is obvious that (s) is PSD for any proper and 8. We prove by induction that (1 -1-3(A - r) (s) (s) (1 3(h F.) + 4(h T)xA
(5)
for any 1 5 r S h and E (6-11:)
For = h. we have that (x) (*) for any E S. Fix & 2 2 and assume that (5) holds for t
For such that d T ((s > 1, we have that Fe-1(s) = Fi-1(s) 0. where (5) holds trivially. Below assume Φe 1(,, ( ø(s, Te- (s)) 1 1. Recall that + 21. By definition, we have that for s E (36-23)221
X, = Im
N
fs-1(s) = (s) x.'
Σ
2rA
2=1
E (e(s)) + (4) (8) + 2nA
(1)
- [F(()) + 2 (s) + + 2xA
= F 422 + +
2
(6)
where
N
A (1) (s) = 00-1 xx-1
Σ
Xa F Eg' [e(ss)]
i=1
N
= 0 x-
- ((())
P((:):
(7)
A (s) = Egg Pp (60) Bi(ss) Bi(s)- Fi(s)
(8)
By the induction assumption, we have that
0 3 (1 - 3(h ())) = Fe(s) (1 3(h F)2)F(()) + +4hh T)zA 2A.
23

---

By Lemma 14, with probability 1 16m it holds that
6
md log dH
(s) 600
cb
A 2x:;;
(9)
dl md log(
2 = V
2xA
(10)
N
For the second term A 2-1 (8), by the induction condition, we have that
E- (s) = 3(h
[Fe(s') + 4(h - E)xA
3(h () + 4(h C)xA;
(11)
2 (s) - ( - ()xBBs 160) [F(()))
-(h ()xFe-1(8)
(12)
Putting all together and noting that x - 10nd/f we learn that
F(-1(8) Fc-1(s)
= 2rA - + 4(h - ()xA)
I 3(h 1ich-6+130 -11)))11FF--0 4(h 1)rA
(13)
Fi-1(s) FE-1(s)
=A - 3(h - ()=F(-1(5)) + 2nA
= 3(h + ()));
(14)
The proof of (5) is finished.
Note that
F6 F6 = (sini) Fi (sini).
Using the induction condition, for any S it holds that
0 W (1 3(H (s) = F (s) N (1 + 3(H 1))) + 4(H - 1)xA = 2A
As result,
F (sini) - Fi (sini) 3 3(h (sini) + 4(h 1)xA
3(h 1)=Fo 4(h 1)xA;
6 (Sini) - (iinni) - 3(h 1)
-3hh 1)xFo.
As result, we obtain that
(1 (-- Fo J Fo 1 (1 3hx) + 4hrA.
The proof is finished.
C.3 Statement and Proof of Lemma 14
Lemma 14. Fix f S + d such that 0 < f(s) = A, S for some PSD matrix A. Let (or, Ar. I. be a sub- from the T-th layer. Assume (0r, 87,4, Ar is independent
of f. Let X, = N X2 0r + zI. Then with probability
I6mH
N
mdlog
HP c5
0 JuT f Tx Σ
22 of (B 3 <60
A
(15)
N
holds for any o E R22 such that ||0112 S 1 and oJ 1 1.
24

---

Proof. By the induction assumption (i) and (iii) about the sub-dataset fōr,s, 37,8, br, in Lemma 6, we have that X = N A for S r S h 1 and max; & 1
Dr.s S f1. By Lemma 17, with
8m
probability 1 H6 we have that
④ 1r - 10 xx,,1 Σ X (r
dH 161 Txx="O od log(
dH Ed
) + 8 max o "0, Xx o. dlog
+ s
Ed
md log
dH
= 1
N
C.4
Statement and Proof of Lemma 15
Lemma 15. Recall the definition of Ån Ag in Algorithm 1. With probability
it holds that
8H
max min 0y An on. 1}] < max [0d (3m/))
4
2d
c
B
++
S
3
fi
8H2
Proof. Recall the definition of 8=0 { and {A in Algorithm 2. It then holds that Af. 15-1 + Mf, for 1 S < m. By the stop condition in Line 6, we have that Af. > Åf. for 1 < é m. Let yf max, E, [min [ (A()) 1}] Then yf is non-increasing in because Let y = y max; Er min o A on 1}}.
A is non-decreasing
By Lemma 16 and Lemma 18, with probability
8mH m
8H
Exe min Trace min
fi 0 (At))-
Φnh 0/ (A (A(-1)-1) )
11]
E [min (Traco(ds (A ( 1}]
pr [ (Af) -1 fi]
d
> Exe TainfTraceddddooo T ( 13]
[i 3Hx)
2 v/ - B
S1(1 - 3Hxr
2 y B
(16)
fi -3Hx)
Case i: y B ([1-3nz)
d
4. Recall that AG, = - A for <8 m.
By Lemma 13 have that
fi
(1 - (H3))
min
(V Φ5 (A:))
1 1
0 T
- A
On the other hand, by (16), we have that
fr
[1 ( ) . > 4
(1 1-3Hr)y
y
(1 E. min
Trace
min
2
0 (Af)))
10
By Lemma 8 with the Dj as the distribution of Φn v(1 (11331) -H-H) min {v 07 (i(ch)) 1) under
n and
# < 0.1, we have that
log(det(A/)) log(det(A
my
(17)
40
25

---

Using Lemma 13, we have that A4, N 31 and thus log(det(Ag)) I dllog3mm.. On the other hand, my
we have that (A)) = d log (c), which means that that y S
40 I dlog(3m/C) Therefore, we have
40d Log(3m/
S 8HZ.
Case ti: y B /(1-380) 4'
In this case, we have that y S {
2d S 8H2 h
C.5
Statement and Proof of Lemma 16
Lemma 16. Let B = 2 (1/6)
+ 2 H log(1/6)
+ 2H
32 md log
+
32mdy Ti log(
rd
N
N
Let (V),') x²} be the output of Opt with input reward as r². With probability 1
5
max Bx [rh(sN)] E [rr (sh)] s B.
Proof. Assume I satisfying | S Let 0r (w) = pu, w. By the induction condition (i). have that X, N A for E 1]. Sm
By Lemma 17 and the induction condition (iii) that X , A drt S fi, with probability 1- 16m we have that
N Σ
6 (w) - -x_x,
dr. (0T,0, +E)
i=1
dHl
ddll C
<8 58y0 To NxTx+to p. dlog
+ +4, /maxxxxa max X2 N -
Ori σe X- X- b.dog
md
dH 68
32md v f log ( dif
< <321
(18)
N
N
for all o such that 1|ø112 < and Φ 1 $1
Let (s)} and (s)) denote respectively the value function under the policy x' and the optimal value function. Let vo 2 (Simi) and o5 max, E, [rf (sw)]- Because (s,
[0, 1] for
any proper (s.a,7). we learn that v, (s), vf (8), No vo [0, 1]. Recall the definition of (V, (x)) in
Algorithm We next prove by induction that V, (s) 2 (f 2 C, (s) for any s E S and 1 I 7 S h.
For h, the inequality is trivial. Assume V, (s)
(s) for any l I s h. By (18) with
w = Vi(-)
Qe-1(8,a) 2 E [V('')) Es [s)))
(19)
when (s, oc (c S 1. In the case oz (s, 01-1 1, we have that
Qe-1(s,a) = Ee = =0
(20)
because Pe-1,8.0 1 Therefore, we have that
Vs- = Rangejo.1] maxx Qe-1 > Range max maxxExPPaae P (v((s'))) = v)-1(s).
By Bernstein's inequality, with probability 1 16m it holds that
N V1((1.)) + +
H2 Holog(1/ 1/8)
H 1og(16m/0)
Vo N
+2
2 Vi((im) 2 (f(m)) v/-
N
N
26

---

To bound the gap max, E, [1 (sw)] - Ex [rA(s))] direct computation gives that
max En (sn)s - Exi (on)]
= =1-- - -xyx [sh)]
Vi Ex [r/ (sh)
Vi
Vi + = (V>(or) PT
Pi V++1(t)
2 (1/()
H (1/6)
h
mdlog
dP cb
32md Fi log
$ 2/
+2
+
Σ
321
(21)
N
N
N
N
T=1
2 (1/5)
H (og(11/))
md log cB
32md Vi log
2
+2
+2H
321
N
N
N
N
=B
where (21) is by plugging orer.,, = Φ and w V+++(() into (18):
md log c6
32md fi log
V+(8+) P. ai (++1()) 5 321
co
N
N
C.6 Statement and Proof of Lemma 17
Lemma 17. [Matrix concentration] Fix u E R& such that ||v]|oo Land f S - && such that 0 f(s) A, Vs for some A. Let (òr, 8r 1N be sub-dataset independent and from the 7-th layer. Let X EE X² Dra + 2L. With probability T6mH2, it holds that
N
④ (()) - xx-1
Σ
(5,1)(
i=1
dH $ 88y ΦJ X; old
dH max @b x X; dlog( eδ
4,
+ S.
and
T F TT f T X- Σ 2 (f
1 (18g/ TTx= log
dH
dHl + 8 / max oT X 2r x; X=Ièdlog
co + +c) A.
for any o such that ||01|2 $ 1.
Proof. Let (E) be an E-net of the d-dimensional unit ball w.r.. La norm. Recall that Ç Then log(E) < 20 log(dH/e). Let
-(1
v))
T ((u)
x
Σ x2 tr
(3ras)
44 ΦJ x; log((11 + 2 /max ob X; 2
1 Xi 1 1ol.g-/0loo111110 log(118))
i=1
27

---

Then Pr(E(o, u)] I 26 by Bernstein's inequality. Assume ( v) holds. Then for any R letting & be the nearest neighbor of ø in (()), it holds that
④ TTO()) - xx Σ
((,,))
==1
N Φ
N
N
$ (Tu) - "To(v)) +
0(u)
X,
(3,30(37,5) - xx,1
x,,
Σ
00 (3,,)) + 3 ((()) ~ X, Σ
xx,'
pr, 2
1=1
1=1
Ng
+ 2 + +A/ A " log(110)) + 2/ max o TT 1 Xx " log(1/6)
X;
$ $AV0 o- x, blogl ( + 2 max of X, 2 Xj x log(1 (/6) +
Ng 2
+ 6log(1/6) 2/2
2
< 4 ot x; blog (1/6) + 2 max oT X7 1r X; log +
Noting that (E) S (d/s)², we have that (E) s 2(d/g)88. By replacing 8 with 16mH ((()) with probability 1 26, it holds that
① O(v)) - - x, xx,x Σ 1=1
(
d
d 2 max of, X7 2 x x (d log
S SAp TO X s
d+ log
C.
for any & such that ||01|2 S 1.
Define E2(Ø, f) to be the event where
N
3 (AVoTx; X, x x1'0) + 2 max oo N, 00,00 X2 fo-plog log (7)),
xxx 0 -
Σ or x
holds. We then show that (0, f)l 26.
N 07 PT f- x== Σ
N
(f((())
= = o x - Tx, Σ x (
1=1
= =
X-11 Σ Xaprr (0r. f + cri)
12 22 Pra + Xx,1
(22)
where we define ,,, Ry (s(') - (s,,,) with (s, a) being the state-action pair such that (- a) Φr,5. Noting that A I Crü I with probability 1, we have that
22 Pr.eT.i
22 log(d/6)
(x T (x)))))) 2max |22 x- 2r.
log(d/8)A
3 2/ log(d/6)oT xx ΦA + 2 max /
TTx='0 22 2T x Ar,A
1
(23)
28

---

holds with probability - 5. In similar way, with probability 1 - ö, we have
X X Ar 32 2 xF + 2 max VOT X-T='00 8. N2,00 ar
(24)
To bound the second term 2Φ" x in (22), we have
x X, pr vl
S 2||0 X; 112 | u112
s v 20 To 3 vd
S V 2d T
X
(25)
X- for any E IR such that || < 1. As result, we have || _ -- S V
V 6. Noting
Xi
that 0 3 f(s) N for
S, we have that
TT Φ6 z X7 3 3 X-
(26)
By (22), (23), (24) and (26), have that
N
② TTTT - o x
34ylog(d/8)o X + 2 max TT x. 2r
(27)
The proof is finished. Assume U (2 f) holds. Fix é and let si be the nearest neighbor of in (E). We then have that
T PT xx=1 Σ (
N (x=
($ n f Tt M [T +
+ xxx===>0 (r.l((TT))) - - xx=1 Σ Ur. (
-
N
+ v (((v)) -(w) X Σ Braa((T..))
(28)
We then bound the three terms in (28) separately. For the first term, have that ( v)) o))Ti ni vl s
Cvd for any E RS such that || xo < 1. As result, we have that || - +)]1 Evd, which
implies that
-VdAA 1 NTTST 16 T pT1 seVds.
(29)
For the second term, we have that
N
N
NE
( v x
2 (
$
for any e IR such that |//|/00 < 1. Using similar arguments, we learn that
VaNg
x
1b
x
Φr,
S
29

---

and
VdNE
N
N
VdNE A.
A 3 0- X,
Σ
f - 16 x,
Σ 1=1
Dy (5r,))))))) 1
(30)
By (26, f). we could bound the third term as
1 ((O()) 1/ _ X, Σ Pr. (
4v /llood//)0/Xx XF
. ds + max
th X 212 x
X
ral r,t
(31)
Putting (29), (30) and (31) together, we learn that
Φ J 0 x Σ Tr. (B7,5)
Evd+ + VaNE 2
+ A log(d/0)0/ X + 2 2axx V Txxx; 19 T x 0T
<vd+ vaNg 12log(d/0)g +
+ 4 log(d/5)0 X; & + max v TTxx 1022
X; "T='0022
X7
07,
2
2/2
i
T,
r,t
2max v x 4 log(d/5)0 Tx
X2 1
X, 02 T. T Xi 2 + 5
(32)
The proof is finished by replacing with 16mH
C.7 Statement and Proof of Lemma 18
Lemma 18. By running Algorithm we have the following claims: (1) The iteration line 3 ends in 10d 2z + +1) rounds; (2) Let Aend be the final value of A. Then it holds that
d
Pry (Aend) - > f1] S - f1(1-3Hz)
Proof. Fix Let Fo be the output of Algorithm 4 with input (h, {A, A, D) where D is group of valid sub-datasets. Since and {= are fixed in the context, we write Fo (o(A) (stochastic) function of A. We also define the expected truncated matrix as
(A) := E, [T f1A) (0r, T,, 87) A + (87, Tr; 87) < [|]
Number of iterations. Let Ar be the value of A after the i-th iteration. Suppose there are T iterations. For < i i T, we have that A, Fo By Lemma 13, we have that
(1 332) = A, = (1
4HTA,-1
(33)
Then we prove by induction that
A; 3 C₂A1-1,
(34)
where C. = (1 111111110 (1HH) for Si For i = 1, we learn that Ao = I and A, = (T < (1
3H ( + 4Hal (H For > 2, by the induction and the fact that Fo(aA) aFo(A)
for a 2 1, we have that
C. Fo(A,-1) = Fo C..
(35)
30

---

By (33) and (35). we have that
A, + HHAN
3 ( 44AM
(1 (1+3H2) A 4H
3
1-3/l
(1+ +H+)A
C.hi-
The proof of (34) finished. By the update rule, we learn that
A; 3 (1+11H+2) A-11 (1 (1+11 A-ii
C I Ai-1:
A + 2x 2
Let A; = A, + 27 I i 2 0. Then we learn that
A m (1 + 11 d 2 A
A = S 2r
I.
As result, the maximal eigenvalue of A, is at most (1 + 11Hx)', while the minimal eigenvalue of Á A is at most 1. Then we have that
log(det(A:)) log(det(A.-1)) S di log(1 + 11Hx) - log(2)-
By noting that dllo((/2x)) log(det(AA) and log(det(Ao)) s d'log(1 + </2x), we learn that for any 1 isjs JT
d dlog(22r/6 1) v di log(11 - 11Hx) - j 1og(2) S 0.
As result, it holds that
log(2) dlog(2x/5+ + 2) j(j + 1) 2 dlog(1 + 11Hx)
for any j < T. Solving the quadratic inequality, learn that T < 10d log 2x +1).
Truncation probability. By definition, have Aend Ar. Note that Aeud ż (1-3Hx) 3..HH)FFooo (Aeed)) and Fo (Aoen) Ex [Toho fi Aena]] We then have that
d
E Trace (T(Δn0% Aede 11] - (1 3Hx)
On the other hand, by noting that
Prx ( (Aend) -' > fi] Si < E. Trace (T(pno) (i (end)))oon)) < - -333)
we have
d
Pry [ (Aend) Si] S fi(1 3Hx)
31

---

C.8 Statement and Proof of Lemma 19
Lemma 19. Recall that 100000e" Let D (oh,s Sh.g. Ahal be the one sub-dataset in in Line 9, Algorithm 7. With probability 1 16m² 172. holds that
N 8m
On + =
An-
Proof. Let Xj and YR be respectively the final value of A and Fo in the i-th call of Algorithm in Algorithm 2 for the h-th round. Let I I [0r (++))) A t (1+3Hr)De 1/.3/x)10 M Eg ( + 4HxX, + S I Y +
< 1, ST kh- 1]. By Lemma 13 holds that
S
S
2
x
2x
2x
and
(1 HHHH)BBBia ( + +HHYY + S Y +
S I.
2x
2x
Because Ån ž X
N
N
m
Nh Dn
2m
j=1
N
m
(1- (1-6Hxx)Y)
2m
1 1 3Hx
j=1
2 A
2m
j=1
N
1 An - (1)
(36)
2
Also noting that An, I fi Ah, using Lemma 9, we have that, with probability 1
16m
N
x
E
- fiAn log(6mHH) /8)
1=1
i=1
N
N
An
CI
8m
Sarn
N
An
2I.
(37)
8m
The proof is completed by re-arranging (37).
C.9 Proof of Lemma
Let θ be dH- -i--eiensioonal grid with distance s4f Let (-oje(.) be the projection function to by projecting each dimension to the grid. obvious that if (0xhne(H) satisfies that ||0x||2 d, vh [H], then ||Proje,x
2d, vh E [M].
suffices show that for any kernel { hew E O, the output policy is f--ottimal. Assume the conditions in Lemma holds. Let M be the final truncated MDP MH. Then we have that
max Pr. [3h E [M], dh Andh > 1] S H 8H2 8H
n
As result, for any and reward function such that ||~|| S 1, we have that
11
11
E
1h
E
Ex
Ph
<
32

---

Fix reward kernel 0 = } heem E ④ We continue the analysis by assuming the ground MDP is M. Let be the returned policy and x' be the optimal policy. Let (s), oi a)) and (s), Vh,o (s, a)} be respectively the optimal value function and the value function of In particular, let Vo,- = (ima) Let (s), Qn,o(s, a)} be the value of (V),s), (s a)} in Algorithm with input reward kernel as 0. Let Vo,5 = (smm)) and V0,0 = (f,(())))) When clear from the context, we omit in the subscript.
We then have that
V0= Vo- = (Vo Vo) + (Vo Vo*)
(38)
We then prove by induction that V (s) Vs((s) 2 (H h) मH for all 8 S and h E [M]. The inequality is trivial for h H. Now we assume it is correct for all h 2 l. Let X =I for E [H] Recall that (g) is g-net of the d-dimensional unit ball. Fix
Ei X2 17, E ((E) with ||øl|2 I and V R$ with | I H. By Bernstein's inequality (I-dimensional
case of Lemma 9), with probability (|[ it holds that
X
XR On, ((5.a) o0 V
1=1
4H 4H|*(E)) 101)
4H| |0]
4
X== X=-6log olog
+ max
Φ X 6. K on log
128m
(H) |0]
32m
44H |
log
TT X Llog
N
8
N
With a union bound over & E (E)), we learn that, with probability
N
mdH log
dH cB
128m
dH
V(nnn) - T5 VTV < 321
& x tb dH log
N
N
cd
mdH log N
dH
32mdH log
4H cd
$ 32
N
16H1
for any o such that ||ø||2 < 1 and o A < 1. Note that (-)) is determined by 0 = =(0 hee(
and the sub-datasets after the 1i-th layer (non-inclusive). With union bound over E O, we learn that: with probability
Σ Φ
TX,
On. on Vn+1o(5nn)) o TT,, Vn+1, I 16H
i=1
for any ó such that ||012 s 1, T And < and 0 E O. Then we have that
(s - (s)
=Q - (s)) - Vs-1(s)
< < 1s)) (()1((s
N X-1 Σ
PP (1) (V²" - Vi) + P.T 2- (2) of
1e +
e 16H
1=1
< - (4) (Vi - Vi) + e
8H
H - h)
8H
33

---

As result, we learn that Vi- V/ I arguments, we have that
For the second term (Vo Vir) in (38), using similar
Vo
V0-
E
(h an) - -0 an (8+
-1=1
H
8H
Putting all together, with probability 2 have that Vo.8 VO,0 S S S for all O, As result, π is at least e-ottimal policy under the original MDP M. The proof is completed.
D Missing Algorithms
In this section, we present and explain the missing algorithms. Let Range (x) all a+alla b] + bl[x for fixed a, 6 ER and
Planning (Algorithm 5). This algorithm is used to compute the optimal policy given a group of datasets. The planning method combines backward planning with linear regression. A key distinction is that the feature is clipped based on block matrices. Here θ denotes dH- -imennsional grid with distance 34H and (-oje(-) denotes the projection operator to θ by projecting each dimension the grid. We refer the readers to Appendix C.9 for the effectiveness of this algorithm.
Planning-R (Algorithm 6). This algorithm used compute the near-optimal policy given fixed reward function. This algorithm is similar to P Planning (Algorithm 5), except that the reward function is given as input (it possible that the reward function is non-linear).
Policy-Execution (Algorithm 7). This algorithm is used to collect multiple copies of the datasets. The efficiency of the collected dataset is explained in Lemma 19.
Algorithm 5 PPaanning
Input: reward kernel 0 hh wi, sub-datasets (on,ir Sh,i, Ab, Ae,e block matrices (An heem: Initialization: < Proje (s+ <- for all S: for h H. 1, do
for (s, E x d:
@ ())
To T (Enz Nha + 2I) EN Sn Viti15hhh
(s( -
00
else;
a)) t Rangep. m (sn(s,
end for
for E do
Vi(s)) + max. Qn a);
T. + arg max, Qu(s,00 a);
end for
end for return: < TH hhemm-
E Computational Efficiency
In this section, we present the time complexity of our algorithms. In the rest of the analysis, we use the fact that the time cost of computing the inverse of d-dimensional PSD matrix is Od
34

---

Algorithm 6 Plaaniing-R
Input: horizon h, reward function r, sub-datasets {07,0 Br,i, PE block matrices
{Aihre(h-1]:
(s) f max, Th (n a), Vs E 19
for h h .,... do
X, Σ X2 0,,1 +1;
for E 15-111 a E do
Φ (8)
Φ T x'x-'> Ei21 2r (r + 32
md mdlog
32md Ing
$ ,Ι Φ 1
Q+(,, -
N
N
0,
else
as) + Range 00. (Q+(8,)));
end for
for s E 1it do
(,(s) max Q (s, a); (s) = arg max, Q (s)
end for end for
Vo (8inn))
return: (Vo, m
Input h, { ( Ji= An
2: π uniform (n Sh m))
H do 4: for z 1,2 2m do
3: 1,,2,
5: for j = 1,2, 1..,.... N do
6:
Run observe the feature oh and the next state sh.f
7:
An.j min (1 ohe on end for
8:
9:
(2)
(on Shis Anoly
10: end for
DT, -[D] (2) 2m 21
12: end for
return Dr + (D)..-
35

---

Bruncated-Matrix-EEaa (Algorithm 4). Firstly, the truncation operator T(-) could be im- plemented with time (dd)). Then the total computational cost of this algorithm bounded by O(H(Nd + d))) = HdN).))
Matrix-Eval (Algorithm 3). The computational cost of this algorithm is at most ((m) multi- plies that of Truncated-Matzii---eee (Algorithm 4), which is O(mNHd))
Planning (Algorithm and Planning-R (Algorithm 6). These two algorithms shares similar structure, with computational cost O(HANd") to compute the action give the current state.
Policy-Design (Algorithm 2). The computational cost of this algorithm at most ((m) multiplies that of Matriix---s (Algorithm 3) and P Planning-R, (Algorithm 6), which is bounded by NHm²
Policy-Execution (Algorithm 7). The time cost of this algorithm is simply O(m²N2 H²
Exploration (Algorithm 1). By the above results, the total computation cost of this algorithm ( = Ō g2
36


Reviews:
[{"review_id": "YpJQwQ9vAM", "reviewer": "Reviewer_JxHB", "summary": "This paper studies reward-free reinforcement learning under linear model, and aims to design deployment efficient algorithm, i.e. the number of exploration policy used is significantly less than the number of online episodes. The paper proposed a new algorithm that only needs $O(H)$ exploration policies to output an $\\epsilon$-optimal policy at the planning phase, where H is the horizon length.", "questions": "1. Can authors discuss the tradeoff between deployment efficiency and the sample efficiency. Is there any fundamental hardness here (e.g. we cannot achieve deployment efficiency and sample efficiency at the same time) or is it because the technical tools we have so far have limitations. (While there is some discussion after thm4, it seems that it is about the reachability parameter rather than the deployment complexity and the sample complexity themselves if I understand correctly.)", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n1. The theoretical result seems novel and it shows that the number of exploration policies is independent of the sub-optimal gap $\\epsilon$.\n2. The algorithm design is new in terms of the handling infrequent visits in the linear MDP setting.\n\nWeaknesses:\n1. While the algorithm design is indeed novel, and provide insights on how to design deployment efficient algorithms in linear or low-rank RL, the problem is limited to linear MDPs with known features, thus the significance is reduced. \n2. It is better to provide a comparison table of the results of related works showing the deployment complexity, sample complexity and the MDP setting.", "was_revised": true, "final_justification": "The authors have addressed my major concerns. I decide to keep my score.", "rebuttal": "We thank the reviewer for the valuable comments. Below we provide our responses to each point.\n\n**Regarding the linear MDP assumption.** \n\nWhile our algorithm is currently limited to linear MDPs, extending these results to low-rank MDPs or MDPs with linear Bellman completeness would be an interesting direction for future work. \n\n\n\n\n\n\n **Regarding  the table to summarize the related works.**\n\n Thanks for the suggestion. We will include this table in the next revision. The most important related works include: (i) Huang et al., 2022, which achieves $O(H)$ deployment complexity with the reachability  assumption; (ii) Zhao et al., 2023, which obtains $O(dH)$ deployment complexity for general function approximation.\n\n**Regarding  the trade-off between deployment efficiency and sample efficiency.**\n\nBy Theorem 3.2 in Huang et al., 2022, achieving polynomial sample complexity requires at least $cH/\\log_d(1/\\epsilon)$ deployments for some constant c > 0. Any deployment budget below this threshold results in super-polynomial sample complexity. With $O(H)$ deployments, our algorithm achieves polynomial sample complexity. Moreover, with $\\tilde{O}(dH)$ deployments, one could learn an $\\epsilon$ optimal policy with a near optimal sample complexity of $\\tilde{O}(\\frac{d^2H^3}{\\epsilon^2})$ with the help of online learning methods (He et al., 2022). \n\nThe remaining challenge is to determine the deployment complexity threshold for achieving near-optimal sample complexity. Specifically, we ask:\n ***Are $\\Omega(dH)$ deployments necessary to attain the near-optimal sample complexity of $\\tilde{O}(\\frac{d^2H^3}{\\epsilon^2})$?*** When the reachability assumption holds, it could be possible to improve the deployment complexity to $H$ while maintaining near optimal sample complexity with existing techniques. However, when the reachability assumption does not hold, the technical tools we have so far fail to address  this problem.  We leave this problem as an open question for future research.\n\n\n\n\n\n**References:**\n\nHuang et al., 2022: Towards deployment-efficient reinforcement learning: lower bound and optimality.\n\nZhao et al., 2023:  A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation.\n\nHe et al., 2022:   Nearly minimax optimal reinforcement learning for linear Markov Decision Processes"}, {"review_id": "VjIH0Ur4ON", "reviewer": "Reviewer_ktTz", "summary": "The paper proposes an algorithm for reward-free exploration in linear MDPs. Its main result is a nearly optimal deployment complexity (i.e., the number of different exploration policies used to collect data) of $O(H)$, and a polynomial (though suboptimal) sample complexity. Its main technical novelty is providing such guarantees without assumptions on the reachability coefficients of the MDP.", "questions": "- From line 782, the sample complexity of your algorithm is $O(d^{15} H^{15} / \\epsilon^5)$, right? This information would be useful in the main text. An interesting direction for future work could be improving this sample complexity. Hence, it would be helpful if you could summarise the main causes of sub-optimality there!\n\n- In algorithm 1, there seems to be exactly $H$ policy deployments. Why is the deployment complexity in Theorem 4 $O(H)$ and not exactly $H$?\n\n- Out of curiosity, is there any result showing whether sample complexity and deployment complexity are conflicting objectives (i.e., whether both could be near-optimal)?\n\n- I understand that this is a theoretical RL paper, but even in that case, I believe that experiments (on toy environments at least) are important. For example, one important contribution of the paper is obtaining guarantees without reachability assumptions. From what I understood, this is also a consequence of algorithmic improvements (not only proof techniques), so it would be interesting to see if (i) your algorithm works in a toy MDP with hard-to-reach states; (ii) if previous algorithms that require reachability assumptions get stuck in that case. I also understand that, in order for it to be feasible to run experiments, some theoretical constants (often too large) need to be relaxed empirically, but that shouldn’t be difficult, and would illustrate the main algorithmic ideas that make exploration work.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The paper is organised and written clearly.\n\n- The authors provide the first nearly optimal algorithm for their setting without making assumptions on reachability coefficients of the MDP.\n\n## Weaknesses\n\n- Lack of experiments (even on toy MDPs). \n\n- According to Assumption 2, the considered linear MDP setting assumes a finite number of states, unlike [Jin et al. 2019](https://arxiv.org/pdf/1907.05388).\n\n## Suggestions\n\n- A table including the deployment complexity and the sample complexity of your algorithm and related work would be useful (even if in the appendix).", "was_revised": true, "final_justification": "I think the paper brings a relevant theoretical contribution to the field. I increase my rating from 4 to 5 following the authors responses, and experimental validation on a toy experiment.", "rebuttal": "We appreciate the reviewer's valuable comments. We respond to each comment below.\n\n**Regarding the numerical experiments.** \n\n  We thank the reviewer for the suggestion. The primary goal of this work is to eliminate dependence on reachability in both sample complexity and deployment complexity. To ensure our algorithm outperforms reachability-dependent approaches, we require the reachability parameter to be exponentially small. However, this leads to highly artificial MDP constructions. In practice, features are typically learned via neural networks, making it unclear how to test reachability parameters in such settings. Since different features yield different reachability values, evaluating the algorithm in a natural, practical environment becomes challenging.\n\n**Regarding the hardness in improving the sample complexity.**\n\nYou are right that the sample complexity of our algorithm is $O(d^{15}H^{15}/\\epsilon^5)$. \n In the next revision, we will provide the precise sample complexity in the theorem statement.  \n\nThe main reason of the bad dependency is that: The main algorithm (Algorithm 1) involves two iterative processes, and since the results of different iterations all rely on the same offline dataset, these results are subtly coupled with each other. To break the statistical coupling, we simply make independent copies of the offline datasets by following the exploration policy and repeatedly sampling trajectories  with fresh randomness.\n\n One potential approach to improving the sample complexity is to  prove concentration inequalities (e.g., Lemma 17) through union bound arguments. The major difficulty in this approach is that the complexity of the offline planning policy in Algorithm 3 and 4 could be high.\n\n\n**Regarding the trade-off between deployment efficiency and sample efficiency.**\n\nBy Theorem 3.2 in Huang et al., 2022, achieving polynomial sample complexity requires at least $cH/\\log_d(1/\\epsilon)$ deployments for some constant c > 0. Any deployment budget below this threshold results in super-polynomial sample complexity. With $O(H)$ deployments, our algorithm achieves polynomial sample complexity. Moreover, with $\\tilde{O}(dH)$ deployments, one could learn an $\\epsilon$ optimal policy with a near optimal sample complexity of $\\tilde{O}(\\frac{d^2H^3}{\\epsilon^2})$ with the help of online learning methods (He et al., 2022). \n\nThe remaining challenge is to determine the deployment complexity threshold for achieving near-optimal sample complexity. Specifically, we ask: \n***Are $\\Omega(dH)$ deployments necessary to attain the near-optimal sample complexity of $\\tilde{O}(\\frac{d^2H^3}{\\epsilon^2})$?***  \nWe leave this problem as an open question for future research.\n\n**Regarding the finite state space.**\n\nWe are sorry for the confusion.  We will redefine $\\mu$ as $d$ measures $(\\mu_1,\\mu_2,\\ldots, \\mu_d)$ over the state space $\\mathcal{S}$ as in Jin et al., 2019. We emphasize that our algorithm and theoretical analysis hold even for infinite state spaces.\n\n\n**About the exact number of deployments.** \n\nThe number of deployments is exactly $H$ assuming the initial state is fixed as $s_1$. Without this assumption, we need $H+1 $ deployments. We will clarify this in the next revision.\n\n**Regarding the table to summarize the related works.** \n\nWe thank the reviewer for this suggestion and will include the table in the next revision.\n\n\n\n**References:** \n\nHuang et al., 2022: Towards deployment-efficient reinforcement learning: lower bound and optimality.\n\nHe et al., 2022:  Nearly minimax optimal reinforcement learning for linear Markov Decision Processes.\n\nJin et al., 2019: Provably efficient reinforcement learning with linear function approximation."}, {"review_id": "qtUUwYEJSj", "reviewer": "Reviewer_Ty3N", "summary": "This paper studies reward free exploration problem in linear MDP problem. In particular, we assume a linear MDP setting without the knowledge of the reward function. The goal is to accumulate enough data to find a good estimate of the underlying MDP. This estimation then will be used in the next step to find an estimation of the optimal policy corresponding to an arbitrary reward function. The authors develop this algorithm, and show that their algorithm requires only a polynomial number of samples with respect to the problem parameters.", "questions": "- What is \"z\" in Algorithm 5?\n- Can you provide a sample complexity (with exact dependency on parameters of the MDP) for tabular MDP setting?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The main strength of the paper is to remove the infrequent direction assumption in the prior work. In particular, this work does not assume a uniform lower bound on the eigen values of $\\Lambda_h$ matrix over all the horizons. Instead, they devise algorithm 3, which helps on achieving a good data set, with at most H number of deployments (rather than exponential number of deployments with respect to H, which might happen since the lower bound on the distribution over states can decrease exponentially with respect to the horizon). \nThe main weakness is that in terms of problem formulation is relatively similar to the prior work, and the work is summarized in just a theorem with polynomial dependency on \\epsilon, H, d, and log(1/$\\delta$). This polynomial dependency can be very bad, and no lower bounds or simulations are provided to support the result.", "was_revised": true, "final_justification": "The authors conducted experiment, and claim that their algorithm outperforms prior work. If paper gets accepted, I expect to see the result of the experiment in the final version of the paper.", "rebuttal": "We are grateful to the reviewer for the constructive feedback. Below we present our response.\n\n**Regarding the bad polynomial dependency.**\n\nIndeed our current sample complexity is far from being optimal. The main reason of the bad dependency is that: The main algorithm (Algorithm 1) involves two iterative processes, and since the results of different iterations all rely on the same offline dataset, these results are subtly coupled with each other. To break the statistical coupling, we simply make independent copies of the offline datasets by following the exploration policy and repeatedly sampling trajectories  with fresh randomness.\n\n One potential approach to improving the sample complexity is to  prove concentration inequalities (e.g., Lemma 17) through union bound arguments. The major difficulty in this approach is that the complexity of the offline planning policy in Algorithm 3 and 4 could be high.\n\n**Regarding the lower bound.**\n\nWhile the precise trade-off between sample complexity and deployment complexity remains unknown, Theorem 3.2 in Huang et al., 2022 provides an $\\Omega(H/\\log_d(1/\\epsilon))$ lower bound for the sample complexity under polynomial sample complexity constraints.\n\n**Regarding the numerical experiments.**\n \nThe primary goal of this work is to eliminate dependence on reachability in both sample complexity and deployment complexity. To ensure our algorithm outperforms reachability-dependent approaches, we require the reachability parameter to be exponentially small. However, this leads to highly artificial MDP constructions. In practice, features are typically learned via neural networks, making it unclear how to test reachability parameters in such settings. Since different features yield different reachability values, evaluating the algorithm in a natural, practical environment becomes challenging.\n\n**Regarding $z$ in Algorithm 5.**  \n\nWe set $z = \\frac{100000\\epsilon^2}{d^4H^5}$. Please refer to line 781 for the parameter settings.\n\n**Regarding the tabular case.**\n\nLet $S$ and $A$ be respectively the sizes of the state space and the action space.\nBy the method in (Zhang et al., 2022), one could reach the asymptotically optimal $\\tilde{O}(\\frac{SAH^3}{\\epsilon^2})$ sample complexity (in episodes) with $H+1$ deployments. \nIn this approach, we use the first $H$ deployments (which corresponds to $H$ batches in Zhang et al., 2022) to learn an approximate transition model $\\tilde{P}$ using $\\mathrm{poly}(S,A,H)$ episodes. Then we  design an exploration policy $\\pi'$ with minimax coverage under the approximate model $\\tilde{P}$ such that\n$$\\max_{\\pi} \\sum_{s,a,h} \\frac{d_{\\pi}(h,s,a)} {d_{\\pi'}(h,s,a)}  = O(SAH).$$\nHere $d_{\\pi}(h,s,a) = \\mathbb{E}_{\\pi,\\tilde{P}} \\mathbb{I}(s_h=s,a_h=a)$ denotes the occupancy distribution of the policy $\\pi$ under the transition $\\tilde{P}$.\n  By running $\\pi'$  for $O(\\frac{SAH^3}{\\epsilon^2})$ episodes, we could learn an $\\epsilon$ optimal policy. \nSimilar approaches have also been explored by Qiao et al. (2022).\n\n**References:** \n\nHuang et al., 2022: Towards deployment-efficient reinforcement learning: lower bound and optimality.\n\nZhang et al., 2022: Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning.\n\nQiao et al., 2022: Sample-efficient reinforcement learning with $\\log\\log(t)$ switching cost."}, {"review_id": "oMpdo6U86d", "reviewer": "Reviewer_tYnN", "summary": "In this paper, the authors study deployment-efficient reward-free exploration with linear function approximation, where the goal is to explore a linear Markov Decision Process (MDP) without revealing the reward function, while minimizing the number of distinct policies implemented during learning. For the task, the authors design a provably efficient algorithm with near optimal deployment efficiency while the sample complexity has polynomial dependence on relevant parameters. Compared to previous algorithms, this work removes a crucial assumption of reachability, directly addressing an open problem from prior work.", "questions": "Please refer to the weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The problem of deployment efficient RL is important and interesting.\n2. The technical results in this paper are solid, while the paper provides lots of novel techniques.\n3. This paper removes the assumption of reachability, which is a strong assumption in previous works.\n\nWeaknesses:\n1. The sample complexity upper bound does not appear in the main part, and the bound is far from optimal. The bound is better than previous results only when the reachability coefficient in previous papers is very close to 0. While I understand the difficulty to remove the reachability assumption, it will be helpful if there are more discussions about the difficulty to improve the current sample complexity. \n\n2. The proof overview in the main part is not very informative. The intuition of the three statements in Lemma 6 is not clear and requires more explanation. A proof sketch (even in the appendix) showing the amount of data for different parts of the algorithm (e.g. policy design, matrix evaluation) and how does these data combine to the whole sample complexity would be helpful.\n\n3. I would suggest the authors to polish the writing and check for the typos in the main part. E.g., in line 7 of Algorithm 4 and (i) of Lemma 6, should the $\\Lambda$ be $\\Lambda^{-1}$?\n\nOverall, I think removing the reachability assumption is an important contribution. Therefore, I slightly lean towards acceptance of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. Below we provide our responses to each point.\n\n**Regarding the bad dependencies on $d, H$ and $1/\\epsilon.$**\n\nThe main reason of the bad dependency is that: The main algorithm (Algorithm 1) involves two iterative processes, and since the results of different iterations all rely on the same offline dataset, these results are subtly coupled with each other. To break the statistical coupling, we simply make independent copies of the offline datasets by following the exploration policy and repeatedly sampling trajectories  with fresh randomness.\n\n One potential approach to improving the sample complexity is to  prove concentration inequalities (e.g., Lemma 17) through union bound arguments. The major difficulty in this approach is that the complexity of the offline planning policy in Algorithm 3 and 4 could be high.\n\n\n\n**Regarding the proof sketch of the sample complexity.** \n\nThanks for the suggestion. In Section 6, we present the framework for proving the main theorem. The most complicated components are the proofs of Lemmas 6 and 15, for which we will provide high-level proof sketches in the next revision.\n\nHere, we present a summary of the sample complexity for each component of the algorithm. We will provide the details in Appendix E.\n\nWe begin by counting the number of sub-datasets required throughout the learning process. Then the sample complexity (total number of episodes) is obtained by multiplying this number $N = \\frac{10^{9}d^7H^7\\log\\left(\\frac{dH}{\\epsilon\\delta}\\right)}{\\epsilon^3}$.\n\n*Algorithm 4* (Truncated-Matrix-Eval): This algorithm requires at most $H$ sub-datasets. \n\n*Algorithm 3* (Matrix-Eval): This algorithm makes $O(m)$ calls to Algorithm 4, each requiring at most $O(Hm)$ sub-datasets.\n\nThe effectiveness about Algorithm 3 (including Algorithm 4) is provided in Lemma 18, which means we could achieve efficient truncation with recursive truncated planning.\n\n*Algorithm 5* (Planning) and *Algorithm 6* (Planning-R): These two algorithms shares similar structure, which requires at most $H$ sub-datasets.\n\n*Algorithm 2* (Policy-Design): This algorithm makes $O(m)$ calls to Algorithm 3  and  Algorithm 5, which requires at most $O(m^2H)$ sub-datasets.\n\n*Algorithm 1* (Exploration): This algorithm makes $H$ calls to Algorithm 2, which requires at most $O(m^2H^2)$ sub-datasets.\n\nPutting all together, the total number of episodes is $O(m^2H^2N)=\\tilde{O}\\left( \\frac{d^{15}H^{14}}{\\epsilon^5}\\right)$.\n\n\n\n**Regarding the typos.**\n\n Thanks for pointing out the typos and we will fix accordingly in the next revision."}]

Author rebuttal:

Meta-review: All reviewers agree that the paper is a solid theoretical contribution to the problem of deployment-efficient exploration with function-approximation.  It is the first efficient algorithm that handles the whole family of linear MDPs.  Existing work, e.g., Huang et al, and Qiao et al. while providing better dependence on parameters like H and d, their sample complexity (at least in finite sample) depends on certain "reachability" conditions.

The results are primarily technical, and the paper is recommended to be accepted as a theoretical work without experiments.   The authors should work on addressing all reviewer comments (including improving clarity) for the camera ready version.
Decision: Accept (poster)