Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation
Authors: Dan Qiao
Yu-Xiang Wang
Venue: ICLR 2023 poster (2023)
Keywords: Reinforcement Learning
Deployment efficiency
Reward free RL
Low adaptive RL

Abstract: We study the problem of deployment efficient reinforcement learning (RL) with linear function approximation under the \emph{reward-free} exploration setting. This is a well-motivated problem because deploying new policies is costly in real-life RL applications. Under the linear MDP setting with feature dimension $d$ and planning horizon $H$, we propose a new algorithm that collects at most $\widetilde{O}(\frac{d^2H^5}{\epsilon^2})$ trajectories within $H$ deployments to identify $\epsilon$-optimal policy for any (possibly data-dependent) choice of reward functions. To the best of our knowledge, our approach is the first to achieve optimal deployment complexity and optimal $d$ dependence in sample complexity at the same time, even if the reward is known ahead of time. Our novel techniques include an exploration-preserving policy discretization and a generalized G-optimal experiment design, which could be of independent interest. Lastly, we analyze the related problem of regret minimization in low-adaptive RL and provide information-theoretic lower bounds for switching cost and batch complexity.

Published as a conference paper at ICLR 2023
NEAR-OPTIMAL DEPLOYMENT EFFICIENCY IN REWARD-FREE REINFORCEMENT LEARNING WITH LINEAR FUNCTION APPROXIMATION
Dan Qiao
Yu-Xiang Wang Department of Computer Science, UCSB yuxiangwëcs, ucsb edu
Department of Computer Science, UCSB danqiao@ucss edu
ABSTRACT
We study the problem of deployment efficient reinforcement learning (RL. with linear function approximation under the reward-free exploration setting. This is a well-motivated problem because deploying new policies is costly in real-life RL applications. Under the linear MDP setting with feature dimension d and
planning horizon H, we propose new algorithm that collects at most Ō ((= trajectories within H deployments to identify c-optimal policy for any (possibly data-dependent) choice of reward functions. To the best of our knowledge, our approach is the first to achieve optimal deployment complexity and optimal d dependence in sample complexity at the same time, even if the reward is known ahead of time. Our novel techniques include an exploration pranttroon--reervinnnn policy discretization and generalized G-optimal experiment design, which could be of independent interest. Lastly, we analyze the related problem of regret minimization in low- low-adaptive RI. and provide information-theoreti lower bounds for switching cost and batch complexity.
INTRODUCTION
In many practical reinforcement learning (RL) based tasks, limited computing resources hinder applications of fully adaptive algorithms that frequently deploy new exploration policy. Instead, usually cheaper to collect data in large batches using the current policy deployment. Take recommendation system (Afsar et al., (021)) an instance, the system is able to gather plentiful new data in very short time, while the deployment a new policy often takes longer time, as requires extensive computing and human resources. Therefore, it is impractical to switch the policy based on instantancous data as a typical RL algorithm would demand. A feasible alternative is to run a large batch of experiments in parallel and only decide whether to update the policy after the whole batch is complete. The same constraint also appears in other RL applications such as healthcare (Yu et al. 2021), robotics (Kober et al. 2013) and new material design (Zhou et al. 2019). In those scenarios, the agent needs to minimize the number of policy deployment while learning a good policy using (nearly) the same number of trajectories its fully-adaptive counterparts. On the empirical side, Matsushima et al.) (2020) first proposed the notion deployment efficiency. Later, Huang et al.) (2022) formally defined deployment complexity. Briefly speaking, deployment complexity measures the number of policy deployments while requiring each deployment to have similar size. We measure the adaptivity of our algorithms via deployment complexity and leave formal definition to Section 2
Under the purpose of deployment efficiency, the recent work by Qiao et al. (2022) designed an algorithm that could solve reward-free exploration in O(H) deployments. However, their sam-
ple complexity Ö((S)) /e²) although being near-optimal under the tabular setting, can be unacceptably large under real-life applications where the state space is enormous or continuous. For environments with large state space, function approximations are necessary for representing the feature of each state. Among existing work that studies function approximation in RL, linear function approximation is arguably the simplest yet most fundamental setting. In this paper, we study deployment efficient RL with linear function approximation under the reward-free setting, and we consider the following question:
Question 1.1. Is it possible to design deployment efficient and sample efficient reward-free RL algorithms with linear function approximation?

---

Published as a conference paper at ICLR 2023
Algorithms for reward-free RL
Sample complexity E"H
Deployment complexity
Algorithm 1 & 2 in Wang et al. (0020)
H"H"
FRANCIS Zanctte et al., 2020b
RFLIN (Wagenmaker et al. 2022b
Algorithm in Huang et al.
(2022
H
2
LARFE (Qiao et al.
2022
0 st AH
2H
Our Algorithm
[Theorem
5.1
Our Algorithm Theorem
7.1
St AH'
H
Lower bound Wagenmaker et 2022b)
12 H
N.A. S2(H)
Lower bound (Huang et al. 2022 If polynomial sample
Table 1: Comparison of our results (in blue) existing work regarding sample complexity and deployment complexity. We highlight that our results match the best known results for both sample complexity and deployment complexity at the same time. f: We ignore the lower order terms in sample complexity for simplicity. *: V'ii is the gobblem-dependen reachability coefficient which is upper bounded by 1 and can be arbitrarily small. t: This work is done under tabular MDP and we transfer the under tabular MDP, we can replace one d sample complexity by S.
switching cost to 2H deployments. *: When both our algorithms are applied
Our contributions. In this paper, we answer the above question affirmatively by constructing an algorithm with near-optimal deployment and sample complexities. Our contributions are threefold.
A new layer-by-layer type algorithm (Algorithm[) D for reward-free RI. that achieves deploy- ment complexity of H and sample complexity of Ō (² Ō("")²) Our deployment complexity and In addition, when
is optimal while sample complexity has optimal dependence applied to tabular MDP, our sample complexity (Theorem 7.1 recovers best known result Ō -/a)).
We generalize G-optimal design and select near-optimal policy via uniform policy evaluation on a finite set of representative policies instead of using optimism and LSVI. Such technique sample complexity and may be of independent interest.
helps tighten
We show that "No optimal-regret online learners can be deployment efficient" and deploy- ment efficiency is incompatible with the highly relevant regret minimization setting. For regret minimization under linear MDP, we present lower bounds (Theorem 7.2 and 7.3) for other measurements of adaptivity: switching cost and batch complexity.
1.1 CLOSELY RELATED WORKS
There is a large and growing body of literature on the statistical theory of reinforcement learning that we will not attempt thoroughly review. Detailed comparisons with existing work on reward-free RL (Wang et al. 2020 Zanette et af. 20205] Wagenmaker et al., (2022b] Huang et al. 2022 Qiao et al.) (022) are given in Table For more discussion of relevant literature, please refer Appendix A and the references therein. Notably, all existing algorithms under linear MDP either admit fully adaptive structure (which leads deployment inefficiency) suffer from sub-optimal sample complexity. In addition, when applied to tabular MDP, our algorithm has the same sample complexity and slightly better deployment complexity compared Qiao et al.) (2022).
The deployment efficient setting is slightly different from other mcasurements of adaptivity. The low switching setting (Bai et al., 2019) restricts the number of policy updates, while the agent can decide whether to update the policy after collecting every single trajectory. This can be difficult to implement in practical applications. decisions about policy changes to be made at only few (often predefined) checkpoints. Compared to batched RL, the requirement of deployment efficiency is stronger by requiring each deployment to collect the same number of trajectories. Therefore, deployment efficient algorithms easier to deploy in parallel (see. e.g.. Huang et al.) 20222, for more elaborate discussion). Lastly, we remark that our algorithms also work under the batched RL setting by running in H batches.
more relevant setting, the batched RL setting (Zhang et al. 2022) requires
2

---

Published as a conference paper at ICLR 2023
Technically, our method is inspired by optimal experiment design well-developed research area from statistics. In particular, a major technical contribution of this paper is to solve a variant of G-optimal experiment design while solving exploration in RL at the same time. Zanette et al. (2020b); Wagenmaker et al. 2022b) choose policy through online experiment design, i.e., running no-regret online learners select policies adaptively for approximating the optimal design. Those online approaches, however, cannot be applied under our problem due to the requirement of deployment efficiency. To achieve deployment complexity of H. we can only deploy one policy for each layer, so we need to decide the policy based on sufficient exploration for only previous layers. Therefore, our approach requires offfine experiment design and thus raises substantial technical challenge.
A remark on technical novelty. The general idea behind previous RL algorithms with low adaptivity optimism and doubling schedule for updating policies that originates from UCB2 (Auer al.) 2002). The doubling schedule, however, can not provide optimal deployment complexity. Different from those approaches, we apply layer-by-layer exploration to achieve the optimal deployment complexity, and our approach is highly non-trivial. Since we can only deploy one policy for each layer, there are two problems to be solved: the existence of a single policy that can explore all directions a specific layer and how to find such policy. We generalize G-optimal design to show the existence of such explorative policy. Besides, we apply exploration peplorationprresrvinn policy discretization for approximating our generalized G-optimal design. We leave detailed discussions about these techniques to Section
PROBLEM SETUP
V Vx Ar. For matrix X E RRdxd 11.112, || IIr, Amin (.), Amax (-) denote the operator norm, Frobenius norm, smallest eigenvalue and largest eigenvalue, respectively. For policy æ, E,, and Pr denote the expectation and probability measure induced by under the MDP we consider. For any set U, A(U) denotes the set of all possible distributions over U. In addition, we use standard notations such as O and 12 to absorb constants while and Ω suppress logarithmic factors.
Notations. Throughout the paper. for E Zt, [m] {1,2, nn. We denote ||~|||-
Markov Decision Processes. We consider mnite-horizon episodic Markov Decision Processes (MDP)
with non-stationary transitions, denoted by tuple M (S, A, H, Ph, (Sutton Barto 1998). where S is the state space, A is the action space and H is the horizon. The non-stationary transition kernel has the form Ph: S x AAx S + [o, 1] with PA [s, a) representing the probability transition from state s, action to next state s' at time step h. In addition, rh (,, a) E A(O 1)) denotes the corresponding distribution of reward] Without loss of generality, we assume there is a fixed initial state $1 P A policy can be seen series of mapping π (II,... TH). where each T. maps each state 8 E S to a probability distribution over actions, iee. Fn S + ((A), A h E [A]. A random trajectory (81; 01, "1,".. 88H THH,,,,, 81++1 is generated by the following rule: 81 is fixed, an (-1a)) Th ~ TA (5h, ax), Sh+1 ~ Pr. ax), Vhe E [H].
Q-values, Bellman (optimality) equations. Given policy π and any h E [H], the value function (T(()) and Q-value function (T) are defined as: (s) = E, [E relsh = s]. (T, a) = E, (E 1 Tr|88, AA 8, a), Vs,a S x A. Besides, the value function and Q-value function with respect to the optimal policy n² is denoted by (-) and Q,(;,)) Then Bellman (optimality) equation
follows Vhe E [H]:
(7(s.a) = nn + Pa(-1s, V) V, = En (Q7, (s = rx. + Pr.-Is. V) VW max Q (-)
In this work, consider the reward-free RL setting, where there may be different reward functions. Therefore, we denote the value function of policy x with respect to reward r by (=(r). Similarly, V* (r) denotes the optimal value under reward function We say that policy is c-ottmmll with respect to r if V (r) 2 (r) c.
Linear MDP (Jin et al. 2020b). An episodic MDP (S, A, H. is linear MDP with known feature map &= S x A IR if there exist H unknown signed measures uh, E Rd over S and H unknown reward vectors 0n E Rd such that
Pa (s' s, a) = (0(s, a), s9 (s')), Th (s, a) = (o(s, a), On), Vh, E [M] X
'ee abuse the notation so that r also denotes the expected (immediate) reward function. 2The generalized case where the initial distribution is arbitrary distribution can be recovered from this setting by adding one layer the MDP.
3

---

Published as a conference paper at ICLR 2023
Without loss of generality, we assume (| a)ll2 S 1 for all s, a; and for all h [H], I v Vd, 1/On|2 vd.
For policy æ, we define A == E (d( an ((),, az) 'T the expected covariance matrix with respect to policy क and time step h (here 8h, On follows the distribution induced by policy ι). Let X = [H] supx Amin Amin(Ar, (Ar,a). We make the following assumption regarding explorability.
Assumption 2.1 (Explorability of all directions). The linear MDP we have satisfies X > O.
We remark that Assumption 2.1 only requires the existence of (possibly non-Markovian) policy to visit all directions for each layer and it is analogous to other explorability assumptions in papers about RL under linear representation (Zanette 2022). In addition. the parameter X only appears in lower order terms of sample complexity bound and our algorithms do not take X as an input.
al., 2020b Huang et al., 2022 Wagenmaker & Jamieson
Reward-Free RL. The reward- RL setting contains two phases, the exploration phase and the planning phase. Different from PAC R setting, the learner does not observe the rewards during the exploration phase. Besides, during the planning phase, the learner has to output near-optimal policy for any valid reward functions. More specifically, the procedure is:
1. Exploration phase:
Given accuracy and failure probability ō, the learner explores an MDP for K (e, ö) episodes and collects the trajectories without rewards {sh a (N,)))(())
2. Planning phase: The learner outputs a function ((-) which takes reward function as input. The function R (-) satisfies that for any valid reward function (+( 2 (+) -
The goal of reward-free frre RL is to design procedure that satisfies the above guarantee with probability at least 1 5 while collecting as few episodes possible. According to the definition, any procedure satisfying the above guarantee is provably efficient for PAC RL setting.
Deployment Complexity. In this work, we measure the adaptivity of our algorithm through deploy- ment complexity, which is defined as:
Definition 2.2 (Deployment complexity (Huang et al., 2022 We say that an algorithm has deploy- ment complexity of M, if the algorithm is guaranteed to finish rumning within M deployments. In addition, the algorithm is only allowed to collect at most N trajectories during each deployment, where N should be fixed priori and cannot change adaptively.
We consider the deployment of non-Markovian policies (i.e. mixture of deterministic policies) (Huang et al. 2022).. The requirement of deployment efficiency is stronger than batched RI. (Zhang et al. 2022) or low switching RL (Bai et al.) 2019). which makes deployment-efficee
algorithms more practical in real-life applications. For detailed comparison between these definitions, please refer to
Section I.1 and Appendix A
3 TECHNIQUE OVERVIEW
In order to achieve the optimal deployment complexity of H, we apply layer-by-layer exploration. More specifically, we construct a single policy TV to explore layer h based on previous data. Follow- ing the general methods in reward-free RL (Wang et al., 2020 Wagenmaker al., 2022b). we do exploration through minimizing uncertainty. As will be made clear in the analysis, given exploration dataset D {5% ab (nne(H))(N)) the uncertainty of layer h with respect to policy ı can be char- acterized by Ex an) AA"", where A = + - 6(8% (s5) og) T is (regularized and unnormalized) empirical covariance matrix. Note that although we can not directly optimize As, we can maximize the expectation Nz,- E,, [ T (N,,, is the number of trajectories we apply TT) by optimizing the policy т₁ Therefore, to minimize the uncertainty with respect to some policy set II, we search for an explorative policy To to minimize maxzen E (x0(Sh, on) (n)(E,,, o,, (6((8. ax).
3.1
GENERALIZED G-OPTIMAL DESIGN
For the minimization problem above, traditional G-optimal design handles the case where each deterministic policy я generates some Φx at layer h with probability (i.e. we directly choose ø instead of choosing T), is the case under deterministic MDP. However, traditional G-optimal design
Asso known reward-aware RI., which aims identify near optimal policy given reward function.
4

---

Published as a conference paper at ICLR 2023
cannot tackle problem since under general linear MDP, each will generate distribution over the feature space instead of a single feature vector. We generalize G-optimal design and show that for any policy set II, the following Theorem 3.1 holds. More details are deferred to Appendix
Theorem 3.1 (Informal version of Theorem B.I. If there exists policy To E A(T) such that Amin (Bn, o2. > 0, then EA(T) max, ell Ex ((sn,
0n0 1 an) S d.
Generally speaking, Theorem 3.1 states that for any II, there exists a single policy from A(TI) (i.e., mixture of several policies in II) that can efficiently reduce the uncertainty with respect 11. Therefore, assume we want to minimize the uncertainty with respect to II and we are able to derive the solution To of the minimization above, we can simply run To repeatedly for several episodes.
However. there are two gaps between Theorem 3.1 and our goal of reward free RL. First, under the Reinforcement Learning setting, the association between policy π and the corresponding distribution of 6 is unknown, which means we need to approximate the above minimization. It can be done by estimating the two expectations and we leave the discussion to Section 3.3 The second gap is about choosing appropriate II in Theorem 3.1 for which natural idea is to use the set of all policies. is however infeasible to simultaneously estimate the expectations for all m accurately. The size of {all policies) is infinity and ( policies}) is even bigger. It seems intractable to control its complexity using existing uniform convergence techniques (e.g., a covering number argument).
3.2 DISCRETIZATION OF POLICY SET
The key realization towards a solution to the above problem is that we do not need to consider the set of policies. It suffices to consider a smaller subset IT that more amenable to an e-ner argument. This set needs to satisfy few conditions.
(I) Due to condition in Theorem 3.1 II should contain explorative policies covering all directions.
(2) ll should contain representative policy set 11eval such that it contains a near-optimal policy for any reward function.
(3) Since we apply offtine experimental design via approximating the expectations, Il must be "small" enough for a uniform-convergence argument to work.
We show that we can construct a finite set II with II] being small enough while satisfying Con- dition (1) and (2). More specifically, given the feature map .(-,)) and the desired accuracy 6, we can construct the explorative policy set Th such that log([I((2P)) I Ó(d (oo(l//))) where Ie is the policy set for layer h. In addition, when is small compared to X*, we have (U)*= Amin (B 2 Ā (22))) which verifies Condition (1) Plugging in IT and approximating the minimization problem, after the exploration phase we will be able to estimate the value functions of all E 11 accurately.
It remains to check Condition (2) by formalizing the representative policy set discussed above. From I,T we can further select a subset, and we call policies to evaluate: IIeval It satisfies that (T |) = (d log(1/<)) while for any possible linear MDP with feature map o(:,)), ITeval is guaranteed to contain one e-optimal policy. As a result, it suffices to estimate the value functions of all policies in IIvval and output the greedy one with the largest estimated value 5
6,h
3.3 NEW APPROACH TO ESTIMATE VALUE FUNCTION
Now that we have a discrete policy set, we still need estimate the two expectations in Theorem 3.1 We design a new algorithm (Algorithm 4 details can be found in Appendix E)) based on the technique of LSVI Jin et al., (2000b) estimate R,, an) given policy æ, reward r and exploration data. Algorithm 4 can estimate the expectations accurately simultaneously for all л E IT and (that appears in the minimization problem) given sufficient exploration of the first h - layers. Therefore, under our layer-by-layer exploration approach, after adequate exploration for the first h - layers, la
Algorithm 4 provides accurate estimations for En,d d and Er, [0(SE, an) (E=,, - - an)] As a result, the (1) we solve serves as an accurate approximation of the minimization problem in Theorem 3.1 and the solution TA of is provably efficient in exploration.
*For more details about explorative policics, please refer to Appendix For details about policies evaluate, please refer Appendix
5

---

Published as a conference paper at ICLR 2023
Finally, after sufficient exploration of all H layers, the last step is to estimate the value functions of all policies in II We design a slightly different algorithm (Algorithm details Appendix D) for this purpose. Based on LSVI, Algorithm takes II and reward function as input, and estimates V (r) accurately given sufficient exploration for all layers.
ALGORITHMS
In this section, we present our main algorithms. The algorithm for the exploration phase is Algorithm 1 which formalizes the ideas in Section 3 while the planning phase is presented in Algorithm 2
Algorithm 1 Layer-by-layer Reward- Free Exploration via Experimental Design (Exploration)
1: Input: Accuracy Failure probability 5.
2: Initialization:
(og(dH/e6)) Error budget for each layer Cse_ Construct 11 in
H2
Section 3.2 Number of episodes for each deployment Cade Cnd Cf
Dataset = 0.
3: for h = 2, H do
4: Solve the following optimization problem.
5:
Thh
argmin
max E
an) -dsh, (1)
=e =
6/3 stt Anin S. Cg
R t/3
6:
where En, is Ex (o(sn an (o)s)s an) [ ax)
EstimateER( a(s a) ;= 1, D))
7:
Ex ((sh; on) T
EstimateER (fs, a) T (N --)-11(65 ()s,
G h, 81). // Both expectations are estimated via Algorithm
8:
for n = 1,2, .... N do
Run Ty and add trajectory {&] a. he(m) to D. // Run Policy Ty for N episodes. 10: end for
9:
end for
12: Output: Dataset D.
We apply layer-by-layer exploration and Ty is the stochastic policy we deploy to explore layer h. For solving The we approximate generalized G-optimal design via (I). For each candidate and ã, we estimate the two expectations by calling EstimateER (Algorithm 4 details in Appendix E). EstimateER is generic subroutine for estimating the value function under a particular reward design. We estimate the two expectations of interest by carefully choosing one specific reward design for each coordinate separately, so that the resulting value function provides an estimate to the desired quantity in that coordinate. [ As mentioned above and will be made clear in the analysis, given adequate exploration of the first h 1 layers, all estimations will be accurate and the surrogate policy Ta sufficiently explorative for all directions at layer h.
Exploration Phase.
The restriction on Amiu (Êx) is for technical reason only, and we will show that under the assumption in Theorem 5.1 there exists valid solution of ( Lastly, we remark that solving ( is inefficient in general. Detailed discussions about computation are deferred to Section 7.2
Algorithm 2 Find Near- Dear-Olt Policy Given Reward Function (Planning)
1: Input: Dataset D from Algorithm] Feasible linear reward function r = (rk (
2: Initialization: Construct Ieeval in Section 3.2 // The set of policies evaluate.
c/3
3: for E 1e do
4: (T*(r) = Estimate (T. 81). // Estimate value functions using Algorithm
5: end for
6: π arg ellsaa
(r)).. // Output the greedy policy w.r. (r)).
7: Output: Policy
FFor E. what we need to handle is matrix reward Φ and stochastic policy π E A(I1)2)) we apply generalized version of Algorithm to tackle this problem as discussed in Appendix

---

Published as a conference paper at ICLR 2023
Planning Phase. The output dataset D from the exploration phase contains sufficient information for the planning phase. In the planning phase (Algorithm{) 2). we construct a set of policies to evaluate and repeatedly apply Algorithm (in Appendix[D] to estimate the value function of each policy given reward function. Finally, Algorithm Putputts the policy with the highest estimated value. Since 'D has acquired sufficient information, all possible estimations in line 4 are accurate. Together with the property that there exists near-optimal policy in e/3
we have that the output र is near-optimal.
5
MAIN RESULTS
In this section, we state our main results, which formalize the techniques and algorithmic ideas we discuss in previous sections.
Theorem 5.1. We run Algorithm 7 to collect data and let Planning(.) denote the output of Algorithm 2 There exist universal constants C1 C2 C3. Cs.Ca= such that for any accuracy c > O and failure probability 8 >> O, as well as < Caa (o/(1//r) with probability - 5, for any feasible linear reward function v, Planning(r) returns a policy that is e-optimal with respect to v. In addition, the
H(X
deployment complexity of Algorithm is H while the number of trajectories is O d' H(
2²
The proof of Theorem 5.1 is sketched in Section 6 with details in the Appendix. Below we discuss some interesting aspects of our results.
Near optimal deployment efficiency. First, the deployment complexity of our Algorithm D is optimal up to a log-factor among all reward-free algorithms with polynomial sample complexity. according to a / (N,,H) lower bound (Theorem B.3 of Huang et al. (2022)) In comparison, the deployment complexity of RFLIN (Wagenmaker et al. (022b) can be the same as their sample complexity (also ( HD (e)) in the worst case.
Near optimal sample complexity. Secondly, our sample complexity matches the best-known sam- ple complexity (d H3 / (Wagemmaker et al. 2022b) of reward-free RL even when deployment efficiency not needed. It is also optimal in parameter and up lower-order terms, when compared against the lower bound of ((d 2 /²²)") (Theorem 2 of Wagenmaker et al. (2022b))
Dependence on X" A striking difference of our result comparing to the closest existing work (Huang et al. 2022) is that the sample complexity is independent to the explorability parameter X in the small-c regime. This highly desirable because we only require non-zero X to exist, and smaller X does not affect the sample complexity asympiotically. In addition, our algorithm does not take > as an input (although we admit that the theoretical guarantee only holds when e small compared to )²). In contrast, the best existing result (Algorithm 2 of Huang et al. (2022) requires the knowledge of explorability parameter Vmin and sample complexity of v min) for any e > 0. We leave detailed comparisons with Huang et al. (2022) to Appendix
Sample complexity in the large-c regime. For the case when is larger than the threshold: H(**}²
Oadi/2 log(1/>+)> we can run the procedure with e C.dF/9log and the sample complexity will
be Ö H² (x+J) (.r))): So the overall sample complexity for any 0 can be bounded by Ö 2 8
d
- + (A*J+)
This effectively says that the algorithm requires a "Burn-In" period before getting non trivial results.
Similar limitations were observed for linear MDPs before (Huang et al. 2022 Wagenmaker &
Jamieson 2022 so it not a limitation of our analysis.
Comparison to Qiao et al. (202)). Algorithm 4 (LARFE) Qiao et al. 2022
tackles reward-free
exploration under tabular MDP in (HF) deployments while collecting O 8 A
trajectories. We generalize their result to reward-free RL under linear MDP with the same deployment complexity. More importantly, although a naive instantiation of our main theorem to the tabular MDP only gives S²A"H") ), a small modification to an intermediate argument gives the same Ö S²A"A which Ö( 22
matches the best-known results for tabular MDP. More details will be discussed in Section 7.1
1 Cr, C2, C3 are the universal constants in Algorithm 1
V/min in Huang al. (2022) is defined as Mnin min H]] minja --1 max= V R.. (c0) 0)a which is also measurement of explorability. Note that Vmni always upper bounded by and can he arbitrarily small.
7

---

Published as a conference paper at ICLR 2023
6 PROOF SKETCH
In this part, we sketch the proof of Theorem 5.1 Notations i, E, C, (i E [4)), II IIeval E and E, are defined in Algorithm We start with the analysis of deployment complexity.
Deployment complexity. Since for each layer h E [H], we only deploy one stochastic policy Ta for exploration, the deployment complexity is H. Next we focus on the sample complexity.
Sample complexity. Our proof of sample complexity bound results from induction. With the choice of and N from Algorithm suppose that A is empirical covariance matrix from data up to the
k-th deploymen assume maX E, Li V V0 (1) T - o7, - (h- 1)7
A-1
holds and prove that with high probability, max = Exly ((h,, an) (A (0hh. an) S ?.
Note that the induction condition implies that the uncertainty for the first h layers is small, have the following key lemma that bounds the estimation error of Σ, from II
Lemma 6.1. With high probability, for all E A( 15 - BRo ll Cad
According to our assumption on c, the optimal policy for exploration Tे satisfies that
Amin (Ra 2 Ha Therefore, TH is feasible solution of (T) and it holds that:
max Ea (o(sn, an) J(N Em.. " "0(s), an) S Ren
max Ea [o(s), an) (N- Eng) "olsh, an) Ren
Moreover, due to matrix concentration and the Lemma 6.1 we derive, we can prove that (gIng) )-1 > (gaz)-1 and (N ) > (2A/)=1 In addition, similar to the estimation error of Ex, the following lemma bounds the estimation error of Ee (o(s,, (n)TT( - at)) from
Lemma 6.2. With high probubility, for all के E IT E ((11773) such that Amin (Ex)) 2 Czd HEL
E ((sn, " (NN En) "'6(s,'(,a an) - Es an)) 7 (N- (.) 6(sb, an))
2²
2d
With all the conclusions above, we have (E, is short for E, Ex(0n07,))
32
5d
4N
E²
max (n)) REll
( an)] +
AN
2²
max E& (a[( sh, an) T(N mm;)- (0s an)) #Ell;73
8
2 max Ee(o(sh, an) ) T(N =xz) -'p(sn, [()ssnaa))= #E
max Eg (o(s,, an) T (N. -mm) an) #e
2
max Ee(o(sn, an) J TNN (mm))_mm)) #Ell-x0
max E& Bsin an) ((2At) (Ssh. an)] #e
8
8
2
Ea / elyolsh,nn an) ( -A an)
max
2 Re 4/5
As a result, the induction holds. Together with the fact that IIyaal is subset of 11 we have max Ex EH Volsh, (A)) (osn an) & He. We have the following lemma.
Lemma 6.3. With high probability. for all π e 11eps and r, - < Õ(H HE HE
Finally, since Neval contains c e/3-optimal policy, the greedy policy with respect to v=((r) is coptimall.
"Detailed definition is deferred to Appendix F.4
i"Solution of the actual minimization problem. detailed definition in (39)
"xr B.g (6n The proof through direct calculation, details deferred Appendix F.6
8

---

Published as a conference paper at ICLR 2023
7 SOME DISCUSSIONS
In this section, we discuss some interesting extensions of our main results.
7.1 APPLICATION TO TABULAR MDP
Under the special case where the linear MDP is actually tabular MDP and the feature map is canonical basis (Jin et al., 2020b), our Algorithm [ and 2 are still provably efficient. Suppose the tabular MDP has discrete state-action space with cardinality |S] S. |A] A, let dm ming sup, min,,a d% (s, a) > O where dj, is occupancy measure, then the following theorem holds.
Theorem 7.1 (Informal version of Theorem H.2). With minor revision to Algorithm 7 [and when e is small compared to dm- our algorithms can solve reward-free exploration under tabular MDP within H deployments and the sample complexity is bounded by Ö S2 AHH
The detailed version and proof of Theorem 7.1 are deferred to Appendix 1. due to space limit. We highlight that we recover the best known result from Qiao et al. (2022) under mild assumption about reachability to all (state,action) pairs. The replacement of one d by S is mainly because under tabular MDP, there are A different deterministic policies for layer h and the log-covering number of TT can be improved from (dd to ÖS5). In this way, we effectively save a factor of A.
7.2 COMPUTATIONAL EFFICIENCY
We admit that solving the optimization problem ①I is inefficient in general, while this can be solved approximately exponential time by enumerating и from a tight covering set of A (111)7)) that the issue of computational tractability arises many previous works (Zanette et al. 2020a Wagenmaker & Jamieson 2022) that focused on informatiin--hhoortic results under linear MDP, and such issue is usually not considered as a fundamental barrier. For efficient surrogate of (T). we remark that possible method is to apply softmax (or other differentiable) representation of the policy space and use gradient- optimization techniques to find approximate solution of (T).
</3 ). Note
7.3 POSSIBLE EXTENSIONS TO REGRET MINIMIZ.ATION WITH LOW ADAPTIVITY
In this paper, we tackle the problem of deployment efficient reward-free exploration while the optimal adaptivity under regret minimization still remains open. We remark that deployment complexity is not an ideal measurement of adaptivity for this problem since the definition requires all deployments to have similar sizes, which forces the deployment complexity to be S if we want regret bound of order Ö(VT). Therefore, the more reasonable task to design algorithms with near optimal switching cost or batch complexity. We present the following two lower bounds whose proof is deferred to Appendix H.2 Here the number of episodes is K and the number of steps T' == KH.
Theorem 7.2. For any algorithm with the optimal Ö(Vpoly(dd HYT) regret bound, the switching cost is at least Q(dH log T).
Theorem 7.3. For any algorithm with the optimal Ö( Oly/oly HyT) regret bound, the number of batches is at least 52( log, + log log T).
To generalize our Algorithm to regret minimization, what remains is to remove Assumption 2.1 Suppose we can do accurate uniform policy evaluation (as in Algorithm 2 with low adaptivity without assumption on explorability of policy set, then can apply iterative policy elimination (i.e., eliminate the policies that are impossible to be optimal) and do exploration with the remaining policies. Although Assumption 2. is common in relevant literature, it not necessary intuitively since under linear MDP, if some direction is hard to encounter, we do not necessarily need to gather much information on this direction. Under tabular MDP, Qiao al. (2022) applied absorbing MDP to ignore those "hard to visit" states and we leave generalization of such idea as future work.
8 CONCLUSION
In this work, studied the well-motivated deployment efficient reward-free RL with linear function approximation. Under the linear MDP model, we designed a novel reward-free exploration algorithm that collects Ō 2 trajectories in only Hf deployments. And both the sample and deployment complexities are near optimal. An interesting future direction to design algorithms to match our lower bounds for regret minimization with low adaptivity. We believe the techniques develop (generalized G-optimal design and exploration-preserving policy discretization) could serve as basic building blocks and leave the generalization future work.
(

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The research is partially supported by NSF Awards #2007 117. The authors would like to thank Jiawei Huang and Nan Jiang for explaining the result of their paper.
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-23200 2011.
M Mehdi Afsar, Trafford Crump, and Behrouz Far. Reinforcement learning based recommender systems: A survey, arXiv preprint 1rXiv:2101.000 2021.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-2011 2020.
Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, pp. 1184-1194, 2017.
Peter Auer, Nicolo Besa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235 256, 2002.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with aalue-targeted regression. In International Conference Machine Learning, pp. 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learming. In Proceedings of the 34th International Conference on Machine Learning-Vii -oolume 70, pp. 263 272.. JMLR. org, 2017.
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.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(0ct):213-23,, 2002.
Nicolo Cesa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. In Advances in Neural Information Processing Systems, pp. 1160-1168, 2013.
Xiaoyu Chen, Jiachen Hu, Lin F Yang, and Liwei Wang. Near-optimal reward-free exploration for linear mixture mdps with plug-in solver. arXiv preprint arXiv:21 2021.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountablc reinforcement learning. International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for batched bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7340-7348, 2021.
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 SCi::2101.0099/ 2021.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glymn, and Yinyu Ye. Se- quential batch learning in finite-action linear contextual bandits. arXiv preprint arXiv:2004.06321, 2020.
10

---

Published as a conference paper at ICLR 2023
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 8971-9019 PMLR, 2022.
Jiawei Huang. Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie- Yan Liu. Towards deployment- efficient reinforcement learning: Lower bound and optimality. In International Conference on Learning Representations, 2022.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. q-learning provably efficient? In Advances in Neural Information Processing Systems, pp. 4863-4873, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pp. 4870-4879, PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406-13418 2021.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithiic Learning Theory, pp. 865-891. PMLR, 2021.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning polynomial time. Machine learming, 49(2-3):209-22) 222, 2002.
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 International Journal of Robotics Research, 32(11)1128--1274, 2013.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, and Shixiang Gu. Deployment- efficient reinforcement learning via model-based offline optimization. In International Conference on Learning Representations, 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, pp. 7599-7608. PMLR, 2021.
Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems, 34: 7598-7610, 2021.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):660-66 681, 2016.
Dan Qiao, Ming Yin, Ming Min, and Yu- Yiania Wang. Sample-efficient reinforcement learning with loglog(T) switching cost. In International Conference on Machine Learning, pp. 18031-18061. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2023
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, pp. 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.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Andrew Wagenmaker and Kevin Jamieson. Instance-dependent near-optimal policy identification in linear mdps via online experiment design. arXiv preprint arXiv:2207.025733 2022.
Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pp. 22022-234222 22429. PMLR, 2022a.
Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward- free rl is no harder than reward-aware rl in linear markov decision processes. In International Conference on Machine Learning, pp. 22430-22456 PMLR, 2022b.
Ruosong Wang. Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward-fres reinforcement learning with linear function approximation. Advances in neural information processing systems, 2020.
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, 2021.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features.
In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: survey. ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
Andrea Zanette and Emma Brunskill. Tighter problem-dependerr regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312, PMLR, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989, PMLR, 2020a.
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:117566 1766, 2020b.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-based reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 34: 1582-1593, 202
Xuezhou Zhang, Adish Singla, et al. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 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 learning via reference-advvntagee decomposition. Advances in Neural Information Processing Systems, 33: 15198-15207, 2020c.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Variance- confidence set: Variance- dependent bound for linear bandits and horizon-free bound for linear mixture mdp. arXiv preprint arXiv:2101. 12745, 2021b.
12

---

Published as a conference paper at ICLR 2023
Zihan Zhang, Yuhang Jiang, Yuan Zhou, and Xiangyang Ji. Near-optimal regret bounds for multi- batch reinforcement learning. arXiv preprint arXiv:2210.082..8, 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory, pp. 4532-4576. PMLR, 2021.
Zhenpeng Zhou, Steven Kearnes, Li Li, Richard N Zare, and Patrick Riley. Optimization of molecules via deep reinforcement learning. Scientific reports, 9(1):1-10, 2019.
13

---

Published as a conference paper at ICLR 2023
A EXTENDED RELATED WORKS
Low regret reinforcement learning algorithms. Regret minimization under tabular MDP has been extensively studied by a long line of works (Brafman & Tennenholtz, (2002, Kearns & Singh 2002 Jaksch et al., 2010 Osband et al. 2013; Agrawal & Jia 2017; Jin et al.) 2018)) Among those optimal results. Azar et al. (017) achieved the optimal regret bound D(VISA for stationary MDP through model-based algorithm, while Zhang et al. (2020c) applied Q-learning type algorithm to achieve the optimal Ō SA) regret under non-stationary MDP. Dann et al. (2019) provided policy certificates in addition to stating optimal regret bound. Different from these minimax optimal algorithms, Zanette & Brunskill (2019) derived problem-dependent regret bound, which can imply minimax regret bound. Another line of works studied regret minimization under linear MDP. Yang & Wang 2019) developed the first efficient algorithm for linear MDP with simulator. Jin al. (2020b) applied LSVI-UCB achieve the regret bound of Ō (VVd3 (HT). Later, Zanette et al. 2020a) improved the regret bound to O( at the cost of computation. Recently, Hu et al. (2022 first
reached the minimax optimal regret Ö(V H(TTH via computationally efficient algorithm. There are some other works studying the linear mixture MDP setting (Ayoub et al., 20200 Zhou et al.) 202 I
Zhang et al. 2021b) or more general settings like MDP with low Bellman Eluder dimension (iin
ct al. 2021).
Reward-free exploration. Jin et al. designed an algorithm while using EULER
(2020a) first studied the problem of reward -frerd-free exploration, they
Zanette & Brunskill 2019) for exploration and arrived
at the sample complexity of Ö(S AH+ This sample complexity was improved by Kaufmann et al. 2021) to AHS²AHH/*? by building upper confidence bound for any reward function and
any policy. Finally, minimax optimal result Ö(S AH*/ /c²) was derived in Ménard et al. (2021) by constructing a novel exploration bonus. At the same time, a more general optimal result was achieved by Zhang et al. (2020b) who considered MDP with stationary transition kernel and uniformly bounded reward. Zhang et al. (2020a) studied a similar setting named task-agnostic exploration and designed an algorithm that can find c-optimal policies for N arbitrary tasks after at most ASS log 2 episodes. For linear MDP setting, |Wang et al. (2020) generalized LSVI-UCB and arrived at the sample complexity of (dd (e2). The sample complexity was improved by Zanette et al. (002bb) to Ó(d /²²2) through approximating G-optimal design. Recently, Wagenmaker et al. (2022b) did exploration through applying first-order regret algorithm (Wagenmaker et al.) (202aa) and achieved sample complexity bound of ( (tdfHH//p H /E²), which matches their lower bound (ddd 2 /e2) up to H factors. There are other reward-fres works under linear mixture MDP (Chen et al. 2021 Zhang et al. 2021ab. Meanwhile, there is a new setting that aims to do reward-fres exploration under low adaptivity and Huang al. (2022): Qiao et al. (2022) designed provably efficient algorithms for linear
MDP and tabular MDP, respectively.
Low switching algorithms for bandits and RL. There are two kinds of switching costs. Global switching cost simply measures the number of policy switches, while local switching cost is defined (only under tabular MDP) as Nfwoed [[(h, =EKI K-1 s) E [H] x S (s) + ( (s)} where K the number of episodes. For multi- aamti- bandits with A arms and T episodes, (Cesa-Bianchh et al.
(2013) first achieved the optimal O(VAT) regret with only ( log log T') policy switches. Simchi Levi & Xu 2019) generalized the result by showing that to get optimal Ö(VTT) regret bound, both the switching cost upper and lower bounds are of order A log log T. Under stochastic linear bandits,
Abbasi-Yadkori et al. (2011) applied doubling trick to achieve the optimal regret (ddVT) with O(d T") policy switches. Under slightly different setting, Ruan et al. (2021) improved the result by improving the switching cost to O(log log T') without worsening the regret bound. Under tabular MDP. Bai et al. (2019) applied doubling trick to Q-learning and reached regret bound 3(VH3SAD with local switching cost O(H's S A log T). Zhang et al. (202cc) applied advantage decomposition to improve the regret bound and local switching cost bound to O(V AT) and O(H2S log T), respectively. Recently, Qiao et al. (022) showed that to achieve the optimal ((VT) regret, both the global switching cost upper and lower bounds are of order HSA log log T. Under linear MDP, Gao et al. (202)) applied doubling trick to LSVI-UCB and arrived at regret bound Ō H²T) while global switching cost is OddH log T). This result is generalized by Wang al. (2021) 1) to work for
14

---

Published as a conference paper at ICLR 2023
arbitrary switching cost budget. |Huang et al. (2022) managed to do pure exploration under linear MDP within O(HH) switches.
Batched bandits and RL. In batched bandits problems, the agent decides a sequence of arms and observes the reward of each arm after all arms in that sequence are pulled. More formally, at the beginning of each batch, the agent decides list of arms to be pulled. Afterwards, list of (arm,reward) pairs is given to the agent. Then the agent decides about the next batch (Esfandiari et al.) 2021). The batch sizes could be chosen non-adaptively or adaptively. In a non-adaptive algorithm, the batch sizes should be decided before the algorithm starts, while in an adaptive algorithm, the batch sizes may depend on the previous observations. Under multi aamlt- bandits with A arms and T episodes, (Cesa-Bianchh et (2013) designed an algorithm with O(VAT) regret using O(log log T)
batches. Perchet al. (2016) proved a regret lower bound of 9( for algorithms within M batches under 2-armed bandits setting, which means (log log T') batches are necessary for regret bound of Ö(VT). The result is generalized to K K-armed bandits by Gao et al. 2019 Under stochastic linear bandits, Han et al. (2020) designed an algorithm that has regret bound Õ(VT) while running in O (log log 7 batches. |Raa et al. (2021) improved this result by using weaker assumptions. For batched RL setting, Qiao et al. (2022) showed that their algorithm uses the optimal O(H + log log batches to achieve the optimal (vTT) regret. Recently, the regret bound and computational efficiency is improved by Zhang al. (2022) through incorporating the idea of optimal experimental design. The deployment efficient algorithms for pure exploration by Huang et al.) (2022) also satisfy the definition of batched RL.
B GENERALIZATION OF G-OPTIMAL DESIGN
Traditional G-optimal design. We first briefly introduce the problem setup of G-optimal design. Assume there is some (possibly infinite) set A C Rd, let т A + [0, 1] be a distribution on A so that
EaEA [(a)= = (TT) E Radd and g(TT) E R are given by
V(*) = Σ Ta))aT,, T, g( = max |allv(=) aeA
aEA
The problem of finding a design π that minimises g is called the G-optimal design problem. G-optimal design has wide application regression problems and it can solve the linear bandit problem (Lattimore & Szepesvári 2020). However, traditional G-optimal design can not tackle our problem under linear MDP where we can only choose π instead of choosing the feature vector ø directly.
In this section, we generalize the well-known G-optimal design for our purpose under linear MDP. Consider the following problem: Under some fixed linear MDP, given fixed finite policy set II, want to select a policy Tu from (III (distribution over policy set II) to minimize the following term:
max E, 6ss, on) (E 01 10ss,, 4x), FE
where the Sh, aj follows the distribution according and the dy, follows the distribution of policy We first consider its two special cases.
Special case If the MDP deterministic, then given any fixed deterministic policy x, the trajectory generated from this π is deterministic. Therefore the feature 6) at layer h is also deterministic. We denote the feature at layer h from running policy π by dr, In this case, the previous problem reduces to
min max (E,, 2n.0,) Dx
(II) HEll
which can be characterized by the traditional G-optimal design, for more details please refer to Kiefer & Wolfowitz (1960) and chapter 21 Lattimore & Szepesvári 2020). According Theorem 21.1 of Lattimore & Szepesvári (2020). the minimization of 3) can be bounded by d, which is the dimension
of the feature map ø.
Special case 2. When the linear MDP is actually a tabular MDP with finite state set |S] = S and finite action set |A| A, the feature map reduces to canonical basis in Rdd SRAA with Φ(s, a) ((xa))
15

---

Published as a conference paper at ICLR 2023
(Jin al. 2020b). Let di (s. I (sh
8, Q/
a) denote the occupancy measure, then the
previous optimization problem reduces to
d (s.
min max TTE
WEll
(8,a)
(
Such minimization problem corresponds finding policy To that cover all policies from the policy set II. According to Lemma in Zhang et al. (2022) (we only use the case where m = 1), the minimization of (4) can be bounded by d SA.
Different from these two special cases, under our problem setup (general linear MDP), the feature map be much more complex than canonical basis and running each will lead to distribution over the feature map space rather than a fixed single feature. Next, we formalize the problem setup and present the theorem. We are given finite policy set and finite action set & (we only consider finite action set, the general case can be proven similarly by passing to the limit (Lattimore & Szepesvári (020)), ) where each II is distribution over & (with (a) denoting the probability of choosing action a) and each action E O is vector in Rd. In addition, can be any distribution over II. In the following part, we characterize as a vector in R [m with (()) denoting the probability of choosing policy
Let ((x) Eeeg (a))aa' and V (p)) Exen ((T))))T))))) function we want to minimize is g = max Enco T Ta)aa V(u) la.
Even ((TT) E0s4 (a)aaa The
Theorem B.1. Define the set & {a E $ F = > 0}. If span 3) R.d, there exists distribution je' over II such that g(u²) s d.
Proof of Theorem B. Define [(x) = log det (nx) and take n² to be
μ = arg max f(u).
/
According to Exercise 21.2 Lattimore & Szepesvári (020)) f is concave. Besides, according to Exercise 21.1 of Lattimore & Szepesvári (2020), we have 1
d
log (A(()) del(A(())
T (r(adj(A) A(t) TT(A-1 A(t))
di
Plugging f in, directly have:
(vf())) = -TV-V
Σ T V(n)-
ac
In addition, by direct calculation, for any feasible μ4,
Σ [(())( Tr( m(x)
Tr(la) =
Hlll
aE
Since 1z is the maximizer of f. by first order optimality criterion, for any feasible μa,
O2(ff(1)) -- 1*)
=M(T))
((T))
Σ x(aa V =M'(T) Σ
T(a)a (
sEll
aell ae
Σ ((x) Σ
x(a)a V(p)) d.
For any II.
choose i be Dirac n, which proves that for any E II. Enco xaaaa ((pt)-aa- S d. Due to the definition of g(x²), we have g(H²) I d.
Remark B.2. By replacing the action set t with the set of all feasible features at layer h, Theorem B.I B.oss that for any linear MDP and fixed policy set II.
min max E, ((Sn, an) T (n ((sn, an) s d.
(5)
ETTT TEll
This theorem serves as one of the critical theoretical bases for analysis.
16

---

Published as a conference paper at ICLR 2023
Remark B.3. Although the proof is similar Theorem 21.1 Lattimore & Szepesvári (2020), our Theorem [. I is more general since it also holds under the case where each a will generate distribution the action space. In contrast, G-optimal design is special case of our setting where each x will generate fixed action from the action space.
Knowing the existence of such covering policy, the next lemma provides some properties of the solution of (2) under some additional assumption.
Lemma B.4. Let xtx arg m max En E on) (Em, )n - an). Assume that (IT)) Amia (B, 2 X", then it holds that
( Φh 6
(6)
d
where d the dimension of and Amin denotes the minimum eigenvalue.
Before we state the proof, we provide the description of the special case where the MDP a tabular MDP. The condition implies that there exists some policy सं (III such that for any s, a 8 A, di (s. a) 2 X², where (x,-) is occupancy measure. Due to Theorem B.1 x² satisfies that
(s.0)) a)
maX sEll
Σ (s.a)ESxA
di (s, S SA.
For any (8,a) E 8 x A. choose Ts.. = arg max di (8, a) and (s," > (s, > X Therefore, it holds that dj. (s) 2 SA for any 8, a, which is equivalent to the conclusion of 6
Proof of Lemmal B.4 If the conclusion (6) does not hold, have Amin (E,, (u0 1 which implics that Amax
x Denote the eigenvalues of (E,= on on ) by < A S
X2 S ... < Ay. There exists a set of orthogonal and normalized vectors {ō, (o:heed such that Φ is corresponding eigenvector of X;
According to the condition, there exists मे E AlII) such that Amin Aminn ( 2 X². Therefore, for any E Rd with || = 1, @ (E= )o= = (o(o) o)² 2 A². Now we consider E#0,, ) - on.
where E,, is short for E,, on holds that:
Eadh (En.) On = E&
o 6:)0:] (En.)) 1
(0t dc)..)
Ex
(0) (.) 2 01 (E )
> Ex b2) 01 (E..) ) 11 %
>X x = d.
where the first equation is due to the fact that (Ø: Jaej forms a set of normalized basis. The second equation results from the definition of eigenvectors. The last inequality is because our assumption ((n. 6 -- )
) and condition (A ||01|2 = 1, o (E=0LØ) ) (0), Φ) 2 X*).
Finally, since this leads contradiction with Theorem B.1 the proof is complete.
C CONSTRUCTION OF POLICY SETS
In this section, we construct policy sets given the feature map Φ(-.)). We begin with several technical lemmas.
17

---

Published as a conference paper at ICLR 2023
C.I TECHNICAL LEMMAS
Lemma C.1 (Covering Number of Euclidean Ball (Jin et al. 2020b)). For any E > 0, the e-covering number of the Euclidean ball in R with radius
upper bounded by (1+ 2
Lemma C.2 (Lemma B.1 of Jin et al. (2000))) Let wj denote the set of weights such that Q (s, a)
(ő(s, a), wg). Then | 11 & v
Lemma C.3 (Advantage Decomposition), For any MDP with fixed initial state st, for any policy n it holds that
" (i(s)) - (T = E,
(vv - Q (s,, an),,
h=1
here the expectation means that Sh; On follows the distribution generated by
Proof of Lemma C.3
(i1(s1) (V7(s)) = Ex (s)
Ex (T(1).
[Vi - Qi(s), ai)] 11 Σ ((3))),
EES
(st) - Q7 a1)] Eggnn V2 (82) V2 (s2)
Ex, Σ (s)) (sh an),
where the second equation is because Bellman Equation and the forth equation results from applying the decomposition recursively from h = 1 to H.
Lemma C.4 (Elliptical Potential Lemma, Lemma 26 of Agarwal et al. 2020 Consider a sequence of d x d positive semi- semi-definite matrices , with max, T T (X.).
1 and define Mo
I.-' Mi = Mi-1 + Xt. Then
T ) Tr(X,MZ1) 2d 2ogo
C.2 CONSTRUCTION OF POLICIES TO EVALUATE
We construct the policy set eval given feature map o( :). The policy set IIeval satisfies that for any feasible linear MDP with feature map o, evall contains near-optimal policy of this linear MDP. We begin with the construction.
Construction of [ceaa Given e > 0, let W be 277 -over of the Euclidean ball Bd (2HVd)) = {a
Rd, || < 2Hvd) Next, we construct the Q-function set Q = (Q(s, a) 6(s a) w E W). Then the policy set at layer is defined as A E [H], 1I, = {s(s) = arg max Q(s, a)s.)]l E Q).
with ties broken arbitrarily. Finally, the policy set 11 is II 1I, 11. x x ll
Lemma C.5. The policy set 1I satisfies that for any h [H].
log [L S dllog1 + SH 3 Ō(d).
In addition, for any linear MDP with feature map 6(.,)), there exists (M1, "., (TH) such that
Th E for all h E [H] and v 2 V*
Proof of Lemma
C.5 Since W a 2H covering of Euclidean ball, by Lemma we have
log W| S dlog(1 + 8H2 Vd.
18

---

Published as a conference paper at ICLR 2023
In addition, for any w in W, there is most corresponding Q and one Th I Therefore, it holds that for any E [H].
log [T,. < log [ S log [W] dog((1 8H3
For any linear MDP, according to Lemma C.2 the optimal Q-unction can be written as:
(s (ø(s, a,s,,a,,. wf),
with 11 I /d. Since Wis is covering of the Euclidean ball, for any h E [H] there exists 277
wh E W such that |mm wall2 I 2 Select Qs a) <(s,a) wn from Q and (T(s)) =
arg maX Qn a) from II, Note that for any h. a E H x SSXA A A.
(Q Qx(s,a)) - (o(ssa)]l
1 Wm 12 -
(8)
2H
Let (M1, " "H. we prove that this is c-optimal.
Denote the optimal policy under this linear MDP by x", then we have for any s, E S x [H].
())s - (s, (s))) =sQ, (/(()) - Qn(s,
( m (s)) (Q, ()()) - (n(ss (Qn - (T
2H +0+
2H H
(9)
where the inequality results from the definition of n and (8) Now we apply the advantage decomposition (Lemma
it holds that:
(in(s) - VT (s1) =E, V (s,) Qi (sh.aa)
SH. H
where the inequality comes from
Remark C.6. Our concurrent work Wagenmaker & Jamieson 2022 also applies the idea of policy discretization. However, to cover c-optimal policies of all linear MDPs. the size of their policy set is log [[T]| S O(dH2. log !) (stated in Corollary of Wagenmaker & Jamieson ( 2022))). In comparison, our IIgeal satisfies that log |M < H log [0 S O(dH log ?), which improves their results by factor of H. Such improvement is done by applying advantage decomposition. Finally, by plugging in our IIrall into Corollary of Wagenmaker & Jamieson 2022). we can directly improve their
worst-case bound by factor of H.
C.3 CONSTRUCTION EXPLORATIVE POLICIES
Given the feature map ((:,-) and the condition that for any h E [H]. sup, Amin (Bx X where π can be any policy, we construct a finite policy set II that covers explorative policies under any feasible linear MDPs. Such exploratory is formalized for any linear MDP and h [H], there exists some policy π in (([T=p)) such that (F= is large enough. We begin with the construction.
Construction of I[ Given > 0, consider all reward functions that can be represented as
r(s, a) v ((s,a) a) T -
(10)
where Σ is positive semi-definite According to Lemma D.6 Ji et al. (020b), we can construct
2H -cover R. of all such reward functions while the size of R, satisties log R2, dl log(1 32f12 /
19

---

Published as a conference paper at ICLR 2023
For all h E [H] denote II, {s((s) arg maxaeea R.} with ties broken arbitrarily. Meanwhile, denote the policy 11, (w.rtt e) in the previous Section C.2 by I Finally, let
I,, = I L.I. be the policy set for layer h. The whole policy set is the product of these h policy sets, _ 11 X ... HlH.c.
Lemma C.7. For any O, we have 11 C [1gap, In addition, log [1n.el S 2d log(1 + 32H2 For any reward r that is the form of (10) and h E [H], there exists a policy E II such that
Egr(sh, (n) sup Esr(sh an)
Proof of Lemma C.7 The T.
The conclusion that Ie C II is because of our construction: Ih
In addition,
log [h,ell log [ + log IT log [Rel + dllog(1 + 8H2 Vd
32H Vd
2d
s 2d log(1 +
2
Consider the optimal Q-function under reward function r(sh, as) (reward always other layers).
We have (7,s, a) r(s, a) and for i S h - 1,
as) =0 + Σ ())ss.
*'S
= a)(s,a), Σ (
E'ES = (0(8, a), w
for some w Rd with ||will2 2vd. The first equation because of Bellman Equation and our design of reward function.
Since O covered by R. up to 2H accuracy while O < h 1) is covered by in section C.2 up to TH accuracy, with identical proof to Lemma C.5 the last conclusion holds.
Lemma C.8. Assume sup, Amin (F 2 X2, ife 2 we have
(2+)²
sup #EA(1
Amiin (B 64dlog(1/2+)
Proof of Lemma C.8
Fix t
61d (2+)²
we construct the following policies:
Ti is arbitrary policy in I
For any i E [t]. Σ; = Ej=1 En, TN a)) = Vo(s,a) (1+ 1os-) Due to Lemma
C.7 there exists policy Ti+1 E IT such that 2 an) 2 sup, Exri(sn, an)
The following inequality holds:
E
(I E1-1)-1
Exr, oT (1 (1+ E--1)
1=1
E TT + -
(1I)
Tr(E., 2n (T (i-)-)))
2dl log(1 g
20

---

Published as a conference paper at ICLR 2023
where the second inequality holds because of Cauchy-Schwarz Schwarz inequality and the last inequality holds due to Lemma C.4
Therefore, have that s Bx V 0% (I (I+ Ix-1)-1m1
2dlog(1+t/d)
because of our
choice of v 1 and /. 64d God(1/(/ [A*}²
According to Lemma E. 1.14 of Huang et al. 2022 we have
that Amiu (Σ 2
Finally, choose π =
we have и E A(I) and
(A*)2
Amin (Br
64d (1g(/2))
C.4 A SUMMARY
Policy sets
Cardinality
Deseription
Relanionship with each other
The set of all policies
Infinity
The largest possible policy set
Contains the following two sets Subset all policies Subset TTrp
Explorative policies: I2r
log [ O(d))
Sufficient for exploration
Policies evaluate: MTqua
log [m Ō(d)
Uniform policy evaluation over I1. sufficient for policy identification
Table 2: Comparison of different policy sets.
We compare the relationship between different policy sets in the Table 2 above. In summary, given the feature map o):,-) of linear MDP and any accuracy e, we can construct policy Ie which satisfies that log [ = Ödd). At the same time, for any linear MDP, the policy set I[ is guaranteed to contain near-optimal policy. Therefore, it suffices to estimate the value functions of all policies in [e accurately.
Similarly, given the feature map o(::-) and some that is small enough compared X we construct policy set II which satisfies that log | = (d?). At the same time, for any linear MDP, the policy set I[ is guaranteed to contain explorative policies for all layers, which means that it suffices do exploration using only policies from 1I=2p,
D ESTIMATION OF VALUE FUNCTIONS
suffices to estimate the value functions of policies in Ie In this section, design algorithm estimate the value functions of any policy in I[ given any reward function. Recall that for accuracy 6o, we denote the policy set constructed in Section C.2 by Ieval and the policy set for layer h is denoted by Ieval
According to the construction of eval in Section C.2 and Lemma C.5
Ourr condition that sup, Amin (E. 2 X* implies that for any Rd with ||ll|
max, (6 u)? 2 X*. Therefore, the proof of Lemma R.14 of Huang al. 2022 holds by plugging
21

---

Published as a conference paper at ICLR 2023
D.1 THE ALGORITHM
Algorithm 3 Estimation of (T) given exploration data (EstimateV)
1: Input: Policy to evaluate π IIgeat Linear reward function (rhthejmn bounded in [0. 1].
Exploration data {sh- 0% ((.)) [[N] Initial state
2: Initialization: 1++1(:+ + O, (+) + O.
3: for h H,
do
4: An - I+ En (5% of (s aT)
5: Th + (An) E> oss 0 V1+1
6:
Qu(:;)) (d(:.)) th + ( 1) (.HH-
7:
V.(() (T().
8: end for
9: Output: (s1).
Algorithm 3 takes policy from II and linear reward function as input, and uses LSVI to estimate the value function of this given policy and given reward function. From layer H to layer 1, we calculate A₁ and Wi, to estimate Q7 in line 6. In addition, according to our construction in Section C.2 all policies in II are deterministic, which means we can use line 7 to approximate Wang et al. (2020). However, there are two key differences. First, Algorithm 2 of Wang et al.] (2020) aims to find near optimal policy for each reward function while we do policy evaluation for each reward and policy. In addition, different from their approach, do not optimism, which means we do not need to cover the bonus term. This is the main reason why we can save factor of vd.
Vg. Algorithm 3 looks similar to Algorithm
D.2 TECHNICAL LEMMAS
Lemma D.1 (Lemmaa D.4 Jin al. (0200))). Let { 1 be stochastic process state space with corresponding filtration [Fr1r=n Let { Ør 100 r--1 be an Rd-valued stochastic process where o- E FT-1, and || | S 1. Let Ae I + Σx T= OTOTT Then for any ō > O, with probability at least 8. for all k 2 0, and any E V so that sup, (V S H, we have:
d
No 8
Σ o (V [[
< 4H²
log(k: + + log( + 86222
2
where No is the c-covering number of V with respect to the distance däst(V, V\) = sup,, V(x) V'(x)). Lemma D.2. The Wh in line 5 of Algorithm is always bounded by ||wal|2 S HVdN.
Proof of Lemma D.2 For any Rd with ||0||2 1, we have
10 mnl = T|8T (An)
( a (+-
#=1
N
0 (An) - 105) an))a H
==1
N BT (A -10 1 o(s 0% (AA)) -1 (s an)
N
<H
m=1
<
<HV.N.
The second inequality is because of Cauchy-Schward inequality. The last inequality holds according to Lemma D.1 of Jin et al. (2020b).
22

---

Published as a conference paper at ICLR 2023
D.3 UPPER BOUND ESTIMATION ERROR
We first consider the covering number of V,, in Algorithm 3 All V2, can be written as:
V+(+) = (ol ma (-)) (wx + +0x) [o.
(12)
where 0% is the parameter with respect to ra (ry(s, a) (Ø(s, a), 0x)))
Note that Ie x We (where We is c-cover of (2H ( (N)) provides c-cover of {V.). Therefore, the e-covering number Nº of (V)) is bounded by
8H2 Vd
+ d + 4H VHvdN
log NC log 2 log [&ll S d'log(1 +
(13)
co
Now we have the following key lemma.
Lemma D.3. With probability 1 - for any policy л E IIeval and any linear reward function r that may appear in Algorithm
3 the (een derived by Algorithm 3 satisfies that for any h [H]
N
Hd v Voou
Σ 0% ((++((h+))) - Σ
S ScHvd.
+ log
c00
S'ES
A7
for some universal constant c e>0
Proof of Lemma D.3 The proof is by plugging e Hyd in Lemma D.1 and using 13
N
Remark D.4. Assume the final goal is to find e-optimal policy for all reward functions, we can choose that co Z poly(() and N S poly(d, H. Then the R.H.S. of Lemma D.3 is of order ((Hvd), which effectively saves a factor of vd compared Lemma A.I Wang al. 2020
Now we are ready to prove the following lemma. Lemma D.5. With probability
for any policy π E IIewel and any linear reward function r that may appear in Algorithm 3 the hei] and }wn]ee belm) derived by Algorithm satisfies that for all h, s, a [H] x S A.
Hd Egd
N 8
(o(s,a) Wh
Σ Pa(ss scHVa /
log((
+ log
())(s,
S'ES
for some universal constant d'
This part of proof is similar to the proof of Lemma in Wang et (2020) For completeness, we state it here.
Proof of Lemma D.5 Since (a a) = a(s,a) (T
(n'),, we have
Σ
a( wh. Twn
EES
for some | || < Hdd. Therefore, we have
Φ(s,a) a) Wr Σ Pa(s' s, a))
8'E8
N
= () (es,a)((A)) (AAA)~
Σ
t Vh (
Σ
n=1
EES
=)(s,a) T((s,))(AAn)
(An)-1
9h Vn44(5hh11) Anwn Σ
(14)
= ((An)
Wih Σ Φ (d)) Wh
=p(s, TTT()) (An)
Σ 1h
Vh+z(5h+t)
- Σ Pa Pa(s''ss,, 1 a Vutz((6) wh
==1
23

---

Published as a conference paper at ICLR 2023
It holds that,
((s,a)((NN) (Aa))
Σ 6
(n+1(1h+1)) - Σ Ph(s'lo% (h)
n=
a1lb(s,))llAz"
Vi+t(sh+t))
E
Pa(s' a/) Vn+zz(ss)
(15)
Ph
S
ScHVd. Vlog
logl
Hd E08
+ log
N
(1
8
for some constant e due to Lemma D.3 addition, we have
(Ø(8,)) (Ax)~ mmal= s | A) ||TAllA.' S HVd. 11((8, a))aa,
Combining these results, have
Hd v log(
()) Wh - Σ
ScHV
'g + log(
11 a))aa,
E'ES
Finally, the error bound of our estimations are summarized in the following lemma.
Lemma D.6. For Te and linear reward function let the output of Algorithm 3 be (r).
(r).
Then with probability - 6, for any policy II and any linear reward function r, it holds that
Hd log( cgg
N ) + log( 8
11
(ー())- - ( sdHvd
Ex Σ
1o(s an)l
(16)
h=1
for some universal constant d > 0.
Proof of Lemma D.6 For any policy т E Neval and any linear reward function r, consider the V functions and Th in Algorithm
we have
(V((s)) - VT (s:) E. (1) w1 +r(( - Σ
P(5(ss (1),
s'ES
<En 0(s1, a1) Σ (18))1s,, + E, Σ
(16]s,,a)) -2(6'))1((((()))
s'ES
E'ES
Hd
N
SE,CHVd. v Voog( 600
500) + log( ) [I)(,,, + (2(22 (52
....
H
sCHVdd / Vogg 606
Hd
+ log
ES
Σ ==1
[6(sh, (nlla,
(17)
where the first inequality results from the fact that (s1) Lemma D.5 The forth inequality is due to recursive application of decomposition.
(11) E [0,
H). The third inequality comes from
Remark D.7. Compared to the analysis in Wang et al. (2020) and Huang al. (2022), our analysis saves factor of Vd. This is achieved by discretization of the policy set and bypassing the need to cover the quadratic bonus term. More specifically, the log-covering number of our l1gral is Ö(d). Combining with the covering set of Euclidean ball in Rd, the total log log-covering number is still Ö(d). In contrast, both previous works need to cover bonus like v //()))) (A)-))(-,)) which requires the log-covering number be (d.).
24

---

Published as a conference paper at ICLR 2023
E GENERALIZED ALGORITHMS FOR ESTIMATING VALUE FUNCTIONS
Since II we construct in Section is guaranteed to cover explorative policies under any feasible linear MDP, it suffices do exploration using only policies from IT In this section, we generalize the algorithm we propose in DoctionnDoor our purpose during exploration phase. To be more specific, we design an algorithm to estimate (sh, oh) for any policy [[epp and any reward r. Recall that given accuracy é1, the policy set we construct in Section C.3 is 1 and the policy set for layer is "1.h'
E.1 THE ALGORITHM
Algorithm 4 Estimation of r,,,, an) given exploration data (EstimateER)
1: Input: Policy evaluate π ITep.
Reward function r(s, a) and its uniform upper bound A. Layer h. Exploration data {s.. oz (1 Initial state 81-
2: Initialization: Qu(:,-) + r(;)), (.(()) + Qu m.)-).
N 3: for h h= h
1, ......11 do
4: An - + En 06 a ( TT
5:
Wh + -An) 'A o a
h+t (s 4+1)
6:
Qī(:.)) + (o(.-) ( (0.A].
7:
Vi()) (T((T()))))))
8: end for
9: Output: (81).
Algorithm 4 applies LSVI to estimate Brr(s,,a, for any π E Ieap (according to our construction, all possible 's are deterministic), any reward function r and any time step h. Note that the algorithm takes the uniform upper bound A of all possible reward functions (i.e.. for any reward function r that may appear as the input,
[0, AD) as the input, and uses the value of A to truncate the Q-function in there are two key differences. First, the reward
line 6. Algorithm function is non-zero at only one layer in Algorithm 4 while the reward function in Algorithm can be any valid reward functions. In addition, Algorithm 4 takes the upper bound of reward function as input and uses this value to bound the Q-functions while Algorithm uses as the upper bound.
+ lookss similar to Algorithmm
E.2 TECHNICAL LEMMAS
Lemma E.1 (Generalization of Lemma D.4 Jin et al. (2020b)). Let {I.) 1.20 be stochastic process on state space with corresponding filiration { Let (Ø, 100 be an Rd valued stochastic process where dy E F1 and || S 1. Let Ag I + Σk= S. Then for any 5 > O, with probability at least 1 - ò. for all k 2 O, and any V V so that sup, (V S A, we have:
k
[
log(k +1 + log( No.)
S 4A22
+ 8K222,
2
8
A7
where No is the e-covering number of V with respect to the distance dist(V, V') sup, V(x) V'(x))- Lemma E.2. IfA the Wy in line 5 of Algorithm is is always bounded by ||,,y112 S VdN.
Proof of Lemma F.2 The proof is almost identical to Lemma D.2, the only difference is that H is
replaced by 1.
E.3 UPPER BOUND OF ESTIMATION ERROR
We first consider the covering number of all possible V, in Algorithm 4 In the remaining part of this section, we assume that the set of all reward functions to be estimated is R. with uniform
25

---

Published as a conference paper at ICLR 2023
upper bound Ag < 1. In addition, assume there exists e-covering R. of R with covering number (Rg( = B.
For fixed h [H], under the case where the layer to estimate is exactly h, V4 can be written
V&(+) (-)).
(18)
The set 1 R. provides an e-covering Vn. Thus the covering number under this case is (i [
In addition, if the layer to estimate is some h > h, then Va can be written as:
Va(+) ( nh (.)) (hh (o.a))
(19)
where the set T x W. (We is e-covering of B dN)) provides an e-covering of Vz. The covering number under this is | -Wel.
Since all possible Vn is either the case in (8)) (the layer to estimate is exactly h) or (9) (the layer to
estimate is larger than h), for any [ the c-covering number Nr all possible V. satisfies that:
log No. < log( [
41 RR, + | (Wel)
< <log(
[T
61.h
+ log RR,l) log (og()
(20)
32H /d
+ dlog(1 + 2v
<2d log(1 +
+ B
ef
Now we have the following key lemma. The proof is almost identical to Lemma D.3 so we omit here.
Lemma E.3. With probability 1 - 6, for any policy Ie any reward function r E R that may appear in Algorithm (with the input A AAR and layer h, the {Vi Milhen derived by Algorithm satisfies that for any h E [1-
1}.
N
Σ
1/+1(0%/11
Σ - Pi(''s (V))
#'ES
(21)
ScAR V da log(
dPloog
Hd
d dlog(
NV + BAR/N + +log( 1 8
610
for some universal constant c > 0.
Now we can provide the following Lemma whose proof is almost identical to Lemma D.5 only difference is that H is replaced by AR.
The
Lemma E.4. With probability 1 - for any policy E 1erF, any reward function r E R that may appear in Algorithm 4 with the input
functionn
A and layer h, the {V; Vilee he(m and {w, heep- derived
by Algorithm 4 satisfies that for all h 8, E [h- S
[o(5, a) WH
Σ
(22)
sdAR de log e,0¹
Hd
N + d d x) + BA + log(5) [|o([s, (|(((s
for some universal constant d' >>0 0.
Finally, the error bound of our estimations are summarized in the following lemma.
Lemma E.5. For any policy π E IIsz, any reward function r E R that may appear in Algorithm
(with the input A = AR) and layer h, let the output of Algorithu 4 be Bar(Sh, ax). Then with
We will show that all cases consider in this paper satisfy these assumptions.
26

---

Published as a conference paper at ICLR 2023
probability 1 - 5. for any policy I any reward function E RR and any layer h, it holds that [xr(sh, an) (sh((hh as)]
SdAA V dc logl c1d
Hd d
N + dlog( g) + BAR/N Ex
Σ h=1
A-1 az)lla
(23)
for some universal constant d'
For any policy E TT any reward function r E R and any layer h, consider the [Vil functions and [wn)ken-aj in Algorithm we have (,,, an) = (=1) Besides, we abuse the notation and let denote the reward function where rw a) = 1(' h)r(s, a), let the value function under this r be (8), then ( (sy, an). holds that
Proof of Lemma E.S
Esn, an) (sr((hh =11 (s1(
R
o 181,00 a1) T 10
Σ
01
s'ES
E (11) (
Σ
+ EE Σ
Pi a1) (1))(s) V2
s'ES
s'ES
Hd
N
SE,d AR V d /lllo
log
+ dloog 8)
BAR/N (1((,1, a1)ll, E=(VV((82) V25 (x2)
618
...
Hd
N
se AR V d
log(
d logg
BAR/N E
I| a2)lla?"
F. (a(n)) V7 (sn))
8
h=11
=d AR V ddllog
log(
Hd
d llog(
) BAR/N
N
Er
P=
(24)
where the first inequality results from the fact that (s1) E ARl The third inequality comes from Lemma E.4 The fifth incquality is due to recursive application of decomposition. The last equation holds since V.(() V/ (-) r(;,,(())))) (.)).
E.5 we can see that the estimation error at layer h can be bounded by the summation of uncertainty from the previous layers, with additional factor of (Ad). Therefore, if the uncertainty of all previous layers are small with respect to 11 we can estimate EgTh accurately for any _1 and any reward from large set of reward functions.
Remark E.6. From Lemmal
Remark E.7. Note that we only need to estimate E an) accurately for π E II For takes policy E I1rp with probability pi (for E [K), then we define
), if AII
Ear(sh, an) = Σ Pt Er,r(sn, EE(R]
(25)
where Egr(sh, an) is the estimation we acquire w.rl policy π and T an) is the output of Algorithm 4 with inpul n, E [[ezp, Assume that for all E _IT [E, an) - F r( an)l
we have for all A(II==P), EEr an) EEr(SE, an)l < <E, Pi p:ppiE,, E,, an)-aaa.. E., r(sh an) S
Therefore, the conclusion of Lemmal E.5 naturally holds for π E A(II
F PROOF OF THEOREM 5.1
Recall that & log(dH/e6),, Cie
Hayd The explorative policy set we construct is II while the
policies to evaluate is Ignral Number of episodes for each deployment is N = C.ds
24
Cf
27

---

Published as a conference paper at ICLR 2023
In addition, En is short for E. while Σx is short for [ For clarity, restrict our choice that < C1 1 and C2 C3 We begin with detailed explanation of Σ, and E# (shh TNV. - mt)
from T
F. DETAILED EXPLANATION
First of all, as have been pointed out in Algorithm 1 En is short for [o(s,, ap (s)) an) Assume the feature map is o(s,a) a) (s, (s, a), (s, a). (a((s,))) where (5, a) E RR Then
the estimation of covariance matrix is calculated pointwisely. For each coordinate i,j E [d] [d]
we use Algorithm 4 estimate [s, ap) Ex, (s, 11 More specifically, for any т E _1 -(())) 2E - L, where Ed is the output of Algorithm with input т, r(s, ()s,a)
(s..)) with A layer h and exploration dataset D. Therefore, the set of all possible rewards is R (=. (i.j) [d] [d]. The set R. is a covering set of itself with log-covering number B. = log RR) = 2 log d. In addition, note that the estimation Σx(() = Σ for all j. which means the estimation Σ. is symmetric. The above discussion tackles the case where E IT for the general case where E A(II.")). the estimation is derived by (25) in Remark E.7
In the discussion below, we only need to bound [E=000% - E.onoh ll2 for all x E II. and the same bound applies to π E )(
The second estimator is Ex ( aA) T 1 an)] which is calculated via directly applying Algorithm 4 with input म E uT r(s,a) = a( (N- -x)-" with A He 12, layer h and exploration dataset D. Note that the validity uniform upper bound A holds since we only consider the case where Amiu Amiu({r) (Σx) 2 dHH which means that Amin (N (x)= > HE. Eodl Hud Therefore the set of all possible rewards is subset of R (r(s,a) a) ó(s,a) (2) los, a) ammmm 2 Cdd and the e-covering number is Cie
Cie
characterized by Lemma F3 below.
F.2 TECHNICAL LEMMAS
In this part, we state some technical lemmas. Lemma F.1 (Lemma H.4 of Min et al. (021)). Let ④ : A Rd satisfies [|o(s, S for all s, S x A. For any K > 0, >
define GK =EK- 00sk, (k))(sk, ax) Xla where
(sk, ox) 's are i.dd samples from some distribution v. Then with probability -5
Gx
Gk
4V202 2
2d log
1/2
E,
(26)
K
K
VK
Lemma F22 (Corollary of Lemma D.6.. There exists universal constant cp > 0, such that with our choice of eo = S and N Cad H the multiplicative factor of (16) satisfies that Offz
d'H dHVd. v Vogg
Hd, 50d
+ log( N 8 cDHVa. log( C2dHl Cied
).
(27)
Proof of Lemma F.2) The existence of universal constant cp holds since c' in 16 is universal constant and direct calculation.
Lemma E3 (Covering number). Consider the set of possible rewards R. {r(s,a)
Cie 6(8, a) (O)(TT)))))))))))))) (E)- (1(,, (008,))) a) Amin (E) 2 G Let Ar Ca and N = C
H4,
Cie
we
have that the Ag Ag- cover RA R satisfies that for some universal constant OF 0,
C2dH
B log( A I c log(
Cie )
(28)
The transformation ensure that the reward larger than O.
28

---

Published as a conference paper at ICLR 2023
Proof of Lemma E.3
The conclusion holds due to Lemma D.6 of Jin et al. (2020b) and direct
calculation.
Lemma F.4 (Corollary of Lemma E.5 There exists universal constant dR > 0 such that for the
first case Section Fl with our choice of E1 ÿ. A= B 2oog(d) and N Cod the Cf
multipliaative factor
23 satisfies that
Hd 9
N BAR/N ce dlog( C2dH C₁e8
d'R
de log
d'log(
(29)
8
Proof of Lemma F.4 The existence of universal constant de holds since d' in (33 universal con- stant and direct calculation.
Lemma F5 (Corollary of Lemma E.5
There exists universal constant eg 0 such that for
the second case in Section
F.1 with our choice e1 3. A
Cxe
B
Hr H2
c log( CadH and Cse
H'
Cfe² the multiplicative factor of
23 satisfies that
N d ( 610
Hd
log( C2dH Cieō
d'AR v de logl
BA c
(30)
C2d2
Proof of Lemma F.5 The existence universal constant dj holds since c' in 23 universal con- stant and direct calculation.
Now that have the universal constants cD. cp, CP, Cr. for notational simplicity, let cæ max max ). Therefore, the conclusions of Lemma F.4 and F5 hold if we replace de with cy.
F.3 CHOICE UNIVERSAL CONSTANTS
In this section, we determine the choice of universal constants in Algorithm and Theorem 5.1 First, C1 C2 satisfies that Ci C2- = 1,0 < Ci < and the following conditions:
cp Vd. log( O2dHl
1 VVVVloog
dH
(31)
Cied
301
C2dH E
CE
Hr log(
Cied
2d
(32)
It is clear that when C2 is larger than some universal threshold and C₁ J. the constants C₁ C2 satisfy the previous four conditions. Next, we choose Cg such that
C3
d.
CadHl
log cF log(
(33)
Cied
and C4 = S0C' C3. Since cp, CE, are universal constants, our C1, C2, C3, Ca are also universal constants that are independent with the parameters e,e,8 8.
F.4 RESTATE THEOREM 5.I AND OUR INDUCTION
Theorem F.6 (Restate Theorem 5.1p. We run Algorithm collect data and let Planning(.) denote the output of Algorithm 2 For the universal constants Ci, C2. C2, C4 we choose, for any > 0 and
8 > as well C2 log(1/X"]' with probability 1 for any feasible linear reward reward function
H(*+²
Planning(r) returns a policy that is c-optimal with respect to r.
H(**> Throughout the proof in this section, we assume that the condition < C.d7/2 log(1/X*) holds. Then
state our induction condition.
29

---

Published as a conference paper at ICLR 2023
Condition F.7 (Induction Condition). Suppose after h deployments (i.e., after the explo- ration of the first h - layers), the dataset DDh11 hh ( (0%) for all h [H]. The induction condition is:
and Ah-1
I 1+ 0f E, xe
665% 97) 10(56 o7)
5h 1)e.
(34)
Suppose that after h deployments, the dataset D DNy o ( for h E [H]. We will prove that given condition F7 holds, with probability at least 1 - 6, the following induction holds:
(s 0 T x(NN) and A
(o(onnoa) -Ahh) as) SE.
max EN x 11
(35)
Note that the induction
35
naturally implies that
max E Σ V (1 o7)
S he.
(36)
8 EEI PP
Suppose after the whole exploration process, the dataset D = { a ( and A
+ HNN (T))) for all E [H]. If the previous induction holds, we have with probability 1 Ho,
max E,
Σ Ø(sh (ANn)) ax) S He.
(37)
3 TEl SP
Next begin the proof of such induction. We assume the Condition F7 holds and prove (35).
F.5 ERROR BOUND OF ESTIMATION
Recall that the policy apply explore the h-th layer is
(d(shaa)) T(V. T
" (38)
Wh
argmin TEA( stt. Aman (S. o2 HH
max ER FEll"
where the detailed definition of Σx and Es [Ss,, an) JNN--NN-NN (ssh, an)] explained in Section F.I In addition, we define the optimal policy मं for exploring layer h:
argmin ER [ø(sh, Tx) (N Σx) -0ss an)]
(39)
where EE means the actual expectation. Similarly, Ex is short for Ex, [o(s,, an)o(sh an)
According to Lemma C.8 since e S C,07/2 log(1/2>) S
H(A)}
is
we have
(2+)2
sup (T)
Amin (E,
(40)
64d
Therefore, together with the conclusion Lemma B.4 and our definition of मे. holds that:
and
(A+)²
Xmin (Be, on
(41)
64d log (og()
We ignore the extreme where H is super large for simplicity. When 17 is very large, we can simply construct 1T instead and the proof is identical.
4/H
30

---

Published as a conference paper at ICLR 2023
F.5.1 ERROR BOUND FOR THE FIRST ESTIMATOR
We first consider the upper bound of
B. (o(s,, (n) an) [ (0(sn, On (8( an a1 Re-
call that (as stated first half Section F.1.. Er (0(8. an ( T is estimated through calling
Algorithm 4 for each coordinate i,j [d] x [d]. Therefore, first bound the pointwise error.
Lemma E8 (Pointwise error). With probability 8, for all π _r and all coordinates (i,j)
[d] x [d]. it holds that
CadHe
Bo an (n))(sn
R (x an (0) an) T6o) S
(42)
4
Proof of Lemma F.8
We have
h Σ | o7 a2>ll(a0-71-
3Hd
LHS <d
d2 log(
+ d log( 8 + 2og(dd) E
C2dH Cicō
(43)
Sep dlog(
He
CzdHeL
4
The first inequality holds because Lemma E.5
The second inequality results from Lemma F.4
and and
our induction condition F.7 The last inequality is due to our choice C3 (33).
Now we can bound lemma.
Ex (d(n,, on (o)) an) J Er(o(sh, an ( an) T] by the following
Lemma E9 (&2 norm bound).
With probubility for all ng holds that
Czd² HEL
[os0, an)((sn,a))
-- (n)ss,,
[o(s,
(44)
Proof of Lemma
F.9
The inequality results from Lemma F.8 and the fact that for any X E Rdxd
||||2 < |X]]F.
(45)
Note that the conclusion also holds for all E A(II. due to discussion in Remark E.7
According to our condition that
H(A")2
=
and 41
we have
C4d ToR(1/A*)
800 Cad ToR(1/A*)
(A+)2
50
50/0
503d HE
Anin(Ea (Ea
(46)
64d log log(1/>*)
4H
4
Therefore, under the high probability case Lemma F9 due to Weyl's inequality,
Amin (Re; (noT) 2 Czd2 He.
(47)
We have (47 implics that मं is a feasible solution of the optimization problem I and therefore, at)
max E [0ssh, an) T(N Ex.) (ssss < max RE
ES [0(sh: and T (NN Emg)) (((), an)
#Elleap
(48)
where Ta is the policy apply explore layer h and Amin (E.r,)) Czdl He.
31

---

Published as a conference paper at ICLR 2023
F.5.2 ERROR BOUND FOR THE SECOND ESTIMATOR
We consider the upper bound of
RRg (p(ss:aa) TnaaaTTT (tn) an) Es [0($): (T (NN.5))'' (sh an)
Recall that Ex [0(sh, T Σn) d(s an) is calculated by calling Algorithm with A
OrdSH1a- Note that only need to consider the case where ā E 3 A and
Amin (Ex) 2 Czd HEL.
Lemma F.10. With probability 1 - 5, for all स E
n and all x E A( such that Amin (Ex) 2
Czd Het, it holds that:
6²
Ex (shh (N [hs) Ex [o(s and T -n)- - an)
$
(49)
2d2²
Proof of Lemma F.10
We have
C2dH
h |, ap)1((
LHS Sce
log( C2cō
)
Ex
CydHHo H
(50)
2
S 22
HE
2d
The first inequality results from Lemma
E.5 and Lemma
F.5
The second inequality holds since our
choice of C2 32 and induction condition E.
Remark F11. We have with probability - ā (under the high probability case in Lemma F.I0 due
the property of max for all x E A(II such that Xmin (E.) 2 Cgd? HE,, it holds that:
ES (0(h,, an) (NN 1--)
ES -NN- an)
62
max REn
max
S
REn
2d
(51)
F.6
MAIN PROOF
With all preparations ready, we are ready to prove the main theorem. We assume the high probability cases in Lemma F. (which implies Lemma F99 and Lemma F.T0hold. First of all, we have:
Ep [0(sh, (s)))an))T (n (NN -1 "'hss,nnn an)
max
Rel1op
E²
max Es (0sh)) (n)) an) Tn) (NN Em;)) "0(s) an) *en
+
2d
22
max Es (0shh and T(N.T(NNNNNN Σ$z) - 16sh am)]
+
(52)
#e Sxp 3
8
Eg (s)) T 4N
( - an)
+ 62
max *P $
5d 22
322
4N
8
8
The first inequality holds because of Lemma F.10 (and Remark F.11). The second inequality is
because under meaningful case, d 2 2. The third inequality holds since under the high probability
case in Lemma F.9
Cad' Ta > Σx; 9r; can imply 2x; > 5 E and thus ($+;)-1
I 1o
The forth inequality is due to the definition of मे and Theorem B.I The last inequality holds since our choice of N and Cz.
Note that all matrices here symmetric and positive definite.
32

---

Published as a conference paper at ICLR 2023
Combining (52) and (88).
we have
3x²
max
Ex
((sh, T t an)
(53)
aell
According to Lemma
F.10 Remark
F.11
and the fact that Amin (Eira) 2 Cydc It holds that
32 max Ex ((sn, an) Emn) (0ps and #EIT $
2
(54)
8
8
Or equivalently, / max Ex (T) (N REll""
un)
Suppose after applying policy Nn for N episodes, the data we collec is {sh, he Assume
Aạ = Σ (s)) (ss) T, we now consider the relationship between An and E.y. First, according to Lemma
we have:
1 CaNd la 5 N- Em.. N 4
N Em N E.o
(55)
Besides, due to Lemma
(with C 1), with probability 1
N Emp An < A la CaNdHEE la
1 INN. Smy. 4
(56)
Combining (55) and (56). we have with probability 1 - 8.
N. ETT
1 N Ema. An < 2
(57)
or equivalently,
(N -' (2
(58)
Plugging into
588
54). we have with probability 8,
> max Eg REl
((ss,, an) T(N Exm) -1p(ss
2
2 max Ee (o(sn, an) ((2n)) ((sh, an)) #el
(59)
max Es / o(sn,
an)
2
#em
where the last inequality follows Cauchy-Schwarz Schwarz inequality.
Recall that after the exploration of layer h. A in (35) uses all previous data up to the /-th deployment, which implies that A & A, and (A & (An) Therefore, with probability - 8,
max ER V ((s,, T -AA) an) 2 max EA / ((sn, ((AR) -10(s,, an), (60) RElloap
Rell""
which implies that the induction process holds.
Recall that after the whole exploration process for all H layers, the dataset D (5%, aj (M and A have with probability 1 - -88.
NHN (T( for all h e [H]. Due induction, we
max E SP
Σ V an) (AN) $ He.
(61)
We only consider the data from layer h.
33

---

Published as a conference paper at ICLR 2023
In addition, according to Lemma
C.7
IIg
C I " have
max
Ex
@(sn,
an) s HC.
(62)
mellg
Given (62) we are ready to prove the final result. Recall that the output of Algorithm 3 (with input and r) is (r)). With probability 1 for all feasible linear reward function r, for all II holds that
3Hd
H
(v*())-v'(> SdHVa
V Vlog( cd
+ log
E,
(lo(sn. an)ll
h=1
C2dH Cied
(63)
SCDHVd log(
-HE
1 - HE- 3C1
-E=
where the first inequality holds due to Lemma D.6 The second inequality because of Lemma F2
and (62). The third inequality holds since our choice of C₁ 31 The last equation results from our definition that é
Cic
H²Vd
Suppose #(r) arg ma V²(r). Since output policy f(r) is the greedy policy with respect (r), have
(r) - (a(r) (r) ( + p)())()) -
(F) + (r( - -
2e
(64)
In addition, according to Lemma C.5
(*(r) - (+( $ 3. Combining these two results, we have
with probability 1 6, for all feasible linear reward function
V*(r) (*()) Se.
(65)
Since the deployment complexity of Algorithm is clearly bounded by H, the proof of Theorem 5.]
completed.
G COMPARISONS ON RESULTS AND TECHNIQUES
In this section, we compare our results with the closest related work (Huang al. 2022). We begin with comparison of the conditions.
Comparison of conditions. In Assumption 2.1 we assume that the linear MDP satisfies
min sup Amin (Er[o(s,, an (ss,, J) >
HE(H)
In comparison, Huang et al. 2022) assume that
min min max V E [TTT0)] 0.
Pmin
hE(A] |
Overall these two assumptions analogous reachability assumptions, while our assumption is slightly stronger since viin lower bounded by X*
Dependence on reachability coefficient. Our Algorithm only takes as input and does not require the knowledge of X*, while the theoretical guarantee in Theorem 5.1 requires additional condition that is small compared to X*. For larger than a problem-dependeet threshold, the theoretical guarantee no longer holds. Such dependence similar to the dependence on reachability coefficient Miin in Zanette et al. (0200) where their algorithm also takes input and requires be small compared
reqquirrs
34

---

Published as a conference paper at ICLR 2023
to Piiin In comparison, Algorithm 2 in Huang et al. (2022) takes the reachability coefficient V/nin as input, which a stronger requirement than requiring e to be small compared to X*
Comparison of sample complexity bounds. Our main improvement over Huang et al. 2022 is the sample complexity bound the small-e regime. Comparing our asymptotic sample complexity bound O _ with O( d²=²) in Huang et al. (0022), our bound is better by factor of 2 where Vmin is always upper bounded by I and can be arbitrarily small (please see the illustration below). In the large-c regime, the sample complexity bounds in both works look like poly(d, H, X (or poly(d, H, _1)) )) and such "Burn in" period is common in optimal experiment design based works Emiin Wagenmaker & Jamieson 2022).
Illustration of Umin- this part, we construct some examples to show what Mmin will be like. First, consider the following simple example where the linear MDP is defined as:
1. The linear MDP is tabular MDP with only action and several states 1, 1).
2. The features are canonical basis (Jin et al. 2020b and thus d = S.
3. The transition from any (s. a) E S A at any time step h E [H] is uniformly random.
Therefore, under linear MDP 1, both vinin in Huang et al. (002)) and our X are à and our improve- ment on sample complexity is a factor d² Generally speaking, this example has a relatively large Piinn and there are various examples with even smaller Vmin- Next, construct the linear MDP that is similar to the linear MDP but does not have uniform transition kernel:
1. The linear MDP is tabular MDP with only one action and several states (A = 1, 1).
2. The features are canonical basis (Tin al. 2020b and thus d
3. The transitions from any (s, a) E S x A any time step h E [H] are the same and satisfies ming'ss (s a) Pmin-
Therefore, under linear MDP 2, both v in Huang et al. (2022) and our X are Pmin (Pmin S a and our improvement on sample complexity is a factor of d/ d/Pmni which is always larger than d² and can be much larger. In the worst case, according to the condition (e viii for the asymptotic sample complexity in Huang al. (2022) to dominate, Pmin 12 min can be as small as e1/4, and the sample complexity in Huang et al. 2022) is (x+b), ). which does not have optimal dependence on e. In conclusion, improvement on sample complexity is least factor of d and can be much more significant under various circumstances.
Technique comparison. We discuss why we can get rid of the = dependence in Huang et al.
2022 First, instead of minimizing max, E. Ex|lonlla,; we only minimize the smaller [|oolll where the maximum is taken over our explorative policy set. Therefore, our approximation of generalized G-optimal design helps save the factor of 1/v In addition, note that in Lemma 6.3 the dependence on is only vd, this is because we estimate the value functions (w.rt and r) instead of adding optimism and using LSVI. Compared to the log-covering number (d)) of the bonus term V / A 1 - our covering of (policy n. -evval linear reward r),) has e/3.k
max T
log-covering number Ödd)
H PROOF FOR SECTION 7
H.1 APPLICATION TO TABULAR MDP
Recall that the tabular MDP has discrete state-action space with |S| S. |A| = A. We transfer our Assumption 2. to its counterpart under tabular MDP, and assume it holds.
Assumption H.1. Define (:..) to be the occupancy measure, i.e. di a) = Pr = s, s,a, = a). Let d,, ming sup, mins,a a di, a), we assume that dm 0.
35

---

Published as a conference paper at ICLR 2023
Theorem H.2. We select E
Cie Tep
N Io
{all deterministic policies) and
H²
N-
CaSAr CaS A
in Algorithm
and
The optimization problem replaced by
Cfea
(s.0) =EA(Uo) &. (s.0), ( ( Hello
argmin
max
(66)
(8,
where di, (s, a) is estimated through applying Algorithm 4 for any reward function r, Algorithm returns policy that is e-optimal with respect to r. In addition, the deployment complexity of Algorithm 2 is H while the number of trajectories is O A²A""
Suppose S C,SA' with probability 1-
Hdm
Proof of Theorem H.2 Since the proof is quite similar to the proof of Theorem 5.1 we sketch the
proof and highlight the difference to the linear MDP setting while ignoring details.
Suppose after the h-th deployment, the visitation number of (h, s, a) is N (s,
a).
Then our induction
condition becomes after the (f- 1)-th deployment, max,
Σ h--1 h=1 Es,a
(s,0)
S (h - I)E.
V VN (s.a)
We base on this condition and prove that with high probability, max,
dy (s.a)
SE.
(NT(s,a)
First, under tabular MDP, Algorithm T is equivalent value iteration based on empirical transition kernel. Therefore, due to standard methods like simulation lemma, we have with high probability, for any π E Hy and reward r with upper bound A (the Vi function is the one we derive in Algorithm 4
A-1
[Er an) Egr(sh, a+)l SE
Σ
Pp- -Pi)
-V (87.
1=1
h-1
A |/, Pall
S
h-1
(67)
<0
AVS.
E.
N (g)
h=1
(s, (s,a)
<ō
AVS. h=1
(s,
<AVS HEE
Now we prove that our condition about is enough. Note that with high probability, for all policy E To and the estimation error of d a) is bounded by vS- Hr. As result, the estimation error can be ignored compared to d,, a) or df (s, a). With identical proof to Section F.6 we have the induction still holds.
From the induction, suppose Nu(s,, a) is the final visitation number of (h, s, a), we have He. Using identical proof 67 we have with high proba-
max, Σ# E.a (s.a,)) bility, for all π E Ho and r,
(Na(s.))
(-(r-- SOHVS Hz) S 2
(68)
Since IIl contains the optimal policy, output policy is e-optimal.
H.2 PROOF OF LOWER BOUNDS
For regret minimization, we assume the number of episodes while the number of steps is T: KH.
36

---

Published as a conference paper at ICLR 2023
Theorem H.3 (Restate Theorem 7.2) For any algorithm with the optimal p/polllle H)T) regret bound, the switching cost is at least S log log T).
Proof of Theorem H.
We first construct linear MDP with two states, the initial state 51 and the
absorbing state
For absorbing state $2, the choice action is only ag, while for initial state $1. the choice of actions is {ai, 02 ... Add11 1). Then we define the feature map:
(x2, ao) = (1, 0, 0, ... .0), ((81, a.) = (0, ... 0, 1.
where for 81, ag (i [d - 1], the (i + 1)-th element is while all other elements are 0. We now define the measure (4,, and reward vector Og as:
U/ (8)) = (0,1,0,0, ,0,, (x2) = (1,0,1,1, .1), Aa [H].
0n = (0, 0. rh.2. .M -hhdd-1,, where rh,s 's are unknown non-zert values.
Combining these definitions, we have: Pa (82)82, 82, un) = 1, rs (82, ao) 0, Pa(s1 a1) 1, (81 = for all h E [H]. Besides, (8222)81, 0:) = 1, (11 a.) Th for all h E [M] i 2 2.
Therefore, for any deterministic policy, the only possible case is that the agent takes action aj and stays at for the first h steps, then at step h the agent takes action (i 2 2) and transitions to $2 with reward Th,s, later the agent always stays at #2 with no more reward. For this trajectory, the total reward will be Th,s. Also, for any deterministic policy, the trajectory is fixed, like pulling an "arm" multi-armed bandits setting. Note that the total number of such "arms" with zero unknown reward is at least (d H. Even if the transition kemnel is known the agent, this linear MDP is still as difficult as multi-armed bandits problem with (ddH) arms. Together will Lemma H.4 below, the proof is complete.
Lemma H.4 (Theorem 2 in (Simchi-Levi & Xu 2019). Under the K K-armed bandits problem, there exists an absolute constant C >> 0 such that for all K 1,5 2 0, 2 2K and for all policy π with switching budget S, the regret satisfies
C log
R*(K
2
K
2-2-u(
where q(S,K) = 1- This further implies that Q(K log log T) switches are necessary for achieving Ö(VT) regret bound.
Theorem H.5 (Restate Theorem 7.3). For any algorithm with the optimal ppllpl (d, HYT) regret bound, the number of batches least 5 loga + log log T).
Corollary 2 of Gao et al. 2019) proved that under multi-armed bandits problem, for any algorithm with optimal O regret bound, the number of batches is at least A(log log T'. In the proof of Theorem H.3 we show that linear MDP can be at least as difficult as a multi-armed bandits problem, which means the Milog log T) lower bound on batches also applies to linear MDP.
Proof of Theorem H.S
H In addition, Theorem B.3 in Huang et al. (022) stated an Ω Toga NH) lower bound for deployment complexity for any algorithm with PAC guarantee. Note that deployment of arbitrary policy equivalent one batch. Suppose we can design an algorithm to get Õ(vT) regret within K episodes and M batches, then we are able to identify near-optimal policy in M deployments while each deployment is allowed to collect K trajectories. Therefore, we have M 2 2 Tog. T
Combining these two results, the proof is complete.
37


Reviews:
[{"review_id": "V7OrpnN3Z2h", "reviewer": "Reviewer_idiY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies reward-free learning for linear MDPs. In particular, the authors focus on reducing the number of deployment (or switching cost). The proposed algorithm achieves a sample complexity of $\\tilde{O}(d^2H^5/\\epsilon^2)$ and deployment complexity $O(H)$, where the order of $d,\\epsilon$ are near-optimal in the sample complexity, and the deployment complexity is tight up to constant factors.", "summary_of_the_review": "Given the considerations above, the paper is on my broaderline. I tend to accept it currently.", "strength_and_weaknesses": "Strengths: As stated above, the theorectical results of this paper are non-trivial. In technique, the major contribution is  utilizing the G-optimal design to reduce the order of $d$. There are also some interesting by-products, e.g., resutls in Section 7.\n\n\nWeakness: My major concern is the computational cost of the proposed algorithm. The authors also admit that the optimization problem (1) is computational intractable. In my opinion it should not be neglected. For the tabular case, recent work [Zhang et. al.] has achieved a computational efficient algorithm to minimize the number of batches (or deployments), where the authors manage to avoid enumeration over the policy space. So it is natural to ask whether efficient algorithm for linear MDPs is possible.\n\nReference: [Zhang et. al.]  Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GLOAv-hhA8", "reviewer": "Reviewer_y46E", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of deployment efficient reinforcement learning with linear function approximation under the reward-free exploration setting. The authors propose a new algorithm that achieves optimal deployment complexity and near-optimal sample complexity at the same time. Their techniques include an exploration-preserving policy discretization and a generalized G-optimal experiment design, which makes incremental contributions to the RL theory community.", "summary_of_the_review": "The paper considers a well-formulated theoretical problem and makes incremental improvements to existing algorithms. Although some parts of the algorithm and proof are novel, the proposed algorithm is computationally-inefficient, and the proposed techniques are dedicated to the DE linear MDP. Thus, the overall contributions are marginally below the ICLR threshold.", "strength_and_weaknesses": "Strength\nS1: The proposed algorithm achieves SOTA sample complexity and preserves optimal deployment complexity simultaneously.\nS2: The proposed exploration-preserving policy discretization looks novel.\n\nWeakness\nS1: The proposed algorithm appears to be only making limited improvement compared to existing works in (Huang et al. 2022). Specifically, the paper considered a well-formulated dedicated problem, yet only makes a factor of d improvement on sample complexity, compared to that in (Huang et al. 2022). Besides, the proposed algorithm is computationally inefficient.\nS2: The technical contribution of this paper is limited and below the threshold of ICLR. The basic algorithm framework looks similar to that in (Huang et al. 2022), except upgrading the policy set and estimating the value functions instead of optimism, as pointed out in Appendix G. Besides, the idea of estimating the value functions instead of optimism has already been proposed in (Chen et al. 2021) for reward-free exploration in linear mixture MDPs.\nS3: The overall writing is not very clear such that readers are hard to follow the technical points, while this paper focuses on algorithm techniques. It is strongly recommended that authors could provide more details about G-optimal design in the main body of the paper.\n\n(Chen et al. 2021) Chen, Xiaoyu, Jiachen Hu, Lin F. Yang, and Liwei Wang. \"Near-optimal reward-free exploration for linear mixture mdps with plug-in solver.\" arXiv preprint arXiv:2110.03244 (2021).\n\nComments and Questions\nC1: The writing of the introduction looks similar to that in (Huang et al. 2022) and does not provide much further information.\nC2: The linear MDP definition in (Jin et al., 2020b)’ paper is different from this paper. There $\\mu_h$ is a matrix, not a vector.\nC3: Assumption 2.1 is very strong and limits the generality of the algorithm, as those in (Zanette et al., 2020b; Wagenmaker & Jamieson, 2022). Since under linear MDP, if some direction is hard to encounter, we do not necessarily need to gather much information on this direction. Besides, I do not find analogous assumptions in (Huang et al., 2022).\nC4: It is more common to say different “stages” of $h$, instead of “layer”\nC5: The full-text layout is poor since the authors manually decrease the margin between paragraphs and sections. For example, there is an overlapping between the text and the footnote line.\nC6: In the paragraph below Theorem 7.1, what is the “mild assumption” to recover the best-known result from (Qiao et al. 2022).\nC7: As stated in Section 7.2, why the computational issue of the algorithm is usually not considered as a fundamental barrier? A computationally-inefficient algorithm largely hurts the significance of the proposed algorithm.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5R6k5Eqrrfz", "reviewer": "Reviewer_W2e3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies deployment-efficient reward-free exploration problems in the linear MDP setting. The authors propose an algorithm that can achieve optimal deployment efficiency.", "summary_of_the_review": "I think this paper is good overall. I did not check the details of the proof so I don't have high confidence in my assessment.", "strength_and_weaknesses": "Strength:\n\nThe theoretical results seem to be sound although I did not check all the details. The writing is clear and the discussion about prior work is sufficient.\n\nWeakness:\n\nI think this paper is a combination of several existing RL theory works. Reward-free exploration problems with linear function approximation have been studied in the literature. Deployment-efficient (similar to low-switching cost RL) problems have also been studied. This paper combines all the ingredients and resolves some additional technical difficulties to obtain the new results. This is good but I feel the novelty is not significant.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "2w-NUu86dd-", "reviewer": "Reviewer_i7oS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studied the deployment efficient reinforcement learning in linear MDP. The authors proposed new algorithms with improved sample complexity bound than previous papers as well as the near-optimal deployment complexity.", "summary_of_the_review": "Although some weakness in this paper, I still found the results interesting, and I recommend for the acceptance.", "strength_and_weaknesses": "# Strength\n\nThe sample complexity to state of the art, to my knowledge. The algorithm also seems interesting and somewhat novel.\n\n\n# Weakness\n\nI think the main issue is whether it is appropriate to claim the algorithm does not require the knowledge of $\\lambda^*$. It seems to me that the main reason the algorithm does not use the knowledge of $\\lambda^*$ is because the authors assumed that the accuracy level $\\epsilon$ is smaller comparing with $\\lambda^*$. From this perspective, it is kind of misleading to claim this paper get rid of knowledge of $\\lambda^*$. Or maybe the authors should include discussion about how to avoid knowledge of $\\lambda^*$ for arbitrary $\\epsilon$.\n\nMinor issues:\n\n(1) the linear MDP is kind of restrictive, although more general than tabular setting.\n\n(2) when $\\lambda^*$ is extremely small, the algorithm can only success when choosing a extremely small $\\epsilon$.\n\n(3) algorithm seems not computationally efficient", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster