Exploration by Maximizing Rényi Entropy for Reward-Free RL Framework

The trade-off between exploration and exploitation is at the core of reinforcement learning (RL). Designing efficient exploration algorithm, while being a highly nontrivial task, is essential to the success in many RL tasks (Burda et al. 2019b; Ecoffet et al. 2019). Hence, it is natural to ask the following high-level question: What can we achieve by pure exploration? To address this question, several settings related to meta reinforcement learning (meta RL) have been proposed (see e.g., Wang et al. 2016; Duan et al. 2016; Finn, Abbeel, and Levine 2017). One common setting in meta RL is to learn a model in a reward-free environment in the meta-training phase, and use the learned model as the initialization to fast adapt for new tasks in the meta-testing phase (Eysenbach et al. 2019; Gupta et al. 2018; Nagabandi et al. 2019). Since the agent still needs to explore the environment under the new tasks in the meta-testing phase (sometimes it may need more new samples in some new task, and sometimes less), it is less clear how to evaluate the effectiveness of the exploration in the meta-training phase. Another setting is to learn a policy in a reward-free environment and test the policy under the task with a specific reward function (such as the score in Montezuma’s Revenge) without further training with the task (Burda et al. 2019b; Ecoffet et al. 2019; Burda et al. 2019a). However, there is no guarantee that the algorithm has fully explored the transition dynamics of the environment unless we test the learned model for arbitrary reward functions. Recently, Jin et al. (2020) proposed reward-free RL framework that fully decouples exploration and exploitation. Further, they designed a provably efficient algorithm that conducts a finite number of steps of reward-free exploration and returns near-optimal policies for arbitrary reward functions. However, their algorithm is designed for the tabular case and can hardly be extended to continuous or high-dimensional state spaces since they construct a policy for each state.

The reward-free RL framework is as follows: First, a set of policies are trained to explore the dynamics of the reward-free environment in the exploration phase (i.e., the meta-training phase). Then, a dataset of trajectories is collected by executing the learned exploratory policies. In the planning phase (i.e., the meta-testing phase), an arbitrary reward function is specified and a batch RL algorithm (Lange, Gabel, and Riedmiller 2012; Fujimoto, Meger, and Precup 2019) is applied to solve for a good policy solely based on the dataset, without further interaction with the environment. This framework is suitable to the scenarios when there are many reward functions of interest or the reward is designed offline to elicit desired behavior. The key to success in this framework is to obtain a dataset with good coverage over all possible situations in the environment with as few samples as possible, which in turn requires the exploratory policy to fully explore the environment.

Several methods that encourage various forms of exploration have been developed in the reinforcement learning literature. The maximum entropy framework (Haarnoja et al. 2017) maximizes the cumulative reward in the meanwhile maximizing the entropy over the action space conditioned on each state. This framework results in several efficient and robust algorithms, such as soft Q-learning (Schulman, Chen, and Abbeel 2017; Nachum et al. 2017), SAC (Haarnoja et al. 2018) and MPO (Abdolmaleki et al. 2018). On the other hand, maximizing the state space coverage may results in better exploration. Various kinds of objectives/regularizations are used for better exploration of the state space, including information-theoretic metrics (Houthooft et al. 2016; Mohamed and Rezende 2015; Eysenbach et al. 2019) (especially the entropy of the state space, e.g., Hazan et al. (2019); Islam et al. (2019)), the prediction error of a dynamical model (Burda et al. 2019a; Pathak et al. 2017; de Abril and Kanai 2018), the state visitation count (Burda et al. 2019b; Bellemare et al. 2016; Ostrovski et al. 2017) or others heuristic signals such as novelty (Lehman and Stanley 2011; Conti et al. 2018), surprise (Achiam and Sastry 2016) or curiosity (Schmidhuber 1991).

In practice, it is desirable to obtain a single exploratory policy instead of a set of policies whose cardinality may be as large as that of the state space (e.g., Jin et al. 2020; Misra et al. 2019). Our exploration algorithm outputs a single exploratory policy for the reward-free RL framework by maximizing the Rényi entropy over the state-action space in the exploration phase. In particular, we demonstrate the advantage of using state-action space, instead of the state space via a very simple example (see Section 3 and Figure 1). Moreover, Rényi entropy generalizes a family of entropies, including the commonly used Shannon entropy. We justify the use of Rényi entropy as the objective function theoretically by providing an upper bound on the number of samples in the dataset to ensure that a near-optimal policy is obtained for any reward function in the planning phase.

Further, we derive a gradient ascent update rule for maximizing the Rényi entropy over the state-action space. The derived update rule is similar to the vanilla policy gradient update with the reward replaced by a function of the discounted stationary state-action distribution of the current policy. We use variational autoencoder (VAE) (Kingma and Welling 2014) as the density model to estimate the distribution. The corresponding reward changes over iterations which makes it hard to accurately estimate a value function under the current reward. To address this issue, we propose to estimate a state value function using the off-policy data with the reward relabeled by the current density model. This enables us to efficiently update the policy in a stable way using PPO (Schulman et al. 2017). Afterwards, we collect a dataset by executing the learned policy. In the planning phase, when a reward function is specified, we augment the dataset with the rewards and use a batch RL algorithm, batch constrained deep Q-learning (BCQ) (Fujimoto, Meger, and Precup 2019; Fujimoto et al. 2019), to plan for a good policy under the reward function. We conduct experiments on several environments with discrete, continuous or high-dimensional state spaces. The experiment results indicate that our algorithm is effective, sample efficient and robust in the exploration phase, and achieves good performance under the reward-free RL framework.

Our contributions are summarized as follows:

• •

  (Section 3) We consider the reward-free RL framework that separates exploration from exploitation and therefore places a higher requirement for an exploration algorithm. To efficiently explore under this framework, we propose a novel objective that maximizes the Rényi entropy over the state-action space in the exploration phase and justify this objective theoretically.

• •

  (Section 4) We propose a practical algorithm based on a derived policy gradient formulation to maximize the Rényi entropy over the state-action space for the reward-free RL framework.

• •

  (Section 5) We conduct a wide range of experiments and the results indicate that our algorithm is efficient and robust in the exploration phase and results in superior performance in the downstream planning phase for arbitrary reward functions.

A reward-free environment can be formulated as a controlled Markov process (CMP) ¹¹1 Although some literature use CMP to refer to MDP, we use CMP to denote a Markov process (Silver 2015) equipped with a control structure in this paper. $(\mathcal{S},\mathcal{A},\mathbb{P},\mu,\gamma)$ which specifies the state space $\mathcal{S}$ with $S=|\mathcal{S}|$, the action space $\mathcal{A}$ with $A=|\mathcal{A}|$, the transition dynamics $\mathbb{P}$, the initial state distribution $\mu\in\Delta^{\mathcal{S}}$ and the discount factor $\gamma$. A (stationary) policy $\pi_{\theta}:\mathcal{S}\to\Delta^{\mathcal{A}}$ parameterized by $\theta$ specifies the probability of choosing the actions on each state. The stationary discounted state visitation distribution (or simply the state distribution) under the policy $\pi$ is defined as $d_{\mu}^{\pi}(s):=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\text{Pr}(s_{t}=s|s_{0}\sim\mu;\pi)$. The stationary discounted state-action visitation distribution (or simply the state-action distribution) under the policy $\pi$ is defined as $d_{\mu}^{\pi}(s,a):=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\text{Pr}(s_{t}=s,a_{t}=a|s_{0}\sim\mu;\pi)$. Unless otherwise stated, we use $d_{\mu}^{\pi}$ to denote the state-action distribution. We also use $d_{s_{0},a_{0}}^{\pi}$ to denote the distribution started from the state-action pair $(s_{0},a_{0})$ instead of the initial state distribution $\mu$.

When a reward function $r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ is specified, CMP becomes the Markov decision process (MDP) (Sutton and Barto 2018) $(\mathcal{S},\mathcal{A},\mathbb{P},r,\mu,\gamma)$. The objective for MDP is to find a policy $\pi_{\theta}$ that maximizes the expected cumulative reward $J(\theta;r):=\mathbb{E}_{s_{0}\sim\mu}[V^{\pi_{\theta}}(s_{0};r)]$, where $V^{\pi}(s;r)=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s;\pi]$ is the state value function. We indicate the dependence on $r$ to emphasize that there may be more than one reward function of interest. The policy gradient for this objective is $\nabla_{\theta}J(\theta;r)=\mathbb{E}_{(s,a)\sim d^{\pi_{\theta}}_{\mu}}[\nabla_{\theta}\log\pi_{\theta}(a|s)Q^{\pi_{\theta}}(s,a;r)]$ (Williams 1992), where $Q^{\pi}(s,a;r)=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a;\pi]=\frac{1}{1-\gamma}\langle d_{s,a}^{\pi},r\rangle$ is the Q function.

Rényi entropy for a distribution $d\in\Delta^{\mathcal{X}}$ is defined as $H_{\alpha}(d):=\frac{1}{1-\alpha}\log\left(\sum_{x\in\mathcal{X}}d^{\alpha}(x)\right)$, where $d(x)$ is the probability mass or the probability density function on $x$ (and the summation becomes integration in the latter case). When $\alpha\to 0$, Rényi entropy becomes Hartley entropy and equals the logarithm of the size of the support of $d$. When $\alpha\to 1$, Rényi entropy becomes Shannon entropy $H_{1}(d):=-\sum_{x\in\mathcal{X}}d(x)\log d(x)$ (Bromiley, Thacker, and Bouhova-Thacker 2004; Sanei, Borzadaran, and Amini 2016).

Given a distribution $d\in\Delta^{\mathcal{X}}$, the corresponding density model $P_{\phi}:\mathcal{X}\to\mathbb{R}$ parameterized by $\phi$ gives the probability density estimation of $d$ based on the samples drawn from $d$. Variational auto-encoder (VAE) (Kingma and Welling 2014) is a popular density model which maximizes the variational lower bound (ELBO) of the log-likelihood. Specifically, VAE maximizes the lower bound of $\mathbb{E}_{x\sim d}[\log P_{\phi}(x)]$, i.e., $\max_{\phi}\mathbb{E}_{x\sim d,z\sim q_{\phi}(\cdot|x)}[\log p_{\phi}(x|z)]-\mathbb{E}_{x\sim d}[D_{\text{KL}}(q_{\phi}(\cdot|x)||p(z))]$, where $q_{\phi}$ and $p_{\phi}$ are the decoder and the encoder respectively and $p(z)$ is a prior distribution for the latent variable $z$.

The objective for the exploration phase under the reward-free RL framework is to induce an informative and compact dataset: The informative condition is that the dataset should have good coverage such that the planning phase generates good policies for arbitrary reward functions. The compact condition is that the size of the dataset should be as small as possible to ensure a successful planning. In this section, we show that the Rényi entropy over the state-action space (i.e., $H_{\alpha}(d_{\mu}^{\pi})$) is a good objective function for the exploration phase. We first demonstrate the advantage of maximizing the state-action space entropy over maximizing the state space entropy with a toy example. Then, we provide a motivation to use Rényi entropy by analyzing a deterministic setting. At last, we provide an upper bound on the number of samples needed in the dataset for a successful planning if we have access to a policy that maximizes the Rényi entropy over the state-action space. For ease of analysis, we assume the state-action space is discrete in this section and derive a practical algorithm that deals with continuous state-action space in the next section.

Why maximize the entropy over the state-action space? We demonstrate the advantage of maximizing the entropy over the state-action space with a toy example shown in Figure 1. The example contains an MDP with two actions and five states. The first action always drives the agent back to the first state while the second action moves the agent to the next state. For simplicity of presentation, we consider a case with a discount factor $\gamma=1$, but other values are similar. The policy that maximizes the entropy of the state distribution is a deterministic policy that takes the actions shown in red. The dataset obtained by executing this policy is poor since the planning algorithm fails when, in the planning phase, a sparse reward is assigned to one of the state-action pairs that it visits with zero probability (e.g., a reward function $r(s,a)$ that equals to $1$ on $(s_{2},a_{1})$ and equals to $0$ otherwise). In contrast, a policy that maximizes the entropy of the state-action distribution avoids the problem. For example, executing the policy that maximizes the Rényi entropy with $\alpha=0.5$ over the state-action space, the expected size of the induced dataset is only 44 such that the dataset contains all the state-action pairs (cf. Appendix The toy example in Figure 1). Note that, when the transition dynamics is known to be deterministic, a dataset containing all the state-action pairs is sufficient for the planning algorithm to obtain an optimal policy since the full transition dynamics is known.

Why using Rényi entropy? We analyze a deterministic setting where the transition dynamics is known to be deterministic. In this setting, the objective for the framework can be expressed as a specific objective function for the exploration phase. This objective function is hard to optimize but motivates us to use Rényi entropy as the surrogate.

We define $n:=SA$ as the cardinality of the state-action space. Given an exploratory policy $\pi$, we assume the dataset is collected in a way such that the transitions in the dataset can be treated as i.i.d. samples from $d_{\mu}^{\pi}$, where $d_{\mu}^{\pi}$ is the state-action distribution induced by the policy $\pi$.

In the deterministic setting, we can recover the exact transition dynamics of the environment using a dataset of transitions that contains all the $n$ state-action pairs. Such a dataset leads to a successful planning for arbitrary reward functions, and therefore satisfies the informative condition. In order to obtain such a dataset that is also compact, we stop collecting samples if the dataset contains all the $n$ pairs. Given the distribution $d_{\mu}^{\pi}=(d_{1},\cdots,d_{n})\in\Delta^{n}$ from which we collect samples, the average size of the dataset is $G(d_{\mu}^{\pi})$, where

which is a result of the coupon collector’s problem (Flajolet, Gardy, and Thimonier 1992). Accordingly, the objective for the exploration phase can be expressed as $\min_{\pi\in\Pi}G(d_{\mu}^{\pi})$, where $\Pi$ is the set of all the feasible policies. (Notice that due to the limitation of the transition dynamics, the feasible state-action distributions form only a subset of $\Delta^{n}$.) We show the contour of this function on $\Delta^{n}$ in Figure 2a. We can see that, when any component of the distribution $d_{\mu}^{\pi}$ approaches zeros, $G(d_{\mu}^{\pi})$ increases rapidly forming a barrier indicated by the black arrow. This barrier prevents the agent to visit a state-action with a vanishing probability, and thus encourages the agent to explore the hard-to-reach state-actions.

However, this function involves an improper integral which is hard to handle, and therefore cannot be directly used as an objective function in the exploration phase. One common choice for a tractable objective function is Shannon entropy, i.e., $\max_{\pi\in\Pi}H_{1}(d_{\mu}^{\pi})$ (Hazan et al. 2019; Islam et al. 2019), whose contour is shown in Figure 2b. We can see that, Shannon entropy may still be large when some component of $d_{\mu}^{\pi}$ approaches zero (e.g., the black arrow indicates a case where the entropy is relatively large but $d_{1}\to 0$). Therefore, maximizing Shannon entropy may result in a policy that visits some state-action pair with a vanishing probability. We find that the contour of Rényi entropy (shown in Figure 2c/d) aligns better with $G(d_{\mu}^{\pi})$ and alleviates this problem. In general, the policy $\pi$ that maximizes Rényi entropy may correspond to a smaller $G(d_{\mu}^{\pi})$ than that resulted from maximizing Shannon entropy for different CMPs (more evidence of which can be found in Appendix An example to illustrate the advantage of using Rényi entropy).

Theoretical justification for the objective function. Next, we formally justify the use of Rényi entropy over the state-action space with the following theorem. For ease of analysis, we consider a standard episodic setting: The MDP has a finite planning horizon $H$ and stochastic dynamics $\mathbb{P}$ with the objective to maximize the cumulative reward $J(\pi;r):=\mathbb{E}_{s_{1}\sim\mu}[V^{\pi}(s_{1};r)]$, where $V^{\pi}(s;r):=\mathbb{E}_{\mathbb{P}}\left[\sum_{h=1}^{H}r_{h}(s_{h},a_{h})|s_{1}=s,\pi\right]$. We assume the reward function $r_{h}:\mathcal{S}\times\mathcal{A}\to[0,1],\forall h\in[H]$ is deterministic. A (non-stationary, stochastic) policy $\pi:\mathcal{S}\times[H]\to\Delta^{\mathcal{A}}$ specifies the probability of choosing the actions on each state and on each step. The state-action distribution induced by $\pi$ on the $h$-th step is $d_{h}^{\pi}(s,a):=\text{Pr}(s_{h}=s,a_{h}=a|s_{1}\sim\mu;\pi)$.

We provide the proof in Appendix Proof of Theorem 3.1. The theorem justifies that Rényi entropy with small $\alpha$ is a proper objective function for the exploration phase since the number of samples needed to ensure a successful planning is bounded when $\alpha$ is small. When $\alpha\to 1$, the bound becomes infinity. The algorithm proposed by Jin et al. (2020) requires to sample $\tilde{O}(H^{5}S^{2}A/\epsilon^{2})$ trajectories where $\tilde{O}$ hides a logarithmic factor, which matches our bound when $\alpha\to 0$. However, they construct a policy for each state on each step, whereas we only need $H$ policies which easily adapts for the non-tabular case.

In this section, we develop an algorithm for the non-tabular case. In the exploration phase, we update the policy $\pi$ to maximize $H_{\alpha}(d_{\mu}^{\pi})$. We first deduce a gradient ascent update rule which is similar to vanilla policy gradient with the reward replaced by a function of the state-action distribution of the current policy. Afterwards, we estimate the state-action distribution using VAE. We also estimate a value function and update the policy using PPO, which is more sample efficient and robust than vanilla policy gradient. Then, we obtain a dataset by collecting samples from the learned policy. In the planning phase, we use a popular batch RL algorithm, BCQ, to plan for a good policy when the reward function is specified. One may also use other batch RL algorithms. We show the pseudocode of the process in Algorithm 1, the details of which are described in the following paragraphs.

Policy gradient formulation. Let us first consider the gradient of the objective function $H_{\alpha}(d_{\mu}^{\pi})$, where the policy $\pi$ is approximated by a policy network with the parameters denoted as $\theta$. We omit the dependency of $\pi$ on $\theta$. The gradient of the objective function is

As a special case, when $\alpha\to 1$, the Rényi entropy becomes the Shannon entropy and the gradient turns into

Due to space limit, the derivation can be found in Appendix Policy gradient of state-action space entropy. There are two terms in the gradients. The first term equals to $\mathbb{E}_{(s,a)\sim d_{\mu}^{\pi}}\left[\nabla_{\theta}\log\pi(a|s)Q^{\pi}(s,a;r)\right]$ with the reward $r(s,a)=(d_{\mu}^{\pi}(s,a))^{\alpha-1}$ or $r(s,a)=-\log d_{\mu}^{\pi}(s,a)$, which resembles the policy gradient (of cumulative reward) for a standard MDP. This term encourages the policy to choose the actions that lead to the rarely visited state-action pairs. In a similar way, the second term resembles the policy gradient of instant reward $\mathbb{E}_{(s,a)\sim d_{\mu}^{\pi}}\left[\nabla_{\theta}\log\pi(a|s)r(s,a)\right]$ and encourages the agent to choose the actions that are rarely selected on the current step. The second term in (3) equals to $\nabla_{\theta}\mathbb{E}_{s\sim d_{\mu}^{\pi}}[H_{1}(\pi(\cdot|s))]$. For stability, we also replace the second term in (2) with $\nabla_{\theta}\mathbb{E}_{s\sim d_{\mu}^{\pi}}[H_{1}(\pi(\cdot|s))]$ ²²2 We found that using this term leads to more stable performance empirically since this term does not suffer from the high variance induced by the estimation of $d_{\mu}^{\pi}$ (see also Appendix Practical implementation). . Accordingly, we update the policy based on the following formula where $\eta>0$ is a hyperparameter:

Discussion. Islam et al. (2019) motivate the agent to explore by maximizing the Shannon entropy over the state space resulting in an intrinsic reward $r(s)=-\log d_{\mu}^{\pi}(s)$ which is similar to ours when $\alpha\to 1$. Bellemare et al. (2016) use an intrinsic reward $r(s,a)=\hat{N}(s,a)^{-1/2}$ where $\hat{N}(s,a)$ is an estimation of the visit count of $(s,a)$. Our algorithm with $\alpha=1/2$ induces a similar reward.

Sample collection. To estimate $d_{\mu}^{\pi}$ for calculating the underlying reward, we collect samples in the following way (cf. Line 5 in Algorithm 1): In the $i$-th iteration, we sample $m$ trajectories. In each trajectory, we terminate the rollout on each step with probability $1-\gamma$. In this way, we obtain a set of trajectories $\mathcal{D}_{i}=\{(s_{j1},a_{j1}),\cdots,(s_{jN_{j}},a_{jN_{j}})\}_{j=1}^{m}$ where $N_{j}$ is the length of the $j$-th trajectory. Then, we can use VAE to estimate $d_{\mu}^{\pi}$ based on $\mathcal{D}_{i}$, i.e., using ELBO as the density estimation (cf. Line 6 in Algorithm 1).

Value function. Instead of performing vanilla policy gradient, we update the policy using PPO which is more robust and sample efficient. However, the underlying reward function changes across iterations. This makes it hard to learn a value function incrementally that is used to reduce variance in PPO. We propose to train a value function network using relabeled off-policy data. In the $i$-th iteration, we maintain a replay buffer $\mathcal{D}=\mathcal{D}_{i}\cup\mathcal{D}_{i-1}\cup\cdots\cup\mathcal{D}_{i-n+1}$ that stores the trajectories of the last $n$ iterations (cf. Line 5 in Algorithm 1). Next, we calculate the reward for each state-action pair in $\mathcal{D}$ with the latest density estimator $P_{\phi}$, i.e., we assign $r=(P_{\phi}(s,a))^{\alpha-1}$ or $r=-\log P_{\phi}(s,a)$ for each $(s,a)\in\mathcal{D}$. Based on these rewards, we can estimate the target value $V^{\text{targ}}(s)$ for each state $s\in\mathcal{D}$ using the truncated TD($\lambda$) estimator (Sutton and Barto 2018) which balances bias and variance (see the detail in Appendix Value function estimator). Then, we train the value function network $V_{\psi}$ (where $\psi$ is the parameter) to minimize the mean squared error w.r.t. the target values:

Policy network. In each iteration, we update the policy network to maximize the following objective function that is used in PPO:

where $g(\varepsilon,A)=\begin{cases}(1+\varepsilon)A&A\geq 0\\ (1-\varepsilon)A&A<0\end{cases}$ and $\hat{A}(s,a)$ is the advantage estimated using GAE (Schulman et al. 2016) and the learned value function $V_{\phi}$.

We first conduct experiments on the MultiRooms environment from minigrid (Chevalier-Boisvert, Willems, and Pal 2018) to compare the performance of MaxRenyi with several baseline exploration algorithms in the exploration phase and the downstream planning phase. We also compare the performance of MaxRenyi with different $\alpha$s, and show the advantage of using a PPO based algorithm and maximizing the entropy over the state-action space by comparing with ablated versions. Then, we conduct experiments on a set of Atari (with image-based observations) (Machado et al. 2018) and Mujoco (Todorov, Erez, and Tassa 2012) tasks to show that our algorithm outperforms the baselines in complex environments for the reward-free RL framework. We also provide detailed results to investigate why our algorithm succeeds. More experiments and the detailed experiment settings/hyperparameters can be found in Appendix Experiment settings, hyperparameters and more experiments..

Experiments on MultiRooms. The observation in MultiRooms is the first person perspective from the agent which is high-dimensional and partially observable, and the actions are turning left/right, moving forward and opening the door (cf. Figure 3a above). This environment is hard to explore for standard RL algorithms due to sparse reward. In the exploration phase, the agent has to navigate and open the doors to explore through a series of rooms. In the planning phase, we randomly assign a goal state-action pair, reward the agent upon this state-action, and then train a policy with this reward function. We compare our exploration algorithm MaxRenyi with ICM (Pathak et al. 2017), RND (Burda et al. 2019b) (which use different prediction errors as the intrinsic reward), MaxEnt (Hazan et al. 2019) (which maximizes the state space entropy) and an ablated version of our algorithm MaxRenyi(VPG) (that updates the policy directly by vanilla policy gradient using (2) and (3)).

For the exploration phase, we show the performance of different algorithms in Figure 3b. First, we see that variants of MaxRenyi performs better than the baseline algorithms. Specifically, MaxRenyi is more stable than ICM and RND that explores well at the start but later degenerates when the agent becomes familiar with all the states. Second, we observe that MaxRenyi performs better than MaxRenyi(VPG) with different $\alpha$s, indicating that MaxRenyi benefits from adopting PPO which reduces variance with a value function and update the policy conservatively. Third, MaxRenyi with $\alpha=0.5$ performs better than $\alpha=1$ which is consistent with our theory. However, we observe that MaxRenyi with $\alpha=0$ is more likely to be unstable empirically and results in slightly worse performance. At last, we show the visitation frequency of the exploratory policies resulted from different algorithms in Figure 3a. We see that MaxRenyi visits the states more uniformly compared with the baseline algorithms, especially the hard-to-reach states such as the corners of the rooms.

For the planning phase, we collect datasets of different sizes by executing different exploratory policies, and use the datasets to compute policies with different reward functions using BCQ. We show the performance of the resultant policies in Figure 3c. First, we observe that the datasets generated by running random policies do not lead to a successful planning, indicating the importance of learning a good exploratory policy in this framework. Second, the dataset with only 8k samples leads to a successful planning (with a normalized cumulative reward larger than 0.8) using MaxRenyi, whereas a dataset with 16k samples is needed to succeed in the planning phase when using ICM, RND or MaxEnt. This illustrates that MaxRenyi leads to a better performance in the planning phase (i.e., attains good policies with fewer samples) than the previous exploration algorithms.

Further, we compare MaxRenyi that maximizes the entropy over the state-action space with two ablated versions: “State + bonus” that maximizes the entropy over the state space with an entropy bonus (i.e., using $P_{\phi}$ to estimate the state distribution in Algorithm 1), and “State” that maximizes the entropy over the state space (i.e., additionally setting $\eta=0$ in (6)). Notice that the reward-free RL framework requires that a good policy is obtained for arbitrary reward functions in the planning phase. Therefore, we show the lowest normalized cumulative reward of the planned policies across different reward functions for the algorithms in Table 1. We see that maximizing the entropy over the state-action space results in better performance for this framework.

Experiments on Atari and Mujoco. In the exploration phase, we run different exploration algorithms in the reward-free environment of Atari (Mujoco) for 200M (10M) steps and collect a dataset with 100M (5M) samples by executing the learned policy. In the planning phase, a policy is computed offline to maximize the performance under the extrinsic game reward using the batch RL algorithm based on the dataset. We show the performance of the planned policies in Table 2. We can see that MaxRenyi performs well on a range of tasks with high-dimensional observations or continuous state-actions for the reward-free RL framework.

We also provide detailed results for Montezuma’s Revenge and Hopper. For Montezuma’s Revenge, we show the result for the exploration phase in Figure 4a. We observe that although MaxRenyi learns an exploratory policy in a reward-free environment, it achieves reasonable performance under the extrinsic game reward and performs better than RND and ICM. We also provide the number of visited rooms along the training in Appendix Experiment settings, hyperparameters and more experiments., which demonstrates that our algorithm performs better in terms of the state space coverage as well. In the planning phase, we design two different sparse reward functions that only reward the agent if it goes through Room 3 or Room 7 (to the next room). We show the trajectories of the policies planned with the two reward functions in red and blue respectively in Figure 4b. We see that although the reward functions are sparse, the agent chooses the correct path (e.g., opening the correct door in Room 1 with the only key) and successfully reaches the specified room. This indicates that our algorithm generates good policies for different reward functions based on an offline planning in complex environments. For Hopper, we show the t-SNE (Maaten and Hinton 2008) plot of the state-actions randomly sampled from the trajectories generated by different policies in Figure 5. We can see that MaxRenyi generates state-actions that are distributed more uniformly than RND and overlap those from the expert policy. This indicates that the good performance of our algorithm in the planning phase is resulted from the better coverage of our exploratory policy.

In this paper, we consider a reward-free RL framework, which is useful when there are multiple reward functions of interest or when we design reward functions offline. In this framework, an exploratory policy is learned by interacting with a reward-free environment in the exploration phase and generates a dataset. In the planning phase, when the reward function is specified, a policy is computed offline to maximize the corresponding cumulative reward using the batch RL algorithm based on the dataset. We propose a novel objective function, the Rényi entropy over the state-action space, for the exploration phase. We theoretically justify this objective and design a practical algorithm to optimize for this objective. In the experiments, we show that our exploration algorithm is effective under this framework, while being more sample efficient and more robust than the previous exploration algorithms.

Chuheng Zhang and Jian Li are supported in part by the National Natural Science Foundation of China Grant 61822203, 61772297, 61632016, 61761146003, and the Zhongguancun Haihua Institute for Frontier Information Technology, Turing AI Institute of Nanjing and Xi’an Institute for Interdisciplinary Information Core Technology. Yuanying Cai and Longbo Huang are supported in part by the National Natural Science Foundation of China Grant 61672316, and the Zhongguancun Haihua Institute for Frontier Information Technology, China.

In this example, the initial state is fixed to be $s_{1}$. Due to the simplicity of this toy example, we can solve for the policy that maximizes the Rényi entropy of the state-action distribution with $\gamma\to 1$ and $\alpha=0.5$. The optimal policy is

where $\pi_{i,j}$ represents the probability of choosing $a_{i}$ on $s_{j}$. The corresponding state-action distribution is

where the $(i,j)$-th element represents the probability density of the state-action distribution on $(s_{j},a_{i})$. Using equation (1), we obtain $G(d_{\mu}^{\pi})=43.14$ which is the expected number of samples collected form this distribution that contains all the state-action pairs.

Although we did not justify theoretically that Rényi entropy serves as a better surrogate function of $G$ than Shannon entropy in the main text, here we illustrate that this may hold in general. Specifically, we try to show that the corresponding $G$ of the policy that maximizes Rényi entropy with small $\alpha$ is always smaller than that of the policy that maximizes Shannon entropy. Notice that when the dynamics is known to be deterministic, $G$ indicates how many samples are needed in expectation to ensure a successful planning. In the stochastic setting, $G$ also serves as a good indicator since this is the lower bound of the number of samples needed for a successful planning.

To show that Rényi entropy is a good surrogate function, we can use brute-force search to check if there exists a CMP on which the Shannon entropy is better than Rényi entropy in terms of $G$. As an illustration, we only consider CMPs with two states and two actions. Specifically, for this family of CMPs, there are 5 free parameters to be searched: 4 parameters for the transition dynamics and 1 parameter for the initial state distribution. We set step size for searching to 0.1 for each parameter and use $\alpha=0.1$, $\gamma=0.9$. The result shows there does not exists any CMP on which the Shannon entropy is better than Rényi entropy in term of $G$ out of the searched $10^{5}$ CMPs.

To further investigate, we consider a specific CMP. The transition matrix $P\in\mathbb{R}^{SA\times S}$ of this CMP is

where the rows corresponds to $(s_{1},a_{1}),(s_{1},a_{2}),(s_{2},a_{1}),(s_{2},a_{2})$ respectively and the columns corresponds the next states ($s_{1}$ and $s_{2}$ respectively). The initial state distribution of this CMP is

For this CMP, the $G$ value of the policy that maximizes Shannon entropy is 88, while the values are only 39 and 47 for policies that maximize Rényi entropy with $\alpha=0.1$, $\alpha=0.5$ respectively. The optimal $G$ value is 32. This indicates that we may need 2x more samples to accurately estimate the dynamics of the CMP. We observe $s_{2}$ is much harder to reach than $s_{1}$ on this CMP: The initial state is always $s_{1}$ and taking action $a_{1}$ will always reach $s_{1}$. In order to visit $s_{2}$ more, policies should take $a_{2}$ with a high probability on $s_{1}$. In fact, the policy that maximizes Shannon entropy takes $a_{2}$ on $s_{1}$ with the probability of only 0.58, while the policies that maximize Rényi entropy with $\alpha=0.1$ and $\alpha=0.5$ take $a_{2}$ on $s_{1}$ with probabilities 0.71 and 0.64 respectively.

This example illustrates the following essence that widely exists in other CMPs: A good objective function should encourage the policy to visit the hard-to-reach state-actions as frequently as possible and Rényi entropy does a better job than Shannon entropy from this perspective.

We provide Theorem 3.1 to justify our objective that maximizes the entropy over the state-action space in the exploration phase for the reward-free RL framework. In the following analysis, we consider the standard episodic and tabular case as follows: The MDP is defined as $\langle\mathcal{S},\mathcal{A},H,\mathbb{P},r,\mu\rangle$, where $\mathcal{S}$ is the state space with $S=|\mathcal{S}|$, $\mathcal{A}$ is the action space with $A=|\mathcal{A}|$, $H$ is the length of each episode, $\mathbb{P}=\{\mathbb{P}_{h}:h\in[H]\}$ is the set of unknown transition matrices, $r=\{r_{h}:h\in[H]\}$ is the set of the reward functions and $\mu$ is the unknown initial state distribution. We denote $\mathbb{P}_{h}(s^{\prime}|s,a)$ as the transition probability from $(s,a)$ to $s^{\prime}$ on the $h$-th step. We assume that the instant reward for taking the action $a$ on the state $s$ on the $h$-th step $r_{h}(s,a)\in[0,1]$ is deterministic. A policy $\pi:\mathcal{S}\times[H]\to\Delta^{\mathcal{A}}$ specifies the probability of choosing the actions on each state and on each step. We denote the set of all such policies as $\Pi$.

The agent with policy $\pi$ interacts with the MDP as follows: At the start of each episode, an initial state $s_{1}$ is sampled from the distribution $\mu$. Next, at each step $h\in[H]$, the agent first observes the state $s_{h}\in\mathcal{S}$ and then selects an action $a_{h}$ from the distribution $\pi(s_{h},h)$. The environment returns the reward $r_{h}(s_{h},a_{h})\in[0,1]$ and transits to the next state $s_{h+1}\in\mathcal{S}$ according to the probability $\mathbb{P}_{h}(\cdot|s_{h},a_{h})$. The state-action distribution induced by $\pi$ on the $h$-th step is $d_{h}^{\pi}(s,a):=\text{Pr}(s_{h}=s,a_{h}=a|s_{1}\sim\mu;\pi)$.

The state value function for a policy $\pi$ is defined as $V_{h}^{\pi}(s;r):=\mathbb{E}\left[\sum_{t=h}^{H}r_{t}(s_{t},a_{t})|s_{h}=s,\pi\right]$. The objective is to find a policy $\pi$ that maximizes the cumulative reward $J(\pi;r):=\mathbb{E}_{s_{1}\sim\mu}[V_{1}^{\pi}(s_{1};r)]$.

The proof goes through in a similar way to that of Jin et al. (2020).

Hazan et al. (Hazan et al. 2019) proved the convexity of such feasible regions in the infinite-horizon and discounted setting. For completeness, we provide a similar proof on the convexity of $\mathcal{K}_{h}$ in the episodic setting.

Similar to Jin et al. (Jin et al. 2020), we define $\delta$-significance for state-action pairs on each step and show that the policy that maximizes Rényi entropy is able to reasonably uniformly visit the significant state-action pairs.

Recall the way we construct the dataset $\mathcal{M}$: With the set of policies $\varpi:=\{\pi^{(h)}\}_{h=1}^{H}$ where $\pi^{(h)}:S\times[H]\to\Delta^{\mathcal{A}}$ and $\pi^{(h)}\in arg\max_{\pi}H_{\alpha}(d_{h}^{\pi}),\forall h\in[H]$, we first uniformly randomly choose a policy $\pi$ from $\varpi$ at the start of each episode, and then execute the policy $\pi$ through the episode. Note that there is a set of policies that maximize the Rényi entropy on the $h$-th layer since the policy on the subsequent layers does not affect the entropy on the $h$-th layer. We denote the induced state-action distribution on the $h$-th step as $\mu_{h}$, i.e., the dataset $\mathcal{M}$ can be regarded as being sampled from $\mu_{h}$ for each step $h\in[H]$. Therefore, $\mu_{h}(s,a)=\frac{1}{H}\sum_{t=1}^{H}d_{h}^{\pi^{(t)}}(s,a),\forall s\in\mathcal{S},a\in\mathcal{A},h\in[H]$.

When $\alpha\to 0^{+}$, we have

When $\alpha=\frac{1}{2}$,