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 weightzerr@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( H + dd) 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 (s; (s, {ra]a) and Vi (s; (s; (n)) We define
the optimal value function (Vr ===1 and the optimal vetiu function {Q; as (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) Σiz o a)0; Mean- while, for any V S - [0, 1], i [d] (s.a) a) E S x is computable. For simplicity, let Φ [øi...., Eves @(s'|s (s). Without loss of generality, we assume 10- S B, (1)v(s,)) a)la) I for all V [0, 1] and (s,a) E S
(iss|ssa)) 7 Epes ( a))(")
A. the summation
0- 00 ................................ .01 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 -eearn 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) -eeaea 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) E
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 at 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 1) - 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 p
7: for h 1, 2, .... H. do
8: Take action afF +- TT (s%) and receive sh+11
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% (ii (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_A " (o(s, a, .1), ................................ o(s, a, S(s))) and (sskaaa))l 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)f//; 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 h== 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 &k 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+)))) /l0h
(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//// / 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,21113
(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, + 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, O.)
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) 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, [) 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- 11-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 between 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": "sxrdSOvMU2", "reviewer": "Reviewer_USFu", "summary": "Reward free learning is a recently proposed reinforcement learning (RL) problem which has seen significant attention in the RL community. At the same time, the RL community has begun to devote much attention to obtaining theoretical results for MDPs with linear structure. This works seeks to bridge these two settings, and studies reward free learning in linear MDPs (in particular, the linear mixture MDP setting). They propose and analyze two algorithms based on the UCRL algorithm, and show that they attain sample complexities close to minimax optimal.", "questions": "", "limitations": "", "rating": 6, "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": "Reward free exploration (RFE) is a relatively new problem in the RL community where the goal is for the agent to explore an MDP so that it can derive a near optimal for any reward function. While minimax optimal algorithms now exist for this problem in the tabular setting, less attention has been given to reward free learning in the setting of linear MDPs. This work expands on this literature and studies reward free learning in linear MDPs (in particular, in the linear mixture MDP setting of [1]).\n\nThe authors propose two algorithms, both based on the UCRL algorithm. The first, which relies on Hoeffding bonuses, achieves a sample complexity of O(H^5 d^2/epsilon^2). The second, which relies on Bernstein bonuses, achieves a sample complexity of O(H^4 d (d+H)/epsilon^2). In their original form, neither algorithm is computationally efficient, but the authors propose a computationally efficient version which achieves a slightly worse complexity of O(H^5 d^3/epsilon^2), though it requires that the number of states be finite. In addition, the authors prove a lower bound of \\Omega(H^2 d/epsilon^2) for reward free learning in the linear mixture MDP setting.\n\nPros:\n- Reward free learning and learning in linear MDPs have both been topics of significant recent interest in the RL community but only a handful of works have studied reward free learning in linear MDPs. This work, then, fills a gap in the existing literature and addresses a relevant problem. In particular, it is the first work to study RFE in the linear mixture MDP setting of [1].\n- To my knowledge, this is the first algorithm for RFE in MDPs with some form of linear structure that achieves the minimax bound in terms of the dimensionality. Previous works have only achieved complexity scaling as d^3. As such, this is the state-of-the-art bound for RFE in MDPs with linear structure (though it is important to note that it only achieves this when H >= d).\n- The lower bound is, I believe, the first lower bound for reward-free learning with linear function approximation. \n\nCons:\n- The algorithms proposed are not computationally efficient. While they do present a computationally efficient relaxation, this only applies in the setting where the number of states is finite (i.e. the setting where linear function approximation is not typically necessary), and does not achieve the optimal rates (the computationally efficient versions both have a rate of O(H^5 d^3/\\epsilon^2)).\n- Their best algorithm (UCRL-RFE+) does not hit the optimal dependence on H and only hits the optimal dependence on d in the case when H >= d. While this is the state of the art sample complexity for linear function approximation, it is therefore still not optimal. \n- [2] and [3] should be cited and mentioned. \n\nThis work is certainly a contribution in that it solves an unsolved but timely problem. However, while it improves on the state of the art, it does not hit the optimal rate and is not computationally efficient. As such, I believe it is a borderline accept—it makes a contribution but is not ground-breaking. \n\n\n[1] Ayoub, Alex, et al. \"Model-based reinforcement learning with value-targeted regression.\" International Conference on Machine Learning. PMLR, 2020.\n[2] Agarwal, Alekh, et al. \"Flambe: Structural complexity and representation learning of low rank mdps.\" arXiv preprint arXiv:2006.10814 (2020).\n[3] Qiu, Shuang, et al. \"On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game.\" International Conference on Machine Learning. PMLR, 2021.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss potential societal impact. However, the work is primarily theoretical so it is difficult to determine what negative societal impacts it may have, if any. Limitations are discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "i_d9PKqhMK", "reviewer": "Reviewer_nnra", "summary": "The authors study the problem of reward free exploration in the Linear Mixture MDP model. They propose the UCRL-RFE algorithm and show the number of samples required during the exploration phase is at most of the order of O(H^5d^2epsilon^{-2}). They also develop a \"fast\" version of their algorithm/analysis that shows a rate of O(H^4 d(H+d)epsilon^{-2}). They complement these results with a lower bound showing they are unimprovable in their dependence on d and epsilon in case H \\geq d.\n", "questions": "", "limitations": "", "rating": 6, "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": "First comment, the paper's name is awfully similar to the related work\nThe paper's name is extremely similar to: \"On Reward-Free Reinforcement Learning with Linear Function Approximation\". It may be a good strategy to change the name of the paper (if possible) to better reflect the contents of this work and draw distinctions with previous work.\n\nOriginality\n\nThis is yet another paper treating the problem of reward free exploration in MDPs. The linear approximation model that the authors work with (the MDP linear mixture model) is different from that discussed in previous works in the topic such as the aforementioned paper\u0010. This work different from the reward free approaches to Linear MDPs in that it is a model based algorithm more related to \"Reward-Free Exploration for Reinforcement Learning\".  The results are technically correct but it is unclear if they have any component of unexpected in them.\n\nQuality and clarity\n\nThe paper is well written and structured.\n\nSignificance\n\nThe results probably meet the bar for publication in the conference. The results are not very surprising and the problem studied in this work is an obvious extension of existing results, but it may be worthwhile showcasing them. \n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequate", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hrs"}, "extra_text": {}}, {"review_id": "FWjKtb8BCP", "reviewer": "Reviewer_Zh4L", "summary": "This paper studies the problem of reward-free exploration in linear mixture MDPs. In the reward-free setting, the agent interacts in two stages where it must explore sufficiently without a reward function and then an arbitrary function is revealed that it must now solve without further interaction. Two reward-free algorithms based on UCRL are proposed. Both algorithms aim to reduce uncertainty. The second is an improvement that leverages variance estimates to improve the regret bound in terms of H. A lower bound is proved, but it is not matching.", "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 offers some interesting results in the reward-free setting for linear mixture MDPs, which answer questions about sample complexity for this type of model. It is interesting that one is able to achieve d^2/eps^{-2} in this model (better than other models, but matching what is achievable in the non-reward free setting). The paper is very well-written and easy to understand. The related work also does a good job of distinguishing the work from past work in both reward-free learning and general reinforcement learning with linear function approximation.\n\nI do not have any technical complaints about the paper. It matches assumptions that have been made in the past without imposing more. The analysis seems technically correct from what I can tell and it is grounded in some fairly tried-and-true techniques.\n\nMy primary critique is that the paper does not seem to introduce any technically novel analysis, approach, model, or problem setting. It seems like a relatively simple combination of existing ideas, which is not inherently bad, but it also yielded an unsurprising conclusion. By now, there are many existing papers that have already shown that essentially applying standard online algorithms with good exploration is a good strategy for reward-free learning. So, while I think this is a good paper that answers some questions that definitely should be answered, the significance and novelty of the contribution seems to be lacking.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0TYLzDQ5Hv", "reviewer": "Reviewer_6DWQ", "summary": "This paper considers the Reward Free Reinforcement Learning for the linear mixture MDP assumption. Their (model-based) UCRL-RFE achieves $\\tilde{O}(H^5d^2\\epsilon^{-2})$ complexity and can be further improved to $\\tilde{O}(H^4d(H+d)\\epsilon^{-2})$ with a Bernstein-type design. In addition, it also provides a lower bound for reward-free RL with $\\Omega(H^2d\\epsilon^{-2})$ in the linear mixture MDP setting.", "questions": "", "limitations": "", "rating": 6, "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": "In general, this paper provides some nice contributions to the reward-free RL with the best finite sample guarantee of order $\\tilde{O}(H^4d(H+d)\\epsilon^{-2})$. However, there are a few reasons that make the current version slightly below the acceptance bar in my opinion. \n\n The lower bound obtained in Theorem 6.1 is not tight, which makes the discussion of matching parameter dependence vague. Concretely, it is known that reward-free learning is harder than the standard reward-specific task. For the linear mixture MDP, the reward-specific task is known to have the regret lower bound $\\Omega(dH\\sqrt{T})$ (ZHOU, D., GU, Q. and SZEPESVARI, C. COLT 21). This will be translated into $\\Omega(H^3d^2\\epsilon^{-2})$ in the PAC sense. Therefore, the tight lower bound should be of order at least $d^2$.\n\nHence, the claim \"Our upper bound matches the lower bound in terms of the dependence on ε and the dependence on d if $H\\geq d$\" is vague since the dependence on $d$ should at least be $d^2$ instead of $d$. Also, the way to do the claim is lacking rigor since $\\tilde{O}(H^4d(H+d)\\epsilon^{-2})\\geq \\tilde{O}(H^4d^2\\epsilon^{-2})$, the dependence is always quadratic. Such a weak lower bound diminishes the contribution of UCRL-RFE since it is not clear how far your upper bound is from the \"true\" statistical limits of the current problem. Indeed, even in the tabular offline RL, the PAC bound for outputting a $\\epsilon$-optimal policy for the reward-free task has a lower bound $\\Omega(H^2S/d_m\\epsilon^{2})$ (which translates to quadratic dependence in $S$ https://arxiv.org/pdf/2105.06029.pdf). Understanding the correct (statistical) rate for the setting is important.\n\nLastly, your remark 3.2 states \"linear mixture MDPs do not need the reward function $r$ to be linear, which makes our algorithms more general.\" Indeed, it is commonly known that for linear MDP and linear mixture MDP, one does not contain the other. Therefore, I am not sure what the word \"general\" means here.\n\nOverall, the paper provides a nice perspective and by further modification, the paper's quality could increase. Therefore, I choose the weak reject.\n\n  \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 Hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes two algorithms (corresponding to Bernstein and Hoeffding bonuses) for reward-free exploration in linear mixture MDPs and analyzes their sample complexity. The authors also provide a lower bound for this setting. The proposed algorithms involve a computationally difficult subproblem, which is replaced by an LP relaxation in the implementation.
Overall, the results and techniques are not very surprising, leaving most reviewers ambivalent. However, given that the paper is executed well and fills a gap in the literature, I recommend acceptance.

Decision: Accept (Poster)