On Reward-Free Reinforcement Learning with Linear Function Approximation

Introduction

In reinforcement learning (RL), an agent repeatedly interacts with an unknown environment to maximize the cumulative reward. To achieve this goal, RL algorithm must be equipped with exploration mechanisms to effectively solve tasks with long horizons and sparse reward signals. Empirically, there is a host of successes by combining deep RL methods with different exploration strategies. However, the theoretical understanding of exploration in RL by far is rather limited.

In this work we study the reward-free RL setting which was formalized in the recent work by Jin et al. (2020). There are two phases in the reward-free setting: the exploration phase and the planning phase. During the exploration phase, the agent collects trajectories from an unknown environment without any pre-specified reward function. Then, in the planning phase, a specific reward function is given to the agent, and the goal is to use samples collected during the exploration phase to output a near-optimal policy for the given reward function. From a practical point of view, this paradigm is particularly suitable for 1) the batch RL setting (Bertsekas and Tsitsiklis, 1996) where data collection and planning are explicitly separated and 2) the setting where there are multiple reward function of interest, e.g., constrained RL (Achiam et al., 2017; Altman, 1999; Miryoosefi et al., 2019; Tessler et al., 2018). From a theoretical point view, this setting separates the exploration problem and the planning problem which allows one to handle them in a theoretically principled way, in contrast to the standard RL setting where one needs to deal both problems simultaneously.

The sample complexity bound in (Jin et al., 2020), although being near-optimal in the tabular setting, can be unacceptably large in practice due to the polynomial dependency on the size of the state space. For environments with a large state space, function approximation schemes are needed for generalization. RL with linear function approximation is arguably the simplest yet most fundamental setting. Clearly, in order to understand more general function classes, e.g., deep neural networks, one must understand the class of linear functions first. In this paper, we study RL with linear function approximation in the reward-free setting, and our goal is to answer the following question:

Is it possible to design provably efficient RL algorithms with linear function approximation in the reward-free setting?

We obtain both polynomial upper bound and hardness result to the above question.

Our first contribution is a provably efficient algorithm for reward-free RL under the linear MDP assumption (Yang and Wang, 2019; Jin et al., 2019), which, roughly speaking, requires both the transition operators and the reward functions to be linear functions of a $d$-dimensional feature extractor given to the agent. See Assumption 2.1 for the formal statement of the linear MDP assumption. Our algorithm, formally presented in Section 3, samples $\widetilde{O}\left(d^{3}H^{6}/\varepsilon^{2}\right)$ trajectories during the exploration phase, and outputs $\varepsilon$-optimal policies for an arbitrary number of reward functions satisfying Assumption 2.1 during the planning phase with high probability. Here $d$ is the feature dimension, $H$ is the planning horizon and $\varepsilon$ is the required accuracy.

One may wonder whether is possible to further weaken the linear MDP assumption, since it requires the feature extractor to encode model information, and such feature extractor might be hard to construct in practice. Our second contribution is a hardness result for reward-free RL under the linear $Q^{*}$ assumption, which only requires the optimal value function to be a linear function of the given feature extractor and thus weaker than the linear MDP assumption. Our hardness result, formally presented in Section 4, shows that under the linear $Q^{*}$ assumption, any algorithm requires exponential number of samples during the exploration phase, so that the agent could output a near-optimal policy during the planning phase with high probability. The hardness result holds even when the MDP is deterministic.

Our results highlight the following conceptual insights.

Reward-free RL might require the feature to encode model information. Under model-based assumption (linear MDP assumption), there exists a polynomial sample complexity upper bound for reward-free RL, while under value-based assumption (linear $Q^{*}$ assumption), there is an exponential sample complexity lower bound. Therefore, the linear $Q^{*}$ assumption is strictly weaker than the linear MDP assumption in the reward-free setting.

Reward-free RL could be exponentially harder than standard RL. For deterministic systems, under the assumption that the optimal $Q$-function is linear, there exists a polynomial sample complexity upper bound (Wen and Van Roy, 2013) in the standard RL setting. However, our hardness result demonstrates that under the same assumption, any algorithm requires exponential number of samples in the reward-free setting.

Simulators could be exponentially more powerful. In the setting where the agent has sampling access to a generative model (a.k.a. simulator) of the MDP, the agent can query the next state $s^{\prime}$ sampled from the transition operator given any state-action pair as input. In the supplementary material, we show that for deterministic systems, under the linear $Q^{*}$ assumption, there exists a polynomial sample complexity upper bound in the reward-free setting when the agent has sampling access to a generative model. Compared with the hardness result above, this upper bound demonstrates an exponential separation between the sample complexity of reward-free RL in the generative model and that in the standard RL model. To the best our knowledge, this is the first exponential separation between the standard RL model and the generative model for a natural question.

1 Related Work

This paper studies linear function approximation. Linear MDP is the setting where both the transition and the reward are linear functions of a given feature extractor. Recently, in the standard RL setting, many works (Yang and Wang, 2019; Jin et al., 2019; Cai et al., 2020; Zanette et al., 2019) have provided polynomial sample complexity guarantees for different algorithms in linear MDPs. Technically, our algorithm, which works in the reward-free setting, combines the algorithmic framework in (Jin et al., 2019) with a novel exploration-driven reward function (cf. Section 3). Linear $Q^{*}$ is another setting where only the optimal $Q$-function is assumed to be linear, which is weaker than the assumptions in the linear MDP setting. In the standard RL setting, it is an open problem whether one can use polynomial number of samples to find a near-optimal policy in the linear $Q^{*}$ setting (Du et al., 2020a). Existing upper bounds all require additional assumptions, such as (nearly) deterministic transition Wen and Van Roy (2013); Du et al. (2019b, 2020b).

Preliminaries

Throughout this paper, for a given positive integer $N$, we use $[N]$ to denote the set $\{1,2,\ldots,N\}$.

When the initial distribution $\mu$ and the transition operators $P=\{P_{h}\}_{h=1}^{H}$ are all deterministic, we say $\mathcal{M}$ is a deterministic system. In this case, we may regard each transition operator $P_{h}:\mathcal{S}\times\mathcal{A}\to\mathcal{S}$ as a function that maps state-action pairs to a states. We note that deterministic systems are special cases of general MDPs.

A policy $\pi$ chooses an action $a\in\mathcal{A}$ based on the current state $s\in\mathcal{S}$ and the time step $h\in[H]$. Formally, $\pi=\{\pi_{h}\}_{h=1}^{H}$ where for each $h\in[H]$, $\pi_{h}:\mathcal{S}\to\mathcal{A}$ maps a given state to an action. The policy $\pi$ induces a trajectory $s_{1},a_{1},r_{1},s_{2},a_{2},r_{2},\ldots,s_{H},a_{H},r_{H}$, where $s_{1}\sim\mu$, $a_{1}=\pi_{1}(s_{1})$, $r_{1}=r_{1}(s_{1},a_{1})$, $s_{2}\sim P(s_{1},a_{1})$, $a_{2}=\pi_{2}(s_{2})$, $r_{2}=r_{2}(s_{2},a_{2})$, etc.

An important concept in RL is the $Q$-function. For a specific set of reward functions $r=\{r_{h}\}_{h=1}^{H}$, given a policy $\pi$, a level $h\in[H]$ and a state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, the $Q$-function is defined as

Similarly, the value function of a given state $s\in\mathcal{S}$ is defined as

For a specific set of reward functions $r=\{r_{h}\}_{h=1}^{H}$, We use $\pi^{*}_{r}$ to denote an optimal policy with respect to $r$, i.e., $\pi^{*}_{r}$ is a policy that maximizes

We also denote $Q_{h}^{*}(s,a,r)=Q_{h}^{\pi^{*}_{r}}(s,a,r)$ and $V_{h}^{*}(s,r)=V_{h}^{\pi^{*}_{r}}(s,r)$. We say a policy $\pi$ is $\varepsilon$-optimal with respect to $r$ if

Throughout the paper, when $r$ is clear from the context, we may omit $r$ from $Q_{h}^{\pi}(s,a,r)$, $V_{h}^{\pi}(s,r)$, $Q_{h}^{*}(s,a,r)$, $V_{h}^{*}(s,r)$ and $\pi^{*}_{r}$.

2 Linear Function Approximation

The following linear MDP assumption, which was first introduced in (Yang and Wang, 2019; Jin et al., 2019), states that the model of the MDP can be predicted by linear functions of the given features.

An MDP $\mathcal{M}=\left(\mathcal{S},\mathcal{A},P,r,H,\mu\right)$ is said to be a linear MDP if the followings hold:

there are $d$ unknown signed measures $\mu_{h}=(\mu_{h}^{(1)},\mu_{h}^{(2)},\ldots,\mu_{h}^{(d)})$ such that for any $(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$, $P_{h}\left(s^{\prime}\mid s,a\right)=\left\langle\mu_{h}(s^{\prime}),\phi\left(s,a\right)\right\rangle$;

As in (Jin et al., 2019), we assume for all $(s,a)\in\mathcal{S}\times\mathcal{A}$ and $h\in[H]$, $\left\|\phi(s,a)\right\|\leq 1$, $\left\|\mu_{h}(S)\right\|_{2}\leq\sqrt{d}$, and $\left\|\eta\right\|_{2}\leq\sqrt{d}$.

The following linear $Q^{*}$ assumption, which is a common assumption in the theoretical RL literature (see e.g. (Du et al., 2019b, 2020a)), states that the optimal $Q$-function can be predicted by linear functions of the given features.

We note that Assumption 2.2 is weaker than Assumption 2.1. Under Assumption 2.1, it can be shown that for any policy $\pi$, $Q_{h}^{\pi}(\cdot,\cdot)$ is a linear function of the given feature extractor $\phi(\cdot,\cdot)$. In this paper, we show that Assumption 2.2 is strictly weaker than Assumption 2.1 in the reward-free setting, meaning that reward-free RL under Assumption 2.2 is exponentially harder than that under Assumption 2.1.

3 Reward-Free RL

In the reward-free setting, the goal is to design an algorithm that efficiently explore the state space without the guidance of reward information. Formally, there are two phases in the reward-free setting: exploration phase and planning phase.

During the exploration phase, the agent interacts with the environment for $K$ episodes. In the $k$-th episode, the agent chooses a policy $\pi^{k}$ which induces a trajectory. The agent observes the states and actions $s_{1}^{k},a_{1}^{k},s_{2}^{k},a_{2}^{k},\ldots,s_{h}^{k},a_{h}^{k}$ as usual, but does not observe any reward values. After $K$ episodes, the agent collects a dataset of visited state-actions pairs $\mathcal{D}=\{(s_{h}^{k},a_{h}^{k})\}_{(k,h)\in[K]\times[H]}$ which will be used in the planning phase.

Planning Phase.

During the planning phase, the agent is no longer allowed to interact with the MDP. Instead, the agent is given a set of reward functions $\{r_{h}\}_{h=1}^{H}$ where $r_{h}:\mathcal{S}\times\mathcal{A}\rightarrow$ is the deterministic reward function in level $h$, and the goal here is to output an $\varepsilon$-optimal policy with respect to $r$ using the collected dataset $\mathcal{D}$.

To measure the performance of an algorithm, we define the sample complexity to be the number of episodes $K$ required in the exploration phase to output an $\varepsilon$-optimal policy in the planning phase.

Reward-Free RL for Linear MDPs

In this section, we present our reward-free RL algorithm under the linear MDP assumption.

The exploration phase of the algorithm is presented in Algorithm 1, and the planning phase is presented in Algorithm 2.

During the exploration phase of the algorithm, we employ the least-square value iteration (LSVI) framework introduced in (Jin et al., 2019). In each episode, we first update the parameters $(\Lambda_{h},w_{h})$ that are used to calculate the $Q$-functions, and then execute the greedy policy with respect to the updated $Q$-function to collect samples. As in (Jin et al., 2019), to encourage exploration, Algorithm 1 adds an upper-confidence bound (UCB) bonus function $u_{h}$.

The main difference between Algorithm 1 and the one in (Jin et al., 2019) is the definition of the exploration-driven reward function. Since the algorithm in (Jin et al., 2019) is designed for the standard RL setting, the agent can obtain reward values by simply interacting with the environment. On the other hand, in the exploration phase of the reward-free setting, the agent does not have any knowledge about the reward function. In our algorithm, in each episode, we design an exploration-driven reward function which is defined to be $r_{h}(\cdot,\cdot)=u_{h}(\cdot,\cdot)/H$, where $u_{h}(\cdot,\cdot)$ is the UCB bonus function defined in Line 8. Note that we divide $u_{h}(\cdot,\cdot)$ by $H$ so that $r_{h}(\cdot,\cdot)$ always lies in $$. Intuitively, such a reward function encourages the agent to explore state-action pairs where the amount of uncertainty (quantified by$u_{h}(\cdot,\cdot)$) is large. After sufficient number of episodes, the uncertainty of all state-action pairs should be low on average, since otherwise the agent would have visited those state-action pairs with large uncertainty as guided by the reward function.

Planning Phase.

After the exploration phase, the returned dataset contains sufficient amount of information for the planning phase. In the planning phase (Algorithm 2), for each step $h=H,H-1,\ldots,1$, we optimize a least squares predictor to predict the $Q$-function, and return the greedy policy with respect to the predicted $Q$-function. During the planning phase, we still add an UCB bonus function $u_{h}(\cdot,\cdot)$ to guarantee optimism. However, as mentioned above and will be made clear in the analysis, since the agent has acquired sufficient information during the exploration phase, $u_{h}(\cdot,\cdot)$ should be small on average, which implies the returned policy is near-optimal.

2 Analysis

In this section we outline the analysis of our algorithm. The formal proof is deferred to the supplementary material. We first give the formal theoretical guarantee of our algorithm.

After collecting $O\left(d^{3}H^{6}\log(dH\delta^{-1}\varepsilon^{-1})/\varepsilon^{2}\right)$ trajectories during the exploration phase, with probability $1-\delta$, our algorithm outputs an $\varepsilon$-optimal policy for an arbitrary number of reward functions satisfying Assumption 2.1 during the planning phase.

Now we show how to prove Theorem 3.1. Our first lemma shows that the estimated value functions $V^{k}$ are optimistic with high probability, and the summation of $V^{k}_{1}(s_{1}^{k})$ should be small.

With probability $1-\delta/2$, for all $k\in[K]$,

for some constant $c>0$ where $V^{k}_{1}(\cdot)$ is as defined in Algorithm 1.

Note that the definition of the exploration driven reward function $r^{k}$ used in the $k$-th episode depends only on samples collected during the first $k-1$ episodes. Therefore, the first part of the proof is nearly identical to that of Theorem 3.1 in (Jin et al., 2019). To prove the second part of the lemma, we first recursively decompose $V^{k}_{1}(s_{1}^{k})$ (similar to the standard regret decomposition for optimistic algorithms), and then use the fact that $r_{h}(\cdot)=u_{h}(\cdot)/H$ and the elliptical potential lemma in (Abbasi-Yadkori et al., 2012) to given an upper bound on $\sum_{k=1}^{K}V^{k}_{1}(s_{1}^{k})$. The formal proof is provided in the supplementary material.

Our second lemma shows that with high probability, if one divides the bonus function $u_{h}(\cdot,\cdot)$ (defined in Line 5 in Algorithm 2) by $H$ and uses it as a reward function, then the optimal policy has small cumulative reward on average.

With probability $1-\delta/4$, for the function $u_{h}(\cdot,\cdot)$ defined in Line 5 in Algorithm 2, we have

for some absolute constant $c^{\prime}>0$.

for all $k\in[K]$, which implies the desired result.

Our third lemma states the estimated $Q$-function is always optimistic, and is upper bounded by $r_{h}(\cdot,\cdot)+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid\cdot,\cdot)V_{h+1}(s^{\prime})$ plus the UCB bonus function $u_{h}(\cdot,\cdot)$. The lemma can be proved using the same concentration argument as in (Jin et al., 2019).

With probability $1-\delta/2$, for an arbitrary number of reward functions satisfying Assumption 2.1 and all $h\in[H]$, we have

Now we sketch how to prove Theorem 3.1 by combining Lemma 3.2 and Lemma 3.3. Note that With probability $1-\delta$, the events defined in Lemma 3.2 and Lemma 3.3 both hold. Conditioning on both events, we have

where the first inequality follows by Lemma 3.3, the second inequality follows by Lemma 3.3 and decomposing the $V$-function recursively, the third inequality follows by the definition of $V^{*}$, and the last inequality follows by Lemma 3.2.

In this section we prove lower bound for reward-free RL under the linear $Q^{*}$ assumption. We show that there exists a class of MDPs which satisfies Assumption 2.2, such that any reward-free RL algorithm requires exponential number of samples during the exploration phase in order to find a near-optimal policy during the planning phase. In particular, we prove the following theorem.

Since deterministic systems are special cases of general MDPs, the hardness result in Theorem 4.1 applies to general MDPs as well. In the remaining part of this section, we describe the construction of the hard instance and outline the proof of Theorem 4.1.

In the hard instance, there are $H$ levels of states

where $\mathcal{S}_{h}$ contains all states that can be reached in level $h$. The action space $\mathcal{A}=\{0,1\}$. For each $h\in[H-2]$, we represent each state in $\mathcal{S}_{h}$ by an integer in $[2^{h-1},2^{h})$, i.e., $\mathcal{S}_{1}=\{1\}$, $\mathcal{S}_{2}=\{2,3\}$, $\mathcal{S}_{3}=\{4,5,6,7\}$, etc. We also have $S_{H-1}=\{s_{H-1}^{+},s_{H-1}^{-}\}$ and $S_{H}=\{s_{H}^{+},s_{H}^{-}\}$. The initial states is $1\in\mathcal{S}_{1}$.

Transition.

For each $h\in[H-3]$, for each $s\in\mathcal{S}_{h}$, $P_{h}(s,a)$ is fixed and thus known to the algorithm. In particular, for each $h\in[H-3]$, for each $s\in\mathcal{S}_{h}$, we define $P_{h}(s,a)=2s+a\in\mathcal{S}_{h+1}$ where $a\in\{0,1\}$. We will define the transition operator for those states $s\in\mathcal{S}_{H-2}\cup\mathcal{S}_{H-1}$ shortly.

Feature Extractor.

For all states $s\in\mathcal{S}_{H-1}$, we define

Finally, for all states $s\in\mathcal{S}_{H}$, we define

The Hard MDPs.

By Yao’s minimax principle (Yao, 1977), to prove a lower bound for randomized algorithms, it suffices to define a hard distribution and show that any deterministic algorithm fails for the hard distribution. We now define the hard distribution. We first define the transition operator $P_{H-2}(s,a)$ for those states $s\in\mathcal{S}_{H-2}$. To do this, we first pick a state-action pair $(s_{H-2}^{*},a_{H-2}^{*})$ from $\mathcal{S}_{H-2}\times\mathcal{A}$ uniformly at random, and define

To define the transition function $P_{H-1}(s,a)$ for those states $s\in\mathcal{S}_{H-1}$, we pick a random action $a^{*}_{H-1}$ from $\{0,1\}$ uniformly at random, and define

The Reward Function.

We now define the optimal $Q$-function which automatically implies a set of reward function $r=\{r_{h}\}_{h=1}^{H}$. During the planning phase, the agent will receive $r$ as the reward functions. By construction, there exists a unique trajectory $s_{1}^{*},a_{1}^{*},s_{2}^{*},a_{2}^{*},\ldots,s_{H-1}^{*},a_{H-1}^{*},s_{H}^{*},a_{H}^{*}$ with $(s_{H}^{*},a_{H}^{*})=(s_{H}^{+},0)$. For each $h\in[H]$, we define $\theta_{h}$ in Assumption 2.2 as $\phi(s_{h}^{*},a_{h}^{*})/2$. This implies that for each $(s,a)\in\mathcal{S}_{H}\times\mathcal{A}$,

For each $(s,a)\in\mathcal{S}_{H-1}\times\mathcal{A}$, we have

which implies that $r_{H-1}(s,a)=0$ for all $(s,a)\in\mathcal{S}_{H-1}\times\mathcal{A}$. Now for each $h\in[H-2]$, for each $(s,a)\in\mathcal{S}_{h}\times\mathcal{A}$, we define $r_{h}(s_{h},a_{h})=Q^{*}_{h}(s_{h},a_{h})-\max_{a\in\mathcal{A}}Q^{*}_{h+1}(\cdot,a)$ so that the Bellman equations hold. Moreover, by construction, for each $h\in[H]$, we have $Q^{*}_{h}(s,a)=0.5$ when $(s,a)=(s_{h}^{*},a_{h}^{*})$, and $|Q^{*}_{h}(s,a)|\leq 0.01$ when $(s,a)\neq(s_{h}^{*},a_{h}^{*})$ and thus $r_{h}(\cdot,\cdot)\in[-0.02,0.5]$.Note that this is slightly different from the assumption that $r_{h}(\cdot,\cdot)\in$. However, this can be readily fixed by shifting all reward values by $0.02$.

Proof of Hardness.

Now we sketch the final proof of the hardness result. We define $\mathcal{E}$ to be the event that for all $(s,a)\in\mathcal{D}$ where $\mathcal{D}$ are the state-action pairs collected by the algorithm, we have $s\neq s_{H-1}^{*}=s_{H-1}^{+}$. For any deterministic algorithm, we claim that if the algorithm samples at most $2^{H}/100$ trajectories during the exploration phase, with probability at least $0.9$ over the randomness of the distribution of MDPs, $\mathcal{E}$ holds. This is because the feature extractor is fixed and thus the algorithm receives the same feedback before reaching $s_{H-1}^{+}$. Since there are $2^{H-2}$ state-action pairs $(s,a)\in\mathcal{S}_{H-2}\times\mathcal{A}$ and only one of them satisfies $P_{H-2}(s,a)=s_{H-1}^{+}$, and the algorithm samples at most $2^{H}/100$ trajectories during the exploration phase, $\mathcal{E}$ holds with probability at least $0.9$.

Now during the planning phase, by construction of the optimal $Q$-function, the only $0.1$-optimal policy is $\pi_{h}(s_{h}^{*})=a_{h}^{*}$. However, conditioned on $\mathcal{E}$, any deterministic algorithm correctly output $\pi_{H-1}(s_{H-1}^{*})=a_{H-1}^{*}$ with probability at most $0.5$, since conditioned on $\mathcal{E}$, $\mathcal{D}$ does not contain $s_{H-1}^{*}$, and the set of reward functions $r=\{r_{h}\}_{h=1}^{H}$ also does not depend on $a_{H-1}^{*}$. Therefore, during the planning phase of the algorithm, a $0.1$-optimal policy is found with probability at most $0.6<0.9$.

Conclusion

This paper provides both positive and negative results for reward-free RL with linear function approximation. Our results imply three new exponential separations: 1) linear MDP v.s. linear $Q^{*}$, 2) standard RL v.s. reward-free RL, and 3) query with a simulator v.s. query without a simulator. An interesting future direction is to generalize our results to more general function classes using techniques, e.g., in (Wen and Van Roy, 2013; Ayoub et al., 2020; Wang et al., 2020).

Acknowledgments

RW and RS are supported in part by NSF IIS1763562, AFRL CogDeCON FA875018C0014, and DARPA SAGAMORE HR00111990016. SSD is supported by NSF grant DMS-1638352 and the Infosys Membership.

References

Appendix A Missing Proofs in Section 3

In this section, for all $(k,h)\in[K]\times[H]$, we denote

Since $K=c_{K}\cdot d^{3}H^{6}\log(dH\delta^{-1}\varepsilon^{-1})/\varepsilon^{2}$, we have

for appropriate choices of $c_{\beta}$ and $c_{K}$.

To prove Lemma 3.1, we need a concentration lemma similar to Lemma B.3 in [Jin et al., 2019].

Suppose Assumption 2.1 holds. Let $\mathcal{E}$ be the event that for all $(k,h)\in[K]\times[H]$,

for some absolute constant $c>0$. Then $\Pr[{\mathcal{E}}]\geq 1-\delta/4$.

The proof is nearly identical to that of Lemma B.3 in [Jin et al., 2019]. The only deference in our case is that we have a different reward functions at different episodes. However, note that in our case

Thus our value function $V^{k}_{h+1}$ is of the form

In our proof, we condition on the event $\mathcal{E}$ defined in Lemma A.1, which holds with probability at least $1-\delta/4$. Since $P_{h}(s^{\prime}|s,a)=\phi(s,a)^{\top}\mu_{h}(s^{\prime})$, we have

is an unknown vector. By Assumption 2.1, $\sum_{s^{\prime}\in\mathcal{S}}\mu_{h}(s^{\prime})\leq\sqrt{d}$. Therefore,

We thus have, for all $(h,k)\in[H]\times[K]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,

Now we prove the first part of the lemma.

Our proof is by induction on $h$. Indeed, for $h=H+1$, it holds that for all $s\in\mathcal{S}$,

since $V_{H+1}^{*}=V_{H+1}^{k}=0$. Suppose for some $h\in[H]$, it holds that for all $s\in\mathcal{S}$,

Notice that for all $(s,a)\in\mathcal{S}\times\mathcal{A}$,

Second Part.

To prove the second part, for all $(k,h)\in[K]\times[H-1]$, we denote

Note that for each $h\in[H-1]$, $\{\xi_{h}^{k}\}_{k=1}^{K}$ is a martingale difference sequence with $|\xi_{h}^{k}|\leq H$. Define $\mathcal{E}^{\prime}$ to be the even that

By Azuma–Hoeffding inequality, we have $\Pr[\mathcal{E}^{\prime}]\geq 1-\delta/4$.

By Lemma D.2 in [Jin et al., 2019], we have

Conditioned on $\mathcal{E}\cap\mathcal{E}^{\prime}$ which holds with probability at least $1-\delta/2$, we have

A.2 Proof of Lemma 3.2

which we condition on in the rest of the proof. Therefore, we have,

Hence we have for all $(k,h)\in[K]\times[H]$,

for some absolute constant $c^{\prime}>0$. ∎

A.3 Proof of Lemma 3.3

Using the same argument in the proof of Lemma 3.1, with probability at least $1-\delta/4$, for all $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, we have

Therefore, for all $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,

Moreover, $Q_{h}(s,a)\leq H$. Since $u_{h}(\cdot,\cdot)=\min\left\{\beta\cdot\sqrt{\phi(\cdot,\cdot)^{\top}(\Lambda_{h})^{-1}\phi(\cdot,\cdot)},H\right\}$, we have

Now we prove for all $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, $Q^{*}_{h}(s,a,r)\leq Q_{h}(s,a)$. We prove by induction on $h$. When $h=H+1$ this is clearly true. Suppose for some $h\in[H]$, $Q^{*}_{h+1}(s,a,r)\leq Q_{h+1}(s,a)$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$. We have

Since $Q^{*}_{h+1}(s,a,r)\leq H$ and $u_{h}(\cdot,\cdot)=\min\left\{\beta\cdot\sqrt{\phi(\cdot,\cdot)^{\top}(\Lambda_{h})^{-1}\phi(\cdot,\cdot)},H\right\}$, it suffices to prove that

A.4 Proof of Theorem 3.1

In our proof we condition on the events defined in Lemma 3.2 and Lemma 3.3 which hold with probability at least $1-\delta$. By Lemma 3.3, for any $s\in\mathcal{S}$,

By definition of $V^{*}_{1}(s,u)$, we have

By taking $K=c_{K}\cdot d^{3}H^{6}\log(dH\delta^{-1}\varepsilon^{-1})/\varepsilon^{2}$ for a sufficiently large constant $c_{K}>0$, we have

which implies $\pi$ is $\varepsilon$-optimal with respect to $r$. ∎

In this section, we present an algorithm for reward-free RL under the linear $Q^{*}$ assumption (Assumption 2.2) in deterministic systems, when the agent has access to a generative model (a.k.a. simulator) of the MDP. More specifically, for each state action $(s,a)\in\mathcal{S}\times\mathcal{A}$, for each $h\in[H]$, we assume the agent can query $P_{h}(s,a)$. We show that after querying the transition operator for polynomial number of times during the exploration phase, during the planning phase, the agent can find an optimal policy for any given reward function $r$.

The exploration phase of our algorithm is described in Algorithm 3, while the planning phase is described in Algorithm 4.

During the exploration phase, for each level $h$, we find $(s_{h}^{1},a_{h}^{1}),(s_{h}^{2},s_{h}^{2}),\ldots,(s_{h}^{d},a_{h}^{d})$ such that

Notice that during the exploration phase, the algorithm query the transition operator for $dH$ times in total. To prove the correctness, we prove by induction on $h$ that during the planning phase, $Q_{h}(\cdot,\cdot)=Q^{*}_{h}(\cdot,\cdot)$. Note that this is clearly true when $h=H+1$. Suppose $Q_{h+1}(\cdot,\cdot)=Q^{*}_{h+1}(\cdot,\cdot)$. It is clear that $V_{h+1}(\cdot)=V^{*}_{h+1}(\cdot)$, which implies $Q_{h}(s^{i}_{h},a^{i}_{h})=Q_{h}^{*}(s^{i}_{h},a^{i}_{h})$ by the Bellman equation. By Assumption 2.2, if $\phi(s,a)=\sum_{i=1}^{d}\beta_{i}\cdot\phi(s^{i}_{h},a^{i}_{h})$,

Appendix C Missing Proofs in Section 4

$|\phi_{i}^{\top}\phi_{j}|\leq 0.01$ for all $i,j\in[2^{H}]$ with $i\neq j$.

This is a direct implication of Lemma A.1 in [Du et al., 2020a] by setting $n=2^{H}$ and $\varepsilon=0.01$. ∎

Note that the above lemma implies the existence of the required feature exactor, since for each $h\in[H-2]$, there are less than $2^{H}$ state-action pairs in $\mathcal{S}_{h}\times\mathcal{A}$. We simply define the feature of the $i$-th state-action pair in $\mathcal{S}_{h}\times\mathcal{A}$ to be $\phi_{i}$ in the above lemma.

In order to prove Theorem 4.1, by Yao’s minimax principle [Yao, 1977], it suffices to prove that for the hard distribution constructed in Section 4, for any deterministic algorithm $\mathcal{A}$ that samples at most $2^{H}/100$ trajectories during the exploration phase, the probability (over the randomness of the hard distribution) that $\mathcal{A}$ outputs a $0.1$-optimal policy in the planning phase is at most $0.9$.

We first show that for the deterministic algorithm $\mathcal{A}$, among all the $2^{H-2}$ choices for $(s_{H-2}^{*},a_{H-2}^{*})$, $s_{H-1}^{+}$ is in the collected dataset $\mathcal{D}$ for at most $2^{H}/100$ choices for $(s_{H-2}^{*},a_{H-2}^{*})$ during the exploration phase. Note that whenever $(s_{H-2},a_{H-2})\neq(s_{H-2}^{*},a_{H-2}^{*})$, we must have $s_{H-1}=s_{H-1}^{-}$ and $s_{H}=s_{H}^{-}$. Therefore, the feedback received by $\mathcal{A}$ is always the same unless $(s_{H-2},a_{H-2})=(s_{H-2}^{*},a_{H-2}^{*})$. However, since $\mathcal{A}$ samples at most $2^{H}/100$ trajectories during the exploration phase, there are most $2^{H}/100$ choices for $(s_{H-2}^{*},a_{H-2}^{*})$ during the exploration phase for which $s_{H-1}^{+}$ is in the collected dataset $\mathcal{D}$.

Recall that $\mathcal{A}$ is deterministic. For any choice of $(s_{H-2}^{*},a_{H-2}^{*})$, if $s_{H-1}^{+}$ is not in the collected dataset $\mathcal{D}$, the collected dataset $\mathcal{D}$ is always the same, no matter $a_{H-1}^{*}=0$ or $a_{H-1}^{*}=1$. Moreover, for any fixed choice of $(s_{H-2}^{*},a_{H-2}^{*})$, it can be verified that the reward function $r$ does not depend on the choice of $a_{H-1}^{*}$. Note that during the planning phase, algorithm $\mathcal{A}$ deterministically maps the collected dataset $\mathcal{D}$ and the reward function $r$ to a policy. Furthermore, the only $0.1$-optimal policy must satisfy $\pi(s_{h}^{*})=a_{h}^{*}$. However, for any choice of $(s_{H-2}^{*},a_{H-2}^{*})$, if $s_{H-1}^{+}$ is not in the collected dataset $\mathcal{D}$, $\pi(s_{H-1}^{*})$ does not depend on $a_{H-1}^{*}$ since both the collected dataset $\mathcal{D}$ and the reward function $r$ do not depend on $a_{H-1}^{*}$. Therefore, for those choices of $(s_{H-2}^{*},a_{H-2}^{*})$, $\mathcal{A}$ outputs a $0.1$-optimal policy with probability at most $0.5$. Therefore, the probability that $\mathcal{A}$ outputs a $0.1$-optimal policy is at most