A Unified View of Entropy-Regularized
Markov Decision Processes
Gergely Neu

gergely.neu@gmail.com

arXiv:1705.07798v1 [cs.LG] 22 May 2017

Universitat Pompeu Fabra, Barcelona, Spain

Vicenç Gómez

vicen.gomez@upf.edu

Universitat Pompeu Fabra, Barcelona, Spain

Anders Jonsson

anders.jonsson@upf.edu

Universitat Pompeu Fabra, Barcelona, Spain

Abstract
We propose a general framework for entropy-regularized average-reward reinforcement learning in Markov decision processes (MDPs). Our approach is based on
extending the linear-programming formulation of policy optimization in MDPs to
accommodate convex regularization functions. Our key result is showing that using
the conditional entropy of the joint state-action distributions as regularization yields
a dual optimization problem closely resembling the Bellman optimality equations.
This result enables us to formalize a number of state-of-the-art entropy-regularized
reinforcement learning algorithms as approximate variants of Mirror Descent or Dual
Averaging, and thus to argue about the convergence properties of these methods. In
particular, we show that the exact version of the TRPO algorithm of Schulman et al.
(2015) actually converges to the optimal policy, while the entropy-regularized policy
gradient methods of Mnih et al. (2016) may fail to converge to a fixed point. Finally,
we illustrate empirically the effects of using various regularization techniques on
learning performance in a simple reinforcement learning setup.

1. Introduction
Reinforcement learning is the discipline of model-based optimal sequential decisionmaking in unknown stochastic environments. In average-reward reinforcement learning,
the goal is to find a behavior policy that maximizes the long-term average reward,
taking into account the effect of each decision on the future evolution of the decisionmaking process. In known environments, this optimization problem has been studied
(at least) since the influential work of Bellman (1957) and Howard (1960): the optimal
behavior policy can be formulated as the solution of the Bellman optimality equations.
In unknown environments with partially known or misspecified models, greedily
solving these equations often results in policies that are far from optimal in the true
environment. Rooted in statistical learning theory (Vapnik, 2013), the notion of

Neu Gómez Jonsson

regularization offers a principled way of dealing with this issue, among many others.
In particular, entropy regularization has proven to be one of the most successful tools
of machine learning and related fields (Littlestone and Warmuth, 1994; Vovk, 1990;
Freund and Schapire, 1997; Kivinen and Warmuth, 2001; Arora et al., 2012).
The idea of entropy regularization has also been used extensively in the reinforcement learning literature (Sutton and Barto, 1998; Szepesvári, 2010). Entropyregularized variants of the classic Bellman equations and the entailing reinforcementlearning algorithms have been proposed to induce safe exploration (Fox et al., 2016) and
risk-sensitive policies (Howard and Matheson, 1972; Marcus et al., 1997; Ruszczyński,
2010), or to model observed behavior of imperfect decision-makers (Ziebart et al., 2010;
Ziebart, 2010; Braun et al., 2011), among others. Complementary to these approaches
rooted in dynamic programming, another line of work proposes direct policy search
methods attempting to optimize various entropy-regularized objectives (Williams and
Peng, 1991; Peters et al., 2010; Schulman et al., 2015; Mnih et al., 2016; O’Donoghue
et al., 2017), with the main goal of driving a safe online exploration procedure in an
unknown Markov decision process. Notably, the state-of-the-art methods of Mnih
et al. (2016) and Schulman et al. (2015) are both based on entropy-regularized policy
search.
In this work, we connect these two seemingly disparate lines of work by showing a
strong Lagrangian duality between the entropy-regularized Bellman equations and
a certain regularized average-reward objective. Specifically, we extend the linearprogramming formulation of the problem of optimization in MDPs to accommodate
convex regularization functions, resulting in a convex program. We show that using the
conditional entropy of the joint state-action distribution gives rise to a set of nonlinear
equations resembling the Bellman optimality equations. Observing this duality enables
us to establish a connection between regularized versions of value and policy iteration
methods (Puterman and Shin, 1978) and incremental convex optimization methods
like Mirror Descent (Nemirovski and Yudin, 1983; Beck and Teboulle, 2003) or Dual
Averaging (Xiao, 2010; McMahan, 2014; Hazan et al., 2016; Shalev-Shwartz, 2012). For
instance, the convex-optimization view we propose reveals that the TRPO algorithm
of Schulman et al. (2015) and the regularized policy-gradient method of Mnih et al.
(2016) are approximate versions of Mirror Descent and Dual Averaging, respectively,
and that both can be interpreted as regularized policy iteration methods.
Our work provides a theoretical justification for various algorithms that were first
derived heuristically. In particular, our framework reveals that the exact version of
TRPO is identical to the MDP-E algorithm of Even-Dar et al. (2009). This establishes
the fact that the policy updates of TRPO converge to the optimal policy, improving
on the theoretical results claimed by Schulman et al. (2015). We also argue that our
formulation is useful for pointing out possible inconsistencies of heuristic learning
algorithms. In particular, we show that the approximation steps employed by Mnih
et al. (2016) may break the convexity of the objective, thus possibly leading to
convergence to bad local optima or even divergence. This observation is in accordance
2

A unified view of entropy-regularized MDPs

with the very recent findings of Asadi and Littman (2016), who show that value iteration
with poorly chosen approximate updates may lead to divergence. To complement
these results, we suggest an alternative objective that can be optimized consistently,
avoiding the possibility of diverging.
A similar Lagrangian duality between the Bellman equations and entropy maximization has been previously noted by Ziebart (2010, Sec. 5.2) and Rawlik et al. (2012)
for a special class of episodic Markov decision processes where the time index within
the episode is part of the state representation. In this particular setting, the convexity
of the conditional entropy is more obvious. One of our key observations is pointing
out the convexity of the conditional entropy of distribution functions defined over
general state spaces, which enables us to develop a much broader theory of regularized
Markov decision processes. We note that our theory also readily extends to discounted
MDPs by replacing the stationary state-action distributions we consider by discounted
state-action occupancy measures. For consistency, we will discuss each particular
algorithm in their most natural average-reward version, noting that all conclusions
remain valid in the simpler discounted and episodic settings.
The rest of the paper is organized as follows. In Section 2, we provide background on
average-reward Markov decision processes, briefly discussing both linear-programming
and dynamic-programming derivations of the optimal control. In Section 3, we provide
a convex-programming formulation of regularized average-reward Markov decision
processes, and show the connection to the regularized Bellman equations. Section 4
provides a brief summary of the complementary dynamic-programming formulation
and discusses regularized equivalents of related concepts, such as expressions of the
regularized policy gradient. In Section 5, we describe several existing learning algorithms in our framework. We provide an empirical evaluation of various regularization
schemes in a simple reinforcement learning problem in Section 6.
P
P
set S, we will often use s as shorthand for s∈S , and we
Notation. Given a finite
P
use ∆(S) = {µ ∈ RS : s µ(s) = 1, µ(s) ≥ 0 (∀s)} to denote the set of all probability
distributions on S.

2. Preliminaries on Markov decision processes
We consider a finite Markov decision process (MDP) M = (X , A, P, r), where X is the
finite state space, A is the finite action space, P : X × A × X → [0, 1] is the transition
function, with P (y|x, a) denoting the probability of moving to state y from state x
when taking action a, and r : X × A → R is the reward function mapping state-action
pairs to rewards.
In each round t, the learner observes state Xt ∈ X , selects action At ∈ A, moves to
the next state Xt+1 ∼ P (·|Xt , At ), and obtains reward r(Xt , At ). The goal is to select
actions as to maximize some notion of cumulative
reward.iIn this paper we consider the
h P
T
1
average-reward criterion lim inf T →∞ E T t=1 rt (Xt , At ) . A stationary state-feedback
3

Neu Gómez Jonsson

policy (or policy for short) defines a probability distribution π(·|x) over the learner’s
actions in state x. MDP theory (see, e.g., Puterman (1994)) stipulates that under
mild conditions, the average-reward criterion can be maximized by stationary policies.
Throughout the paper, we make the following mild assumption about the MDP:
Assumption 1 The MDP M is unichain: All stationary policies
P π induce a unique
stationary distribution νπ over the state space satisfying νπ (y) = x,a P (y|x, a)π(a|x)νπ (x)
for all y ∈ X .
In particular, this assumption is satisfied if all policies induce an irreducible and
aperiodic Markov chain (Puterman, 1994). For ease of exposition in this section, we
also make the following simplifying assumption:
Assumption 2 The MDP M admits a single recurrent class: All stationary policies
π induce stationary distributions strictly supported on the same set X 0 ⊆ X .
In general, this assumption is very restrictive in that it does not allow policies to cover
different parts of the state space. We stress that our results in the later sections do
not require this assumption to hold. With the above assumptions in mind, we can
define the average reward of any policy π as
"
#
T
X
1
ρ(π) = lim E
rt (Xt , At ) ,
T →∞
T t=1
where At ∼ π(·|Xt ) in each round t and the existence of the limit is ensured by
Assumption 1. Furthermore,
the average reward of any policy π can be simply
P
written as ρ(π) = x,a νπ (x)π(a|x)r(x, a), which is a linear function of the stationary
state-action distribution µπ = νπ π. This suggests that finding the optimal policy
can be equivalently written as a linear program (LP) where the decision variable is
the stationary state-action distribution. Defining the set of all feasible stationary
distributions as
(
)
X
X
∆ = µ ∈ ∆(X × A) :
µ(y, b) =
P (y|x, a)µ(x, a) (∀y) ,
(1)
x,a

b

the problem of maximizing the average reward can be written as
µ∗ = arg max ρ(µ).

(2)

µ∈∆

Just as a policy π induces stationary distributions νπPand µπ , a stationary distribution
µ induces a state distribution νµ defined as νµ (x) = a µ(x, a) and a policy πµ defined
as πµ (a|x) = µ(x, a)/νµ (x), where the denominator is strictly positive for recurrent
states by Assumption 2. Since ∆ is a compact polytope (non-empty by Assumption 1)
4

A unified view of entropy-regularized MDPs

the maximum in (2) is well-defined and induces an optimal policy πµ∗ in recurrent
states. Due to Assumption 2, πµ∗ can be arbitrarily defined in transient states.
The linear program specified in Equation (2) is well studied in the MDP literature
(see, e.g., Puterman, 1994, Section 8.8), although most commonly as the dual of the
linear program
minρ∈R

ρ

subject to ρ + V (x) −

(3)
X

P (y|x, a)V (y) ≥ r(x, a),

∀(x, a).

(4)

y

Here, the dual variables V are commonly referred to as the value functions. By
strong LP duality and our Assumption 1, the solution to this LP equals the optimal
average reward ρ∗ and the dual variables V ∗ at the optimum are the solution to the
average-reward Bellman optimality equations
!
X
V ∗ (x) = max r(x, a) − ρ∗ +
P (y|x, a)V ∗ (x) ,
(∀x) .
(5)
a

y

Note that V ∗ is not unique as for any solution V , a constant shift V − c for any c ∈ R
is also a solution. However,
we can obtain a unique solution V ∗ by imposing the
P
additional constraint x,a µ∗ (x, a)V ∗ (x) = 0, which states that the expected value
should equal 0.

3. Regularized MDPs: A convex-optimization view
Inspired by the LP formulation of the average-reward optimization problem (2), we
now define a regularized optimization objective—a framework that will lead us to our
main results. Our results in this section only require the mild Assumption 1. Our
regularized optimization problem takes the form
(
)
X
1
max ρeη (µ) = max
µ(x, a)r(x, a) − R(µ) ,
(6)
µ∈∆
µ∈∆
η
x,a
where R(µ) : RX ×A → R is a convex regularization function and η > 0 is a learning
rate that trades off the original objective and regularization. Note that η = ∞ recovers
the unregularized objective. Unlike previous work on LP formulations for MDPs, we
find it useful to regard (6) as the primal.
We focus on two families of regularization functions: the negative Shannon entropy
of (X, A) ∼ µ,
X
RS (µ) =
µ(x, a) log µ(x, a),
(7)
x,a

5

Neu Gómez Jonsson

and the negative conditional entropy of (X, A) ∼ µ,
X
X
µ(x, a)
=
νµ (x)πµ (a|x) log πµ (a|x).
RC (µ) =
µ(x, a) log P
b µ(x, b)
x,a
x,a

(8)

In what follows, we refer to these functions as the relative entropy and the conditional
entropy. We also make use of the Bregman divergences induced by RS and RC which
take the respective forms
X
X
µ(x, a)
πµ (a|x)
DS (µkµ0 ) =
µ(x, a) log 0
and
DC (µkµ0 ) =
µ(x, a) log
.
0 (a|x)
µ
(x,
a)
π
µ
x,a
x,a
While the form of DS is standard (it is the relative entropy between two state-action
distributions), the fact that DC is the Bregman divergence of RC (or even that RC is
convex) is not immediately obvious1 . The following proposition asserts this statement,
which we prove in Appendix A.1. The only work we are aware of that establishes a
comparable result is the recent paper of Neu and Gómez (2017).
Proposition 1 The Bregman divergence corresponding to the conditional entropy
RC is DC . Furthermore, DC is nonnegative on ∆, implying that RC is convex and
DC is convex in its first argument.
We proceed to derive the dual functions and optimal solutions to (6) for our two
choices of regularization functions. Without loss of generality, we assume that the
reference policy πµ0 has full support, which implies that the corresponding stationary
distribution µ0 is strictly positive on the recurrent set X 0 . We only provide the
derivations for the Bregman divergences; the calculations are analogous for RS and
RC . Both of these solutions will be expressed with the help of dual variables V :
RX → R which are useful to think about as value functions, as in the case of the
LP formulation
(2). We also define the corresponding advantage functions A(x, a) =
P
r(x, a) + y P (y|x, a)V (y) − V (x).
3.1. Relative entropy
The choice R = DS (·kµ0 ) has been studied before by Peters et al. (2010) and Zimin
and Neu (2013); we defer the proofs to Appendix A.3. The optimal state-action
distribution for a given value of η is
∗

µ∗η (x, a) ∝ µ0 (x, a)eηAη (x,a) ,

(9)

where A∗η is the advantage function for the optimal dual variables Vη∗ . The dual
function is
X
1
g(V ) = log
µ0 (x, a)eηA(x,a) ,
(10)
η
x,a
1. In the special case of loop-free episodic environments, showing the convexity of RC is straightforward (Lafferty et al., 2001; Ziebart, 2010; Rawlik et al., 2012).

6

A unified view of entropy-regularized MDPs

that now needs to be minimized on RX with no constraints in order to obtain Vη∗ .
By strong duality, g is convex in V and takes the value ρe∗η = maxµ∈∆ ρeη (µ) at its
optimum.
3.2. Conditional entropy
The choice R = DC (·kµ0 ) leads to our main contributions. Similar to above, the
optimal policy is
∗

πη∗ (a|x) ∝ πµ0 (a|x)eηAη (x,a) .

(11)

In this case, the dual problem closely resembles the average-reward Bellman optimality
equations (5):
Proposition 2 The dual of the optimization problem (6) when R = DC (·kµ0 ) is
given by
minλ∈R

λ

!!
X
X
1
P (y|x, a)V (y)
, (∀x) .
πµ0 (a|x) exp η r(x, a) − λ +
subject to V (x) = log
η
y
a
We defer the proofs to Appendix A.4. Using strong duality, the optimum of the above
problem is ρe∗η , which implies that the optimal dual variables Vη∗ are given as a solution
to the system of equations
!!
X
X
1
P (y|x, a)Vη∗ (y)
, (∀x) .
πµ0 (a|x) exp η r(x, a) − ρe∗η +
Vη∗ (x) = log
η
y
a
(12)
By analogy with the Bellman optimality equations (5), we call this the regularized
average-reward Bellman optimality equations. Since ρe∗η is guaranteed to be finite
(because it is the maximum of a bounded function on a compact domain), the solution
to the above optimization problem is well-defined, bounded, and unique up to a
constant shift (as in the case of the LP dual variables). Again, we can make the
solution unique by imposing the constraint that the expected value should equal 0.

4. Dynamic programming in regularized MDPs
We now present a dynamic-programming view of the regularized optimization problem
(Bertsekas, 2007) for the choice R = DC (·kµ0 ). Similar derivations have been done
several times for discounted and episodic MDPs (Littman and Szepesvári, 1996;
Ruszczyński, 2010; Azar et al., 2011; Rawlik et al., 2012; Asadi and Littman, 2016;
Fox et al., 2016), but we are not aware of any work that considers the average-reward
case. That said, the generalization is straightforward, and the existence and unicity of
7

Neu Gómez Jonsson

the optimal solution to the Bellman optimality equation (12) follows from our results
in the previous section.
We first define the regularized Bellman equations for an arbitrary policy π and a
reference policy π 0 :
!
X
X
π(a|x)
1
− ρeη (π) +
P (y|x, a)Vηπ (y)
(∀x) ,
Vηπ (x) =
π(a|x) r(x, a) − log 0
η
π
(a|x)
y
a
(13)
where ρeη (π) is the regularized average reward of policy π defined as in Equation (6).
By our Assumption 1 and Proposition 4.2.4 of Bertsekas (2007), it is easy to show
that this system of equations has a unique solution satisfying the additional constraint
P
∗|π 0
π
and
x,a µπ (x, a)Vη (x) = 0. We also define the Bellman optimality operator Tη
π|π 0

the Bellman operator Tη that correspond to the Bellman equations (12) and (13),
0
respectively, as well as the greedy policy operator Gπη that corresponds to Equation (11)
(for completeness, the formal definitions appear in Appendix B).
We include two results that are useful for deriving approximate dynamic programming algorithms. We first provide a counterpart to the performance-difference lemma
(Burnetas and Katehakis, 1997, Prop. 1, Kakade and Langford, 2002, Lemma 6.1, Cao,
2007). This statement will rely on the regularized advantage function Aπη defined for
each policy π as
Aπη (x, a) = r(x, a) −

X
1 log π(a|x)
P (y|x, a)Vηπ (y) − Vηπ (x),
−
ρ
e
(π)
+
η
η log π 0 (a|x)
y

where Vηπ is the regularized value function corresponding to π with baseline π 0 .
Lemma 3 For any pair of policies π, π 0 , we have
X
µπ0 (x, a)Aπη (x, a).
ρe(π 0 ) − ρe(π) =
x,a

For completeness, we provide the simple proof in Appendix B.1.
Second, we provide an expression for the gradient of ρeη , thus providing a regularized
counterpart of the policy gradient theorem of Sutton et al. (1999). To formalize this
statement, let us consider a policy πθ parametrized by a vector θ ∈ Rd and assume
that the gradient ∇πθ (a|x) exists for all x, a and all θ. The form of the policy gradient
is given by the following lemma, which we prove in Appendix B.2:
Lemma 4 Assume that ∂πθ∂θ(a|x)
/πθ (a|x) > 0 for all θi , x, a. The gradient of ρeη exists
i
and satisfies
X
∇e
ρη (θ) =
µπθ (x, a)∇ log πθ (a|x)Aπη θ (x, a).
x,a

8

A unified view of entropy-regularized MDPs

5. Algorithms
In this section we derive several reinforcement learning algorithms based on our
results. For clarity of presentation, we assume that the MDP M is fully known, an
assumption that we later relax in the experimental evaluation. We will study a generic
sequential optimization framework where a sequence of policies πk are computed
iteratively. Inspired by the online convex optimization literature (see, e.g., ShalevShwartz, 2012; Hazan et al., 2016) and by our convex-optimization formulation, we
study two families of algorithms: Mirror Descent and Dual Averaging (also known as
Follow-the-Regularized-Leader).
5.1. Iterative policy optimization by Mirror Descent
A direct application of the Mirror Descent algorithm (Nemirovski and Yudin, 1983;
Beck and Teboulle, 2003; Martinet, 1978; Rockafellar, 1976) to our case is defined as


1
µk+1 = arg max ρ(µ) − DR (µkµk ) ,
(14)
η
µ∈∆
where DR is the Bregman divergence associated with the convex regularization function
R. We now proceed to show how various learning algorithms can be recovered from
this formulation.
5.1.1. Mirror Descent with the relative entropy
We first remark that the Relative Entropy Policy Search (REPS) algorithm of Peters
et al. (2010) can be formulated as an instance of Mirror Descent with the Bregman
divergence DS . This is easily seen by comparing the form of the update rule (14) with
the problem formulation of Peters et al. (2010, pp. 2), with the slight difference that
our regularization is additive and theirs is enforced as a constraint. It is easy to see
that this only amounts to a change in learning rate. This connection is not new: it
has been first shown by Zimin and Neu (2013)2 , and has been recently rediscovered by
Montgomery and Levine (2016). Independently of each other, Zimin and Neu (2013)
and Dick et al. (2014) both show that Mirror Descent achieves near-optimal regret
guarantees in an online learning setup where the transition function is known, but the
reward function is allowed to change arbitrarily between decision rounds. This implies
that REPS duly converges to the optimal policy in our setup.
5.1.2. Mirror Descent with the conditional entropy
We next show that the Dynamic Policy Programming (DPP) algorithm of Azar et al.
(2012) and the Trust-Region Policy Optimization (TRPO) algorithm of Schulman
et al. (2015) are both approximate variants of Mirror Descent with the Bregman
2. Although they primarily referred to Mirror Descent as the “Proximal Point Algorithm” following
(Rockafellar, 1976; Martinet, 1978).

9

Neu Gómez Jonsson

divergence DC . To see this, note that a full Mirror Descent update requires computing
the optimal value function Vη∗ for the baseline µk , e.g. by regularized value iteration or
regularized policy iteration (see Appendix B). Since a full update for Vη∗ is expensive,
DPP and TRPO provide two ways to approximate it. We remark that the algorithm
of Rawlik et al. (2012) can also be viewed as an instance of Mirror Descent for the
finite-horizon episodic setting, in which the exact update can be computed efficiently
by dynamic programming.
Dynamic Policy Programming. We first claim that each iteration of DPP is
a single regularized value iteration step: Starting from the previous value function
Vk , it extracts the greedy policy πk+1 = Gπη k [Vk ] and applies the Bellman optimality
∗|π
∗|π
operator Tη k to obtain Vk+1 = Tη k [Vk ]. This follows from comparing the form of
DPP presented in Appendix A of Azar et al. (2012): their update rules (19) and (20)
precisely match the discounted analogue of our expressions (26) in Appendix B with
π 0 = πk . The convergence guarantees proved by Azar et al. (2012) demonstrate the
soundness of this approximate update.
Trust-Region Policy Optimization. Second, we claim that each iteration of
TRPO is a single policy iteration step: TRPO first fully evaluates the policy πk to
compute its unregularized value function Vk = V∞πk and then extracts the regularized
greedy policy πk+1 = Gπη k [Vk ] with πk as a baseline. This can be seen by inspecting
the TRPO update3 that takes the form
(

)
X
X
π(a|x)
1
πk
πk+1 = arg max
νπk (x)
π(a|x) A∞
(x, a) − log
.
η
πk (a|x)
π
x
a
This objective approximates Mirror Descent by ignoring the effect of changing the
policy on the state distribution. Surprisingly, using our formalism, this update can be
expressed in closed form as
πk

πk+1 (a|x) ∝ πk (a|x)eηA∞ (x,a) .
We present the detailed derivations in Appendix B.3. A particularly interesting
consequence of this result is that TRPO is completely equivalent to the MDP-E
algorithm of Even-Dar et al. (2009) (see also (Neu et al., 2010, 2014)), which is known
to minimize regret in an online setting, thus implying that TRPO also converges to
the optimal policy in the stationary setting. This guarantee is much stronger than
the ones provided by Schulman et al. (2015), who only claim that TRPO produces a
monotonically improving sequence of policies (which may still converge to a suboptimal
policy).
3. As in the case of REPS, we discuss here the additive-regularization version of the algorithm. The
entropy-constrained update actually implemented by Schulman et al. (2015) only differs in the
learning rate.

10

A unified view of entropy-regularized MDPs

5.2. Iterative policy optimization by Dual Averaging
We next study algorithms arising from the Dual Averaging scheme (Xiao, 2010;
McMahan, 2014), commonly known as Follow-the-Regularized-Leader in online learning (Shalev-Shwartz, 2012; Hazan et al., 2016). This algorithm is defined by the
iteration


1
(15)
µk+1 = arg max ρ(µ) − R(µ) ,
ηk
µ∈∆
where ηk is usually an increasing sequence to ensure convergence in the limit. We
are unaware of any pure instance of dual averaging using relative entropy, and only
discuss conditional entropy below.
5.2.1. Dual Averaging with the conditional entropy
Just as for Mirror Descent, a full update (15) requires computing the optimal value
function Vη∗ . Various approximations of this update have been long studied in the RL
literature—see, e.g., (Littman and Szepesvári, 1996) (with additional discussion by
(Asadi and Littman, 2016)), (Perkins and Precup, 2002; Ruszczyński, 2010; Petrik
and Subramanian, 2012; Fox et al., 2016). In this section, we focus on the stateof-the-art algorithms of Mnih et al. (2016) and O’Donoghue et al. (2017) that were
originally derived from an optimization formulation resembling our Equation (6). Our
main insight is that this algorithm can be adjusted to have a dynamic-programming
interpretation and a convergence guarantee.
Entropy-regularized policy gradients. The A3C algorithm of Mnih et al. (2016)
aims to maximize
X
1 X
ρ(π) −
νπk (x)
π(a|x) log π(a|x)
ηk x
a
by taking policy gradient steps. Interestingly, our formalism implies a connection
between TRPO and A3C. Due to P
Lemma 4,Pthe gradient of ρ(πθ ) with respect
to θ coincides with the gradient of x νπk (x) a πθ (a|x)Aπ∞k (x, a), so A3C actually
attempts to optimize the objective


X
X
1
πk
log πθ (a|x) .
(16)
νπk (x)
πθ (a|x) A∞ (x, a) −
η
k
x
a
This objective can be seen as the dual-averaging counterpart of the TRPO objective.
As in the case of TRPO, the maximizer of this objective can be computed in closed
form as
πk
πk+1 (a|x) ∝ eηk A∞ .
Unlike for TRPO, we are not aware of any convergence results for A3C, and we believe
the algorithm does not converge. Indeed, the objective (16) is non-convex in either
11

Neu Gómez Jonsson

of the natural parameters µ or π, which can cause premature convergence to a bad
local optimum. An even more serious concern is that the objective function changes
between iterations, so gradient descent may fail to converge to any stationary point.
This problem is avoided by TRPO since the sum of the TRPO objectives is a sensible
optimization objective (Even-Dar et al., 2009, Theorem 4.1). However, there is no
such clear interpretation for the objective (16).
O’Donoghue et al. (2017, Section 3.1) study the stationary points of the objective (16) and, similarly to us, show a connection between a certain type of value
function and a policy achieving the stationary point. However, they do not show that
this stationary point is unique nor that gradient descent converges to a stationary
point4 . As we argue above, this may very well not be the case. These observations
are consistent with those of Asadi and Littman (2016), who show that softmax policy
updates may lead to inconsistent behavior when used in tandem with unregularized
advantage functions.
To overcome these issues, we advocate for directly optimizing the objective (15)
instead of (16) via gradient descent. Due to the fact that (15) is convex in µ and to
standard results regarding dual averaging (McMahan, 2014), this scheme is guaranteed
to converge to the optimal policy. Estimating the gradients can be done analogously
as for the unregularized objective, by our Lemma 4.

6. Experiments
In this section we analyze empirically several of the algorithms described in the
previous section, with the objective of illustrating the interplay of regularization and
model-estimation error in a simple reinforcement learning setting. We consider an
iterative setup where in each episode k = 1, 2, . . . , N , we execute a policy πk , observe
the sample transitions and update the estimated model via maximum likelihood.
We focus on the regularization aspect, with no other approximation error than that
introduced by model estimation. It is important to emphasize that the comparison
may not extend to other variants of the algorithms or in the presence of other sources
of approximation.
We consider a simple MDP, defined on a grid (Fig. 1, left), where an agent has
four possible actions (up, down, left and right) that succeed with probability 0.9 but
fail with probability 0.1. In case of failure, the agent does not move or goes to any
random adjacent location. Negative (or positive) rewards are given after hitting a
wall (or reaching one of the white diamond locations, respectively). In both cases, the
agent is sent back to one of the starting locations (marked with ’X’ in the figure).
The reward of the diamonds is proportional to the distance from the starting
locations. Therefore, the challenge of this experiment is to discover the path towards
the top-right reward while learning the dynamics incrementally, and then exploit it.
4. Strictly speaking, O’Donoghue et al. (2017) do not even show that a stationary point (16) exists.

12

A unified view of entropy-regularized MDPs

8
0.05

8

0.04
0.03
0.02

6

6
DA-RV
DA
TRPO
DPP
RegVI
Opt

4

0.01

2
0
-0.01

0
10 -4 10 -3 10 -2 10 -1 10 0 10 1
2

avg reward

10

avg reward

0.06

4
DPP
ModRegPI-2
ModRegPI-20
TRPO

2

0
10 0

10 1

10 2

iteration k

Figure 1: Left: the MDP used for evaluation. Reward is −0.1 at the walls and
5, 50, 200 at the diamonds. The optimal policy is indicated by red arrows.
The cell colors correspond to the stationary state distribution for open
locations. Middle: Average reward as a function of the learning rate η for
all algorithms (see text for details). Number of iterations N and samples
per iteration S are N = S = 500. Results are taken over 20 random runs
per value of η. Right: Performance of DPP, TRPO and two version of
modified regularized Policy Iteration for a fixed η ≈ 0.1.

Note that the optimal agent ignores the intermediate reward at the center and even
prefers to hit a wall in locations too far away from the largest reward (bottom-left).
We fix the number of iterations N and samples per iteration S and analyze the
average reward of the final policy as a function of η. We compare the following
algorithms: regularized Value Iteration with a fixed reference uniform policy and fixed
η (RegVI); several variants of approximate Mirror Descent, including DPP and TRPO
(Section 5.1); and two Dual Averaging methods (DA and DA-RV). DA corresponds to
optimizing the objective (16), which is not guaranteed to lead to an optimal policy,
and DA-RV corresponds to the iteration (15), which has convergence guarantees
(Section 5.2). For both variants, we use a linear annealing schedule ηk = η · k.
Fig. 1 (middle) shows results as a function of η. The maximum reward is depicted
in blue at the top. For very small η (strong regularization), all algorithms perform
poorly and do not even reach the intermediate reward. In contrast, for very large η,
they converge prematurely to the greedy policy that exploits the intermediate reward.
Typically, for an intermediate value of η, the algorithms occasionally discover the
optimal path and exploit it. Note that this is not the case for RegVI, which never
obtains the optimal policy. This shows that using both a fixed value of η and a fixed
reference policy is a bad choice. In this MDP, we observe that the performance of
both Dual Averaging methods (DA and DA-RV) is very similar, and in general slightly
better than the approximate Mirror Descent variants.
13

Neu Gómez Jonsson

We also show an interesting relationship between the Mirror Descent approximations. Our analysis in Section 5.1.2 suggests an entire array of algorithms lying
between DPP and TRPO, just as Modified Policy Iteration lies between Value Iteration
and Policy Iteration (Puterman and Shin, 1978; Scherrer et al., 2012). Fig. 1 (right)
illustrates this idea, showing the convergence of DPP and TRPO for a fixed value of
η. TRPO tends to converge faster than DPP to a locally optimal policy, since DPP
uses a single value update per iteration. Using more value updates leads to a modified
regularized Policy Iteration algorithm (we call it ModRegPI-2 and ModRegPI-20, for
2 and 20 updates, respectively) that interpolates between DPP and TRPO.

7. Conclusion
We have presented a unifying view of entropy-regularized MDPs from a convexoptimization perspective. We believe that such unifying theories can be very useful
in moving a field forward: We recall that in the field of online learning theory, the
convex-optimization view has enabled a unified treatment of many existing algorithms
and acts today as the primary framework for deriving new algorithms (see the progress
from Cesa-Bianchi and Lugosi (2006) through Shalev-Shwartz (2012) to Hazan et al.
(2016)). In this paper, we argued that the convex-optimization view may also be
very useful in analyzing algorithms for reinforcement learning: In particular, we
demonstrated how this framework can be used to provide theoretical justification for
state-of-the-art reinforcement learning algorithms, and how it can highlight potential
problems with them. We expect that this newly-found connection will also open the
door for constructing more advanced reinforcement learning algorithms by borrowing
further ideas from the convex optimization literature, such as Composite Objective
Mirror Descent Duchi et al. (2010) and Regularized Dual Averaging (Xiao, 2010).
Finally, we point out that our work does not provide a statistical justification
for using entropy regularization in reinforcement learning. In the case of online
learning in known Markov decision processes with changing reward functions, entropyregularization has been known to yield near-optimal learning algorithms (Even-Dar
et al., 2009; Neu et al., 2010, 2014; Zimin and Neu, 2013; Dick et al., 2014). It remains
to be seen if this technique also provably helps in driving the exploration process in
unknown Markov decision processes.

References
S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: A
meta-algorithm and applications. Theory of Computing, 8:121–164, 2012.
Kavosh Asadi and Michael L. Littman. A new softmax operator for reinforcement
learning. CoRR, abs/1612.05628, 2016.

14

A unified view of entropy-regularized MDPs

Mohammad Gheshlaghi Azar, Vicenç Gómez, and Hilbert J Kappen. Dynamic policy
programming with function approximation. In International Conference on Artificial
Intelligence and Statistics, pages 119–127, 2011.
Mohammad Gheshlaghi Azar, Vicenç Gómez, and Hilbert J Kappen. Dynamic policy
programming. Journal of Machine Learning Research, 13(Nov):3207–3245, 2012.
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods
for convex optimization. Operations Research Letters, 31(3):167–175, 2003.
R. Bellman. Dynamic Programming. Princeton University Press, Princeton, New
Jersey, 1957.
D. P. Bertsekas. Dynamic Programming and Optimal Control, volume 2. Athena
Scientific, Belmont, MA, 3 edition, 2007.
Daniel A Braun, Pedro A Ortega, Evangelos Theodorou, and Stefan Schaal. Path
integral control and bounded rationality. In Adaptive Dynamic Programming And
Reinforcement Learning (ADPRL), 2011 IEEE Symposium on, pages 202–209. IEEE,
2011.
A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for Markov Decision
Processes. 22(1):222–255, 1997.
Xi-Ren Cao. Stochastic Learning and Optimization: A Sensitivity-Based Approach.
Springer, New York, 2007.
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge
University Press, New York, NY, USA, 2006.
T. Dick, A. György, and Cs. Szepesvári. Online learning in markov decision processes
with changing cost sequences. In ICML 2014, 2014.
John C Duchi, Shai Shalev-Shwartz, Yoram Singer, and Ambuj Tewari. Composite
objective mirror descent. In COLT, pages 14–26, 2010.
E. Even-Dar, S. M. Kakade, and Y. Mansour. Online Markov decision processes.
Mathematics of Operations Research, 34(3):726–736, 2009.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning
via soft updates. In Proceedings of the Thirty-Second Conference on Uncertainty in
Artificial Intelligence, 2016.
Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning
and an application to boosting. Journal of Computer and System Sciences, 55:
119–139, 1997.
15

Neu Gómez Jonsson

Elad Hazan et al. Introduction to online convex optimization. Foundations and
Trends R in Optimization, 2(3-4):157–325, 2016.
R. A. Howard. Dynamic Programming and Markov Processes. The MIT Press,
Cambridge, MA, 1960.
Ronald A Howard and James E Matheson. Risk-sensitive markov decision processes.
Management science, 18(7):356–369, 1972.
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on
Machine Learning (ICML 2002), pages 267–274, 2002.
J. Kivinen and M. Warmuth. Relative loss bounds for multidimensional regression
problems. Machine Learning, 45:301–329, 2001.
John Lafferty, Andrew McCallum, and Fernando Pereira. Conditional random fields:
Probabilistic models for segmenting and labeling sequence data. In ICML 2001, pages
282–289, 2001. URL citeseer.ist.psu.edu/lafferty01conditional.html.
N. Littlestone and M. Warmuth. The weighted majority algorithm. Information and
Computation, 108:212–261, 1994.
M.L. Littman and Cs. Szepesvári. A Generalized Reinforcement Learning Model:
Convergence and applications. In Int. Conf. on Machine Learning, pages 310–318,
1996.
Steven I Marcus, Emmanual Fernández-Gaucherand, Daniel Hernández-Hernandez,
Stefano Coraluppi, and Pedram Fard. Risk sensitive markov decision processes. In
Systems and control in the twenty-first century, pages 263–279. Springer, 1997.
B. Martinet. Perturbation des méthodes d’optimisation. applications. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse
Numérique, 12(2):153–171, 1978. URL http://eudml.org/doc/193317.
H Brendan McMahan. A survey of algorithms and analysis for adaptive online learning.
arXiv preprint arXiv:1403.3465, 2014.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy
Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods
for deep reinforcement learning. In International Conference on Machine Learning,
pages 1928–1937, 2016.
William H Montgomery and Sergey Levine. Guided policy search via approximate
mirror descent. In NIPS-29, pages 4008–4016, 2016.

16

A unified view of entropy-regularized MDPs

A. Nemirovski and D. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley Interscience, 1983.
G. Neu, A. György, and Cs. Szepesvári. The online loop-free stochastic shortest-path
problem. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT),
pages 231–243, 2010.
Gergely Neu and Vicenç Gómez. Fast rates for online learning in Linearly Solvable
Markov Decision Processes. 2017.
Gergely Neu, András György, Csaba Szepesvári, and András Antos. Online Markov
decision processes under bandit feedback. IEEE Transactions on Automatic Control,
59:676–691, 2014.
Brendan O’Donoghue, Remi Munos, Koray Kavukcuoglu, and Volodymyr Mnih. PGQ:
Combining policy gradient and Q-learning. In 5th International Conference on
Learning Representations, 2017.
Theodore J. Perkins and Doina Precup. A convergent form of approximate policy
iteration. In Advances in Neural Information Processing Systems, pages 1595–1602,
2002.
Jan Peters, Katharina Mülling, and Yasemin Altun. Relative entropy policy search.
In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence,
pages 1607–1612, 2010.
Marek Petrik and Dharmashankar Subramanian. An approximate solution method
for large risk-averse markov decision processes. In Proceedings of the Twenty-Eighth
Conference on Uncertainty in Artificial Intelligence, pages 805–814, 2012.
Martin L. Puterman. Markov Decision Processes. Wiley, 1994. ISBN 9780471727828. URL http://books.google.com/books/about/Markov_decision_
processes.html?id=Y-gmAQAAIAAJ.
Martin L. Puterman and Moon Chirl Shin. Modified policy iteration algorithms for
discounted Markov decision processes. Management Science, 24:1127–1137, 1978.
Konrad Rawlik, Marc Toussaint, and Sethu Vijayakumar. On stochastic optimal
control and reinforcement learning by approximate inference. In Proceedings of
Robotics: Science and Systems VIII, 2012.
R. Tyrrell Rockafellar. Monotone Operators and the Proximal Point Algorithm. SIAM
Journal on Control and Optimization, 14(5):877–898, 1976.
Andrzej Ruszczyński. Risk-averse dynamic programming for Markov decision processes.
Mathematical programming, 125(2):235–261, 2010.
17

Neu Gómez Jonsson

B. Scherrer, V. Gabillon, M. Ghavamzadeh, and M. Geist. Approximate modified
policy iteration. In ICML 2012, pages 1207–1214, 2012.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.
Trust region policy optimization. In Proceedings of the 32nd International Conference
on Machine Learning (ICML-15), pages 1889–1897, 2015.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations
and Trends in Machine Learning, 4(2):107–194, 2012.
R. S. Sutton, D. A. McAllester, S. P. Singh, and Y. Mansour. Policy gradient
methods for reinforcement learning with function approximation. In NIPS-12, pages
1057–1063, 1999.
R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. MIT Press,
1998.
Cs. Szepesvári. Algorithms for Reinforcement Learning. Synthesis Lectures on Artificial
Intelligence and Machine Learning. Morgan & Claypool Publishers, 2010.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business
media, 2013.
V. Vovk. Aggregating strategies. In Proceedings of the third annual workshop on
Computational learning theory (COLT), pages 371–386, 1990.
Ronald J Williams and Jing Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):241–268, 1991.
Lin Xiao. Dual averaging methods for regularized stochastic learning and online
optimization. Journal of Machine Learning Research, 11(Oct):2543–2596, 2010.
Brian D Ziebart. Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy. PhD thesis, Carnegie Mellon University, 2010.
Brian D Ziebart, J Andrew Bagnell, and Anind K Dey. Modeling interaction via
the principle of maximum causal entropy. In International Conference on Machine
Learning (ICML), pages 1247–1254, 2010.
A. Zimin and G. Neu. Online learning in episodic Markovian decision processes by
relative entropy policy search. In NIPS-26, pages 1583–1591, 2013.

18

A unified view of entropy-regularized MDPs

Appendix A. Complementary Technical Results
A.1. Convexity of the negative conditional entropy
Let us consider
the joint state-action distribution µ on the finite set X × A. We denote
P
νµ (x) = a µ(x, a) and πµ (a|x) = µ(x, a)/νµ (x) for all x, a. We study the negative
conditional entropy of (X, A) ∼ µ as a function of µ:
RC (µ) =

X
x,a

X
µ(x, a)
µ(x, a)
=
µ(x, a) log
.
µ(x, a) log P
ν
(x)
µ
b µ(x, b)
x,a

We will study the Bregman divergence DRC corresponding to RC :
DRC (µkµ0 ) = RC (µ) − RC (µ0 ) − ∇RC (µ0 )> (µ − µ0 ),
P
where the inner product between two vectors v, w ∈ RX ×A is w> v = x,a v(x, a)w(x, a).
Our aim is to show that DRC is nonnegative, which will imply the convexity of RC .
We begin by computing the partial derivative of RC (µ) with respect to µ(x, a):
X µ(x, b)
µ(x, a)
µ(x, a)
∂RC (µ)
= log
+1−
= log
,
∂µ(x, a)
νµ (x)
ν
ν
µ (x)
µ (x)
b
where we used the fact that ∂νµ (x)/∂µ(x, a) = 1 for all a. With this expression, we
have
RC (µ0 ) + ∇RC (µ0 )> (µ − µ0 ) =

X

=

X

µ0 (x, a) log

µ0 (x, a)
µ0 (x, a) X
+
(µ(x, a) − µ0 (x, a)) log
νµ0 (x)
νµ0 (x)
x,a

µ(x, a) log

µ0 (x, a)
.
νµ0 (x)

x,a

x,a

Thus, the Bregman divergence takes the form


X
µ0 (x, a)
µ(x, a)
0
DRC (µkµ ) =
µ(x, a) log
− log
νµ (x)
νµ0 (x)
x,a
=

X
x,a

µ(x, a) log

X
X
πµ (a|x)
πµ (a|x)
=
ν(x)
πµ (a|x) log
.
πµ0 (a|x)
πµ0 (a|x)
x
a

This proves that the Bregman divergence corresponding to RC coincides with DC , as
claimed. To conclude the proof, note that DC is the average relative entropy between
the distributions πµ and πµ0 —that is, a sum a positive terms. Indeed, this shows that
DC is nonnegative on the set of state-action distributions ∆(X × A), proving that
RC (µ) is convex.

19

Neu Gómez Jonsson

A.2. Derivation of optimal policies
Here we prove the results stated in Equations (9)-(11) and Proposition 2, which give the
expressions for the dual optimization problems and the optimal solutions corresponding
to the primal optimization problem (6), for the two choices of regularization function
DS (·kµ0 ) and DC (·kµ0 ). We start with generic derivations that will be helpful for
analyzing both cases and then turn to studying the individual regularizers.
Recall that the primal optimization objective in (6) is given by
(
)
X
1
max ρeη (µ) = max
µ(x, a)r(x, a) − R(µ) ,
µ∈∆
µ∈∆
η
x,a
where ∆, the feasible set of stationary distributions, is defined by the following
constraints:
X
X
µ(y, b) =
µ(x, a)P (y|x, a), ∀y ∈ X ,
(17)
x,a

b

X

µ(x, a) = 1,

(18)

µ(x, a) ≥ 0, ∀(x, a) ∈ X × A.

(19)

x,a

We begin by noting that for all state-action pairs where µ0 (x, a) = 0, the optimal
solution µ∗η (x, a) will also be zero, thanks to the form of our regularized objective.
Thus, without loss of generality, we will assume that all states are recurrent under µ0 :
µ0 (x, a) > 0 holds for all state-action pairs.
For any choice of regularizer R, the Lagrangian of the primal (6) is given by
X
X
X
1
µ(y, b)
V (y)
µ(x, a)P (y|x, a) −
L(µ; V,λ, ϕ) =
µ(x, a)r(x, a) − R(µ) +
η
x,a
y
x,a
b
!
X
X
+λ 1−
µ(x, a) +
ϕ(x, a)µ(x, a)
X

x,a

x,a

!
=

X

=

X

x,a

x,a

µ(x, a) r(x, a) +

X

P (y|x, a)V (y) − V (x) − λ + ϕ(x, a)

y

1
− R(µ) + λ
η

1
µ(x, a) (A(x, a) − λ + ϕ(x, a)) − R(µ) + λ,
η

where V , λ and ϕ are the Lagrange multipliers5 , and A is the advantage function for
V . Setting the gradient of the Lagrangian with respect to µ to 0 yields the system of
5. Technically, these are KKT multipliers as we also have inequality constraints. However, these will
be eliminated by means of complementary slackness in the next sections.

20

!

A unified view of entropy-regularized MDPs

equations
∂L
1 ∂R(µ)
= (A(x, a) − λ + ϕ(x, a)) −
,
∂µ(x, a)
η ∂µ(x, a)
∂R(µ)
= η (A(x, a) − λ + ϕ(x, a)) ,
(20)
⇔
∂µ(x, a)
for all x, a. By the first-order stationary condition, the unique optimal solution µ∗η
satisfies this system of equations. To obtain the final solution we have to compute
the optimal values Vη∗ , λ∗η and ϕ∗η of the Lagrange multipliers by optimizing the dual
optimization objective g(V, λ, ϕ) = L(µ∗η ; V, λ, ϕ), and insert into the expression for
µ∗η . V and λ are unconstrained in the dual, while ϕ satisfies ϕ(x, a) ≥ 0 for each
(x, a) ∈ X × A. We give the derivations for each regularizer below.
0=

A.3. The relative entropy
P
Here we prove the results for R(µ) = DS (µkµ0 ) = x,a µ(x, a) log µµ(x,a)
0 (x,a) . The gradient
of R is
∂R(µ)
µ(x, a)
= log 0
+ 1.
∂µ(x, a)
µ (x, a)
The optimal state-action distribution µ∗η is now directly given by Equation (20):
µ∗η (x, a) = µ0 (x, a) exp (η (A(x, a) − λ + ϕ(x, a)) − 1) .

(21)

For µ∗η to belong to ∆, it has to satisfy Constraints (18) and (19). Because of
the exponent in (21), µ∗η (x, a) ≥ 0 trivially holds for any choice of ϕ(x, a), and
complementary slackness implies ϕ∗η (x, a) = 0 for each (x, a). Eliminating ϕ and
inserting µ∗η into Constraint (18) gives us
X
1=
µ0 (x, a) exp (ηA(x, a)) e−ηλ−1 ,
x,a

1
⇔ λ=
η

!
log

X

µ0 (x, a) exp (ηA(x, a)) − 1 .

(22)

x,a

Since the value of λ is uniquely determined by (22), we can optimize the dual over V
only. The dual function is given by


X
µ∗η (x, a)
1
1
∗
∗
g(V ) = L(µη ; V, λ) =
µη (x, a) A(x, a) − λ − log 0
+λ= +λ
η
µ (x, a)
η
x,a
X
1
= log
µ0 (x, a) exp (ηA(x, a)) .
η
x,a
This is precisely the dual given in Equation (10). Note that this dual function has
no associated constraints. The expression for the optimal state-action distribution in
Equation (9) is obtained by inserting the advantage function A∗η corresponding to the
optimal value function Vη∗ into (21).
21

Neu Gómez Jonsson

A.4. The conditional entropy
We next prove the results for R(µ) = DC (µkµ0 ) =
gradient of R is

P

x,a

µ(x, a) log ππµ0(a|x)
. The
(a|x)
µ

∂R(µ)
πµ (a|x) X µ(x, b) ∂πµ (b|x)
= log
+
·
.
∂µ(x, a)
πµ0 (a|x)
πµ (b|x) ∂µ(x, a)
b
Since the policy is defined as πµ (a|x) =

µ(x,a)
,
νµ (x)

its gradient with respect to µ is


I{a=b} µ(x, b)
∂πµ (b|x)
1
=
−
I
−
π
(b|x)
, ∀x ∈ X , a, b ∈ A.
=
µ
{a=b}
∂µ(x, a)
νµ (x)
νµ (x)2
νµ (x)
Inserting into the expression for the gradient of R yields

πµ (a|x) X πµ (b|x)
∂R(µ)
= log
+
I{a=b} − πµ (b|x)
∂µ(x, a)
πµ0 (a|x)
πµ (b|x)
b
X
πµ (a|x)
πµ (a|x)
πµ (b|x) = log
= log
+1−
.
πµ0 (a|x)
πµ0 (a|x)
b
The optimal policy πµ∗ is now directly given by Equation (20):
πη∗ (a|x) = πµ0 (a|x) exp (η (A(x, a) − λ + ϕ(x, a))) .

(23)

For µ∗η to belong to ∆, it has to satisfy Constraint (19). Because of the exponent
in (23) and the fact that µ∗η (x, a) ∝ πη∗ (a|x), µ∗η (x, a) ≥ 0 trivially holds for any choice
of ϕ(x, a), implying that ϕ∗η (x, a) = 0 for each (x, a) by complementary slackness.
Since πη∗ (a|x) =

µ∗η (x,a)
,
νη∗ (x)

X

we also obtain the following set of constraints:

πη∗ (a|x) =

a

X µ∗η (x, a)
a

νη∗ (x)

=

νη∗ (x)
= 1, ∀x ∈ X .
νη∗ (x)

Inserting the expression for πη∗ yields
1=

X

πµ0 (a|x) exp (ηA(x, a)) e−ηλ , ∀x ∈ X .

a

If we expand the expression for A(x, a) and rearrange the terms we obtain
!!
X
X
1
P (y|x, a)V (y)
πµ0 (a|x) exp η r(x, a) − λ +
, ∀x ∈ X .
V (x) = log
η
a
y
(24)
22

A unified view of entropy-regularized MDPs

The dual function is obtained by inserting the expression for µ∗ into the Lagrangian:


X
πη∗ (a|x)
1
∗
∗
g(V, λ) = L(µη ; V, λ) =
µη (a|x) A(x, a) − λ − log
+ λ = λ. (25)
0 (a|x)
η
π
µ
x,a
Together, Equations (24) and (25) define the dual optimization problem in Proposition 2. The expression for the optimal policy in Equation (11) is obtained by inserting
the optimal advantage function A∗η into (23).
We remark that to recover the optimal stationary state-action distribution µ∗η , we
would have to insert the expression for the optimal policy πη∗ into Constraints (17)
and (18), and solve for the stationary state distribution νη∗ . However, this is not
necessary since µ∗η and νη∗ are not required to solve the dual function or to compute
the optimal policy.

Appendix B. The regularized Bellman operators
In this section, we define the regularized Bellman operator Tπ|π0 corresponding to the
policy π and regularized with respect to baseline π 0 as
!
X
π(a|x) X
0
0
π|π 0
P (x |x, a)V (x )
(∀x) .
+
Tη [V ](x) =
π(a|x) r(x, a) − log 0
π (a|x)
a
x0
Similarly, we define the regularized Bellman optimality operator T∗|π0 with respect to
baseline π 0 as
!!
X
X
1
0
Tη∗|π [V ](x) = log
π 0 (a|x) exp η r(x, a) +
P (y|x, a)V (y)
(∀x) ,
η
a
y
and the regularized greedy policy with respect to the baseline π 0 as
!!
0

Gπη [V ](a|x) ∝ π 0 (a|x) exp η r(x, a) +

X

P (y|x, a)V (y) − V (x)

.

y

With these notations, we can define the regularized relative value iteration algorithm
with respect to π 0 by the iteration
0

πk+1 = Gπη [Vk ]

0

Vk+1 (x) = Tη∗|π [Vk ](x) − δk+1

(26)
∗|π 0

for some δk+1 lying between the minimal and maximal values of Tη [Vk ]. A common
∗|π 0
technique is to fix a reference state x0 and choose δk+1 = Tη [Vk ](x0 ).
Similarly, we can define the regularized policy iteration algorithm by the iteration

∞
π0
πk+1 |π 0
πk+1 = Gη [Vk ]
Vk+1 (x) = Tη
[Vk ](x) − δk+1 ,
(27)
23

Neu Gómez Jonsson

with δk+1 defined analogously.
For establishing the convergence of the above procedures, it is crucial to ensure
∗|π 0
that the operator Tη is a non-expansion: For any value functions V1 and V2 , we
need to ensure
0
0
Tη∗|π [V1 ] − Tη∗|π [V2 ] ≤ kV1 − V2 k
for some norm. We state the following result claiming that the above requirement
indeed holds and present the simple proof below. We note that analogous results
have been proven several times in the literature, see, e.g., (Fox et al., 2016; Asadi and
Littman, 2016).
∗|π 0

is a non-expansion for the supremum norm kf k∞ = maxx |f (x)|.
P
Proof For simplicity, let us introduce the notation Q1 (x, a) = r(x, a)+ y P (y|x, a)V1 (y),
with Q2 defined analogously, and ∆ = Q1 − Q2 . We have
Proposition 5 Tη

∗|π 0

Tη

∗|π 0

[V1 ](x) − Tη

!

1
[V2 ](x) =
η

log

X

π 0 (a|x) exp (ηQ1 (x, y)) − log

X

π 0 (a|x) exp (ηQ2 (x, y))

a
a
P


0
π
(a|x)
exp
(ηQ
(x,
y))
1
1
=
log Pa 0
π
(a|x)
exp
(ηQ
η
2 (x, y))
Pa 0


exp (η (Q2 (x, y) + ∆(x, y)))
1
a π (a|x)
P 0
=
log
η
a π (a|x) exp (ηQ2 (x, y))
X
1
p(x, a) exp (η∆(x, a))
(with an appropriately defined p)
= log
η
a

1
log max exp (η∆(x, a))
a
η
X
= max ∆(x, a) = max
P (y|x, a) (V1 (y) − V2 (y))
≤

a

a

y

≤ max |V1 (y) − V2 (y)| .
y

With an analogous technique, we can also show the complementary inequality
0

0

Tη∗|π [V2 ](x) − Tη∗|π [V1 ](x) ≤ max |V2 (y) − V1 (y)| ,
y

which concludes the proof.
∗|π 0

Together with the easily-seen fact that Tη is continuous, this result immediately
∗|π 0
implies that Tη has a fixed point by Brouwer’s fixed-point theorem. Furthermore,
this insight allows us to treat the value iteration method (26) as an instance of
generalized value iteration, as defined by Littman and Szepesvári (1996).
∗|π 0
We now argue that regularized value iteration converges to the fixed point of Tη .
If the initial value function V0 is bounded, then so is Vk for each k since the operator
24

A unified view of entropy-regularized MDPs

∗|π 0

Tη is a non-expansion. Similar to Section 3, we assume without loss of generality
that the initial reference policy π0 has full support, i.e. π0 (a|x) > 0 for each recurrent
0
state x and each action a. Inspecting the greedy policy operator Gπη , it is easy to
show by induction that πk has full support for each k. In particular, πk+1 (a|x) only
equals 0 if either πk (a|x) equals 0 or if the exponent Ak (x, a) equals −∞, which is
only possible if Vk is unbounded.
Now, since πk has full support for each k, any trajectory always has a small
probability of reaching a given recurrent state. We can now use a similar argument as
Bertsekas (2007, Prop. 4.3.2) to show that regularized value iteration converges to the
∗|π 0
fixed point for Tη .
B.1. The proof of Lemma 3
Let µ and µ0 be the respective stationary distributions of π and π 0 . The statement
follows easily from using the definition of Aπη :
X
x,a

µ

0

(x, a)Aπη (x, a)

X
1 log π(a|x)
=
µ (x, a) r(x, a) −
−
ρ
e
(µ)
+
P (y|x, a)Vηπ (y) − Vηπ (x)
0
η log π (a|x)
x,a
y
!
X
X
µ0 (x, a)
P (y|x, a)Vηπ (y) − Vηπ (x)
= ρe(µ0 ) − ρe(µ) +
X

0

x,a

y

0

= ρe(µ ) − ρe(µ),
where the last step follows from the stationarity of µ0 .

B.2. Regularized policy gradient
Here we prove Lemma 4 which gives the gradient of the regularized average reward
ρeη (θ) when the policy πθ is parameterized on θ. Following Sutton et al. (1999), we
first compute the gradient of Vηπθ :
!
X
1
πθ (a|x)
r(x, a) − log 0
− ρeη (θ) +
P (y|x, a)Vηπθ (y)
η
π (a|x)
y
!
X
∂Vηπθ (y)
1
∂πθ (a|x) ∂ ρeη X
+
πθ (a|x) −
−
+
P (y|x, a)
.
ηπθ (a|x) ∂θi
∂θi
∂θi
a
y

∂Vηπθ (x) X ∂πθ (a|x)
=
∂θi
∂θi
a

25

!

Neu Gómez Jonsson

Rearranging the terms gives us
X
1
1
πθ (a|x)
r(x, a) − log 0
− ρeη (θ) +
P (y|x, a)Vηπθ (y) −
η
π (a|x)
η
y

∂ ρeη X ∂πθ (a|x)
=
∂θi
∂θi
a
+

X

πθ (a|x)

X

a

=

P (y|x, a)

y

X ∂πθ (a|x)
∂θi

a

Aπη θ (x, a)

+

!

∂Vηπθ (y) ∂Vηπθ (x)
−
∂θi
∂θi
X

πθ (a|x)

a

X
y

∂Vηπθ (y) ∂Vηπθ (x)
P (y|x, a)
−
.
∂θi
∂θi

P
The last equality follows from the fact that since a ∂πθ (a|x)/∂θi = 0 for each x,
we can add any state-dependent constant to the multiplier of ∂πθ (a|x)/∂θi ; adding
the term η1 − Vηπθ (x) results in the given expression. Summing both sides over the
stationary state distribution νπθ yields
∂ ρeη X
∂πθ (a|x) πθ
∂ ρeη X
=
νπθ (x)
=
νπθ (x)
Aη (x, a)
∂θi
∂θ
∂θ
i
i
x
x,a
+

XX
y

=

X

=

X

x,a

x,a

νπθ (x)πθ (a|x)P (y|x, a)

x,a

∂Vηπθ (y) X
∂Vηπθ (x)
−
νπθ (x)
∂θi
∂θi
x

X
∂Vηπθ (y) X
∂Vηπθ (x)
∂πθ (a|x) πθ
Aη (x, a) +
νπθ (y)
−
νπθ (x)
νπθ (x)
∂θi
∂θi
∂θi
y
x
νπθ (x)

∂πθ (a|x) πθ
Aη (x, a).
∂θi

To conclude the proof it is sufficient to note that
µπθ (x, a)

∂ log πθ (a|x)
µπ (x, a) ∂πθ (a|x)
∂πθ (a|x)
= θ
= νπθ (x)
.
∂θi
πθ (a|x)
∂θi
∂θi

B.3. The closed form of the TRPO update
Here we derive the closed-form solution of the TRPO update. To do so, we first briefly
summarize the mechanism of the algorithm. The main idea of Schulman et al. (2015)
is replacing ρ(µ0 ) by the surrogate
X
X
Lπ (π 0 ) = ρ(π) +
νπ (x)
π 0 (a|x)Aπ∞ (x, a),
x

a

26

A unified view of entropy-regularized MDPs

where Aπ∞ is the unregularized advantage function corresponding to policy π.
Furthermore, TRPO uses the regularization term
DTRPO (µkµ0 ) =

X

νµ0 (x)

X

x

πµ (a|x) log

a

6

πµ (a|x)
.
πµ0 (a|x)

The difference between L + DTRPO and ρ + DC is that the approximate version ignores
the impact of changing the policy π on the stationary distribution. Given this surrogate
objective, TRPO approximately computes the distribution


1
(28)
µk+1 = arg max Lµk (µ) − DTRPO (µkµk ) .
η
µ∈∆
Observing that the TRPO policy update can be expressed equivalently as
(

)
X
X
1
π(a|x)
π(a|x) Aπ∞k (x, a) − log
πk+1 = arg max
νµk (x)
,
η
πk (a|x)
π
a
x
we can see that the policy update can be expressed in closed form as
πk

πk+1 (a|x) ∝ πk (a|x)eηA∞ (x,a) .
This update then can be seen as a regularized greedy step with respect to the value
function of the previous policy πk .

6. This form is inspired by the well-known identity we state as Lemma 3.

27

