On Principled Entropy Exploration in Policy Optimization

1 Introduction

Deep reinforcement learning (RL) has recently shown to be remarkably effective in solving challenging sequential decision making problems [Schulman et al., 2015; Mnih et al., 2015; Silver et al., 2016]. A central method of deep RL is policy optimization, which is based on formulating the problem as the optimization of a stochastic objective (expected return) of the underlying policy parameters [Williams and Peng, 1991; Williams, 1992; Sutton et al., 1998]. Unlike standard optimization, policy optimization requires the objective and gradient to be estimated from data, typically gathered from a process depending on current parameters, simultaneously with parameter updates. Such an interaction between estimation and updating complicates the optimization process, and often necessitates the introduction of variance reduction methods, leading to algorithms with subtle hyperparameter sensitivity. Joint estimation and updating can also create poor local optima whenever sampling neglect of some region can lead to further entrenchment of a current solution. For example, a non-exploring policy might fail to sample from high reward trajectories, preventing any further improvement since no useful signal is observed. In practice, it is well known that successful application of deep RL techniques requires a combination of extensive hyperparameter tuning, and a large, if not impractical, number of sampled trajectories. It remains a major challenge to develop methods that can reliably perform policy improvement while maintaining sufficient exploration and avoiding poor local optima, yet do so quickly.

∗Equal contribution

Several ideas for improving policy optimization have been proposed, generally focusing on the goals of improving stability and data efficiency [Peters et al., 2010; Van Hoof et al., 2015; Fox et al., 2015; Schulman et al., 2015; Montgomery and Levine, 2016; Nachum et al., 2017b; Abdolmaleki et al., 2018; Haarnoja et al., 2018]. Unfortunately, a notable gap remains between empirically successful methods and their underlying theoretical support. Current analyses typically assume a simplified setting that either ignores the policy parametrization or only considers linear models. These assumptions are hard to justify when current practice relies on complex function approximators, such as deep neural networks, that are highly nonlinear in their underlying parameters. This gulf between theory and practice is a barrier to wider adoption of model-free policy gradient methods.

In this paper, we consider the maximum entropy reward objective, which has recently re-emerged as a foundation for state-of-the-art RL methods [Fox et al., 2015; Schulman et al., 2017a; Nachum et al., 2017b; Haarnoja et al., 2017; Neu et al., 2017; Levine, 2018; Deisenroth et al., 2013; Daniel et al., 2012]. We first reformulate the maximization of this objective as a lift-and-project procedure, following Mirror Descent [Nemirovskii et al., 1983; Beck and Teboulle, 2003]. We establish a monotonic improvement guarantee and the fixed point properties of this setup. The reformulation also has practical algorithmic consequences, suggesting that multiple gradient updates should be performed in the projection. These considerations lead to the Policy Mirror Descent (PMD) algorithm, which first lifts the policy to the simplex, ignoring the parametrization constraint, then approximately solves the projection by gradient updates in the parameter space.

We then investigate additional improvements to mitigate the potential deficiencies of PMD. The main algorithm we propose, Exploratory Conservative Policy Optimization (ECPO), incorporates both an entropy and relative entropy regularizer, and uses the mean seeking KL divergence for projection, which helps avoids poor deterministic policies. The projection can be efficiently solved to global optimality in certain non-convex cases, such as one-layer softmax networks. The entropy exploration is principled. Firstly, in the convex subset setting, the algorithm enjoys sublinear regret. Secondly, we prove monotonic guarantees for ECPO with respect to a surrogate objective SR(π). We further study the properties of SR(π) and provide theoretical and empirical evidence that SR can effectively guide good policy search. Finally, we also extend this algorithm using value function approximations, and develop an actor-critic version that is effective in practice.

1.1 Notation and Problem Setting

We consider episodic settings with finite state and action spaces. The agent is modelled by a policy π(·|s) that specifies a probability distribution overs actions given state s. At each step t, the agent takes an action at by sampling from π(·|st). The environment then returns a reward rt = r(st, at) and the next state st+1 = f(st, at), where f is the transition not revealed to the agent. Given a trajectory, a sequence of states and actions ρ = (s1, a1, . . . , aT-1, sT ), the policy probability and the total reward of ρ are defined as π(ρ) = ∏T-1 t=1 π(at|st) and r(ρ) = ∑T-1 t=1 r(st, at). Given a set of parametrized policy functions πθ ∈ Π, policy optimization aims to find the optimal policy π∗ θ by maximizing the expected reward,

We use ∆ ≜ {π| ∑ρ π(ρ) = 1, π(ρ) ≥ 0, ∀ρ} to refer to the probability simplex over all trajectories. Without loss of generality, we assume that the state transition is deterministic, and the discount factor γ = 1. All theoretical results for the general stochastic environment are presented in the appendix.

2 PolicyMirror Descent

We first introduce the Policy Mirror Descent (PMD) strategy, which forms the basis for our algorithms. Consider the following optimization problem: given a reference policy ¯π (usually the current policy), maximize the proximal regularized expected reward, using relative entropy as the regularizer:

Relative entropy has been widely studied in online learning and optimization [Nemirovskii et al., 1983; Beck and Teboulle, 2003], primarily as a component of the mirror descent method. This regularization makes the policy update in a conservative fashion, by searching policies within the neighbours of the current policy. In practice πθ is usually parametrized as a function of θ ∈ Rd and Π is generally a non-convex set. Therefore, Eq. (2) is a difficult constrained optimization problem.

One useful way to decompose Eq. (2) is to consider an alternating lift-and-project procedure.

Crucially, Eq. (3) remains equivalent to Eq. (2), in that it preserves the same solution, as established in Proposition 1.

Proposition 1. Given a reference policy ¯π,

Note this result holds even for the non-convex setting. Eq. (3) immediately leads to the PMD algorithm: Lift the current policy πθt to ¯π∗ τ , then perform multiple steps of gradient descent in the Project step to update πθt+1 . 1

When Π is convex, PMD converges to the optimal policy [Nemirovskii et al., 1983; Beck and Teboulle, 2003]. For general Π, PMD still enjoys desirable properties.

Proposition 2. PMD satisfies the following properties for an arbitrary parametrization Π.

1. (Monotonic Improvement) If the Project step min πθ∈Π DKL(πθ‖¯π∗ τ ) can be globally solved, then

1. (FixedPoints) If the Project step is optimized by gradient descent, then the fixed points of PMD are stationary points of Eρ∼πθ r(ρ).

Proposition 2 relies on the condition that the Project step in PMD is solved to global optimality. It is usually not practical to achieve such a stringent requirement when Π is not convex, limiting the applicability of Proposition 2.

Another shortcoming is that PMD typically gets trapped in poor local optima. The regularizer helps prevent large policy updates, it also tends to limit exploration. Moreover, minimizing DKL(πθ‖¯π∗ τ ) is known to be mode seeking [Murphy, 2012], which can lead to mode collapse during learning. Once a policy has lost important modes, learning can easily become trapped at a sub-optimal policy. Unfortunately, at such points, the regularizer does not encourage further exploration.

3 Exploratory Conservative Policy Optimization

We propose two modifications to PMD that overcome the aforementioned deficiencies. These two modifications lead to our proposed algorithm, Exploratory Conservative Policy Optimization (ECPO), which retains desirable theoretical properties while achieving superior performance to PMD in practice.

The first modification is to add an additional entropy regularizer in the Lift step, to improve the exploration. The second modification is to use a reversed, mean seeking direction of KL divergence in the Project step. In particular, the ECPO algorithm solves the following alternating optimization problems:

The effect of minimizing the other KL direction is well known [Murphy, 2012] and has proved to be effective [Norouzi

1 To estimate this gradient one would need to use self-normalized importance sampling [Owen, 2013]. We omit the details here since PMD is not our main algorithm; similar techniques can be found in the implementation of ECPO.

Algorithm 1 The ECPO algorithm

Input: temperature parameters τ and τ ′ , number of samples for computing gradient K

• 1: Random initialized πθ
• 2: For t = 1, 2, . . . do
• 3: Set ¯π = πθ
• 4: Repeat
• 5: Sample a mini-batch of K trajectories from ¯π
• 6: Compute the gradient according to Eq. (6)
• 7: Update πθ by gradient descent
• 8: Until t reaches maximum of training steps
• 9: end For

et al., 2016; Nachum et al., 2017a]. In particular, minimizing DKL(πθ‖q) usually underestimates the support of q, since the objective is infinite if q = 0 and πθ > 0. Thus, πθ is driven to 0 wherever q = 0. The problem is that when q changes, πθ can have zero mass on trajectories that have nonzero probability under the new q, hence πθ will never capture this part of q, leading to mode collapse. By contrast, minimizing DKL(q‖πθ) is zero-avoiding in πθ, since if q > 0 we must ensure πθ > 0. Note that by Eq. (5): (a) the q in our method is nonzero everywhere, (b) we further add entropy in Eq. (4) to avoid q prematurely converging to a deterministic policy, (c) DKL(q‖πθ) is zero-avoiding for minimization over πθ. These ensure that the proposed method does not exhibit the same mode-seeking behavior as MD. As we will see in Section 5, ECPO outperforms PMD significantly in experiments.

3.1 Learning Algorithms

We now provide practical learning algorithms for Eq. (4). The Lift Step has an analytic solution,

where we take πθt as the reference policy ¯π. The Project Step in Eq. (4), minπθ∈ΠDKL(¯π∗ τ,τ ′‖πθ), can be optimized via stochastic gradient descent, given that one can sample trajectories from ¯π∗ τ,τ ′ . The next lemma shows that sampling from ¯π∗ τ,τ ′ can be done using self-normalized importance sampling [Owen, 2013] when it is possible to draw multiple samples from ¯π, following the idea of UREX [Nachum et al., 2017a].

Lemma 1. Let ωk = r(ρk)-τ ′ log ¯π(ρk) τ+τ ′ . Given K i.i.d. samples {ρ1, . . . , ρK} from the reference policy ¯π, we have the following unbiased gradient estimator,

The Pseudocode is presented in Algorithm 1. Derivation for the analytic solution of the Lift step and above Lemma as well as other implementation details can be found in the appendix.

3.2 Analysis of ECPO

We now present the theoretical analysis of ECPO. Our first result shows that, ECPO enjoys sublinear regret by a particularly designed choice of τ and τ ′ , when the policy class is any convex subset of the probabilistic simplex, recovering the simplex setting as a special case.

Theorem 1. When the policy class Π is a convex subset of the probabilistic simplex, by choosing τ ′ = 1/√T log n, and τ + τ ′ = √T/√2 log n, (or τ ′ = 1/√t log n, and τ + τ ′ = √t/√2 log n), ∀π ∈ Π,

where πt is defined by Eq. (5) with πt-1 as the reference policy, and n is the total action/trajectory number.

Our second result shows that ECPO enjoys similar desirable properties (Proposition 2) to PMD in general settings, with respect to the surrogate reward SR(πθ).

Theorem 2. ECPO satisfies the following properties for an arbitrary parametrization Π.

1. (Monotonic Improvement) If the Project step DKL(¯π∗ τ,τ ′‖πθ) can be globally solved, then

where

1. (FixedPoints) If the Project step is optimized by gradient descent, then the fixed points of ECPO are stationary points of SR(πθ).

Theorem 2 establishes desirable properties for ECPO of SR(πθ), but not necessarily Eρ∼πθ r(ρ). However, SR(πθ) is a reasonable surrogate that can provide good guidance for learning. By properly adjusting the two temperature parameters τ and τ ′ , SR(πθ) recovers existing performance measures.

Lemma 2. Let ˆ r = r-τ ′ logπ, ˆ r∞ = ‖ˆ r‖∞ and η = τ +τ ′ . For any policy π and τ ≥ 0, τ ′ ≥ 0, we have

Furthermore,

A key question is the feasibility of solving the Project step to global optimality. For a one-layer softmax network policy, the Project stepDKL(¯π∗ τ,τ ′ ‖πθ) can be solved to global optimality, affording computational advantages over PMD.

Proposition 3. Suppose πθ(s) = softmax(φ⊤s θ). Given any ¯π, DKL(¯π‖πθ) is a convex function of θ.

4 An Actor-Critic Extension

Finally, we develop a natural actor-critic extension of ECPO by incorporating a value function approximator. We refer to this algorithm as Exploratory Conservative Actor-Critic (ECAC).

The data efficiency of policy-based methods can be generally improved by adding a value-based critic. Given ¯π and an initial state s, the objective in the Lift step of ECPO is

where ρ = (s1 = s, a1, s2, a2, . . .). To incorporate value function, we need temporal consistency for this objective:

Denote ¯π∗ τ,τ ′(·|s) ≜ argmaxπ OECPO(π, s) the optimal policy on state s. Denote the soft optimal state-value function OECPO(¯π∗ τ,τ ′(·|s), s) by ¯ V ∗ τ,τ ′(s), and let ¯Q∗τ,τ ′(s, a) = r(s, a) + γ ¯ V ∗ τ,τ ′ (s′ ) be the soft-Q function. We have,

We propose to train a soft state-value function Vφ parameterized by φ, a soft Q-function Qψ parameterized by ψ, and a policy πθ parameterized by θ, based on Eq. (4). The update rules for these parameters can be derived as follows.

The soft state-value function approximates the soft optimal state-value ¯ V ∗ τ,τ ′ , which can be re-expressed by

This suggests a Monte-Carlo estimate for ¯ V ∗ τ,τ ′(s): by sampling one single action a according to the reference policy ¯π, we have ¯ V ∗ τ,τ ′ (s) ≈ ¯Q∗τ,τ ′ (s, a) - τ ′ log ¯π(a|s). Then, given a replay buffer D, the soft state-value function can be trained to minimize the mean squared error,

One might note that, in principle, there is no need to include a separate state-value approximation, since it can be directly computed from a soft-Q function and reference policy, using Eq. (8). However, including a separate function approximator for the state-value can help stabilize the training [Haarnoja et al., 2018]. The soft Q-function parameters ψ is then trained to minimize the soft Bellman error using the state-value network,

The policy parameters are updated by performing the Project Step in Eq. (4) with stochastic gradient descent,

where we approximate ¯π∗ τ,τ ′ by the soft-Q and state-value function approximations.

Finally, we also use a target state-value network [Lillicrap et al., 2015] and the trick of maintaining two soft-Q functions [Haarnoja et al., 2018; Fujimoto et al., 2018].

5 Experiments

We evaluate ECPO and ECAC on a number of benchmark tasks against strong baseline methods. Implementation details are provided in the appendix.

5.1 Settings

We first investigate the performance of ECPO on a synthetic bandit problem, which has 10000 distinct actions. The reward of each action i is initialized by ri = s8i such that si is randomly sampled from a uniform [0, 1) distribution. Each action i is represented by a random feature vector ωi ∈ R20 from a standard Gaussian, and it is fixed during training. We further test ECPO on five algorithmic tasks from the OpenAI gym [Brockman et al., 2016] library, in rough order of difficulty: Copy, DuplicatedInput, RepeatCopy, Reverse, and ReversedAddition [Brockman et al., 2016]. Second, we test ECAC on continuous-control benchmarks from the OpenAI Gym, utilizing the MuJoCo environment [Brockman et al., 2016; Todorov et al., 2012]; including Hopper, Walker2d, HalfCheetah, Ant and Humanoid.

Only cumulative rewards are used in the synthetic bandit and algorithmic tasks. Therefore, value-based methods cannot be applied here, which compels us to compare ECPO against REINFORCE with entropy regularization (MENT) [Williams, 1992], and under-appreciated reward exploration (UREX) [Nachum et al., 2017a], which are state-of-the-art policy-based algorithms for the algorithmic tasks. For the continuous control tasks, we compare ECAC with deep deterministic policy gradient (DDPG) [Lillicrap et al., 2015], an efficient off-policy deep RL method; twin delayed deep deterministic policy gradient algorithm (TD3) [Fujimoto et al., 2018], a recent extension of DDPG by using double Q-learning; and Soft-Actor-Critic (SAC) [Haarnoja et al., 2018], a recent state-of-the-art offpolicy algorithm on a number of benchmarks. All of these algorithms are implemented in rlkit. 2 We do not include TRPO and PPO in these experiments, as their performances are dominated by SAC and TD3, as shown in [Haarnoja et al., 2018; Fujimoto et al., 2018].

5.2 Comparative Evaluation

The results on synthetic bandit and algorithmic tasks are in Fig. 1. ECPO substantially outperforms the baselines. ECPO is able to consistently achieve a higher score substantially faster than UREX. We also find the performance of UREX is unstable. On the difficult tasks, including RepeatCopy, Reverse and ReversedAddition, UREX only finds solutions a few times out of 25 runs, which brings the overall scores down. This observation explains the gap between the results we find here and those in [Nachum et al., 2017a]. 3 Note that the performance of ECPO is still significantly better than UREX even compared to the results in [Nachum et al., 2017a].

Fig. 2 presents the continuous control benchmarks, reporting the mean returns on evaluation rollouts obtained by the algorithms during learning. The results are averaged over five instances with different random seeds. The solid curves corresponds to the mean and the shaded region to the standard errors over the five trials. We observe that the reparameterization trick dramatically improve the performance of SAC. Therefore, to gain further clarity, we also report the result of SAC with the reparameterization trick, denoted SAC+R. The results show that ECAC matches or, in many cases, surpasses all other baseline algorithms in both final performance and sample efficiency across tasks, except compared to SAC+R in Humanoid. In Humanoid, although SAC+R outperforms ECAC, its final performance is still comparable with SAC+R.

2 https://github.com/vitchyr/rlkit

3 The results reported in [Nachum et al., 2017a] are averaged over 5 runs of random restarting, while our results are averaged over 25 random training runs (5 runs × 5 random seed for neural network initialization).

5.3 Ablation Study

The comparative evaluations provided before suggest that our proposed algorithms outperform conventional RL methods on a number of challenging benchmarks. In this section, we further investigate how each novel component of Eq. (4) improves learning performance, by performing an ablation study on ReversedAddition and Ant. The results are presented in Fig. 3, which clearly indicate all of the three major components of Eq. (4) are helpful for achieving better performance.

Importance of entropy regularizer. The main difference between the objective in Eq. (4) and the PMD objective Eq. (3) is the entropy regularizer. We demonstrate the importance of this choice by presenting the results of ECPO and ECAC without the extra entropy regularizer, i.e. τ ′ = 0.

Importance of KL divergence projection. Another important difference between Eq. (4) with other RL methods is to use a Project Step to update the policy, rather than one SGD. To show the importance of the Project Step, we test ECPO and ECAC without projection, which only performs one step of gradient update at each iteration of training.

Importance of direction of KL divergence. We choose PMD Eq. (3) as another baseline to prove the effectiveness of using the mean seeking direction of KL divergence in the project step. Similar to ECPO, we add a separate temperature parameter τ ′ > 0 to the original objective function in Eq. (3) to encourage policy exploration, which gives argmaxπθ∈ΠEρ∼πθ r(ρ) - τKL(πθ‖¯π) + τ ′H(πθ). We name it PMD+entropy. The corresponding algorithms in the actor-critic setting, named PMD-AC and PMD-AC+entropy, are also implemented for comparison.

6 RelatedWork

The lift-and-project approach is distinct from the previous literature on policy search, with the exception of a few recent works: Mirror Descent Guided Policy Search (MDGPS) [Montgomery and Levine, 2016], Guide Actor-Critic (GAC) [Tangkaratt et al., 2017], Maxmimum aposteriori (MPO) [Abdolmaleki et al., 2018], and Soft Actor-Critic (SAC) [Haarnoja et al., 2018]. These approaches also adopt a mirror descent framework, but differ from the proposed approach in key aspects. MDGPS [Montgomery and Levine, 2016] follows a different learning principle, using the Lift Step to learn multiple local policies (rather than a single policy) then aligning these with a global policy in the Project Step. MDGPS does not include the entropy term in the Lift objective, which we have found to be essential for exploration. MPO [Abdolmaleki et al., 2018] also neglects to add the additional entropy term. Alternatively, MPO imposes a KL constraint in its projection to avoid entropy collapse in policy update. Section 5.3 shows that entropy regularization with an appropriate annealing of τ ′ significantly improves learning efficiency. Both GAC and SAC use the mode seeking KL divergence in the Project Step, in opposition to the mean seeking direction we consider here [Tangkaratt et al., 2017; Haarnoja et al., 2018]. Additionally, SAC only uses entropy in the Lift Step, neglecting the proximal relative entropy. The benefits of regularizing with relative entropy has been discussed in TRPO [Schulman et al., 2015] and MPO [Abdolmaleki et al., 2018], where it is noted that proximal regularization significantly improves learning stability. Another point is the reparameterization trick used in SAC and MPO relies on the Gaussian represetation for the continuous action space, which makes them cannot be used in discrete spaces, where our ECPO performs well. GAC seeks to match the mean of Gaussian policies under second order approximation in the Project Step, instead of directly minimizing the KL divergence with gradient descent. Although one might also attempt to interpret "one-step" methods in terms of lift-and-project, these approaches would obliviously still differ from ECPO, given that we use different directions of the KL divergence for the Lift and Project steps respectively.

TRPO and PPO have similar formulations to Eq. (2), using constraints of mean seeking KL divergence [Schulman et al., 2015; Schulman et al., 2017b]. Our proposed method includes additional modifications that, as shown in Section 5, significantly improve performance. UREX also uses mean seeking KL for regularization, which encourages exploration but also complicates the optimization; as shown in Section 5, UREX is significantly less efficient than the method proposed here.

Trust-PCL adopts the same objective Eq. (4), including both entropy and relative entropy regularization [Nachum et al., 2017c]. However, the policy update is substantially different: while ECPO uses KL projection, Trust-PCL minimizes a path inconsistency error between the value and policy along observed trajectories [Nachum et al., 2017b]. Although policy optimization by minimizing path inconsistency error can efficiently utilize off-policy data, this approach loses the desirable monotonic improvement guarantee.

7 Conclusion and FutureWork

We have proposed Exploratory Conservative Policy Optimization (ECPO) as an effective new approach for policy based reinforcement learning that also guarantees monotonic improvement in a well motivated objective. We show that the resulting method achieves better exploration than both a directed exploration strategy (UREX) and undirected maximum entropy exploration (MENT). It will be interesting to further extend the follow-on ECAC actor-critic framework with further development of the value function learning approach.

Acknowledgements

Part of the work has been done when the first two authors were interns in Borealis AI Lab. We gratefully acknowledge funding from Canada's Natural Sciences and Engineering Research Council (NSERC).