Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
Authors: Xiaoyu Chen
Jiachen Hu
Lin Yang
Liwei Wang
Venue: ICLR 2022 Spotlight (2022)
Keywords: reward-free exploration
model-based reinforcement learning
learning theory

Abstract: Although model-based reinforcement learning (RL) approaches are considered more sample efficient, existing algorithms are usually relying on sophisticated planning algorithm to couple tightly with the model-learning procedure. Hence the learned models may lack the ability of being re-used with more specialized planners. In this paper we address this issue and provide approaches to learn an RL model efficiently without the guidance of a reward signal. In particular, we take a plug-in solver approach, where we focus on learning a model in the exploration phase and demand that \emph{any planning algorithm} on the learned model can give a near-optimal policy. Specicially, we focus on the linear mixture MDP setting, where the probability transition matrix is a (unknown) convex combination of a set of existing models. We show that, by establishing a novel exploration algorithm, the plug-in approach learns a model by taking $\tilde{O}(d^2H^3/\epsilon^2)$ interactions with the environment and \emph{any} $\epsilon$-optimal planner on the model gives an $O(\epsilon)$-optimal policy on the original model. This sample complexity matches lower bounds for non-plug-in approaches and is \emph{statistically optimal}. We achieve this result by leveraging a careful maximum total-variance bound using Bernstein inequality and properties specified to linear mixture MDP.

Published as a conference paper at ICLR 2022
NEAR-OPTIMAL REWARD-FREE EXPLORATION FOR LINEAR MIXTURE MDPs WITH PLUG-IN SOLVER
Xiaoyu Chen & Jiachen Hu
Lin F. Yang
Key Laboratory of Machine Perception, MOE, School of Artificial Intelligence, Peking University {cxy30, NickH)@pku. fet.kku.edu.cc
Electrical and Computer Engineering Department, University of California, Los Angeles
1 linyangeee. vclaa.ddo
Liwei Wang"
Key Laboratory of Machine Perception, MOE, School of Artificial Intelligence, Peking University
International Center for Machine Learning Research, Peking University wanglwê cis pku. eduu
ABSTRACT
Although model-based reinforcement learning (RL) approaches are considered more sample efficient, existing algorithms usually relying on sophisticated planning algorithm to couple tightly with the model-learning procedure. Hence the learned models may lack the ability of being re-used with more specialized planners. In this paper we address this issue and provide approaches to learn an RL model efficiently without the guidance of reward signal. In partieular, we take a plug-in solver approach, where we focus on learning a model in the explo- ration phase and demand that any planning algorithm on the learned model can give a near-optimal policy. specifically, we focus on the linear mixture MDP set- ting, where the probability transition matrix is a (unknown) convex combination of a set of existing models. We show that, by establishing novel exploration algo- rithm, the plug-in approach learns model by taking Ó H// /e²) episodes with the environment and any e-optimal planner on the model gives an O(e) (optomal policy on the original model. This sample complexity matches our lower bound for non-plug-in approaches and is statistically optimal. We achieve this result by leveraging a careful maximum and properties specified to linear mixture MDPs.
bound using Bernstein incquality
INTRODUCTION
In reinforcement learning, an agent repeatedly interacts with the unknown environment in order to maximize the cumulative reward. To achieve this goal, RL algorithm must be equipped with effective exploration mechanisms to learn the unknown environment and find a near-optimal policy. Efficient exploration is critical to the success of reinforcement learning algorithms, which has been widely investigated from both the empirical and the theoretical perspectives (e.g. Stadie et al. (2015); Pathak et al. (2017): 7): Azar et al. (0117): Jin et al. 2018)). Model-based RL is one of the important approaches to solve for the RL environment. In model-based RI., the agent learns the model of the environment and then performs planning in the estimated model. It has been widely applied in many RL scenarios, including both online setting (Kaiser et al. 2019 Luo et al. 2019 Azar al. 2017) and offline setting (Yu et al., 2020; Kidambi et al. (020). is also believed that model- based RL is significantly more sample-efficient than model-free RL, which has been justified by many recent empirical results (e.g. Kaiser et al. (2019): | Wang et al. (2019). Though the theoretical model-based learning in small scale problems has been studied extensively (Azar et al., 2017 Zhou
et al. 2020a Jin et al. 2020a). it is still far from complete, especially with the presence of a function approximator.
"Corresponding author.

---

Published as a conference paper at ICLR 2022
As important implication of model-basee approaches, the power of plug-in approach have been studied in several works (Cui & Yang 2020 Agarwal et al. 2020). The idea of plug-in approach is rather simple: We construct empiniaal Markov Decision Process (MDP) using maximum like- lihood estimate, then return the (approximate) optimal policy with efficient planning algorithm in this empirical model. The significance of plug-in approaches is two-folded. For one thing, it pre- serves an empirical model that keeps the value of the policies, which is of independent interests. For another, the empirical model can be used for any down-stream tasks, which makes the application much more flexible. It is shown that the plug-in in approach achieves the minimax sample complexity to compute the c-optimal policies with a generative model in the tabular (Agarwal et al. 2020) and linear settings (Cui& & Yang 2020).
In this paper, we aim to understand the power of plug-in approach in the reward-free exploration with linear function approximation. We study the linear mixture MDPs, where the transition probability kernel is a linear mixture of a number of basis kernels (Ayoub et al.) 2020; Zhou et al.) (b). We first build an empirical model with an estimation of the transition dynamics in the exploration phase, and then find near-optimal policy by planning with the empirical model via arbitrary plug-in solver in the planning phase. Our setting is different from the reward- -ree exploration with linear function approximation without plug-in in model (Wang et al.] [2000] Zanette et al., (020b)) in which the agent can directly observe all history samples and design specialized model-free algorithm in the planning phase.
Our results show that the plug-in approach can achieve near-optimal sample complexity in the reward-fire setting. In particular, we proposed a statistically efficient algorithm for reward-free exploration. Our algorithm samples O(d= He2)²) trajectories during the exploration phase, which suffices obtain O(t)ooiiimal policies for an arbitrary reward function with an e-optimal pluging solver in the planning phase. Here d is the feature dimension, and H is the planning horizon. Fur- thermore, with a more refined trajectory-wise uncertainty estimation, we further improve the sample complexity bound Ô (dFHH/2²) in the regime where > H and S H/Vd. This matches our lower bound (2 for reward-free exploration in linear mixture MDPs, which indicates that our upper bound is near-optimal except for logarithmic factors. To the best of our knowledge, this is the first work that obtains minimax sample complexity bounds for the plug-in approach in reward-free exploration with linear function approximation.
2 RELATED WORK
RL with Linear Function Approximation
Reinforcement learning with linear function approxi-
mation has been widely studied in the recent few years (e.g. g. Jiang al. (2017); Yang & Wang (2019
2020); et al. (2000b); Modi et al. (2020): Du et al. (2019) 1011; Zanette et al. (020aa): Cai et al. (0220):
Ayoub et al. (2020); Weisz et al. (2021): Zhou al. (2020a b)). The linear mixture MDPs model
studied in our work assumes the transition probability function is parameterized as a linear func-
tion of given feature mapping over state-action cereeccctioonnexxtee settionnneet-staae next-state triple (Ayoub et al. 2020 Zhou al.
2020b]a) a). Based on the Bernstein inequality for vector-valued martingales, Zhou et al. posed an efficient algorithm that obtains minimax regret in the regime where d > H. Besides linear mixture MDPs, linear MDPs is another category of RL with linear function approximation, which assumes both the transition probability function and reward function are parameterized as linear function of a given feature mapping over state-action pairs. The algorithms with best regret bounds were proposed by Din et al. (2020b) Yang Wang (2020), which studied model-free algorithm and model-based algorithm respectively. The minimax regret bound for linear MDPs is still unclear.
(020a)) pro-
Reward-Free Reinforvement Learning In contrast to the standard RL setting, reward-free re- inforcement learning separates the exploration problem and the planning problem, which allows one to handle them in a theoretically principled way. For tabular setting, reward-free free reinforcement learning has been well-exploited in many previous results (Tin et al.) 2020a, Kauřmann et al.) 2021
Ménard et al., 2020 Zhang et al., 2020 202 lb; Wu et al., 202 Bai & Jin 2020 Liu et al. 202 where the minimax rate is obtained by Ménard et al. (2020). For reward-fres exploration with lin- ear function approximation, Wang et al. (2020) proposed the first efficient algorithm that obtains (d H /c²) sample complexity for linear MDPs However, their algorithm is model-free in nature and cannot guarantee good performance with any plug-in solver. Further, QQu et al. (202T) proposed the first provably efficient reward-free algorithm with kernel and neural function approximation.
2

---

Published as a conference paper at ICLR 2022
We also noticed that there is concurrent work which also studied reward-free exploration for linear mixture MDPs (Zhang et al. 2021a). Compared with their results, we focus on the setting of the reward-free exploration with plug-im in solver, which covers the standard reward-free setting studied in the previous results. Furthermore, our sample complexity bounds are tighter than theirs by a factor of # The above differences introduce new challenges in both the algorithmic design and the complexity analysis in this work, which makes our algorithms much more complicated than theirs. Besides, our lower bound is tighter than theirs in the dependence on d.
Plug-in Approach The plug-in in approach has been studied in tabular/linear case in restrictive set- tings. E.g., Agarwal et al. (2020) and Cui & Yangl (2020) studied the standard plug-in approach with a generative model, where the algorithm is allowed to query the outcome of any state action pair from an oracle. They showed the plug-in approach also achieved the minimax optimal sample complexity to find an e-optimal policy in both tabular MDPs and linear MDPs. The reward-free al- gorithms proposed jyj al. (2020a) are model-based in nature, thus can be regarded as solution in the plug-in solver setting. However, their algorithms are restricted to the tabular case and cannot be applied to the setting with linear function approximation.
3. PRELIMINARIES
3.1 EPISODIC MDPS
We consider the setting of episodic Markov decision processes (MDPs), which can be denoted by six-tuple (S, A, P, R. H. H.),, where S is the set of states, A is the action set, P is the transition probability matrix so that Pa (-1s, a) gives the distribution over states if action a is taken on state at step h. RA (s, a) is the deterministic reward function of taking action on state with support [0, 1] in step h, H is the number of steps in each episode, and y is the distribution of the initial state.
In episode k, the agent starts from an initial state $k,1 sampled from the distribution v. At each step E [H], the agent observes the current state 8g.4 E S, takes action dg E A, receives reward (5k,b, b Ak and transits to state $t,4+1 with probability Ps, (sk,At+11s.. as,A). The episode ends when # is reached.
A deterministic policy a is a collection of H policy functions {mA S + A]EE[H] We use to denote the set all deterministic policies. For a specific reward function R, we use VÆ S x R + R to denote the value function at step h under policy w.r.. ward R, which gives the expected sum of the remaining rewards received under policy v starting from Sh = =s ie. ingly, we define (T,,,, R) the expected Q-value function at step h: QT(s,,, E R at) + D Rsw The (sW)) 8/h s, an = a.
V (s, R) E E (sw, Th (SW)) Sh = =, Accord-
We use R to denote the optimal policy w.r.t. reward R, and we use Vi R) and Q%(,, R) to denote the optimal value and Q-function under optimal policy Fं at step We say policy x is c-optimal w.r.t. reward R E
Σm_ R3, (Sh, an)) 2 E E
RA (s)) Tī
For the convenience of explanation, we assume the agent always starts from the same state $1 in each episode. straightforward to extend to the case with stochastic initialization, by adding a initial state 80 with no rewards and only one action dg. and the transition probability of (so, on) is the initial distribution μ. We use Pý (s, a, R) as a shorthand of Σ.- Pa(s'1a, Vs', R)..
3.2 LINEAR MIXTURE MDPs
We study a special class of MDPs called linear mixture MDPs, where the transition probability kernel a linear mixture of a number of basis kernels (Ayoub et al. 2020 Zhou et al. 20206 a This model is defined follows in the previous literature.
When transformed to the time-homogeneous MDPs setting studied in Zhang et al. 2021a), our algorithms achieve sample complexity bounds Ö(d H3 (e) and Ō(( H² + //+))""), respectively.
3

---

Published as a conference paper at ICLR 2022
Definition 1. (Ayoub et al. 2020) Let ((s, a. a. : SxAxS - Rd be a feature mapping satisfying that for any foudctiuu V :SS [o. 1] and any tuple (s, a) E x A, we have lōv(s, a)llı S 1, where (v a) E''ss Φ (s, a' V (s'). An MDP is called linear mixture MDP if there exists a parameter vector On, Ra with ||0, ll S B for a constant B and a feature vector o(.,;:). such that (u (ss|ssa) = 0 ő(s, a, s for any state-action-ee and step h E [
triplet (s, a') E S Ax
3.3 REWARD-FREE REINFORCEMENT LEARNING
We study the problem of reward-free exploration with plug-in solver. Our setting is different from the reward-free free exploration setting studied in the previous literature. Formally, there are two phases in this setting: exploration phase and planning phase.
During the exploration phase, the agent interacts with the environment for K episodes. In episode k the agent chooses a policy Ta which induces a trajectory. The agent observes the states and actions $,,1, 0g,1,"' H, Ok.H usual, but does not observe any rewards. After K episodes, the agent calculates the estimated model {Ph 0% @) which will be used in the planning phase to calculate the optimal policy.
During the planning phase, the agent is no longer allowed to interact with the MDP. Also, it cannot directly observe the history samples obtained in the exploration phase. Instead, the agent is given set of reward function {Ra (eje)) where RG S x A + [0. 1] is the deterministic reward in step h. For notation convenience, we occasionally use R as a shorthand of (Ra)e during the analysis.
We define V/..P (s, R) as the value function of transition P and reward R, i.e. V7. (s, R) =
E Rn (sw, The (sH)) 8h = = 8,
In the planning phase, the agent calculates the optimal policy मæ with respect to the reward function R in the estimated model P using any Copt -optmmal model-based solver. That is, the returned policy in satisfies: V.. (s1, R) A...PP P (s1. R) S Capt-
The agent's goal is to output an accurate model estimation 15 after the exploration phase, so that the policy म calculated in planning phase can be e + oppt-ottimal w.r.t. any reward function R. Compared with the reward- wward--fee setting studied in the previous literature (Jin et al. 2020al Wang
et al. 2020 Ménard et al. 2020 Kaufmann et af. (021). the main difference is that we require that the algorithm maintains a model estimation instead of all the history samples after the exploration phase, and can use any model-based solver to calculate the near-optimal policy in the planning phase.
4 REWARD-FREE RL WITH PLUG-IN SOLVER
4.1 ALGORITHM
The exploration phase of the algorithm is presented in Algorithm | Recall that for a given value function Vk,b+I, we have PA Ve,,41 ax.4)) = 0% Φv.. N41 (sk,h; 4k,n) for any k. h. Therefore, V (5k,A+1) and VV a+1 (Sk,A, (g,h) can be regarded as the stochastic reward and the linear fea- ture of a linear bandits problem with linear parameter On. We employ the standard least-square regression to learn the underlying parameter fr. In each episode, we first update the estimation 0 based history samples till episode k --1 1. We define the auxiliary rewards RA, to guide explo- ration. We calculate the optimistic Q-function using the parameter estimation Ōz. and then execute the greedy policy with respect to the updated Q-function to collect new samples.
The main problem is how to define the exploration-driven reward RE,n a), which measures the uncertainty for state-action pair (s, a) at the current step. In the setting of linear mixture MDPs, the linear feature dy (s, a) is a function of both state-action pair (s, a) and the next-step value func- tion V. This is not big deal in the standard exploration setting (Ayoub et al. 2020 Zhou et al.) 2020a). However, in the reward-free setting, since the reward function is not given beforehand, we need to upper bound the estimation error of value functions for any possible rewards. To tackle
4

---

Published as a conference paper at ICLR 2022
Algorithm Reward-free Exploration: Exploration Phase
Input: Failure probability ò > 0 and target accuracy e X B-2, < H / (
VAB, V. V (V: 10, H]
for episode k = 1, 2, ... K do
Qa, (..)) = 0, (
5:
for step h = H. H - 1, ,
Ak, + Ek=1 1 (e. (e,h) +
0u, - (Ap,A) E Pi.n (81 0t W.
VEA+1,,, t arg max EE, O(s, a, s') (V'V (1)))- As,
(8, + E. a, 8 8),
Vs,a
(s, -- 8v (r.n (s, a) (AR,a) 0R.h (8, a), V8,a
Define the exploration-driver reward function (s,h a) = Qs, + min { (Ev Ø(s. a.s.a,s')e s')Ve,n+1(s')) + (s, a) + as, Ve,A(s) &- max.EA Qk, a). (s) = arg ma (s,n(s,a)
Vs,
end for for step = 1, 2, H do
15:
Take action ax,t = T T (sk.k) and observe sk,4+1 Ps ok,h end for end for
Find Pa. such that the transition Pa(-1.-)- 0% o(.,,-) is well-defined and | 6K Asaa
B for h E [H] 20: Output: {Pr)
maxvey By (s, T)T (As,a) Φv (s a) measure of the maximum uncertainty for the state-action pair (s, where V (V S - [0. H) the set of all possible value functions, and АR is the summation of all the history sam- ples {st,ns ar 81,441 ) with feature Φe.n (St, (r,n.) = arg maxør (s, episode, we define (s, a) = (x, a) maxvev Bllov a)llAz) where Rx, a) is exploration-driven reward used to guide exploration, and uk.A (s, a) is the additional bonus term which helps to guarantee that Qs,n a) is an optimistic estimation. Finally, the algorithm re- turns the model estimation {Paha that is well defined (i.c. Σ. Ph(s'ss,a) 1, Pr("ss)) 2 0, Vs, s'), and satisfy the constraints 00, 0x., AN, S.B.
this problem,
maxvev (s,
In each
4.2 IMPLEMENTATION DETAILS
Algorithm [ involves two optimization problems in line 8 and line 19. These problems can be formulated the standard convex optimization problem with slight modification. Specifically, the optimization problem in line 8 of Algorithm [ can be formulated in the following way:
max Σ 6(s a, s')(('))
s.t. 0 V(s) HHYSES
(1)
(Av.))
In general, solving this optimization problem is hard. For the case of finite state space (S < oc), a recent work of Zhang et al. (202 relaxed the problem to the following linear programming problem:
Σ 1/2 t (s, a)r//
s.l. ||f] H,
where (ss (6 (s, a, Si). .... (s. and = (Si) ... (Siss)) As dis- cussed in Zhang al. (2021a), the sample complexity will be worse by factor of d if we solve the
5

---

Published as a conference paper at ICLR 2022
linear programming problem approximation. For the case where the state apace is infinite, can use state aggregation methods (Ren & Krogh 2002, Singh et al. 1995) to reduce the infinite state space to finite state space and apply the approximation approaches to solve it.
The optimization problem in line 19 of Algorithm is find parameter 0, satisfying several con- straints. For the case where the state space is finite, we can solve this problem the following way:
min 10. 0Kc 8n
s.l. E ((=, a(s, 2,V
Ax.
The above problem can be regarded as a quadratic programming problem and can be solved ef- ficiently by the standard optimization methods. By Lemma 4 we know that the true parameter 0g satisfies ||0, - On AN, $ 3 with high probability. Therefore, the solution 0n satisfies the constraint 0, 0K,,
Axa S B with high probability.
For the case where the state space is infinite, we can also solve the above problem using state ag- gregation methods. particular, the linear mixture MDP model can regarded as a linear com- bination of several base MDP models (i.e. 6(8, 8') (Pi (s'1s, (,lls,a) a), P2(8'18, a), Pa(8'(8, ((.((ssa))) a)) where (s'lss, a) is the transition probability of certain MDP model), then we can formulate the optimization problem in the following way:
min 0n 0K, 8,
s.t. 0 = 1,0
AN.
which can also be solved efficiently in the case of infinite state space.
4.3 REGRET
Theorem 1. With probability at least 5, after collecting K K= (+))) trajectories, Algo- rithm returns transition model P. then for any given reward in the planning phase, policy returned by any opptootimall plug-in solver on (S, A, P, R. H, is (npt+ for the true MDP, (S, A, P, R, v).
We also propose lower bound for reward-free exploration Appendix C cates that (2d2 H H²/ /e²) episodes are necessary to find an e-optimal policy with constant probability. This lower bound is achieved by connecting the sample complexity lower bound with the regret lower bound of certain constructed learning algorithms in the standard online exploration setting. Compared with this bound, our result matches the lower bound w.r.t. the dimension d and the preci- sion except for logarithmic factors.
Our lower bound indi-
There is also a recent paper Wang et al. (2000) studying reward-free exploration the setting of linear MDPs. Their sample complexity O H f thus our bound better than theirs by factor of 2 Though the setting is different, find that parameter choice and the more refined analysis is applicable to their setting, which can help to further improve their bound by a factor of H² Please see Appendix D for the detailed discussion.
5 IMPROVING THE DEPENDENCE ON H
In this section, we close the gap H with maximum total-variance bound using Bernstein in- equality. In the previous results studying regert minimization online RL setting (Azar et al.) 2017 Zhou et al. 2020a Wu et al.] 2021b), one commonly-used approach to obtain the minimax rate is to upper bound the regret using the total variance of the value function by the Bernstein's concentration inequalities, and finally bound the summation of the one-step transition variance by the law of total variance (Lattimore & Hutter 2012 Azar et al.) 2013 2017). However, the situa- tion becomes much more complicated in the reward-fiee free setting with linear function approximation. Recall that V2 Vg, (s') defined in Line 9 of Algorithm| | is the next-step value function that max- imizes the uncertainty [ (8, a)ll for state-action parr (s, a). One naive approach is to still use

---

Published as a conference paper at ICLR 2022
maxy (,, the uncertainty measure for (s, a) and upper bound the error rate by the summation of the one-step transition variance of Vk.4+1,5., a. (8'). However, we can not upper bound the variance summation of aa,. (s') in H steps by O similarly by the law of total variance, since x...............l....... and transition dynamics. To tackle the above problem, we need to define the exploration-driven reward and the confidence bonus for each state-action pair in more refined way. Our basic idea is to carefully measure the expected total uncertainty along the whole trajectories w.r.t. each MDPs in confidence set. will explain the detail in the following subsections.
not the value functions induced from the same policy
5.1 ALGORITHM
Algorithm Reward-free Exploration: Exploration Phase
Input: Failure probability 5 > 0 and target accuracy c > 0
X < B-2, 3 +- 16 / + K H² (dx)) log (gg32k22/0)) + VBB
3 /
+ K / log (32K + VBB
3 + 16H2 / (ogg(1 + K H/ ((A)) (32 + VBB
5: Set Ai,A,6 +- AI, 0,,A,A + 0 for k = 1, E [M] 1,2,3,4,5
Set Mi, be the set containing all the 0r that makes Ph. well-defined, [H]. for episode k = 1,2 ... K do Calculate nh. 0x. R2 arg max n.O, EUR.AR V.. for step = 2... do
V (81, R), where V is defined in Eqn
10:
Take action according to the policy Tueh and observe 88,441 Pa ag.n) end for
for step 1, 2, ... do Update (A, (A, 1i using Eqn 67
68
71
72 and 77
Update the model estimation k+1. Pi=1
(=1 using Equ 69
70
73
74 and 78
15:
Add the constraints (Eqn
3) to the confidence set Ur and obtain U
end for end for Output: { -
= 0k (k)((r)))
Our algorithm is described in Algorithm At a high level, A maintains high-confidence set Us,, for the real parameter 02 each episode k, and calculates an optimistic value function
V... ',1 (s1, (s1, R) for any reward function R and transition Ph. 0% ø with 0, E Uye Roughly speak- ing, the value function V2.1 (81, R) measures the expected uncertainty along the whole trajectory induced by policy π in the MDP with transition P and reward R. To collect more "informative" samples and minimize the worst-case uncertainty over all possible transition dynamics and reward function, we calculate Tek = arg max, maxi, a V (s1, R), and execute the policy Fe to collect more data episode k. To ensure that the model estimation 0x+1,h is close to the true model 8% w.r.t. features Φv (s, a) of different value functions V. use the samples collected so far cal- culate five model estimation {5 and the corresponding constraints at the end of the episode k. Each constraint is an ellipsoid in the parameter space centered at the parameter estimation 0g with covariance matrix Ai,,, and radius 3,, i.e.
||0, &.A.AlllAa. S Bi.
We update Uk++1, by adding these constraints the the confidence set Ui
The remaining problems are how to define the value function V. (s1, R) that represents the ex- pected uncertainty for policy म, transition P and reward R, and how to update the model estimation Ock and the confidence set Mk
7

---

Published as a conference paper at ICLR 2022
Uncertainty Measure Instead of using maxy [s, (s,a))la, to measure the maximum uncer- tainty for the state-action pair (s, a) in Algorithm we separately define the uncertainty along the trajectories induced by different policy reward function R and transition dynamics Ps. 0 Φ. Specifically, Recall that ( / (s, R) is the value function of policy и in the MDP model with transi- tion P and reward R. We define the following exploration-driven reward for transition P. reward R and policy n.
T.P. u (1, R) R) 3 ( [ s' R)
(4)
(AL
S, we define the corresponding value function recursively from step H + 1 to step 1. That is,
Suppose T. (s, R) Vs Vs k,
Ven k.h (s, It) min { " (1 (s) + PA P.VV..P n. (6), R), (+),
Vo ES
(5)
V (8, R) can be regarded as the expected uncertainty along the trajectories induced by policy m kih
for the value function 1/ R). In each episode ks we wish to collect samples by executing the V.
policy π that maximizes the uncertainty measure mäxgeut, R. k,1 (8, R). However, the definition
of V...P( (s, R) explicitly depends on the real transition dynamics P. which is unknown to the agent. k.1
To solve this problem, we construct an optimistic estimation V-n.Pt k,h (s, R). We define V= k,h (s, R)
from step H 1 to step 1 recursively. Suppose V.n.P k, (s, R) 0. We calculate
R.P U 2 a, R) =
Σ (' ( (5',R) R)
(6)
(A2ma)
R) (s kih
min {
n.P " (s, (s),
T.P u2 (s, (s). R) PAV (s,
P.P where U2 is the confidence bonus which ensures that the optimism VATA (s, R) 2 V.r (s, R) holds with high probability. After calculating V.a.P (s, R), we take maximization over all 0. E Uk. arg max, max n. Ve, (s1, Rt.. We execute
and reward function Rt and calculate to collect samples in episode k.
Weighted Ridge Regression and Confidence Set In Algorithm 2 we maintain five model estima- tion (0r,, ) and add five constraints to the confidence set h in each episode. These constraints can be roughly classified into three categories. The first and the third constraints are applied to en- sure that Pk. Vr.. (s, a, R.) is accurate estimation of PR. A V. (s, a, R) for any reward function R and Pk.h = 8% satisfying 0g. E Uk.k. while the second and the forth constraints are used to guarantee that PA., V.r (s, a, R) is accurate estimation of PA V...P ( (s, a, R) for any reward function and Pr.n = 0 satisfying Ōz,1 E Us... The last constraint is applied due to technical issue and will be explained Appendix B.2 In this subsection, we introduce the basic idea behind the construction of the first and the third constraints. The second and the forth constraints follow the same idea but consider the different value function VIT (s. R). The formal definition of the parameters
and the constraints are deferred to Appendix B.2
For notation convenience, we use (s) as shorthand of V. PP (s, RR) in this part. The con- struction of our confidence sets inspired by recent algorithm called UCRL-VTR" proposed by Zhou al. (2020a). Recall that we use (sk,h, (g.h) to denote the state-action pair that the agent
8

---

Published as a conference paper at ICLR 2022
encounters step h in episode k. We use the following ridge regression estimator to calculate the corresponding 01, in episode k:
11, arg min 2101 2 + E [
@Ve (sL, (1 a(,)) - (a1),,.,41...B/0....a (8)
BER
where T.x. max { [f2 /d, [V k.
ak.) + EI } is optimistic estimation of the VA ( (k.h) = Pa (VE,6+1(5)) Pa PAV (k.t))
one-step transition variance:
In the definition of L VR,.V (Sk, (k,a) is an empirical estimation for the variance Va Va- i ak,,), and EL ELA bonus defined in Eqn. 61 which ensures that k is an optimistic estimation of Vv Vk. (SK, ag,A). One technical issue here is how to estimate the variance V Vish+1 (Sk,h, ok,A). Recall that by definition,
V R.V.K+1 (Sk,br an,b Pn
Pr Vi 1 aR,a) [P + I
(9)
=0% OvR (Sk,h, (k,)) - 10 ov
(10)
mn (Sk.), We use V (sk,, ak.h) Oo (Sk,h,
as our variance estimator Va ( (k,)), where ONn E Ur, is the parameter which maximizes the value Vil (s1, R) in episode k. To ensure that VR, VE,A+1 (SK,,, ()) is accurate estimator, main- tain another parameter estimation 03,4. using history samples w.r.t. the feature ΦVZ (8 (g,n)=
03,4,h = arg min 2llOlN GERR
1
Oo OVe (sE, - Li, V ($r.++))
(1I)
After calculating 0 01, and 0g we add the first and the third constraints (Eqn. 3 to the confidence set Uke where ALA and Ag,k, the corresponding covariance matrix of all history samples, i.e. ALA Et-l - T (Sc, dt,)) (st, (c,)) and A3, E ΦVZ (Se,s, do, Vi 1,tt1
(,,)).
5.2 REGRET
We present the regret upper bound of Algorithm Zn Theorem 2 In the regime where 2 H and < H/Vd, we can obtain (d H/3 /22) sample complexity upper bound, which matches the sample complexity lower bound except logarithmic factors.
Theorem 2. With probability at least 1 - 8, after collecting K = KŌŌ (
(fIHHaa + 1
trajectories, Algorithm 2 returns transition model Pk, then for any given reward in the planning phase, policy returned by any opptimt plug-in solver (S, Pk, R, H,v) is Ole + copt) optimal for the true MDP, (S, A, V.
CONCLUSION
This paper studies the sample complexity of plug-in solver approach for reward-free reinforcement learning. We propose statistically efficient algorithm with sample complexity Ô [d / We further refine the complexity by providing an another algorithm with sample complexity Ô (d H²/22) in certain parameter regimes. To the best of our knowledge, this is the first mini- max sample complexity bound for reward-free -errrdffree exploration with linear function approximation. As a side note, our approaches provide an efficient learning method for the RL model representation, which preserves values and policies for any other down-stream tasks (specified different rewards).
Our sample complexity bound matches the lower bound only when > H and H/Vd. It is unclear whether minimax rate could be obtained a more broader parameter regimes. We plan to address this issue in the future work.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGMENTS
Liwei Wang was supported by National Key R&D Program of China (2018YFB1402600) Ex- ploratory Research Project of Zhejiang Lab (No. 2022RC0AN02), BJNSF (L172037), Project 2020BD006 supported by PKUBaidu Fund.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pp. 2312-2320, 2011.
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with gener- ative model minimax optimal. In Conference on Learning Theory, pp. 67-83, PMLR, 2020.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-474 PMLR, 2020.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax pac bounds the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3); 325-349, 2013.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference Machine Learning, pp. 263 272. PMLR, 2017.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In Inter- national Conference Machine Learning, pp. 551-560. PMLR, 2020.
Qi Cai, Zhuoran Yang. Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, pp. 1283-1294, PMLR, 2020.
Qiwen Cui and Lin F Yang. Is plug-in solver sample-efficient for feature-based reinforcement learn- ing? arXiv preprint arXiv:2010.05673, 2020.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is a good representation sufficient
for sample efficient reinforcement learning? arXiv preprint arXiv:1910.03011 2019.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are pac-leamable. In International Conference on Machine Learning, pp. 1704-1713. PMLR, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? arXiv preprint 1rXiv:1807.03765. 2018
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pp. 4870-4879.
PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143.
PMLR, 2020b.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, al. Model-based reinforcement learning for atari. arXiv preprint arXiv: wwxivv/903.0000 1903.00374, 2019.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pp. 865- 891. PMLR, 2021.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims, Morel: Model- based offline reinforcement learning. arXiv preprint arXiv:2005.05951 2020.
10

---

Published as a conference paper at ICLR 2022
Tor Lattimore and Mareus Hutter. Pac bounds for discounted mdps. In International Conference Algorithmic Learning Theory, pp. 220-334. Springer, 2012.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforce- ment learning with self-play. In International Conference on Machine Learning, pp. 7001-7010. PMLR, 2021.
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorithmic framework for model-based deep reinforcement learning with theoretical guarantees. In Intema- tional Conference on Learning Representations, 2019. URL
nett/
Rorum?id=RJJ11222 122R5XX
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. arXiv preprint vrXv:2007.13442, 2020.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2020. PMLR, 2020.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, pp. 2778-2787. PMLR, 2017.
Shuang Qiu, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. On reward-free rl with kernel and neural function approximations: Single-agent mdp and markov game. In International Conference Machine Learning, pp. 8737-8747. PMLR, 2021.
Zhiyuan Ren and Bruce H Krogh. State aggregation in markov decision processes. In Proceedings of the 41st IEEE Conference on Decision and Control, 2002., volume 4, pp. 3819-3824. IEEE, 2002.
Satinder P Singh, Tommi Jaakkola, and Michael Jordan. Reinforcement learning with soft state aggregation. Advances in neural information processing systems, pp. 361-368, 1995.
Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint arXiv: 2015.
Ruosong Wang, Simon S Du, Lin F Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear function approximation. arXiv preprint wxXiv:2006.11274 2020.
Tingwu Wang, Xuchan Bao, Ignasi Clavera, Jerrick Hoang, Yeming Wen, Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel, and Jimmy Ba. Benchmarking model-based reinforce- ment learning. arXiv preprint 1 2019.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions. In Algorithmic Learning Theory, pp. 1237-1264. PMLR, 2021.
Jingfeng Wu, Vladimir Braverman, and Lin Yang. Gap-dependent unsupervised exploration for reinforcement learning. arXiv preprint (tti::2008.055330 2021a.
Yue Wu, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal regret for learning infinite-horizon average-reward mdps with linear function approximation. arXiv preprint arXiv:2102.07301, 2021b.
Lin Yang and Mengdi Wang. Samplc-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning, pp. 10746-10756. PMLR, 2020.

---

Published as a conference paper at ICLR 2022
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. arXiv preprint arXiv:2005.13239, 2020.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989 PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. arXiv preprint arXiv:2008.07733, 2020b.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-basee reinforcement learn- ing with linear function approximation. arXiv preprint arXiv:2110.063994 2021a.
Xuezhou Zhang, Adish Singla, et al. Task-agnostic exploration in reinforcement learning. arXiv preprint arXiv:2006. X1v:220006009997,, 2020.
Zihan Zhang, Simon Du, and Xiangyang Ji. Near optimal reward-free reinforcement learning. In International Conference Machine Learning, pp. 1 12402-12412. PMLR, 2021b.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. arXiv preprint arXiv:2012.08507, 2020a.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for dis- counted mdps with feature mapping. arXiv preprint vrXiv:2006.33163 2020b.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for dis- counted mdps with feature mapping. In International Conference on Machine Learning, pp- 12793-12802. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2022
A
OMITTED DETAILS IN SECTION 4
A.1 NOTATIONS
In this subsection, summarize the notations used in Section A
Symbol & Sk,h, 4kah
Explanation
The pethhbbobbbbiitty event for Theorem
The state and action that the agent encounters in episode & and step h
Vk,
The value function with maximum uncertainty: arg maxvev 1E,, o(8, a, 8 V') (d'llan
(8,)(
Es d(s a, 8') V')V,, (s..
den
The estimation of 0% in episode k: (Ag,a) - (en ar, V. a (8t,411)
The covariance matrix in (k, h): E 1 01,6) AI
(8,
The uncertainty measure: By (s,,((8, (Ak,,) (8,
(s.
The exploration-driven reward which equals uy_h (s,
(8,a)
The Q function defined in line 12 of Algorithm]]
(8)
The value function defined in line of Algorithm
(s,
The value function defined in Equ 12
(%, Rt)
The Q value similarly defined as (s, R?)
R),
The value function of policy π similarly defined as Vr (s, R)
The parameter estimation returned at the end of the exploration phase (L a,, 0j ((s,a,8))
(,(s'(s,a)
A.2 PROOF OVERVIEW
Now we briefly explain the main idea in the proof. Firstly, we introduce the value function V7 Rt), which is recursively defined from step H 1 to step 1:
( R) = 0, Vs E
(12)
(s, R) = max aEA
min [n, a) + Ps (s, R), H}} ()), Ys E h [M]
(13)
Compared with the definition of Vi (s, R), the main difference is that we take minimization over the value and at each step. We state the following lemma, which gives an upper bound on the sub-optimality gap of क in the planning phase.
Lemma 1. With probability at least 1 - 5, the sub-optimality gap of the policy in for any reward function R the planning phase satisfies Ví (s1, V. R) S 4V7 (8). Rx) + Copt. where Rg is the exploration-driven reward used for episode K in the exploration phase.
This lemma connects the sub-optimality gap with the value function of the auxiliary reward in episode K. So the remaining problem how to upper bound V (s1, Rg). Since the exploration- driven reward Rg non-increasing w.r.t. k, it not hard to prove that KV (#1. Rx) S ΣK (s1, Rx). We use the following two lemmas to upper bound Σk (T R2).
Lemma 2. With probability at least 1 - 6, (s, R&) < (s) holds for any (8, a) E x A [H] and [K].
Lemma 3. With probability at least 1 1-6. 8,
K
Vv.1(s1) < olt
KH²B3/d)
With the help of the optimistic bonus term Ugsh- we can prove that the estimation value Ve, is always optimistic w.r.t Vi. which is illustrated in Lemma
Therefore, we have Σ (i R&) < ΣK (s1). By adapting the regret analysis in the standard RL setting to the reward-free setting, we can upper bound the summation of Vi, (51) in Lemma Combining the above two lemmas, we derive the upper bound of (51, Rx). then we bound the sub-optimality gap of A by Lemmal
13

---

Published as a conference paper at ICLR 2022
A.3 PROBA-RROYAILITY EVENTS
We firstly state the following high-probability events.
Lemma 4. With probability at least 1-6/2, the following inequality holds for any k E [K], [M]
10s. On ll S B.
(14)
Proof. For some step h [H], the agent selects an action with feature Fk,h = ( dg.b The noise 7k, Vk.hh.u...as.. (s') 0% @k, (Sk, (g.A) satisfies
By Lemma 20 the
following inequality holds with probability 2H
4H3K | BAllAZA S H logg
+ 12/2B.
(15)
A8
By taking union bound over all / E [H]. we can prove the lemma.
Lemma 5. With probability at least - 8/2, we have
K
H
(PAVe--1SSL,, (e.n-((4R)+1)) S 2HHK log(4/8).
(16)
Proof.
This lemma follows directly by Azuma's inequality.
During the following analysis, we denote the high-probability events defined in Lemma and Lemma as E
A.4 PROOF OF LEMMA II
Lemma 6. (Restatement of Lemma 7 Under event &1, the sub-optimality gap of the policy it for any reward function the planning phase can be bounded by
(s, R) Vial(ss R) I (V," Rk) + Copt-
(17)
Proof.
(8 R) -V R)
(18)
= -(Vi(s), - pitiie (s1,
( R)) + (VRRi (st, - VT" R3) + (prtii((ss (s1, D (s1 R)
(19)
(s1, $ (v) - Viai (sl, Ri) + (f R) - V) R)) + Copt-
(20)
The inequality is because that the policy मे the copt oopt-mlt policy in the estimated MDP M, i.c.
y (51, R) S V (s1, R) + Copt
For the notation convenience, for certain sequence {Ra Jk= define the function WA () recursively from step H +1+ to step 1. Firstly, we define W # (R,.) = 0. Wx((Ra)) is calculated
recursively from (1+1((RA)))
Wa W(RR, RR,)) min (H, Rg + Wh++1(RAN ({Rr)))
(21)
Similarly with the definition of V (s, R), we introduce the value function V (s, R), which is recur- sively defined from step H + to step 1:
V
(s, R) 0, S
(22)
(s, R) min Ry,
(s. (s)) -
R). U. [H].
,
(23)
14

---

Published as a conference paper at ICLR 2022
We use traj ~ (TT, P) to indicate that the trajectory (sh, 1 is sampled from transition P with policy т. For any policy T, we have
ESINy (1 (s1, R) VT v(((1))
(24)
(((Ph. - PA
PK (sh, One R)
(T Wi
(25)
(0h 0n) E ((sn on, s s') With (s', R) }}
(araji(ar Wi
(26)
ssn ans 5¹) Vori (s's 18) (cmaa))) (
Punjj((s,)WWi W1
110h On AKK.
Σ
(27)
(Aica) }}
Σ Φssh: an h+1 ( RR)
(B W1
2
(28)
(T W1 (fuK,((h,,n,) an)))
(29)
-2V7 Rx)
(30)
(31)
The second inequality is due to lemma and the definition of Ø. Plugging this inequality back to we can prove the lemma.
Inq. 18
A.5
PROOF OF LEMMA 2
(s, R&) S (s. holds for any (s, a) E Lemma 7. (Restatement of Lemma 2 Under event &,, (s,
x A, [H] and [K]..
Proof. We prove the lemma by induction. Suppose Vi, R&) S Vr,++1(s).
(s, Rx) - ())
(32)
S 5- () + (BEA - 0k.h))
Σ
+ Pa(Vit1 - Vs,Nt)((s
(33)
S ux) + (0an-0m.n) 0b.n))
Σ Mss a Vo.n
(34)
< ux + |0kn - 8Rm -kimllen
Σ o(s a, s V'
(35)
(New))
< (x + | - 0k.n Ae.
Σ o(s a')V())
max VEV
(36)
(Ama))1
S Uk,A + max VEV
Σ Ess
(37)
(Ae.))-
=0.
(38)
The first inequality is due to induction condition Viti R&) S (o) The last inequality
is due to Lemma Since (s, < QK,1(8, a, Rx) for any a E A, we have V (s. Rx) <
(s)
A.6 PROOF OF LEMMA 3
Lemma 8. (Restatement of Lemma
Under event &, Ek Vh.(skk)
W
6H2d (2/))33BB))))))) log(1 KH²B² /d).
15

---

Published as a conference paper at ICLR 2022
Proof.
Qk,h (8,,h,
(39)
=min
H, R (s.h)) + uanh (8k.0; (n,a)) + PA. Va (BR andh)
(40)
<min
H, 23 0 al + PR.N Ve, (Sk (sa and)
(41)
Smin
(H, I aR. 3. } + min { H, (Pn. Ph.) Vi, Vi (shi))
(42)
+ (PrVe (SK,, V (SK,A41)) + VI,h+I(SR,A+1)
(43)
<33 min ( (.
(Pr (( ax,A) V Va, (5K,415
(44)
The last inequality is from
(PEA- Ph)) Ve,,tilS,,, ax,A) -60,, 0n 0n) (8k ak,,))
(45)
1m.n On Nen
I Ilovants (Sk,hs an.b
(46)
3 ll (sk akwWllaz
(47)
3,3 (sh.
(48)
From Inq 39
we have
K
K
(81
33 min { (S
(49)
1=1
k= h=1
H
(P ak.h) V (16A44))))
(50)
For the first term, by Lemma 21 we have for any [H).
k
K
Σ min { 11 (x S
min { (sk.
(51)
2dK log(1 + KH2 (dd))
(52)
Since À = we have
K #
33 min {I, (9..) s bo + KH²B²/d)
k=1==1
(53)
For the second term, by Lemma 5
H
1= (PAVA (k.h) V S /2H3K (4/5))
(54)
Therefore, have
/ ( KH²Ba/J)
(55)
Lemma 9. Under event &, (s Rx) < d log (LH*KB* log KH
16

---

Published as a conference paper at ICLR 2022
Proof. Since (sk,,, R&) S (sk,1) ( by lemmal 7 we have
K
(1 R2) S Σ Vx,1 S 6HPdy Kogg(4H33B//0)0oggg /H2
(56)
By the definition of Rk, we know that R& (s, a) is non-increasing w.r.t Therefore,
(s1, Vs,, 1
(57)
1=11
The lemma is proved by dividing both sides by K.
A.7 PROOF OF THEOREM 1
Combining the results in Lemma 9 and Lemma 6 we know that for any reward function R,
log log(Aff*KB**)) + KH²B²/d
(81, R) (si, R) s dy
Copt
(58)
Choosing K C,H'd log(1H KB 1ogg for some constant C₁ suffices to guarantee
that (s1, R. V R) S e Copt-
B OMITTED DETAILS IN SECTION 5
B. NOTATIONS
In this subsection, we summarize the notations used in Section B
Symbol
Explanation
&2
The high-probability event for Theorem
Sk,A, Ak,h
The state and action that the agent encounters in episode and step Ev 0(8, a, a, s'v VT. (s',, 3 Rt) for certain value function V
(v a, R)
P (s, R)
The value function policy æ in the MDP model with transition P and reward R
b P
V...
k.h (s, R)
The expected uncertainty along the trajectories induced by policy ı for Vyn. (s, R) (Defined in Eqn
VT.
ki (s, R)
The optimistic estimation of V (s, R) (Defined in Eqn
J.P. "La (s, a, R) P.x u (s,a,
The exploration-driven reward for transition P. reward R and policy æ (Defined in Eqn 4
The confidence bonus ensuring the optimism =. (s, 2 TT.P (s, R) (Defined in Eqn
(s,(s,
The one-step transition variance w.r.t. certain value function V
VI (s)a)
ls The empirical variance estimation w.r.t. the value V
The empirical variance estimation w.r.t. the value Dx (s, R2) (Defined in Eqn 59
22,4 a))
Px (s, R&) (Defined in Eqn 60
ELA.A, E2
The confidence bonus for the variance estimation V1,4. (s,a) and 22 k. (s, a). respectively
R. 2.
The optimistic variance estimation for V Ii,k h. (s, a) and V2,4, k. (s, a). respectively
The parameter estimation w.r.t. certain value function (Defined in Section B.2
A
The empirical covariance matrix w.r.t. certain value function (Defined in Section B.2
Uk
The confidence set containing 0₁ with high probability
Tk. 0x, Rs (s)
arg max n, ET4,,,, V (s1, R)
The "value function" for the MDP with transition Ps and reward V1, log(32K log² KH B2)
B.2 OMITTED DETAILS ALGORITIIM 2
In algorithm 2 we maintain five different parameter estimation 01 P n. dskk d and 05 and the corresponding covariance matrix AI,a,,, A2, Ag. Ask and Ag.
17

---

Published as a conference paper at ICLR 2022
81, 62 are the parameter estimation using history samples w.r. the features of variance- normalized value function Ve (ō,,,, and k,h+1 fō respectively. 8g B4,,, are the P.
parameter estimation using samples war the features of value function (v and (w.te+t) k,,+1)
0s,4,A is somewhat technical and will be explained later. for any [5] and h [Lf] 0z,1, are initialized as O, and 1, are initialized as Al in Algorithm 2 U1 is the set containing all the On that makes Ph. well-defined, i.e. Ex 0/ (ss'|s [s, a) and 0, d0s' |s, a) 2 0, Vs,a.
After observing {SE,A; 0K.A lim in episode k; we calculate VI,A, (s, a) and V2 (8,a) as the corresponding variance in the empirical MDP with transition dynamics Pk-
(1, -0 E (s, (Vre.Pr (s', Ra))²
0k E s'Vi. Ra)
(59)
(2) =0,, =0,, Σ a(s,a,s)) (VrsiPt Py (s', (s,,
1h, Σ a M' Rx)
(60)
To guarantee the variance estimation is optimistic, we calculate the confidence bonus FL, and E2 for variance estimation V 11, (Sa,ns (g.s) and V2,0. (8k,b, oR
E1 min
H² 4H BR
Σ o(su ansh. 8¹) s') Di Ra)
k.h+i
(61)
(1
+ min
112 23p
Σ d(Rk. (k),,
klitl (5', (s' (R))
(62)
F2, = min
H² 4H
Σ M88k,h ak,h, 8') Vi.hii Re)
(63)
+ min
H22 23,
Σ d(sk,n s') (oo)vvVvv (Ven.Pi(s',, (s',
(64)
We add the bonuses V V ap.n) and V ap.)) and maintain the optimistic variance estimation Tf 1 and 22 k.
L,k. max (H2/dd (1 + ELa.
(65)
2 2, max { H22 1F2//, (K. + F
(66)
We use ōikk.h to normalize the value obtained in each step. By setting X = B-2 and solving the ridge regression defined in Eqn. 8 know that 0 and Age+1, updated in the following
18

---

Published as a conference paper at ICLR 2022
way:
A1411= = -L + (OLLx))
Σ (sk,h Okhn, s Wentil (s', Ra))
(
o(sk, Oke 8 (s (s', Ri))
(67)
A2A411= = AIRA (62xx))
Σ Essn akih, s V (
Σ
akn s¹) sf ,s))
(68)
01,411 = (A1A+Ln)
Σ D(oLAN)
Σ ae V').. (s Rt)
Vehh+i (s Re),
V.T..P
(69)
4 -1
02,411h = =AA2,+1.))
Σ (o2en))
Σ aen V
Ch+1 (s', (s.))( (8i)
Veliil (9 Re).
1=1
(70)
Similarly, we update the estimation w.r.t (Vir.iitss (s', (R))) and (d
(6',
Σ (( (Ver (Ventils'' R&x) )²) T
R (Ra)))().
A3,441.6 = -A3,6, + Σ (k)))) 8') (Ven,t
(71)
(I (( (veu (s', Rix) 2 T
( Raa)²) Σ sk))))) (vanii(ss
A4,841, = -aautt +
(72)
Σ olsen.ae.hs (vaniflss,, mii)) (VTr (vunf((ouats:Ba))) Bi))
03,441,- = (As.+LiN)
(73)
Σ p(S (e ( (wisiflos, R.)) (vinh (vischlouatt))B)) "
01R+IIA = (Au.41in) -1
(74)
We define VE, to be the "value function" with transition Ps and reward Vi
(5) 0, Ye,((s) = WI,AA(S, (x))) + Pan
(75)
(76)
0, is the parameter estimation using samples w.r.t (s):
Σ (ssnn an, 5f of (fanntll))) (Σ p(san, of
A0,b41A- = AD, +
(77)
0,,441,4 = (A6,641A))
al 8 Ven-i(saati)
(78)
19

---

Published as a conference paper at ICLR 2022
We update the high-confidence set u by adding following five constraints:
0/ 0 AIAAAAAA S 3
(79)
|| 06 A2A,All $B,
(80)
|| 0 A3A.NlAaAA S
(81)
10; AsAAnllaan. S B,
(82)
16 A5,k,AllAG...A S S.
(83)
Note that we add new constraints to this confidence setlls, in each episode, instead of updating Mr.h as the intersection of the new constraints. This operation designed ensure that the cardinality
of the confidence set Un h is non-increasing w.r.. the episode k, that V (s1, R) is always non-increasing w.r.t. k. During the proof, we use @ve,p a, R) as shorthand of E. D(8 a, V'.. R).
B.3 HIGHI-RRBAABLIITY EVENTS
For notation convenience, use (1,4,, a) and V2,,, a) to denote the one-step transition variance with regard to T/ and VT. . i.e.
Tu kh+1 (6, Ph P (s, as, Rk)
R
2
(84)
Pv (VEA4 (s', PAVER (s, (s, Rk))
27
(2,,,(s, -Es-Paa(la.a
(85)
(86)
Lemma 10. With probability least 1 8, the following event holds for any h E [H], [K]:
0k.h 8n
S 223
(87)
AI,M.
00. 0nl A2.
$ 23,
(88)
V1,4, (Sk,h, an,n)
V VI,,, (SK an.n)
5 Fl
(89)
V2,4, (Sk at.)))
22 (sk, akeh
S E2,
(90)
0n.n On No.u.
5 2
(91)
Proof. We firstly prove the first and the third inequality, the second and the fourth inequality can be proved following the same idea. By the definition V 11... ag.n) and V1,4, (Sk,ho ag,)):
W 1. (k..)
V (SR.n
(92)
min
H? H1,211 2H
Ōā,n 0nl| 0allarea
depeie (SK,A, Re) Peeuie
(93)
Ba.n - -Onllazea I (Vra)t)) (SK. apen, Rhd)
+ min
H2
(94)
Let 24 (ō1,).,)
Pppt. (8k, ax.)), and the noise hhil
7is (GI.R.n) -
Ps (SK,6+1, R&) -6
DycuiPs (SR,n, an,h, ak,h, R&) Rx),0r)
Since TIA,A 2 HH2/d, we have |axll2 Vd. E m Gz] d. By Lemma 22 have with prob
at least 1 - 6/(8H), for all & & K.
|0h 0
S 16dv + (A) + VĀB= =3. (95)
AL.KA
20

---

Published as a conference paper at ICLR 2022
Similarly, prove that
I 16H2 /dlog(1 + (o + VAB = -.
(96)
Since 62.6 - 81,
B S
B by Inq 79 we have 0%, 6k.n Baamlaaa0
2B. Similarly,
since (k.A Bs.kn
we have |8A, Bk. Assen I 29. Plugging the above by Inq 81
As A.
inequalities back to Inq.
92
we have
1 (Sk,h, ak,h) LL an,N) S Ei
(97)
The above inequality indicates that ō1,k, 2 V1,4, which is an optimistic estimation.
As a result, the variance of the single-step noise 7/ = (o1,
- k.h+ (8k,h+1, R&)
(ō1,k.)) Pp (sk,h, ak, Rk) 8n satisfies E [nk GR] s 1. By Lemma 22 can prove a tighter confidence guarantee for 12,
0), 02 AI
16 dlogll
log(2)
log
+ VAB B.
(98)
Combining with 02,4.n
01, Ar.k. S B by Inq 79 we have 0r, 02.00
I S 23,
A.A.A.
Now we prove the last inequality in this lemma. Recall that we define
(s) 0,
(99)
(E) (I, (s))) + PR.AA Ve. (s)))).
(100)
Note that (s) < H² by the law of total variance (Lattimore & Hutter 2012 Therefore, the variance on the single-step noise at most H² By Lemma 22 we have
Azar et al.
2013
00 05.u.h A..
||
(101)
Combining with 00,
0s.u.
An, I 3 by Inq 83 we have |00 0o,0.n Aocie
2
Lemma 11.
With probability least 1 8/2, we have
Pr
Te.. k (SK,,, OK, RA)
Pt. Vkh+l (SK. QR. Rt))
/2H33 (173Klog(8/8), (102)
A=1
(e ak Rx) Ye.4I((9.-111 S
(103)
Proof. This lemma follows directly by Azuma's inequality for martingale difference sequence and union bound.
During the following analysis, we denote the high-probability events defined in Lemma 10 and Lemma as Ez.
B.4 PROOF OF THEOREM 2
Lemma 12. Under event &z. we have
K
Pk(81, Rx)
Pre
(104)
k.
k=1
<0
Vidlt+ (gg + (22.5 d log K KH/8) log" (
(KH*B²)
(105)
21

---

Published as a conference paper at ICLR 2022
This lemma can be proved with the technique for regret analysis. We will explain it in Appendix B..
Lemma 13. (Optimism) Under event E2, for any h [H] k [K] S, F II, R and P
satisfying Pa 0n @. we have
V Vi (s, R).
k.h (s. R)
(106)
Proof. This lemma is proved by induction. Suppose V k, (8, R) 2 V.T.P k (8, R), we have
Velh (s, Rt) Viinn (s, R) T.P
(107)
2,2 (s, x (s); R) + (Pk. ( (s)) R) Ps (vent V (hht1) (8, (s)), R)
(108)
T.P 2 क (5), R) + (Pk. Ph) V A.++ ()),
(109)
T.P 242 π (s), R) - | - On
Σ (s)) s Vinh
(110)
20.
(111)
This indicates that V. (s, R) 2 V.r (s, R) holds for step h.
PK (81, Rx) S Ek vo Pt Rc)
Lemma 14. under event Ez, we have V
Proof. Firstly, we prove that V7,1" (s, R) is non-increasing w.r. l for any fixed π, P,, and R. This
can be proved by induction. Suppose for any bn S 1:z, Vr (s, R) 2 V.. ( R) for any Recall that
A.P Vr, (s, R) min { a. (s (s, (s), + U2 (s, + (s,
(112)
Since A $ A1 Az A2 and F prove that
K1,441 (s, R) 2 V 11 (s, R) for any 8, we can
P.P ( Te (s), Rt) 2 " (8, (x), R).
J.P
(113)
" (3, Th (s), R) 2 22 (8, TT(s), Rt.
J.P
(114)
PA P h1 (s, Th (s), R) P.. ka (s, (s), R).
(115)
Therefore, VT. (s, R) 2 Vill (s, R) holds for step h and any 8.
Since the cardinality of the transition set Uk non-increasing (We add more constraints in each episode), we know that 0, E M By the optimality of THy 8,, and Rk, in episode k1, we have PPr, (s1, RR, 2 Thy Pug
Vk,11
1
R..).
Combining the above two inequalities, we have
Per
(s), RR,1) 2 Vil Pro Pea (8), RMJ) 2 Vill Vite Pro (s), REa)
(116)
k1.1
Px,, This indicates that the value V. (81, R&) is non-increasing w.r.t. h. Therefore,
K
KV PK (s1, Rg) < K11
Σ
Rk).
(117)
k.
km
n
22

---

Published as a conference paper at ICLR 2022
Lemma 15. Under event Ez, the sub- sub-optimality gap of the policy a returned in the planning phase for any reward function R can be bounded by
(s. - -V R) S 4VER.PK < (s1,Rx) + Copt.
(118)
Proof. Recall that VE to denote the value function of policy on the estimated model 0g-
(11 R) 17 R)
(119)
=(Vi(11, Vira. (s1, (), + (V),:)((5)),))) -V²Ex()1) + (Vih
(51, R). (V (51.,K((11,10 V. (s1, R)
(s1, R),
(120)
(V) R) Vi (s,, R) P (s,, (f*((s, R) + Copt
(121)
The inequality is because that the policy स is the cop: policy in the estimated MDP M.
For notation convenience, we use traj (I,, P) to denote that the trajectory (f5%, an H is sampled with transition P and policy æ. For certain sequence {Ra Jh=1 we define the function ( }) recursively from step H + 1 to step 1. Firstly, we define W WH+1(1 Rx)) = 0. (, is calculated from (R):
WA (( = min (H, Rg + (h+i((B))))
(122)
With the above notation, we can prove that for any policy π E II,
ViT Px (s1, Rt) - (/T(s)))
(123)
({ (PPnn Pr) (s
(sh: an R) R)}}]
< (T, W1
(124)
Px (s', R) })
(inaj W1
(0KA - 0n) Σ ((sh, 5
S') h+1
(125)
})
plsn, ar, 6') Vi (s', R) |0x, On A..K. Σ
(126)
(AL.K.a)
1)
W
2
Σ Olsnn an, an,
V' PK (s', R)
(127)
P2 Wi ((
T. ([". (sn, an, R2)
(128)
-2 R)
(129)
22V K.1
(s1, R))
(130)
<2V 2 Pw ($1, Rk).
(131)
The second inequality is due to lemma 10 The third inequality is due Lemma
13
The last
inequality is due to the optimality of n and Rg. Plugging this inequality back to Inq. 119 prove the lemma.
we can
Proof. (Proof of Theorem 2
Combining Lemma
12 Lemma 14 and Lemma we know that (
K +2 log")) (de)) log (KHB/((e))
"H" + H
log(dH/(5e)) log (H())())) for
2
some constant C2 suffices to guarantee that Ví (81, R) Vf (81, R) S 6 capt.
23

---

Published as a conference paper at ICLR 2022
B.5 PROOF OF LEMMA 12
Proof. From the standard value decomposition technique (Azar et al. 201 7 Ji et al. 2018). we can
decompose Px ($1, R&) into following terms:
VTl. (81, Rx)
(132)
H
H
Th Pe (sk an Ri) + Σ min { H, u
TeiPa min HH, u2kih (smin ana Rs)
(133)
h=1
min (Pr. Pa) Va khtt (5k, aR, Rux)
(134)
Ph VTL.PPP Pt (sk, ax,b, R&) V.L.Pe Miitl (su,001, ax,011 R&))
(135)
H
min
H. Tu.Pe Ui (Sk. ak Ri)
(136)
hm
Tu.Po min H, u2, (sk,nr ak, Ru)}
2
(137)
Ph Vi
Ae (sk,,, Ak,b, R&) - vau. ( G1,611,
(8,,41,,0,,41 Ra)),
(138)
where the second inequality is derived from
(Pk. P..V 6.h+1 (SK au,i, Ra) -00,, - 0n) Σ ah, VT.. (s', Rk)
(139)
< 02.n on onll Σ d(s ak. 8') S' (s',
Ag,
(140)
Te..PP Suzkh (ap,,, ap,, Rx).
(141)
Eqn 138 is a martingale difference sequence. By Lemma 11 the summation over all k E [K] is at
most / /2H* log(4/8). We mainly focus on Eqn 136 and Eqn 137
Upper bound of Eqn 136
Firstly, we bound the summation of min { H, (SK., an,,, Re)
su ui ki
24

---

Published as a conference paper at ICLR 2022
H
min
Te H, WI,hh
(142)
Rem 1 hmml
min H. 3
Σ
(s', Rs)
(143)
Amm hmml
V. k.h+l T1,k,
(8', R&)
k.hh min
1, Σ
(144)
AT
P Pv khh+1
(s', Rk)
<
Σ
Σ
min 1, Σ
(145)
k,h
h
Σ
2dH log(1 + KH/A).
(146)
The first inequality is due to Cauchy-Schwand inequality. The second inequality is due to Lemma 21
By the definition of of I. we have
oi S /d+ FL, + VIA Ok,n).
(147)
Now we bound Σn, ELR and Ek, VI,, ax,)) respectively. For Σn. EL we have
H K
Σ k
EIRRA S
Σ bosk an, 8') WeNi (d', Ra) min H² H2,4H 3,3
(148)
k=1
H
K
Σ b(sk. ax... (Drr.ft RRs) 2
min
H2 2
(149)
For the first part,
min
Hº. AH3
Σ blsk,h S' (5', Ri.)
(150)
h=lk= k=
H
<4H
30 min
1,
Σ b(su.h, s'
kihtl (s', Ra)/oLmN
(151)
Auml 1mm
(A
DeL.PE k.h+ (s', Ry)
<4HB
22
Σ
min 1,
Σ ((sk,, sk.,,
(152)
I.k.h
Ø1,kbb
A
<4HB
Σ
G.....
2dH1 log(1 + KH/A),
(153)
k.h
where the last inequality due to Lemma 21 Similarly, for the second part, by Lemma 21 we have
#1 K
ΣΣ min
H2 H2
Σ (Ssnn 8') (V (s', Ru))²
(154)
h=1k=1
(Aa2a)-1
<29 22H222 log(1 + KH/A).
(155)
25

---

Published as a conference paper at ICLR 2022
Note that VI,A, (SK,,, (g,A) is the empirical variance of V. (s'; Rx) with transition
(s' (g. ag.a). We bound the summation of V (S,,, 0g,h) by the law of total variance Lat- timore & Hutter 2012 Azar et al. 2013).
Recall that we define
Hx. = O, (8) V (1, Tn(s)) + (s,
(156)
(157)
By the law of total variance, we have (s) S 112 holds for any s, a and k. We now bound the difference between Σx=1 (8R,1) and Ex=1 En= (1,,, an.b)
(sk1)) VIAAM(SEA ak,h)
(158)
h=1
Yn2.))2(SH Σ
V VIRA(S
(159)
h=2
Smin Quin(Ht (IP,, H2, (Ps)- (x11)) + ( p),((02)))
(160)
H1 Σ V
+ (Fe2(0n2))
(161)
h=2
Therefore, we have
K Ve. (6x,1)
K
V (s,,n
(162)
k=
1=h111
K
min H2, (PE. - Ph) F (skn
(163)
A
K
(P - V(o+I((AA+1))
(164)
For Eqn 164 this term can be regarded as a martingale difference sequence, thus can be bounded by KH KHH by Lemma
For Eqn 163 we can bound this term in the following way:
min H2 (PEn - -P1) Fh (SK. (snn))
(165)
K
min H2 1lo., oullaonn (oK, an R) Mllaa
(166)
h=1
K
min 1, ( axn,, Bllla
(167)
km 1 h
H
K
K
min 1, Illy (SK, ax,b, R) R))l
(168)
1=1
<B 2dH K log(1+
(169)
The second inequality is due Lemma TO ity. The last inequality is due to Lemma 2T
The third inequality is due to Cauchy-Sehwarz inequal-
From the above analysis, have
Σ WI.. H2K + B 2d log(1 (1 KH/A). k.h
(170)
26

---

Published as a conference paper at ICLR 2022
Therefore, the summation of o, can be bounded as
Σ
o L.K.
(171)
k
< SH 3/dd++
Σ
Ei, +
Σ
V
(172)
k,
S/ 4HB
2dH log(1 + KH/A) - 1²
+
k,h
(173)
We define T log 2 H/ KH* Solving for Ex,, J.M. we have
Σ k,h
L Sei
K/d H K + H d VH2
(174)
2ec (1 K/d+ =² + 1 dT))
(175)
where denote certain constant. The last inequality is due to 2 ab S b a, 0. Plugging above inequality back to Inq 142 we have for constant C2.
K
ne. Pke u Lih (Sp,hs ag,h, R&) S 02 / + KT + 22
(176)
Ft.Pt 137 Now we focus on the summation u22,, (8k,,, Ok,b, Rg). The proof
Upper bound of Eqn
Na, follows almost the same arguments as the summation of u1,kh (Sk ag.hs Rs), though the upper
bound of Σx E/z V2,,, (k,A) is derived in a different way. Following the same proof idea, we can show that
H
Te.Pk 22k,h (Sk,A) dg,As Re) S Eosua log(1 + KH/A),
(177)
k=11=1
R.h
2 I H22 H2//d= E2RCA + (2,,, ak.h);
(178)
K
H
E S 4H3
Σ
2dH log(1 + KH/A) + /2H22K Iog(1+ KH/A).
2,
Aml
k.h
(179)
Combining Inq 178 and Inq and and solving for kk, 22 we have
Σ
2
(180)
k.h
<2H K/d 16 log(1 + KH/A) + / log(1 + KH/A) 2 Σ V2 V2, (8k,h, (k.h))
(181)
<6H 32 KH/A)++ log(1 + KH/A) +2 Σ V2A.A ak.h))
(182)
Plugging this inequality back to Inq 177
we have
Tu.Pe up 2, (Sk.h, ak.h: Ra)
(183)
<3 < log(1 4B log(1 + KH/A) + 233a8/2 log(1 + KH/X) (184)
32d log (1+ (1+KBBB2) Σ V2An(snAAaaa.) an.N)
(185)
k.h
27

---

Published as a conference paper at ICLR 2022
We now bound the last term in the above equation. Define 1og(32k (1+ KH+BB) we have:
32d HT
(2,,, as.A)
(186)
k,h
11
(v,bt (VTTaft)) Ra))
32d HT
B Pr.a (1..
(187)
k=
K
32d 1
y Pa. (1
(EAti (s', Ra)
(188)
k= h=1
<4V20gd T
E Ey sk.
khh+ Rx)
(189)
HgHl
K
H
24V2 H 7+
viua kih+1
(8k,t+1, Rs)
(190)
H
H
Ps V..VE k,b+l (Sk.h, ake R&) kit+l (9,,ht1,R))
(191)
call
k=1
H
Pk.h - Ph) ViT. ak Ry),
(192)
where čअ is constant be defined later. The last inequality due to 2v + b for any a, b 2 0. Note that by Lemma I0 Eqn 192 is upper bounded by cal Ena Pu. 22,kch (Sk,h, ag.h, Re). Eqn a martingale difference sequence, and can be bounded
by /HKlog(1 log(1 1/8) with high probability. Plugging the above inequality back to Inq 183 and solving Pe.Pt 22 (SK, ak RR), we have
Σm for Σk= k=
K
Pe. 2,
(Sk,h) ake R&)
(193)
k=1h=1
K
Scg
VaH+KT+ (225 (2
Via k,h+1
(SK,441, REs)
(194)
C3
1=1
where c3 2 1 is a constant here. We set č3 = C3, then we have
K
H
Up Un
Fei
ask, Rs)
(195)
K Ses (VaH-Kr+ (225 (HH))) + + H
Ta (8k, R&),
(196)
k= k=1
Bounding the summation of Pt. 11
(81, Ri) the above analysis, we derive the upper bound
of Eqn 136 and Eqn 137 (Inq and and Inq 195 Now we can finally bound Σk Vk.1 Te For a constant C1.
(SK, Ra).
k
P.
Pr
(sk,1,RA)
(197)
k.
K
H
Senv (dllddd++++ (d + cc 252 d H
(s4, Ra). (198)
H
k
h=1
28

---

Published as a conference paper at ICLR 2022
Following the same analysis, the above inequality actually also holds for any step h [H]:
Pe (Sk,hs Rs)
(199)
K
H
SCIV(dH+ dHH (d2 &
VT Aiit
(1,, Rx). (200)
k= hy hh
Define G
ca (H))))
+
and
4h
Σ Viaa (s R₂). The above inequality be simplified into the following form:
a
S G
1 H h1=h
Σ
ah.
(201)
and we have a##1 From the elementary calculation, we can prove that #1 S (1+ eG. Therefore, we have
K
Te. Ps (Sk.1, R&) 1
(202)
Sas
+ + log( (C0 + + log( (H/8) (K
(K
(203)
for a constant C3 = EC1.
C THE LOWER BOUND FOR REWARD-FREE EXPLORATION
In this section, we prove that even the setting of non-plug-in reward-free exploration, the sample complexity in the exploration phase to obtain an e-optimal policy is at least 22 ( We say an algorithm can (e, -lears the linear mixture MDP M if this algorithm returns an e-optimal policy for M with probability at least 1 - 5 in the planning phase after receiving samples for K episodes in the exploration phase. Our theorem is stated as follows.
min (CIVH, O2 CLVdH=B 1BI,H 4, 3 for certain positive constants C1 and Cz. Then for any algorithm ALG there exists linear mixture MDP instance M = (S,A, P, R. H. such that if ALG (e, 8 the problem M, ALG needs to collect at least K = Cd2t j² episodes during the exploration phase, where C is an absolute constant, and 8 < 1 a posilive constant that has no dependence on e, H, d, K.
Theorem 3. Suppose
Compared with the lower bound proposed by Zhang al. (021a)), further improve their result by a factor of d. This lower bound also indicates that our sample complexity bound in Theorem 2 is statistically optimal. We prove Theorem in Appendix C.I
C.1 PROOF OF THEOREM 3
Our basic idea to prove Theorem 3 is to connect the sample complexity lower bound with the regret lower bound of another constructed learning algorithm in the standard online exploration setting.
To start with, notice that the reward-free exploration is strictly harder than the standard non- reward-free online exploration setting (e.g. Jiin et al. (2018); Zhou et al. (2021) 2020a)), where the reward function is deterministic and known during the exploration. Therefore, if we can prove the sample complexity lower bound in the standard online exploration setting, this bound can also be applied to the reward-free frree setting.
For readers who are not familiar with the formulation of online exploration setting studied in this section, we firstly introduce the preliminaries. Compared with the reward-free exploration, the only
29

---

Published as a conference paper at ICLR 2022
difference is that the reward R(s, is fixed and known to the agent. In each episode, the agent starts from an initial state Sk,1 sampled from the distribution v. At each step h E [H], the agent observes the current state Sg,4 S, takes action 4 E A, receives the deterministic reward Ra (Sk,A, ag,A), and transits to state 88.4+1 with probability Ps (s (8k, (g.a). The episode ends when $1+11 is reached. The agent's goal is find c-optimal policy a after K episodes. We say policy is e-optimal if
H
H
E
Σ
Ra (sh, an)
|
2
E
Σ
RA (sh, 0n) 1 1 -
where 't" is the optimal policy for the MDP (S, R.A.P.R.HH,,
Theorem 4. Suppose e S min (CIVH, C2VdH+B) B > 1, 4, > Then for any algorithm ALG1 solving the non-rewaad-free online exploration problem, there exists an linear mixture MDP M = (S R, H. v) such that ALG, needs to collect at least K = Cd2 H3 /22 episodes output an e-optimal policy for the linear mixture MDP M with probability least 1 1-5, where C is an absolute constant, and 0 < < is a positive constant that has no dependence on c, .., d, K.
From the above discussion, Theorem 3 can be directly proved by reduction if Theorem is true.
Proof. (Proof of Theorem 3) The theorem can be proved by contradiction. Suppose there is an algo- rithm ALG which can (e, -eernns any linear mixture MDP instance M with only K' S Cdf episodes. Then we can use this algorithm to solve the online exploration problem by simply ignor- ing the information about the reward function and directly calling the exploration algorithm of ALG during the exploration phase. Then in the planning phase, we use the planning algorithm of ACG to output policy based the reward function well samples collected in the exploration phase. Therefore, this indicates that ALG can output an c-optimal policy for the non-reward-fiee online exploration problem with probability least ô after only K' I Cd2 11 /e² episodes. This contradicts the sample complexity lower bound in Theorem
Now we discuss on how to prove Theorem 4
Proof. (Proof of Theorem Set K; cK for a positive constant algorithm ACG₂ for any possible ALG1 in the following way: In ALG2, the agent firstly runs ACG, for K1/c K episodes. After K episodes, suppose ALG, outputs a policy according to certain policy distribution vz. ALG2 executes the policy á in the following -- Ki episodes. The interaction ends after K2 episodes. ALG2 can be regarded as an algorithm which firstly runs the online exploration algorithm ALG, for K episodes, and then evaluates the performance of the policy स in the following episodes. We study the total regret of ACG2 from episode ++1 to episode K1.
We construct another
Recently, Zhou et al. (2020a proposed the following regret lower bound for linear mixture MDPs In order avoid confusion, use the notation K₂ instead of K to denote the number of total episodes of the regret minimization problem.
Lemma 16. (Theorem 5.6 in Zhou et al. (2020a)) Let B > 1 and suppose K₂ 2 max {(d (dd-1)²H/2, (d- (3 1]]}. ists an episodicc, B-bounded linear mixiure MDP parameterized by O = (0), ...,,..000... ,0H) such that the expected regret is at least Q(dH 2H
d 4, H 2 3. Then for any algoritlum there
To prove the above regret lower bound, Zhou et al. (2000a) construct a class of hard instances which is an extension of the hard instance class for linear bandits (cf. Theorem 24.1 in Latti- more & Szepesvári (020)). They show that for any algorithm. there exists a hard instance in the instance class such that the regret at least ((HH/HK)) By Theorem 16 and setting K2 K1, we know that for any possible algorithm ALG2, there exists hard instance M such that K1 E (V* v (s1)) 2 ondH HH for positive constant C22 where π& denotes the policy used in episode & for algorithm ALG2. The expectation is over randomness of the algorithm and the environment.
30

---

Published as a conference paper at ICLR 2022
Note that in the hard instance constructed in Zhou et al. (2020a), the per-step regret is at most E (si) v**(s))) I dH H. for any episode h I K₁ By choosing max 2v/20 2). 4/2 V
K₁ we know that for the instance M.
K
C2 1 1) HA HK 2 dH HKK. 02- 4v2c
(VV - V** (81))
/HK
(204)
2
RE= ki//1
By the definition of ALG2, we have Th = if >> K1/c c.. Therefore, we have
2 dH HKK (c - 1A (V*()1) (s1) 2 2
C2C dHVHK.
(205)
2
Dividing both sides by (c - 1)K, we have
E Ex~pa (V* V (s1)) 2 2
C2C dH v H/K.
(206)
The above inequality indicates that, for any algorithm ALG there exists an instance M such that the expected sub-optimality gap of the policy returned by ALGı is at least 2(c-1) dH HH/K K after collecting samples for K episodes.
Suppose ACG1 returns an e-optimal policy स with probability at least 1 1- 5. Recall that the per-step sub-optimality gap is at most E (V* (** (s1)) S
dH
H in the constructed hard instance. V ck
1v2
We have
(1 8). 6
dH
H
Eamp, (V*(s)) - (s1)) 2
C2C dH HH/K/K (207)
4
2
cK
2(c-1)
We set 8 to be constant satisfying 0 < 8 < min {1, 2V2c" oz
Solving the above inequality,
have K > Cd for positive constant C.
D IMPROVED BOUND FOR REWARD-FREE EXPLORATION IN LINEAR MDPs
In this section, we explain how our choice of the exploration-driven reward can be used to improve the sample complexity bound for reward-free exploration in linear MDPs (Wang et al. 2020). We study the same reward-free setting that in Wang et al. (2020), which is briefly explained in Ap- pendix D.I We describe our algorithm and bound in Appendix D.2 and prove our theorem in Appendix D.3
D.1 PRELIMINARIES
For the completeness of explanation, we briefly restate the reward-frre free setting studied in /Wag al. (202)). Compared with the setting in this work, the main differences are twofold: Firstly, they study the linear MDPs setting instead of linear mixture MDPs in this work. Secondly, they study the standard reward-free exploration setting without the constraints of the plug-in solver.
The linear MDP assumption, which was first introduced in Yang & Wang 2019); Jin al, 2020b).
states that the model of the MDP can be represented by linear functions of given features.
Assumption 1. (Linear MDP) an MDP M = AS P. R, H. is said to be a linear MDP if the following hold:
There are d unknown signed measures Phh (16g 14 .... (10) such that for any S, Ps (s' s,a) = (1h (s'), ((8,))))))))))))
11) (2)
(8,a, E S
There exists H unknown vectors Th 72. ... nh E IRd such that for any (s,0) E S x A, Ra Rs(s, a) (Ø(s, a), ma).
31

---

Published as a conference paper at ICLR 2022
We assume for all (s. a) S A and h [H], [l)(s,a)] s 1, [| vd and Ilnll2 S vd.
For the reward-free exploration studied in Wang et al. (020), the agent collects dataset of vis- ited state-action pairs 'D (sh- af) (K.A)e(K] [(*] which will be used in the planning phase. Then during the planning phase, the agent can follow certain designed learning algorithm to calculate an e-optimal policy w.r.. the reward function R. using the dataset D.
D.2 ALGORITHM AND THEOREM
Our algorithm can be divided into two parts. The exploration phase the algorithm is presented in Algorithm and the planning phase is presented in Algorithm 4
Algorithm Reward-free Exploration for Linear MDPs: Exploration Phase
Input: Failure probability 5 > 0 and target accuracy > 0
B + dH /lg (dHô-lc-1) for some > 0
K + CK d H log (dH8-1g-1) / 2 for some eк > 0
for episode k 1, 2, ... K do
5: 2R,H+1 (:.)) ) f- 0. HR,H+1 0
for step H, H - -1, -,..... do
Λg. + Σt=l ((81,10 (00,), (2,) T +
(.. 3/ )(.-)) (Ak,h) ((:.))
Define the exploration-driven reward function Re,n(-;)) (.-))==--))))) = (ns)(s))
Wk,h (AR,a) El p(st, ae, VonN)
10:
Qu,((:-)) + min i (x(((,)))) Re,((:))) uk, )), H
Ve,n &- max.EA Qk, a), (8) = arg max Q (s, end for
for step h 1, 2, H, do
15:
Take action ag,A = T (sk..) and observe Sk,4+1 ~ (s Ck.1) end for end for
Output: D 4- ((..,,, (RN))
Algorithm Reward-free Exploration for Linear MDPs: Planning Phase
Input: Dataset D +- {SK,, (R.b) (K.N)((K)x({)) reward functions R (Ra he(H
Qk,H+1 (-. = 0. (.))
for step h H, H 1, 1
An Σx= ( ar,n))((ss,. ac,n) +I
K
5:
(n(.,) min B d(.))) (Av,a) ((.)),
wn + (Aa) [=] o(SL
Qx(.,-) )) + min 20) o(.,))+ + Ra(--) + +ul.)) .,, H}
V <- max.5A Qu (8, a), Tn(s) = arg max Q (s.
end for
10: Output: = {Th J
Compared with the algorithm in Wang et al. (200)), the main difference is that we set Re, 4k in the exploration phase, instead Re, Uk.h/ H. The following theorem states the complexity bound of our algorithms.
Theorem 5. With probability least 1 - 8. after collecting O(d log
trajecto- ries during the exploration phase, our algorithm outputs an e-optimal policy for any given reward during the planning phase.
32

---

Published as a conference paper at ICLR 2022
D.3 PROOF OF THEOREM! 5
The proof of Theorem | follows the proof framework in Wang et al. (2020) with slight modifica- tion. Therefore, we only sketch the proof and mainly focus explaining the differences. Firstly,
introduce the value function Vi (s, R), which is recursively defined from step H to step 1:
V (s, R 0, Vs ES
(208)
(s, R) = max
{ min (s, PA PA R), CEA
H) R), vs e [H]
(209)
Compared with the definition of (s, R),, the main difference that we take minimization over value and H at each step. We can similarly define Q7, (s, a, R), V/ (s, R) and (s, a, R).
Lemma 17. With probability 8/2, all [K],
(s1,s, R&) S (81,))
(210)
and
K
(1.1( on loggKoo)
(211)
for some constant c where VK,1 is as defined in Algorithm
This lemma corresponds to Lemma 3.1 in Wang et al. 2020)). The main difference is that replace V with V Note that Vi (s, RR s H by the definition of Vi Rt). Lemma 17 can be similarly proved following the proof of Lemma 3.1 in Wang al. (2020) and replacing Vū, by Vi during the proof.
Lemma 18. With probability 1 - 8/4, for the function un (:))) defined Line Algorithm we have
E Esnu
Vi (s, (n)
s dd dd log (/)))
(212)
Compared with Lemma 3.2 in Wang et al. (2020). we replace the term Vi (s, H)/H) with VIr (s, un). Note that with our choice of exploration-driver reward in the exploration phase (i.e. Ry.A = k). replace the term wg/H with us in the expectation. This lemma be proved by following the proof of Lemma 3.2 in Wang et al. al.) (202))
Lemma 19, With probubility 5/2, for any reward function satisfying Assumption 7 and all h [H]. have
s0l.:))s@a(. Ra(:.) ) Σ Ph (s' V4+1 (s') 2un(-.))
(213)
Since our algorithm in the planning phase is exactly the same with that of Wang et al. (022)) this lemma shares the same idea of Lemma 3.3 Wang et al. (2020).
Now we can prove Theorem 5 with the help of Lemma 18 and Lemma 19
Proof. (Proof of Theorem 5) We condition on the events defined Lemma 18 and Lemma 19 which hold with probability at least 8. By Lemma 19 have for any S,
Vi(g) = max Qs(s, 2 max (i a, = (s,
(214)
which implies
Eg u [Vi (s1, R) V (S1, r) $ EziNg (V1 (81) - V (s1, R)
(215)
Note that 0 < (s) < H and 0 S V (s, R) < H since 0 S R(s, a) S 1. Therefore, we always have (s) VT (s, R) < H. For any Sh. we have
(*(ss) - V (sh. R)
(216)
min {11, PA Vn TA (sn)) + Zup (Sh, mn(3s)) PA PAVV V7 R)}
(217)
33

---

Published as a conference paper at ICLR 2022
By recursively decomposing (sh) Vg (sh: R) from step H to 1, we have
Eg [Vi (s1) - VI" (s1. r)] - Esnu VT u)
(218)
By definition of V/7 (s, u), we have Exnn (s. u) S 2ggmpp
Vi. u)
By Lemma 18
E smup
w) S d' 1og/
(219)
By taking K = cx a H log 1/) for sufficiently large constant CK > 0, we have
E Sapp
[Vi (51, Ht) V1" (81, r)] < dd lo((dK s.
(220)
E AUXILIARY LEMMAS
Lemma 20. cofffaoomalized Bound for Vector- Vector-Valued Martingales, Theorem I and 2 in Abbasi- Yadkori et al. (2011)) Let {Fele be a filtration. Let {n be real-valued stochatic process such that ne Pe-measurbble and 1). is conditionally (-sub-Gaussian for some R 2 0, i.e.
(2²R2 2
VY E R, Ele Am Fi-1l S exp
(221)
Let {X1]=1 be an -vauudd stochastic process such that Xe is Fem--muaurralle Assume that V positive definite matrix. For any 2 define
V-V+ Σ x.X. S, = 1 nox.
(222)
$=1
a=1
Then, for any > 0, with probability at least for all 2 0,
det (V:) 1/2 det 1V2
|| 2R log
(223)
8
Further, let V = 12, O. Define Y, (Xe, 0.) + Te and assume that ||0.112 S S, [|eell2 S L, 2 Thenfor any 8 0,with probability at least 8, for all O, 0, satisfies
1. 0- 0.110, S SRy d
1 (1+112/X) +
(224)
where 6, is the -ergeullaizzdd least-squares estimation of 0, with regularization parameter X based on history samples fill step t.
Lemma 21. (Lemma 11 in Abbasi- Yadkori et al. (011)) Let {X)] be a sequence in Rdd X,X_ Then, we have that
x d positive definite matrix and define V, = V + E.m1
det (V₂) del(V)
log
|xll
(225)
Further, if||Xell2 S. for all I, then
min [xel } < (log det (V.) llog det V) < (dlog ((trace(V) + nL²) /d) log det V).
(226)
and finally. if Aamin (V) 2 max(1, L?), then
[xll < 2 log det (V,)
(227)
del(V)
34

---

Published as a conference paper at ICLR 2022
Lemma 22. (Bernstein inequality for vector-valued martingales. Theorem 4.1 in Zhou al. 2020a)) Let {Gelt=1 be a filtration. {Ie, Tu h:21 stochastic process so that Ds RR is Gr- measurable and Tn E is G4+1 meeasurabl Fix R. L, 0, > O, nr" E Rd. For 2 1, let Yt (1,", (2)) n and suppose that Tı, 3t also satisfy
Imd R. Em [ol O, m 9i] S of ||ee|le S
(228)
Then, for any 0 < 8 < 1, with probability at least 1 6, have
Vt 0,
Σ 2,77
S Bcs l1 1. 1l SB + v VAllp"112
(229)
2,
where for t 2 1, = Z b, Zi = A + EE 2, b, Ei= aa and
= ddog (1 ( log (4t2 + 4Rlog (4t11).
(230)
35


Reviews:
[{"review_id": "rTr_bRozi3", "reviewer": "Reviewer_ZcuD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper makes a fundamental contribution to the reward-free exploration field. The proposed solution to the technical challenge of the Bernstein-type analysis under this scenario is novel. Moreover, the paper is well organized. \n\nHowever, several issues/limitations preclude me from fully accepting this paper. \n\n1. The claim of “near-optimal” does not appear suitable in my opinion, provided that (Jin et al., 2020) considered the tabular MDP. Can you explain more why this is a suitable argument? In particular, why can we translate the $S^2A$ term to $d^2$? To my understanding, the reduction between tabular and linear settings is strange/unsafe.  To see this, if we let $d=S^2 A$ (i.e.,  use the one-hot feature as the linear feature), the resultant upper bound $d^2$ becomes $O(S^{4}A^2)$. This upper bound (actually this translation) is not tight, compared with the lower bound in the tabular setting. \n\nI would suggest, if the authors agree, to adjust the language to be clear of this mismatch in problem settings between this paper and (Jin et al., 2020). This would make this paper’s place in the literature more clear.\n\n2. Under the linear mixture MDPs setting, there is no concrete optimization procedure for the $\\epsilon_\\text{opt}$-optimal model-based solver (a key assumption in this paper). This assumption can be well addressed if the state space is finite (see (Jin et al., 2020)). I do not aware of efficient optimization procedures when the state space is infinite. Can you provide some algorithms that satisfy this assumption when the state space is infinite?  I have the same question for several optimization steps in the algorithm design; for example, Line 9 in Algorithm 1 and Line 7 in Algorithm 2. \n\nThis issue would not significantly detract from the contribution of this paper, but it would be better if you could provide some possible solutions or provide some discussion. \n\n3. The sample complexity in Theorem 1 and Theorem 2 does not show the dependence on $B$ (i.e., the upper bound for the weight norm of $\\theta$ in Definition 1). Indeed, we cannot treat $B$ as a absolute constant because $B$ contains the state and action space size information. For instance, considering the one-hot feature $\\phi$, we have that $d=SAS$ and $\\Vert \\phi_{V}(s, a) \\Vert_2 \\leq \\sqrt{S}$ based on the definition $\\phi_{V}(s, a) = \\sum_{s^\\prime \\in \\mathcal{S}} \\phi(s, a, s^\\prime) V(s^\\prime)$. This contradicts with the assumption that $\\Vert \\phi_{V}(s, a) \\Vert_2 \\leq 1$. To resolve this issue, we can normalize the one-hot feature by dividing $1/\\sqrt{S}$. Consequently, to ensure that $P_h(s^\\prime | s, a) = \\theta_h^{\\top} \\phi(s, a, s^\\prime)$ is a valid transition, we could set $B = \\sqrt{S^2 A}$.\n\nI realize that previous literature somehow does not show the dependence on $B$. But it’s better to discuss this point, which could make the connection between tabular and linear settings more clear. Please correct me if my understanding is wrong.\n\n4. Some important steps in proposed algorithms are not well discussed. For instance, how to find a valid transition at Line 20 in Algorithm 1. A similar issue holds for Line 5 in Algorithm 2. I would suggest the authors involve more implementation details. \n\n\nSeveral sentences are confusing/misleading in this submission. I suggest revising these statements to improve clarity.\n\n1. “Compared to our results, the standard plug-in approach (Agarwal et al., 2020; Cui & Yang, 2020) requires reward signals to guide exploration”\n \nThere is no exploration issue in Agarwal et al., 2020. \n\n2. “Based on the Berstein inequality for vector-valued martingales”\n\nThere is a typo: Berstein -> Bernstein\n\n3. “Compared with the reward-free setting studied in the previous literature ...., the main difference is that we require that the algorithm maintains an model estimation instead of all the history samples after the exploration phase”\n\nThere is a typo: an model estimation -> a model estimation.\n\n4. “Then with probability at least 1 − $\\delta$, for any given reward”\n\nIn Theorem 1 and Theorem 2, “Then with probability 1-$\\delta$” should be posted before the first claim or the authors should clarify the randomness source. \n\n5. The paragraph below Lemma 3 seems incomplete since no conclusion is given. As a result, readers must combine Lemma 3 and Lemma 1 to infer the result that the authors want to claim. \n\n6. $R_K$ is not properly defined in (4).  Maybe you mean the concatenation of all one-step “exploration rewards” in iteration $K$? \n\n\nI would like to raise my score if the above concerns are addressed in the authors’ response.\n\n---\n\nDuring the review, I noticed that there is a related paper in the Arxiv. \n\nZhang, Weitong, Dongruo Zhou, and Quanquan Gu. \"Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation.\" arXiv preprint arXiv:2110.06394 (2021).  https://arxiv.org/abs/2110.06394\n\nAccording to the review guide, authors are excused for such a paper (i.e., the Arxiv paper would not affect my decision). But, I encourage authors to incorporate the following points to further improve the quality of this paper:\n1. Compare Algorithms 1 and 2 in this work with algorithms in (Zhang et al., 2021). \n2. Point out which steps/components/analyses in this paper lead to better results.\n3. Discuss involved optimization steps as Zhang et al. do. \n\n\n===========================\n\nAfter rebuttal, the authors have addressed my concern regarding the lower bound and computational details. Thus, I raise my score from 5 to 6.\n\n\n\n\n\n", "summary_of_the_paper": "This paper studies reward-free exploration with linear function approximation (i.e., under the setting of linear mixture MDPs). Specifically, this work introduces two algorithms: the first one has a simple form with the sample complexity $\\tilde{\\mathcal{O}}(d^2H^4 / \\varepsilon^2)$, and the second one is much complicated (i.e., with 5 estimators) but has an improved sample complexity $\\tilde{\\mathcal{O}}(d^2H^3 / \\varepsilon^2)$. To improve the dependence on $H$, the main technical challenge is that the traditional Bernstein-type analysis could not be directly applied because the variance summation of $\\{\\tilde{V}\\}_{h \\in [H]}$ is not induced from the same policy and transition function.  This paper addresses this technical challenge and makes a solid contribution to reward-free exploration.", "summary_of_the_review": "This paper improves the statistical sample complexity (in terms of $H$) for reward-free exploration with linear function approximation. Thus, this paper deserves to be accepted and I would raise my score if the mentioned concerns are addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fD1YjQsgZiU", "reviewer": "Reviewer_VReK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strength\n\n- S1. The theoretical results are strong and interesting.\n- S2. The paper did a good job such that readers can grasp the high level proof idea.\n\n# Weakness\n\n- W1. There are some typos. Also, there are some arguments and proofs that I can't quite follow.\n\n# Comments and Questions\n\n- C1. In abstract, I think it would be better to replace \"interactions\" in \"taking $\\mathcal{O} (d^2 H^3 / \\varepsilon^2)$ interactions...\" with episodes. I imagine the number of steps $KH$ by \"interactions\".\n- C2. How do you solve $\\max\\_{V \\in \\mathcal{V}} \\| \\phi\\_V (s, a) \\|\\_{\\Lambda\\_{k, h}^{-1}}$ for $V$ in practice? Is it possible to obtain the optimal $V$ analytically?\n- C3. In Page 5, it is said that \"By the reduction from the tabular reward-free RL problem ... the linear mixture model setting is $\\Omega (\\frac{d^2 H^3}{\\varepsilon^2})$\". It is not unclear for me how to get $d^2$ rather than $d$. Would you explain it a bit more? Also, it would be nice if $H^3$ dependence is formally derived.\n- C4. In the equation at the bottom of Page 4, $\\beta$ is unnecessary.\n- C5. In Page 5, $\\phi\\_{t, h} (s_h, a_h)$ should be defined as argmax rather than max, I think. \n- C6. In Eqn 7, I think $P$ in $u\\_{1, k, h}^{\\pi, P}$ should be $\\widetilde{P}$.\n- C7. In Eqn 15, don't you need $B$ on RHS? Is there any assumption on $H$, $d$ etc so that $B$ disappears?\n- C8. In Eqn 21, LHS should be $W_h ( \\{ R_h \\})$.\n- C9. In Eqn 29, is $\\widetilde{V}_1^{\\pi}$ defined anywhere? I can infer its meaning, though.\n- C10. In Eqn 49, $H$ seems to be missing in $\\log$?\n- C11. In Lemma 9, \"Under event $\\Lambda_1$\" should be \"Under event $\\mathcal{E}_1$\"?\n- C12. In the definition of the noise $\\eta_k$ below Eqn 90, $\\theta_h^*$ should be $\\theta_h$?\n- C13. In Eqn 91 and 92, don't you need $B$?\n- C14. In Lemma 16, $\\theta_\\star$ above Eqn 199 should be $\\theta\\_\\*$, I think. Also in Eqn 199, $\\widehat{\\theta}\\_t$ is undefined, and $\\theta$ should be $\\theta\\_\\*$.\n- C15. There are some places where $\\star$ is used instead of $*$.\n- C16. Maybe it is nice to have a list of notations. There are too many $V$ variants, and I needed to look for their definitions.", "summary_of_the_paper": "The paper propose and analyze a model-based algorithm for the reward-free exploration setting. The analysis shows that the proposed algorithm is (nearly) minimax optimal. The proposed algorithm is agnostic of the planning algorithm that is used to solve an MDP constructed with the estimated model. This property is of independent interest because it allows the computation of the value of the policies, and the estimated model can be used for any down-stream tasks. ", "summary_of_the_review": "I think the results are strong and interesting. There are many typos in equations. While typos are not serious but needs revision. I found some parts of the proofs that I don't quite follow (lacking $B$) and undefined notations.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "WiPy-9Qvst7", "reviewer": "Reviewer_kLwC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "After Response Update\n\nIn their replies, the authors have clarified my concerns regarding the lower bound and the computational tractability. They are incorporating useful changes in the paper, including a comparison with a relevant concurrent work. I am now fully convinced this is a valuable paper, and I am increasing my score accordingly.\n\n\n-------\n\nI provide below some detailed comments and doubts that the authors might address in their response.\n\nCOMPUTATIONAL TRACTABILITY\n\nI think the paper is somewhat missing an assessment of the tractability of the propose methods, and especially the computational complexity of the optimization problems involved. Can the authors clarify this point?\n\nLOWER BOUND\n\nThe paper provides a lower bound $\\Omega (H^3 d^2 \\epsilon^{-2})$ by reducing a previous result from tabular MDPs, i.e., $\\Omega (H^2 S^2 A \\epsilon^{-2})$ (Jin et al., 2020a). Can the authors clarify how this reduction is carried out? I would say that tabular MDPs can be obtained from a linear mixture MDPs with $d = S^2 A$. I see why there is an additional $H$ factor w.r.t. time-homogenous settings, but where is the additional $d$ factor coming from?\n\nCOMPARING SUB-OPTIMALITY\n\nThe sub-optimality guarantee of Theorems 1, 2 includes an additional $\\epsilon_{opt}$ term with respect to previous works, which instead provide $\\epsilon$-optimality guarantees. I am wondering if this should be intended as an unavoidable cost of the generality of the proposed method, which works with any planning solver, or there is a way to make a fair comparison with the complexity rates of previous works.\n\nRELATED WORK\n\nThe work (W. Zhang et al., Reward-free model-based reinforcement learning with linear function approximation, 2021) seems to be very much related to the setting of this paper. Even if this is very recent, and thus concurrent to this work, can the authors provide a brief discussion over similarities and differences of their approaches?  \n\nADDITIONAL REFERENCES\n\nReward-free RL is a relatively novel field, which does not count a huge number of works yet, thus I would suggest the authors to try to reference all of them, even if they are not crucially relevant or comparable to the proposed setting. E.g., they could consider adding:\n- Z. Zhang et al., Near optimal reward-free reinforcement learning, 2021;\n- W. Zhang et al., Reward-free model-based reinforcement learning with linear function approximation, 2021;\n- Qiu et al., On reward-free RL with kernel and neural function approximations, 2021;\n\nas well as works in the close task-agnostic setting:\n- X. Zhang and Singla, Task-agnostic exploration in reinforcement learning, 2020;\n- Wu et al., Gap-dependent unsupervised exploration for reinforcement learning, 2021;\n\nand multi-agent settings:\n- Bai and Jin, Provable self-play algorithms for competitive reinforcement learning, 2021;\n- Liu et al., A sharp analysis of model-based reinforcement learning with self-play, 2021.", "summary_of_the_paper": "This paper addresses the reward-free exploration problem with function approximation under linear mixture MDP assumption. It proposes a pair of model-based exploration algorithms, one with a lightweight methodology and sample complexity rate $\\tilde{O}(H^4 d^2 \\epsilon^{-2})$ and the other as a refined and more convoluted version with rate $\\tilde{O}(H^3 d^2 \\epsilon^{-2})$, which is matching the reported lower bound up to logarithmic factors. Crucially, the proposed approach can work with any planning solver to provide an $(\\epsilon + \\epsilon_{opt})$-optimal policy for any reward function.", "summary_of_the_review": "This works looks like a solid contribution to the reward-free RL literature. To the best of my knowledge, it provides the best known sample complexity rate for reward-free exploration under linear mixture assumptions (especially, it improves over W. Zhang et al. 2021 by a factor of H), and the best rate for a reward-free method that can work with any planning solver (e.g., Jin et al. 2020a, W. Zhang et al. 2021). \n\nSince I believe these improvements are valuable, I am providing a positive evaluation for this work. A careful inspection of the novelty of the analysis (especially w.r.t. Zhou et al. 2020a), as well as additional reassurances from the authors on some questions over the computational tractability of the proposed algorithms and the sample complexity lower bound, could make me consider raising my score towards an even stronger accept.\n\nI believe that extending the proposed analysis to improve known sample complexity rates under the looser linear MDP assumption, as the authors suggest in Section 4.2, would potentially increase the value of this work from solid to great.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses the reward-free exploration problem with function approximation under linear mixture MDP assumption. The analysis shows that the proposed algorithm is (nearly) minimax optimal.  The proposed approach can work with any planning solver to provide an ($\epsilon + \epsilon_{opt}$)-optimal policy for any reward function.

After reading the authors' feedback and discussing their concerns, the reviewers agree that the contributions in this paper are valuable and that this paper deserves publication.
I encourage the authors to follow the reviewers' suggestions as they will prepare the camera-ready version.
Decision: Accept (Spotlight)