Towards Minimax Optimal Reward-free Reinforcement Learning in Linear MDPs
Authors: Pihe Hu
Yu Chen
Longbo Huang
Venue: ICLR 2023 poster (2023)
Keywords: Reinforce Learning
Reward-Free Exploration
Linear MDPs
Learning Theory

Abstract: We study reward-free reinforcement learning with linear function approximation for episodic Markov decision processes (MDPs). In this setting, an agent first interacts with the environment without accessing the reward function in the exploration phase. In the subsequent planning phase, it is given a reward function and asked to output an $\epsilon$-optimal policy. We propose a novel algorithm LSVI-RFE under the linear MDP setting, where the transition probability and reward functions are linear in a feature mapping. We prove an $\widetilde{O}(H^{4} d^{2}/\epsilon^2)$ sample complexity upper bound for LSVI-RFE, where $H$ is the episode length and $d$ is the feature dimension. We also establish a sample complexity lower bound of $\Omega(H^{3} d^{2}/\epsilon^2)$. To the best of our knowledge, LSVI-RFE is the first computationally efficient algorithm that achieves the minimax optimal sample complexity in linear MDP settings up to an $H$ and logarithmic factors. Our LSVI-RFE algorithm is based on a novel variance-aware exploration mechanism to avoid overly-conservative exploration in prior works. Our sharp bound relies on the decoupling of UCB bonuses during two phases, and a Bernstein-type self-normalized bound, which remove the extra dependency of sample complexity on $H$ and $d$, respectively.

Published as a conference paper at ICLR 2023
TOWARDS MINIMAX OPTIMAL REWARD-FREE REIN- FORCEMENT LEARNING IN LINEAR MDPs
Pihe Hu", Yu Chen Longbo Huang!
Institute for Interdisciplinary Institute for Interdisciplinary Information Sciences Tsinghua University, Beijing, China [hph19, 9, e- @ma ils tss tsiingha www.nnghuu.u...... edu.cn, hon.ooohaanaagggttttnnnnuuu edw.euuuaeeddeeoo. cn
ABSTRACT
We study reward-free reinforcement learning with linear function approximation for episodic Markov decision processes (MDPs). In this setting, an agent first interacts with the environment without accessing the reward function in the explo- ration phase. In the subsequent planning phase, it is given reward function and asked to output an 6-optimal policy. We propose a novel algorithm LSVI-RFE un- der the linear MDP setting, where the transition probability and reward functions
are linear in a feature mapping. We prove an O(Hdd//e² sample complexity upper bound for LSVI-RFE, where H is the episode length and d is the feature dimension. We also establish a sample complexity lower bound of 52( 3 /e²). To the best of our knowledge, LSVI-RFE is the first computationally efficient algorithm that achieves the minimax optimal sample complexity in linear MDP settings up to an Il and logarithmic factors. Our LSVI-RFE algorithm is based on a novel variance-aware exploration mechanism to avoid overly-conservatie exploration in prior works. Our sharp bound relies on the decoupling of UCB bonuses during two phases, and a Bernstein-type self-normalized bound, which remove the extra dependency of sample complexity H and d, respectively.
INTRODUCTION
In reinforcement learning (RL), agent tries to learn optimal policy that maximizes the cumula- tive long-term rewards by interacting with an unknown environment. Designing efficient exploration mechanisms, being a critical task in RL algorithm design, of great significance in improving the sample efficiency of RL, both theoretically Azar et al. (201)): Ménard et al. (2021) and empirically Schwarzer et al. (2020); Ye al. (202I). In particular, for scenarios where reward signals are sparse and require multi-task settings where RL. agents are required accomplish different goals in different stages, e.g., Hessel et al. (2019): Yang et al.) (2020), efficient exploration of the environments is crucial, as it can avoid the agent from repeated learning under different reward functions, resulting in inefficiency and even intractability of sample complexity. However, the theoretical understanding is still limited, especially for MDPs with large (or infinite) states or action spaces.
reward functions, Nair et al. (2018); Riedmiller et al. (2018), or
To understand the exploration mechanism in RL, reward-free exploration (RFE) is firstly proposed in Jin et al. (2020a) to explore the environment without reward signals. RFE contains two phases: exploration and planning. In the exploration phase, the agent first interacts with the environment without accessing the reward function. In the subsequent planning phase, the agent is given a re- ward function and asked output an c-optimal policy. RFE has great significance in host of reinforcement learning applications, e.g., multi-task RL Hessel et al. (2019): Yang et al.) (2020), RL with sparse rewards Nair al. (20T8); Riedmiller et al. (0088), and systematic generalization of RL Jiang et al. ) Mutti et al. 22022). ) The minimax optimal sample complexity O SAA/²) of RFE obtained in Ménard et al. (202T) for tabular settings where S and A are sizes of state and action space, respectively. However, this bound is intractable when state and action space are large.
In this paper, we consider the RFE problem in the linear MDP setting, where the transition proba- bility and the reward function are linear in feature mapping +(.,)). The linear MDP model is an
$ Equal contribution.
Corresponding author.

---

Published as a conference paper at ICLR 2023
important formulation that provides linear function approximation for general MDP problems with large (or infinite) state and action space, and has received much recent attention in RL studies, c.g., Jin et al. (2020b); Zhou et al. (2021). Existing works in Wang et al. (2020a); Zanette al. (2020c); Chen et al. (021) also study RFF in linear MDPs. The best known sample complexity upper bound
in this setting is O(H' / obtained in Chen et al. (201)), and the best known lower bound is
(mma ( /e2) by combining results obtained in Zhang et al. (2021) and Wagenmaker et al.
(2022). This means that the following fundamental question still remains open:
Does there exist compulationeeficient and minimax optimal algorithm for RFE in linear MDPs?
We make constructive contributions to minimax optimality by proposing computationally ef- ficient algorithm LSVI-RFE, achieving the state-of-the-art sample complexity upper bound of O(H422/e /c²), which is minimax optimal up to an H and logarithmic factors. The LSVI-RFE al- gorithm based on novel variance-aware exploration mechanism with weighted linear regression to avoid weelyy-oonervvtive exploration in prior works. Accordingly, our sharp bound relies on the decoupling of UCB bonuses during two phases, and Bernstein-type self-normalized bound, which remove the extra dependency of sample complexity on H and d, respectively. We summarize the main contributions of the paper below.
We propose the LSVI-RFE algorithm for RFE in linear MDPs based on a novel variance- aware exploration mechanism with weighted linear regression to avoid overly-conservative exploration in prior works. also builds the monotonicity of constructed value functions between two phases, providing new reward-free linear RL techniques.
LSVI-RFE achieves a sample complexity of Ó d (H/dd/²), which relies on the decoupling of UCB bonuses during two phases. In addition, Bernstein-type ceff-normalized bound and the conservatism of elliptical potentials are utilized to reach optimal dependency of sample complexity on which is potentially general tool for linear reward-free RL.
We prove sample complexity lower bound of (H (ofdd/ee)) showing that LSVI-RFE is the first computationally efficient algorithm to achieve the minimax optimal sample complexity in linear MDPs up to an H and logarithmic factors.
Notations Scalars are denoted in lower case letters, and vectors/matrices are denoted in boldface letters. Denote ||æ=||* = x Aa for vector æ and positive definite matrix A, and || denotes the Frobenius norm. Denote {1...., n. as [n]. an O(b,) if there exists absolute constant >> 0 such that a, & cbn, holds for all n > 1 and a, ((b,,), for inverse direction. Ö(-) further suppresses the polylogarithmic factors in (-)) & denotes approximately less than up to constant factors.
RELATED WORKS
RL with Linear Function Approximation There are a number of ways to parameterize an MDP linearly. The first sample efficient algorithm is introduced by Tiang al. (2017), where low Bellman rank MDPs are considered. Subsequent works include Dann et al. (2018) Sun et al.) (209)) Yang & Wang (2019) develops the first statistically and computationally efficient algorithm for linear MDPs with generative models, while Jin et al. (20205) considers RL settings and proposes the LSVI-UCB algorithm. Concurrently. Zanette al. (2020a) provides Thompson sampling-bas based algorithm. He et al. (002)) Wagenmaker et al. (2021) provide a gap-dependent regret bound and a first-order regret bound for linear MDPs, respectively. Subsequently, the minimax optimal algorithm is proposed in Hu et al. (2022). More works on RL with linear function approximation include /Zanette et al. (2020b) for low inherent bellman error case, Wann et al.] (2020c) for linear Q function case, and Wang et al. (2020b) for bounded Eluder dimension case. Another popular linearly parameterized
MDP is the linear mixture MDP, studied in Modi et al. (2020); Yang & Wang (2020): Jia et al.
2020 Ayoub et al. (2020): Cai et al. 2020); Zhou et al. (2021).
Reward-Free Exploration in Tabular MDPs Reward-free exploration is studied in Jin et al.
2020a): Kaufmann et al. 22021); Ménard et al.
(201)): [Zhang et al. (2020). [Jin et al. (2020a)
achieves an O A/c²) sample complexity in the tabular setting. Subsequently, the RF- UCRL.
algorithm in Kaufmann et al.) (2021) improves this result by an H factor. MMnard et al. (202T)
modifies the Upper Confidence Bound (UCB)-bonus of UCRL and achieves sample complexity of
Ō 52 A/e²), matching the minimax lower bound provided in Jin al. (2020a) up logarithmic
factors. Concurrently, the SSTP algorithm Zhang et al. (2020) also achieves minimax optimality in the hime-homoeeneous setting. Besides, Wu et al. (2022) proposes the first gap dependent bound.
2

---

Published as a conference paper at ICLR 2023
RFE with Linear Function Approximation There are recent works Wang al. (2020a); Zanette et al. (020cc;; Zhang et al. (202I); Chen et al. (2021); Huang et al. (2022); ; Wagenmaker et al.
focusing on RFE in RL with linear function approximation. [Chen et al. (2021) gives sample complexity bound of Ö 0 /E²) which is sharpest result on II, while Wagenmaker al. (2022)
2022
gives a sample complexity bound of d(H)d which achieves optimal dependency on Our technical framework, i.c., aggressive variance- aware exploration mechanism, is very different from that in Wagenmaker et al. 2022), and also achieves an optimal dependency on and a better dependency H. The best known lower bound is (mmx Hdd d //²2) by combining results obtained in [Zhag et al. (2221) and Wagenmaker et al. (2022). ) Another line of works (Zhang et al. (022); Chen et al. (2021) focus on RFE in linear mixture MDPs. where the minimax optimal sample complexity is obtained in Chen et al. (2021) when d > H but the algorithm is not computationally efficient. A detailed comparison of some most related works is shown Table Moreover, low- rank MDPs, which subsume linear MDPs, are considered in Modi et al. (2021): Chen et al. (2022). In addition, more related work focuses on block MDPs, where the representation & is unknown, Du et al. 2019); Misra et al. (2020); /Zhang et al. (2022).
Table 1: Comparison of reward-free exploration in episodic RL with linear function approximation.
Setting
Algorithm
Computation-Effice
Sample Complexity
Linear
UCRL-RFE+
Zhang et al.
2021
No
Ö(H² d)/e²)
Mixture
Chen et al.
Chen et al. 202
No
O d)/e)
MDP
Lower bound
Chen et 2021
((HP/22)
Wang et al.
Wang et al. (020a)
Yes
0(H9/8/2
FRANCIS
Zanette al.
2020c
Yes
0(H'0/2)
Linear MDP
Chen et
Chen et al. (2021)
Yes
Ö(H-d//)
RFLIN Wagenmaker et al.
2022)
Yes
0(H2(12)
LSVI-RFE (Alg.
Yes
Õ(H4812)
Lower bound (Th.
((HP/2)
PRELIMINARIES
We consider an episodic space, A is the action space, H E Z is the episode length, IP,, :Sx A(S) and rh S x A [0. 1] are dependenn transition probability and deterministic reward function. We assume that S is a measurable space with possibly infinite number of elements and A is a finite set.
MDP M (S, (PPr) (ra3a). where S the state
For time-inhomogeneous MDP, the policy is time-dependent, which denoted as π { TH) where (s) is the action that agent takes at state at the h-th step. We define the state-action function (i.c., Q-function) and value function as
"
07 (8,0;T) = E
Σ
Th (sw, an) 8h = 0, = a,
H
V/ (s:T) = IE
The (sw,aN)
3h = 8, n
(2)
respectively for a specific set of the reward function R. we further denote Py, V,, a; = E,--p,(-Is.a)) V (s';r) and value function variance W (2, a; (P. a; r)1? where 22 stands for the function whose value at is (s:r). The Bellman equation associated with a policy æ for reward function r is
(r For any function V(rr)
Q a;) = (x(s, a) + Pr (P arr), (s;)) = Q7 (s, (s)))))
(3)
for any (s E x and h E [M]. Since the action space and the episode length are both finite, there always exists optimal policy n* for the reward function r (H such that the associated optimal state-action function and value function are (2 a; = sup, (T as));))
For time-inhomogennus case, the bound of UCRL-RFE Zhaan et al. 2021 degraded by H factor.
3

---

Published as a conference paper at ICLR 2023
and rs; = sup, (s; r), respectively. For any (s, E S A and h [H], the Bellman optimality equation for the reward function (ra)i-
(s) - (, a) + Pr V++ i
V (s;)) max (s r)r),
(4)
asA
The structural assumption we make in this paper is a linear structure in both transition and reward, which has been considered in prior works, c.g., Yang & Wang (2019) Jin et al. (2020b) as below: Definition 3.1 (Linear MDP). A MDP M {S, A. H, (IPh h, (raba) is linear MDP with known feature mapping Φ : x A - IR if for any E [H]] there cxist unknown d-dimensional measures μh = (s))) E IR dx [S] over and an unknown vector O E Rd such that for any (s, a) E E A,
(x 88 a) (Ø(s; a), pn(s'),, ra(s, a) (cb(s, On)
We make the following norm assumptions: for any h E [H], (i) sup s.a Φ(s,a)l22 & 1, (ii) (iil) |0 W. where W is constant. These assumptions are mild and are common in the existing literature [Jin et al. (2200b)
| v for any vector [R|S| such that ||oloc
Reward-Free Exploration (RFE) We consider the following RFE model, which has been con- sidered in previous literature Jin al. (2020a); Kaufmann et al. (2021) Ménard al. (021); ZZang et al. (2020). Specifically, there are two phases in the RFE paradigm. (i) Exploration Phase: The agent interacts with the environment for exploration up K episodes without accessing the reward function. (ii) Planning Phase: The agent is given reward function {rm) with the goal of outputting an e-optimal policy ı based on learned information from the exploration phase.
We define the sample complexity to be the number of episodes required in the exploration phase to output e-optimal policy in the planning phase for any possible reward function r, i.e.,
Ez-u [V]* [s E.- [v; e
where μ A(S) denotes the initial state distribution.
ALGORITHM AND MAIN RESULTS
This section presents our LSVI-RFE algorithm for reward-free reinforcement learning linear MDPs. It builds upon the procedure of optimistic learning as |Wang et al. (2020a); Zhang et al. (202I) but with critical novelty of introducing an aggressive variance-aware exploration mecha- nism. The mechanism is inspired by Chen et al. (2021); Hu et al. (2022), and LSVI-RFE further makes critical improvements in variance-aware weights, value function monotonicity, and compu- tational tractability. In addtion, the mechanism is implemented by aggressive exploration bonus 6R, and an aggressive reward function TkA6 in the exploration phase: (i) The aggressive explo- ration bonus guarantees the monotonicity of value functions between two phases and removes the additional dependency of sample complexity on feature dimension d, due to building a uniform con- vergence argument by the covering net in prior works, e.g., Jin et al. (2020b:; Wang al. (2020a) (ii) The reward function is also more aggressive than those in prior works Wang et al. 2020a); Zanette et al. (2020c) by an H factor to avoid extra dependency of sample complexity on episode length H.
exploration, which removes the
4.1 EXPLORATION PHASE
Overall Exploration Sketch The observed state-action pairs are collected in each episode for estimating the parameter [p]))e[H)] by weighted linear regression. Then, the optimistic state-action function Qu,i is constructed (Line 9). and the agent executes the greedy policy n with respect to the optimistic state-action function (Line 11). Two critical steps in the exploration are the variance- aware exploration mechanism and the weighted linear regression, which are illustrated below.
Aggressive Variance-Aware Exploration Mechanism LSVI-RFE designs variance-aware weight θx, and subsequently builds an exploration bonus by. and a reward function т to en- respectively. Our exploration mechanism courage the exploration in Lines 7 and 8 of Algorithm []
is variance-awee aware and aggressive with the following critical differences to prior works:
(i) Variance-awarr weights: G (Line 24 of Algorithm contains two terms: Wk. and WR.h- The motivation to introduce σR, remains that we utilize a Bernstein-type nelf-normalized bound (Lemma C in Appendix C.T) build the confidence set, and the Bernstein bound contains
4

---

(-) - arg max (.) Published as a conference paper at ICLR 2023
variance term (o²) and elliptical potential term (R). Thus, LSVI-RFE estimates the variance upper bound of the value function VA, by WR,A k in Line 16, and dynamically adjusts Wk,h in Lines 19-23 keep | 1 (s af) _,, /ōr,n small. This fine-grained control of wa.h critical for removing d, which is inspired by Hu et al. (2022 for regret minimization in linear
the extra dependency MDPs, and is detailed in step 2 Section [ However, k in Hu et al. (2022) contains three terms and the difference is that abandon the variance upper estimator term concerning the real value function. Due to the agnosticism of the reward function in the exploration phase, a uniform upper bound of the value function (concerning the actual reward function) variance is infeasible.
Algorithm Least-Squares Value Iteration RFE (LSVI-RFE); Exploration Phase
Require: Regularization parameter X, exploration radius 3
1: for step h H, ....? 1 do
2: A1.h 11,h h AI; fi, - O; Vo,n(-) -:;
3: end for
4: (., -0
5: for episode k 1, ... K do
6: for step h = H. H...., // Value iteration do
7:
(t. :) 2.35 ( - // Exploration driven bonus
8:
(x)) b,,a(,,))/2 // Exploration driven reward function
9:
(x)(..-)) (.-) ( V k,,+,, -)> + bk,((t,)) // Optimistic Q function
10:
V-, min max.E. (,,,(,
11:
12:
end for
13:
Receive the initial state sf
for step h 1, ..., Hl do af - ()))), , and observe shit ~ ( at)
15:
WK, min(H H. ((Ax, VENtI, ((5), )² 351 a.))) HHV/2KVV), HP)
17:
TR. /max H. (d. (d/H))We..
ARtI,h Aos x ((5 a (s T
19:
if o (stt att ا > 1/d then
20:
Wk.h Hdd
21:
else
22:
Wk.A - VHI
23:
end if
24:
OE + max( Tk.
25:
A ÅEA 0 pb ( T
2-2
26:
P - A Σx_ o 1
2 (s)) // Solution to the weighted regression
27:
end for
28:
end for
29:
Return (ÁK+LI, PK +1,4)
(ii) Aggressive exploration bonus dy.n. It is aggressive by a factor of 2 enlargement to ensure the monotonieity of the estimated value function between the exploration phase and planning phase, i.c., (-:r) + (.) > Vx((-) (Lemma A.15 Appendix), which is also necessary for removing the extra dependency of the sample complexity d. This monotonicity is similar to "over-optinism" Hu et al. 2022), but our monotonicity built between the exploration phase and the planning phase, which is different from that in Hu al. (2022). which builds monotonicity in each episode. The reason remains that only the planning phase bonus determines the sharpness the sample complexity as detailed in Section such that monotonicity is only required between the exploration phase and the planning phase, instead of each episode in the exploration phase.
(iii) Aggressive reward function Tk.b: It is more aggressive by factor of H enlargement than existing works for RFE linear MDPs, e.g., Wang et al. (2020a). which sets the reward function as min(br,n(, -)/ H, 1) so that it belongs to [0, IJ. Tk. takes the same order the exploration bonus,
5

---

Published as a conference paper at ICLR 2023
Le., without the 1/H factor. Using factor of H enlargement to achieve faster learning rates was firstly proposed in Chen et al. (202I) for linear mixture MDPs, achieving minimax optimal sample complexity, yet in computattionally-inffiiiii works for our variance-aware exploration mechanism a computationalll--ffiiieenn way, and saves an H factor in the sample complexity.
manner. We prove that the H enlargement also
Weighted Linear Regression To enable aggressive variance-aware exploration, we employ weighted linear regression to assemble variance-aware weights in linear regression. Note that the weighted ridge regression estimator has been built for regret minimization algorithms for RL with linear function approximations, e.g., Zhou et al. 2021); Hu et al. (2022). Denote 8(s) E TRIST as a one-hot vector that is zero everywhere except the entry corresponding to state one, and define <x := (A s aa)) - (1)++1) Considering [|E sx "..aa]= = 0, (s is an unbiased estimate of
P- 6% (f)) 14 Φb hh: ). Thus, μa can be learned via regression from d( at)) to 8(
and the sequence (or hie [e[]]] serves as the weight sequence. The estimated parameter fa,h in Line 26 of Algorithm T the solution to the following weighted linear regression:
min min
que R 4818
[uTT a -(( 5,h
(5)
with solution in Line 26 and the estimated transition probability PA.n sh att
m blsh
4.2 PLANNING PHASE
Overall Planning Sketch During the planning phase, the e-optimal policy и is the greedy policy concerning the optimistic value iteration with respect to the estimated transition matrix from the exploration phase, i.e. parameters (Āk-1nhhe(m)) We introduce a UCB bonus term b,((,)), which still takes variance-aware mechanism by utilizing the covariance matrix Å AK+ 1, to ensure opti- mism of (.). particular, Step in Section 3 reveals that the sub-optimality gap upper bounded by the summation of UCB bonus term (.. ) in the planning phase, which is small on average and ensures the near optimality of the returned greedy policy m
Algorithm 2 Least-Squares Value Iteration RRFE (LSVI-RFE); Planning Phase
Require: Planning radius parameter (AK+IA, RK+1n reward function r = (Fu]ne(m)
1: V++1(.) + 0
2: for step h H.... 1 Value iteration
3: bu(.,)) = m ( K K+
H)}
4: Qu(-))) rn(:))) + (FK+1A h+1 s(,,))) bn())) // Optimistic Q function
5: V.(-) - min { maxaa Qu(;a), H}
6: (.(()) arg max Qn(:aa)
7: end for
8: Return [TA)RE[H]
Remark 4.1. In our analysis, introduce auxiliary value functions (Definition A.5 in Appendix). Although it is inspired by Chen et al. (2021), we make critical changes, i.e., building optimism in our variance-aware exploration mechanism with a computationallly-ffiicii functions, we can further decouple UCB bonuses bū,6 and bn of exploration and planning phases, i.e., by.h and by can take different orders, as revealed in Eq. (9) and Eq. (10). In particular, Step 4 in Section 5 further shows that only the planning phase bonus by, determines the sharpness of the sample complexity. This is very different from prior works Wang et al.) (2020a); Zhang et al. (202T). which take the same order of bonuses in two phases. Our heterogenous UCB bonuses in two phases and accompanying auxiliary value functions together are able to reduce an 2 factor and a d factor in the sample complexity, compared to prior work in Wang et al. (2020a).
manner. By auxiliary value
4.3
MAIN RESULTS
The sample complexity of the proposed LSVI-RFE algorithm given below in Theorem 4.2 with proof sketch in Section The detailed proof is given in Appendix

---

Published as a conference paper at ICLR 2023
After collecting δ (2) trajectories during exploration phase, with probability 1 LSVI-RFE outputs an c-optimal policy for arbitrary reward function satisfying Definition 3.7 during the planning phase.
Theorem 4.2 (Upper bound), Set 3
H(d/H) and B = Ö(VHd) B
Remark 4.3. Theorem shows that LSVI--FE achieves the state-of-the-are sample complexity for RFE in linear MDPs. Compared to the RFE algorithms in Wang et al. (2020a):: Zanette et al. (2200)); Wagenmaker et al. (2022) for linear MDPs, our sample complexity is sharper in H, which comes from the more aggressive reward function. Moreover, the optimal dependency on d is achieved by our variance- aware UCB bonus such that the extra overhead due to building the uniform convergence argument in Wang al. (2020a); Chen et al. (2021) is removed. Compared to Wagenmaker et al. (2022), which also achieves optimal dependency on d, our technical framework, i.e., an aggressive variance-aware exploration mechanism, is very different, and gives better dependency on H.
Remark 4.4 (Computational Tractability). LSVI-RFE is computationally efficient algorithm, i.e., it has polynomial space and computation complexities. Besides, it suffices to only analyze the space and computation complexity of Algorithm | in the exploration phase, since Algorithm 2 in the planning phase is equivalent to a single-episode run of Algorithm [ The space and computation complexities (detailed in Appendix Di of Algorithm | are (dd H K)) and (dd A HK?), respectively, where K is the number of episodes that Algorithm has run. By Theorem 4.2 K can
take the order of Ô (H+ d2/c2) to output c-optimal policy with high probability.
5 MECHANISM
In this section, we overview the key techniques and ideas used in the analysis of reward-free ex- ploration and the proof of Theorem [.2] As preliminary steps in optimistic learning, we construct the confidence sets ČE and C₁2² for the exploration phase and planning phase respectively in Steps and 2. Subsequently, we bound the exploration error, i.e., summation of the exploration bonus, during the exploration phase based on the confidence set CF in Step 3. Finally, we bound the sub-optimality gap of the recovered policy in the planning phase with confidence set č% and the monotonicity of the exploration bonus in Step 4. The full proof is in Appendix A
Step 1: Build Confidence Set C in the Exploration Phase LSVI-RFE estimates the parameter
{pn be( of the transition probability matrix in the exploration phase. The confidence set ČE is built with Hoeffding-type self-normalized bound, i.e., Lemma C. in Appendix [ and a standard covering net argument, e.g., Lemma B.3. in Jin et al. (020b)), such that we have for any & E [K], [H]. with high probability,
My E OF = je: (H (a),,)) Vi Re,
FF
(6)
This is detailed in Lemma C.3 with 3 ((VTH) Consequently, we have (PPA,A PP,) VALn-
3F (s I12 by the Cauchy-Schwaer inequality. Under confidence set ŌF (z, is upper confidence estimator of the optimal value function with exploration- driven reward, i.e., Vi (::r)) where 2 (rk,A)ee[M) which is detailed in Lemma A.7
êP Step 2: Build the Confidence Set Cj in the Planning Phase for any h E [H] in the planning phase,
We prove that, with high probability,
14 E Ch :e 1((- (K++IN) Vn+al I
<
ARm.
where the bonus radius 3P Ö(vdH) is sharper than B Ö(dv H) in the exploration phase. Specifically, we build the confidence set ER, by the intersection of two confidence sets E (P(1) and Cf (P(2), similar that in Azar al. 2017) for tabular MDPs, where (P(1)
p1: (1 pk++1,)) V Vitllazna & &BPON)
(P(2)
:e: (1 (1)+1.))) (Vi+1- Viet.) ARAE
where (+) refers to (3rr) A couple of remarks are in place here. (i) In particular, since V (+) is a fixed function, where the real reward function given in planning phase, we can
The exact forms of 3 3P(1) 33((2) are given in Eq. 20
30 and
32
respectively in Appendix A

---

Published as a conference paper at ICLR 2023
(P(1) with radius 3P()) Hd) by Hoeffding-type self-normalized bound build confidence set ct directly without a uniform convergence argument, as detailed in Lemma A. (ii) When building
the confidence set C CP(2) the Bernstein-type self-normalized bound (Lemma C.2 in Appendix C.1
is applied, where the variance term (a²) and elliptical potential term (R) need to be controlled. In fact, we build the monotonicity of the estimated value function between the exploration phase and planning phase in Lemma A.15 i.e. V (++))+ (+) > (-) such that the variance term (a²) can keep the elliptical potential term (R) small, which is detailed in Lemma A.9 This gives 3 = Hd) detailed in Lemma A.17 Consequently, the overhead due to building a uniform convergence argument by covering net is removed and BP pP(1) + TP(2) O(vHd).
be bounded by the variance of (-) Moreover, by dynamically adjusting Wk,h,
Step 3: Bound the Exploration Error The exploration error refers the summation of the con- structed optimistic value function in the exploration phase, i.e., Vr,1, which upper bounded by the summation of the bonus term under the confidence sets ČØ for any h [H]. It is named as the exploration error since the summation of the bonus term upper bounds the estimation error (PKAA- PA) In particular, the exploration error is upper bounded in Lemma A.20 by
K
H
K
H
(st) 4
min
|
A 1 Ö(VPHH (8)
12
where the second inequality holds since I2 can be bounded as Õ(v Hd) by the elliptical potential lemma (Lemma C.6 and J (H(THT) since the enlargement operation in Line 20 of Algorithm rarely happens due to the conservatism of elliptical potentials according to Lemma C.7 and the summation of WA. is in the order of /T by Lemma A.
Step 4: Bound the Sub-optimality Gap The sub-optimality gap refers to the expected gap be- tween the optimal value function (;+r) and the value function VT (srr) associated with the
recovered policy æ in the planning phase. Notice that (|)( & ( since
As,h 3 AK+IA h for any E [K]. We thus have
(-.) = 1- +)x > vdba(s--) v (d3PIp0( )1) Ri...
(9)
where (..) is the exploration bonus in the planning phase. Then, we can apply standard analysis as in Wang et al. (2020a) to bound E [V] (s1;r) - VT (s1; by
E,, ERycH u [V (s1:)) - VT (s1:)) =
E EH (11) VP (s1:r) EsioH
(10)
K Σ
< Basop [[]:))) < EeInH [T((I:TH)) (aaiir)]/VVee
(ii(sr) /KKV
where the first inequality holds due to optimism under the confidence sets CP for any h [H] (Lemma A.15). the second inequality is the application of regret composition and V/ is an auxiliary value function defined in Appendix, the third inequality holds by Eq. (9). and the last inequality holds due the optimism under the confidence sets ČF for any h [H] (Lemma A.7). Indeed, Eq. (10) establishes the connection between the exploration phase and planning phase. Thus, if is an c-optimal policy, obtain K 2 Ö H /c2) by combining Eq. (8) and Eq. (10).
LOWER BOUND AND SUB-OPTIMALITY GAP
We provide a sample complexity lower bound for reward-free RL under the linear MDP setting in Theorem 6. We show that there exists an instance of linear MDP, such that any reward-free RL algorithm requires H H/2e²) episodes of interaction during the exploration phase to find a near-optimal policy during the planning phase.
Theorem 6.1 (Lower Bound). Suppose H > 4, 2,1/32K < 8 1/H. Then, there exists a linear MDP instance M = (S,A, H, (Px), (ra)), such that any algorithm ALG that learns an e-optimal policy with probability at least 1-6 needs to collect least K Cdl 11 3/2 episodes dur- ing the exploration phase, where C is an absolute constant, and 8 has no dependence on e, HI d, K.
8

---

Published as a conference paper at ICLR 2023
Proof Sketch. Notice that if the reward function is given in the exploration phase, the RFE setting degrades to Probably Approximately Correct (PAC) RL setting Dann et al. (001)). Thus, a lower bound for PAC RL also serves as lower bound for RFE since algorithm for RFE also works for PAC RL by neglecting the reward function in the exploration phase. The proof of Theorem 6.1 is inspired by the lower bound of RFE in linear mixture MDPs in Chen et al. (202T). First, construct a hard-to-learn MDP M such that any algorithm which runs A episodes will obtain the regret at least (
as shown in Zhou et al. (201)). Then, for any algorithm ALG running K episodes to learn an e-optimal policy π. T(K) with probability least that under the instance M. K >
6. it suffices to prove Cd 12/H//2 /e2. We prove this by constructing a new algorithm ALg₂ which runs ACG1 in the first K episodes and executes the generated policy π (()) in the rest (c-1) episodes, where c >> is a positive constant. The regret under .M in the last (c- 1) episodes by & Ke, where is the initial state distribution, the first inequality holds due to the hardness of the constructed MDP, and the second inequality holds due to π (TK) is e-optimal policy. Thus, obtain K >
executing x (K) satisfies Q HK) & > =k=K+1 Ex [V] (z
For detailed proof, please refer to Appendix [
Remark 6.2. Theorem 1.1 presents an improved sample complexity lower bound for RFE in linear MDPs than the results of Q2 d/2) in Zhang et al. (2021) and (2d2/22) in Wagenmaker et al. 2022). The lower bound and Theorem 4.2 together show that the sample complexity of LSVI-RFE,
i... O(H*d/ee), matches the lower bound S2 d2 (22) except for an H and logarithmic factors.
To our best knowledge, the upper bound in Theorem 4.2 and lower bound in Theorem 6.1 are both
sharper than those in existing works Wang et al. (2020a)
Lneette et al. (2020c): /Zhang et al. (2021)
Chen et al. (202I).
6.1 TOWARDS MINIMAX OPTIMALITY
The sample complexity of LSVI-RFE is Ö(H+P))))) which matches the lower bound up to an H and logarithmic factors. The factor H between the upper and lower bounds is potentially due to utilizing a Hoeffdingg-tee type bonus instead of a Bermstein-type one for building the confidence set (Pa), Intuitively, a Bernstein-type bonus based on the variance of the value function, combined with the Law of Total Variance (LTV) Lattimore & Hutter 2012)). can effectively reduce a V H factor in the statistical complexity of RL algorithms. This phenomenon has been observed in existing works Zhou et al. 2; Hu et al. (202)) for regret minimization in linear MDPs. However, to utilize the Bernstein-type inequality in building (P(1), we estimate the variance of the optimal value function V (.)) with real reward function. Unfortunately, under the RFE, the agent is unaware of the real reward during the exploration phase. which brings obstacles to building the variance estimator. In the Linear mixture setting, Chen et al. (2021); Zhang et al./ (222I) successfully utilize the Bernstein- type self- normalized bound and presents nearly minimax optimal algorithm. However, their works still cannot estimate the variance of the optimal value function. Instead, they build an upper-bound estimator from a candidate set to avoid estimating the variance, which is computationally inefficient.
Degradation to PAC RL Our sample complexity upper and lower bounds in Theorem 4.2 and 6 are also applicable to the PAC RL setting, i.c., the agent is aware of the reward function during the exploration phase, both upper and lower bounds are sharp, yet there is still an H gap. However, a direct adaption of the Bernstein-type bonus will not improve the sample complexity under PAC RL due to policy inconsistency. Specifically, when we apply the total variance lemma (Lemma C.5 in Jin ee al. (2018)), the exploration policy n for episode is inconsistent with the recovered policy x in the planning phase, since x* is the greedy with respect to constructed value function by exploration- driven reward function, instead of the real reward function given in the planning phase. A potential solution may be bounding the distance between two policies by policy distance measures, e.g., KL divergence, which helps tabular RFE to reach minimax optimality in Ménard et al. (202))
7 CONCLUSION
This work studies reward-free reinforcement learning with linear function approximation for episodic MDPs. We propose a novel computation-efficien algorithm LSVI-RFE with O(H*a2/22 sample complexity upper bound for linear MDPs. We also establish a sample complexity lower bound of 2 &f /e),, showing that LSVI-RFE's complexity is optimal up an H and logarith- mic factors. LSVI-RFE introduces a novel variance-ave aware exploration mechanism with weighted linear regression to avoid avgrly-aggeessive exploration in prior works. Our sharp bound relies on the decoupling of UCB bonuses during two phases, a Bernstein-tyyp conservatism of elliptical potentials We leave removing the H gap as future work.
normalzzdl bound and the

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
The assumption we make to the MDP structure can be found in Definition 3.1 The complete proof of main theoretical results, Theorem 4.2 and Theorem 6.1 be found in Appendix [A] and Appendix respectively. We also provide auxiliary lemmas required for our complete proof in Appendix
ACKNOWLEDGEMENTS
The work is supported by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108400 and 2020AAA0108403, the Tsinghua University Initiative Scientific Research Program, and Tsinghua Precision Medicine Foundation 10001020109.
REFERENCES
Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312 11-2312-23333 2222200, 2011.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-tar strgeted regression. In International Conference on Machine Learning, pp- 463 PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference Machine Learning, pp. 1283-1294. PMLR, 2020.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. On the sta-
tistical efficiency of reward-fres exploration in non-linear rl. Advances Neural Information Processing Systems, 2022.
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:2110.03244, 2021.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert Schapire. On oracle-efficient pac rl with rich observations. In Proceedings of the 32nd Interna-
tional Conference on Neural Information Processing Systems, pp. 1429-1439, 2018.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards account- able reinforcement learning. In International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pp. 1665-1674. PMLR, 2019.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 4171-4180. PMLR, 2021.
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojeiech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 33, pp. 019633396000 3803, 2019.
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with lin- 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. 2022.
10

---

Published as a conference paper at ICLR 2023
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model- reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pp. PMLR, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning. pp. 1704-1713, PMLR, 2017.
Yiding Jiang, Shixiang Shane Gu, Kevin P Murphy, and Chelsea Finn. Language abstrac- tion for hicrarchical deep reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? Advances in neural information processing systems, 31, 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. In Conference Learning Theory, pp. 2137-2143. PMLR, 2020b.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pp. 865- 891. PMLR, 2021.
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In International Conference on Algorithmic Learning Theory, pp. pp. 320-334. Springer, 2012.
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 Inter- national Conference on Machine Learning, pp. 7599-7608. PMLR, 2021.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state ab- straction and provably efficient rich-observation reinforcement learning. In International confer- ence on machine learning, pp. 6961-6971. PMLR, 2020.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2020. PMLR, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07035, 2021.
Mirco Mutti, Riccardo De Santi, Emanuele Rossi, Juan Felipe Calderon, Michael Bronstein, and Marcello Restelli. Provably efficient causal model-based reinforcement learning for systematic generalization. arXiv preprint arXiv:2202.06545 2022.
Ashvin Nair, Bob McGrew, Marcin Andrychowicz, Wojeiech Zaremba, and Pieter AbbeeL. Over- coming exploration in reinforcement learning with demonstrations. In 2018 IEEE international conference on roboties and automation (ICRA), pp. 6292-6299 IEEE, 2018
Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom Wiele, Vlad Mnih, Nicolas Heess, and Jost Tobias Springenberg. Learning by playing solving sparse reward tasks from scratch. In International conference on machine learning, pp. 4344 4353. PMLR, 2018
Max Schwarzer, Ankesh Anand, Rishab Goel, R Devon Hjelm, Aaron Courville, and Philip Bach- man. Data-efficient reinforcement learning with self self-predictive representations. arXiv preprint arXiv:2007.059929 2020.
11

---

Published as a conference paper at ICLR 2023
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 2998-2933. PMLR, 2019.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. First- order regret in reinforcement learning with linear function approximation: robust estimation approach. arXiv preprint arXiv:21 2021.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. Reward- free rl is no harder than reward-aware rl in linear markov decision processes. arXiv preprint arXiv:2201. /206, 2022.
Ruosong Wang, Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 33:17816
1778166-7826... 17826. 2020a.
Ruosong Wang. Russ R Salakbutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020b.
Yining Wang, Ruosong Wang. Simon Shaolei Du, and Akshay Krishnamurthy Optimism in rein- forcement learning with generalized linear function approximation. International Conference on Learning Representations, 2020c.
Jingfeng Wu, Vladimir Braverman, and Lin Yang. Gap-dependent unsupervised exploration for reinforcement learning. In International Conference Artificial Intelligence and Statisties, pp- 4109 4131. PMLR, 2022.
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.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning, pp. 10746-107550 PMLR, 2020.
Ruihan Yang, Huazhe Xu, Yi Wu, and Xiaolong Wang. Multi-task reinforcement learning with soft modularization. Advances Neural Information Processing Systems, 33:4767-4777,, 2020.
Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data, Advances in Neural Information Processing Systems, 34, 2021.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Confer- ence on Artificial Intelligence and Statistics, pp. 1954-1964. PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference on Muchine Learning. pp. 10978-10989, PMIR, 2020b.
Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill. Provably ef- ficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 1776-11666 2020c.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-based reinforcement learn- ing with linear function approximation. Advances in Neural Information Processing Systems, 34, 2021.
Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block mdps: A model-free representation learning approach. In International Conference on Machine Learning, pp. 26517-26547. PMLR, 2022.
Zihan Zhang, Simon S Du, and Xiangyang Ji. Nearly minimax optimal reward-free reinforcement
learning. arXiv preprint arXiv:2010.055900 005000 2020.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532- 4576. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2023
Supplementary Materials
Proof of Upper Bound (Theorem 4.2)
14
A.1
Notations and Preliminaries)
14
A.2
High Probability Events in Exploration Phase
15
A.3
High Probability Events in Planning Phase
18
A.4
Upper Bounding the Exploration Error
24
A.5
Proof of Theorem 4.2
29
Proof of Lower Bound (Theorem 6.1
31
Auxiliary lemmas
33
C.1
Concentration Inequality
33
Linear MDP Property
34
Covering Ne
35
Elliptical Potentials
35
D
Computational TrantaaaiilrTraaaalllliil
35
Space Complexity Algorithm
35
D.2
Computational Complexity of Algorithm
36
13

---

Published as a conference paper at ICLR 2023
A PROOF OF UPPER BOUND (THEOREM 4.2)
A.1 NOTATIONS AND PRELIMINARIES
We summarize the key notations used in our analysis in Table
Table Notations
Symbol
Explanation
FE,
d-algebra generated by random states and actions up to stage of episode
V(,
Function class defined in Definition A.4
(+)
Constructed optimistic value function in exploration phase
VA()
Constructed optimistic value function in planning phase Optimal value function in planning phase Abbreviation of Vit rs)
A (s:T)
V. (s)
(s;r)
Truncated optimal value function in planning phase, defined Eq.
3E
(dv H), exploration bonus radius built in Lemma A.6
BP(L)
Ó( Hd), part one of planning bonus radius built in Lemma A.11
(P(2)
Ō Hd), part of planning bonus radius built in Lemma A.12
3P
(v Hd), planning bonus radius built in Lemma A.13
ČE
Confidence set in exploration phase, defined in Eq.
k.h.
EP()
Part one of confidence set planning phase, defined in Eq. (4
(())
Part two of confidence set in planning phase, defined in Eq.
15)
Confidence set in planning phase, defined in Eq. (16
Episodic optimism event in exploration phase, defined in Eq.
12
k.h.
VE
Optimism event in exploration phase, defined in Eq. 13
Optimism event in planning phase, defined in Eq. Defined P (-] $ a (s)
P. s, s)
Estimated transition probability, ((,,
Before the formal proof begins, first start with some necessary definitions of measurable space and filtration required during our proofs.
Measurable Space Note that the stochasticity in the transition probability the MDP is the only source of randomness. Denote P as the gather of the distributions over state-action pair sequence (S x A)N, induced by the interconnection of policy obtained from Algorithm | and the episodic linear MDP M. Denote E as the corresponding expectation operator. Hence, all random variables can be defined over the sample space given by the triplet (S2 JF, F.... PP.. where F is the product -aaleerra generated by the discrete o-algebras underlying and A.
(S A Thus, we work with the probability space
Definition A.1 (Filtration). For any & [K] and any h e [H] let F be the o-algebra generated by the random variables representing the state-action pairs up to and including that appears in stage of episode
Ōk.h. Ōk, A A are FR. -easmuuaareblle P4t1I is -eeasrree, Qu. Vi, nh are Fi-.---memauuabable yet not Fx-1, F -eessurable due to their backwards construc- tion.
Measurability
We provide some necessary definitions of high probability events in Definition A.2 and Defini- tion A.3 for exploration and planning phases, respectively. particular, high probability events for the exploration phase are built in Appendix A.2 and those for the planning phase are built in Appendix A.33
Definition A.2 (High Probability Events Exploration Phase).
14

---

Published as a conference paper at ICLR 2023
Confidence Set in Exploration Phase
Ch, Ch,== :- pe: [ (o Venti /
Aec & $B8]. E(k,h) [H]
(11)
Optimistic Events in Exploration Phase
V R1 [ee GE R. vh < h' & H),
((k,h) E [K] x [H]
(12)
Č E : | E 1, Vi E [K]. 4A & HI)
vh E [H]
(13)
Definition A.3 (High Probability Events in Planning Phase).
Confidence Sets in Planning Phase
(P(1) = p [1u (0++ V Vittllaaann & 3
Vh x| (14)
(P(2) = pi (u --x++11)))) (Vu+1 Viizz)
3322)
th x x| (15)
ARELA
Ch == {w: (:|(um (K+L1)) Vutal I AN-LA $BP].
the x x[H] (16)
Optimistic Event in Planning Phase
1 {PA E C4. vh 1/ H), e
(17)
We also define the optimistic value function class below, which required build a uniform con- vergence argument by the covering net.
Definition A.4 (Optimistic Value Function Class). For any I., B 0, let (T. B) denote class of functions mapping from to R with the following parametric form
V(-) = min { max w maxx" Φ(.,a) a) + BB Φl. () A- Φ( a), H Q)
(18)
where the parameters (w, A) satisfy wll22 < L, 3 E [0, B). the minimum eigenvalue satisfies Amin (A) > X, and sups,a ( a)ll2 1.
Moreover, we also utilize the truncated optimal value function in the planning phase, which is de- fined recursively as below. Compared to the definition of (s; we take minimization over the value function and H in each step in this definition. We can similarly define (s;r), (7, a)
Definition A.S (Truncated Optimal Value Function). We introduce the value function V7 which is recursively defined from step H 1 to step 1:
V (s;rr) 0, Vs S S
(x;,))))) = rn a) + PA V (s, ((x,a)
(19)
V. (s;r) min maxra(s, a) + PA (s, { &
Proof Overview We first build the confidence sets GE, and Cf for both exploration and planning phases, respectively Appendix A.2 and A.3] Subsequently, we bound the exploration error, i.e., summation of the exploration bonus, during the exploration phase based on the built confidence set C in Appendix A.4 Finally, can bound the sub-optimality gap of the recovered policy in the planning phase with confidence set č₁ and the monotonicity of the exploration bonus in Appendix A.5 which also ends the proof of Theorem 4.2
A.2 HIGH PROBABILITY EVENTS EXPLORATION PHASE
In this subsection, we build high probability events in exploration phase, including confidence set G
CR and optimism in Lemma and Lemma A.7 respectively.
15

---

Published as a conference paper at ICLR 2023
A.2.1 CONFIDENCE SET IN EXPLORATION PHASE
Lemma A.6. In Algorithm for any E (0, 1) and fixed h [H], with probability at least 1 - 8/H, have that for any [
GE CEA Mh
{ ;e: ||44-- (2) Vesntt Amg
< =Beg.
where
3 =VHI
dlog 1+
K Hdd
+ log
H dlog
1+
8K3vd H H
+ da dogo log
(1+
32K²B2 By
H222vd
HV
(20)
with Be satisfying 33 & BE.
Proof. (Lemmaa A.6mma..66) Line 10 of Algorithm ! for any (k, h) E x [K]] x [H], we have
Ven()) = min maxx( Ve + 3 p a) a> H
Moreover,
| Vanttll2 A Σ
o in (is of (anni( & (VH)²
H
A k,
and
$
K X
where the first inequality holds since V & H and G. E H for any i E [k]. and the second inequality holds since Amiu(AA (Ak.h) A and sup,,a (Ø(s, a) 1.
Thus, we claim that VA.
(LE, BB) for any (k, [K] x [H]. where function set (.,-) is Le K/X and Bg is constant satisfying 3 & Bg with J given in
defined in Definition A.4
Eq. 20
For fixed function V E (T. BE), let G, Fe = ((), a/,) and
T o.. c V ( V, (s), af)) (ssh+1))
for any i E [b:]. Then, x; is meaaauuraee and n is G.+ -measurabllee and we have E[n: 0.
Since ō., 2 VH, we also have |og/le & 1/vH H and Ins & VH.
By Lemma C.1 for any k [K] and fixed h [H], with probability least 1 8/H,
Σ 3 ( c Tv
<V H dlog(1 + 1)/(Hd))) log( H//)
<V H H dlog(1 + K/(HdX)) (og(H/5)
Denote the e-cover of function class D(LEE BE) as NeLLE, BF). For an arbitrary f(-) (LE, Bg), there exists V(.) Ne. such that If - Vl & Since lej (f- - V) l2 2e
and - 25 el. A-) & &VV we have
Σ
a (s
2
(21)
H
1-1
16

---

Published as a conference paper at ICLR 2023
Thus,
( eh f
R-1
7 ( s/1 cc v/
Σ
ah)ch (f v)
A
(22)
. (sh oh T
2 Vd
Hvλ
< V dlog(1 K/(HdX)) + 1og(H/68 + log We(LE, Bæ) + 2sKvd
HvX
where the first inequality is due triangle inequality, the second one holds by Eq. inequality follows from a union bound over all functions in No (Lr. Br) with
21 and the third
log MV (Lg, Bg)l dllog (1 4Lgg) + d² log(1 /d (Xe²))
(23)
according to Lemma C.5
Moreover, we have
(faR. - 1a) VENNt Aun
1-1
T
Vanr
A-
-Apen + Σ
σ i,
(sh ah) eh
Aenn
k-1 1
(24)
Apa
VEAt41
+
Σ
Φ (sh ah) ch T Vicnt
Aih
in
Ax
Σ
(sh. ah) t) Ve
where the equality is due to Lemma C.4. the first inequality is due to the triangle inequality, and the
second inequality holds since lnr illa H-d and the minimum eigenvalue of ΛR, is no less than A.
Thus, since VE,tH D. we have that with probability least 1 5/H, any k [K] and fixed h E [H]:
(PAN (n) Ve.nttal |
<VAHVd+
Eon o (ssh ef. VELNAI
8-1
K 1+ Hdd
SKLEVd
(1+
32
<V H, dlog
llo
+ dlog
1+
HVA
(olog
H2X
+ H +
3E
where the last inequality follows by Eq. 22 and setting E = HVT/(2KV0)
A.2.2 OPTIMISM IN EXPLORATION PHASE
Lemma A.7 (Optimism Exploration Phase), In Algorithm 7 for any k [K] and any [H],
under To E k,k we have
(8;Tk) & PeL(s), S.
17

---

Published as a conference paper at ICLR 2023
Proof. (Lemma A.7 We first prove the optimism for some fixed episode & [K] by induction.
Initially, the statement holds for h
+ 1 since V(.H+1(+) V (37k)) 0 by definition.
Assume the statement holds for h + 1, which means VE,A+1(1) 3= Vi (:Tk)) under & k1++1 Recall the definitions of (x))(;;)) and 2% (
Qu.((s-)) =..,((s))) + (Pen VRA+I, o(:,))( + 11b( (1b ( min - (r P (441()5)))) H}
(25)
(26)
We have for any (s.0) E Sx A that
as)(s (x,
*)),((,,0) + (i V Vh,++ ((s, + 3d 16(s,,)) - -Iran(s,a) PP.
- Ve,b+1, Φ(8, a)) (m V V a)) + (816(3,00));;; x))
Pr.K - Pn V (
IPEEN (1) Ven++1
1 (0( + (
Anga
(I Pr (1.
PA P Pr, 1
0.
Here the first inequality holds by Eq. (26). the second inequality follows from Cauchy-Schwarz in- equality, the third inequality holds by the assumption that 44 E ČF k,h under V k the last inequality holds by the induction assumption that V=)++1-)) 3 V* (+rr)) under D *k,4+1 and Pn, a valid dis- tribution. Therefore, (-) min A Qu,n(: a), H} > max.e (x(aaar)))) Vg((r))
The lemma follows by applying the above argument to any k [K].
A.3 HIGH PROBABILITY EVENTS IN PLANNING PHASE
In this subsection, we built high probability events in planning phase, including confidence set C% and optimism Lemma A. and Lemma A.14 respectively. In particular, confidence set Ct in Lemma A.13 is built based on confidence set CP()) and 2,,02) in Lemma A.11 and Lemma A. respectively. Apart from the optimism in Lemma 14 we also build over-optimism between the exploration phase and planning phase in Lemma A.15 In addition, we denote V/+(()) (-rr)
for convenience, where r = he(H] is the real reward function given in the planning phase.
A.3.1 CONFIDENCE SET IN PLANNING PHASE
First, we present a lemma regarding the difference between AE, and At, Lemma A.8. In Algorithm for any [K 1] and any h E [H], have d3 Aen Ā
Proof. (Lemma A.8 Since ōz. & Vd by definition, we have
A ÄRA - af ((s)) 0
is semi-positive definite matrix.
Lemma A.9. In Algorithm I for any i E [K] and any h [H]. we have
/ min 1 ((s). af 2 1) H
18

---

Published as a conference paper at ICLR 2023
Proof. We discuss two cases that are considered in Algorithm 1
1. If 1 1
of x
& 1 as then Wich v H, such that Gic Ōihh- Thus we have
(sn att
- P ai)l 7n & vd
c o s/ ai)
$
873h
This leads to T.. min { 1 (sh ai a 1
vHa 0 VH.
2. If Th ((5 a A > zo then Wke = Hd.. Then we have
न.h min { oi a A +. 1 &ōih with 1
VHd
Lemma A.10. For any i e [K]. h E [H - 1]. fixed function V S - [0, HJ. and S
HVT/(2K Vd) d)), we have
[V~(V- (s d 1 Vi+t1- V ViN+1 Vi+1 + 5c [ Wa,e: (27)
where Wa, is defined Algorithm]] !
W.n min { H Prann ah)) + 3rhh | abhl R. + 5) ,s), H23]
(28)
We define V = V Viu and E = {-s & V & Vinti + +c} for brevity. Thus we can
Proof.
write
[v(V - vitta)((s/ ab)) - I Vi h+11 -5 V & V.N41 + Vitt2 + c] 1 (W
=IVn ob) 1 { [
- -(Pa(()) a (Px 17.7(0 (s). (1)))) {
*H (P, )) 1 1 w
where the inequality holds by |V| H. Moreover, further condition on event & o T the left term of Eq. 27 will be zero. This leads to
H. (PA V (s ) 1 fE V.A.)
&H. (Pr Pu ah) + () 1 {E w.
V. 1(s) ahh) +
(un - (....) V.n+i olhh + +c) 11 fēn W.i]
+ (mn - ( V A 10sh and R + +6) 1 ff8 w
<H.
<H (1.. D( ab.) + 3 |0(5h a 1 + +5) 1 f8c w.A)
where the first inequality holds since consider event غ, the second inequality holds by Cauchy- Schwarz incquality, and the last inequality holds under event E Moreover, the left term of Eq. 27
is smaller than H², since VV - Vi-il < H. Then we have Eq. 27 holds.
Lemma A.1I. In Algorithm 2 for any & [K] and h E [H]. with probability at least 1- 8/
μ4 E (P(1)) [1: ((p (K++1.)) ViL A & 3P())
(29)
where
BP()) VHH dd doog(1 + Kj(Hd2)) log (H/())) Ad.
(30)
19

---

Published as a conference paper at ICLR 2023
Proof. (Lemma A.11 A.11 For i [K], let 9; Fr, x; = (5% ah)) and
= 1 Vx+ = 67,h [un 1+ ((5) a/))> - Vit (sh+1)].
Since (-) is fixed function, it is clear that are ---measurable and 1/: is 91+1- In addition, we have [ [77 [ = O. Since og,, 2 v H. we see that 17s < V and || & 1/v/H. H.
Then, by Lemma C.1 with probability at least 8/ H. for all lo [K] and fixed h [H]
G 2 (sh (h) en Vit+1
<V H dlog(1 + (A: 1)/(Hd))) + (o/(1/))
AZ
&VH/dlogh + K/(HdX)) + log(1/0)
Using similar argument as in Eq. (24). we have
(ĀK+LA (b)) Vittallna & HV
Ad
Σ a Φ (5) ab) ef Vh+tz
A
Therefore, with probability least 1 8/H, for any k [K] and fixed h [H]]
[(K=I1 14h) Vi WHVddoo(1 (/(Hd))) + log(H/0) HV = BP(1)
Lemma A.12. In Algorithm
2 for any & [K] and fixed h E [H]. under w nn w. Wha with
probability least 1- 8//H:
Uh ch GP(2)
= { pe: (m (u++LN)) (Vit1 - Vitts) AKTLA
<3P10)) I &
(31)
where
3P(2) =81
H log
K
1
d
Hdd
[KK2H
8K 8KvLLp)
d3 de log (1+ 32d3/2
log
doog
1+
HVA
H²X2
4K
(1+
8KvdLp)
+ + log 11 32d K2BB.
+ 4
log(
+ dlog
1+
d3
8
HV
22
H Hv A
(32)
with Lp W + K/A and an arbitrary Bp > BP.
Proof. (Lemmal A.12 In Line 6 of Algorithm 2 for any e [H]. we have
Vx(ss) = min
(ra(s,a) + (D Ph ((,,a)) + an(s,a)).
max aeA
(0p + fu4+1 P + ||ss, =
min
max aeA
Moreover, we have
K
0n + PK+1I M = 0 + A
A
K+1h
σ i
(ss
at.) 1h (
2
H
K Σ (
< W +
A
(VH)²
K+1h
1-1
< W + K/X
20

---

Published as a conference paper at ICLR 2023
where the first inequality holds by the triangle inequality with |10/1l2 & W. Vi+1(1) < H, and
Gih b vH for any i [K], and the second inequality holds since Amin (Axn((A+11,))) > A and sup,,a ( a2 $ 1. This implies that V.= (L,, Bp) for any E [ff] with Lp = W + K/A
and an arbitrary Bp > 3P, where function set (-:--) is defined in Definition A.4
For fixed h E [H], fixed V(.) E (LL, Br) and constant Ç HvV/(2K dd), let 9 Fenh J; = - ((hh a%). and
T/e i. Eh V(+z) 1 V h-1 - & Vi + V c) 1 (W
for any i E [k]. Note that (-) is a fixed function, (),++()) and V. are 9--meauurable. Thus, 2; is m--mesuurbll and 17, 9.+1 -measurable.
Also, we have [[n[ 0. By Lemma A.9 we have 0 min ,, ((s af)1
A 1:2 & VHB
Since le), (V V (++1) ) H. we have (7% min A 131 & VII /d..
Furthermore, since o > (d/H)We,,. it holds that
[ - [Va(V V 1s at)) 1 ([VVii 1141-555 - -
Vutt V +5] { (
< W., < H/d,
where the first incquality holds by Lemma A.10 By Lemma
C.2
for fixed h E [If], with probability at least 1 6/H,
K
ΣΣ
2 66(( (/, oh)ei T (V - Vi+ti)
i
V - ( & V & Vinti + V/- + cc 1 ( ine
|
1l
Axt.x.
H 1 d
K Hdd
4KKH
H
4K²H
log
1+
log
+ A1 d3 log(
5
Denote the covor of function class DLL,, Bp) as Nc. we have
log | logg(1 + p + d² log(1 2d (²,(((()))
C.5 Here Lp = W + K/A and Bp > 3r. Then for any E [K] and fixed h E [W], with probability at least 1 8/11, for any Nr, conditioned on (i.e. 1 E for any i E [k:), we build our argument under L h++ in the following), we have
according to Lemma
1,
Virti) 1 (1 (V141 h+1 - & V & ViN+4 + Vi+ti + +5]
Σ
2 2
ch (V
h
A
<8
H
log
1+ Hdd )
K
log
[4K2H 8
+ log (NGl)
log///l)
H 4K2H ) + log [Vr1 + +4V ds
log(
d
(33)
For any
f(-)
E (LL, Bp),
there exists
V(-)
E NG.
such
that If
Vl
& C
Since
[ T (s - -V)
2 and
ΣK 3. ce T 1 Vi+i -5 V V + V + +5} AZLLA
& (H
we have K
Σ 0, ci (f- (f-V)-
1
1(v Vi+
- - & V V 1,,41 + Vhu +5}
2CK Vd
HVZ
(34)
21

---

Published as a conference paper at ICLR 2023
Conditioning on V have
Σ o O
oh T (f- ( 1 V h-1 - V
Vin+i h- +5}
Ax11n
K
Σ
t (s) cg T (V vh+1) V - & V V Vhti + 5}
Axtia
+
H (65 ch (S-V) 1 -
Vi++
< V & S V + Vh+1 + c}
$
Σ
T ((sh c (V - vx+1)
V h+1
5 V V.N++ + Vh+ + 5}
AN+1A
VCVV
HVĀ
H
4K2H 5
4K2H
$8
log
1+
log
+ log Well + 4V d3 logg 5
+ log (W3]
d
Hdd
2CVvd
HVX
(35)
Here the first incquality is due to triangle inequality, the second holds by Eq. 34 and the third holds by Eq. 33
We further assume 1it holds. In addition, for any (,+1()),, there exists V'(+) Nr such that Ç. Since ( HVV/(2K we have
Vh+1 v
v' Vn+ h+1 + Vi+1
VeN+++
for any e [K] where the second inequality holds by Lemma A.15 under Tp other hand, V - Vh+1 - V', where the first inequality holds by Lemma A.14 under
p On the
A+1
/r - Thus, Vi - V1 + k+1 + 5} = for any i E [K] under v n 4
Moreover, have that, with probability at least 8/H, under v vr Whtp for any E [K] and fixed h [H]:
(AK+LA- -Mh) (Vi+1 Vittt ARALL
<VXHVd+ Σ Mo ah (Vit1
Vitts)
H
K Hdd
log
1
d
4K2H
8K 8K HVX
1+ 3203/22BB
log
+ dlog
1+
+ dd
8
2²X
И
4K2H
1 8K
1+ 3/ K2 K2DBB
+ 41
log(
+ d dog
+dBlog log
8
HVA
22
+ HV Ad +
3P(2)
22

---

Published as a conference paper at ICLR 2023
Here the first inequality holds similarly as Eq. 24 and the second inequality holds by Eq. (35) and
<= Hv HVA/(2K (2)
Lemma A.13. Set BP = }P(L) + BP(2) Eq equation 16 for any & (0, 1), with probability at least 1 - 35, f o vpP holds, Le., any h E [H] in the planning phase,
pn Ch po: (u: (--px+1N) (K+11)) Va+1
AKTLA $ 3P
Proof. (Lemma (.13) We first prove the following claim: Under F fixed h e [H] and any & [K], with probability at least 1 2(H - 1)6/H, v.f holds.
We prove this claim by induction. Firstly, when h = H the result is trivial. Assume the claim holds for h + 1 & H. Then, for any E [K], under V with probability 1 2(H holds.
1)6/H, H, v 1
Subsequently, for any l E [K], by Lemma A.11 and A.12 bility 1 26 H that
under T o T.P h+11 we have with proba-
sh E Ch E
EP(I)
GP(2)
By taking the union bound, for any [K], under w with probability 1 - 2(H 1) V.P.
holds, which means the claim holds for h. Thus, the claim is proved by induction.
Since f) 1 8 by Lemma A.6 the conclusion obtained by setting and taking union bound.
A.3.2 OPTIMISM IN PLANNING PHASE
Lemma A.14 (Optimism in Planning Phase). In Algorithm 2 for any h E [H], under Vof we have
(s;)) & (s(s,, E
Proof. We prove the optimism by introduction. Notice that the statement holds trivially when l H + 1 since V (:rr Vi++1 (.) 0.
Assume the statement holds for h 1, which means V (i+i(:))) & Vn+1(-) under Wf Since
(a(::)=ra(e + (PK+LA Puti o(.,)) 3P)(0(: Q7(117)= = =m(())) + (2()3)))
have for any (s,a) E SSx x A that
@n(s,a) (s, a))(s,0) + (f Vn ((s, + 80 a)ll - (r)(s, + PA PAVei (ss
( Vn+1, (6 a)) (un ((,,, + 331 A
PA a) Pi V (s,
| 1h)) Vn-
( 33110(
ARat
+ PRPre1(s, a) PA (3
P. 1,.1((s))) -P,Vi
20 0.
where the first inequality due to Cauchy-Schwarz inequality, the second inequality holds by μa Ōh under u the last inequality holds by the induction assumption Vi++(-)) > V (crr) under
P W and PA is valid distribution. Therefore, Vx(()) max Qn(:aa) max (%
V (:r).
23

---

Published as a conference paper at ICLR 2023
Lemma A.15 (Over-optimism Between Two Phases). In Algoirhms 7 and 2 for any and any h [H], under vr F. o M we have
(s;r) (s)) > (s),,, E
Proof. ) We first prove the conclusion by introduction for some & [K].
Notice that the statement holds trivially when H+1 since (;+))))))++++ + +1) = V+++1-)= by definitions. Assume the statement holds for 1, which means Vi (+rr + Pr,+1()) 2
(-+1(-) under 1p h+1 O h+1-
We see that
()(:;r) = rn((s)) + PAViials
Qu.(())) = -(.))))))) + (Pen VAL+I ((.,))) 3 :))l
Qa(,))) = -r((s)) + (itt
htt (o....)(()))))))) o(.,)) 301(0 ) )1
Thus, we have for any (8, SS* x that,
(%(s,a;)) + Qun(s, a) as)
= a))(s,a) + PP (s. r) + Tk, a) + Pr. (xn+(,s))) + 3 1 (((s, a|
(ra(s,a) a) (pK+IA V (cs, a)) 33
[PAVitt(s, + Pn Pn P Pn 3 ((8,)(s 1111(s.0))
+ (PAR V VE,++1, - (nD v(,++,,
a(s W
PA VIT I (8, a) Pn (P -i PPPn+tiss 3,35 (385)((8,0))1; - -p (0),))))) ())
1 ( (PK+IA pb) Vitta (PLA mn) Ventt1 AEM
10 (0, T AK-LA
PAVi + (s))) Pn Pa 333 Aet. - 1 AKtn.
(010(s,a))x -31100s x WiLL PAVIL + PP (P PA Ph > 0,
where the first inequality is due to Cauchy-Schward inequality, the second incquality holds by μy CE o Eh. under & n v/f,, the third inequality holds since AK+LE 2 Art and B > 3r and the last inequality holds by the induction assumption (+r) + Ve,N+1(-) 2 Vn+1(-) under u E
h+1 Whe and Pú, is valid distribution. Therefore,
V (xr) + Vin(() max Qh(,, max Qu.((;a) > max Qn((a)= -Ph() aeA
aeA
aEA
Finally, note that the same argument can be extended to any & [K].
A.4 UPPER BOUNDING THE EXPLORATION ERROR
In this subsection, bound the exploration error in Lemma A.20 Before that, provide simu- lation lemma in linear MDPs in Lemma A.17 Besides, we denote the reward function ( // in Algorithm I at episode k rk. for all à: [K]
24

---

Published as a conference paper at ICLR 2023
Definition A.16 (Trajectory Distribution). For a fixed policy {TT1 T2,... TH), define dī, (sh) as the probability measure over trajectory Th = (8), On 8h+1: ah+1: SH ag) induced by fol- lowing т starting Sp, stage h:
(T))((T))== =
I
P7 (8t, az s6-1, 0c-1,
2mh+1
where PF (St; Or. St-1, az-1) means the probability that the probability of stat-action pair transition
from (St-1, (z-1) (82, 04) in trajectory Th. (8h, th 8h+ 0h-1,""' , aH) started at 8h
stage h by following policy π.
Lemma A.17 (Simulation Lemma). In Algorithm for any & E [K] and any h E [M]. under V k,
we have
H Σ hh=
0 & (5) & E -aa- (st)
min
4
ab H
Proof. (Lemma
A.17 First, recall that
(u = -ra.((;-)) + (ū Vr MK,++ () + 3 3010(= ((((:))) (10(:))5a) 1
=righ((s-)) + PA.n V h (s ah) + BE||0( )1ā
Vk, = min max ( a., aeA
Thus, for any [K] and any E [1]] in Algorithm
we have
(s)) < Qun (sh, ati) (s. a + PA. Vaani (s a 1 aill az
=3 1 a + |Pa. D at) - Pr P at) + Pr V n- (3 a.
H
(a)
Σ
PANM V Pw V ax) +330 | a a
h dd (stt)
E. _dx (st)
(PEE m4x)) Ve, Ml o + 3 (0( ot oto
H
< EE BBg (sh)
438 Σ hn
( axk Ix
where the equality (a) holds since can expand V in recursive way until
(1))) and the expectation taken over trajectory distribution di (sf) over trajectory = (s% ali &t *ht1, " , )
and the last inequality holds since Pa CE for any & l &
H under K Since (x,(())) & H and ( (s) by Lemma A.7 under Tr k. the conclusion is obtained.
Lemma A.18. Fix 5 > O. In Algorithm 1 under F have with probability 1 28.
K
Σ
PA V
(36)
E
Σ
Σ
Σ
12 1) (H² H) 2T (oTg((H))) H/5).
25

---

Published as a conference paper at ICLR 2023
Proof. First, have
K
K
H
Ph PAVE
Σ
( + [P i att
Panti(sttt)
h=1
(37)
K
H
Σ
V H 2Tlo)(H/0),
holds with probability 6, by common Hoeffding inequality, as stated in Lemma
C.3
Notice that
(sh) min (2nn }
min
3.3 Al + (ax, Va ( an))), H
(43 Ml PA PiVaettlsh at), H
x min
min
a Mll V PP att ( H
(38)
where the inequality holds under f.. For fixed h, We can recursively use this method and get
min
1>b a 1
h-mh
+ IPP ( ahr) (
4, 6 minfll(sss ax. b
M=h
>
Ph - ( a
VI.
k- 1 A
K
H
k
"
<
Σ
) A.
11 + H H 2T log( H/8).
(39)
The inequalities above hold with probability 1 - 5 by Cauchy-Schward inequality and Lemma Thus, we have
OK
H
Ph 1
H 2T (8)
(40)
R- h-1
K
K
H
3R
min
0 A 1) (H² H) H) 2T 22 log(H/8)
holds with probability
25.
Lemma A.19. In Algoritim ! under F we have
K H
RR 2HH + 12H log(1 + 2d ((HH) + 2/2 H2
+ +22(H² H) 2T)o S H(1 + (05 log(1 + K/(Hd)).
holds with probability 1 25.
26

---

Published as a conference paper at ICLR 2023
Proof. (Lemma A.19 From Algorithm| 1
we write the definition of ōg₂h here,
de
ŌR = max
Wk.h
Wk.h
H
Thus we can write
K
H
K
d2
K
H
k,h
W
H
To bound utilize the conservatism of ellintical potentials, i.e., Lemma C.7 Initially, for fixed
h E [H] set at as 0x, (( a in Lemma C.7 Then for C = 1/d2, during K episodes, there are at
most 3d log (1 + d/ log(1 (2))) / /log(1 C²) episodes that | ( at) A
1/d for
fixed E [H]. Thus, there are at most 3ddlog (1 + d/(AH log(1 + (²))) log(1 + C9) episodes that there exists N' E [H] such that - 20 k axp) 2
> 1/d5. In particular, w Hd
during these episodes.
In summary, we obtain
3Hd
d AH log(1 1/d5) (41)
H H Hdd
log (1+
1+
log(1 + 1/d5)
k=1æ=1
HT 6 d log(1 + 2d/ /(H)).
where the last inequality holds by log(1 1/x) & 2x for x> 0.
To bound ii, we can write
d
H
WR.
d
Σ min
(prnn Vinti, ah)) + 10(s), ahils, 5.
11
1-1h11
H
<d HKę d
Σ
3 ab (.
hm1
+ a
Σ
Σ
Mh Ve,t4 ol att) + ((Rrn Mn) V (l att
HHC 2d
min (3 (6(5%/ a o H de
PA (
(42)
where < = -HVA/(2K Vd) and the last inequality holds under v.f Moreover, since B
H > H holds for any E [K] and h E [H], we can write
K
H
H Ōan min(l a
2d
min 8 ( a 1a H & 2d 3
(43)
K
3
Σ
Σ
(1)1)>)))))))11) A
k.
A
By Lemma
18
have
K
H
PA V Vr.u+ (sh
1=1
K
Ad H3F
22
Σ
Σ
min (l
.1) d HW/TT 2T 20go (H/))
11
A.t."
(44)
27

---

Published as a conference paper at ICLR 2023
Thus, combine Eq 41 42 43
44 and Lemma C.6
we have
K
H
A
HT
6H d log(1 + 2d 2d /(HH) + 8 H & H) 2T log H/
+ 22+
Σ Σ
T R,h V 22d + K/(HdA),
Since for any 0, > 0,b 0. & a + leads to & 26 + a² we have
K H
22HT + 12H d log( 2 (AH)) + 22
+ 2d² H 2T 8d ( + (85) + (/(Hd).
which finishes the proof.
Lemma A.20. In Algorithm
under Uf, we have with probability at least - 36,
H
V
E Bf ( (04)
min Σ
A [ (o(s%,afiill., af)llaa H
(45)
v M4d3KK
Proof. (Lemma[A.22)
On the one hand, be Lemma 17 we have
E + oi (of)
min
Σ
4 (0
ailll H
(46)
k=
h=1
under f.
On the other hand, we have
F (ss5 a a 12 H
min
4 _ kh.
| 11sh at)
A.t
(47)
3 o min
| ant
where the inequality holds since BRōRA VHd HH > H. To further bound I, we have
.1]
I 1
3
min
1-- (onh)(saa)) A.A. .1)
1=1
1=1A=1
(48)
H
3
Σ
02
22Hdlog1 (/( K/(AHd))
where the first inequality holds due to Cauchy-Schwarz inequality and the second inequality holds due to Lemma C.6 with the fact that @ Φ (sht (sh+ at)|| ||, I/VH.
28

---

Published as a conference paper at ICLR 2023
By setting 1/(Hvd), we obtain 3 Ödd H log(T)) by Lemma A.6
where T KH. By
Lemma A.19
we have with probability 25
<2H 12H log(1 2d ((HH) + 2/ 2d
K
2d + H) lo H/5) + & H(1 + 2 1og(1 + (HdHd))
-(T).
(49)
Substituting Eq.
49 in 48
and combing Eq.
47
we obtain
K
H
min
Σ
4
k
a
k=1
H
<43E
k. 2Hdlog + KX
(50)
k=14=1
-ō (dv -ō(dvi HogHloog//) v /Hdlog T HT)) & Ō ( log"
holds with probability at least 26. Finally, by Hoeffding inequalityLLemma probability at least 1 - 36,
we have with
K
H
(s
&
E f -ap-attaa (st) min
48 (ssh at) 2 H Σ
x0
(v HHd (T/6))
H Hy 22 (og(H/5)
= (VH+**K).
That finishes the proof.
We denote the event that the inequality in Lemma Le2m holds as Φ which holds with probability least 1 36.
A.5 PROOF OF THEOREM 4.2
this subsection, we bound the sub-optimality gap of the recovered policy the planning phase under event & o vf E 4, which also ends the proof of Theorem 4.2
Lemma A.21. For any 0 < 8 < 1, with probability at least
6, we have
K
[1+(8:7))) - V (otiTa)) < HHH2KK logg1//01//0) -Vi
EanD
where T3 = (ra,nheejm.
Proof. (Lemma A.21 Denote A = Ez-g (*:T)) -Vi (sf: Since sf is FR. measurable,
As is -measuuuaalble and E [A Fx-1,n] = 0, i.e. A& is a martingale difference sequence.
Since | < H by 0 & (*;TT)) Hl for all E S, we can apply Azuma-Hoeffühee inequality (Lemma to this martingale difference sequence and obtain
K
A & 2//2Klog(1/00
(51)
with probability at least - 8.
29

---

Published as a conference paper at ICLR 2023
Now denote the event that the conclusion of Lemma A.21 holds E, which is high probability
event.
Lemma A.22. Under f o en L, we have
Egnus V (s: & (
where NeH]) is the UCB bomus defined in Algorithm 2
Proof. (Lemmal A.22
Notice that AK+LN 2 An, 3 =(dvH) H), and BP ÖÖ(HHHH for any & E [K] and any h E [H] We have
30 Al > cv [b((, A
where e > 0 is constant, which further implies rk,n(:s-) 3 evdbn(..-) for LSVI-RFE. Subse- quently, we have
cv dE
(s:
Vi (s
E sn
Eonn [it((s /K
(Ean (i:(s)))) -M(6ir))))))) 11x
(s + Σ
k=1
Σ (sfi:)))
/K H 2H log(1/8)/K
/K + H log(1//8)
where the second inequality holds by Lemma A.21 under E, and third inequality holds by
Lemma A.7 under f and the last inequality holds by Lemma A.20 under Vi 4. Thus
Ex-p (V* b)] & δ (VHAP/K)
Now we are ready to prove the main theorem.
Proof of Theorem 4.2 suffices to prove the conclusion under the event o o vf 3 which holds probability least 1 75 by Lemma A.13 and Lemma and and taking union bound.
Initially, we have
Es, m
[V* (81;T) - VT (s1:r)
< E
- ([
= -E,cH
min (ri(s)) + (fK+11 ((s,,, (())), }
rr1 ((11) PIV. (s1, ((1):)))
= Eai= min { H, (fx Dz,
(s
30

---

Published as a conference paper at ICLR 2023
{ H, (()))) - (HI V2. ((s), (1(s1,
= Ea min
+ (oo
min H, (px+1.1 Axi
10(8), + +s),
P1 (211 π (51)::) P112 (s1):
& Eg Es
min
H, 2b ($1, x (s1)) + P1
(s))
= Eg P(llsaa))(
min H, 2b (81, ((()) + V2((2) - V3r (82;
< En
min
2bn (ss)),
< <d'
min
bn( (sh)),
$ 2F (s1:b))
where the first inequality holds by Lemma A.14 the second inequality holds by Cauchy-Schwarz inequality, the third inequality holds since μhh ÓF under VP the fourth inequality holds by recursively decomposition, and the last inequality holds by definition of (=;b).. In addition, we have
En- VTT Es-n [Vr (o: Ō @Ö(
where the first incquality holds by definition of V (s; and the second inequality holds by Lemma A.22 under & o n Φ
If we ignore logarithmic terms and take K m m(H4P//2) for sufficiently large constant m O, we have
Eej-a LV (BIiT) VT (sir)] δ (VI**e/K) &
Thus, we need K Ö(HAPP/e episodes to output an e-optimal policy when e is small enough.
B PROOF LOWER BOUND (THEOREM 6.1)
In this section, we provide proof for Theorem 6.1 in the manuscript. Notice that if the reward function given in the exploration phase, the RFE setting degrades Probably Approximately Correct (PAC) RL setting Dann et al. (2019). Thus, it suffices to prove a lower bound for PAC RL since an algorithm for RFE also works for PAC RI. by neglecting the reward function in the exploration phase.
Our proof is inspired by the proof of Theorem 3 in Appendix Cfen et al. (021). which provides a lower bound for RFE in linear mixture MDPs. In particular, we connect the lower bound of RFE with regret minimization in linear MDPs.
Firstly, construct hard-to-learn MDP M (S,A, H, (PP)), (rnhn, v in Lemma B.1 such that any algorithm which runs K episodes will obtain the regret least 2 d.H. (HK) as shows in Lemma B.I
Lemma B.1 (Remark 23 in Zhou et al. (221 ). Let d > 1 and suppose d > 4, H. > and
K max {dd- H/2 1)/(HH 1)) Then, there exists an episodic linear MDPM AS H, (Phh, (rx)n, parameterized by { (0r he [m] and satisfy Definition 3.1. such that for any algorithm, the expected regret lower bounded as follows:
E
(*(s)) v=" ((+)) Q(dHvT),
y denotes the initial state distribution.
31

---

Published as a conference paper at ICLR 2023
where T KH and the expectation is taken over the probability distribution generated by the interconnection of the algorithm and the MDP.
Hard MDP Instance M In this MDP, S f01, 22,'" TH+2)), A (- and the linear
parameterized of M are specified as
(a, BaB 00
= Th, h E [H + +1
((s, a)
(0,0T,
8 8 xH+2
((1- 1)/a, - -1 13.00)
= HH+1
Uh (5')
(1/..17//11)
Og
otherwise
0 = (0",1))
where + = 1/H1 A (VVK/(AV2) = VI/(1+ and B = V 1)).
Under this parameterization, we have
1+ (un. a),
s' = =
1 - (e (ph, a)),
s zi+1 Otherwise
0.
and only the transition starting at # generates a reward.
Then, for any algorithm ACG, running Kı episodes to learn e-optimal policy T (K1) with prob- ability at least 1 6, it suffices to prove that under the instance M, K1 3 Cd H3/22
We prove this by constructing then ALG1 outputs a c-optimal policy T(K) with probability at least 1 - 5. Then ACG₂ executes T (K1) in the following (c K) episodes, which means ALGa runs K₂ cKı episodes.
algorithm ALGz- ALGz firstly
AL91 for K₃ episodes,
Note that Lemma B.2 also gives an upper bound for the regret of every single step under M.
Lemma B.2. Suppose 3(d 1)A Then, for all k [K2]. have
E B (+())) (x1) & dH H
4v2V K2
Proof. (Lemma B.2 We prove this lemma by computing (x)), following the standard analysis of this hard-to-learn MDP in Zhou et al. (202I).
By definition of M, we have (d - 1)A = maxocA a) such that
V (x1) E
rn(s,, on) 81 21,00 =n(sw)
+2, :) 1, we have (TT(z) EM h)P(Nt), where Nn. {sn+1 J.H HH 8h = ). We also have
Since only Th (2
P(8h+1 = xH 84 = Th, 81 = x1.)
Σ ([5h+I=THM) 8h The an a)l a sh -h, 81 21)
=1 (Mh, TH
where 07 EaEA P(an a 8h Th, 21)a. Thus
h-1
P(N)) = (++ (mh, mH))
(1
(13g,T5)))
j-1
Subsequently, we get
h-1 (x( Σ (H (H- (aa +
H
aj 1).
(52)
j=1
32

---

Published as a conference paper at ICLR 2023
By definition of VP, we choose the optimal policy at each stage. Since max a) -(d11) we get
H (+(+))= - Σ H ( + () (d 1)4 1)a 1 & H (dA)
(53)
where the inequality holds by 0 1 (d- 1) <<< and A L. Since the inequality holds by all fixed 21, we also have
dH
π
E (1+(a1) - V/" (x1) & Buy [Vi dH
4v2
K2
where the last inequality holds by = 1/H.
On the one hand, by Lemma B.1 we have
Σ E Ea ~v (1(())) Vi (xi) > ddH HK2,
where n² denotes the policy for ALG2 episode k and a constant number. On the other hand, by Lemma
B.2 we have
K1
E Emjav
(1((x)) VI (i (mi)
dH
H K₂
dH
HK1
dH
V HK2.
4
4
c
4v2c
By choosing c max(1/(2V2c),, 23, we know that for ALG2 under M,
E Exi -e (11( VT" (x1) > (c'-
1
d' dH HK2 dH HK₃ = d' dH VcHK, 2
4v2c
2
R= K1+1
Because x² = (K1) in ALGz for K1 + 1 & k & K2 and K₂ -K1 + 1) + = (c - 1) we
have
c'vo Hh H/K1
Ex (f((z)) -on))-vr(((( (i((K)
(54)
1)c-1)
Since AL91 outputs an c-optimal policy x (K1) with probability least 1 ō, we also have
Exyo (i((z)) ((((i)--v7100 (2r))-vr((k)) (s)) < (1 6) 8
dH
H
& (1 (1-0) -e 8 dH H
4/2
K₂
4/2 cKi'
(55)
where the inequality holds by utilizing Lemma B.2 and the second inequality holds by K₂ cK1. Combining Eq. (54) and Eq. (55) gives
8 dH
H
dVLe dH dH H/K, / 2 1)
(1-8)e+
2
K2
By setting d satisfying 0 < < min 2 2ede /lc/// 1)3, we obtains Ki Cd. 12 for some positive constant C, which completes our proof.
C AUXILIARY LEMMAS
C.1 CONCENTRATION INFQUALITY
This subsection gives the encountered concentration inequalities in proof.
33

---

Published as a conference paper at ICLR 2023
Lemma C.1 (Hoeffding inequality for vector-valued martingales, Theorem in Abbasi- Yadkori et al. 2011)). Ler {gt)==1 be a filtration. Mth be a stochastic process so that H, E R is 9: measurabble and nt R is G2+1 meesurrble.
Denote Z AI Σ a fort = 1 and Zu XI. If xil22 & L, and nn satisfies
E 1T G.] 0, 1 < R
for all t 1. Then, for any 0 < 8 < 1, with probability least 8 we have:
vt 0,
RR /logog/ +12//dd)) + log(1/0).
z,
Lemma C.2 (Bernstein inequality for vector-valued martingales, Theorem 7.1 in Hu et al. (2022) o Let (Gr)-1 be a filtration, (xt, mhea be a stochastic process so that at E IR is Ge-measurable and nj. RR is G1+1-menn meeasurbbl.
If a. l2 & L. and T satisfies
E [m | Gel = O,
E
2
Ge
o²?
n min 1, x | } $ R
for all t 2 1. Then, for any 0 < 8 < 1. with probability at least - 8 we have:
Vt 0,
Dilli
Soydlogg (1 + +1+ log (4t35) 4Rlog (4f²/8)
2
where Z, +I+ Ei=1 x for t and Zu
AI.
Lemma C.3 AAzuma-Hoeffddin Inequality). Let {x=}/=1 be a martingale difference sequence with respect filtration (9 such that [xg M almost surely. That is, I, 94+1 -measurable and E [x 9 = a.s. Then for any 0 < 5 1, with probability at least 8,
2 & MM
2n log(1/))
C.2 LINEAR MDP PROPERTY
This subsection gives some indirect results about the estimated parameter PAct the exploration phase.
Lemma C.4. In Algorithm 7 for any k [K + 1] and any h E [H], we have:
Pa, ph
k.
App + Σ 2 (sh, at) ch
(56)
Proof. (Lemma C.4
We start from the closed-form solution of pack
P = A k
o o (sh, ) (sh+1))
A -1
3R (sh. ai) (Pnl: T + ch !)
k.
A k.
o. 3. (sh. of) (p(sh, and un + ci ))
A k.
Σ
. o (sh, o ais pn + Azl Σ 0 2 (sh a ci
34

---

Published as a conference paper at ICLR 2023
R-1
Aii (Aris - 21) un AZ Σ o (sh, a/) c
= Ph - -A + k, Σ
20 (s) a/h ch
Rearranging the terms gives Eq. (56)
C.3 COVERING NET
Lemma C.5 (Lemma D.6. in Jin et al. (200bb). Let Ne be the e-covering of (L, I B) with respect to the distance dist. (V, V sup, V(x) V'(x), where VL, B) is defined in Definition A.4 Then
log Nel < dlog(1 + 4L/E) df log 1 8d B3/ (x=2)
C.4 ELLIPTICAL POTENTIALS
In this subsection, present Lemma C.6 from Abbasi- Yadkori al. (2011), which is important for establishing the ((vT) worst case regret for linear bandits or RL with linear function approxi- mation. Moreover, we also present the conservatism of Elliptical Potentials Lemma from Hu
et al. (022)), which states that Elliptical Potentials are usually small.
Lemma C.6 (Lemma 11 in Abbasi-Yadkori al.
2011 ). Given 0 and sequence (#t) c
Rd with [æell2 & for all E [T]. define Z. AI +
Ei= Tι0; for t > 1 and Zo = AL We have
Σ min 1,, 1allazell 12,2112221 } 2d (1+ TI.2
dA
Lemma C.7 (Conservatism of Elliptical Potentials, Lemma D.8 in Hu et al. (2022)). Given À > 0
and sequence {xt) T C Rd with |æel2 for all t E [T']. define Ze Al > a. for t 3
and Zu = AI. During [T], the number of times [ Dellz," 32 c is at most
3d
L
log 1+
log + 2)
Alog(1 + c2)
where O is constant.
D COMPUTATIONAL TRACTABILITY
In this section, analyze the space and computational complexity of the LSVI-RFE algorithm. No- tice that Algorithm 2 in the planning phase only performs a single run of value iteration to compute the output policy (Th [e] the computational requirement of Algorithm 2 in the planning phase equivalent to a single-episode run of Algorithm Thus, it suffices to only analyze the space and computation complexity of Algorithm D in the exploration phase. Though we consider the linear MDP setting where the size of states [S] might be infinite, Algorithm is computationally--fficii i.e. the space and computational complexities are polynomial in d, H, K and |AA,, and do depend on (S). where K is the number of episodes that Algorithm has run.
D.1 SPACE COMPLEXITY OF ALGORITHM
Though we give the explicit form of Pa.. E Rdx(s] in Algorithm we do not need to store
directly. In fact, we only need to store fa Vk, Rd since only this term is used in computing the Q-function ( a) for fixed s and a. Moreover, we only explore {s} h e [H] E [K]] in Algorithm Thus, Algorithm only needs to store fuu, VR. AR, Gr d(s); a) for h E [H]. & E [K]. a E A. The total space complexity is (d + d H)), where K the number of episodes that Algorithm has run.
35

---

Published as a conference paper at ICLR 2023
D.2 COMPUTATIONAL COMPLEXITY OF ALGORITHM
In Algorithm Lines 6-12 show the methods to calculate the estimated value function Vz,5 and policy (-). Notice that only AK.A VR,4+1 and 7 (sf) contribute to the observation steps (Line 15) and calculation of ōR.h. Å AKtIa and 1.+11 (Lines 16-26). We consider the computational cost of the following 3 parts for fixed & E [K].
1. Calculating policy (h()f)) for sh h E [H]. Assume that we have already ob- served sy for some h [H] and calculated fun, Vi,N+1 By definition, = arg maXoea (n a). We can determine T by calculating Qu, a) for all a A. Notice that (s,, a) = 3 ( a))lk + (PAc, VEN+I, (6 a)), which costs O(d²) operations for every A. Thus calculate (x(()))) in Odd ((H)))) for every [M].
2. Calculating f4+11 VR+14+1 for h [H]. In Section D.1 show that we only need to store f Vg,4+1 for every E [K] and h E [M]. Thus, instead of calculating fk+1.6 calculate P V in the (Line 26) and V4+1, (Line 10) in the next episode, next episode by
İKLLA VE+LA4I Arti, Σ ToR LELL
Hence we need calculate VK+1, for i [k], which means we have calculate 1. a) for any i [k] and A. This will take ((d) operations. With known (6/ we need (dd operations to calculate the left term. Thus, cal- culating 1, Vk+1,4+1 will take Odd)AA)HH operations for every h [H] and fixed k [K].
3. Calculating TRA Å A Notice that we can compute ÄRT1A A & by the Sherman- Morrison formula, which takes (dd²) operations. By Lines 16-24, we know that calculat- ing Ōk.h will take another (dd) operations.
By arguments above, for episode k. we need ((d))A(HK) operations. Thus, the full algorithm costs ((H)) which is polynomial in d, |A, H and K, and independent on (8].
36


Reviews:
[{"review_id": "pLsEwYNRxd", "reviewer": "Reviewer_tyVT", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 reward-free learning in linear MDPs. It proposes a computationally efficient algorithm LSVI-RFE and improves the upper bound to O(H^4d^2/eps^2). An Omega(H^3d^2/eps^2) lower bound is also provided.", "summary_of_the_review": "Please see other blocks.", "strength_and_weaknesses": "Strengths:\n\n1. The LSVI-RFE algorithm is computationally efficient and improves the current state of the art bound in reward-free linear MDPs.\n\nWeaknesses:\n\n1. Some literature in reward-free learning could be added to the paper.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "V0o02gwmBxp", "reviewer": "Reviewer_Dide", "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 studies the reward-free reinforcement learning in linear MDPs. In particular, by utilizing techniques from the minimax optimal algorithm for ordinary reinforcement learning in linear MDPs, this paper improves the sample complexity to an order of $\\widetilde{O}(H^4d^2/\\epsilon^2)$. Meanwhile, it also improves the lower bound to an order of $\\Omega(H^3d^2/\\epsilon^2)$, thus matching the lower bound in terms of dimension $d$.", "summary_of_the_review": "This paper improves the upper bound and lower bound for reward-free reinforcement learning in linear MDPs to achieve a sample complexity that is optimal in $d$. However, the technical novelty and significance semm to be limited.", "strength_and_weaknesses": "### Strengths\nThis paper proves a first sample complexity bound that is optimal in $d$ by improving over the previous lower bound. Meanwhile, the paper is also well-written with a clear logical flow.\n\n### Weaknesses\nIt seems most of the technical innovations claimed in Algorithm 1 directly come from [Hu et al. (2022)]. Indeed, it is by no means trivial to derive all details step-by-step. However, it will be better if the paper can clarify whether the techniques in Algorithm 1 that are similar to those in [Hu et al. (2022)] actually contain significant difference.\n\nOn the other hand, the improvement seems to be marginal since [Wagenmaker et al. (2022)] has already achieved optimal dependence in $d$. It will be more significant if the results in this paper can also be optimal in $H$.\n\n```\n[Hu et al. (2022)] 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.\n[Wagenmaker et al. (2022)] Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. Rewardfree rl is no harder than reward-aware rl in linear markov decision processes. arXiv preprint arXiv:2201.11206, 2022.\n```", "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": "IeSZqRpHjR", "reviewer": "Reviewer_nPcg", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 authors study reward-free reinforcement learning in linear MDPs.  In this setting, the agent first interacts with the environment for some fixed number of timesteps without knowledge of the downstream reward function it is trying to optimize.  Based on the estimated transition distribution from samples obtained in this exploration phase, the agent is given a reward function and is tasked with outputting an $\\epsilon$-optimal policy.  This paper focuses on the linear MDP setting, where the rewards and transition kernel can be written in terms of a known feature representation of an unknown vector (or distribution).  The authors show a novel algorithm with an $H^4 d^2 / \\epsilon^2$ sample complexity bound, where $H$ is the episode length and $d$ is dimension of features.  They also show a lower bound of $H^3 d^2 / \\epsilon^2$, essentially showing their result is tight up to a factor of $H$.  The algorithm is based on new concentration based on Bernstein confidence sets to improve upon the sample complexity results of prior literature.\n\nMore concretely, the authors consider an MDP defined as $(S,A,P,r,H)$ where $S$ and $A$ are state-action space, $P$ transitions, $r$ reward, and $H$ horizon.  They assume MDP is linear, i.e. known features $\\phi$ of $S \\times A$ which map to a $d$ dimensional vector with $r = \\theta^\\top \\phi$ and $P( = \\phi^\\top \\mu$ where $\\mu$ is a distribution over the next states.  The goal is to perform reward free exploration, i.e. design policies to explore the space with unknown reward function, and then given a reward function compute a near optimal policy.\n\nAt a high level the authors provide two contributions on this setup:\n1. The authors improve the best known algorithmic guarantee to be $H^4 d^2 / \\epsilon^2$.  The algorithmic framework follows the standard form (use reward as \"exploration\" bonuses in the data collection phase), and then solve planning problem over estimated transitions once given a reward function.  However, they modify the algorithmic sketch by introducing novel confidence terms with Bernstein concentration to obtain the new results.\n2. The authors improve the lower bound result to be $H^3 d^2 / \\epsilon^2$ improving on the best known results.  They highlight how the lower bound is novel, and uses existing techniques from the linear MDP lower bound setup.\n\n## Questions\n- Based on the discussion on page 9 - do you believe that the gap remains in the achievability portion (i.e. designing an even better algorithm to save the extra $H$ factor) or the impossibility result?\n\n## Minor Comments\n- Defining sample complexity on page 4 should highlight that it should hold for all $r$\n- vspace issues on page 6 before algorithm 2", "summary_of_the_review": "The paper provides strong theoretical contributions for improving upper and lower bounds for reward-free exploration in linear MDPs, which improves the state-of-the-art bounds in this setting.  The paper is well written, although very technical, but highlights the main differences and contributions between the paper and the related work.  However, the paper offers no empirical results (or discussion on computational tractability of their proposed algorithm), although standard in the RL with linear function approximation literature.", "strength_and_weaknesses": "## Strengths\n1. The authors tighten the lower bound and prove new state-of-the-art sample complexity guarantees for the well-studied reward free learning in linear MDPs.\n2. The authors present a simple algorithmic framework using existing techniques (least squares regression of the value function under \"bonus\"-tuned reward functions) allowing them to improve on the sample complexity required.\n\n## Weaknesses\n1. The authors include no discussion on the computational complexity of the algorithm.\n2. The authors provide no empirical results of their algorithm's performance\n3 The algorithmic design seems like a straightforward extension of prior mechanisms for linear function approximation for the reward-aware setting. The algorithmic contributions could be highlighted more in the writing.\n", "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": "DMaHwsP61N", "reviewer": "Reviewer_FkPf", "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 studies the reward free exploration problem in the linear MDP setting. It proposes a sample-efficient and computational-efficient algorithm LSVI-RFE, which returns an $\\epsilon$-optimal policy given any reward function using $\\tilde{O}(d^2H^4/\\epsilon^2)$ exploration trajectories, which is tighter than previous works. Moreover, it shows that the lower bound of sample complexity of reward free exploration in linear MDPs is at least $\\Omega(d^2H^3/\\epsilon^2)$. \n", "summary_of_the_review": "This paper proposes a reward free exploration algorithm in linear MDPs with improved sample complexity. It also provides a lower bound by reducing the reward free problem to the standard linear MDP exploration problem. The paper provides rigorous proofs for all the statements, but some formulas and sentences are a bit confusing. Overall, I vote for acceptance, but I strongly recommend the authors to clarify their expressions and clean the typos in the technical part of the paper.", "strength_and_weaknesses": "In general, this paper is an extension from Hu et al. (2022) who studies the regret minimization problem in linear MDPs to the reward free setting. The key technical novelties include the variance-aware weighting mechanism to estimate the transition dynamics, the over-optimistic bonus term in the exploration phase, and a larger exploration function in terms of $H$. Although these techniques have been proposed by Hu et al. (2022) and Chen et al. (2021), it requires effort to adapted them to the reward free setting. However, the results in this paper is not that surprising, given previous works such as Hu et al. (2022) and Chen et al. (2021).\n\nImportantly, I found it hard to understand a few sentences in the main text, mainly because the authors used involved explanations instead of straight forward sentences. For example, what does it mean by \"negligible cost\" at the bottom of page 5? How does the mentioned term relate to the total uncertainty in the exploration phase? Another example is the first sentence in Remark 4.2. It is confusing to directly say \"auxiliary value functions\" and \"decouple UCB bonuses\" since this function and meaning of decouple are not defined at all. I suggest the authors use more straight forward sentences to express their ideas.\n\nLastly, I want to mention that the line spacing on page 5 and 6 seems to be abnormal, the lines are too much squeezed. \n\nMinor comments and typos: \n- Line 9 of Algorithm 1: $\\hat{V}_{k,h}$ -- $\\hat{V}_{k,h+1}$\n- Line 7 of Algorithm 1: it seems that the constant should be 4 according to the proof in Lemma A.15\n- Section 4: instatanous -- instantaneous\n- Why does the first inequality (the $\\sqrt{d}$ term) of Equation (9) hold?", "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