Reward-Free Exploration for Reinforcement Learning

Introduction

In reinforcement learning (RL), an agent repeatedly interacts with an unknown environment with the goal of maximizing its cumulative reward. To do so, the agent must engage in exploration, learning to visit states in order to investigate whether they hold high reward.

Exploration is widely regarded as the most significant challenge in RL, because the agent may have to take precise sequences of actions to reach states with high reward. Here, simple randomized exploration strategies provably fail: for example, a random walk can take exponential time to reach the corner of the environment where the agent can accummulate high reward (Li, 2012). While reinforcement learning has seen a tremendous surge of recent research activity, essentially all of the standard algorithms deployed in practice employ simple randomization or its variants, and consequently incur extremely high sample complexity.

On the other hand, sophisticated exploration strategies which deliberately incentivize the agent to visit new states are provably sample-efficient (c.f., Kearns and Singh (2002); Brafman and Tennenholtz (2002); Azar et al. (2017); Dann et al. (2017); Jin et al. (2018)), with recent work providing a nearly-complete theoretical understanding for maximizing a single prespecified reward function Dann and Brunskill (2015); Azar et al. (2017); Zanette and Brunskill (2019); Simchowitz and Jamieson (2019). In practice, however, reward functions are often iteratively engineered to encourage desired behavior via trial and error (e.g. in constrained RL formulations (Altman, 1999; Achiam et al., 2017; Tessler et al., 2018; Miryoosefi et al., 2019)). In such cases, repeatedly invoking the same reinforcement learning algorithm with different reward functions can be quite sample inefficient.

One solution to avoid excessive data collection in such settings is to first collect a dataset with good coverage over all possible scenarios in the environment, and then apply a “Batch-RL” algorithm. Indeed many algorithms are known for computing near optimal policies from previously collect data, provided that the dataset has good coverage (Munos and Szepesvári, 2008; Antos et al., 2008; Chen and Jiang, 2019; Agarwal et al., 2019). However, prior work provides little guidance into how to obtain such good coverage.

In this paper, we aim to develop an end-to-end instantiation of this proposal. To this end we ask:

How can we efficiently explore an environment without using any reward information?

In particular, by exploring the environment, we aim to gather sufficient information so that we can compute the near-optimal policies for any reward function after-the-fact.

In this paper, we present the first near-optimal upper and lower bounds which characterize the sample complexity of achieving provably sufficient coverage for Batch-RL. We do so by adopting a novel “reward-free RL” paradigm: During an exploration phase, the agent collects trajectories from an MDP $\mathcal{M}$ without a pre-specified reward function. Then, in a planning phase, it is tasked with computing near-optimal policies under the transitions of $\mathcal{M}$ for a large collection of given reward functions.

Our exploration phase is conceptually simple, using an existing RL algorithm as a black-box (Zanette and Brunskill, 2019), and our planning phase accommodates arbitrary Batch-RL solvers. We instantiate our result with value iteration and natural policy gradient as special cases. By decoupling exploration and planning, our work sheds light on the algorithmic mechanisms required for sample efficient reinforcement learning. We hope that this insight will be useful in the design of provably efficient algorithms for more practically relevant RL settings, such as those where function approximation is required.

In addition to our algorithmic results, we establish a nearly-matching $\Omega(S^{2}AH^{2}/\epsilon^{2})$ lower bound, demonstrating the near-optimality of our algorithm in this paradigm. Notably, this lower bound quantifies a price of “good-coverage” in the reward-free setting: while RL with a pre-specified reward has sample complexity of only $\widetilde{\Theta}(SAH^{2}/\epsilon^{2})$ (Dann and Brunskill, 2015), the reward-free sample complexity is a factor of $S$ larger.

The main technical challenge in our work involves handling environments with states that are difficult to reach. In such cases, we cannot learn the transition operator to high accuracy uniformly over the environment, simply because we cannot reach these states to collect enough data. With $\lambda(s)$ denoting the maximal probability of visiting state $s$ under any policy, our key observation is that we can partition the state space into two groups: the states with $\lambda(s)$ so small that they have negligible contribution to reward optimization, and the rest. We introduce a rigorous analysis which enables us to “ignores” the difficult-to-visit states altogether and only requires that we visit the remaining states with probability proportional $\lambda(s)$. To achieve this latter guarantee, we conduct our exploration with the Euler algorithm (Zanette and Brunskill, 2019), which in our context yields refined sample complexity guarantees in terms of $\lambda(s)$. We believe that this decomposition of states into their ease of being reached may be of broader interest. Our lower bound also adopts a novel and sophisticated construction, detailed in Section 4.

For reward-free exploration in the tabular setting, we are aware of only a few prior approaches. First, when one runs a PAC-RL algorithm like RMax with no reward function (Brafman and Tennenholtz, 2002), it does visit the entire state space and can be shown to provide a coverage guarantee. However, for RMax in particular the resulting sample complexity is quite poor, and significantly worse than our near-optimal guarantee (See Appendix A for a detailed calculation). We expect similar behavior from other PAC algorithms, because reward-dependent exploration is typically suboptimal for the reward-free setting.

Second, one can extract the exploration component of recent results for RL with function approximation (Du et al., 2019; Misra et al., 2019). Specifically, the former employs a model based approach where a model is iteratively refined by planning to visit unexplored states, while the latter uses model free dynamic programming to identify and reach all states. While these papers address a more difficult setting, it is relatively straightforward to specialize their results to the tabular setting. In this case, both methods guarantee coverage, but they have suboptimal sample complexity and require that all states can be visited with significant probability. In contrast, our approach requires no visitation probability assumptions and achieves the optimal sample complexity.

The last point of comparison is a recent result of Hazan et al. (2018), that gives an efficient algorithm for finding a certain exploratory policy. They use a Frank-Wolfe style algorithm to find a policy whose state occupancy measure has maximum entropy. One can show that an exact optimizer for their objective has a similar coverage property to our exploratory policy, but the Frank-Wolfe style algorithm can only guarantee an approximate optimizer. They do not analyze how the optimization error enters in the coverage guarantee, but we are able to show that setting the error to $O(1/S)$ suffices (see Appendix B). Unfortunately, this implies that their sample complexity scales with $S^{5}$, which is much worse than ours. More generally, their result is not end-to-end in that they do not show how to use their policy for planning, and they do not establish a final sample complexity bound, both of which we do here.

Finally, the main source of motivation for our work is recent and classical results on batch reinforcement learning (Munos and Szepesvári, 2008; Antos et al., 2008; Chen and Jiang, 2019; Agarwal et al., 2019), a setting where the goal is to find a near optimal policy, given an a priori dataset collected by some logging policy that satisfies certain coverage properties. In this paper, we show how to find such a logging policy for the tabular setting, which enables straightforward application of these batch RL results. As an example, we show how to apply both value iteration and natural policy gradient to optimize the policy given any reward function. More generally, these works typically also consider the function approximation setting, and we believe our modular approach will facilitate development of provably efficient algorithms for these challenging settings.

Preliminaries

where we define $V^{\pi}_{H+1}(s)=V^{\star}_{H+1}(s)=0$ for any $s\in\mathcal{S}$.

The RL objective is to find an $\epsilon$-optimal policy $\pi$, satisfying

In the reward-free setting, we would like to design algorithms that efficiently explore the state space without the guidance of reward information. Formally, the agent interacts with the environment through Protocol 1—a reward-free version of the MDP, where the agent can transit as usual but does not collect any rewards. Over the course of $K$ episodes following Protocol 1, the agent collects a dataset of visisted states, actions, and transitions $\mathcal{D}=\{s^{(k)}_{h},a^{(k)}_{h}\}_{(k,h)\in[K]\times[H]}$, which is the outcome of the exploration phase.

The effectiveness of the exploration strategy is evaluated in the next phase—the planning phase—in which the agent is no longer allowed to interact with the MDP. In this phase, the agent is given a reward function $r(\cdot,\cdot)$ that can be potentially adversarily designed, and the objective here is to compute a near optimal policy for this reward function using the dataset $\mathcal{D}$. Performance is measured in terms of how many episodes $K$ are required in the exploration phase so that the agent can reliably achieve the objective above. As notation, we use $V(\cdot;r)$ to emphasize that the value function depends on the reward $r$.

We remark that providing the reward function after the exploration phase (as opposed to before) makes the setting more challenging, and so our algorithm applies to the easier setting. We also note that our results address the setting where the reward is observed through interaction with the environment, as learning the reward is typically not the statistical barrier to efficient RL. Indeed, a provably effective reward-free exploration strategy must visit all “significant” state-action pairs (see Definition 3.2) sufficiently many times anyway, and this experience is sufficient to learn the reward function.

Main Results

Ther exists an absolute constant $c>0$ and a reward-free exploration algorithm such that, for any $p\in(0,1)$, with probability at least $1-p$, the algorithm outputs $\epsilon$-optimal policies for an arbitrary number of adaptively chosen reward functions. The number of episodes collected in the exploration phase is bounded by

where $\iota\mathrel{\mathop{:}}=\log(SAH/(p\epsilon))$.

We emphasize that the correctness guarantee here is quite strong: the dataset $\mathcal{D}$ collected by the algorithm is such that any number of adaptively chosen reward functions can be optimized with no further data collection. In contrast, if we naïvely deployed a reward-sensitive RL algorithm, we would have to collect additional trajectories for each reward function, which could be quite sample inefficient. We emphasize that requiring near-optimal policies for many reward functions is quite common in applications, especially when we design reward functions by trial and error to elicit specific behaviors.

Our algorithm proceeds with following high level steps:

learn a set of policies $\Psi$ which allow us to visit all “significant” states with reasonable probability.

collect a sufficient amount of data by executing policies in $\Psi$.

The first two steps are performed in the exploration phase, while the latter two steps are performed in the planning phase. In Section 3.1 and Section 3.2, we will present our formal algorithms and the corresponding theoretical guarantees for two phases separately. One important feature of our algorithm is that we can use existing approximate MDP solvers or batch-RL algorithms in the last step. We demonstrate with two examples, namely Value Iteration (VI) and Natural Policy Gradient (NPG), in Section 3.3.

1 Exploration Phase

The goal of exploration is to visit all possible states so that the agent can gather sufficient information in order to find the optimal policy eventually. However, rather different from the bandit setting where agent can select an arbitrary arm to pull, it is possible that certain state in the MDP is very difficult to reach no matter what policy the agent is taking. Therefore, we first introduce the concept of the state being “significant”. See Figure 1 for illustrations.

A state $s$ in step $h$ is $\delta$-significant if there exists a policy $\pi$, so that the probability to reach $s$ following policy $\pi$ is greater than $\delta$. In symbol:

Intuitively, with limited budeget of samples and runtime, one can be only hopefully to visit all significant states. On the other hand, since insignificant states can be rarely visited no matter what policy is used, they will not significantly change the value from the initial states. Thus, for the sake of finding near-optimal policies, it is sufficient to visit all significant states with proper significance level $\epsilon$. Indeed, Algorithm 2 is able to provide such a guarantee as follows.

There exists absolute constant $c>0$ such that for any $\epsilon>0$ and $p\in(0,1)$, if we set $N_{0}\geq cS^{2}AH^{4}\iota_{0}^{3}/\delta$ where $\iota_{0}\mathrel{\mathop{:}}=\log(SAH/(p\delta))$, then with probability at least $1-p$, that Algorithm 2 will returns a dataset $\mathcal{D}$ consisting of $N$ trajectories $\{z_{n}\}_{n=1}^{N}$, which are i.i.d sampled from a distribution $\mu$ satisfying:

Theorem 3.3 claims that using Algorithm 2, we can collect data from a underlying distribution $\mu$, which ensures that for policy $\pi$, the ratio $P_{h}^{\pi}(s,a)/\mu_{h}(s,a)$ will be upper bounded for any significant state and action. That is, all significant state and action will be visited by distribution $\mu$ with reasonable amount of probability. Notice as $\delta$ becomes smaller, there will be more significant states and the condition (4) becomes stronger. As a result we need to take larger $N_{0}$. As we will see later, the $\delta$ we take eventually will be $\epsilon/\left(2SH^{2}\right)$, where $\epsilon$ is the suboptimality of the policy we find in the planning phase.

Algorithm 2 can be decompose into two parts, where Line 3-7 learns a set of exploration policies $\Psi$ and Line 8-11 simply collects data by uniformly executing policies in $\Psi$. Therefore, the key mechanism lies in how to learn the set of exploration policies $\Psi$. Our strategy is to first learn the best policies that maximize the probability to research each state $s$ at step $h$ individually, and then combine them.

There exists absolute constant $c>0$ such that for any $N_{0}>0$ and $p\in(0,1)$, with probability at least $1-p$, if we run Euler algorithm for $N_{0}$ episodes, it will output a policy set $\Phi$ with $|\Phi|=N_{0}$ that satisfies:

where $\iota_{0}=\log\left(SAHN_{0}/p\right)$.

2 Planning Phase

There exists absolute constant $c>0$, for any $\epsilon>0$, $p\in(0,1)$, assume dataset $\mathcal{D}$ has $N$ i.i.d. samples from distribution $\mu$ which satisfies Eq.(4) with $\delta=\epsilon/\left(2SH^{2}\right)$, and $N\geq cH^{5}S^{2}A\iota/\epsilon^{2}$, then with probability at least $1-p$, for any reward function $r$ simultanouesly, the output policy $\hat{\pi}$ of Algorithm 3 is $3\epsilon$-suboptimal. That is:

Under the preconditions of Theorem 3.5, with probability at least $1-p$, for any reward function $r$ and any policy $\pi$, we have:

where evaluation errors are bounded by $\epsilon$ by Lemma 3.6 and optimization error is bounded by $\epsilon$ by assumption. ∎

3 Approximate MDP Solvers

Another popular approach frequently used in practice is the Natural Policy Gradient (NPG) algorithm as shown in Algorithm 4. In each iteration, the algorithm first evaluates the value of policy $\pi^{(t)}$ using Bellman equation Eq.(1). Then it updates the policy by first scale it with the exponential of learning $\eta$ times value $Q^{\pi^{(t)}}$, and then performs a normalization. For completeness, we provides its guarantee here. Similar analysis also appears in Agarwal et al. (2019).

for any learning rate $\eta$ and iteration number $T$, the output policy $\pi^{(T)}$ of Algorithm 4 satisfies the following:

Therefore, it is easy to verify, by choosing $\eta=\sqrt{\log A/HT}$ and $T=4H^{3}\log A/\epsilon^{2}$, the policy $\pi^{(T)}$ returned by NPG is $\epsilon$-optimal.

Lower Bound

In this section, we establish that $\Omega(H^{2}S^{2}A/\epsilon^{2})$ trajectories are necessary to satisfy the guarantee from Theorem 3.1.

Let $C>0$ be a universal constant. Then for $A\geq 2$, $S\geq C\log_{2}A$, $H\geq C\log_{2}S$, and any $\epsilon\leq\min\{1/4,H/48\}$, any reward-free exploration algorithm $\mathsf{Alg}$ which statisfies the guarantee of Theorem 3.1 with $p=1/2$ and accuracy parameter $\epsilon$ must collect $\Omega(S^{2}AH^{2}/\epsilon^{2})$ trajectories in expectation. This is true even if $\mathsf{Alg}$ can return randomized or history-dependent (non-Markov) policies, and holds even if the rewards and transitions are identical across stages $h$.

In particular, Theorem 4.1 shows that our upper bound (Theorem 3.1) is tight in $S,A,\epsilon$, up to logarithmic factors and lower-order terms. Note that lower bound holds against querying an unlimited number of reward vectors. It is left as an open question whether such a lower bound holds when the algorithm is only required to ensure correctness over a smaller number of reward vectors pre-determined in advance. In what follows, we sketch a proof of Theorem 4.1; a formal proof is given in Appendix D.

The learner is then tasked with learning near optimal policies for reward vectors $r_{\nu}$ parametrized by $\nu\in^{2n}$, which assigns a state-dependent but action-independent reward $\nu(s)$ to states $s\in[2n]$, and no reward to $x_{1}=0$. The blue (“left”) transitions or red (“right”) transition in Figure 2 mirror this construction, which we formalize in Definition D.1. We show that reward-free exploration essentially forces the learner to learn the probability vectors $q(\cdot,a)$ in total-variation distance for each $a\in[A]$, yielding an $\Omega(nA/\epsilon^{2})$ lower bound for this construction. A formal statement is of the following Lemma is given in Lemma D.2 in the appendix.

Suppose $S\geq C\log_{2}(A)$ for a universal constant $C>0$. Suppose $\mathsf{Alg}$, when faced with the instances described above (with $q$ satisfying Eq. (6)) successfully returns $\epsilon$-suboptimal policies for exponentially many reward vectors with total failure probability $1/2$. Then $\mathsf{Alg}$ requires $\Omega(SA/\epsilon^{2})$ trajectories in expectation.

Unfortunately, we cannot show a direct reduction from estimating $q$ in total variation to learning near optimal-policies. Instead, by selecting appropriate reward vectors $r_{\nu}$, the algorithm can decode a packing of $\exp(\Omega(n))$ transition vectors $q(\cdot,a)$ for each action $a\in[A]$. By a variant of Fano’s inequality, this leads to the same $\Omega(nA/\epsilon^{2})$ lower bound that would be obtained by a direct reduction. ∎

Lemma 4.2 differs from existing $\Omega(SA/\epsilon^{2})$ lower bounds in that the only quantities unknown to the learner are the transition probabilities associated with the single state . This is in contrast to most existing lower bounds where the learner needs to collect transition information at multiple states. In particular, here the factor of $S$ arises because the transition is to $\Theta(S)$ states, while in most constructions this factor arises because transitions from $\Theta(S)$ states must be estimated.

2 Lower Bound for Multiple States

The only part unknown to the learner are the transition vectors $\{q_{x}\}_{x\in[n]}$, where $q_{x}(s,a)$ describes the probability of transitioning to leaf $(s,1+\log_{2}n)$ when taking action $a$ from state $(x,\log_{2}n)$. We now index rewards by $(x,\nu)\in[n]\times^{2n}$, where $r_{x,\nu}$ places action-independent reward $1$ on state $(x,\log_{2}n)$, action-independent reward $\nu(s)$ on states $(s,1+\log_{2}n)$, and reward everywhere.

Assume that the transitions $q_{x}$ satisfy the near-uniformity condition of (6) for $\epsilon=1/4H$. Then, for reward $r_{x,\nu}$, the high reward of $1$ at $(x,\log_{2}n)$ forces any near-optimal policy to visit $(x,\log_{2}n)$ and subsequently play near optimal actions at this state. However, playing optimally at $(x,\log_{2}n)$ under reward $r_{x,\nu}$ for all $\nu$ is equivalent to reward-free learning of a single instance of the construction from Lemma 4.2. By varying $x\in[n]$ for the reward vectors $r_{x,\nu}$, the learner is forced to learn $n$ such instances, yielding the $\Omega(n\cdot nA/\epsilon^{2})=\Omega(S^{2}A/\epsilon^{2})$ lower bound. This can be improved to $\Omega(H^{2}S^{2}A/\epsilon^{2})$ by using the absorbing states to create a chain of $\Omega(H)$ rewards.

Conclusion

In this paper, we propose a new “reward-free RL” framework, comprising of two phases. In the exploration phase, the learner first collects trajectories from an MDP $\mathcal{M}$ without receiving any reward information. After the exploration phase, the learner is no longer allowed to interact with the MDP and she is instead tasked with computing near-optimal policies under for $\mathcal{M}$ for a collection of given reward functions. This framework is particularly suitable when there are many reward functions of interest, or when we are interested in learning the transition operator directly.

Another interesting direction is to design reward-free RL algorithms for settings with function approximation. We believe our work highlights and introduces some mechanisms that may be useful in the function approximation setting, such as the concept of significant states (Definition 3.2) and the coverage guarantee (4). How do we generalize these concepts to the function approximation setting?

We hope to pursue these directions in future work.

References

Appendix A The ZeroRMax algorithm

RMax is a well-known PAC exploration algorithm Brafman and Tennenholtz . Here, we show that a modified version of RMax, which we call ZeroRMax, addresses the reward-free exploration setting. The difference between ZeroRMax and RMax is that we set the reward in “known” states to instead of the true reward, which explains the name. We briefly describe the algorithm and derive the PAC bound relying heavily on prior arguments. Details about RMax and its analysis can be found in prior work Brafman and Tennenholtz , Kakade .

Following the reward-free exploration framework proposed in Section 2, the ZeroRMax algorithm first collects samples without knowledge about reward (exploration) and then computes a policy for each configuration of reward function (planning). We define set of known states $\mathcal{K}$ to be

where $N_{h}\left(s,a\right)$ counts how many times $s$ has been visited and $a$ was taken in the $h$-th step and $m$ is a parameter to be specified later. The set $\mathcal{K}$ contains states that we have visited enough times to estimate the corresponding transition kernel, and is typically referred to as the “known set” in the literature. For $(s,h)$ not in $\mathcal{K}$, we call them “unknown.”

Now ZeroRMax explores as follows. In each episode $i\in[N]$, the agent has a known set $\mathcal{K}_{i}$ and

builds an empirical MDP $\hat{\mathcal{M}}_{i,\mathcal{K}_{i}}$ with parameters

computes $\pi_{i}=\pi_{\hat{\mathcal{M}}_{i,\mathcal{K}_{i}}}^{\star}$ on $\hat{\mathcal{M}}_{i,\mathcal{K}_{i}}$ by value iteration.

samples a trajectory from the environment following $\pi_{i}$.

constructs $\mathcal{K}_{i+1}$ for the next episode

For the planning phase, we first sample an index $i\in[N]$ uniformly and construct the MDP $\hat{\mathcal{M}}_{i,\mathcal{K}_{i}}$. Then given reward function, we can just perform value iteration on $\hat{\mathcal{M}}_{i,\mathcal{K}_{i}}$, which gives us a near optimal policy.

A central concept for analyzing the sample complexity of ZeroRMax is the escape probability, which is the probability of visiting the unknown states. Formally,

The above definition also depends on the corresponding MDP $\mathcal{M}$. Since we only care about the escape probability w.r.t the true MDP $\mathcal{M}$, we will omit this dependence. The key observation is that there cannot be too many episodes where the escape probability is large. The inuition is that, if the escape probability is big, then the agent will soon visit an unknown states. However, the agent can visit unknown states at most $mSA$ times in total.

Let $\pi_{i}$ be the policy followed in the $i^{\textrm{th}}$episode and $\mathcal{K}_{i}$ be corresponding set of known states. Then with probability $1-p$, there can be at most $\mathcal{O}\left(\frac{mSA}{\varepsilon}\log\frac{SANH}{p}\right)$ episodes where $p_{\mathcal{K}_{i}}^{\pi_{i}}>\varepsilon$.

As a result, we have the following corollary.

If we sample $i$ uniformly from $1$ to $K$, then with probability $1-p-\mathcal{O}\left(\frac{mSA}{\varepsilon N}\log\frac{SANH}{p}\right)$, we have $p_{\mathcal{K}_{i}}^{\pi_{i}}\leq\varepsilon$.

In what follows, we focus on a single “good” episode $i$ where $p_{\mathcal{K}_{i}}^{\pi_{i}}\leq\varepsilon$. Since we focus on a single episode, let us denote $\mathcal{K}_{i}$ by $\mathcal{K}$ and $\pi_{i}$ by $\pi_{\hat{\mathcal{M}}_{\mathcal{K}}}^{\star}$. There are three MDPs of interest, with important details presented in Table 1.

$\mathcal{M}$ is the true MDP of interest, that we will use to measure the performance of the policy we find in the planning phase. $\hat{\mathcal{M}}_{\mathcal{K}}$ is the MDP we use for computing policies in both exploration and planning phases. The final MDP, $\mathcal{M}_{\mathcal{K}}$ is an intermediate MDP which agrees with $\mathcal{M}$ on the known set but follows self-loops in the unknown states. Our plan is to prove with high probability, the value of any policy$\pi$ on $\mathcal{M}$ and $\hat{\mathcal{M}}_{\mathcal{K}}$ are close, which implies the desired sample complexity result using the same argument as in Theorem 3.5.

The first step is to prove that for any policy $\pi$, the values on $\mathcal{M}_{\mathcal{K}}$ and $\hat{\mathcal{M}}_{\mathcal{K}}$ are similar.

With probability $1-p$, for any policy $\pi$ and reward function $r$,

We apply Lemma C.1 to $\mathcal{M}_{\mathcal{K}}$ and $\hat{\mathcal{M}}_{\mathcal{K}}$, since the reward function is the same and the transition kernel is the same for unknown states,

The second step is to prove that for any policy $\pi$, the values on $\mathcal{M}_{\mathcal{K}}$ and $\mathcal{M}$ are similar, which is less straightforward.

With probability $1-p$ and $i$ is a ”good” episode, for any policy $\pi$,

Notice that for any policy $\pi$, if we can upper bound the escape probability, then $\mathcal{M}_{\mathcal{K}}$ and $\mathcal{M}$ must be similar for this policy. Fortunately, this is actually the case, due to our setting of the reward function in the exploration phase, following (7). Then by definition for any $s$,

However, since we are considering a good episode, we know that for the optimal policy on $\hat{\mathcal{M}}_{\mathcal{K}}$, $\pi_{\hat{\mathcal{M}}_{\mathcal{K}}}^{*}$, we have $p_{\mathcal{K}}^{\pi_{\hat{\mathcal{M}}_{\mathcal{K}}}^{*}}\leq\varepsilon$. Therefore,

Now notice $\mathcal{M}_{\mathcal{K}}$ and $\mathcal{M}$ are only different on unknown states, which will not influence the agent unless the agent escapes from $\mathcal{K}$. Using Lemma C.1 on $\mathcal{M}_{\mathcal{K}}$ and $\mathcal{M}$ we have

Finally we can put everything together. Again following the argument in Theorem 3.5, we have

With probability $1-2p-\mathcal{O}\left(\frac{mSA}{\varepsilon K}\log\frac{SANH}{p}\right)$, given any reward function, the ZeroRMax algorithm can output a policy $\pi$ such that

This sample complexity is quite poor because it scales with $\epsilon^{-3}$ and polynomially, rather than logarithmically, with $1/p$.

Appendix B MaxEnt Exploration

At this point we can see that if $\alpha\geq 1/S$ then this expression is negative, so the mixture policy with large $\alpha$ does not yield any improvement in objective. On the other hand, for any $\alpha<1/S$ then this inner expression is $\Theta(S)$. So if we set $\alpha=\Theta(1/S)$ the overall improvement in objective is $\Omega(1/S)$. This means that if we want establish the guarantee in Theorem 3.3, we must set $\varepsilon=1/S$, at which point the overall sample complexity scales with $S^{5}$, which is quite poor.

Note that this calculation shows that $O(S^{5})$ samples is sufficient for the maximum entropy approach to find a suitable exploratory policy, but we do not claim that it is necessary for this method. A sharper analysis may be possible, but we are not aware of any such results.

Appendix C Proof for Main Results

In this section, we present proofs for results in Section 3.

We begin with the proof of Lemma 3.4, which is a simple modification of the Theorem 1 in Zanette and Brunskill .

We use an alternative upper-bound for equation (156) in Zanette and Brunskill , which gives:

where $\pi_{k}$ is the policy used in Euler in the $k$-th episode. Step (i) is because using the reward function designed in Line 4 in Algorithm 2, we have all reward equal to zero except one state. Therefore, we have $\sum_{h=1}^{H}r(s_{h},a_{h})\leq 1$ and $V_{1}^{\pi}(s_{1})\leq 1$. Therefore, we have replace the upper bound $\mathcal{G}^{2}$ in (156) of Zanette and Brunskill by $4V_{1}^{\star}(s_{1})$.

This allows us also replace the $\mathcal{G}^{2}$ in Theorem 1 of Zanette and Brunskill by $4V_{1}^{\star}(s_{1})$, which gives the regret of algorithm (note Zanette and Brunskill is for stationary MDP, while our paper is for non-stationary MDP, thus $S$ in Zanette and Brunskill need to be replaced by $SH$ in our paper due to state augmentation, which creates new states as $(s,h)$):

Finally, plug in $T=N_{0}H$, we finish the proof. ∎

Now we can prove the main result in this section.

In the following we can fix a state $(s,h)$ and consider the corresponding policy given by Euler. Remember in our setting (Line 4 in Algorithm 2),

Therefore the regret guarantee Lemma 3.4 implies

for some absolute constant $c_{0}$. Therefore, in order to make the following true

We simply need to choose $N_{0}$ large enough so that:

for a sufficient small absolute constant $c_{1}$. Combining with the fact that for \text{~{}\delta-significant~{}}(s,h), $\max_{\pi}P_{h}^{\pi}(s)\geq\delta$, we know choosing $N_{0}=\mathcal{O}(S^{2}AH^{4}\iota_{0}^{3}/\delta)$ is sufficient. As a result, we have

Since Algorithm 2 sets all policy in $\Phi^{(s,h)}$ to choose action uniformly randomly at $(s,h)$, this implies

Finally, we can apply the same argument for all $\delta$-significant $(s,h)$, and let $\Psi=\cup\{\Phi^{(s,h)}\}_{(s,h)}$ which gives:

C.2 Planning Phase

The following lemma (E.15 in Dann et al. ) will be useful to characterize the difference between $V_{h}^{\pi}(s;r)$ and $\hat{V}_{h}^{\pi}(s;r)$ .

With this decomposition in mind, we can prove Lemma 3.6.

Let $\mathcal{S}_{h}^{\delta}:=\{s:\underset{\pi}{\max}P_{h}^{\pi}(s)\geq\delta\}$ be the set of $\delta$-significant states in the $h$-th step. We further have:

By definition of insignificant state, we have:

On the other hand, by Cauchy-Shwartz inequality, we have:

We note since $\hat{V}_{h+1}^{\pi}$ only depends on $\pi$ at $h+1,\cdots,H$ steps, it does not depends on $\pi_{h}$. Therefore, we have:

where the last step is because the maximization over $\pi^{\prime}_{h}$ achieves at deterministic polices.

Recall that by preconditions, we have 4 holds for $\delta=\epsilon/(2SH^{2})$. That is, for any $s\in\mathcal{S}_{h}^{\delta}$ we always have

Therefore, for any $(s,a)$ pair, we can design a policy $\pi^{\prime}$ so that $\pi^{\prime}_{h^{\prime}}=\pi_{h^{\prime}}$ for all $h^{\prime}<h$, and $\pi^{\prime}_{h}(s)=a$. This will give that

Therefore, combine all equations above, we have

Recall our choice $\delta=\epsilon/(2SH^{2})$ and $N\geq c\frac{H^{5}S^{2}A}{\epsilon^{2}}\log(\frac{SAH}{p\epsilon})$ for sufficiently large absolute constant $c$, which finishes the proof. ∎

To simplify the notation, when some property of $Y_{i}$ holds for any $i$, we just use the notation $Y$ to describe a generic $Y_{i}$.

We first state some properties of the random variables $Y_{i}$, which are justified at the end of the proof.

(Empirical risk minimization) $\sum_{i=1}^{N}{Y_{i}}\leq 0$

We can simply choose $\varepsilon=HS/36N$ and thus

Taking union bound w.r.t. $h$, the claim holds for any $h$ with probability $1-p$.

Finally we give the proofs for the claimed three properties of $Y_{i}$. We begin with the expectation property:

The emipirical risk minimization property is true because the evaluation rule is essentially minimizing the empirical Bellman error for each $(s,a)$ pair separately. Mathematically,

C.3 Proof of Theorem 3.1

Putting everything together we can prove the main theorem.

We only need to choose the parameter $\delta$ and $N_{0}$. From the proof of Lemma 3.6 we can see, we need $\delta=\epsilon/(2SH^{2})$ and thus $N_{0}\geq cS^{3}AH^{6}\iota^{3}/\epsilon$. Since we need $N_{0}$ episodes for each $(s,h)$, the total number episodes required for finding $\Psi$ is $\mathcal{O}(cS^{4}AH^{7}\iota^{3}/\epsilon)$, which gives the second term in (3). The proof is completed by combining Theorem 3.5, which gives the first term in (3). ∎

C.4 Approximate MDP Solvers

The convergence of NPG is well studied in Agarwal et al. (tabluar & infinite horizon) and Cai et al. (linear approximation). However, the episodic setting has some unique characters (For example, we not every state can be arrive at the first step and the corresponding analysis in Agarwal et al. does not apply). Therefore the guarantee given in Proposition 3.7 is different.

Since we only need to prove the guarantee on the true MDP, we will not distinguish true MDP $\mathcal{M}$ and estimated MDP $\hat{\mathcal{M}}$ here. Remember the NPG is defined by

where $Q_{h}^{(t)}(s,a):=Q_{h}^{\pi^{(t)}}(s,a)$ is computed following the value iteration procedure. Similarly we define $V_{h}^{(t)}(s):=V_{h}^{\pi^{(t)}}(s)$. The normalization constant can be written explicitly as

Notice the definition of the normalization constant is not unique. Here we choose the form that makes the following proof simpler but different choice will essentially gives exactly the same algorithm.

We begin with a lemma showing that the value function monotonically increases.

By performance difference lemma Kakade and Langford ,

because $V_{h}^{(t)}(s)=\sum_{a\in\mathcal{A}}{\pi_{h}^{(t)}(a|s)Q_{h}^{(t)}(s,a)}$ by definition. ∎

Equipped with the monotone property, we can simply prove an upper bound for the cumulative regret, which immediately implies the convergence rate for the last iteration.

Now we can upper bound the regret of $\pi^{(T-1)}$ by upper bound the cumulative regret using Lemma C.3

Therefore we only need to bound $\log Z_{h}^{(t)}(s_{h})$, where the technique in Agarwal et al. does not apply and we use a different approach. Notice for $x\leq 1$, $\exp\{x\}\leq 1+x+x^{2}$. So as long as $\eta\leq\frac{1}{H}$, $\eta[Q_{h}^{(t)}(s,a)-V_{h}^{(t)}(s)]\leq 1$ and we have

Appendix D Proof of Lower Bound

In this section, we prove our lower bound, Theorem 4.1. First, we develop further notation in Section D.1 which will aid in distinguishing between multiple possible instances. Next, Section D.2 states Lemma D.2, the formal analogue of Lemma 4.2, which describes a lower bound for learning transitions at a single state. Then, Section D.3 embeds the construction to obtain an instance where the learner to learn transitions at $n$ states, yielding the lower bound Theorem 4.1. Finally, Section D.4 details the proof of the $1$-state lower bound, Lemma 4.2.

For the lower bound, we allow the policies $\pi$ prescribed by $\mathsf{Alg}$ to be arbitrary randomized mappings form observed histories, that is, $\mathsf{Alg}$ selects a random seed $\xi$ from some distribution; that is the policy at stage $h$ is a map

D.2 Learning A Single Instance

In this section, we define a triple $(\mathscr{E},\mathscr{R},\mathscr{P})$ on $\mathcal{O}\left(n\right)$-states which forces the learner to spend $\Omega(nA/\epsilon^{2})$ trajectories to learn the transition probabilities at a given state.

Due to its level of technical, the proof of Lemma D.2 is given in Section D.4.

D.3 Learning Transitions at n𝑛n states: Proof of Theorem 4.1

Suppose that a (possibly randomized, non-Markovian) policy $\pi$ satisfies, for $\epsilon\leq 1/4$ and $\epsilon_{0}\leq 1/8H$,

Due to the structure of the transitions and rewards, the value of any policy $\pi$ is

To prove Theorem 4.1, we use the following lemma:

We directly construct the map $\Psi$. Observe that policies $\pi^{(x)}$ on the single state environment can be discred by a distribution over which actions $a\in[A]$ they select at the initial state $x$. Thus identifying policies as elements of $\Delta(A)$, we set

We now conclude with the proof of our main theorem:

Since $S/8\leq n\leq S$, for the above conditions to hold, it suffices that, for a sufficiently large constant $C$, $S\geq C\log_{2}A$, $\epsilon\leq\min\{\frac{1}{4},\frac{H}{48}\}$, and $H\geq C\log_{2}S$. Moreover, $\frac{n^{2}AH^{2}}{\epsilon^{2}}=\Omega(\frac{S^{2}AH^{2}}{\epsilon^{2}})$, as needed. ∎

D.4 Proof of Lemma D.2

For a cardinality parameter $M$ to be chosen shortly, we consider a packing of vectors

Throughout, we shall consider packings $\mathcal{V}_{A,M}$ which are uncorrelated in the following sense:

For $\gamma\in(0,1)$, we say that $\mathcal{V}_{A,M}$ is $\gamma$-uncorrelated if, for any pair $(a,j),(a^{\prime},j^{\prime})$ with either $a\neq a^{\prime}$ or $j\neq j^{\prime}$, it holds that $|\langle v_{a,j},v_{a^{\prime},j^{\prime}}\rangle|<2n\gamma.$.

The following lemma shows that the exist $\gamma$-uncorrelated packings of size $e^{\Omega(n\gamma^{2})}$:

Fix $\gamma\in(0,1)$, and suppose that $2\log(M)\leq n\gamma^{2}-\log(4n)-2\log(A)$. Then, there exists a $\gamma$-uncorrelated packing $\mathcal{V}_{A,M}$.

Given a $\gamma$-uncorrelated packing $\mathcal{V}_{A,M}$, define transition vectors

As a consequence, we find that if $\gamma\leq 1/10$ and $\mathsf{Alg}$ is $(\epsilon/24,p)$-correct,

In particular, if $\log M\geq 4\log 2$ and $p\leq 1/2$, then,

Take $\gamma=1/10$. For constants $c_{0},c_{1}$ sufficiently large, we can ensure that if $n\geq c_{0}\log_{2}A$, then $M=e^{-n/c_{1}}$ statisfies $2\log(M)\leq n\gamma^{2}-\log(4n)-2\log(A)$ and $\log M\geq 4\log 2$. Thus, we can construct a $\gamma$-uncorrelated packing of cardinality $\log M\geq n/c_{1}$,

D.4.1 Proof of Lemma D.6

We begin with the following concentration inequality:

For any fixed $(a,j)$ and $(a^{\prime},j^{\prime})$, we have

By permuting coordinates, we may assume that

where we set $Z=|\{s\in[n]:v_{a,j}[s]=1\}|$. Hence, if $|\langle v_{a,j},v_{a^{\prime},j^{\prime}}\rangle|\geq 2\gamma n$, we need

We now finish the proof of our intended lemma:

By a union bound over at most $A^{2}M^{2}-1$ pairs $(a,j),(a^{\prime},j^{\prime})$, there exists a $\gamma$-uncorrelated packing for any $M$ satisfying

Taking logarithms, we require $2\log(M)\leq n\gamma^{2}-\log(4n)-2\log(A)$.

D.4.2 Proof of Lemma D.7

To begin, let us state a variant of Fano’s inequality, which replaces mutual-information with an arbitrary comparison measure:

This follows from the standard statement of Fano’s inequality, where we use that

For reference, see e.g. Equation (11) in Chen et al. . ∎

where $(i)$ uses $1+\epsilon v_{j,a}[s]\geq 0$ and the identity $\log(1+x)\leq x$, and $(ii)$ uses the fact that $v_{j,a}[s]^{2}=1$ and $\sum_{s=1}^{2n}v_{j,a}[s]=0$ for $v_{j,a}\in\mathcal{K}$. Thus, by Eq 11,

By taking an expectation over index tuples $J$ drawn uniformly from $[A]^{M}$, we have

D.4.3 Proof of Lemma D.8

which can be checked to lie $^{2n}$. We shall establish the following lemma, which says that for sufficciently uncorrelated packings, the vectors $\nu_{(\dots)}$ witness separations between $q_{a_{1},j_{1}}$ and $q_{a_{2},j_{2}}$ for different actions $a_{1},a_{2}$:

Fix $a_{1}\in[A]$ and $j_{1}\in[M]$, and suppose the packing is $\gamma=1/10$-uncorrelated: Then, for any $a_{2}\neq a_{1}$ and $j_{2}\in[M]$, the following holds

where we use the fact that $v_{a,j}^{\top}\mathbf{1}=1$ for all $a,j$. If $a^{\prime}_{1}=a_{1}$ and $j_{1}^{\prime}=j_{1}$, and the packing is $\gamma\leq 1/6$-uncorrelated

On the other hand, if $j_{1}\neq j_{1}^{\prime}$, but $(a_{2},j_{2})=(a_{2}^{\prime},j_{2}^{\prime})$ then a similar computation reveals that for $\gamma\leq 1/10$,

We can now conclude the proof of our reduction:

We conclude our proof by showing that, on the good event Eq. (12), the condition in Eq. (13) holds if and only if $j=J_{a}$. To this end, define the short hand

so that on the good event of Eq. 12, we have