#  A general Markov decision process formalism for action-state entropy-
regularized reward maximization

Dmytro Grytskyy  Center for Brain and Cognition, and Department of Information
and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain
Jorge Ramírez-Ruiz  Center for Brain and Cognition, and Department of
Information and Communication Technologies, Universitat Pompeu Fabra,
Barcelona, Spain  Rubén Moreno-Bote  Center for Brain and Cognition, and
Department of Information and Communication Technologies, Universitat Pompeu
Fabra, Barcelona, Spain  Serra Húnter Fellow Programme, Universitat Pompeu
Fabra, Barcelona, Spain

###### Abstract

Previous work has separately addressed different forms of action, state and
action-state entropy regularization, pure exploration and space occupation.
These problems have become extremely relevant for regularization,
generalization, speeding up learning and providing robust solutions at
unprecedented levels. However, solutions of those problems are hectic, ranging
from convex and non-convex optimization, and unconstrained optimization to
constrained optimization. Here we provide a general dual function formalism
that transforms the constrained optimization problem into an unconstrained
convex one for any mixture of action and state entropies. The cases with pure
action entropy and pure state entropy are understood as limits of the mixture.

##  1 Introduction

It is well known that classical reinforcement learning, understood as learning
from external rewards, has severe limitations. While it has been posited that
reward is “enough" to learn any behavior [1], agents interacting with the real
world often have only access to sparse rewards. Many approaches have been
proposed to overcome the sparse reward limitation, endowing agents with
additional signals to be optimized along with the rewards. These include
minimizing surprise by refining predictions [2, 3, 4, 5, 6, 7], novelty
seeking by visiting states with low visit counts [8, 9, 10], generating
actions that leads to predictable transitions (empowerment) [11, 12, 13], or
seeking pure state entropy [14] and related forms of pure exploration
objectives [3, 15, 16, 17, 18, 19], to name a few.

A popular choice for augmenting the reward signal –the one that we focus on in
this paper– is with entropy regularization [20, 21, 22, 23, 24, 25, 26, 27,
28]. The idea is that the agent will be driven, all else equal, to visit
states and taking actions that make the agent act as random as possible (pure
entropy regularization, e.g., [25]) or penalize the agent for having a policy
very different from a default policy (KL regularization, e.g., [20]). Using
this type of regularization can lead to better exploration [14], more variable
and realistic behaviors [29], more efficient learning [30, 25] and more robust
solutions [21] against noise and adversarial attacks [19] than classical
reinforcement learning algorithms.

While the above approaches use entropy as a regularizer to the optimization
reward problem, the specific type of entropy regularizer varies widely across
studies, and as a result the approaches and the solutions are hectic. For
instance, some use pure action entropy regularization [31, 24, 25, 26], others
employ purely state entropy [14], others take advantage of KL action
regularization [32, 23, 28], and yet others combine action and state pure
entropy in balanced [33, 22] or arbitrary ways [29]. The variety of approaches
and techniques makes it hard to know what the specific effects of different
weighting of action and state entropies are on exploration, robustness, and
generalization.

To address these questions, it is important to first develop an overarching
theory that ideally includes all previous approaches as limits or special
cases. This is indeed the goal and achievement of this paper. We first show
that augmenting the standard reward objective with a non-negative mixture of
action and state entropies leads to a convex optimization problem. We next
show that the optimization problem can be cast in its dual form, from where it
is easier to prove existence and uniqueness of the optimal distribution
$p(s,a)$ over states $s$ and actions $a$. Here we focus on the harder problem
where the future reward discount factor equals one, $\gamma=1$. The case
$\gamma<1$ can be treated using more standard approaches. As expected, KL
regularization is a special case where rewards are simply redefined. Next, we
derive a general iterative method to find the optimal solution, which is shown
to converge in practice. We conclude by showing in simple examples how the
optimal behavior of the agent depends on the values of the action-state
entropy mixture, which suggests that it can be a flexible way for biasing
exploration towards actions or states.

##  2 Results

###  2.1 Markov decision problem with a mixture of action entropy and state
entropy

The agent is modeled as a finite action-state Markov decision process (MDP) in
discrete time. At any state $s$ the agent can choose one action $a$ out of
several possible (non-empty set) with a probability $\pi(a|s)$. Given the
state $s$ and action performed $a$, a new state $s^{\prime}$ results with
probability $p(s^{\prime}|s,a)$. The set of all probabilities
$\pi=\\{\pi(a|s)\\}$ defines the agent’s policy. We do not need to assume that
the MDP be ergodic, and thus different subsets of states can be disconnected
and absorbing states are allowed. The distribution over states and actions
$p(s,a)$ is the stationary probability under the policy, understood as
frequency of visiting $(s,a)$ averaged over time, realizations over
transitions and initial conditions following the same distribution.

We define the immediate policy-dependent reward for being at state $s$ and
performing action $a$ as

$R_{\pi}(s,a)=r(s,a)-\alpha\log\pi(a|s)-\beta\log p_{\pi}(s)\;.$ (1)

The first term on the right-hand side is the standard policy-independent
reward $r(s,a)$ (assumed to be finite), while the second and third terms
correspond to policy-dependent intrinsic rewards [14, 23, 25, 29]. The first
one is an exploration bonus for performing rare actions, while the second is
an exploration bonus for visiting rare states. The parameters $\alpha\geq 0$
and $\beta\geq 0$ measure the relative strengths between action and state
entropies and with respect to the reward. Note that it is possible to
introduce additional terms of the form $\log\pi_{0}(a|s)$ and $\log p_{0}(s)$,
where $\pi_{0}(a|s)$ is an arbitrary default policy and $p_{0}(s)$ is an
arbitrary default stationary distribution by replacing the log terms in Eq.
(1) by $-\alpha\log(\pi(a|s)/\pi_{0}(a|s))-\beta\log(p(a|s)/p_{0}(a|s))$;
introducing a default policy ($\alpha=1$ and $\beta=0$) is customary in
approaches where the entropy regularization is replaced by a KL regularization
[20, 23, 28]. The formalism and solutions that we describe below do not
change, and the above case can be simply obtained by replacing in every
equation $r(s,a)$ with the policy-independent total reward
$\tilde{r}(s,a)=r(s,a)+\alpha\log\pi_{0}(a|s)+\beta\log p_{0}(s)$. The
additional terms can be understood as generating an additional form of
intrinsic reward, which can be arbitrarily negative for impossible actions or
unreachable states under the default policy and default state probability
distribution.

We define the average total reward of Eq. (1) as

$R_{\pi}=\sum_{s,a}p_{\pi}(s,a)\left(r(s,a)-\log(\pi^{\alpha}(a|s)p_{\pi}^{\beta}(s))\right)\;,$
(2)

where $p_{\pi}(s,a)\equiv\pi(a|s)p_{\pi}(s)$ is the stationary joint state-
action distribution under policy $\pi(a|s)$ (existence a stationary
distribution is not strictly required, that is, solutions can be periodic, and
then $p_{\pi}(s,a)$ is understood as action-state frequency counts over the
long run) The objective is to find the policy $\pi(a|s)$ that maximizes
average total reward

$R_{max}=\max_{\pi}\sum_{s,a}p_{\pi}(s,a)\left(r(s,a)-\log(\pi^{\alpha}(a|s)p^{\beta}_{\pi}(s))\right)\;,$
(3)

under suitable constraints (see below). However, this objective is in general
non-convex in $\pi$ (e.g., for $\alpha=0$ and $\beta=1$, see [14]).

Eq. (2) includes, and expands, a number of standard problems that have been
considered previously: action-state entropy $(\alpha,\beta)=(1,1)$ [33], pure
state-dependent action entropy $(\alpha,\beta)=(1,0)$ [31], and pure state
entropy $(\alpha,\beta)=(0,1)$ [14]. Action-state entropy problems [33] leads
to an unconstrained optimization problem through the dual function approach;
pure state-dependent action entropy problems leads to a constrained convex
optimization problem [31]; pure state entropy problems leads to a convex
optimization problem [14].

The main contribution of this paper is to show that the average total reward
optimization (primal) problem defined in Eq. (2) can be transformed into a
convex optimization problem for $\alpha\geq 0$ and $\beta\geq 0$ that can be
easily solved as unconstrained convex optimization using the dual problem for
$\alpha>0$ and $\beta>0$. The pure cases with $\alpha=0$ or $\beta=0$ are
understood as limits of the obtained solutions.

###  2.2 The optimization problem is concave in $p(s,a)$

The optimization problem can be recast as a convex optimization problem by
optimizing $p(s,a)$ instead of the policy $\pi(a|s)$. Once the optimal
$p(s,a)$ is obtained, the state-distribution is defined as
$p(s)=\sum_{a}p(s,a)$, and the policy is realized as $\pi(a|s)=p(s,a)/p(s)$,
where we assume that $p(s)>0$. For $s$ such that $p(s)=0$, the policy
$\pi(a|s)$ can be arbitrarily defined. Written as a function of
$p=\\{p(s,a)\\}$, the average total reward is

$R_{p}=\sum_{s,a}p(s,a)\left(r(s,a)-\log\left(\frac{p^{\alpha}(s,a)}{p^{\alpha}(s)}p^{\beta}(s)\right)\right)\;.$
(4)

The objective is to maximize the average total reward with respect to $p$,

$R_{max}=\max_{p}\sum_{s,a}p(s,a)\left(r(s,a)-\log\left(\frac{p^{\alpha}(s,a)}{p^{\alpha}(s)}p^{\beta}(s)\right)\right)$
(5)

under the constraints

$\displaystyle p(s,a)\geq 0$ (6) $\displaystyle\sum_{s,a}p(s,a)=1$ (7)
$\displaystyle\sum_{s,a}p(s^{\prime}|s,a)p(s,a)=\sum_{b}p(s^{\prime},b)\;.$
(8)

The expression $\sum_{a}g(s,a)$ denotes the sum over all actions available at
state $s$.

######  Theorem 2.1.

The average total reward $R_{p}$ is concave in $p$ for $\alpha\geq 0$ and
$\beta\geq 0$.

To see this, we first rewrite $R_{p}$ as

$\displaystyle R_{p}$ $\displaystyle=$
$\displaystyle\sum_{s,a}p(s,a)r(s,a)-\alpha\sum_{s,a}p(s,a)\log p(s,a)$ (9)
$\displaystyle-(\beta-\alpha)\sum_{s,a}p(s,a)\log\left(\sum_{b}p(s,b)\right).$

We note that $R_{p}$ is continuous in $p$ in the whole domain and
differentiable for $0<p(s,a)<1$. Therefore, concavity of $R_{p}$ is equivalent
to show that the second order derivative in any direction from any
$0<p(s,a)<1$ for all $(s,a)$ (i.e., away from the simplex boundaries) are non-
positive. From any such $p(s,a)$, consider the direction $u(s,a)$ (we only
need to consider directions such that $\sum_{s,a}u(s,a)=0$ so that
$p(s,a)+\eta u(s,a)$ is a probability distribution for small enough values of
$\eta$). To compute the 2nd-order directional derivatives, we first write the
average reward by moving $p(s,a)$ in the direction $u(s,a)$ by an amount
$\eta$

$\displaystyle R_{p,u}(\eta)$ $\displaystyle=$
$\displaystyle\sum_{s,a}(p(s,a)+\eta u(s,a))r(s,a)$ (10)
$\displaystyle-\alpha\sum_{s,a}(p(s,a)+\eta u(s,a))\log(p(s,a)+\eta u(s,a))$
$\displaystyle-(\beta-\alpha)\sum_{s,a}(p(s,a)+\eta
u(s,a))\log\left(\sum_{b}(p(s,b)+\eta u(s,b))\right).$

From here, the 2nd-order directional derivative is

$\displaystyle R^{{}^{\prime\prime}}_{p,u}(\eta)\Bigr{\rvert}_{\eta=0}=$
$\displaystyle-\alpha\sum_{s}\left(\sum_{a}\frac{u^{2}(s,a)}{p(s,a)}-\frac{(\sum_{a}u(s,a))^{2}}{\sum_{a}p(s,a)}\right)-\beta\sum_{s}\frac{(\sum_{a}u(s,a))^{2}}{\sum_{a}p(s,a)}\leq
0$ (11)

for $\alpha\geq 0$ and $\beta\geq 0$. To see this, note that the second term
in the right-hand side is non-positive for all directions iff $\beta\geq 0$
(it is zero in the trivial direction $u(s,a)=0$ for all $s$ and $a$, but also
in the action directions such that $\sum_{a}u(s,a)=0$ for all $s$). Likewise,
the first term is non-positive for al directions iff $\alpha\geq 0$; it is
only zero for the trivial direction and the parallel direction $u(s,a)\propto
p(s,a)$. This is because each term in the sum over $s$ is non-negative, as it
can be seen by using Schwartz’s inequality
$(\sum_{a}x_{a}^{2})(\sum_{a}y_{a}^{2})\geq(\sum_{a}x_{a}y_{a})^{2}$ with
$x_{a}=u(s,a)/\sqrt{p(s,a)}$ and $y_{a}=\sqrt{p(s,a)}$. As the parallel
direction is excluded because it does not obey the normalization condition
$\sum_{s,a}u(s,a)=0$, then the first term is strictly negative iff $\alpha>0$.
In summary, the 2nd-order derivative in any direction from any $p(s,a)$ not in
the simplex boundaries is non-positive for $(\alpha\geq 0,\beta\geq 0)$, which
implies that the average total reward $R_{p}$ is concave everywhere due to
continuity, concluding the proof.

Along with the fact that the constraints (6-8) are linear in $p(s,a)$, and
thus define a convex set, the optimization problem in Eqs. (5-8) is convex.

Previous work has shown that the average total reward for the cases
$(\alpha,\beta)=(1,1)$ [33], $(\alpha,\beta)=(1,0)$ [31] and
$(\alpha,\beta)=(0,1)$ [14] is concave in $p(s,a)$. Thus, Theorem 2.1 can also
be readily obtained by linearly combining the second and third cases with non-
negative coefficients $(\alpha\geq 0,\beta\geq 0)$. The novelty of our proof
is to show that Eq. (9) is concave iff $(\alpha\geq 0,\beta\geq 0)$ if we
allow any direction, including the parallel one.

###  2.3 Critical points

We now find the critical points of the average total reward (4) as a function
of $p$ under the constraints (6-8) using Lagrange multipliers. The Lagrangian
$L\equiv L(p,V,\lambda)$ is

$\displaystyle L$ $\displaystyle=$
$\displaystyle\sum_{s,a}p(s,a)r(s,a)-\alpha\sum_{s,a}p(s,a)\log
p(s,a)-(\beta-\alpha)\sum_{s,a}p(s,a)\log\left(\sum_{b}p(s,b)\right)$ (12)
$\displaystyle+\sum_{s^{\prime}}V(s^{\prime})\left(\sum_{s,a}p(s^{\prime}|s,a)p(s,a)-\sum_{b}p(s^{\prime},b)\right)+\lambda\left(\sum_{s,a}p(s,a)-1\right)\;,$

where the $V$ and $\lambda$ are multipliers, and condition (6) will be shown
below to be automatically satisfied by the optimal solution. Differentiating
with respect to each $p(s,a)$ leads to the equation for the critical points of
the average total reward

$\displaystyle\frac{\partial L}{\partial p(s,a)}$
$\displaystyle=r(s,a)-\alpha-\alpha\log
p(s,a)-(\beta-\alpha)\log\left(\sum_{b}p(s,b)\right)$
$\displaystyle-(\beta-\alpha)\frac{\sum_{a}p(s,a)}{\sum_{b}p(s,b)}+\sum_{s^{\prime}}V(s^{\prime})p(s^{\prime}|s,a)-V(s)+\lambda$
$\displaystyle=0\;.$ (13)

After simplification and solving for $p(s,a)$, we obtain for $\alpha\neq 0$
the equation

$p(s,a)=e^{(\lambda-\beta)/\alpha}\left(\sum_{b}p(s,b)\right)^{1-\beta/\alpha}e^{A(s,a)/\alpha}\;,$
(14)

where we have defined the advantage function

$A_{V}(s,a)=r(s,a)+\sum_{s^{\prime}}V(s^{\prime})p(s^{\prime}|s,a)-V(s)\;.$
(15)

Note that $V(s)$ can be interpreted as the value of being at state $s$, and
thus states with larger $V(s)$ are preferred over the others [33, 34].

Summing over $a$ in Eq. (14) and solving for $\sum_{a}p(s,a)$, we obtain for
$\beta\neq 0$

$\sum_{a}p(s,a)=e^{\lambda/\beta-1}\left(\sum_{a}e^{A_{V}(s,a)/\alpha}\right)^{\alpha/\beta}$
(16)

Inserting this equation into the right-hand side of Eq. (14)

$p(s,a)=e^{\lambda/\beta-1}\left(\sum_{b}e^{A_{V}(s,b)/\alpha}\right)^{\alpha/\beta-1}e^{A_{V}(s,a)/\alpha}\;.$
(17)

Normalization of $p(s,a)$ implies that

$p(s,a)=\frac{1}{Z_{V}}\left(\sum_{b}e^{A_{V}(s,b)/\alpha}\right)^{\alpha/\beta-1}e^{A_{V}(s,a)/\alpha}\;,$
(18)

with normalization constant

$Z_{V}=\sum_{s}\left(\sum_{a}e^{A_{V}(s,a)/\alpha}\right)^{\alpha/\beta}\;,$
(19)

and the multiplier $\lambda$ is given by

$\lambda=\beta(1-\log Z_{V})\;.$ (20)

Eqs. (18-19) formally define the optimal state-action joint probability
$p^{*}(s,a)$ as a function of the optimal multipliers $V^{*}$. It is clear
that for any value of the $V$ the probabilities are non-negative, and
therefore condition (6) is automatically satisfied. The normalization
condition (7) is obviously satisfied. It is shown below that condition (8) is
satisfied by the optimal values $V^{*}$, thus fully determining $p^{*}(s,a)$.

Once the optimal $V^{*}$ is obtained, the optimal policy is

$\pi^{*}(a|s)=\frac{e^{A_{V^{*}}(s,a)/\alpha}}{\sum_{b}e^{A_{V^{*}}(s,b)/\alpha}}\;,$
(21)

the optimal joint action-state probability is

$p^{*}(s,a)=\frac{1}{Z_{V^{*}}}\left(\sum_{b}e^{A_{V^{*}}(s,b)/\alpha}\right)^{\alpha/\beta-1}e^{A^{*}(s,a)/\alpha}$
(22)

and the stationary state distribution becomes

$p^{*}(s)=\frac{1}{Z_{V^{*}}}\left(\sum_{a}e^{A_{V^{*}}(s,a)/\alpha}\right)^{\alpha/\beta}\;.$
(23)

###  2.4 Dual function

We consider the primal problem the one defined in (5-8). The dual problem
consists in minimizing the dual function of the Lagrangian with respect to the
multipliers. The dual function for $\alpha>0$ and $\beta>0$ is obtained by
replacing $p(s,a)$ in the (log terms of the) Lagrangian (12) by their critical
values in Eq. (17) as a function of the multipliers. This substitution leads
to the dual function (Appendix B)

$L^{d}(V,\lambda)=\beta\log Z_{V}\;.$ (24)

Due to duality, maximizing the average total reward in the primal problem
(5-8) is equivalent to minimizing the partition function $Z_{V}$ in Eq. (19)
with respect to the $V$ without any constraint (see Appendix B to confirm that
$\lambda$ can be chosen to obey the normalization constraint
(LABEL:eq:p2_norm)). Therefore, the initial constrained concave optimization
problem has been transformed into an unconstrained convex optimization one
where $\log Z_{V}$ is to be minimized with no constraints over the $V$, and
thus

$V^{*}=\operatorname*{arg\,min}_{V}\log Z_{V}\;.$ (25)

From here, the optimal policy and state probability are found using Eqs.
(21-23).

Although from duality it is clear that $\log Z_{V}$ is convex in $V$, this
fact can also be directly checked, as follows. This exercise will also show
under what conditions the $\log Z_{V}$ is strictly convex, which will be
important to show below uniqueness of the optimal solution. We first write the
dual function as

$L^{d}(V)=\beta\log
Z_{V}=\beta\log\left(\sum_{s}e^{\frac{\alpha}{\beta}\log(\sum_{a}e^{A_{V}(s,a)/\alpha})}\right)$
(26)

and notice that $A_{V}(s,a)$ is convex in the $V$ (indeed, it is linear).
Then, by noticing that $\log Z_{V}$ is an increasing function of $A_{V}$, we
just need to show that it is convex in $A_{V}$, as the composition of an
increasing convex function with a convex function is convex (see Appendix A).
Further, we note that Eq. (26) is the composition of two identical functions
of the log-sum-exp form $h(x)=\log(\sum_{i}e^{cx_{i}})$ with (possibly
different) positive $c$. Both are increasing, and therefore according to the
previous composition rule for convexity it remains to be seen that $h(x)$ is
convex to show that $\log Z_{V}$ is convex in $V$.

Although convexity of $h(x)$ is a well-known fact [35], here we explicitly
prove it to get additional information that will be relevant to show
uniqueness of the optimal solution. Let us calculate the 2nd-order directional
derivative of $h(x)$ in a direction $y$. For that, consider $h(x+\eta y)$.
Taking the 2nd-order derivative with respect to $\eta$ and noticing that the
we can take $c=1$ without affecting the conclusions on convexity, we find

$\frac{\partial^{2}h(x)}{\partial\eta^{2}}|_{\eta=0}=\frac{(\sum_{i}y^{2}_{i}e^{x_{i}})(\sum_{i}e^{x_{i}})-(\sum_{i}y_{i}e^{x_{i}})^{2}}{(\sum_{i}e^{x_{i}})^{2}}\geq
0\;,$ (27)

where in the inequality we have used the fact that the denominator is
positive, as the action set in non-empty for all $s$, and that the numerator
is non-negative in virtue of the Schwartz’s inequality
$(\sum_{i}w_{i}\tilde{x}_{i}^{2})(\sum_{i}w_{i}\tilde{y}_{i}^{2})\geq(\sum_{i}w_{i}\tilde{x}_{i}\tilde{y}_{i})^{2}$
($w_{i}>0$) with $w_{i}=e^{x_{i}}$, $\tilde{x}_{i}=1$ and
$\tilde{y}_{i}=y_{i}$. This shows that for any $x$ and for any direction $y$
the 2nd-order directional derivative is non-negative, showing that $h(x)$ is
convex, which finally implies that $\log Z_{V}$ is convex in $A_{V}$ being a
composition of $h(x)$ with itself (with possibly different positive values of
$c$).

Now, looking at Eq. (27) and using Schwartz’s inequality, it is clear that
$h(x)$ is strictly convex in all directions $y$ except in the direction
$y_{i}=1$. As $\log Z_{V}$ is the composition of the increasing convex $h(x)$
with itself, this implies that $\log Z_{V}$ is strictly convex in all
directions except in the diagonal direction where $A_{V}(s,a)$ changes by a
constant $A_{0}$ for all $(s,a)$ (that is, $A(s,a)\rightarrow A(s,a)+A_{0}$).
In the diagonal direction, $\beta\log Z_{V}$ is linear and increasing exactly
as $A_{0}$, as it can be easily checked.

Also, from duality the location $V^{*}$ of the minimum of the dual function,
Eq. (25), makes the optimal joint state-action probability in Eq. (22) to
satisfy condition (8). In other words, while conditions (6-7) are
automatically fulfilled by the state-action probability Eq. (22) for any
choice of the $V$, condition (8) is only fulfilled when $V=V^{*}$ (here
equality is understood as matching a member of the class of critical points).
To see that for $V=V^{*}$ condition (8) is satisfied, let us compute the
critical points of the dual function by taking derivatives with respect the
$V$ in Eq. (26),

$\displaystyle\frac{\partial L^{d}(V)}{\partial V(s)}$ $\displaystyle=$
$\displaystyle\frac{\beta}{Z_{V}}\Big{(}-\beta^{-1}e^{\frac{\alpha}{\beta}\log(\sum_{a}e^{A_{V}(s,a)/\alpha})}$
(28)
$\displaystyle+\beta^{-1}\sum_{s^{\prime}}e^{\frac{\alpha}{\beta}\log(\sum_{a}e^{A_{V}(s^{\prime},a)/\alpha})}\frac{\sum_{a}p(s|s^{\prime},a)e^{A_{V}(s^{\prime},a)/\alpha}}{\sum_{a}e^{A_{V}(s^{\prime},a)/\alpha}}\Big{)}$
$\displaystyle=0\;.$

Rearranging terms, this implies that

$\displaystyle\frac{1}{Z_{V}}e^{\frac{\alpha}{\beta}\log(\sum_{a}e^{A_{V}(s,a)/\alpha})}=\sum_{s^{\prime},a}p(s|s^{\prime},a)\frac{e^{\frac{\alpha}{\beta}\log(\sum_{a}e^{A_{V}(s^{\prime},a)/\alpha})}e^{A_{V}(s^{\prime},a)/\alpha}}{Z_{V}\sum_{b}e^{A_{V}(s^{\prime},b)/\alpha}}\;.$
(29)

Now, using Eq. (18), the left-hand side equals $p(s)=\sum_{a}p(s,a)$ and the
right-hand side equals $\sum_{s^{\prime},a}p(s|s^{\prime},a)p(s^{\prime},a)$.
Thus at the critical point(s) Eq. (29) is satisfied, and therefore condition
(8) holds when $V=V^{*}$. Obviously from the above, if $V\neq V^{*}$, then
condition (8) does not hold. In summary, the optimal solution is found at the
critical points of the dual function (which can be at $V(s)=\pm\infty$ for
some $s$).

The above results lead to

######  Theorem 2.2.

The optimal $p^{*}(s,a)$ maximizing the average total reward $R_{p}$ under the
constraints (6-8) for $\alpha>0$ and $\beta>0$ is unique and satisfies

$\displaystyle
p^{*}(s,a)=\frac{1}{Z_{V^{*}}}e^{(\frac{\alpha}{\beta}-1)\log(\sum_{b}e^{A_{V^{*}}(s,b)/\alpha})+A_{V^{*}}(s,a)/\alpha}$
(30)

with

$Z_{V^{*}}=\sum_{s}e^{\frac{\alpha}{\beta}\log(\sum_{a}e^{A_{V^{*}}(s,a)/\alpha})}\;,$
(31)

and

$A_{V^{*}}(s,a)=r(s,a)+\sum_{s^{\prime}}V^{*}(s^{\prime})p(s^{\prime}|s,a)-V^{*}(s)\;,$
(32)

where the $V^{*}$ minimize the (convex) dual function

$L^{d}(V)=\beta\log
Z_{V}=\beta\log\left(\sum_{s}e^{\frac{\alpha}{\beta}\log(\sum_{a}e^{A_{V}(s,a)/\alpha})}\right)\;,$
(33)

that is,

$V^{*}=\operatorname*{arg\,min}_{V}\log Z_{V}\;.$ (34)

The maximum average total reward is

$R_{max}=\beta\log Z_{V^{*}}\;.$ (35)

For $s$ such that $p(s)>0$, the optimal policy is uniquely defined by

$\pi^{*}(a|s)=\frac{e^{A_{V^{*}}(s,a)/\alpha}}{\sum_{b}e^{A_{V^{*}}(s,b)/\alpha}}\;.$
(36)

while for $s$ such that $p(s)=0$ the policy can be arbitrarily defined.

It remains to show uniqueness and the validity of Eq. (35).

That $A^{*}(s,a)$ and thus $p^{*}(s,a)$ are unique can be seen from the strict
convexity of $\log Z_{V}$ as a function of the $A(s,a)$ in directions away
from the diagonal direction. First, assume that there are two optimal (minima)
solutions $V^{*}$ of $\log Z_{V}$ such that $A^{*}_{1}(s,a)$ and
$A^{*}_{2}(s,a)$ are different for some $s$ and $a$. Then, it is not possible
that $A^{*}_{1}=A^{*}_{2}+d$ with a constant $d\neq 0$; otherwise, the value
of $\log Z_{V}$ would be different for the two optimal solutions as $\beta\log
Z_{V}$ is linear in $d$ with slope $1$, contradicting that both are optimal
minima. Therefore, the line that joins $A_{1}^{*}$ and $A_{2}^{*}$ is not in
the diagonal direction. But we already know that $\log Z_{V}$ in any non-
diagonal direction is strictly convex in $A(s,a)$. Therefore, there should a
lower value of $\log Z_{V}$ in between the points $A_{1}^{*}$ and $A_{2}^{*}$,
contradicting that they were the absolute minima. This concludes the proof
that $A^{*}(s,a)$ and thus $p^{*}(s,a)$ are unique.

The previous reasoning also reveals that there are degeneracies in the values
of $V^{*}$, that is, their optimal values are not unique: from Eq. (32) if
$V^{*}(s)$ is an optimal solution, then $V^{*}(s)+d$ for any $d$ is also an
optimal solution, as the value of $A^{*}$ remains unchanged. Degeneracies of
$V^{*}$ are not restricted to the diagonal direction. For instance, if
$p(s^{\prime}=s|s,a)=1$ for some $s$ and for all actions $a$ in that state,
then any value of $V^{*}(s)$ is valid –the value function for the "isolated",
self-connected, node $s$ does not affect the rest of $V^{*}$. Note that this
node would be unreachable from other nodes, but it has generally assigned an
non-zero optimal probability, $p^{*}(s,a)>0$, to increase state entropy.

To conclude the proof of the theorem, Eq. (35) results from strong duality, or
more directly from substitution of the optimal state-action probability Eq.
(30) into Eq. (9).

###  2.5 Solvable toy example

Figure 1: Action and state entropy regularizers have different effects on
optimal policies. (a) Schematic of a toy example. There are two “outer" states
from which it is possible to transition to any other state ($n+2$ actions),
and $n$ “inner" states, from which there are only transitions to the outer
states. (b) Grid world arena. The agent (grey square) has nine available
actions unless constrained by the walls. Therefore, in the middle of the
corridor, there are only three actions: left, right, nothing. (c) Heatmap of
state distributions for two agents with the associated hyperparameters. An
action-focused agent ($\alpha>\beta$, top) prefers the middle of the room,
given the action availability, wheres a state-focused agent ($\beta>\alpha$,
bottom) prefers being spread out evenly in state space. (d) Fraction of time
spent in the corridor for various $\alpha$ and $\beta$ values, where
$\alpha\beta=10$, for various corridor lengths.

We consider here a simple MDP, described in Fig. 1a with $r(s,a)=0$ to study
how states and actions are occupied for different values of $\alpha$ and
$\beta$ without the effect of rewards. This example is designed such that
there are few states with many possible actions and many states with few
actions, so that the effects of manipulating the weights of the action and
state entropies are the clearest. There are two "outer" states of the same
kind, and $n>0$ "inner" states of the same kind. From an outer state, the
agent can take the action of going to the other outer state or go to any of
the inner states. From the inner state, it is only possible to choose the
action of going to one outer state or to the other. Transitions are
deterministic given the action. Thus, there are a total of $n+2$ states; from
the outer states there are $n+1$ possible actions and from the inner states
there are $2$ possible actions. We expect that the state distribution for an
agent with $\alpha\gg\beta$, which favors action entropy over state entropy,
would show a larger probability for the outer than for the inner states. The
reverse is expected for an agent with $\alpha\ll\beta$. Because of the
symmetry of the MDP and the strict convexity of the dual function in any non-
diagonal direction, the optimal values should be identical for the two outer
states, and also identical for the $n$ inner states, but they can differ
between them. Let us call these values $V(s_{outer})=u$ and $V(s_{inner})=w$,
and choose $w=0$ arbitrarily because only relative values are important. The
dual function takes the form

$\displaystyle L^{d}(u)$ $\displaystyle=$ $\displaystyle\beta\log Z_{u}$
$\displaystyle=$
$\displaystyle\beta\log\left(2(1+ne^{-u/\alpha})^{\alpha/\beta}+2^{\alpha/\beta}ne^{u/\beta}\right)$

and its critical point $dL^{d}(u)/du=0$ is given by

$(1+ne^{-u/\alpha})^{\alpha/\beta-1}e^{-u/\alpha}=2^{\alpha/\beta-1}e^{u/\beta}\;.$
(37)

Now we consider three relevant cases:

$\bullet$ $(\alpha=1,\beta=1)$. From Eq. (37) we have $u=0$. Therefore, the
optimal values are identical for all nodes. However, the probabilities of
outer and inner states are not the same. From Eq. (21) it is clear that the
optimal policy is uniform in all the actions, that is, the probability of
going to an inner or outer state from an outer state is the same, and equals
$1/(n+1)$. Using condition (8), this leads to $p(s_{outer})=(n+1)/(2(2n+1))$
and $p(s_{inner})=1/(2n+1)$, and therefore outer are more likely than inner
states. This makes sense, as outer states can achieve higher action entropy
and a balance between action and state entropies is sought by the agent.

$\bullet$ $(\alpha=1,\beta=0)$. Taking the limit $\beta\rightarrow 0$ in Eq.
(37), we obtain $u=\log(1+\sqrt{1+8n})-2\log 2\geq 0$. Therefore, the value of
the outer states grows with $n$ compared to the value of the inner states. In
this case, the transition probability from an outer to the other outer state
is $\pi_{n}=1/(1+ne^{-u})$, which is $\geq$ than the uniform $1/(n+1)$. The
transition probability from an outer to a given inner state is
$1/(n+e^{u})\leq 1/(n+1)$. As a result, $p(s_{outer})=1/(2(2-\pi_{n}))$,
larger than in the previous example.

$\bullet$ $(\alpha=0,\beta=1)$. Taking the limit $\alpha\rightarrow 0$ in Eq.
(37), we obtain $u=-\log(n/2)/2$ for $n>1$ and $u=0$ for $n=1$. Therefore, the
value of the outer states decreases with $n$. In this case
$\pi_{n}=1/(1+ne^{-u})$ is smaller than the uniform probability $1/(n+1)$ for
$n>2$, and $p(s_{outer})=1/(2(2-\pi_{n}))$ is smaller than for the first case
$(\alpha=1,\beta=1)$.

###  2.6 Limit cases

The cases $(\alpha>0,\beta=0)$ and $(\alpha=0,\beta>0)$ can be considered as
the limits of $\beta\rightarrow 0^{+}$ and $\alpha\rightarrow 0^{+}$
respectively. We now show in turn that the limits are well-defined and that
for the first case it corresponds to the actual known solution for
$(\alpha,\beta=0)$.

$\bullet$ $(\alpha>0,\beta\rightarrow 0^{+})$. We rewrite the equation of the
critical points, Eq. (28), as

$\displaystyle\sum_{a}e^{A_{V}(s,a)/\alpha}=\sum_{s^{\prime}}\frac{(\sum_{a}e^{A_{V}(s^{\prime},a)/\alpha})^{\alpha/\beta-1}}{(\sum_{a}e^{A_{V}(s,a)/\alpha})^{\alpha/\beta-1}}\sum_{a}e^{A_{V}(s^{\prime},a)/\alpha}p(s|s^{\prime},a)\;.$
(38)

for all $s$. We restrict ourselves to a MDP where it is possible to choose
actions such that there is a positive probability of reaching any state from
any other state in a finite number of steps. Define
$e^{\eta_{V}(s)/\alpha}=\sum_{a}e^{A_{V}(s,a)/\alpha}$, and assume that in the
limit $\beta\rightarrow 0$ the $\eta_{V}(s)$ are not identical for all $s$ and
that all of them are finite. This implies that there exists one state
$s^{\prime}$ with a successor state $s$ (that is, a state accessible from
$s^{\prime}$ using some action $a$: $p(s|s^{\prime},a)>0$) for which
$\eta_{V}(s^{\prime})>\eta_{V}(s)$. Looking at Eq. (38), it is clear that then
$\eta_{V}(s)=\infty$, as at least one of the ratios in the right-hand side of
the equation diverges as $\beta\rightarrow 0$ and the rightmost sum over
actions is finite and positive. This contradicts the initial assumption, and
therefore $\eta_{V}(s)=\alpha\log(\sum_{a}e^{A_{V}(s,a)/\alpha})=\eta_{V}$ are
identical for all $s$. If $\eta_{V}$ is infinite, then the dual function will
take infinite value, which cannot correspond to its minimum (e.g., choosing
$V(s)=0$ for all $s$ leads to a lower value of the dual function for finite
$r(s,a)$). In conclusion, all
$\alpha\log(\sum_{a}e^{A_{V}(s,a)/\alpha})=\eta_{V}$ must be finite and
independent of $s$, which implies, using Eq. (38), that

$\sum_{a}e^{A_{V}(s,a)/\alpha}=\sum_{s^{\prime},a}e^{A_{V}(s^{\prime},a)/\alpha}p(s|s^{\prime},a)\;.$
(39)

Therefore, in this limit, the dual function becomes
$L^{d}(V)=\beta\log(\sum_{s}e^{\eta_{V}/\beta})=\eta_{V}$. As the dual
function ought to be minimized with respect to $V$, and thus with respect to
$\eta_{V}$, then we have proved

######  Theorem 2.3.

The optimal $p(s,a)$ maximizing the average total reward $R_{p}$ under the
constraints (6-8) for $\alpha>0$ and $\beta\rightarrow 0^{+}$ is unique and
satisfies

$p^{*}(s,a)=\frac{e^{A_{V^{*}}(s,a)/\alpha}}{\sum_{s,b}e^{A_{V^{*}}(s,b)/\alpha}}$
(40)

where $V^{*}$ is such that the constraint

$\eta_{V^{*}}=\alpha\log\left(\sum_{a}e^{A_{V^{*}}(s,a)/\alpha}\right)$ (41)

is satisfied for all $s$, and $\eta_{V^{*}}$ is chosen such that it is the
smallest possible real number.

The maximum average total reward is

$R_{max}=\eta_{V^{*}}\;.$ (42)

The equations result from direct substitution of those in Theorem 2.2 and
taking the appropriate limit. We remark that the optimal solution is identical
to the exact case $(\alpha,\beta=0)$ [31], so here we have shown that the case
$(\alpha,\beta=0)$ corresponds to the limit of $(\alpha,\beta)$ as
$\beta\rightarrow 0$. We note that the constraint (41) is satisfied in the
example of Sec. (2.5).

$\bullet$ $(\alpha\rightarrow 0^{+},\beta>0)$. Taking the limit
$\alpha\rightarrow 0$ in Eq. (33) leads to a novel form of the dual function,

$L^{d}(V)=\beta\log\left(\sum_{s}e^{\max_{a}A_{V}(s,a)/\beta}\right)\;,$ (43)

which should be minimized as a function of $V$. It can be checked that the Eq.
(43) holds in the example of Sec. (2.5). The form of the dual function makes
sense given that the optimal policy in Eq. (36) becomes deterministic in the
limit, except for the possible degeneracy of actions having the same
$\max_{a}A_{V^{*}}(s,a)$. Therefore, in general the optimal policy is not
unique. The optimal policy can induce a periodic Markov process, in which case
$p(s,a)$ might be understood as the probability of finding the process in
$(s,a)$ when observed at a randomly chosen time. For instance, consider the
example consisting of a circular chain with $n$ states where transitions are
allowed to any of the two neighbors and $r(s,a)$ is uniform: the policy that
moves the agent from one state to its right neighbor state induces an uniform
probability in the chain, maximizing state entropy, but the process is
periodic. Importantly, if we take in this example $\alpha$ to be very small
but non-zero, then the problem is regularized and symmetries are broken, in
the sense that the optimal policy is unique and it corresponds to the uniform
action distribution (due to Theorem 2.2), which moves the agent to any of the
two neighboring states with equal probability.

$\bullet$ $(\alpha\rightarrow 0^{+},\beta\rightarrow 0^{+})$. Taking the limit
of $\alpha\rightarrow 0^{+}$ in Eq. (41) leads to the constraint

$\eta_{V^{*}}=\max_{a}A_{V^{*}}(s,a)$ (44)

for all $s$, where $V^{*}$ are chosen such that $\eta_{V^{*}}$ is minimized.
Putting the solution in the more recognizable format

$V^{*}(s)=\max_{a}\left(r(s,a)-\eta_{V^{*}}+\sum_{s^{\prime}}p(s^{\prime}|s,a)V^{*}(s^{\prime})\right)\;,$
(45)

it becomes apparent that it corresponds to the standard solution for the case
where the total reward is simply $R_{\pi}(s,a)=r(s,a)$ [34]. Therefore, one
recovers the well-known average-reward Bellman optimality equation for the RL
problem with no state-action entropy, whose policy is deterministic except for
possible action ties.

###  2.7 Experiments

We simulated an agent for different $(\alpha,\beta)$ in an arena with a room
and a narrow corridor (Fig. 1b; Appendix C.1). In the room there are more
actions than in the corridor. For $\alpha\gg\beta$ the agent seeks action over
state entropy, and therefore the room is occupied while the corridor is left
empty (Fig. 1c, top). In contrast, for $\beta\gg\alpha$ the agent seeks state
over action entropy, and therefore it occupies both the room and corridor more
uniformly (bottom). The effect of $\alpha$ on the fraction of time that the
agent spends in the corridor is smooth and decreases with it for various
corridor lengths (Fig. 1d).

Rather than using gradient descent over the $V$ directly on the dual function
in Eq. (33) to find the optimal $p^{*}(s,a)$, we developed an iterative scheme
that empirically is shown to effectively find the optimal solution (see
Appendix C.2).

##  3 Discussion

Optimal control and reinforcement learning approaches deal with the problem of
solving or obtaining optimal courses of action for a given measure. While it
has been postulated that a scalar reward signal is a sufficient measure to
obtain practically any desirable behavior [36, 1], this approach has severe
limitations that have been highlighted throughout the years [37, 38, 11, 39].
Here, we have shown that seemingly disparate entropy augmentations to the
scalar reward signal are in fact captured by a general framework whose unique
solutions we have found. Our central contribution is to provide a general dual
function formalism (convex and constraint-free) for arbitrary mixtures of
action and state entropy reward regularizers. Standard examples with only
action entropy, only state entropy, or balanced action-state entropy are
particular cases of our formalism (see Introduction). Other cases with no
entropy correspond to certain limits. KL approaches simply correspond to a
redefinition of the reward function in the general maximum mixed action-state
entropy formalism.

We surmise that general mixed action-state entropy regularization is important
because, by changing the mixture hyperparameters $\alpha$ and $\beta$
independently, the agent can be pushed to learn different aspects of an MDP,
namely, the action availability and the state availability, respectively.
Previous work has shown that KL action entropy regularization
($\alpha=1,\beta=0$ with the default policy being the previously learnt
policy) is critical to speed up and stabilize learning [30, 31, 25]. By
allowing arbitrary mixtures $(\alpha,\beta)$ of KL action and state
regularization with a default policy and state distributions corresponding to
the previously learnt ones, we propose that one could more effectively control
the learning process by: (1) biasing the agent to be conservative regarding
the policy update by using KL action regularization, or (2) biasing it to be
more conservative about the state distribution updates by using KL state
regularization. In the first case, the agent will try to repeat behaviors
previously learnt, but could fall into unexpected, potentially dangerous,
states; while in the second case, the agent will try to repeat visiting
previously visited states, but could end up performing undesired actions. Our
framework allows adjusting each depending on the desired learning process. A
complementary view of the same problem is also relevant: in the first case,
the agent is biased to explore state space more, while in the second case, it
prefers exploring action space more. We conjecture that balancing action and
state entropy is critical to optimize exploration and learning.

## Acknowledgments

This work is supported by the Howard Hughes Medical Institute (HHMI, ref
55008742) and MINECO (Spain; BFU2017-85936-P) to R.M.-B, and MINECO/ESF
(Spain; PRE2018-084757) to J.R.-R.

## References

  * Silver et al. [2021] David Silver, Satinder Singh, Doina Precup, and Richard S Sutton.  Reward is enough.  _Artificial Intelligence_ , 299:103535, 2021.
  * Achiam and Sastry [2017] Joshua Achiam and Shankar Sastry.  Surprise-based intrinsic motivation for deep reinforcement learning.  _arXiv preprint arXiv:1703.01732_ , 2017.
  * Pathak et al. [2017] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell.  Curiosity-driven exploration by self-supervised prediction.  In _International conference on machine learning_ , pages 2778–2787. PMLR, 2017.
  * Burda et al. [2018] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov.  Exploration by random network distillation.  _arXiv preprint arXiv:1810.12894_ , 2018.
  * Burda et al. [2019] Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A. Efros.  Large-scale study of curiosity-driven learning.  In _ICLR_ , 2019.
  * Fountas et al. [2020] Zafeirios Fountas, Noor Sajid, Pedro Mediano, and Karl Friston.  Deep active inference agents using monte-carlo methods.  _Advances in neural information processing systems_ , 33:11662–11675, 2020.
  * Hafner et al. [2020] Danijar Hafner, Pedro A Ortega, Jimmy Ba, Thomas Parr, Karl Friston, and Nicolas Heess.  Action and perception as divergence minimization.  _arXiv preprint arXiv:2009.01791_ , 2020.
  * Bellemare et al. [2016] Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos.  Unifying count-based exploration and intrinsic motivation.  _Advances in neural information processing systems_ , 29, 2016.
  * Tang et al. [2017] Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel.  # exploration: A study of count-based exploration for deep reinforcement learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Aubret et al. [2022] Arthur Aubret, Laetitia Matignon, and Salima Hassas.  An information-theoretic perspective on intrinsic motivation in reinforcement learning: a survey.  _arXiv preprint arXiv:2209.08890_ , 2022.
  * Klyubin et al. [2005] Alexander S Klyubin, Daniel Polani, and Chrystopher L Nehaniv.  Empowerment: A universal agent-centric measure of control.  In _2005 ieee congress on evolutionary computation_ , volume 1, pages 128–135. IEEE, 2005.
  * Jung et al. [2011] Tobias Jung, Daniel Polani, and Peter Stone.  Empowerment for continuous agent—environment systems.  _Adaptive Behavior_ , 19(1):16–39, 2011.
  * Mohamed and Jimenez Rezende [2015] Shakir Mohamed and Danilo Jimenez Rezende.  Variational information maximisation for intrinsically motivated reinforcement learning.  _Advances in neural information processing systems_ , 28, 2015.
  * Hazan et al. [2019] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest.  Provably efficient maximum entropy exploration.  In _International Conference on Machine Learning_ , pages 2681–2691. PMLR, 2019.
  * Lee et al. [2019] Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdinov.  Efficient exploration via state marginal matching.  _arXiv preprint arXiv:1906.05274_ , 2019.
  * Jin et al. [2020] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu.  Reward-free exploration for reinforcement learning.  In _International Conference on Machine Learning_ , pages 4870–4879. PMLR, 2020.
  * Zhang et al. [2021] Chuheng Zhang, Yuanying Cai, Longbo Huang, and Jian Li.  Exploration by maximizing rényi entropy for reward-free rl framework.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 10859–10867, 2021.
  * Mutti et al. [2021] Mirco Mutti, Lorenzo Pratissoli, and Marcello Restelli.  Task-agnostic exploration via policy gradient of a non-parametric state entropy estimate.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 9028–9036, 2021.
  * Eysenbach and Levine [2021] Benjamin Eysenbach and Sergey Levine.  Maximum entropy rl (provably) solves some robust rl problems.  _arXiv preprint arXiv:2103.06257_ , 2021.
  * Todorov [2009] Emanuel Todorov.  Efficient computation of optimal actions.  _Proceedings of the national academy of sciences_ , 106(28):11478–11483, 2009.
  * Ziebart [2010] Brian D Ziebart.  _Modeling purposeful adaptive behavior with the principle of maximum causal entropy_.  Carnegie Mellon University, 2010.
  * Tishby and Polani [2011] Naftali Tishby and Daniel Polani.  Information theory of decisions and actions.  In _Perception-action cycle_ , pages 601–636. Springer, 2011.
  * Schulman et al. [2017] John Schulman, Xi Chen, and Pieter Abbeel.  Equivalence between policy gradients and soft q-learning.  _arXiv preprint arXiv:1704.06440_ , 2017.
  * Nachum et al. [2017] Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans.  Bridging the gap between value and policy based reinforcement learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Haarnoja et al. [2018] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International conference on machine learning_ , pages 1861–1870. PMLR, 2018.
  * Hausman et al. [2018] Karol Hausman, Jost Tobias Springenberg, Ziyu Wang, Nicolas Heess, and Martin Riedmiller.  Learning an embedding space for transferable robot skills.  In _International Conference on Learning Representations_ , 2018.
  * Eysenbach et al. [2018] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine.  Diversity is all you need: Learning skills without a reward function.  _arXiv preprint arXiv:1802.06070_ , 2018.
  * Galashov et al. [2019] Alexandre Galashov, Siddhant M Jayakumar, Leonard Hasenclever, Dhruva Tirumala, Jonathan Schwarz, Guillaume Desjardins, Wojciech M Czarnecki, Yee Whye Teh, Razvan Pascanu, and Nicolas Heess.  Information asymmetry in kl-regularized rl.  _arXiv preprint arXiv:1905.01240_ , 2019.
  * Ramírez-Ruiz et al. [2022] Jorge Ramírez-Ruiz, Dmytro Grytskyy, and Rubén Moreno-Bote.  Seeking entropy: complex behavior from intrinsic motivation to occupy action-state path space.  _arXiv preprint arXiv:2205.10316_ , 2022.
  * Schulman et al. [2015] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In _International conference on machine learning_ , pages 1889–1897. PMLR, 2015.
  * Neu et al. [2017] Gergely Neu, Anders Jonsson, and Vicenç Gómez.  A unified view of entropy-regularized markov decision processes.  _arXiv preprint arXiv:1705.07798_ , 2017.
  * Todorov [2006] Emanuel Todorov.  Linearly-solvable markov decision problems.  _Advances in neural information processing systems_ , 19, 2006.
  * Peters et al. [2010] Jan Peters, Katharina Mulling, and Yasemin Altun.  Relative entropy policy search.  In _Twenty-Fourth AAAI Conference on Artificial Intelligence_ , 2010\.
  * Puterman [2014] Martin L Puterman.  _Markov decision processes: discrete stochastic dynamic programming_.  John Wiley & Sons, 2014.
  * Boyd et al. [2004] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Sutton et al. [1998] Richard S Sutton, Andrew G Barto, et al.  Introduction to reinforcement learning.  1998\.
  * McNamara and Houston [1986] John M McNamara and Alasdair I Houston.  The common currency for behavioral decisions.  _The American Naturalist_ , 127(3):358–378, 1986\.
  * Schmidhuber [1991] Jürgen Schmidhuber.  A possibility for implementing curiosity and boredom in model-building neural controllers.  In _Proc. of the international conference on simulation of adaptive behavior: From animals to animats_ , pages 222–227, 1991.
  * Singh et al. [2009] Satinder Singh, Richard L Lewis, and Andrew G Barto.  Where do rewards come from.  In _Proceedings of the annual conference of the cognitive science society_ , pages 2601–2606. Cognitive Science Society, 2009.

##  Appendix A Convexity conditions

As it is well known, if $h(x)$ is increasing and convex in
$x\in\mathbb{R}^{n}$ and $g_{i}(y)$, $i=1,...,n$ are convex in $y$, then for
$y=\eta y_{a}+(1-\eta)y_{b}$ with $0\leq\eta\leq 1$ we have
$h(g_{1}(y),...,g_{n}(y))\leq h(\eta
g_{1}(y_{a})+(1-\eta)g_{1}(y_{b}),...,\eta
g_{n}(y_{a})+(1-\eta)g_{n}(y_{b}))\leq\eta
h(g_{1}(y_{a}),...,g_{n}(y_{a})+(1-\eta)h(g_{1}(y_{b}),...,g_{n}(y_{b}))$,
where in the first inequality we have used convexity of the $g_{i}$, that is,
$g_{i}(\eta y_{a}+(1-\eta)y_{b})\leq\eta g_{i}(y_{a})+(1-\eta)g_{i}(y_{b})$,
and that $h$ is increasing, and in the second inequality we have used
convexity of $h$.

##  Appendix B Derivation

Here we derive Eq. (24). Starting from the definition of the Lagrangian (12),
we replace the log terms by the critical values of $p(s,a)$ in Eq. (17), which
leads to

$\displaystyle L^{d}(V,\lambda)$ $\displaystyle=$
$\displaystyle\sum_{s,a}p(s,a)\left\\{r(s,a)-\alpha\left(\lambda/\beta-1+(\alpha/\beta-1)\log(\sum_{b}e^{A_{V}(s,b)/\alpha})+A_{V}(s,a)/\alpha\right)\right.\left.\right.$
$\displaystyle\left.-(\beta-\alpha)\left(\lambda/\beta-1+\alpha/\beta\log(\sum_{b}e^{A_{V}(s,b)/\alpha})\right)\right\\}$
$\displaystyle+\sum_{s^{\prime}}V(s^{\prime})\left(\sum_{s,a}p(s^{\prime}|s,a)p(s,a)-\sum_{b}p(s^{\prime},b)\right)$
$\displaystyle=\beta\log Z_{V}\;,$

where we have used the normalization constraint $\sum_{s,a}p(s,a)=1$ in the
first equality, and we have used the definition of $A_{V}(s,a)$, Eq. (15), in
the second one.

##  Appendix C Simulation details

###  C.1 Grid world

#### Environment

The arena is composed of one room having size $3\times 3$ cells and a
"corridor" of size $1\times N$ cells, which is connected to the room at the
middle of its right side (see Fig. 1b).

#### States, Actions and Transitions

The (discrete) state is the position of the cell where the agent stays. The
agent has up to 9 actions: to move to one of the available neighbor cells
around the current location (including diagonal motions), or to stay on the
current position. The position to which it moved becomes its state at the
following time step. Moving through borders is not possible, and thus those
actions are not available in the boundary states.

#### Parameters

To obtain agent’s policy $1000$ iterations as described in section C.2 are
performed before starting simulations. In the performed simulations $\alpha$
was varied from $1$ to $10$ in steps of $1$, and $\beta=10/\alpha$. Each
simulation was ran for $25000$ timesteps, divided into $10$ intervals of
$2500$ timesteps, for each of which the measures under consideration (part of
time spent in the corridor) are obtained, and then we report their average and
error bars based on the standard error from those measurements.

###  C.2 Iteration scheme

Rather than using gradient descent directly of the $V$ over Eq. (33), we
developed an iteration scheme to speed up the search for the optimal policy.
We restrict ourselves to the case of environments with deterministic state
transitions. We empirically show that the algorithm finds a critical point of
the dual function, and thus it provides us with the optimal $p^{*}(s,a)$.

Taking derivatives of the dual function in Eq. (33) with respect to $V$ leads
to the critical point condition (28). Defining
$Q_{s}=\sum_{a}\exp(A_{V}(s,a)/\alpha)$, the derivative with respect to $V(s)$
can be written as

$\sum_{s^{\prime}}(\sum_{a}p(s\left|s^{\prime},a\right.)\exp(A_{V}(s^{\prime},a)/\alpha))Q_{s^{\prime}}^{\alpha/\beta-1}-Q_{s}^{\alpha/\beta}=0$
(47)

Now, we consider a MDP where transitions are deterministic and rewards are
zero everywhere ($r(s,a)=0$). Under the deterministic assumption, there is a
one-to-one mapping between accessible state $s$ and action $a$ from state
$s^{\prime}$, that is, $s=s(s^{\prime},a)$. Therefore Eq. (47) can be
expressed as

$Q_{s}^{\alpha/\beta}=\sum_{s^{\prime}}w_{ss^{\prime}}e^{(V(s)-V(s^{\prime}))/\alpha}Q_{s^{\prime}}^{\alpha/\beta-1}$
(48)

where we have used the notation
$w_{ss^{\prime}}=p(s|s^{\prime},a)\in\\{0,1\\}$ to indicate that the sum over
$s^{\prime}$ will only include terms from where $s$ is a possible successor
state from $s^{\prime}$, and $A_{V}(s^{\prime},a)=V(s)-V(s^{\prime})$ due to
the deterministic transition from $s^{\prime}$ to $s$ after performing the
associated action $a$.

Introducing the notation $z_{s}=\exp(V(s)/\alpha)$, we first note that
$Q_{s}=\sum_{a}\exp(A_{V}(s,a)/\alpha)$ can be written as
$Q_{s}=\sum_{s^{\prime}}w_{s^{\prime}s}z_{s^{\prime}}/z_{s}$, and that Eq.
(48) becomes
$Q_{s}^{\alpha/\beta}=z_{s}\sum_{s^{\prime}}w_{ss^{\prime}}z_{s^{\prime}}^{-1}Q_{s^{\prime}}^{\alpha/\beta-1}$.
Inserting $Q_{s}$ from the first equation into the second, and solving for
$z_{s}$ leads to

$z_{s}=\left(\frac{(\sum_{s^{\prime}}w_{s^{\prime}s}z_{s^{\prime}})^{\alpha/\beta}}{\sum_{s^{\prime}}w_{ss^{\prime}}z_{s^{\prime}}^{-1}Q_{s^{\prime}}^{\alpha/\beta-1}}\right)^{\beta/(\alpha+\beta)}$
(49)

Finally, we transform this fix point condition into an iterative scheme
($n=0,1,...$),

$\displaystyle
Q_{s}^{(n)}=z_{s}^{{(n)}\;-1}\sum_{s^{\prime}}w_{s^{\prime}s}z_{s^{\prime}}^{(n)}$
$\displaystyle
z_{s}^{(n+1)}=\left(\frac{(\sum_{s^{\prime}}w_{s^{\prime}s}z_{s^{\prime}}^{(n)})^{\alpha/\beta}}{\sum_{s^{\prime}}w_{ss^{\prime}}z_{s^{\prime}}^{{(n)}-1}Q_{s^{\prime}}^{(n)\;\alpha/\beta-1}}\right)^{\beta/(\alpha+\beta)}\;.$
(50)

As initial conditions we use $z_{s}^{0}=1$, except for absorbing states, for
which we use $z_{s}^{0}=0$. It is possible to see that for absorbing states,
defined as states where a transition occurs with certainty to itself, we have
that $z_{s}^{n}=0$ for all $n$. Indeed, the $0$ value is stable over
iterations: for $n=1$ we have
$\sum_{s^{\prime}}w_{s^{\prime}s}z_{s^{\prime}}^{0}=w_{ss}z_{s}^{0}=1\times
0=0$ in the numerator Eq. (50), and so on for $n>1$. In addition, for
absorbing states, the value has to be minus infinity, and thus $z_{s}=0$. To
see this, note that $A_{V}(s,a)=V(s)-V(s)=0$ for these states, and therefore
using Eq. (47)
$\sum_{s^{\prime}}\exp(A_{V}(s^{\prime},a)/\alpha)Q_{s^{\prime}}^{\alpha/\beta-1}-Q_{s}^{\alpha/\beta}=\sum_{s^{\prime}\neq
s}\exp(A_{V}(s^{\prime},a)/\alpha)Q_{s^{\prime}}^{\alpha/\beta-1}>0$, so that
Eq. (47) cannot be satisfied by any finite $V_{s}$, and thus we should have
$V(s)\rightarrow-\infty$, and hence $z_{s}=0$ for absorbing states.

We empirically observe that for values $\alpha\leq\beta$ the scheme converges
to the optimal solution, but we also observe that for $\alpha>\beta$ the
scheme diverges. This instability is caused by the negative power
$(1-\alpha/\beta)\frac{\beta}{\alpha+\beta}$ of $z^{(n)}_{s}$, because
$z^{(n)}_{s}$ is contained in $Q^{(n)}_{s^{\prime}}$ in the sum of the
denominator on the right side of Eq. (50). To avoid this, we multiply both
sides of Eq. (49) by $z_{s}^{\frac{\alpha-\beta}{\alpha+\beta}}$ and solve for
$z_{s}$ to obtain the new iteration scheme

$z_{s}^{(n+1)}=\left(\frac{z_{s}^{(n)\;-1+\alpha/\beta}(\sum_{s^{\prime}}w_{s^{\prime}s}z_{s^{\prime}}^{(n)})^{\alpha/\beta}}{\sum_{s^{\prime}}w_{ss^{\prime}}z_{s^{\prime}}^{{(n)}-1}Q_{s^{\prime}}^{(n)\;\alpha/\beta-1}}\right)^{\beta/2\alpha}\;.$
(51)

For $\alpha=\beta$ both schemes coincide, providing a smooth transition
between them.