Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
Authors: Weitong ZHANG
Dongruo Zhou
Quanquan Gu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
Reward-Free Exploration
Model Based RL

Abstract: We study the model-based reward-free reinforcement learning with linear function approximation for episodic Markov decision processes (MDPs). In this setting, the agent works in two phases. In the exploration phase, the agent interacts with the environment and collects samples without the reward. In the planning phase, the agent is given a specific reward function and uses samples collected from the exploration phase to learn a good policy. We propose a new provably efficient algorithm, called UCRL-RFE under the Linear Mixture MDP assumption, where the transition probability kernel of the MDP can be parameterized by a linear function over certain feature mappings defined on the triplet of state, action, and next state. We show that to obtain an $\epsilon$-optimal policy for arbitrary reward function, UCRL-RFE needs to sample at most $\tilde O(H^5d^2\epsilon^{-2})$ episodes during the exploration phase. Here, $H$ is the length of the episode, $d$ is the dimension of the feature mapping. We also propose a variant of UCRL-RFE using Bernstein-type bonus and show that it needs to sample at most $\tilde O(H^4d(H + d)\epsilon^{-2})$ to achieve an $\epsilon$-optimal policy. By constructing a special class of linear Mixture MDPs, we also prove that for any reward-free algorithm, it needs to sample at least $\tilde \Omega(H^2d\epsilon^{-2})$ episodes to obtain an $\epsilon$-optimal policy. Our upper bound matches the lower bound in terms of the dependence on $\epsilon$ and the dependence on $d$ if $H \ge d$. 

Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
Weitong Zhang
Dongruo Zhou
Department of Computer Science University of California, Los Angeles
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 drzhou@cs ucla.ellll edu
Los Angeles, CA 90095 weightzero@cs.. wul.s..cclll.........
Quanquan Gu
Department of Computer Science University of California, Los Angeles
Los Angeles, CA 90095 gguêcs www.ucllaeoooooo
Abstract
We study the model-based reward-free reinforcement learning with linear function approximation for episodic Markov decision processes (MDPs). this setting, the agent works in two phases. In the exploration phase, the agent interacts with the environment and collects samples without the reward. the planning phase, the agent is given specific reward function and uses samples collected from the exploration phase to learn a good policy. We propose new provably efficient algorithm, called UCRL-RFF under the Linear Mixture MDP assumption, where the transition probability kernel of the MDP can be parameterized by linear function over certain feature mappings defined the triplet of state, action, and next state. We show that to obtain an e-optimal policy for arbitrary reward function, UCRL-RFE needs to sample at most OHH episodes during the exploration phase. Here, H is the length of the episode, d is the dimension of the feature mapping. We also propose a variant of UCRL-RFE using Bernstein-type bonus and show that it needs to sample at most Ó( + ddc to achieve an c-optimal policy. By constructing special class of linear Mixture MDPs, we also prove that for any reward-free -fee algorithm, it needs to sample at least Q(H 2) episodes to obtain e-optimal policy. Our upper bound matches the lower bound in terms of the dependence on and the dependence on d H 2 d.
Introduction
In reinforcement learning (RL), the agent sequentially interacts with the environment and receives reward from it. In many real-world RL problems, the reward function is manually designed to encourage the desired behavior of the agent. Thus, engineers have to change the reward function time by time and train the agent to check whether it has achieved the desired behavior. In this case, RL algorithms need be repeatedly executed with different reward functions and are therefore sample inefficient or even intractable. To tackle this challenge, Jin et al. [9] proposed new reinforcement learning paradigm called Reward-Free Exploration (RFE), which explores the environment without using any reward function. In detail, the reward-free RI. algorithm consists of two phases. The first phase called Exploration Phase, where the algorithm explores the environment without receiving reward signals. The second phase is called Planning Phase, where the algorithm is given a specific
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

reward function and use the collected data in the first phase to learn the policy. They have shown that this exploration paradigm can learn a near-optimal policy in the planning phase given any reward function after collecting polynomial number of episodes in the exploration phase. Follow up work [12, 14, 28] proposed improved algorithms to achieve better or nearly optimal sample complexity.
All the aforementioned works are focused on the tabular Markov decision process (MDP), where the number of states and actions are finite. In practice, the number of states and actions can be large or even infinite, and therefore, surrctonefurctionn approximation is required for the sake of computational tractability and generalization. However, the understanding of function approximation for reward- free exploration, even under the simplest linear function approximation. remains underexplored, with only two notable related works [18, 27]. Specifically, Wang et al. [18] studied linear MDPs [21, 10], where both the transition probability and the reward function admit linear representations, and proposed a reward-free RL algorithm with (d (1 sample complexity, where d is the dimension of the linear representation, H the planning horizon, and e is the required accuracy. They also proved that if the optimal state-action function is linear, then the reward-free exploration needs an exponential number of episodes in the planning horizon to learn a e-optimal policy. Zanette et al. [27] considered slightly larger class of MDPs with low inherent Bellman error [26], and proposed an algorithm with (dd f sample complexity. However, both works assume the reward function is a linear function over some feature mapping. Moreover, the lower bound proved in [18] is for very large class of MDPs where the optimal state-action function linear, thus is too conservative and cannot tell the coormation-theoretie limits of reward free exploration for linear MDPs or related models.
In this paper, we seek a better understanding of the statistical efficiency for reward-free RL with linear function approximation. We propose two reward-free model-based RI. algorithms for the finite-horizon episodic linear mixture/kernel MDP [16, 7, 3, 30), where the transition probability kernel is a linear mixture model. In detail, our contributions are highlighted as follows:
We propose a new exploration-driven reward function and its corresponding pseudo value function for linear mixture MDPs, which will encourage the algorithm to explore the state-action pair with more uncertainty on the transition probability.
We propose a UCRL-RFE algorithm which guides the agent to explore the state space using the exploration-driven reward function and pseudo value functions. We prove an ((=)) sample complexity for UCRL-RFE to achieve an e-optimal policy for any reward function for time-homogencous MDP.
We further propose a UCRL-RFE+ algorithm which uses a Bernstein-type exploration bonus. UCRL-RFE+ can reduce the error caused by the exploration-driver reward function during the exploration phase. With a novel analysis based on total variance, we prove an Ö(H ad( + +d) sample complexity for UCRL-RFE+, which improves that of UCRL-RFE by factor of min d).
By constructing special class of linear mixture MDPs, show that any reward-free algorithm needs to sample at least d -2) episodes to achieve an e-optimal policy for any reward function. This lower bound matches the upper bound of UCRL-RFE+ in terms of the dependence on the accuracy e and feature dimension d when H 2 d.
Notation. Scalars and constants are denoted by lower and upper case letters, respectively. Vectors are denoted by lower case bold face letters x, and matrices by upper case bold face letters A. We denote by [k:] the set 21, k)} for positive integers k. For two non-negative sequence {a,z) (b,, }. a, (b,)) means that there exists a positive constant C such that an S Cb,, and we use Ö(-) to hide the log factor in O()); an S(b..) means that there exists positive constant C such that an Cb., and we use 22(-) hide the log factor. a, o(b,) means that lim, an/b, = O. We denote by S, A as the cardinality of the state set S and action set A separately. For a vector x Rdd and corresponding matrix A E Idddd we define ||x||² x Ax. We denote [=](0,1)) == max (mn H), 0}. For vector x E Rdd, we denote by [x); the i-th element of x.
2 Related Work
Reinforcement Learning with Function Approximation. Function approximation is extremely useful for RL when the state space and/or the action space are large or even infinite. To develop

---

provable RL algorithms with linear function approximation, linear MDPs [10] is probably the most widely assumed MDP model, where both the transition kernel and the reward function are linear functions of a given feature mapping. A line of works has developed RI. algorithms with polynomial sample complexity or regret bounds under this setting, such as L.VV--CB [19] and randomized L.VV [24]. Besides the linear MDP, linear mixture/kernel MDPs [16, 7, 3, 30] has emerged as a new model which enables efficient RL with linear function approximation. is linear function over feature mapping on the triplet of state, action, and next-state. Under this assumption, nearly minimax optimal regrets can be attained for both finite-horizon episodic MDPs and infinite-horize discounted MDPs [29]. Note also that linear mixture MDPs do not require the reward function to be linear and therefore enables RL with arbitrary reward functions. Therefore, we also consider linear mixture MDPs in this paper.
this setting, the transition kernel
Time Homo.
Model Based
Algorithm
Sample Complexity
MDP Type
Jin et al. [9]
AcH
Tabular
RF-UCRL [12]
O(
Tabular
RF-Express [14]
O(H3
X
Tabular
SSTP [28]
0(H252
V
Tabular
Lower bound [9]
A(H253A022
V
Tabular
Wang et al. [18]
Linear MDP
x
FRANCIS [26]
0(H58E2)
V
Linear MDP
x
UCRL-RFE (Alg. 2)
0(H)
V
Linear Mixture
UCRL-RFE+ (Alg. 3)
((
V Linear Mixture
Lower bound
d(H2dc
Linear MDP/Linear Mixture
(Thm. 6.1)
Table 1: Comparison of episodic reward-free RL algorithms. Time Homo, stands for the MDP is a time-honmee homogeoomg,,,uu,, where the transition probabilities are the same at different stages of the episode. Model Based stands for the algorithm is a model-based algorithm (v) or a model-free algorithm (x).
Reward-Fee Exploration. As the first work on reward-free exploration, Jin et al. [9] assigned each state an ssploration-driver reward function at each round to guide the algorithm to do exploration. Then they utilized the EULER [25] algorithm to minimize the total regret. Their algorithm achieves an OS A sample complexity in the tabular setting to achieve an e-optimal policy, where S the number of states and A is the number of actions. They also proved a sample complexity lower bound 52(52 -2). Kaufmann et al. [12] extended the UCRL [2] algorithm to the reward-fiee free exploration. Their algorithm RF-UCRL achieves a sample complexity of O(5 AH which improves that of [9] by a factor of H. Ménard et al. [14] proposed RF-Express algorithm by modifying the UCB-bonus of UCRL to making it decay faster and achieved a sample complexity of OS5 3H) Zhang et al. [28] proposed SSTP algorithm in the time-homogeneous setting, which achieves O(52 - sample complexity, and matches the minimax lower bound provided in [9] up to logarithmic factors. Liu et al. [13] has shown the similarity between the self-play setting and reward-free setting. All of these works are for tabular MDPs.
Here we summarize and compare the related works on Reward Free Exploration in Table 1. Notice that our lower bound Q 2 2 for linear mixture MDPs can imply the same lower bound for linear MDPs and MDPs with low inherent Bellman error, using a similar argument used in [29].
3 Preliminaries
We consider episodic Markov Decision Processes (MDP), which is denoted by a tuple M(S, A, H, (rk) PP) Here S is the countable state space (may be infinite), A is the action space, H is the length of the episode, Th generality, we assume the reward function is deterministic. P(s'|s, a) is the transition probability function which denotes the probability for state s to transit state s' given action a at step policy Th S + A is a function which maps a state to an action We define the action-valuc
A + [0, 1] the reward function. Without loss of
3

---

function (i.e., Q-function) (%, a) as follows:
H
Th (sws aw) = an a a Vx (ma)a) - (n(s;: (rala)-
QK(s, (ra)a) = E
h/=h
For simplicity, we denote Q7 a;r) (s, {ra]a) and Vi (s; (s; (n)) We define
the optimal value function (Vr ===1 and the optimal vetiu function {Q; (s:r)
sup, V (s;T) and Q7 (s,arr)) = sup- 27 (s, a: respectively. For any function V S R, we denote [PV] (8, a5r) Eg ((-Iaa))))) ( and denote the variance of V
(s](s, [ a)
a)²).
(3.1)
In particular, we have the following Bellman equation, as well the Bellman optimality equation: (7, r) = rx(,,a) I r)r), (1, = (s, + [VV++1]( (8,,))))
In this paper, we focus on model-bused algorithms and consider the following linear mixture/kernel MDP [16, 7, 3, 30], which assumes that the transition probability is a linear mixture of signed basis measures. Meanwhile, for any function V, assume that we can do the summa- tion Eves (ss (s)) efficiently, c.g., using Monte Carlo method [22].
Definition 3.1 (Linear Mixture MDPs [7, 3, 30)). The unknown transition probability IP is linear combination of signed basis measures (sssssss0 a), i.e., a) Eiz o a)Ø; Mean- while, for any V S - [0, 1], i [d] (s.a) a) E S x is computable. For simplicity, let Φ [øi...., Eves ( (s). Without loss of generality, we assume 10- S B, (1 a)la) I for all V [0, 1] and (s,a) E S
(iss|ssa)) 7 Epes ( a))(")
A. the summation
0- 00 ................................ .0 and (s, =
Remark 3.2. A similar but notably different definition (i.e., linear MDPs [21, 10]) has been used in [18]. which assumes that F(s'|s,a) = (Ø(s, a), (u(')) and ry, = (Ø(s, a), 0n), (x(-) is measure and 0 is unknown vector. Comparing with linear MDPs, linear mixture MDPs do not need the reward function r to be linear, which makes our algorithms more general.
With Definition 3.1, it is easy to verify that the expectation of any bounded function V is linear function of sp:
PV] a) = (tby (8, 0*).
(3.2)
Reward-free RL For reward-free RL, the algorithm can be divided into two phases: exploration phase and planning phase. In the exploration phase, the algorithm cannot access the reward function but collect K episodes by doing exploration. In the planning phase, the algorithm is given series of reward functions and find the optimal policy based on these reward functions, using the K episodes collected in the exploration phase. We formally define (c, (c,,))-ean -eeann and sample complexity of the algorithm as follows [9].
Definition 3.3 ((e, 8) -earnability). Given an MDP transition kernel set P. reward function set R. and a initial state distribution μ4, we say reward-fre free algorithm can (e, 8) -e-aea the problem (P, R) with sample complexity K(c, 8), if for any transition kernel P E P. after receiving K(c, 6) episodes in the exploration phase, for any reward function r E R, the algorithm returns a policy æ in planning phase, such that with probability at least 1 6, E [V* (s1:r) VT (s1:)))]
4 Algorithm and Main Results
In this section, we propose a reward- -free algorithm. This algorithm works as follows: Firstly, during the exploration phase, it samples the MDP episodes, build an estimator for the MDP parameter 0* and compute the covariance matrix Σ of the feature mappings, which characterizes the uncertainty of the estimator O. Secondly, during the planning phase, the algorithm uses the collected 0 and Σ in the exploration phase to find the optimal policy based on the given reward functions.
4.1 Planning phase algorithm
We first introduce the PLAN function (Algorithm 1), which a common module in both planning phase and exploration phase. Given a series of reward functions frah the goal of PLAN function

---

Algorithm UCRL-RFE Planning Module (PLAN)
Input: Estimated parameter and covariance 0, E, reward {rm (r parameter 3.
1: For consistency, set (=+)(:))) :) < (+++(.)) + 0
2: for h = H, H 1.... ..... 1 do
3: Compute Q function Qx(:; -) (ra(+)) (1rraal (1:),) 8 811 (>-))lx-))
4: Compute value function (-) f max Q1((:a)
5: Compute policy as (+)-) argmax Qu(:,))
6: end for
Output: Policy π {TA) and (Va)==
to output the optimal policies (#A Ja and Q-functions {Q+}a corresponding to frr Suppose the unknown parameter O' is known, we can compute (Qn)a recursively by the following Bellman equation:
Qn(s,ar)) = (s, + [PV a; (s, + (sV.., (),
(4.1)
However, since 0* is unknown, we cannot compute Qa as in (4.1). Instead, PLAN takes the estimated parameter & and the "covariance matrix" Σ as input. To calculate Qn, PLAN replaces 0 with the estimated P and plus an additional exploration bonus term 8l|vvr,,, (1--) to (4.1), in Line of Algorithm 1. Then PLAN takes the greedy policy of the calculated optimistic Qn and proceeds to the previous step. Finally, the algorithm returns policy i Line well as the estimated value functions [V
4.2 Exploration phase algorithm
Based on the introduced PLAN function, we propose the UCRL-RFE algorithm Algorithm 2. In general, UCRL-RFE guides the agent explore the unknown state space without the information of the reward functions. In detail, for the k-th episode, UCRL-RFE first defines the exploration driven reward function as follows:
(s) min {1,
233
V SES- (1)))(s,0)1 1
max
(4.2)
where L1, is the "covariance matrix" of the feature mapping. Intuitively speaking, r (8, a) represents the maximum possible uncertainty level of the state-action pair (s,a) caused by the randomness of the MDP transition function, which is independent of the true reward functions. Therefore, order to obtain good estimation of the optimal policy for any given reward functions, suffices to obtain the optimal policy for (s, a). Thus, after obtaining {rfh,. UCRL-RFE finds the corresponding near- optimal policies {m]] J using PLAN function, with the estimated parameter 0₂ and the "covariance matrix" Σ1, as input. UCRL-RFE uses {mr)) as its exploration policy and observes the new episode st, & .f....,,s
the
st ; a induced by {T/h In.
Next, UCRL-RFE needs to compute the parameters 02+1 and E for planning in the next episode. Similar to UCRL-VTR proposed by [7, 3], UCRL-RFE also uses "value-targeted regression (VTR)" estimator, which computes 0x+1 as the minimizer to ridge regression problem with the target being the past value functions. The main difference between UCRL-RFE and UCRL-V VTR is that, due to the lack of true reward functions, UCRL-RFE can not use the estimated value functions its regression targets. Instead, UCRL-RFE defines the following pseudo value function uh:
argmax +T E 1 af)).
(4.3)
SES-
Here, uă maximizes the "uncertainty" caused by the transition kernel. which will help the agent to explore the state space. Now given the pseudo value functions, Algorithm 2 computes the estimated 0 as the minimizer to the following ridge regression problem:
H
(0, (sh )) - wy (2itz))²
Ok+1 + argmin 2|
+
(4.4)
0
k Fumm
5

---

which has a closed-form solution as in Line 12. It also updates the covariance matrix E1.++1 as in Line 12, by the observed feature mapping { (s% h, h. in the current episode. In the end, after collecting HK acteon samples, UCRL-RFE calculates the policy {TA) output based on 0x+1 and +1
Algorithm 2 UCRL-RFE (Hoeffding Bonus)
Input: Confident parameter B, regularization parameter À
1: Phase I: Exploration Phase
2: Initialize 1 f- AI, bj t 01 +
3: for 1, ... .K do
4: Compute the exploration driven reward function (rx(::) according to (4.2)
5: Compute exploration policy and value function ((* (VA 18=1) PLAN(O.. Ey,e (PhJkan.
6: Receive the initial state sf μ
7: for h 1, 2, .... H. do
8: Take action afF +- TT (s%) and receive sh+1
9: Calculate uf for sh, at according to (4.3)
10: Set En+ 1,k f- EA, + thg (6 a Jabe / (0%, aT) ba+1A +- bu,e + Duy u (0% (i (0h422)
11: end for
12: Set E1 + EH+LK. 61,+11 + bH+1 ax+1 + 2j,441 b1,411
13: end for
14: Phase I: Planning Phase
15: Receive target reward function (rh 1H
16: Compute policy as (fTa) (Vr (V))==)) + PLAN(OK-1. E1,441, (ra)
Output: Policy {
Remark 4.1. Here do comparison between UCRL-RFE and the reward-free RL algorithm in [18]. The main difference is that Wang et al. [18] estimates 0₂ by regression with value function Vž being the target, while our UCRL-RFE does regression with the pseudo value function ut being the target. That is mainly due to the different problem settings (linear MDP v.s. linear mixture MDP).
4.3 Implementation details
In general, solving the maximization problem (4.3) is hard. Here, provide simple approximate solution to the problem (4.2) and (4.3) for the finite state space case (SS) < 20). Instead of maximizing
1/2 the & norm-based objective 1_ " (o(s, a, .1), ................................ o(s, a, S(s))) and (sskaaa))ll 1 we write ( a) (5s, a) with ((s, a)
(f(S)), ... f(()s)) relax the le norm into & norm since |x||2 | V for any Rdd and maximize the following & norm-based objective
max Σ i,
12 (s, a)fl/; subject to ||f H h.
(4.5)
(4.5) can be formulated linear programming, which can be solved by interior method [11] or simplex method [5] efficiently. Since || / < ||x||2 < ||x|] the performance of this approximate solution is guaranteed. For the case where the state space is infinite, we can use state aggregation methods such as soft state aggregation [15] to reduce the infinite state space to finite state space and then apply the above approximate solution to solve it.
4.4 Sample complexity
Now we provide the sample complexity for Algorithm 2.
Theorem 4.2 (Sample complexity of UCRL-RFE). For Algorithm 2, setting parameter /
H (o + 3²3 11 X = B then for any 0 < E < if 0( we have with probability at least 1 5 that, [V-
(s;r) c.
Remark 4.3. Theorem 4.2 shows that UCRL-RFE only needs poly(d, H.c-I) sample complexity to find an e-optimll policy, which suggests that model-basee based reward-free algorithm sample-efficient. Thanks to linear function approximation, the sample complexity only depends on the dimension of the feature mapping d and the length of the episode and does depend on the cardinalities of the state and action spaces.

---

Corollary 4.4. Under the same conditions as in Theorem 4.2, if solving the relaxed optimization problem in (4.5), Algorithm 2 has K = o( sample complexity.
Improved Algorithm with Bernstein Bonus
Theorem 4.2 suggests that UCRL-RFE in Algorithm 2 enjoys an ((H sample complexity to find e-optimal policy. In this section, seek further improve the sample complexity.
key observation is that for any given reward functions (r the error between the exploration policy {T and the optimal policy can be decomposed into two parts: the exploration enror which is the difference between {r and the exploration driven reward function {r and the approximation error which is the difference between the optimal value function V (+:a%) and our
estimated value function 1ith (c:r%) with respect to {r% Ja. For the latter one, our exploration strategy adapted from VTR is often too conservative since does not distinguish different value functions and aate-action pairs from different episodes and steps. Therefore, inspired by [29], we propose
variant of UCRL-RFE called UCRL-RFE+, which adopts a Bernstein ttppe bonus for exploration and achieves a better sample complexity.
Algorithm 3 RFR+ (Bernstein Bonus)
Input: Parameter B, 3, 3. regularization parameter À 1: Stage I: Exploration Phase
2: Initialize Σ Σ Σ1, AI, bi = bj
3: for k ===11 1.2, ... K do
4: Set (r m== to (4.2).
5: Compute exploration policy and value function as ((*)) (/ ) PLAN( ELe, (rA)
6: Receive the initial state of ~ μt.
7: for h 1, ... do
8:
Take action at = ( and receive wh+1
9:
Calculate uh, of for si at according to (4.3) and (5.2) separately
10: Set Eb+ 4- En, + bag (sh, bbg (s%.at) aT)
11:
Set E 1 11+1A b b using (5.4)
end for
13:
Set E1,++1 + EH+Lk
Set Σ1,441 + Entia 61,411 + b Oct1 -
11,++ (1
15: Set Σ1,++1 + ΣHTLK DLA+I t 1H41K, Qut1 + Σ j 1i.1,biuu b1,411
16: end for
17: Set 0k+1 + 11 EK Eln Vot (sh u (s
18: Stage II: Planning Phase
Receive target reward function (rr)
20: Compute exploration policy as hh=1: (V.) PLAN 1,, E1,441, (H B)
Output: Policy (mh )/
5.1 Exploration phase algorithm with Bernstein bonus
UCRL-RFE+ in presented in Algorithm 3. The algorithm structure is similar to that of UCRL-RFE. which can be decomposed into the exploration phase and planning phase. There are two main differences. First, in contrast to UCRL-RFE which uses O₂ for the PLAN function in both exploration and planning phases, UCRL-RFE+ only uses 0 for the PLAN function in the planning phase. For the exploration phase, UCRL-RFE+ constructs a new estimator O2 based on {Vk
h+ Je which are the value functions of the exploration driven rewards. Second, build OE. one way is to choose as the solution the ridge regression problem with contexts abya' h++ (o kk and targets V (*%+1)
similar to (4.4). However, since the targets Vi (s)())) have different variances at different steps and episodes, we are actually facing a heteroscedastic linear regression problem. Therefore, inspired by recent line of work [29, 20] which use Bernstein inequality for valued self- normalized
7

---

martingale to construct tighter confidence ball for exploration, we also incorporate the variance to build choose O2 the solution to the following weighted ridge regression problem, which is an enhanced estimator for the heteroscedastic case:
bg c argmin X 110 +
ΣΣ
(0. (0. (oh .a,))) - Vi (5t1((h+)))) /l0
(5.1)
R-1A=1
where [0 is the variance of 4+1 (5 1+1)) The idea to use variances to improve the sample complexity closely related to the use of "Bemsttein bonus" in reward-free RL for the tabular MDPs [12, 28, 14J. Since of unknown, we will use o = 1ox ] as a plug-in estimator to replace (a Ja in (5.1). After obtaining dR. UCRL-RFE+ sets the E1, as the covariance matrix of the features vyy,, (sk/a//// /ft and feeds it into the PLAN function with the exploration-drive driven reward functions
and the confidence radius 3. UCRL-RFE+ takes the output {m/ h the exploration policy, and (VA Th as the value functions to construct the estimator 0x+1 for next episode. In the end, when comes the planning phase, after receiving reward functions {rr ha UCRL-RFE+ takes 0k-1 the solution to the ridge regression problem with contexts (t)w) (s%, J,),,,,. and targets {u (#f++1) 1 Ja, and the covariance matrix E1,++ as input, and uses PLAN to find the near optimal policy { with confidence radius B. It remains specify of in the weighted ridge regression. On the one hand, we need of to be an upper bound of [o On the other hand, require vi to have strictly positive lower bound let (5.1) be valid. Therefore, we construct v follows:
/ = max(a, ( a + (s a/)).
(5.2)
where V is the estimated variance of value function V/2 and FE is correction term to calibrate the estimated variance, and a > 0 is a positive constant. To compute 8% (8 a considering the following fact:
[VV ((s, a) = [P[V 13 a) - [PV h+ [(s, as) (0", , 1a (s, a)) - (0", vy,, (s, a)}? suffices to estimate (0", Viive, Fivve,,.% (s, a)) and (0", l/ve,, a)) separately. For the first term, 0" can be regarded as the unknown parameter of a regression problem w.r.t. contexts VIvE,, p o/ a and targets $1 Ja (5% a.'). Therefore, the first term be estimated by (NIIEE, (r a), 0x). where
H ΣΣ (10, th (O of - (5t
k-1
0x + argmin 2llllk +
W=1A=1
In addition, the second term (0), vy,,, (s, a)) can be approximated by (2vv; (s, a). 0z). Therefore, the final estimator [VVA h+ [(s, a) is defined as
(8, a). (s, a) = (ViVA, [= a), 0b) (0.112) - (s)),, 0z) (s) (0.11)
(5.3)
For the correction terms Ex, we define it as follows:
D (s. a) min H 1,,,B B v (s, a) [|s + min 112,21111
(s, a) $
where Σn k is the covariance matrix of the features 1 Sov,,,p( (5h ax B. 3 are two confidence radius. It can be shown that, with these definitions, (h(s, a) + E a) is an upper bound of [o*]².
Finally, to enable online update, UCRL-RFE+ updates its covariance matrices recursively as follows, along with sequences bj, b/::
ENTLA En.t + duy (s aiv ai)) /v
Σn4I + En,t + Wive, (sh at & (5h T DALLA + DAL + vye, (sh, af V
BALLA DaLk + thive, (0h a V/ (s
(5.4)
8

---

have where ii is the pseudo value function in (4.3) and v is defined in (5.2), Then UCRL-RFE+ computes Og Ox as in Line 14 Line 15 of Algorithm 3.
5.2 Sample complexity
Now we present the sample complexity for Algorithm 3.
Theorem 5.1 (Sample complexity of UCRL-RFE+). For Algorithm 3, setting = B-2 a = H12/d in (5.2), and the confidence radius
B 8 d'log(1 KHB bgg 4 +1
8d /lo/oog11 KHBB3 1 4 H² /6) +1
3 8H2 (1 + + log 48 H² / /8) +
B = H -
then for any < E Lf
+ d)e 3). then with probability at least
-
Remark 5.2. Theorem 5.1 suggests that when 2 H. the sample complexity UCRL-RFE+ is O(11AdE=²)) which improves the sample complexity of UCRL-RFE by factor of H. On the other hand, when H 2 d, the sample complexity of UCRL-RFE+ reduces to OHHSde- which is better than that of UCRL-RFE by a factor of d. At high-level, the sample complexity improvement is attributed to the Bernstein-type bonus.
Corollary 5.3. Under the same conditions as in Theorem 5.1, if solving the relaxed optimization problem in (4.5), Algorithm 3 has K = d8 sample complexity.
Lower Bound of Sample Complexity
In this section, we will provide lower bound of sample complexity for reward-free RL under linear mixture MDP setting.
The proof by construction. Given d 2 2, we first define binary vector set M fx|x e Rd-1, [x]; E [-1,1)}- We index each vec- XiMI- Equipped with the set M,, we construct class of MDPs. As shown in Figure 1, there are in total three states SI, S2 S2.2 and |A| [M] actions a1 .-. A|A)- We define the feature mapping ())))),a,) E Rdd as follows:
1/2 c(ai, 0.)
S2.1
tor in M as X1,
S
S2,2
1 c(ai, 0.)
((52,15),a)) =
1/2
22d
The transition kernel IP of the class of hard-to-learn linear mixture MDPs. The kernel P is parameterized by 0 (V2, /Vd) T for some small a. c = ee/(vdd). The learner knows the MDP structure, but does not know the parameter ( O, (or 0, M).
Figure
Φ( ((
V2 4
22
(S a.) (1/V2 O for = 1,2,
and ( s) a) for all the remaining cases.
Furthermore, we define a d-dimensional pa-
rameter set C S 1 by (V2,007 [) where 0 x; E M and is a small absolute constant. Therefore, for each pa- rameter 0, we define the transition probability of the linear mixture MDP as P(-..:)) (6(-1-.)),) 0.). Specifically, the transition between S₁ and (S2.1, S2,2) is represented as
Pe. (S2.1 az) 2
+ a
2al (,,
Po. (S22 az) =
1 a
(.. 22d"
Meanwhile, we have S2,1 and S2.2 are both absorbing states. With the constructed hard-to-learn MDP class, we can prove the lower bound of sample complexity follows:

---

Theorem 6.1. Given dimension d 2 50 and H 2 2. set I (H 1)/(2v2) and é E (0.1/2), then there exists class of linear mixture MDPs, such that any reward-free RL algorithm that (e, 6l-laarss the problem (P, R) where R = ((rn)e=1 0 S I 1), needs to collect at least K = C(1 - 5 -2 episodes during exploration, where C' is an absolute constant.
Remark 6.2. When d S H, the sample complexity of UCRL-RFE+ is OH -),, which matches the lower bound in terms of both and d, ignoring the logarithmic terms. When d >> H, the sample complexity of UCRL-RFE+ is ((H)) which matches the lower bound only in terms of The factor of gap between the upper and lower bounds is due to the fact that our upper bound holds for the arbitrary number of actions. Such gap also appears in best-arm identification in the linear bandits problem (See Eq. (3) in Tao et al. [17] with N = O)2)). There is also a factor of H² gap between the upper and lower bounds, and leave it future work to remove this gap.
7 Conclusion
We studied model-based reward-free exploration for learning the linear mixture MDPs. We proposed two algorithms, UCRL-RFE, and UCRL-RFE+ which are guaranteed to have polynomial sample complexities in exploration find near-optimal policy in the planning phase for any given reward function. To our knowledge, these are the first algorithms and theoretical guarantees for model-based reward-free RL with function approximation. We also give sample complexity lower bound for any reward-free algorithm to learn linear mixture MDPs. The sample complexity of our algorithm UCRL- RFE+ matches the lower bound in terms of the dependence on accuracy and feature dimension d when H 2 d.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments. WZ, DZ and QG are partially supported by the National Science Foundation CAREER Award 1 1906169, 69, IIS- 1I-41904183 and AWS Machine Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
[1] ABBASI- YADKORI, Y., PÁL, D. and SZEPESVÁRL ÁRI, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems.
[2] AUER, P., JAKSCH, T. and ORTNER, R. (2009). Near-optimal regret bounds for reinforcement learning. In Advances in neural information processing systems.
[3] AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L. (2020). Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning. PMLR.
[4] AZUMA, K. (1967). Weighted sums of certain dependent random variables. Tohoku Mathemati- cal Journal, Second Series 19 357-367.
[5] DANTZIG, G. B. (1965). Linear programming and extensions, vol. 48. Princeton university press.
[6] FANO. R. M. (1961). Transmission of information: A statistical theory of communications. American Journal of Physics 29 793-794.
[7] JIA, Z., YANG, L., SZEPESVARI, C. and WANG, M. (2020). Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control. PMLR.
[8] JIN, C., ALLEN-ZHU. 7.,, BUBECK, S. and JORDAN, M. I. (2018). q-learning provably efficient? In Advances in Neural Information Processing Systems.
[9] JIN, C.,, KRISHNAMURTHY, A., SIMCHOWITZ, M. and YU, (2020). Reward-free exploration for reinforcement learning. In International Conference on Machine Learning. PMLR
10

---

[10] JIN, C.,, YANG, Z., WANG, Z. and JORDAN, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory.
[11] KARMARKAR, N. (1984). A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing.
[12] KAUFMANN, E., MÉNARD, P., DOMINGUES, O. D., JONSSON, A., LEURENT, E. and VALKO, M. (2021). Adaptive reward-free exploration. In Algorithmic Learning Theory. PMLR.
[13] LIu, Q. YU, T., BAI, Y. and JIN, C. (2020). sharp analysis of model-based reinforcement learning with self-play. arXiv preprint arXiv:201.01604.
[14] MÉNARD, P., DOMINGUES, O. D., JONSSON, A., KAUFMANN, E., LEURENT, E. and VALKO, M. (2020). Fast active learning for pure exploration in reinforcement learning. arXiv preprint arXiv:2007.13442
[15] MICHAEL, S. P. S. T. J. and JORDAN, I. (1995). Reinforcement learning with soft state aggregation. Advances in neural information processing systems 361.
[16] MODI, A., JIANG, N., TEWARI, A. and SINGH, S. (2020). Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics.
[17] TAO, C., BLANCO, S. and ZHOU, Y. (2018). Best arm identification linear bandits with linear dimension dependency. In International Conference on Machine Learning.
[18] WANG, R., DU, S. S., YANG, L. F. and SALAKHUTDINOV, R. (2020). On reward-free reinforcement learning with linear function approximation. Advances neural information processing systems.
[19] WANG, Y., WANG, R., DU, S. S. and KRISHNAMURTHY, A. (2019). Optimism in reinforce- ment learning with generalized linear function approximation. In International Conference on Learning Representations.
[20] WU, Y., ZHOU, D. and GU, Q. (2021). Nearly minimax optimal regret for learning hnfinite-horizon average-reward mdps with linear function approximation. arXiv preprint arXiv:2/02.0730/
[21] YANG, L. and WANG, M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International Conference on Muchine Learning. PMLR.
[22] YANG, L. and WANG, M. (2020). Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning. PMLR.
[23] YAO, A. C.-C. (1977). Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfes 1977). IEEE.
[24] ZANETTE, A., BRANDFONBRENER, D.. BRUNSKILL, E., PIROTTA, M. and LAZARIC, A. (2020). Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics.
[25] ZANETTE, A. and BRUNSKILL, E. (2019). Tighter reinforcement learning without domain knowledge using value function bounds. In International Conference on Muchine Learning. PMLR.
regret bounds in
[26] ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. and BRUNSKILL. E. (2020). Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning. PMLR.
[27] ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. J. and BRUNSKILLL, E. (2020). Provably efficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems.
(28) ZHANG, 7.,, DU, S. and JI, X. (2020). Nearly minimax optimal reward-free reinforcement learning, arXiv preprint arXiv:2010.05901.

---

[29] ZHOU, D., GU, Q. and SZEPESVARI, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR.
[30] ZHOU, D., HE, J. and GU, Q. (2021). Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning. PMLR.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] See Remark 6.2 addressing the gap hetween the lower bound and the upper bound
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We focusing on the theoretical analysis for Reinforcement Learning, no negative social impact can be found this point
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "zOSutigWjq0", "reviewer": "Reviewer_GGZY", "summary": "The submission considers reward-free exploration scheme for linear mixture MDPs. Similar studies have been done in [17, 26] for a very similar setting of linear MDPs. In both models, the key property is the linear representability of value functions. The proposed algorithm is an optimism-based exploration scheme for linear mixture MDPs with Hoeffding's (or Bernstein's [28]) exploration bonus for linear models. In spirit, this is similar to Kaufmann et al. [12] which studied a similar reward-free approach in tabular MDP settings. If the computational aspect is not concerned for finding a optimistic value-function, then the sample complexity is upper bounded by $O(d^2)$. For computationally efficient implementation, sample complexity is increased by a factor of $O(d)$. The authors also provide a lower bound $\\Omega(H^2 d / \\epsilon^2)$ for reward-free exploration.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is incremental in terms of the originality and significance: (1) the importance of the study on the proposed model should have been more discussed, since a very similar model (linear MDP) has already been studied quite a bit as a benchmark for theoretical studies on function approximation, and (2) techniques (optimistic value-iteration, Bernstein-type bonus) are not particularly new. Pseudo value function seems not much more than some optimistic value function for linear mixture MDP, which is new only because the considered model is different from linear MDP which have slightly different representation for transition and reward models. Main results are also somewhat predictable given many previous works on linear function approximation [3, 7, 10, 12, 17, 26, 28]. Overall, I recommend rejection for this paper. \n\n\n\nComments\n\n1. The claim for matching upper and lower bounds sounds misleading since it only holds for H \\ge d (and in this case, dependence on H is sub-optimal anyway) and computationally inefficient algorithm. \n\n2. Line 43-44 (They also proved ...): In which setting [17] proved exponential lower bound?\n\n3. Line 46-50 (However, both works ...): I do not understand why the model considered in previous work is a very larger class than linear mixture MDP. \n\n4. Eq (4.4): Why do you need regularizer on $\\theta$? On which line in Algorithm 2 uses $\\lambda$? \n\n5. Theorem 4.2: What is B? Any value range for B?\n\nSee also the limitations.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the approach does not seem to be so well discussed in this work. In particular, more discussion on differences/novelties of the approach in comparison to previous work [7, 12, 17, 28] would have helped a lot to appreciate contribution of the paper. I also wonder if the sample complexity could have been better by O(d) in [17, 28] if a NP-hard optimization solver is allowed (as the authors assume for solving (4.3)). If that's the case, then I think even the result is not particularly novel since the improvement on the sample complexity on O(d) is mostly due to ignoring this computational issue. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "q4GG1Dq6rh9", "reviewer": "Reviewer_G5QY", "summary": "In this paper, the authors study reward-free exploration in linear mixture MDPs where the transition probabilities are linear combinations of d known models. The authors propose UCRL-RFE which solves the problem provably efficiently. The authors further improve the sample complexity by using Bernstein-style exploration bonus. Finally, by constructing a hard instance with constant number of states and exponential number of actions, the authors prove a sample complexity lower bound for the problem under consideration. ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "Recently there has been great in understanding the sample complexity of reward-free exploration in reinforcement learning. In this paper, the authors study reward-free exploration in linear mixture models. The main methodology is to combine the idea of defining exploration-driven reward functions as the uncertainty bonus (such idea was proposed in [17]) and mechanisms for quantifying uncertainty in linear mixture models. Moreover, the authors show how to improve the sample complexity by using a Bernstein-type uncertainty bonus. The authors also prove a lower bound by constructing a hard instance with three states and exponential number of actions. \n\nMy main concern is the lack the novelty. The algorithms presented in this paper follow the same methodology developed in [17], with modifications on the exploration-driven reward function so that it works for linear mixture models (see Remark 1). Is that true that the main algorithm in this paper is a direct combination of the methodology in [17] and uncertainty quantification techniques for linear mixture models? If not, the authors should consider adding a section highlighting the technical challenges they face when adapting the methodology in [17] to linear mixture models. Such a discussion will significantly improve the paper.\n\nMinor comment\nTable 1: the algorithm in [25] does not work in linear MDPs. Rather, it requires linear completeness and certain explorability assumption. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "CdwdUL66X0V", "reviewer": "Reviewer_a98J", "summary": "The authors consider reward-free exploration for episodic MDP under the assumption of linear kernel MDP. Precisely they assume that the transition kernel is a linear function over a certain feature mapping. And the goal is to explore the MDP (without observing the rewards) in order to be able to predict the optimal policy for any reward function with high probability. They propose the model-based UCRL-RFE algorithm which uses exploration-driven reward and estimates the parameter by least-square regression with well-chosen targets. They prove a bound on the sample complexity of  UCRL-RFE of order O(H^5d^2\\epsilon^{-2}). They also propose a variant of UCRL-RFE with Bernstein-type bonus that enjoys a sample complexity of order O(H^4d (H+d)epsilon^{-2}). Finally, they provide a lower bound on the sample complexity for reward-free exploration of order \\Omega(H^2d\\epsilon^-2).", "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": "The paper is well written and the proofs seem correct (see specific comments, I did not check the proofs relative to Algorithm 3). I think that in absolute terms it is interesting to study the optimal problem independent rate for reward-free exploration problem with linear kernel assumption. But on the other hand, the implementation seems limited to the tabular case and no simple examples are provided. Thus the proposed solution seems rather theoretical. \n\nMain comments:\n-Can you provide intuition on the different sources of \"optimism\" in your algorithm. Because they are: the exploration driven reward function, additional bonuses in PLAN, and pseudo value function which should all help to explore. In particular why we cannot use the value V_h^k for the target and in the exploration-driven rewards instead of the max (this would save computations)?\n\n-Can you elaborate on the implementation of UCRL-RFE when S is large or infinite? In particular, what is the time complexity of the algorithm in this case?  E.g. do we actually need to do a complete pass over all state-action pairs in Planning Module, Algorithm 1?  \n\n-What do you think is the optimal dependence on the horizon H and how to obtain it? More generally would it be possible to match the lower bound? \n\n-What are the main technical differences/challenges with respect to [17] in linear-kernel MDP?\n\n\nSpecific comments:\n-L49: Can you detail why the bound is too conservative?\n\n-53: maybe here you should explain a bit what is the difference between linear MDP and linear kernel MPD.\n\n-L93, Table 1: For the results, you should be precise with the setting otherwise the table is wrong. The papers [9,12,14] consider episodic MDP with bounded rewards in [0,1] and step-dependent transitions. In this setting, the optimal rate is of order O(H^3S^2A/\\epsilon^2) and O(H^2S^2A/\\epsilon^2) if the transitions are step-independent. [27] consider an additional assumption where the sum of the rewards is equal to 1 (and step-independent transitions) where they obtain a rate of O(S^2A/\\epsilon^2) which they prove to be optimal given this extra assumption. Note that in particular, their algorithm has no guarantees in the setting considered by  [9,12,14].\n\n-L20: It is not clear if the expectation or the variance are well defined for any function V no?\n\n-L126: Do you have any example of MDP that satisfies this assumption except the trivial example of tabular MDP? In particular, an MDP where it is easy to compute the summation in L129.\n\n-L138 Maybe you should describe how the agent interacts with the mdp during the exploration phase. \n\n-L186: Intuitively why do you need to take the maximum over f.  Because the \"exploration driven\nreward function\"  is not enough to explore?\n\n-L206: can you elaborate on this point because the main focus of the paper is to deal with large state space?\n\n-L264: Since \\tiled{\\theta} and \\hat{\\theta} estimate both the same parameter \\theta^* why you need two separate estimators?\n\n-L315:  Thus do you think that the lower bound is sub-optimal in this case?\n\n-L445: For all s?\n\n-L477: Conditioned on the events of lemma A.2 and A.3  do we still have that conditionally the expectation of the random variable in the sum is zero in order to apply Hoeffding inequality?\n\n-L538: there are extra }\n\n-L578: the first equality is inequality.\n\n-L584: can you detail this part, what is E_{s_h}? \n\n-L688: K should be in the sum and you should keep the sum in the middle inequality.\n\n-L740: you also need to choose \\alpha such that the probabilities are in (0,1).\n\n-L745: bound on the cardinal is missing in the statement since taking for \\cM a singleton is sufficient. You mean for all M\\leq ... there exits ...\n\n-L774: x and x' independent.\n\n-L788: Ok you can in fact invoke the chain rule here and you do not have to consider a deterministic algorithm. P_\\theta(Y_k) and E_{Y_k} are not defined.\n\n-L811: could you define clearly \\hat{\\theta}", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is a theoretical paper without direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "B8j-e0RyQVv", "reviewer": "Reviewer_ja4k", "summary": "This paper studies reward-free model-based reinforcement learning for linear mixture MDPs. This paper devises a new algorithm to calculate a near-optimal policy and proves a lower bound on sample complexity. ", "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": "This papers develops a lower bound specifically for linear MDPs, which matches the upper bound in terms of $\\epsilon$.\n\nThe major concern is that the MDP studied in this paper is time homogeneous, which may be restrictive in many practical cases. Is this homogeneity assumption fundamental to the proposed algorithm? In other words, is it possible to extend the analysis to the case where transition probabilities are different from step to step?\n\nThere are a few typos, such as Page 1 \"the algorithm is given a specific reward function and use the collected data\" where \"use\" should be replaced by \"uses\". \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper focuses on theoretical analysis. It's expected that the paper does not have direct negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides the first analysis of reward free in linear mixture MDPs. I think this is a quite natural complement to the literature of RFE. While the paper is well-executed, I find it hard to identify the technical challenges and why certain technical tools are necessary. This concern was also raised by several reviewers. The authors should explain the challenges specific to this setting and why the paper is not a "simple" combination of techniques available in the literature. Due to the theoretical nature of the paper, I think these are quite important points. In addition, during the discussion, no reviewer was willing to champion the paper, which currently stands in a very borderline position. I decided to vote for rejection due to the lack of clarity on the algorithmic choices and novelty to a field that has seen numerous advances in the last couple of years. 
Decision: Accept (Poster)