Policy regularization methods such as maximum entropy regularization are widely used in reinforcement learning to improve the robustness of a learned policy. In this paper, we
unify and extend recent work showing that this robustness arises from hedging against worst-case perturbations of the reward function, which are chosen from a limited set by an implicit adversary.

Using convex duality, we characterize the robust set of adversarial reward perturbations under kl- and $\alpha$-divergence regularization, which includes Shannon and Tsallis entropy regularization as special cases. Importantly,
generalization guarantees can be given within this robust set.   We provide detailed discussion of the worst-case reward perturbations, and present intuitive empirical examples to illustrate this robustness and its relationship with generalization. Finally, we discuss how our analysis complements

previous results on adversarial reward robustness and path consistency optimality conditions.

\[\arraycolsep=.003\textwidth
\begin{array}{cccccc} %[width=40mm]
\begin{subfigure}{0.07\textwidth} \vspace*{-.24cm} \includegraphics[width=\textwidth]
{figs/feasible/uniform_prior.png} \end{subfigure}& %\qquad  \hspace*{.2cm}
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth,  clip]
% {figs/feasible/kl_uniform_01.png}
\caption{ \centering \small $D_{KL}, \beta = 0.1$}\end{subfigure}& % \qquad \hspace*{.2cm}
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth,  clip]
% {figs/feasible/kl_uniform_1.png}
\caption{ \centering  $D_{KL}, \beta = 1$}\end{subfigure}& %\qquad \hspace*{.2cm}
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth,  clip]
% {figs/feasible/kl_uniform_10.png}
\caption{ \centering \small $D_{KL}, \beta = 10$}\end{subfigure}& \rulesep
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth, trim= 0 0 0 0, clip]
% {figs/feasible/alpha-1_no_lambda/alpha_neg1_beta1_uniform.png}
\caption{\centering \small $\alpha = -1, \beta = 10$}\end{subfigure}&
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth, trim= 0 0 0 0, clip]
% {figs/feasible/alpha3_no_lambda/alpha3_beta10_uniform_redo.pdf}
\caption{ \centering \small $\alpha = 3, \beta = 10$}\end{subfigure}
\\ %&\hspace*{.2cm}\\
\begin{subfigure}{0.07\textwidth}\vspace*{-.24cm} \includegraphics[width=\textwidth]{figs/feasible/nonuniform_prior.png}\end{subfigure}& %\qquad \hspace*{.2cm}
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth,  clip]
% {figs/feasible/kl_73_01.png}
\caption{ \centering \small $D_{KL}, \beta = 0.1$}\end{subfigure}& %\qquad \hspace*{.2cm}
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth,  clip]
% {figs/feasible/kl_73_1.png}
\caption{ \centering \small $D_{KL}, \beta = 1$}\end{subfigure}& %\qquad \hspace*{.2cm}
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth,  clip]
% {figs/feasible/kl_73_10.png}
\caption{\centering \small $D_{KL}, \beta = 10$}\end{subfigure}& \rulesep %\hspace*{.2cm}
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth,  clip]
% {figs/feasible/alpha-1_no_lambda/alpha_neg1_beta1_nonuniform.png}
% {figs/feasible/alpha-1_no_lambda/alpha_neg1_beta1_nonuniform_redo.pdf}
\caption{\centering \small $\alpha = -1, \beta = 10$}\end{subfigure}&
\begin{subfigure}{0.175\textwidth}\includegraphics[width=\textwidth,  clip]
% {figs/feasible/alpha3_no_lambda/alpha3_beta10_nonuniform_redo.pdf}
\caption{ \centering \small $\alpha = 3, \beta = 10$}\end{subfigure}
\end{array}
\]

Robust Set (red region) of perturbed reward functions to which a stochastic policy generalizes, in the sense that the policy is guaranteed to achieve an expected modified reward greater than or equal to the value of the regularized objective (<ref>).
The robust set characterizes the perturbed rewards achievable by the adversary. Red stars indicate the worst-case perturbed reward $\mr_{\piopt} = r - \pr_{\piopt}$ (optimal_perturbations).
We show feasible sets

for the optimal $\pi_*(a|s)$ associated with fixed $Q(a,s)=r(a,s)$ values (blue star), where the policy differs based on the regularization parameters $\alpha, \beta, \pi_0$— see <ref>.  The robust set becomes more restricted with decreasing regularization strength (increasing $\beta$), implying decreased generalization.
Importantly, the slope of the boundary of the robust set can be directly linked to the action probabilities under the given policy (see visualizations_feasible).

The shape of the robust set is affected by the choice of $\alpha$-divergence and reference $\pi_0$.

§ INTRODUCTION

Regularization plays a crucial role in various settings across RL,

such as trust-region methods [Peters et al., 2010, Schulman et al., 2015, Schulman et al., 2017, Bas-Serrano et al., 2021], offline learning [Levine et al., 2020, Nachum et al., 2019, Nachum et al., 2019, Nachum & Dai, 2020], multi-task learning [Teh et al., 2017, Igl et al., 2020], and soft
$Q$-learning or actor-critic methods

[Fox et al., 2016, Nachum et al., 2017, Haarnoja et al., 2017, Haarnoja et al., 2018, Grau-Moya et al., 2018].

Various justifications have been given for policy regularization,
such as improved optimization [Ahmed et al., 2019],

connections with probabilistic inference <cit.>,

and robustness to perturbations in the environmental rewards or dynamics [Derman et al., 2021, Eysenbach & Levine, 2021, Husain et al., 2021].

In this work, we use convex duality to

analyze the reward robustness which naturally arises from policy regularization in RL.

In particular, we interpret regularized reward maximization as a two-player game between the agent and an imagined adversary that modifies the reward function.  For a policy $\pi(a|s)$ regularized with a convex function $\Omega(\pi) = \mathbb{E}_{\pi}[\ptReg(\pi)]$

and regularization strength $1/\beta$,

investigate statements of the form

\begin{align}
\hspace*{-.3cm} \max \limits_{\pi(a|s)} \text{\small $(1-\gamma)$}
% \mathbb{E}_{\tau \sim p_\pi(\tau)}
\mathbb{E}_{\taunotation}
\left[ \sum \limits_{t=0}^\infty \gamma^t \bigg( r(a_t, s_t) -  {\frac{1}{\beta}} \ptReg \big(\pi(a_t | s_t)\big) \bigg) \right] = \max \limits_{\pi(a|s)} \min \limits_{r\tick(a,s) \in \feasibleset}  \text{\small $(1-\gamma)$} \mathbb{E}_{\taunotation} \left[ \sum \limits_{t=0}^\infty \gamma^t r\tick(a_t,s_t) \right],
\label{eq:reward_perturbation_stmt}
\end{align}

indicates a modified reward function chosen
from an appropriate robust set $\feasibleset$ (see related-<ref>).

<ref> suggests that an agent may translate uncertainty in its estimate of the reward function into regularization of a learned policy, which is particularly relevant in applications such as inverse RL [Ng et al., 2000, Arora & Doshi, 2021] or learning from human preferences [Christiano et al., 2017].

Robust set $\feasibleset$ (red region) of perturbed reward functions to which a stochastic policy generalizes, in the sense of <ref>.

Red star indicates the worst-case perturbed reward $\mroptpi = r - \proptpi$ (optimal_perturbations) chosen by the adversary.
The robust set also characterizes the set of reward perturbations $\pr(a,s)$ that are feasible for the adversary, which differs based on the choice of regularization function, regularization strength $\beta$, and reference distribution $\pi_0$ (see visualizations_feasible and feasible_set_main).  We show the robust set for the optimal single-step policy with value estimates $Q(a,s) = r(a,s)$ and kl divergence regularization to a uniform $\pi_0$, with $\beta = 1$.

Our robust set is larger and has a
different shape

compared to the

robust set of Derman et al., 2021 (dotted lines, see related).

This reward robustness further implies that
regularized policies achieve a form of `zero-shot' generalization to new environments where the reward is adversarially chosen.

In particular, for any given $\pi(a|s)$ and a modified reward $\mr \in \feasibleset$
within the corresponding robust set,

we obtain the following performance guarantee

\begin{equation}
\hspace*{-.2cm}
%  \text{\small $(1-\gamma)$}
%  \resizebox{.925\columnwidth}{!}{$
\mathbb{E}
%  _{\pi(\tau)}
\left[ \sum \limits_{t=0}^\infty \gamma^t r\tick(a_t,s_t) \right] \geq
%  \text{\small $(1-\gamma)$}
\mathbb{E}
%  _{\pi(\tau)}
\left[ \sum \limits_{t=0}^\infty \gamma^t \bigg( r(a_t, s_t) - {\frac{1}{\beta}} \ptReg
\big(\pi_t \big) \bigg) \right] .
%  \big(\pi(a_t | s_t)\big) \bigg) \right]
% $
\label{eq:generalization}
% }
\end{equation}

<ref> states that the expected modified reward under $\pi(a|s)$, with $\mr \in \feasibleset$ as in related, will be greater than the value of the regularized objective with the original, unmodified reward.
It is in this particular sense that we
make claims about robustness and zero-shot generalization throughout the paper.

Our analysis unifies

recent work exploring similar interpretations [Ortega & Lee, 2014, Husain et al., 2021, Eysenbach & Levine, 2021, Derman et al., 2021]

as summarized in discussion and novelty.

Our contributions include

* A thorough analysis of the robustness associated with and $\alpha$-divergence policy regularization, which includes popular Shannon entropy regularization

as a special case.  Our derivations for the $\alpha$-divergence generalize the Tsallis entropy RL framework of Lee et al., 2019.

* We derive the worst-case reward perturbations $\prpi = r - \mr_{\pi}$ corresponding to any stochastic policy $\pi$ and a fixed regularization scheme (optimal_perturbations).

* For the optimal regularized policy in a given environment, we show that the corresponding worst-case reward perturbations

match the advantage function for any $\alpha$-divergence.
We relate this finding to the path consistency optimality condition, which has been used to construct learning objectives in [Nachum et al., 2017, Chow et al., 2018], and a game-theoretic indifference condition,
which occurs at a Nash equilibrium between the agent and adversary [Ortega & Lee, 2014].

* We visualize the set  $\feasibleset$ of adversarially perturbed rewards against which a regularized policy is robust in related-<ref>, with details in feasible.

Our use of divergence instead of entropy regularization to analyze the robust set

clarifies several unexpected conclusions from previous work.   In particular,
similar plots in
Eysenbach & Levine, 2021
suggest that

MaxEnt rl is not robust to the reward function of the training environment, and that increased regularization strength may hurt robustness.  Our analysis in entropy_vs_div and  eysenbach establishes the expected, opposite results.

* We perform experiments for a sequential grid-world task in visualizations where, in contrast to previous work, we explicitly visualize the reward robustness and adversarial strategies resulting from our theory.

We use the path consistency or indifference conditions to certify optimality of the policy.

Ortega & Lee, 2014     Eysenbach & Levine, 2021       Husain et al., 2021      Derman et al., 2021     Ours
Multi-Step Analysis

Worst-Case $\pr(a,s)$     policy form     policy form     value form     policy (via dual lp <ref>)     policy $\&$ value forms

Robust Set
(see our eysenbach)          (flexible specification)

Divergence Used     KL ($\alpha = 1$)      Shannon entropy (entropy_vs_div)     any convex $\Omega$     derived from robust set

any convex $\Omega$, $\alpha$-Div examples

$\mu(a,s)$ or $\pi(a|s)$ Reg.?

$\pi(a|s)$     Both      $\pi(a|s)$     Both

Path Consistency

tableComparison to related work.

§ PRELIMINARIES

In this section, we review

LP formulations of
discounted MDP and extensions to convex policy regularization.

Notation For a finite set $\mathcal{\myset}$, let $\mathbb{R}^{\mathcal{\myset}}$ denote the space of real-valued functions over $\mathcal{\myset}$, with $\mathbb{R}_+^{\mathcal{\myset}}$ indicating restriction to non-negative functions.  We let $\Delta^{|\mathcal{\myset}|}$ denote the probability simplex with dimension equal to the cardinality of $\mathcal{\myset}$.

For $ \mu, q \in \mathbb{R}^{\mathcal{\myset}}$,

$\langle \mu , q \rangle = \sum_{x \in \mathcal{\myset}} \mu(x) q(x)$ indicates the inner product in Euclidean space.

§.§ Convex Conjugate Function

We begin by reviewing the convex conjugate function, also known as the Legendre-Fenchel transform, which will play a crucial role throughout our paper.

For a convex function $\Omega(\primalvar)$ which, in our context, has domain $\primalvar \in \mudomainconj$,

the conjugate function $\Omega^{*}$ is defined via the optimization

\begin{align}
\Omega^{*}( \dualvar ) = \sup \limits_{\primalvar \in
\mudomainconj
% \mathcal{D}
} \, \big \langle \primalvar, \dualvar \big \rangle - \Omega(\primalvar), \label{eq:conjstar}
\end{align}

where $\dualvar \in \rprimedomainconj$.

The conjugate operation is an involution for proper, lower semi-continuous, convex $\Omega$ [Boyd & Vandenberghe, 2004],

so that $(\Omega^{*})^{*} = \Omega$ and $\Omega^{*}$ is also convex.
We can thus represent $\Omega(\primalvar)$ via a conjugate optimization

\begin{align}
\Omega(\primalvar) = \sup_{\dualvar \in
\rprimedomainconj}
%  \dualdomain}
\big \langle \primalvar, \dualvar \big \rangle - \Omega^{*}(\dualvar). \label{eq:conjomega}
\end{align}

Differentiating with respect to the optimization variable in <ref> or (<ref>) suggests the optimality conditions

\begin{align}
\primalvar_{\dualvar} = \nabla \Omega^{*}( \dualvar )   \quad \qquad \dualvar_{\primalvar} = \nabla \Omega(\primalvar) \, .     \label{eq:optimal_policy_as_grad}
\end{align}

Note that the above conditions also imply relationships of the form $\primalvar_{\dualvar} = (\nabla \Omega)^{-1}(\dualvar)$.   This dual correspondence between

values of $\primalvar$ and $\dualvar$ will form the basis of our adversarial interpretation in adversarial_perturb.

§.§ Divergence Functions

We are interested in the conjugate duality associated with
policy regularization, which is often expressed using a
statistical divergence $\Omega(\mu)$ over a joint density $\mu(a,s) = \mu(s) \pi(a|s)$ (see mdp_background).

In particular, we consider
the family of $\alpha$-divergences [Amari, 2016, Cichocki & Amari, 2010], which includes both the forward and reverse kl divergences as special cases.
In the following, we consider extended divergences that accept unnormalized density functions as input [Zhu & Rohwer, 1995]
so that we may

analyze function space dualities and evaluate Lagrangian relaxations without

onto the probability simplex.

KL Divergence

The `forward' kl divergence to a reference policy $\pi_0(a|s)$ is commonly used for policy regularization in RL.
Extending the input domain to unnormalized measures, we write the divergence as

\begin{align}
&\Omega_{\pi_0}(\mu) = \mathbb{E}_{\mu(s)}\Big[D_{KL}[\pi:\pi_0]\Big] = \sum \limits_{s \in \mathcal{S}} \mu(s) \sum \limits_{a \in \mathcal{A}}  \left(\pi(a|s)  \log \frac{\pi(a|s)}{\pi_0(a|s)} -
% \sum \limits_{a, s}
\pi(a|s)
% \sum \limits_{a,s}
\pi_0(a|s)\right). \label{eq:kl_def}
\end{align}

Using a uniform reference  $\pi_0(a|s) = 1$ $\forall
\, (a,s)$, we recover the Shannon entropy up to an additive constant.

$\alpha$-Divergence The $\alpha$-divergence $\mathbb{E}_{\mu(s)}\big[D_{\alpha}[\pi_0:\pi]\big]$ over possibly unnormalized measures

is defined as

\begin{align}
\hspace*{-.1cm}
\Omega^{(\alpha)}_{\pi_0}(\mu)& =
% \mathbb{E}_{\mu(s)}\big[
% D_{\alpha}[\pi_0:\pi]
% \big]
% &=
\frac{1}{\alpha(1-\alpha)}
% \sum \limits_{s \in \mathcal{S}}
\sum \limits_{s \in \mathcal{S}}
\mu(s)
\bigg( (1-\alpha)
% \sum \limits_{a \in \mathcal{A}}
\sum \limits_{a \in \mathcal{A}}
\pi_0(a|s)
% \\ &\phantom{\sum \limits_{s \in \mathcal{S}}\mu(s)}
+ \alpha
% \sum \limits_{a \in \mathcal{A}}
\sum \limits_{a \in \mathcal{A}}
\pi(a|s)
% \nonumber
% &- \sum \limits_{a \in \mathcal{A}}
% \\ &\phantom{\sum \limits_{s} \mu(s)}
- \sum \limits_{a \in \mathcal{A}}
\pi_0(a|s)^{1-\alpha} \pi(a|s)^{\alpha} \bigg)
% \label{eq:alpha_def}
\label{eq:alpha_def}
\end{align}

Taking the limiting behavior, we recover the `forward' kl divergence $D_{KL}[\pi:\pi_0]$ as $\alpha \rightarrow 1$ or the `reverse' kl divergence $D_{KL}[\pi_0:\pi]$ as $\alpha \rightarrow 0$.

To provide intuition for

the $\alpha$-divergence, we define the deformed $\alpha$-logarithm as in Lee et al., 2019, which matches Tsallis's $q$-logarithm [Tsallis, 2009] for $\alpha = 2-q$.  Its inverse is the $\alpha$-exponential, with

\begin{align}
\log_{\alpha}(u) &=  \frac{1}{\alpha-1} \left( u^{\alpha-1}-1 \right) \, ,
% \label{eq:qlog}
\qquad \qquad
\exp_{\alpha}(u) = [1 + (\alpha-1) \, u ]_+^{\frac{1}{\alpha-1}} \, . \label{eq:qexp}
% \hfill \, \,  \alpha \neq 1 \
\end{align}

where $[\cdot]_+ = \max(\cdot,0)$ ensures fractional powers can be taken and suggests that $\exp_{\alpha}(u)=0$ for $u \leq 1/(1-\alpha)$.

Using the $\alpha$-logarithm, we can rewrite the $\alpha$-divergence

similarly to
the divergence in

\begin{align}
\Omega^{(\alpha)}_{\pi_0}(\mu) &= \frac{1}{\alpha} \sum \limits_{s \in \mathcal{S}} \mu(s) \bigg( \sum \limits_{a \in \mathcal{A}} \pi(a|s) \log_{\alpha}\frac{\pi(a|s)}{\pi_0(a|s)} - \pi(a|s) + \pi_0(a|s) \bigg) \nonumber.
\end{align}

For a uniform reference $\pi_0$, the $\alpha$-divergence
differs from the Tsallis entropy by only the $1/\alpha$ factor and an additive constant (see tsallis).

§.§ Unregularized MDPs

A discounted MDP is a tuple $\{ \mathcal{S}, \mathcal{A}, P, \nu_0, r, \gamma \}$ consisting of a state space $\mathcal{S}$, action space $\mathcal{A}$, transition dynamics $P(s\tick|s,a)$ for $s, s\tick \in \mathcal{S}$, $a \in \mathcal{A}$, initial state distribution $\nu_0(s) \in \Delta^{|\mathcal{S}|}$ in the probability simplex, and reward function $r(a,s):\mathcal{S} \times \mathcal{A} \mapsto \mathbb{R}$.   We also use a discount factor $\gamma\in (0,1)$
(Puterman, 1994 Sec 6).

We consider an agent that seeks to maximize the expected discounted reward by acting according to a decision policy

$\pi(a|s) \in \Delta^{|\mathcal{A}|}$  for each $ s \in \mathcal{S}$.
The expected reward is calculated over trajectories ${\tau \sim \pi(\tau):= \nu_0(s_0) \prod \pi(a_t | s_t) P(s_{t+1} | s_t, a_t)}$, which begin from an initial $s_0 \sim \nu_0(s)$ and evolve according to the policy $\pi(a|s)$ and MDP dynamics $P(s\tick|s,a)$

\begin{align}
\hspace*{-.2cm}
\obj(r) :=
\max \limits_{\pi(a|s)} \, (1-\gamma) \, \mathbb{E}_{\tau \sim \pi(\tau)} \bigg[ \sum \limits_{t=0}^{\infty} \gamma^t \, r(s_t, a_t)  \bigg] \, . \label{eq:policy_only}
\end{align}

We assume that the policy is stationary and Markovian, and thus independent of both the timestep and trajectory history.

Linear Programming Formulation

We will focus on
a linear programming (LP) form for the objective in <ref>, which is common in the literature on convex duality.

With optimization over the discounted
state-action occupancy measure,

${\mu(a,s) \coloneqq (1-\gamma)} \mathbb{E}_{\tau\sim \pi(\tau)} \left[ \sum_{t=0}^\infty \gamma^t \, \mathbb{I}(a_t = a, s_t = s)\right]$,
we rewrite

the objective as

\begin{align}
\hspace*{-.23cm}
\obj(r) \coloneqq
\max \limits_{\mu(a,s)} \big \langle {\mu(a,s)}, {r(a,s)} \big \rangle \qquad \text{subject to } \quad \mu(a,s) &\geq 0 \qquad \forall (a,s) \in \mathcal{A} \times \mathcal{S},   \quad  \label{eq:primal_lp} \\
\sum_{a} \mu(a,s)& = (1-\gamma) \nu_0(s) + \gamma \sum_{a\tick, s\tick} P(s|a\tick, s\tick) \mu(a\tick,s\tick) \qquad \forall s \in \mathcal{S}, \nonumber
%\left( \forall s \in \mathcal{S} \right)
%\, \forall s \in \mathcal{S}\nonumber
\end{align}

\begin{align}
\hspace*{-.23cm}
\obj(r) \coloneqq
\max \limits_{\mu} \big \langle {\mu, r} \big \rangle \qquad \text{subject to } \quad \mu(a,s) &\geq 0 \qquad \forall (a,s) \in \mathcal{A} \times \mathcal{S},   \quad  \label{eq:primal_lp} \\
\sum_{a} \mu(a,s)& = (1-\gamma) \nu_0(s) + \gamma \sum_{a\tick, s\tick} P(s|a\tick, s\tick) \mu(a\tick,s\tick) \qquad \forall s \in \mathcal{S} \nonumber.
%\left( \forall s \in \mathcal{S} \right)
%\, \forall s \in \mathcal{S}\nonumber
\end{align}

We refer to the constraints in the second line of <ref> as the Bellman flow constraints, which force $\mu(a,s)$ to respect the MDP dynamics.

We denote the set of feasible $\mu$ as $\mathcal{M} \subset \mudomainfn$.    For normalized $\nu_0(s)$ and $P(s|a\tick, s\tick)$,   we show in optimal_policy that $\mu(a,s) \in \mathcal{M}$ implies $\mu(a,s)$

is normalized.

It can be shown that any feasible $\mu(a,s) \in \mathcal{M}$  induces a stationary $\pi(a|s) = \mu(a,s) /
\mu(s)$,

where  $\mu(s) \coloneqq \sum_{a\tick} \mu(a\tick,s)$ and $\pi(a|s) \in \Delta^{|\mathcal{A}|}$ is normalized by definition.

Conversely, any stationary policy $\pi(a|s)$ induces a unique state-action visitation distribution $\mu(a,s)$ (Syed et al., 2008,
Feinberg & Shwartz, 2012 Sec. 6.3).

Along with the definition of $\mu(a,s)$ above,

this result demonstrates
the equivalence of the optimizations in <ref> and <ref>.  We will proceed with the LP notation from <ref> and assume $\mu(s)$ is induced by

$\pi(a|s)$ whenever the two appear together in an expression.

Importantly, the flow constraints in <ref> lead to a dual optimization which reflects the familiar Bellman equations [Bellman, 1957].
To see this, we introduce Lagrange multipliers
$V(s)$ for each flow constraint and $\lambdaplus \geq 0$ for the nonnegativity constraints.
$V \in \mathbb{R}^{\mathcal{S}}$ for each flow constraint and $\lambdaplus \in \mathbb{R}_+^{\mathcal{A} \times \mathcal{S}}$ for the nonnegativity constraints.
Summing over $s \in \mathcal{S}$, and eliminating $\mu(a,s)$ by setting $d/d\mu(a,s) = 0$ yields the dual LP

\begin{align}
\hspace*{-.2cm} \obj^{*}(r)&\coloneqq
\min \limits_{V(s), \lambdaplus} \,
%   \min \limits_{V(s)} \,
(1-\gamma) \big \langle \nu_0(s), V(s) \big \rangle
%   \\
%   \text{  subj to: }\label{eq:dual_lp} \\ %\quad \forall (a,s) \in \mathcal{S} \times \mathcal{A}
\quad \text{  subject to } \,\,\, V(s) = r(a,s) + \gamma \transitionv + \lambdaplus
%  \quad \forall (a,s) \in \mathcal{A} \times \mathcal{S}
\label{eq:dual_lp} ,
%  \nonumber \, ,
\end{align}

\begin{align}
\hspace*{-.2cm} \obj^{*}(r)&\coloneqq
\min \limits_{V, \lambda} \,
%   \min \limits_{V(s)} \,
(1-\gamma) \big \langle \nu_0, V \big \rangle
%   \\
%   \text{  subj to: }\label{eq:dual_lp} \\ %\quad \forall (a,s) \in \mathcal{S} \times \mathcal{A}
\quad \text{  subject to } \,\,\, V(s) = r(a,s) + \gamma \transitionv + \lambdaplus
\quad \forall (a,s) \in \mathcal{A} \times \mathcal{S}
\label{eq:dual_lp} ,
%  \nonumber \, ,
\end{align}

where we have used $\transitionv$ as shorthand for $\mathbb{E}_{P(s\tick|a,s)}[ V(s\tick)]$ and reindexed the transition tuple from $(s\tick, a\tick, s)$ to $(s,a, s\tick)$ compared to <ref>.   Note that the constraint applies for all $(a,s) \in \mathcal{A} \times \mathcal{S}$ and that $\lambdaplus \geq 0$.  By complementary slackness,

we know that $\lambdaplus =0$ for $(a,s)$ such that $\mu(a,s) > 0$.

§.§ Regularized MDPs

We now consider regularizing the objective in <ref> using a convex penalty function $\Omega(\mu)$ with coefficient $1/\beta$.
We primarily focus on regularization using a conditional divergence $\Omega_{\pi_0}(\mu) \coloneqq \mathbb{E}_{\mu(s)\pi(a|s)}[\ptReg(\pi)]$ between the policy and a normalized reference distribution $\pi_0(a|s)$, as in divergence_intro and [Ortega & Braun, 2013, Fox et al., 2016, Haarnoja et al., 2017, Haarnoja et al., 2018].
We also use the notation $\Omega_{\mu_0}(\mu) = \mathbb{E}_{\mu(a,s)}[\ptReg(\mu)]$ to indicate regularization of the full state-action occupancy measure to a normalized reference $\mu_0(a,s)$,  which appears, for example, in REPS [Peters et al., 2010, Belousov & Peters, 2019].

The regularized objective $\obj_{\Omega, \beta}(r)$ is then defined as

\begin{equation}
% \resizebox{.87\columnwidth}{!}{ \hspace*{-.2cm}   $
\obj_{\Omega, \beta}(r) :=  \max \limits_{\mu(a,s) \in \mathcal{M} } %\max \limits_{\pi(a|s) \in \Delta^{|A|}}
\blangle \mu(a,s), r(a,s) \brangle - \dfrac{1}{\beta}   \Omega_{\pi_0}(\mu)
%   $
%   }
\label{eq:primal_reg}
\end{equation}

\begin{equation}
% \resizebox{.87\columnwidth}{!}{ \hspace*{-.2cm}   $
\obj_{\Omega, \beta}(r) :=  \max \limits_{\mu \in \mathcal{M} } %\max \limits_{\pi(a|s) \in \Delta^{|A|}}
\blangle \mu, r \brangle - \dfrac{1}{\beta}   \Omega_{\pi_0}(\mu)
%   $
%   }
\label{eq:primal_reg}
\end{equation}

where $\Omega_{\pi_0}(\mu)$ contains an expectation under $\mu(a,s)$ as in <ref>-(<ref>).
We can also derive a dual version of the regularized LP,
by first writing the Lagrangian relaxation of <ref>

\begin{align}
%   \mathcal{L}:=
\max \limits_{\mu(a,s)} \min \limits_{V(s), \lambdaplus}  \,
(1-\gamma) \big\langle \nu_0(s), V(s) \big  \rangle
+ &\langle \mu(a,s), r(a,s) + \gamma \transitionv -V(s) + \lambdaplus \rangle - \frac{1}{\beta} \Omega_{\pi_0}(\mu)  \label{eq:dual_lagrangian}
\end{align}

\begin{align}
%   \mathcal{L}:=
\max \limits_{\mu} \min \limits_{V, \lambda}  \,
(1-\gamma) \big\langle \nu_0, V \big  \rangle
+ &\, \langle \mu, r + \gamma \transitionvinds -V + \lambda \rangle - \frac{1}{\beta} \Omega_{\pi_0}(\mu) . \label{eq:dual_lagrangian}
\end{align}

Swapping the order of optimization

strong duality, we can recognize the
maximization over ${\mu(a,s)}$ as a conjugate function $\frac{1}{\beta}\Omega^{*}_{\pi_0, \beta}$, as in <ref>, leading to a regularized dual optimization

\begin{align}
\hspace*{-.2cm} &  \obj_{\Omega, \beta}^{*}(r) =
%  \min \limits_{V(s)}
\min \limits_{V(s), \lambdaplus}
%\max \limits_{ \mu(s) \rightarrow \mathcal{M}}
\,  (1-\gamma) \big\langle \nu_0(s), V(s) \big  \rangle  + \frac{1}{\beta}\Omega^{*}_{\pi_0, \beta} \bigg(r(a,s) +  \gamma \transitionv -V(s) + \lambdaplus \bigg)\label{eq:dual_reg}
%  &+ \mathbb{E}_{\mu(s)} \bigg[\, \frac{1}{\beta}\Omega^{*}_{\pi_0, \beta} \bigg(r(a,s) +  \gamma \transitionv -V(s) \bigg)  \bigg] \nonumber
\end{align}

\begin{align}
\hspace*{-.2cm} &  \obj_{\Omega, \beta}^{*}(r) =
%  \min \limits_{V(s)}
\min \limits_{V, \lambda}
%\max \limits_{ \mu(s) \rightarrow \mathcal{M}}
\,  (1-\gamma) \big\langle \nu_0, V \big  \rangle  + \frac{1}{\beta}\Omega^{*}_{\pi_0, \beta} \Big(r  +  \gamma \transitionvinds -V + \lambda \Big)\label{eq:dual_reg}
%  &+ \mathbb{E}_{\mu(s)} \bigg[\, \frac{1}{\beta}\Omega^{*}_{\pi_0, \beta} \bigg(r(a,s) +  \gamma \transitionv -V(s) \bigg)  \bigg] \nonumber
\end{align}

which involves optimization over dual variables $V(s)$ only and is unconstrained, in contrast to <ref>.

Dual objectives of this form

in [Nachum & Dai, 2020, Belousov & Peters, 2019, Bas-Serrano et al., 2021, Neu et al., 2017].
We emphasize the need to include the Lagrange multiplier $\lambdaplus$, with $\lambdaplus > 0$ when the optimal policy has $\piopt(a|s) = 0$, since an important motivation for $\alpha$-divergence regularization is to encourage sparsity in the policy (see <ref>, Lee et al., 2018, Lee et al., 2019, Chow et al., 2018).

Soft Value Aggregation
In iterative algorithms such as (regularized) modified policy iteration [Puterman & Shin, 1978, Scherrer et al., 2015], it is useful to consider the regularized Bellman optimality operator [Geist et al., 2019].   For given estimates of the state-action value $Q(a,s) \coloneqq r(a,s) + \gamma \transitionv$, the operator $\mathcal{T}^{*}_{\Omega_{\pi_0, \beta}}$ updates $V(s)$ as

\begin{align}
\hspace*{-.2cm} V(s)  \leftarrow \frac{1}{\beta} \Omega^{*}_{\pi_0,\beta}(Q) = \max \limits_{\pi \in \Delta^{|\mathcal{A}|}} \blangle \pi(a|s), Q(a,s) \brangle - \frac{1}{\beta} \Omega_{\pi_0}(\pi) \label{eq:soft_value}
\end{align}

\begin{align}
\hspace*{-.2cm} V(s)  \leftarrow \frac{1}{\beta} \Omega^{*}_{\pi_0,\beta}(Q) = \max \limits_{\pi \in \Delta^{|\mathcal{A}|}} \blangle \pi, Q \brangle - \frac{1}{\beta} \Omega_{\pi_0}(\pi) \label{eq:soft_value} .
\end{align}

Note that this conjugate optimization is performed in each state $s \in \mathcal{S}$ and explicitly constrains each $\pi(a|s)$ to be normalized.
Although we proceed with the notation of <ref> and <ref>, our later developments

are compatible with the

`soft-value aggregation' perspective above.  See soft_value for detailed discussion.

1c  Divergence
1cConjugate Expression
Optimizing Argument ($\pi_{\pr}$ or $\mu_{\pr}$)

$\frac{1}{\beta} \KL[\pi:\pi_0]$     $\frac{1}{\beta} \Omega^{*}_{\pi_0,\beta}(\pr)$

$\frac{1}{\beta} \sum \limits_{a}
\pi_0(a|s) \expof{\beta \cdot \pr(a,s)} -
%  \sum \limits_{a \in \mathcal{A}}
\frac{1}{\beta} $

$ \pi_0(a|s) \expof{\beta \cdot \pr(a,s)}$

$\frac{1}{\beta} \KL[\mu:\mu_0]$     $\frac{1}{\beta} \Omega^{*}_{\mu_0,\beta}(\pr)$

$\frac{1}{\beta} \sum \limits_{a,s}
% \in \mathcal{A}
%  \sum \limits_{a,s \in \mathcal{A}, \mathcal{S}}
\mu_0(a,s) \expof{\beta \cdot \pr(a,s)} -
\frac{1}{\beta} $

$ \mu_0(a,s) \expof{\beta \cdot \pr(a,s)}$

$\frac{1}{\beta} D_{\alpha}[\pi_0:\pi]$     $\frac{1}{\beta} \Omega^{*(\alpha)}_{\pi_0,\beta}(\pr)$

$\frac{1}{\beta} \frac{1}{\alpha}  \sum \limits_{a} \pi_0(a|s) \exp_{\alpha}\big\{ \beta \cdot \big( \pr(a,s) - \myconst \big) \big\}^{\alpha} - \frac{1}{\beta} \frac{1}{\alpha} +   \psi_{\pr}(s;\beta)  $

$\pi_0(a|s) \exp_{\alpha} \big\{\beta \cdot \left(  \pr(a,s) - \psi_{\pr}(s;\beta)  \right) \big\}$

$\frac{1}{\beta} D_{\alpha}[\mu_0:\mu]$     $\frac{1}{\beta} \Omega^{*(\alpha)}_{\mu_0,\beta}(\pr)
$\frac{1}{\beta} \frac{1}{\alpha} \sum \limits_{a,s} \mu_0(a,s) \exp_{\alpha}\big\{ \beta \cdot \pr(a,s) \big\}^{\alpha} - \frac{1}{\beta} \frac{1}{\alpha}$

$\mu_0(a,s) \exp_{\alpha} \big\{ \beta \cdot \pr(a,s) \big\} $

tableConjugate Function expressions for kl and $\alpha$-divergence regularization of either the policy $\pi(a|s)$ or occupancy $\mu(a,s)$.  See conj1-<ref> for derivations.  The final column shows the optimizing argument in the definition of the conjugate function $\frac{1}{\beta}\Omega^{*}(\pr)$, for example
$\mu_{\pr} \coloneqq \argmax_{\mu} \langle \mu, \pr \rangle -\frac{1}{\beta}\Omega_{\mu_0}(\mu)$.

Note that each conjugate expression for $\pi(a|s)$ regularization also contains an outer expectation over $\mu(s)$.

§ ADVERSARIAL INTERPRETATION

In this section, we interpret regularization as implicitly providing robustness to adversarial perturbations of the reward function.  To derive our adversarial interpretation, recall from <ref> that conjugate duality yields an alternative representation of the regularizer

\begin{equation}
\hspace*{-.2cm}
% \resizebox{.9\columnwidth}{!}{
% $
%       $\omegamu = \max \limits_{\prpi(a,s)} \langle \mu(a,s), \prpi(a,s) \rangle - \alphaconj(\prpi) .$
%      \label{eq:conjomega2} }
\omegamu = \max \limits_{\prinit(a,s)} \langle \mu(a,s), \prinit(a,s) \rangle - \alphaconj(\prinit) . \label{eq:conjomega2}
%  $}
\end{equation}

\begin{equation}
\hspace*{-.2cm}
\omegamu = \max \limits_{\prinit \in \rprimedomain} \, \langle \mu, \prinit \rangle - \alphaconj(\prinit) . \label{eq:conjomega2}
%  $}
\end{equation}

Using this conjugate optimization to expand the regularization term in the primal objective of <ref>,

\begin{equation}
\hspace*{-.2cm}
% \resizebox{.9\columnwidth}{!}{$
\obj_{\Omega, \beta}(r) = \max \limits_{\mu \in \mathcal{M}}  \min \limits_{\textcolor{\highlight}{\prinit(a,s)}}
\langle {\mu(a,s)}, {r(a,s) - \textcolor{\highlight}{\prinit(a,s)}} \rangle  + \alphaconj \big( \textcolor{\highlight}{\prinit} \big) .
% $
%   \nonumber
% }
\label{eq:pedro_form}
\end{equation}

\begin{equation}
\hspace*{-.2cm}
% \resizebox{.9\columnwidth}{!}{$
\obj_{\Omega, \beta}(r) = \max  \limits_{\mu \in \mathcal{M}}  \min \limits_{\textcolor{\highlight}{\prinit \in \rprimedomain}}
\, \langle {\mu}, {r - \textcolor{\highlight}{\prinit}} \rangle  + \alphaconj \big( \textcolor{\highlight}{\prinit} \big) .
% $
%   \nonumber
% }
\label{eq:pedro_form}
\end{equation}

We interpret

as a two-player minimax game between an agent and an implicit adversary, where the agent chooses an occupancy measure $\mu(a,s) \in \mathcal{M}$ or its corresponding policy $\pi(a|s)$,

the adversary chooses reward perturbations $\prinit(a,s)$

subject to the convex
conjugate $\alphaconj(\prinit)$ as a penalty function [Ortega & Lee, 2014].

To understand the limitations this penalty imposes on the adversary, we transform the optimization over $\pr$
in <ref>
to a constrained optimization in generalization.  This allows us to characterize the feasible set of

reward perturbations
available to the adversary or, equivalently, the set of modified rewards $\mr(a,s) \in \feasibleset$ to which a particular stochastic policy is robust.
In any_policy and <ref>, we
interpret the worst-case adversarial perturbations corresponding to an arbitrary stochastic policy and the optimal policy, respectively.

§.§ Robust Set of Modified Rewards

In order to link our adversarial interpretation to robustness and zero-shot generalization as in

we characterize the feasible set of reward perturbations in the following proposition.
We state our proposition for policy regularization, and discuss differences for $\mu(a,s)$ regularization in mu_feasible.

Assume a normalized policy $\pi(a|s)$ for the agent is given, with $\sum_a \pi(a|s) = 1 \, \forall s \in \mathcal{S}$.   Under $\alpha$-divergence policy regularization to a normalized reference $\pi_0(a|s)$,

the optimization over $\pr(a,s)$ in <ref> can be written in the following constrained form

\begin{align}
\min \limits_{\pr(a,s) \in \mathcal{R}^{\Delta}_{\pi}} \blangle \mu(a,s), r(a,s) - \pr(a,s)\brangle \qquad \text{where} \quad
% \alphaconjmu(\pr)
\mathcal{R}^{\Delta}_{\pi} \coloneqq \left\{ \prrob(a,s) \in  \textcolor{red}{\mathcal{F}} \, \bigg| \,
\Omega^{*(\alpha)}_{\pi_0,\beta}(\prrob) \leq 0 \right\} ,
% \alphaconj(\prrob) \leq 0 \right\} ,
% \alphaconj(\pr)\leq 0
\label{eq:alpha_feasible}
% \\\frac{\alpha-1}{\alpha} \langle \mu(s) \pi^{(\pr)}_*(a|s), \pr \rangle - \frac{1}{\alpha}(V^{\pr}_*(s)  \leq 0 \label{eq:alpha_feasible}
\end{align}

\begin{align}
\min \limits_{\pr \in \mathcal{R}^{\Delta}_{\pi}} \blangle \mu, r - \pr \brangle \qquad \text{where} \quad
% \alphaconjmu(\pr)
\mathcal{R}^{\Delta}_{\pi} \coloneqq \left\{ \prrob \in \rprimedomain  \, \bigg| \,
\Omega^{*(\alpha)}_{\pi_0,\beta}(\prrob) \leq 0 \right\} ,
% \alphaconj(\prrob) \leq 0 \right\} ,
% \alphaconj(\pr)\leq 0
\label{eq:alpha_feasible}
% \\\frac{\alpha-1}{\alpha} \langle \mu(s) \pi^{(\pr)}_*(a|s), \pr \rangle - \frac{1}{\alpha}(V^{\pr}_*(s)  \leq 0 \label{eq:alpha_feasible}
\end{align}

We refer to $\mathcal{R}^{\Delta}_{\pi} \subset \rprimedomain$ as the feasible set of reward perturbations available to the adversary.   This translates to a robust set $\feasibleset$ of modified rewards $\mr(a,s) = r(a,s) - \prrob(a,s)$
for the given policy.

These sets depend on the $\alpha$-divergence and regularization strength $\beta$ via the conjugate function.

For kl divergence regularization, the constraint is

\begin{align}
\sum\limits_{a \in \mathcal{A}} \pi_0(a|s) \expof{\beta \cdot \prrob(a,s)} \leq 1 \, . \label{eq:kl_feasible}
\end{align}

See pf_feasible for proof, and conj_table for the convex conjugate function $\alphaconj(\prrob)$ associated with various regularization schemes.
The proof proceeds by evaluating the conjugate function at the minimizing argument $\prpi$ in <ref> (see any_policy), with $\Omega^{*(\alpha)}_{\pi_0,\beta}(\propt)=0 \, \forall \alpha$ for normalized $\pi(a|s)$ and $\pi_0(a|s)$.
The constraint

then follows from the fact that $\Omega^{*(\alpha)}_{\pi_0,\beta}(\propt)$ is convex and increasing in $\pr$ [Husain et al., 2021].

We visualize the robust set for a two-dimensional action space in feasible_set_main, with additional discussion in visualizations_feasible.

As in <ref>,
we can provide `zero-shot' performance guarantees using this set of modified rewards.

For any perturbed reward in the robust set $\mr(a,s) \in \feasibleset$,
we have $\langle \mu(a,s), \mr(a,s) \rangle \geq \langle \mu(a,s), r(a,s) \rangle - \omegamu$,
For any perturbed reward in the robust set $\mr \in \feasibleset$,
we have $\langle \mu, \mr \rangle \geq \langle \mu, r \rangle - \omegamu$,
so that the policy achieves an expected modified reward which is at least as large as the regularized objective.

However, notice that this
form of robustness is sensitive to the exact value of the

regularized objective function.

Although entropy regularization and divergence regularization with a uniform reference
induce the same optimal $\mu(a,s)$,

we highlight crucial differences in their reward robustness interpretations in entropy_vs_div.

§.§ Worst-Case Perturbations: Policy Form

From the feasible set in feasible, how should the adversary select its reward perturbations?

In the following proposition,
we use the optimality conditions in <ref>
to solve for the worst-case reward perturbations $\prpi(a,s)$ which minimize <ref> for an fixed but arbitrary stochastic policy $\pi(a|s)$.

For a given policy $\pi(a|s)$ or state-action occupancy $\mu(a,s)$,
the worst-case adversarial reward perturbations $\prpi$ or $\prmu$ associated with a

convex function $\Omega(\mu)$ and regularization strength $1/\beta$

\begin{align}
\hspace*{-.23cm} \prpi(a,s) = \nabla_{\mu} \frac{1}{\beta} \Omega(\mu) \, .
% - \lambdaplus
\label{eq:prop1}
\end{align}

\begin{align}
\hspace*{-.23cm} \prpi = \nabla_{\mu} \frac{1}{\beta} \Omega(\mu) \, .
% - \lambdaplus
\label{eq:prop1}
\end{align}

See prop2 for proof.
We now provide example closed form expressions for the worst-case reward perturbations under common regularization schemes.
We emphasize that the same stochastic policy $\pi(a|s)$ or joint occupancy measure $\mu(a,s)$ can be associated with different adversarial perturbations depending on the choice of $\alpha$-divergence and strength $\beta$.[One exception is that a policy with $a\tick$ s.t. $\pi(a\tick|s)=0$ can only be represented using kl regularization if $\pi_0(a\tick|s) = 0$.]

KL Divergence For divergence policy regularization, the worst-case reward perturbations

\begin{align}
\prpi(a,s) = \frac{1}{\beta} \log \frac{\pi(a|s)}{\pi_0(a|s)} \, , \label{eq:kl_perturbations}
\end{align}

corresponds to the pointwise regularization $\prpi(a,s)=\ptReg_{\pi_0}(\pi(a|s)$ for each state-action pair, with $\Omega_{\pi_0}(\mu)= \mathbb{E}_{\mu(a,s)}[\ptReg_{\pi_0}(\pi(a|s)]$.

See conj1.

We show an analogous result in conj2

state-action occupancy regularization $\KL[\mu:\mu_0]$, where $\prmu(a,s) = \frac{1}{\beta} \log
% \mu(a|s)/\mu_0(a,s)= \ptReg_{\mu_0}(\mu)$.
\frac{\mu(a,s)}{\mu_0(a,s)}= \ptReg_{\mu_0}(\mu(a,s))$.

$\alpha$-Divergence For divergence regularization, the worst-case reward perturbations had a similar expression for conditional and joint regularization.   However, we observe notable differences

for the $\alpha$-divergence in general.  For policy regularization to a reference $\pi_0$,

\begin{align}
\hspace*{-.23cm} \prpi(a,s) = \frac{1}{\beta} \log_{\alpha} \frac{\pi(a|s)}{\pi_0(a|s)} +
% \underbrace{
\psipr ,
% \frac{1}{\beta}(1-\alpha) D_{\alpha}[\pi_0:\pi]
% }_{\textcolor{red}{\psi_{\pr}(s)}}
% - {\lambdaplus}
\label{eq:optimal_perturbations}
\end{align}

where we define $\psipr$ as

\begin{equation}
%   \hspace*{-.3cm}  \resizebox{.91\columnwidth}{!}{
\psipr \coloneqq \frac{1}{\beta}\frac{1}{\alpha} \left( \sum \limits_{a \in \mathcal{A}} \pi_0(a|s)- \sum \limits_{a \in \mathcal{A}} \pi_0(a|s)^{1-\alpha} \pi(a|s)^\alpha \right).
% $ .
% }
\label{eq:pr_normalizer}
\end{equation}

As we discuss in conj3, $\psipr$ plays the role of a normalization constant for the optimizing argument $\pir(a|s)$ in the definition of $\alphaconjn(\pr)$ (see <ref>, conj_table).  This term arises from differentiating $\Omega^{(\alpha)}_{\pi_0}(\mu)$ with respect to $\mu(a,s)$ instead of from an explicit constraint.

Assuming the given $\pi(a|s)$ and reference $\pi_0(a|s)$ are normalized, note that $\psipr = \frac{1}{\beta}(1-\alpha) D_{\alpha}[\pi_0:\pi]$.
With normalization, we also observe that $\psipr = 0$ for divergence regularization ($\alpha=1$), which confirms <ref> is a special case of <ref>.

For any given state-action occupancy measure $\mu(a,s)$ and joint $\alpha$-divergence regularization

to a reference $\mu_0(a|s)$, the worst-case perturbations become

\begin{align}
\prmu(a,s) = \frac{1}{\beta} \log_{\alpha}\frac{\mu(a,s)}{\mu_0(a,s)}, \label{eq:pr_mu}
% - \lambdaplus \, ,
\end{align}

with detailed derivations in mu_results.
In contrast to <ref>, this expression lacks an explicit normalization constant, as this constraint is enforced by the Lagrange multipliers $V(s)$ and $\mu(a,s) \in \mathcal{M}$ (optimal_policy).

§ VISUALIZING THE FEASIBLE SET

In the previous section, we have established an adversarial interpretation which suggests that regularized policies are robust to worst-case reward perturbations.   However, we have not discussed implications for zero-shot generalization or understood the limitations of this adversary.

In particular, it is not clear how the cost function $\alphaconjmu(\pr)$ in <ref> restricts the feasible set $\mathcal{R}$ of perturbations from which the adversary can select.
We characterize the feasible set in the following proposition, with visualizations in <ref>.

[]propositionfeasible For a given policy $\pi(a|s)$ and any $\alpha$-divergence, the feasible set of reward perturbations available to the adversary is defined by the constraint

\begin{align}
\alphaconjmu(\pr) \leq 0 \label{eq:alpha_feasible}
% \\\frac{\alpha-1}{\alpha} \langle \mu(s) \pi^{(\pr)}_*(a|s), \pr \rangle - \frac{1}{\alpha}(V^{\pr}_*(s)  \leq 0 \label{eq:alpha_feasible}
\end{align}

For kl divergence regularization, we obtain

\begin{align}
\sum\limits_{a \in \mathcal{A}} \pi_0(a|s) \expof{\beta \cdot \pr(a,s)} \leq 1 \, . \label{eq:kl_feasible}
\end{align}

See feasible_pf for proof.
which proceeds by evaluating the conjugate function at the worst-case $\propt$, with $\alphaconjn(\propt)=0 \, \forall \alpha$.

The constraint for the minimization problem in <ref> then follows from the fact that $\alphaconjn(\pr)$ is increasing in $\pr$. no longer holds: alternative proof given in the appendix

The above constraints characterize the robust set of modified reward functions for which we can provide performance guarantees.

More precisely, for given MDP transition dynamics, we say that a policy trained with reward $r(a,s)$ and

regularized objective $\obj_{\Omega,\beta}(r)$
generalizes to an environment with a modified reward $\mr(a,s) = r(a,s) - \pr(a,s)$ if

\begin{align}
\hspace*{-.2cm}
%   \langle \mu(a,s), \mr(a,s) \rangle &\geq \langle \mu(a,s), r(a,s) \rangle - \omegamu \, . \label{eq:robust_def} \\
\langle \mu(a,s), \mr(a,s) \rangle &\geq \langle \mu(a,s), r(a,s) \rangle - \omegamu \, . \label{eq:robust_def}
%   \langle \mu(a,s), \mr(a,s) \rangle &\geq \langle \mu(s)\pi(a|s), r(a,s) - \ptReg(\pi) \rangle \\
%   \langle \mu(a,s), \mr(a,s) \rangle &\geq \obj_{\Omega, \beta}(r) = \alphaconjmu \\
%   \alphaconjmu \text{vs.} \alphaconjmuu \\
%   \alphaconjn \text{vs.} \alphaconjnn \\
%   \langle \mu(a,s), \mr(a,s) \rangle &\geq \langle \mu(s), V_*(s; \beta) \rangle = \langle \mu(s),\alphaconjn \rangle \\
%   \obj_{\Omega, \beta}(r)  = \alphaconjmu &= \frac{\alpha-1}{\alpha} \langle \mu(s), \alphaconjn \rangle
%   \langle \mu(a,s), r(a,s) - \pr(a,s) \rangle &\geq \langle \mu(a,s), r(a,s) - \ptReg(\pi) \rangle  %\blangle \mu(s) \pi(a|s), \mr(a,s) \brangle \geq  \blangle \mu(s) \pi(a|s), r(a,s) - \frac{1}{\beta} \Omega_{\pi_0}(\pi) \brangle \, . \label{eq:robust_def}
\end{align}

In other words, the expected reward using the modified $\mr(a,s)$ is greater than or equal to the value of the regularized objective $\obj_{\Omega,\beta}(r)$ using the original $r(a,s)$.

Note that <ref> holds with equality for the worst-case modified reward $\mropt(a,s)$ (optimal_perturb or preserve).
The feasible set in feasible_set_main shows other rewards for which the inequality holds, with equality

at the boundary. Is this true?  Otherwise, why would we pick out the particular $\Delta r^{*}$ that we do?  Further, the original $r(a,s)$ is at the boundary, and this does not hold with equality.

It is in this particular sense that we can claim zero-shot generalization for a regularized policy.
We also notice that this form of robustness is sensitive to the value of the regularized objective function in <ref>, which we discuss in further detail in entropy_vs_div.

Visualizing the Feasible Set
In feasible_set_main, we visualize the feasible set of perturbed rewards in a two-dimensional action space for the or $\alpha$-divergence, various $\beta$, and a uniform or non-uniform prior policy $\pi_0$.
Since the optimal policy can be calculated easily in the single-step case, we consider fixed $Q(a,s) = r(a,s) = \{1.1, 0.8\}$ and show the robustness of the optimal $\pi_*(a|s)$, which differs based on the regularization scheme (see <ref>, (<ref>)).
We determine the feasible set of $\pr$ using the constraint in feasible (see feasible_plot for details), and plot the modified reward $r\tick(a,s) = Q(a,s) - \pr(a,s)$ for each action.

Inspecting the constraint for the adversary in <ref>, note that both reward increases $\pr(a,s) < 0$ and reward decreases $\pr(a,s) > 0$ contribute non-negative terms at each action, which either up- or down-weight the reference policy $\pi_0(a|s)$.  The constraint on their summation forces the adversary to trade off between perturbations of different actions in a particular state.
Further, since the constraints in feasible integrate over the action space, the rewards for all actions in a particular state must be perturbed together.
While it is clear that increasing the reward in both actions preserves the inequality in <ref>,

<ref> also includes regions where one reward decreases.

For high regularization strength ($\beta=0.1$), we observe that the boundary of the feasible set is nearly linear, with the slope $-\frac{\pi_0(a_1|s)}{\pi_0(a_2|s)}$ based on the ratio of each action in the prior.  The boundary steepens for lower regularization strength.  We can use the indifference condition to provide further geometric insight.   First, drawing a line from the origin with slope $1$ will intersect the feasible set at the worst-case modified reward (red star) in each panel, with $\mropt(a_1,s) = \mropt(a_2,s)$.  At this point, the slope of the tangent line yields the ratio of action probabilities, as we saw for the $\beta = 0.1$ case.  With decreasing regularization as $\beta \rightarrow \infty$, the slope approaches $0$ or $-\infty$ for a nearly deterministic policy and a rectangular feasible region. Where does InDifference go?

Finally, we show the feasible set for the $\alpha$-divergence with $\alpha \in \{-1, 3\}$ and $\beta = 10$ in <ref> (d)-(e) and (i)-(j), with further visualizations in additional_feasible.   Compared with the kl divergence,
we observe a wider feasible set boundary for $\alpha =-1$, whereas $\alpha = 3$

§ COMPARISON WITH ENTROPY REGULARIZATION

As argued in optimal_perturb, the worst-case reward perturbations preserve the value of the regularized objective function.  Thus, we should expect our robustness conclusions to depend on the exact form of the regularizer.

When regularizing with the Tsallis or Shannon ($\alpha = 1$) entropy, the worst-case reward perturbations become

\begin{align}
% \propt(a,s) = \frac{1}{\beta} \log_{\alpha} \pi(a|s) \,. \label{eq:ptwise_perturb_ent}
\hspace*{-.2cm} \propt(a,s) = \frac{1}{\beta} \log_{\alpha} \pi(a|s) + \frac{1}{\beta} \frac{1}{\alpha} \big(1 - \sum
% \limits
_{a \in \mathcal{A}} \pi(a|s)^{\alpha} \big) \,. \label{eq:ptwise_perturb_ent}
\end{align}

In entropy_nonnegative, we show that these perturbations yield a pointwise non-negative contribution to the objective $r(a,s) - \propt(a,s)$, with $-\propt(a,s) \geq 0$ when $\pi(a|s) \leq 1$, for $0 < \alpha \leq 1$.

We argue that this property leads to several unsatisfying conclusions in previous work [Lee et al., 2019, Eysenbach & Levine, 2021], which are resolved by using the kl and $\alpha$-divergence for analysis instead of the corresponding entropic quantities.[Entropy regularization corresponds to divergence regularization with the uniform reference distribution $\pi_0(a|s)$.]

First, this means that an entropy-regularized policy appears to only be `robust' to increases in the reward function.   However, for useful generalization, we might hope that a policy will still perform well when the reward function decreases in at least some state-action pairs.
Including the reference distribution $\pi_0$ via divergence regularization resolves this issue,

and we observe in <ref>-<ref> that the adversary typically chooses reward decreases in some actions and increases in others.  For example, for the kl divergence, $\propt(a,s) = \frac{1}{\beta}\log \frac{\pi(a|s)}{\pi_0(a|s)}$ implies robustness to reward decreases when $\pi(a|s) > \pi_0(a|s)$.

Similarly, Lee et al., 2019 note that , for any $\alpha$,

\begin{align*}
\frac{1}{\beta}\Omega^{*(H_{\alpha})}_{\pi_0,\beta,\pi}(\discussiondual) = %\max_{\pi(a|s)}
\max \limits_{\pi \in \Delta^{|\mathcal{A}|}} \langle \pi, \discussiondual \rangle + \frac{1}{\beta} H_{\alpha}(\pi) \geq \discussiondual(a_{\max}, s)
% \left(-\frac{1}{\beta} H_{\alpha}(\pi)\right)
\end{align*}

where $a_{\max} = \argmax_a \discussiondual(a,s)$ and Tsallis entropy $H_{\alpha}(\pi)$ equals Shannon entropy for $\alpha = 1$.

This soft value aggregation yields a result that is larger than any particular $Q$-value.

By contrast, for the $\alpha$-divergence, we show in qmax that

\begin{equation}
\resizebox{\columnwidth}{!}{ $\discussiondual(a_{\max},s) + \frac{1}{\beta}\frac{1}{\alpha} \log_{\alpha} \pi(a_{\max}| s) \leq \alphaconjn(\discussiondual) \leq  \discussiondual(a_{\max},s) $
} \nonumber
\end{equation}

This provides a more natural interpretation of $V_*(s) =  \alphaconjn(Q)$ as a soft maximum function, with $ \mathbb{E}_{\pi_0}[\discussiondual(a_{\max},s)] \leq V_*(s) \leq \discussiondual(a_{\max},s)$, as in soft_value.

Finally, entropy regularization also affects interpretations of the feasible set.
Eysenbach & Levine, 2021 consider the same constraint as in <ref>, but without the reference distribution

\begin{align}
\sum \limits_{a} \expof{\beta \cdot \pr(a,s)} \leq 1  \, \, \, \forall s \in \mathcal{S} \, . \label{eq:ent_constraint}
\end{align}

This constraint suggests that the original reward function ($\pr = 0$) is not feasible for the adversary.

More surprisingly, Eysenbach & Levine, 2021 App. A5 argues that increasing regularization strength (with lower $\beta$) may lead to less robust policies based on the constraint in <ref>.    In eysenbach, we discuss how including $\pi_0(a|s)$ in the constraint via divergence regularization avoids this conclusion.   As expected,
we observe in
<ref> that increasing regularization strength leads to more robust policies.

§ EXPERIMENTS

In this section, we visualize the robust set and worst-case reward perturbations associated with policy regularization, using intuitive examples to highlight theoretical properties of our adversarial interpretation.

§.§ Visualizing the Robust Set

§.§ Visualizing the Worst-Case Reward Perturbations

In this section, we consider kl divergence regularization to a uniform reference policy, which is equivalent to Shannon entropy regularization but more appropriate for analysis, as we discuss in entropy_vs_div.

Single Step Case
In <ref>, we plot the negative worst-case reward perturbations $-\pr_{\pi}(a,s)$ and modified reward for a single step decision-making case.   For the optimal policy in <ref>(a), the perturbations match the advantage function as in <ref> and the perturbed reward for all actions matches the value function $V_*(s)$.
While we have shown in any_policy that any stochastic policy may be given an adversarial interpretation, we see in <ref>(b) that the indifference condition does not hold for suboptimal policies.

The nearly-deterministic policy in perturb_opt(a)(ii) also provides intuition for the unregularized case as $\beta \rightarrow \infty$.
Although we saw in value_form that $\pr_{\piopt}(a,s) = 0 \,\, \forall a$

in the unregularized case,  <ref> and (<ref>) suggest that $\lambdaplus = V_*(s) - Q_*(a,s)$ plays a similar role to the (negative) reward perturbations in perturb_opt(a)(ii), with $\lambda(a_1,s)=0$ and $\lambda(a,s)>0$ for all other actions.

Sequential Setting

In <ref>(a), we consider a grid world where the agent receives $+5$ for picking up the reward pill, $-1$ for stepping in water, and zero reward otherwise.  We train an agent

using tabular $Q$-learning and a discount factor $\gamma = 0.99$.
We visualize the worst-case reward perturbations $\prpi(a,s) = \frac{1}{\beta}\log \frac{\pi(a|s)}{\pi_0(a|s)}$
in each state-action pair for policies trained with various regularization strengths in <ref>(b)-(d).  While it is well-known that there exists a unique optimal policy for a given regularized MDP,
our results

additionally display the adversarial strategies and resulting Nash equilibria which can be associated with a regularization scheme specified by $\Omega$, $\pi_0$, $\alpha$, and $\beta$ in a given MDP.

Each policy implicitly hedges against an adversary that perturbs the rewards according to the values and colormap shown.  For example, inspecting the state to the left of the goal state in panel <ref>(b)-(c), we see that the adversary reduces the immediate reward for moving right (in red, $\proptpi > 0$).
Simultaneously, the adversary raises the reward for moving up or down towards the water (in blue).

This is in line with the constraints on the feasible set, which imply that the adversary must balance reward decreases with reward increases in each state.

In optimal_policy_confirm <ref>, we certify the optimality of each policy using the path consistency conditions, which also confirms that the adversarial perturbations have rendered the agent indifferent across actions in each state.

Although we observe that the agent with high regularization in <ref>(b) is robust to a strong adversary, the value

of the regularized objective is also lower in this case.   As expected, lower regularization strength reduces robustness to negative reward perturbations.
With low regularization in <ref>(d),

the behavior of the agent barely deviates from the deterministic policy in the face of the weaker adversary.

§ DISCUSSION

Our analysis in adversarial_perturb

unifies and extends several previous works analyzing the reward robustness of regularized policies [Ortega & Lee, 2014, Eysenbach & Levine, 2021, Husain et al., 2021], as summarized in novelty.   We highlight differences in the analysis of
entropy-regularized policies

in entropy_vs_div, and provide additional discussion of the closely-related work of Derman et al., 2021 in related.

§.§ Comparison with Entropy Regularization

As argued in adversarial_perturb, the worst-case reward perturbations preserve the value of the regularized objective function.  Thus, we should expect our robustness conclusions to depend on the exact form of the regularizer.

When regularizing with the Tsallis or Shannon ($\alpha = 1$) entropy, the worst-case reward perturbations become

\begin{align}
% \propt(a,s) = \frac{1}{\beta} \log_{\alpha} \pi(a|s) \,. \label{eq:ptwise_perturb_ent}
\hspace*{-.2cm} \prpi(a,s) = \frac{1}{\beta} \log_{\alpha} \pi(a|s) + \frac{1}{\beta} \frac{1}{\alpha} \Big(1 -
\sum_{a \in \mathcal{A}} \pi(a|s)^{\alpha} \Big) \,. \label{eq:ptwise_perturb_ent}
\end{align}

See entropy_nonnegative, we also show that for $0 < \alpha \leq 1$,

these perturbations cannot decrease the reward, with $-\prpi(a,s) \geq 0$ and $\mr_{\pi}(a,s) \geq r(a,s)$.

In the rest of this section, we

argue that this property leads to several unsatisfying conclusions in previous work [Lee et al., 2019, Eysenbach & Levine, 2021], which are resolved by using the kl and $\alpha$-divergence for analysis instead of the corresponding entropic quantities.[Entropy regularization corresponds to divergence regularization with the uniform reference distribution $\pi_0(a|s)$.]

this means that a Shannon entropy-regularized policy is only

`robust' to increases in the reward function.   However, for useful generalization, we might hope that a policy still performs well when the reward function decreases in at least some states.
Including the reference distribution via divergence regularization resolves this issue,

and we observe in feasible_set_main and pyco that the adversary

chooses reward decreases in some actions and increases in others.  For example, for the kl divergence, $\prpiopt(a,s) = \frac{1}{\beta}\log \frac{\piopt(a|s)}{\pi_0(a|s)} = Q_*(a,s) - V_*(s)$ implies robustness to reward decreases when $\piopt(a|s) > \pi_0(a|s)$ or $Q_*(a,s) > V_*(s)$.

Similarly, Lee et al., 2019 note that for any $\alpha$,

\begin{align*}
\frac{1}{\beta}\Omega^{*(H_{\alpha})}_{\beta}(\discussiondual) = %\max_{\pi(a|s)}
\max \limits_{\pi \in \Delta^{|\mathcal{A}|}} \langle \pi, \discussiondual \rangle + \frac{1}{\beta} H_{\alpha}(\pi) \geq \discussiondual(a_{\max}, s)
% \left(-\frac{1}{\beta} H_{\alpha}(\pi)\right)
\end{align*}

where $a_{\max} = \argmax_a \discussiondual(a,s)$ and the Tsallis entropy $H_{\alpha}(\pi)$ equals the Shannon entropy for $\alpha = 1$.

This soft value aggregation yields a result that is larger than any particular $Q$-value.

By contrast, for the $\alpha$-divergence, we show in qmax that for fixed $\beta$ and $\alpha > 0$,

\begin{equation}
% \resizebox{\columnwidth}{!}{ $
\discussiondual(a_{\max},s) + \frac{1}{\beta}\frac{1}{\alpha} \log_{2-\alpha} \pi(a_{\max}| s) \leq \alphaconj(\discussiondual) \leq  \discussiondual(a_{\max},s)
% $ }
\end{equation}

This provides a more natural interpretation of the Bellman optimality operator $V(s) \leftarrow \alphaconj(Q)$ as a soft maximum operation.   As a function of $\beta$, we see in alpha_results and <ref> that the conjugate ranges between $\mathbb{E}_{\pi_0}[\discussiondual(a_{\max},s)] \leq \alphaconj(Q) \leq \discussiondual(a_{\max},s)$.

Finally, using entropy instead of divergence regularization also affects interpretations of the feasible set.
Eysenbach & Levine, 2021 consider the same constraint as in <ref>, but without the reference $\pi_0(a|s)$

\begin{align}
\sum \limits_{a \in \mathcal{A}} \expof{\beta \cdot \pr(a,s)} \leq 1  \, \quad \forall s \in \mathcal{S} \, . \label{eq:ent_constraint}
\end{align}

This constraint suggests that the original reward function ($\pr = 0$) is not feasible for the adversary.

More surprisingly, Eysenbach & Levine, 2021 App. A8 argues that increasing regularization strength (with lower $\beta$) may lead to less robust policies based on the constraint in <ref>.    In eysenbach, we discuss how including $\pi_0(a|s)$ in the constraint via divergence regularization (feasible) avoids this conclusion.   As expected,

<ref> shows that increasing regularization strength leads to more robust policies.

§.§ Related Algorithms

Several recent works provide algorithmic insights which build upon convex duality
and complement or extend our analysis.

Derman et al., 2021
derive practical iterative algorithms based on a general equivalence between robustness and regularization, which can be used to enforce

robustness to both reward perturbations (through policy regularization) and changes in environment dynamics (through value regularization).

For policy regularization, Derman et al., 2021 translate

the specification of a desired robust set

a regularizer using the convex conjugate of the set indicator function.   In particular, Derman et al., 2021 associate kl divergence or (scaled) Tsallis entropy policy regularization with the robust set $\mathcal{R}^{\Delta}_{\pi} \coloneqq \{
% \prrob \in \rprimedomain  \, | \,
\prrob \, | \,
\prrob(a,s) \in [\frac{1}{\beta} \frac{1}{\alpha} \log_{\alpha} \frac{\pi(a|s)}{\pi_0(a|s)}, \infty) \, \, \forall \,  (a,s) \in  \mathcal{A} \times \mathcal{S}\}$.

Our analysis proceeds in the opposite direction, from regularization to robustness,
using the conjugate of the divergence.    While the worst-case perturbations
result in the same modified objective,
our approach

yields a larger robust set with qualitatively different shape (see related).

Zahavy et al., 2021 analyze a general `meta-algorithm' which alternates between updates of the occupancy measure $\mu(a,s)$ and modified reward $\mr(a,s)$ in online fashion.
This approach highlights the fact that the modified reward $\mr_{\pi}$ or worst-case perturbations $\prpi$ change as the policy or occupancy measure is optimized.
The results of Zahavy et al., 2021 and Husain et al., 2021 hold for general convex MDPs, which encompass common exploration and imitation learning objectives beyond the policy regularization setting
we consider.

As discussed in optimal_policy, path consistency conditions have been used to derive practical learning objectives in [Nachum et al., 2017, Chow et al., 2018].   These algorithms might be extended to general $\alpha$-divergence regularization via <ref>, which involves an arbitrary reference policy $\pi_0(a|s)$ that can be learned adaptively as in [Teh et al., 2017, Grau-Moya et al., 2018].

Finally, previous work has used dual optimizations similar to <ref> to derive alternative Bellman error losses [Dai et al., 2018, Belousov & Peters, 2019, Nachum & Dai, 2020, Bas-Serrano et al., 2021], highlighting how convex duality can be used to bridge between policy regularization and Bellman error aggregation [Belousov & Peters, 2019, Husain et al., 2021].

§ CONCLUSION

In this work, we analyzed the robustness of convex-regularized RL policies to worst-case perturbations of the reward function,
which implies generalization to adversarially chosen reward functions from within a particular robust set.

We have characterized this robust set of reward functions for kl and $\alpha$-divergence regularization, provided a unified discussion of existing works on reward robustness, and clarified apparent differences in robustness arising from entropy versus divergence regularization.

Our advantage function interpretation of the worst-case reward perturbations provides a complementary perspective on how $Q$-values appear as dual variables in convex programming forms of regularized MDPs.  Compared to a deterministic, unregularized policy,

a stochastic, regularized policy
places probability mass on a wider set of actions and

requires state-action value adjustments via the advantage function or adversarial reward perturbations.
Conversely, a regularized agent, acting based on given $Q$-value estimates, implicitly hedges against the anticipated perturbations of an appropriate adversary.

Regularization plays a crucial role in various settings across RL, such as trust-region methods [Peters et al., 2010, Schulman et al., 2015, Schulman et al., 2017, Bas-Serrano et al., 2021], offline learning [Levine et al., 2020, Nachum et al., 2019, Nachum et al., 2019, Nachum & Dai, 2020], multi-task learning <cit.>, and soft
$Q$-learning or actor-critic methods

[Fox et al., 2016, Nachum et al., 2017, Haarnoja et al., 2017, Haarnoja et al., 2018, Grau-Moya et al., 2018].

Various justifications have been given for policy regularization,
such as improved optimization [Ahmed et al., 2019],

connections with probabilistic inference <cit.>,

and robustness to perturbations in environment rewards or dynamics [Eysenbach & Levine, 2021, Husain et al., 2021].

The latter
is crucial in ai safety, where

a primary goal

is to design agents that generalize and adapt safely to new situations or distributional shift.

In this work, we analyze the robustness properties which arise from policy regularization in RL.
For a policy $\pi(a|s)$ regularized using a convex function $\Omega(\pi) = \mathbb{E}_{\pi}[\ptReg(\pi)]$ such as a statistical divergence, we investigate statements of the form

\begin{align}
\hspace*{-.2cm} &\max \limits_{\pi(a|s)} (1-\gamma) \mathbb{E}_{\tau \sim p^{\pi}(\tau)} \left[ \sum \limits_{t=0}^\infty \gamma^t \bigg( r(a_t, s_t) - \ptReg \big(\pi(a_t | s_t)\big) \bigg) \right] \nonumber \\
&= \max \limits_{\pi(a|s)} \min \limits_{r\tick(a,s) \in \feasibleset}  \mathbb{E}_{\tau \sim p^{\pi}(\tau)} \left[ \sum \limits_{t=0}^\infty \gamma^t \, r\tick(a_t,s_t) \right]
\label{eq:reward_perturbation_stmt}
\end{align}

where $r\tick(a,s)$ is the worst-case reward function chosen from an appropriate feasible set $\feasibleset$.
This robustness is intriguing, as it suggests regularized policies achieve a form of `zero-shot' generalization to new environments where the reward has been adversarially chosen.

Using tools from convex duality, we provide a precise characterization of this reward robustness,

We find that the optimal modified reward $r_{*}\tick$ in <ref> re-expresses the value of the objective for a given policy, which places restrictions on the set $\mathcal{R}$.  We discuss the implications of this particular form of robustness for generalization, along with a game-theoretic interpretation of soft value aggregation as hedging against adversarial perturbations that seek to
equalize the reward obtained for each action in a particular state [Ortega & Lee, 2014].

Our analysis unifies several recent works that explore similar interpretations [Ortega & Lee, 2014, Husain et al., 2021, Eysenbach & Levine, 2021], and our main contributions include

* A thorough analysis of the robustness associated with and $\alpha$-divergence regularization of RL policies.  This includes popular Shannon entropy regularization

[Haarnoja et al., 2017, Haarnoja et al., 2018, Eysenbach & Levine, 2021] as a special case, and our derivations for the $\alpha$-divergence generalize the Tsallis entropy RL framework of [Lee et al., 2019].

* Our analysis of the $\alpha$-divergence highlights distinct roles for the value function and policy normalization constant, which coincide in the case of the kl divergence.

* A precise characterization of the feasible set $\mathcal{R}$ of adversarial rewards against which a regularized policy is robust, as visualized in <ref> and shown in perturbations-<ref>.

Our use of divergence regularization instead of entropy regularization clarifies
several unsatisfying conclusions from previous work.

* We link a game-theoretic `indifference condition', which occurs at an equilibrium between the agent and adversary [Ortega & Lee, 2014], to the `path consistency' optimality condition, which has been used to construct learning objectives in [Nachum et al., 2017, Chow et al., 2018].

While the latter observations hold only for the optimal policy, we emphasize that our results provide a reward robustness interpretation for any stochastic policy under a given regularization scheme.

In this section, we review

LP formulations of
discounted MDP, along with extensions to convex policy regularization.
We begin by reviewing the convex conjugate,
which will play a crucial role throughout our paper.

§.§ Convex Conjugate

For any convex function $\Omega(\pi)$ with domain $\pi \in \mathcal{D}$,

the conjugate function $\Omega^{*}$ is defined via the optimization

\begin{align}
\Omega^{*}( \dualvar ) = \sup \limits_{\pi \in \mathcal{D}} \, \big \langle \pi, \dualvar \big \rangle - \Omega(\pi) \label{eq:conjstar}
\end{align}

where $\dualvar \in \dualdomain$ is a function in the continuous dual space of $\pi$.

The conjugate operation is an involution for proper, lower semi-continuous, and convex $\Omega$ [Boyd & Vandenberghe, 2004],

so that $(\Omega^{*})^{*} = \Omega$ and $\Omega^{*}$ is also convex.
We can thus represent $\Omega(\pi)$ via a conjugate optimization

\begin{align}
\Omega(\pi) = \sup_{\dualvar \in \dualdomain} \big \langle \pi, \dualvar \big \rangle - \Omega^{*}(\dualvar) \label{eq:conjomega}
\end{align}

Differentiating with respect to optimization variable in either <ref> or <ref> suggests optimality conditions for $\pi_*$ and $\dualvar$

\begin{align}
\pi_*(a|s) = \nabla \Omega^{*}( \dualvar )   \quad \qquad \dualvar_*(a,s) = \nabla \Omega(\pi)     \label{eq:optimal_policy_as_grad}
\end{align}

From the above, conjugacy also implies relationships of the form $\pi_*(a|s) = (\nabla \Omega)^{-1}(\dualvar_*(a,s))$ when $\pi_*$ and $\dualvar_*$ are in dual correspondence.

We proceed to describe how the conjugate arises in convex programming formulations of regularized MDPs, before describing examples in conj_examples.

§.§ Primal Formulations

We consider an MDP as a tuple $\{ \mathcal{S}, \mathcal{A}, P, \nu_0, r, \gamma \}$ consisting of a state space $\mathcal{S}$, action space $\mathcal{A}$, transition dynamics $P(s\tick|s,a)$ for $s, s\tick \in \mathcal{S}$, $a \in \mathcal{A}$, initial state distribution $\nu_0(s) \in \Delta^{|\mathcal{S}|}$ in the probability simplex, and reward function $r(a,s):\mathcal{S} \times \mathcal{A} \mapsto \mathbb{R}$.   We use a discount factor $\gamma ~\in (0,1)$

, although this may also be handled by including a transition to an absorbing state into the MDP (Puterman, 1994 Sec. 5.3).

Unregularized Case

We consider an agent that seeks to maximize the expected discounted reward by acting according to a decision policy $\pi(a_t|s_t) \in \Delta^{|\mathcal{A}|}$ in each state of the MDP.

We assume that the policy is stationary and Markovian, so that it is independent of both the timestep and trajectory history.

Most commonly, this optimization is written using expectations
with respect to trajectories  $\tau$ which start from an initial state $s_0 \sim \nu_0(s)$ and evolve according to the policy $\pi(a|s)$ and dynamics $P(s\tick|s,a)$, with $ \tau \sim \pi(\tau):= \nu_0(s_0) \prod \pi(a_t | s_t) P(s_{t+1} | s_t, a_t)$.   Writing the objective $\mathcal{R}(r, \nu_0, P, \gamma)$ as $\mathcal{R}(r)$ for simplicity,

\begin{align}
\mathcal{R}(r) := \max \limits_{\pi(a|s)} \, (1-\gamma) \, \mathbb{E}_{\tau \sim \pi(\tau)} \bigg[ \sum \limits_{t=0}^{\infty} \gamma^t \, r(s_t, a_t)  \bigg] \, . \label{eq:policy_only}
\end{align}

To highlight connections with literature on convex duality, we convert this optimization into a equivalent linear program, which we refer to as the primal

\begin{align}
\hspace*{-.2cm} & \mathcal{R}(r) = \max \limits_{\mu(a,s)} \big \langle {\mu(a,s)}, {r(a,s)} \big \rangle \, \, \text{subj. to} \, \quad    \left( \forall s \in \mathcal{S} \right) \label{eq:primal_lp}\\
&\sum_{a} \mu(a,s) = (1-\gamma) \nu_0(s) + \gamma \sum_{a\tick, s\tick} P(s|a\tick, s\tick) \mu(a\tick,s\tick) \nonumber  \, .
%\, \forall s \in \mathcal{S}\nonumber
\end{align}

where inner product notation $\langle \cdot, \cdot \rangle$ indicates summation or integration over the domain of $\mu$.

We refer to the constraints as Bellman flow constraints [Syed et al., 2008], and denote
the set of feasible $\mu$ as $\mathcal{M}$.

The equivalence between the LP in <ref> and the reward-maximization objective in <ref> can be seen by writing the marginal state-visitation distribution $\mu(s) \propto (1-\gamma) \sum_{t=0}^\infty \gamma^t \, \mathbb{I}(s_t = s)$, which accounts for discounting and ensures the flow constraints are satisfied with $\mu(a,s) \in \mathcal{M}$.

It can be shown that any stationary policy $\pi(a|s)$ induces a unique state-action
visitation distribution $\mu(a,s)$, while, conversely, a feasible $\mu(a,s) \in \mathcal{M}$  is induced by some stationary $\pi(a|s)$ <cit.>.
This result allows us to factorize the optimization in <ref> into $\mu(s)\pi(a|s)$ for normalized $\pi(a|s) \in \Delta^{|\mathcal{A}|}$, which matches the optimization in <ref>.   Optimizing over $\mu(s)$ yields the unique marginal induced by $\pi(a|s)$.

Regularized Case
We now consider regularizing the objective in <ref> using a convex penalty function $\Omega$ with coefficient $1/\beta$.
Letting $\Omega_{\pi_0}(\pi)$ be a statistical divergence between the policy and a reference distribution $\pi_0(a|s)$, we define the regularized $\mathcal{R}_{\Omega, \beta}(r)$ [We focus on policy regularization in this work, although similar reasoning may be applied to regularization of the joint-state action distribution $\mu(a,s)$ [Nachum & Dai, 2020, Husain et al., 2021, Bas-Serrano et al., 2021].]

\begin{equation}
\resizebox{.9\columnwidth}{!}{\hspace*{-.2cm} $
\mathcal{R}_{\Omega, \beta}(r) :=  \max \limits_{\ontop{\normalsize \mu(s) \rightarrow \mathcal{M}}{\pi(a|s) \in \Delta^{|A|}}} %\max \limits_{\pi(a|s) \in \Delta^{|A|}}
\blangle \mu(s)\pi(a|s), r(a,s) \brangle - \dfrac{1}{\beta}  \blangle \mu(s), \Omega_{\pi_0}(\pi) \brangle $  %\text{subj. to} \, \sum_{a} \mu(a,s) = (1-\gamma) \nu_0(s) + \gamma \sum_{a\tick, s\tick} P(s|a\tick, s\tick) \mu(a\tick,s\tick) \, \forall s \in \mathcal{S} \label{eq:primal_lp}
\end{equation}

where we use $\mu(s) \rightarrow \mathcal{M}$ to indicate that $\mu(s)$ induces $\mu(a,s) \in \mathcal{M}$ for a given $\pi(a|s)$.

§.§ Dual Formulations

Unregularized Case
The flow constraints in <ref> are insightful, as they lead to a dual optimization reflecting the familiar Bellman equations [Bellman, 1957].    Introducing Lagrange multipliers $V(s)$ for each constraint, summing over $s \in \mathcal{S}$, and eliminating $\mu(a,s)$ by setting $d/d\mu(a,s) = 0$ yields the dual

\begin{align}
&\mathcal{R}^{*}(r):=\min \limits_{V(s)} \,  (1-\gamma) \big \langle \nu_0(s), V(s) \big \rangle \, \text{  subj to: }\, \label{eq:dual_lp} \\ %\quad \forall (s,a) \in \mathcal{S} \times \mathcal{A}
& \, V(s) \geq r(s,a) + \gamma \transitionv  , \, \, \forall (s,a) \in \mathcal{S} \times \mathcal{A}  \nonumber \, ,
\end{align}

where $\transitionv$ is shorthand for $\mathbb{E}_{P(s\tick|a,s)}[ V(s\tick)]$, and we have reindexed the transition tuple $(s\tick, a\tick, s)$ to $(s,a, s\tick)$ compared with <ref>.

Regularized Case

We can similarly derive dual versions of the regularized LP, starting from a Lagrangian relaxation of <ref>

\begin{align}
&  \max \limits_{\ontop{\normalsize \mu(s) \rightarrow \mathcal{M}}{\pi(a|s) \in \Delta^{|A|}}} \min \limits_{V(s)}  \,
(1-\gamma) \big\langle \nu_0(s), V(s) \big  \rangle  \label{eq:dual_lagrangian} \\
+ &\blangle \mu(s)\pi(a|s), r(a,s) +  \gamma \transitionv -V(s) - \frac{1}{\beta} \Omega_{\pi_0}(\pi) \brangle \nonumber
\end{align}

Swapping the order of optimization using strong duality <cit.>, we recognize the maximization over ${\pi(a|s)\in\Delta^{|A|}}$ as a conjugate function, leading to a regularized dual optimization

\begin{align}
\hspace*{-.2cm} &  \mathcal{R}_{\Omega, \beta}^{*}(r) = \min \limits_{V(s)} %\max \limits_{ \mu(s) \rightarrow \mathcal{M}}
\,  (1-\gamma) \big\langle \nu_0(s), V(s) \big  \rangle  \label{eq:dual_reg} \\
&+ \mathbb{E}_{\mu(s)} \bigg[\, \frac{1}{\beta}\Omega^{*}_{\pi_0, \beta} \bigg(r(a,s) +  \gamma \transitionv -V(s) \bigg)  \bigg] \nonumber
\end{align}

which is unconstrained, in contrast to <ref>.
Dual objectives of this form appear variously in <cit.>,
although it is often infeasible to sample from the induced marginal $\mu(s)$.
In both cases, note that the optimization is over the dual variables $V(s)$ only.

§.§ Soft Value Aggregation

Our main object of interest in the rest of the paper will be an alternative decomposition of the Lagrangian
in <ref>.

Eliminating $\mu(s)$ by setting $d/d\mu(s) = 0$, we obtain a condition known as the regularized Bellman operator [Neu et al., 2017, Geist et al., 2019]

\begin{align}
V(s)  = \blangle \pi(a|s), \, r(s,a) + \gamma \transitionv \brangle - \frac{1}{\beta} \Omega_{\pi_0}(\pi) \nonumber . % \label{eq:reg_bell}
\end{align}

Eliminating $\mu(s)$ thus leads to a constraint on the form of $V(s)$, since both may be viewed as enforcing the Bellman flow constraints.  Plugging this expression back into the Lagrangian <ref> and removing the minimization over $V(s)$, we are left with only the initial state term and a maximization over $\pi(a|s) \in \Delta^{|\mathcal{A}|}$.

Recalling the definition of the state-action value, or $Q$ function, ${Q_V(s,a)= r(s,a) + \gamma \transitionv}$, which is recursively defined in terms of value function estimates $V(s\tick)$, we obtain the following optimization

\begin{align}
&\mathcal{R}_{\Omega, \beta}^{*}(r) = \, \max \limits_{\pi(a|s) \in \Delta^{|\mathcal{A}|}} (1-\gamma) \, \blangle \nu_0(s) , V(s) \brangle \label{eq:bellman_reg} \\
& \,\, \text{subj. \footnotesize $ V(s)= \blangle \pi(a|s), r(s,a) + \gamma \transitionv \brangle - \frac{1}{\beta} \Omega_{\pi_0}(\pi) $} \nonumber \\[1.25ex]
&\text{\footnotesize$=(1-\gamma) \mathbb{E}_{\nu_0} \big[\max \limits_{\pi \in \Delta^{|\mathcal{A}|}} \langle \pi(a|s), Q(s,a)  \rangle - \frac{1}{\beta} \Omega_{\pi_0}(\pi) \big]$}  \label{eq:soft_bellman}
\end{align}

This conveniently involves expectations under $\nu_0(s)$ only, and leads to `soft' versions of standard RL algorithms such as value iteration (e.g. Haarnoja et al., 2017, Geist et al., 2019).
In the following sections, we interpret the regularized policy optimization in <ref>, which corresponds to the conjugate function $\frac{1}{\beta}\Omega^{*}_{\pi_0,\beta}(Q)$, as a two player game between an agent and an imagined adversary [Ortega & Lee, 2014].
In <ref>, we visualize the optimal value function $V_*(s) = \frac{1}{\beta}\Omega^{*}_{\pi_0,\beta}(Q)$, for kl or $\alpha$-divergence regularization and different choices of regularization strength $1/\beta$.
The choice of divergence particularly affects the aggregated value for low regularization, although we do not observe a clear pattern with respect to $\alpha$.[See Belousov & Peters, 2019, Lee et al., 2018, Lee et al., 2019, or <ref> for additional discussion of the effect of $\alpha$-divergence regularization on learned policies.]
In all cases, the value function ranges between $\max_a Q(a,s)$ for an unregularized deterministic policy as $\beta \rightarrow \infty$, and the expectation under the reference policy $\mathbb{E}_{\pi_0}[Q(a,s)]$ for strong regularization as $\beta \rightarrow 0$.   We further discuss this property in Sec. <ref>, and provide closed forms for $V_*(s)$ and the optimal policy below.

§.§ Conjugate Function Examples

We consider regularization using the family of $\alpha$-divergences <cit.>, which includes both the forward and reverse kl divergences as special cases.
We take the slightly non-standard step of writing divergences over unnormalized measures rather than probability distributions.  To see why this is useful, consider introducing a Lagrange multiplier to enforce the normalization constraint $\pi(a|s) \in \Delta^{|\mathcal{A}|}$ in <ref>.
In order to evaluate this relaxation,  the regularizer $\Omega_{\pi_0}(\pi)$ must be able to take unnormalized $\tpi(a|s) \not \in \Delta^{|\mathcal{A}|}$ as input.

$\alpha$-Divergence The $\alpha$-divergence over possibly unnormalized measures is defined as

\begin{align}
\hspace*{-.15cm} D_{\alpha}[\tpi_0:\tpi] =
\frac{1}{\alpha(1-\alpha)}\bigg( &  (1-\alpha) \sum \limits_{a \in \mathcal{A}}  \tpi_0(a|s) + \alpha \sum \limits_{a \in \mathcal{A}} \tpi(a|s) \nonumber \\
&- \sum \limits_{a \in \mathcal{A}} \tpi_0(a|s)^{1-\alpha} \tpi(a|s)^{\alpha} \bigg)
\end{align}

We distinguish between the conjugate function $\alphaconju$ and the conjugate with restriction to normalized distributions $\alphaconjn$  <cit.>, with detailed discussion in alpha_conj_all.  The latter appears in defining the optimal value function in <ref> and <ref>,

\begin{align}
V_*(s) &= \alphaconjn(Q) = \max \limits_{\pi \in \Delta^{|\mathcal{A}|}} \blangle \pi(a|s), Q(a,s) \brangle -  \frac{1}{\beta}\Omega^{(\alpha)}_{\tpi_0,\beta}(\pi) \nonumber \\
&= \frac{\alpha-1}{\alpha} \blangle \piopt(a|s), Q(a,s) \brangle + \frac{1}{\alpha} \normalizeralpha \label{eq:alpha_conj_norm_main}
\end{align}

where $\normalizeralpha$ is the normalization constant for the optimizing argument $\piopt(a|s)$ associated with $Q(a,s)$

\begin{align}
\hspace*{-.2cm} \piopt(a|s) = \pi_0(a|s) \, [1+(\alpha-1) \beta \cdot \big( Q(a,s) - \normalizeralpha \big) ]_+^{\frac{1}{\alpha-1}} \label{eq:alpha_opt_policy}
\end{align}

The $\alpha$-divergence is also closely related to the Tsallis entropy [Lee et al., 2019], as discussed in <ref>.
Unfortunately, the normalizer $\normalizeralpha$ appears inside the exponent and must be estimated numerically apart from special cases of $\alpha$ [Lee et al., 2019].[<cit.> provide justification for a multiplicative normalization constant, but this is no longer directly related to the expected reward objective.]

We visualize the optimal value $V_*(s)$ and the normalization constant $\normalizeralpha$ as a function of $\alpha$ in <ref>.   Apart from the case when $\alpha = 1$ as discussed below, we have $V_*(s) \neq \normalizeralpha$ in  <ref>.

$V(s)$ as a function of $\beta$

$V(s)$ and $\psi_{\alpha}(s)$ as a function of $\alpha$ for $\beta=1$
Optimal value function $V_*(s)$ and normalization constant $\psi_{\alpha}(s)$ as a function of $\beta$ (left) and $\alpha$ (right), using $Q(a,s)$ and $\pi_0(a|s)$ from the left inset.   See <ref> and <ref> for closed forms.

KL Divergence
Taking the limit as $\alpha \rightarrow 1$, we obtain an extended version of the kl divergence commonly used as regularization for RL

\begin{align}
\hspace*{-.15cm} D_{KL}[\tpi:\tpi_0] = \sum \limits_{a \in \mathcal{A}} \tpi(a|s) \log \frac{\tpi(a|s)}{\tpi_0(a|s)} - \tpi(a|s) + \tpi_0(a|s) \, . \nonumber
%\sum \limits_{a \in \mathcal{A}} %\lim_{\alpha \rightarrow 1}
\end{align}

The value function, or conjugate $\frac{1}{\beta}\Omega^*_{\pi_0,\beta}(Q)$, as a function $Q$ and with restriction to normalized $\pi$ becomes

\begin{align}
\hspace*{-.2cm} V_*(s) = \frac{1}{\beta}\Omega^*_{\pi_0,\beta}(Q) = \frac{1}{\beta} \log \sum \limits_{a \in \mathcal{A}} \pi_0(a|s) \expof{\beta \cdot Q(a,s)}. \label{eq:kl_v}
\end{align}

This matches the normalization constant for the optimal policy, with $V_*(s) = \psi(s;\beta)$ and

\begin{align}
\pi_*(a|s) = \pi_0(a|s) \expof{\beta \cdot \big( Q(a,s) -  \psi(s;\beta)\big)} \, ,\label{eq:kl_opt_policy}
\end{align}

This can also be seen by plugging $\alpha = 1$ into <ref>.

In this section, we analyze the robustness of regularized policies to adversarial perturbations of the reward function, which arises from an alternative application of convex duality for regularized RL objectives.    We draw connections with similar interpretations from Ortega & Lee, 2014, Eysenbach & Levine, 2021, Husain et al., 2021 throughout our exposition, with additional discussion in discussion.

§.§ Policy-Based Interpretation

We have seen that the conjugate optimization provides an alternative representation of a convex regularizer

\begin{align}
\hspace*{-.2cm} \frac{1}{\beta} \Omega_{\tpi_0}(\tpi) = \max_{\pr} \big \langle \tpi(a|s), \pr(a,s) \big \rangle - \frac{1}{\beta}  \Omega^{*}(\pr) \, .\label{eq:conjomega2}
\end{align}

Expanding the regularization term in <ref> using the conjugate function, we have

\begin{align}
\hspace*{-.2cm} & \quad \max \limits_{\mu(s) \rightarrow \mathcal{M}} \max \limits_{\pi(a|s) \in \Delta^{|\mathcal{A}|}}  \min \limits_{V(s)} \min \limits_{\textcolor{\highlight}{\perturbr(a,s)}} \, \label{eq:pedro_form} \\
& \big \langle {\mu(s)\pi(a|s)}, {r(a,s) +\gamma \transitionv - V(s) - \textcolor{\highlight}{\perturbr(a,s)}} \brangle  \nonumber  \\
& \qquad + \frac{1}{\beta} \Omega^{*}_{\tpi_0, \beta} \big( \textcolor{\highlight}{\perturbr(a,s)} \big) + (1-\gamma) \blangle \nu_0(s), V(s) \brangle \, ,  \nonumber
\end{align}

where we change the maximization in <ref> to a minimization since the divergence is subtracted.
Optimizations over $\mu(s)$ or $V(s)$ enforce the Bellman flow constraints across states of the MDP.

As in Ortega & Lee, 2014, we interpret this minmax optimization as a two player game in each state, between an agent which chooses a policy $\pi(a|s)$, and an imagined adversary which chooses a reward perturbation $\perturbr(a,s)$.
Notice that the adversary is penalized for large reward perturbations, with a cost measured by the conjugate function ${\Omega^{*}_{\tpi_0, \beta}(\perturbr)}$.

In the following proposition, we translate this cost function to a constraint on the feasible set of reward perturbations $\pr$ available to the adversary at a given regularization function $\Omega_{\tpi_0}$ with strength $1/\beta$. We also characterize the optimal adversarial reward perturbations, with detailed proofs in kl_perturb_section and alpha_perturb.

Using divergence regularization $\Omega_{\tpi_0} = D_{KL}[\tpi:\tpi_0]$, we have the following results:

* For a given policy $\pi(a|s)$, the unconstrained optimization over $\pr(a,s)$ in <ref> corresponds to the following constrained optimization

\begin{align}
%&\max \limits_{\mu(s) \rightarrow \mathcal{M}} \max \limits_{\pi(a|s) \in \Delta^{|\mathcal{A}|}}  \min \limits_{V(s)} \min
&\hspace*{-.4cm}  \min \limits_{\perturbr(a,s)} (1-\gamma) \blangle \nu_0(s), V(s) \brangle \label{eq:constraint_set} \\[1.25ex]
& \scriptsize \hspace*{-.55cm} {+ \big \langle {\mu(s)\pi(a|s)}, {r(a,s) +\gamma \transitionv - V(s) - \perturbr(a,s)} \brangle  } \nonumber  \\[1.5ex]
& \hspace*{-.55cm} \text{subj.} \sum \limits_{a} \pi_0(a|s) \expof{\beta \cdot \pr(a,s)} \leq \sum \limits_{a} \pi(a|s)  \, \, \forall s \in \mathcal{S} \nonumber
%\frac{1}{\beta} \Omega^{*}_{\textcolor{red}{\tpi_0}, \beta} \big( \perturbr(a,s) \big)
\end{align}

where the constraint arises from the conjugate function $\Omega^{*}_{\tpi_0,\beta}(\pr)$.

* The optimal strategy for the adversary is to choose reward perturbations equal to

\begin{align}
\propt(a,s) = \frac{1}{\beta} \log \frac{\tpi(a|s)}{\tpi_0(a|s)} \label{eq:optimal_perturbed}
\end{align}

Using $\alpha$-divergence regularization $\Omega_{\tpi_0} = D_{\alpha}[\tpi_0:\tpi]$, we have the following results:

* For a given $\pi(a|s)$, the unconstrained optimization over $\pr(a,s)$ from <ref> translates to the same minimization objective as in perturbations(a), with the following constraint

\begin{align}
\hspace*{-.4cm} \sum \limits_{a \in \mathcal{A}} &\tpi_0(a|s) [1 + (\alpha-1) \beta \cdot \pr(a,s) ]_+^{\frac{\alpha}{\alpha-1}} \label{eq:constraint_set_alpha}  \\
&\leq \sum \limits_{a \in \mathcal{A}} \tpi_0(a|s)^{1-\alpha} \tpi(a|s)^{\alpha} \quad \forall s \in \mathcal{S} \nonumber
%\hspace*{-.5cm}\alphaconju(\pr) \leq  \, \frac{1}{\beta} \frac{1}{\alpha} \sum \limits_{a \in \mathcal{A}} \tpi_0(a|s) \left(\frac{\tpi(a|s)}{\tpi_0(a|s)}^{\alpha} -1 \right) \,\, \forall s \in \mathcal{S} \nonumber
%\tpi_0(a|s)^{1-\alpha} \tpi(a|s)^{\alpha} - \frac{1}{\beta} \frac{1}{\alpha} \sum \limits_{a \in \mathcal{A}} \tpi_0(a|s) \quad \forall s \in \mathcal{S}
\end{align}

where the constraint arises from the conjugate function $\Omega^{*(\alpha)}_{\tpi_0,\beta}(\pr)$.

* The optimal strategy for the adversary is to choose reward perturbations equal to

\begin{align}
\propt(a,s) = \frac{1}{\beta} \log_{\alpha} \frac{\tpi(a|s)}{\tpi_0(a|s)}
\end{align}

$\log_{\alpha}\frac{\tpi(a|s)}{\tpi_0(a|s)}:= \frac{1}{\alpha-1} \left( \frac{\tpi(a|s)}{\tpi_0(a|s)}^{\alpha-1} - 1\right)$.

Conjugate Policy Representation
Our derivations so far have only invoked the conjugate representation of the regularization function, which suggests that any stochastic policy may be interpreted via an adversarial game once $\Omega, \tpi_0,$ and $\beta$ are known.

By contrast, the analysis of Eysenbach & Levine, 2021 is framed in terms of the robustness associated with a given reward function and regularization scheme, rather than a policy.  While the feasible set for divergence regularization in <ref> can be characterized without reference to a particular policy assuming $\sum_a \pi(a|s) = 1$,
the optimal reward perturbations and feasible set for the $\alpha$-divergence require knowledge of the policy.
Unfortunately, associating a policy with a reward function $r(a,s)$ in a given (regularized) MDP requires solving for the optimal policy in <ref> or (<ref>).

Analyzing the Feasible Set
In <ref>, we visualize the feasible set of perturbed rewards in a two-dimensional action space for the or $\alpha$-divergence, various $\beta$, and uniform or non-uniform priors.
Since the optimal policy can be calculated easily in the single-step case, we consider $\pi_*(a|s)$ corresponding to fixed $Q(a,s) = [1.1, 0.8]$ for various regularization settings (see <ref>, (<ref>)).
We determine the feasible set of $\pr(a,s)$ according to the constraint in <ref> or (<ref>), and plot the modified reward $r\tick(a,s) = Q(a,s) - \pr(a,s)$ for
each action.

Inspecting the constraints for the adversary in <ref> and (<ref>), note that both reward increases $\pr > 0$ and reward decreases $\pr < 0$ contribute non-negative terms which either up- or down-weight the reference policy $\pi_0(a|s)$.    The constraint on their summation forces the adversary to trade off between perturbing the reward at different actions in a particular state.

For high regularization strength ($\beta=0.1$), we observe that the boundary is nearly linear, with slope $-\frac{\pi_0(a_2|s)}{\pi_0(a_1|s)}$ based on the ratio of each action in the prior.  The boundary steepens for lower regularization strength, with only small decreases in the reward function available.  In all cases, it is natural that increasing the reward in both actions is feasible for an adversary that seeks to minimize the objective in <ref>.

Finally, we visualize the feasible set for the $\alpha$-divergence, with $\alpha \in \{-1, 3\}$ and $\beta = 1$, in <ref>

(d)-(e) and (i)-(j).
For the optimal policy associated with a given reward function,  we see that the $\alpha = -1$ feasible set may not include this reward function.

Reward Perturbation as Pointwise Regularizer
Note that both the kl and $\alpha$-divergences can be written with an outer expectation over $\tpi(a|s)$, with $\Omega_{\tpi_0}(\tpi) = \langle \tpi(a|s), \ptReg(\tpi(a|s)) \rangle$.
With derivations in tsallis, we can see that the optimal reward perturbations in perturbations (b) and <ref>(b) correspond to the (scaled) pointwise regularization $\ptReg(\pi(a|s))$ for the divergence over normalized $\pi(a|s) \in \Delta^{|\mathcal{A}|}$

\begin{align}
\ptReg(\pi(a|s)) = \frac{1}{\alpha} \propt(a,s) = \frac{1}{\alpha} \log_{\alpha} \frac{\pi(a|s)}{\pi_0(a|s)}
\end{align}

which may be further scaled by the regularization strength $1/\beta$.
This is a natural result, since the objective in <ref> takes the outer expectation $\langle \pi(a|s), r(a,s) - \pr(a,s) \rangle$.  As an example, for the divergence we have $\ptReg(\pi(a|s)) = \log \pi(a|s)/\pi_0(a|s) = \propt(a,s)$ with $\alpha = 1$.
Unresolved... when $\alpha\neq 1$, objective value appears to change due to $\frac{1}{\alpha}$ factor

Finally, note that we have considered the conjugate derived from $\Omega_{\tpi_0}(\tpi)$ over unnormalized density functions in deriving the optimal reward perturbations, so that normalization of $\pi(a|s)$
is enforced when solving <ref> for the policy rather than in the definition of the conjugate itself.
This allows us to avoid a self-referential definition of $\propt(a,s)$, which, for example, would include an additional $\frac{1}{\beta} \log \sum_{a} \pi_0 \expof{\beta \cdot \pr}$ on the right hand side of <ref>.   See kl_perturb_section.

§.§ Value-Based Interpretation

In this subsection, we provide a complementary interpretation of adversarial reward robustness from a value perspective, which highlights the role of $\pr(a,s)$ as a dual variable related to $V(s)$ and $Q(a,s)$.

Soft Value Aggregation & Adversarial Hedging
Using the results of the previous subsection, the value function $V_*(s) = \frac{1}{\beta}\Omega^{*}_{\pi_0,\beta}(Q)$ in <ref> and <ref> can be interpreted as the certainty equivalent <cit.>,
which aggregates over actions $a \in \mathcal{A}$ to measure the payoff of a two-player game where the agent begins in state $s \in \mathcal{S}$ and plays against an adversary defined by the regularizer $\Omega_{\pi}(\pi)$ and strength $\beta$ as in perturbations [Ortega & Lee, 2014].

Reward Perturbations using $Q$-Values

While a stochastic policy may be interpreted as hedging against an imagined adversary, we can also identify a given stochastic policy with an optimal adversarial reward perturbation.

Given a regularizer $\Omega_{\pi_0}(\pi) = D_{KL}[\pi:\pi_0]$, reference distribution $\pi_0(a|s)$, and regularization strength $1/\beta$,
we can simply rearrange <ref> to write

\begin{align}
\propt(a,s) = Q(a,s) - \normalizerexp =  \frac{1}{\beta} \log \frac{\pi(a|s)}{\pi_0(a|s)} \label{eq:perturb_opt_q}
\end{align}

where the difference $Q(a,s) - \normalizerexp$ is uniquely determined from $\pi(a|s)$ and the assumed regularizer.   Note that the choice of $Q(a,s)$ and $\normalizerexp$ are not unique, as the normalization constant $\normalizerexp$ is determined from the choice of $Q(a,s)$ and may be intractable in practice.

We obtain a similar expression for the $\alpha$-divergence, $Q(a,s) - \alphanorm =  \frac{1}{\beta} \ln_{\alpha} \frac{\pi(a|s)}{\pi_0(a|s)}$, although the normalizer $\alphanorm$ is not equal to the conjugate $\alphaconjn(\pr)$ as in the case of the divergence.

We visualize the optimal reward perturbations for the single step case in <ref>.
Notice that the reward perturbations reflecting a given policy $\pi(a|s)$ can either be positive or negative, depending on the likelihood ratio $\frac{\pi(a|s)}{\pi_0(a|s)} \lessgtr 1$ or the difference $Q(a,s) - \alphanorm \lessgtr 0$.    We discuss this property in more detail in discussion.

Indifference Condition for Optimal Policy

For the optimal policy $\opt(a|s)$ in a given MDP, we can additionally state an indifference condition across actions, which is a well-known property of Nash equilibria in game theory [Osborne & Rubinstein, 1994, Ortega & Lee, 2014].   In particular, the adversarial objective

has the same value for each action $a \in \mathcal{A}$ in state  $s \in \mathcal{S}$ (see indifference).
We can see in <ref>(a) that the perturbed rewards for each action match the value function $V_*(s)$ in each state.
While it is possible to derive an adversarial interpretation for any $\pi(a|s)$ using <ref>, we see in <ref>(b) that the indifference condition does not hold for suboptimal policies.

\[\arraycolsep=.005\textwidth
\begin{array}{cccc} %[width=40mm]
& \multicolumn{3}{c}{\text{(i) }\beta = 0.1} \\[.5ex]
\multirow{3}{\WidthMM}{\includegraphics[width=\WidthM, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/env.png} \\[4ex] \includegraphics[width=\WidthM, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/opt_agent.png}} &
%\end{subfigure}&\qquad  \hspace*{.2cm}
\includegraphics[width=\WidthS, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/beta01policy_opt.png} &
%\caption{\centering \small $D_{KL}, \beta = 0.1$}\label{fig:taba}\end{subfigure}& \qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta01perturb_opt.png} &
%\caption{\centering  $D_{KL}, \beta = 1.0$}\label{fig:tabb}\end{subfigure}&\qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta01perturbed_opt.png}  \\[.25ex]
& \multicolumn{3}{c}{\text{(ii) }\beta = 1.0} \\[.5ex]
%\caption{\centering \small $D_{KL}, \beta = 10$}\label{fig:tabc}\end{subfigure}&\hspace*{.2cm}\\
& % NEXT LINE for multi-row
%\includegraphics[width=\WidthM, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/opt_agent.png} &
%\end{subfigure}&\qquad  \hspace*{.2cm}
\includegraphics[width=\WidthS, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/beta1policy_opt.png} &
%\caption{\centering \small $D_{KL}, \beta = 0.1$}\label{fig:taba}\end{subfigure}& \qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta1perturb_opt.png} &
%\caption{\centering  $D_{KL}, \beta = 1.0$}\label{fig:tabb}\end{subfigure}&\qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta1perturbed_opt.png} \\[.25ex]
& \multicolumn{3}{c}{\text{(iii) } \beta = 10} \\[.25ex]
%\end{subfigure}&\qquad  \hspace*{.2cm}
\includegraphics[width=\WidthS, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/beta10policy_opt.png} &
%\caption{\centering \small $D_{KL}, \beta = 0.1$}\label{fig:taba}\end{subfigure}& \qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta10perturb_opt.png} &
%\caption{\centering  $D_{KL}, \beta = 1.0$}\label{fig:tabb}\end{subfigure}&\qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta10perturbed_opt.png}
% \\[.25ex]
\end{array}
\]

\[\arraycolsep=.005\textwidth
\begin{array}{cccc} %[width=40mm]
& \multicolumn{3}{c}{\text{(i) } \beta = 0.1} \\[.5ex]
\multirow{3}{\WidthMM}{\includegraphics[width=\WidthM, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/env.png} \\[4ex] \includegraphics[width=\WidthM, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/agent.png}} &
%\end{subfigure}&\qquad  \hspace*{.2cm}
\includegraphics[width=\WidthS, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/beta01policy_subopt.png} &
%\caption{\centering \small $D_{KL}, \beta = 0.1$}\label{fig:taba}\end{subfigure}& \qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta01perturb_subopt.png} &
%\caption{\centering  $D_{KL}, \beta = 1.0$}\label{fig:tabb}\end{subfigure}&\qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta01perturbed_subopt.png}  \\[.25ex]
& \multicolumn{3}{c}{\text{(ii) } \beta = 1.0} \\[.5ex]
%\caption{\centering \small $D_{KL}, \beta = 10$}\label{fig:tabc}\end{subfigure}&\hspace*{.2cm}\\
& % NEXT LINE for multi-row
%\includegraphics[width=\WidthM, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/agent.png} &
%\end{subfigure}&\qquad  \hspace*{.2cm}
\includegraphics[width=\WidthS, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/beta1policy_subopt.png} &
%\caption{\centering \small $D_{KL}, \beta = 0.1$}\label{fig:taba}\end{subfigure}& \qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta1perturb_subopt.png} &
%\caption{\centering  $D_{KL}, \beta = 1.0$}\label{fig:tabb}\end{subfigure}&\qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta1perturbed_subopt.png} \\[.25ex]
& \multicolumn{3}{c}{\text{(iii) } \beta = 10} \\[.5ex]
%\end{subfigure}&\qquad  \hspace*{.2cm}
\includegraphics[width=\WidthS, height=\HeightS, trim=5 0 5 0, clip]{figs/perturbed/beta10policy_subopt.png} &
%\caption{\centering \small $D_{KL}, \beta = 0.1$}\label{fig:taba}\end{subfigure}& \qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta10perturb_subopt.png} &
%\caption{\centering  $D_{KL}, \beta = 1.0$}\label{fig:tabb}\end{subfigure}&\qquad \hspace*{.2cm}
\includegraphics[width=\WidthM, height=\HeightM, trim=5 0 5 0, clip]{figs/perturbed/beta10perturbed_subopt.png} \\[.25ex]
\end{array}
\]

Suboptimal Policy

Single-Step Reward Perturbations.  $Q$-values in leftmost columns are used for each $\beta$ in columns 2-4.
We report the optimal $-\pr(a,s)$, so that values less than 0 are subtracted in the objective $\langle \pi_Q(a|s), r(a,s) - \pr(a,s) \rangle + \alphaconju(\pr)$.
In (a), we show the optimal policy ($Q(a,s) = r(a,s)$), where the  perturbed reward $r^{\prime}(a,s) = c \, \, \forall a$ reflects the indifference condition.  We also show a suboptimal policy in (b), where indifference does not hold.  In all cases, actions with high $Q(a,s)$ are robust to subtracted perturbations.

§ DISCUSSION

What insights can be obtained from this adversarial interpretation of regularized policies?

In <ref>, we discuss the generalization properties associated with this robustness, which we highlight is particularly sensitive to the form of the objective in <ref>.

We draw connections with the notion of path consistency [Nachum et al., 2017, Chow et al., 2018] in <ref>, and argue that  adversarial reward perturbations can provides a natural justification for including $Q$-values as dual variables in LP formulations of MDPs in <ref>.

§.§ Relationship to Generalization

Our adversarial interpretations imply robustness or generalization of a given policy $\pi(a|s)$ to an environment with a modified reward $\mr(a,s)$ in the sense that, for given MDP transition dynamics

\begin{align}
\hspace*{-.3cm} \langle \mu(s) \pi(a|s), \mr(a,s) \rangle \geq \langle \mu(s) \pi(a|s), r(a,s) \rangle - \langle \mu(s), \frac{1}{\beta} \Omega_{\pi_0}(\pi) \rangle \, \label{eq:robust_def}
%\blangle \mu(s) \pi(a|s), \mr(a,s) \brangle \geq  \blangle \mu(s) \pi(a|s), r(a,s) - \frac{1}{\beta} \Omega_{\pi_0}(\pi) \brangle \, . \label{eq:robust_def}
\end{align}

where the right hand side corresponds to the full objective function, including regularization, whereas the left hand side is only the expected reward.

The constraints in perturbations-<ref> characterize the robust set of modified rewards to which a given policy can generalize, as visualized in <ref>.   Since these constraints integrate over the action space, note that the rewards for all actions in a particular state must be perturbed together.

By running a fixed policy in an environment with higher rewards, we naturally expect the objective function to increase.   However, for useful zero-shot generalization, we might hope that a policy will still perform well when the reward function decreases in at least some states.

In the next subsection, we discuss how these qualitative properties can depend on the form of the regularization function $\frac{1}{\beta} \Omega_{\pi_0}(\pi)$ in <ref>.

§.§ Comparison with Entropy Regularization

When regularizing with the Tsallis or Shannon ($\alpha = 1$) entropy, the optimal reward perturbations become

\begin{align}
\propt(a,s) = \frac{1}{\beta} \log_{\alpha} \pi(a|s) \,. \label{eq:ptwise_perturb_ent}
\end{align}

We argue the pointwise non-negative contribution of these perturbations to the objective $r(a,s) - \propt(a,s)$, with $-\propt(a,s) \geq 0$ for $\pi(a|s) \leq 1$, leads to several unsatisfying conclusions from previous work [Lee et al., 2019, Eysenbach & Levine, 2021], which are resolved by our use of the kl and $\alpha$-divergences instead of the entropic quantities.   In particular, entropy regularization should be considered as a divergence to the uniform reference distribution $\pi_0(a|s)$ over actions.

First, this means that an entropy regularized policy is only `robust' to increases in the reward function.

Including the reference distribution as in perturbations(b) and <ref> changes this property, so that the optimal reward perturbation $\propt(a,s) = \frac{1}{\beta}\log_{\alpha} \frac{\pi(a|s)}{\pi_0(a|s)}$
yields robustness to reward decreases when $\pi(a|s) > \pi_0(a|s)$ and reward increases otherwise.

Similarly, Lee et al., 2019 note that

\begin{align*}
\frac{1}{\beta}\Omega^{*(H_{\alpha)}}_{\pi_0}(\discussiondual) = %\max_{\pi(a|s)}
\max \limits_{\pi \in \Delta^{|\mathcal{A}|}} \langle \pi, \discussiondual \rangle - \left(-\frac{1}{\beta} H_{\alpha}(\pi)\right) \geq \discussiondual(a_{\max}, s)
\end{align*}

where $a_{\max} = \argmax_a \discussiondual(a,s)$ and the Tsallis entropy $H_{\alpha}(\pi)$ equals the Shannon entropy for $\alpha = 1$.

This soft value aggregation, using the negative (Tsallis) entropy as a regularizer,  yields a value which is larger than any particular reward.

By contrast, for the $\alpha$-divergence, we show in qmax that

\begin{align*}
\discussiondual(a_{\max},s) + \frac{1}{\beta} \log_{\alpha} \frac{ \pi(a_{\max}| s)}{\pi_0( a_{\max}| s)} \leq \alphaconjn(\discussiondual) \leq  \discussiondual(a_{\max},s)
%\leq  \alphaconjn(\discussiondual) \leq \max_a \discussiondual(a,s) % \max \limits_{a \in \mathcal{A}} \discussiondual(a_{\max},s)
%     \discussiondual(a_{\max},s) \geq \alphaconjn(\discussiondual) \geq \begin{cases}  \discussiondual(a_{\max},s) -  \frac{1}{\alpha-1} \big( \frac{\pi(a_{\max} | s)}{\pi_0(a_{\max}|s)}^{\frac{1}{\alpha-1}} - 1 \big) \hfill \alpha \neq 1 \\
%   \discussiondual(a_{\max},s) - \log \frac{ \pi(a_{\max}| s)}{\pi_0( a_{\max}| s)}  \hfill \alpha =1 \end{cases}
%   %\leq  \alphaconjn(\discussiondual) \leq \max_a \discussiondual(a,s) % \max \limits_{a \in \mathcal{A}} \discussiondual(a_{\max},s)
\end{align*}

This provides a more natural interpretation of $V(s) =  \alphaconjn(Q)$ as a soft maximum function, with $ \mathbb{E}_{\pi_0}[\discussiondual(a_{\max},s)] \leq V(s) \leq \discussiondual(a_{\max},s)$ as in <ref>.

Finally, entropy regularization also affects interpretations of the feasible set.
Eysenbach & Levine, 2021 consider the same constraint as in perturbations, but without considering the reference distribution

\begin{align}
\sum \limits_{a} \expof{\beta \cdot \pr(a,s)} \leq \sum \limits_{a} \pi(a|s)  \, \, \, \forall s \in \mathcal{S} \, . \label{eq:ent_constraint}
\end{align}

This constraint suggests that the original reward function ($\pr = 0$) is not feasible for the adversary, unless the policy is deterministic.  More surprisingly, Eysenbach & Levine, 2021 App. A5 argues that increasing regularization strength may lead to less robust policies based on the constraint in <ref>.    In eysenbach, we discuss how including $\pi_0(a|s)$ in the constraint via divergence regularization modifies this conclusion.   As expected, we observe in <ref> that increasing regularization strength leads to more robust policies.

The adversarial interpretation in the previous sections may also be written directly using the modified reward $\mr(a,s) = r(a,s) - \pr(a,s)$, which has been studied in a more general setting by Husain et al., 2021.

Husain et al., 2021 consider maximizing an arbitrary concave objective $\concaveopt$, and proceed to derive its convex conjugate $(-\concaveopt)^*$.    Translated to our setting and notation,
this involves the conjugate expansion of the regularized objective $(-\mathcal{R}_{\Omega, \beta}(r))^*$ instead of the conjugate of the regularizer $ (\frac{1}{\beta} \Omega_{\pi_0}(\pi))^*$ only.
With detailed derivations in husain_conjugate, this leads to the Lagrangian

\begin{align}
\hspace*{-.2cm} & \quad \max \limits_{\mu(s) \rightarrow \mathcal{M}} \max \limits_{\pi(a|s) \in \Delta^{|\mathcal{A}|}}  \min \limits_{V(s)} \min \limits_{\textcolor{\highlight}{\mr(a,s)}} \, \label{eq:husain_form} \\
& \big \langle {\mu(s)\pi(a|s)}, {\textcolor{\highlight}{\mr(a,s)} +\gamma \transitionv - V(s) } \brangle  \nonumber  \\
& \quad+ \frac{1}{\beta} \Omega^{*}_{\textcolor{red}{\tpi_0}, \beta} \big( r(a,s) - \textcolor{\highlight}{\mr(a,s)} \big) + (1-\gamma) \blangle \nu_0(s), V(s) \brangle \, ,  \nonumber
\end{align}

which matches <ref> up to simple reparameterization of $\mr(a,s) = r(a,s) - \pr(a,s)$.

Optimal Modified Rewards

Differentiating <ref> with respect to $\pi(a|s)$ and solving for the optimal modified rewards yields the result of Husain et al., 2021 that

\begin{align}
\mropt(a,s) = V(s) - \gamma \transitionv  %\quad \forall (a,s) \in (\mathcal{A}, \mathcal{S})
\end{align}

Adding the environment reward, we can use the optimal reward perturbations $\propt(a,s) = r(a,s) - \mropt(a,s)$ to rewrite this expression

\begin{align}
\propt(a,s) &=  r(a,s) + \gamma \transitionv -  V(s) \label{eq:modified_reward_opt}
\end{align}

This seems problematic because we would write $\pr(a,s) = Q(a,s) - \psi_{\alpha}(s;\beta)$ for $\alpha$-divergence minimization, with $\psi_{\alpha}(s;\beta) \neq V(s)$.
Think I can fix this

Connection with Path Consistency
For the kl divergence regularization, Nachum et al., 2017 use the kkt conditions to show that the optimal policy satisfies path consistency equations, which follow directly from the adversarial rewards in <ref> using perturbations.   In particular,

\begin{align}
r(a,s) - \underbrace{\frac{1}{\beta} \log \frac{\pi(a|s)}{\pi_0(a|s)}}_{\propt(a,s)} = V(s) - \gamma \transitionv
%\, \, \forall s \in \mathcal{S}, a \in \mathcal{A}
\end{align}

for all $s \in \mathcal{S}, a \in \mathcal{A}$.

Generalizing the path consistency equation shown in Chow et al., 2018 for the Tsallis entropy with $\alpha =2$, we can write

\begin{align}
r(a,s) - \underbrace{\frac{1}{\beta}\log_{\alpha}\frac{\pi(a|s)}{\pi_0(a|s)}}_{\propt(a,s)} &= V(s) - \gamma \transitionv + \Lambda(s)  \label{eq:path1}
\end{align}

where $\Lambda(s) = \normalizerexp - V(s)$ is a Lagrange multiplier which can be seen as accounting for the fact that $\normalizerexp \neq V(s)$ for $\alpha \neq 1$.
Finally, we are left with

\begin{align}
r(a,s) + \gamma \transitionv - \propt(a,s) = \normalizeralpha   \label{eq:path}
\end{align}

which matches our condition $\pr(a,s) = Q(a,s) - \normalizeralpha$.
With detailed derivations in <ref>, we show that the optimal $\alpha$-divergence regularized policy satisfies the path consistency condition in <ref>, which generalizes the result of Chow et al., 2018 from $\alpha=2$ to general $\alpha$.

These optimality conditions mirror the equilibrium indifference condition from <ref>, where the quantity $Q(a,s) - \propt(a,s) = r(a,s) + \transitionv -\propt(a,s) = c(s)$ equals a constant for all $a \in \mathcal{A}$.

Likely to be cut

Among the most intriguing observations in Husain et al., 2021 is to relate the adversarial reward perturbation $\pr(a,s) = r(a,s) - \mr(a,s)$ to the td-0 or Bellman backup error.   Similar observations have been made in the context of offline learning [Nachum & Dai, 2020] and REPS [Belousov & Peters, 2019, Bas-Serrano et al., 2021].

However, these works require modifications to the LP to incorporate $Q$-values,
which is necessary since the objective in <ref> involves $V(s)$ instead of $Q(a,s)$ as in the td-0 error.
Previous work has considered a non-standard `$Q$-lp' [Nachum & Dai, 2020] or introduced redundant constraints in a relaxed LP <cit.>.
The latter approach considers augmenting the flow constraints with a second distribution $d(a,s)$

\begin{align}
d(a,s) &= \mu(a,s) \label{eq:d_flow} \\
\sum_{a} d(a,s) &= (1-\gamma) \nu_0(s) + \gamma \sum_{a\tick, s\tick} P(s|a\tick, s\tick) \mu(a\tick,s\tick) \nonumber
\end{align}

In relaxed_lp, we argue that the introduction of dual variables $\mr(a,s)$ or $\pr(a,s)$ via the convex conjugate function
may provide an alternative justification for this relaxed lp.   In particular,  by further expanding the term $\Omega^{*}(\pr(a,s))$ in <ref> using the conjugate optimization $ \max_d \langle d(a,s), \pr(a,s) \rangle - \Omega(d)$, we can obtain

a second state-action visitation distribution $d(a,s)$ or a second policy $d(a|s)$ with a fixed $\mu(s)$

\begin{align}
\hspace*{-.2cm} & \quad \max \limits_{\mu(s) \rightarrow \mathcal{M}} \max \limits_{\pi(a|s) \in \Delta^{|\mathcal{A}|}}  \min \limits_{V(s)} \min \limits_{\textcolor{\highlight}{\perturbr(a,s)}} \max \limits_{\textcolor{\highlight}{d(a,s)}} \, \label{eq:relaxed_lp_form} \\
& \big \langle {\mu(s)\pi(a|s)}, {r(a,s) +\gamma \transitionv - V(s) - \textcolor{\highlight}{\perturbr(a,s)}} \brangle  \nonumber  \\
&+ (1-\gamma) \blangle \nu_0(s), V(s) \brangle + \blangle \mu(s) \textcolor{\highlight}{d(a|s)}, \textcolor{\highlight}{\pr(a,s)}- \frac{1}{\beta} \Omega_{\pi_0}(\textcolor{\highlight}{d})  \brangle \, .  \nonumber
\end{align}

We can make several observations from this objective.  First, differentiating with respect to $\pr(a,s)$ yields the condition that $d(a|s) = \pi(a|s)$ from <ref>, with the second constraint following directly.
Further, for kl divergence regularization, substituting $\pr(a,s) = Q(a,s) - V(s)$ yields the desired td-0 error $r(a,s) +\gamma \transitionv - Q(a,s)$.

We provide an alternative derivation of the Lagrangian for Logistic $Q$-learning [Bas-Serrano et al., 2021] in logistic_q, but leave further exploration, such as extending the primal dual algorithm of <cit.> to the regularized case, for future work.

($r(a,s) = -1$ for water,

$r(a,s) = 5$ for goal)

$\beta = 0.2$ (High Reg.)

$\beta = 1$

$\beta = 10$ (Low Reg.)

Optimal adversarial reward perturbations $\propt(a,s) = \frac{1}{\beta}\log \frac{\pi(a|s)}{ \pi_0(a|s)}$ for a sequential setting. Policy trained with kl divergence regularization,  $\gamma$ = 0.99.  Red indicates robustness to negative reward perturbations.

$\beta = 0.2$ (High Reg.)

$\beta = 1$

$\beta = 10$ (Low Reg.)

Perturbed rewards $\mr(a,s) = r(a,s) - \pr(a,s)$ for policies trained with kl divergence regularization.  The indifference condition holds in all cases, with $\mr(a,s) = c(s)$ for each action, and at each state and $c(s) = V(s)$ for kl regularization.  This confirms that the policy is optimal [Ortega & Lee, 2014, Nachum et al., 2017].

In this work, we have analyzed the robustness of convex-regularized RL policies to adversarial perturbations of the reward function.   This robustness can be given a natural game-theoretic interpretation, in which the equilibrium indifference condition for the optimal policy highlights that the adversarial perturbations re-express the value of the objective function.
Furthermore, policy regularization alone implies generalization to worst-case reward functions chosen within a particular robust set.
We have characterized the robust set of reward functions for and $\alpha$-divergence regularization, and resolved apparent differences in robustness properties arising from entropy versus divergence regularization.   Our analysis integrates several existing works on adversarial robustness, and highlights how convex conjugate representations can provide additional insight into regularization in RL.

Among the most intriguing observations in Husain et al., 2021 is to relate the adversarial reward perturbation $\pr(a,s) = r(a,s) - \mr(a,s)$ to the td-0 or Bellman backup error.   Similar observations have been made in the context of offline learning [Nachum & Dai, 2020] and REPS [Belousov & Peters, 2019, Bas-Serrano et al., 2021].

Extending recent work on alternative Bellman error aggregation [Dai et al., 2018, Nachum & Dai, 2020, Belousov & Peters, 2019, Bas-Serrano et al., 2021] to policy regularization settings,

potentially using $\alpha$-divergence regularization or learned reference distributions <cit.>, remains an intriguing direction for future work.

[Ahmed et al., 2019]
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans.
Understanding the impact of entropy on policy optimization.
In International Conference on Machine Learning. PMLR, 2019.

[Amari, 2016]
Shun-ichi Amari.
Information geometry and its applications, volume 194.
Springer, 2016.

[Arora & Doshi, 2021]
Saurabh Arora and Prashant Doshi.
A survey of inverse reinforcement learning: Challenges, methods and
Artificial Intelligence, 297:0 103500, 2021.

[Banerjee et al., 2005]
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John
Clustering with bregman divergences.
Journal of machine learning research, 60 (10), 2005.

[Bas-Serrano et al., 2021]
Joan Bas-Serrano, Sebastian Curi, Andreas Krause, and Gergely Neu.
Logistic q-learning.
In International Conference on Artificial Intelligence and
Statistics, pp.  3610–3618. PMLR, 2021.

[Bellman, 1957]
Richard Bellman.
A markovian decision process.
Journal of mathematics and mechanics, 60 (5):0
679–684, 1957.

[Belousov, 2017]
Boris Belousov.
Bregman divergence of alpha-divergence.
Blog post, 2017.

[Belousov & Peters, 2019]
Boris Belousov and Jan Peters.
Entropic regularization of markov decision processes.
Entropy, 210 (7), 2019.

[Boyd & Vandenberghe, 2004]
Stephen Boyd and Lieven Vandenberghe.
Convex optimization.
Cambridge university press, 2004.

[Chow et al., 2018]
Yinlam Chow, Ofir Nachum, and Mohammad Ghavamzadeh.
Path consistency learning in tsallis entropy regularized mdps.
In International Conference on Machine Learning, pp.  979–988. PMLR, 2018.

[Christiano et al., 2017]
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario
Deep reinforcement learning from human preferences.
Advances in neural information processing systems, 30, 2017.

[Cichocki & Amari, 2010]
Andrzej Cichocki and Shun-ichi Amari.
Families of alpha-beta-and gamma-divergences: Flexible and robust
measures of similarities.
Entropy, 120 (6):0 1532–1568, 2010.

[Dai et al., 2018]
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and
Le Song.
Sbeed: Convergent reinforcement learning with nonlinear function
In International Conference on Machine Learning, pp.  1125–1134. PMLR, 2018.

[Derman et al., 2021]
Esther Derman, Matthieu Geist, and Shie Mannor.
Twice regularized mdps and the equivalence between robustness and
In Thirty-Fifth Conference on Neural Information Processing
Systems, 2021.

[Diamond & Boyd, 2016]
Steven Diamond and Stephen Boyd.
CVXPY: A Python-embedded modeling language for convex
Journal of Machine Learning Research, 170
(83):0 1–5, 2016.

[Eysenbach & Levine, 2021]
Benjamin Eysenbach and Sergey Levine.
Maximum entropy RL (provably) solves some robust RL problems.
In International Conference on Learning Representations, 2021.

[Feinberg & Shwartz, 2012]
Eugene A Feinberg and Adam Shwartz.
Handbook of Markov decision processes: methods and
applications, volume 40.
Springer Science & Business Media, 2012.

[Fishburn, 1988]
Peter C Fishburn.
Nonlinear preference and utility theory.
Number 5. Johns Hopkins University Press, 1988.

[Fox et al., 2016]
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, pp.  202–211, 2016.

[Geist et al., 2019]
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin.
A theory of regularized markov decision processes.
In ICML 2019-Thirty-sixth International Conference on Machine
Learning, 2019.

[Grau-Moya et al., 2018]
Jordi Grau-Moya, Felix Leibfried, and Peter Vrancx.
Soft q-learning with mutual-information regularization.
In International Conference on Learning Representations, 2018.

[Haarnoja et al., 2017]
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine.
Reinforcement learning with deep energy-based policies.
In Proceedings of the 34th International Conference on Machine
Learning, volume 70 of Proceedings of Machine Learning Research, pp.   1352–1361. PMLR, 06–11 Aug 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, pp.  1861–1870. PMLR, 2018.

[Husain et al., 2021]
Hisham Husain, Kamil Ciosek, and Ryota Tomioka.
Regularized policies are reward robust.
International Conference on Artificial Intelligence and
Statistics, 2021.

[Igl et al., 2020]
Maximilian Igl, Andrew Gambardella, Jinke He, Nantas Nardelli, N Siddharth,
Wendelin Böhmer, and Shimon Whiteson.
Multitask soft option learning.
In Conference on Uncertainty in Artificial Intelligence, pp.  969–978, 2020.

[Kappen et al., 2012]
Hilbert J Kappen, Vicenç Gómez, and Manfred Opper.
Optimal control as a graphical model inference problem.
Machine learning, 870 (2):0 159–182, 2012.

[Lee et al., 2018]
Kyungjae Lee, Sungjoon Choi, and Songhwai Oh.
Sparse markov decision processes with causal sparse tsallis entropy
regularization for reinforcement learning.
IEEE Robotics and Automation Letters, 30 (3):0
1466–1473, 2018.

[Lee et al., 2019]
Kyungjae Lee, Sungyub Kim, Sungbin Lim, Sungjoon Choi, and Songhwai Oh.
Tsallis reinforcement learning: A unified framework for maximum
entropy reinforcement learning.
arXiv preprint arXiv:1902.00137, 2019.

[Levine, 2018]
Sergey Levine.
Reinforcement learning and control as probabilistic inference:
Tutorial and review.
arXiv preprint arXiv:1805.00909, 2018.

[Levine et al., 2020]
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu.
Offline reinforcement learning: Tutorial, review, and perspectives on
open problems.
arXiv preprint arXiv:2005.01643, 2020.

[Nachum & Dai, 2020]
Ofir Nachum and Bo Dai.
Reinforcement learning via fenchel-rockafellar duality.
arXiv preprint arXiv:2001.01866, 2020.

[Nachum et al., 2017]
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans.
Bridging the gap between value and policy based reinforcement
arXiv preprint arXiv:1702.08892, 2017.

[Nachum et al., 2019]
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li.
Dualdice: Behavior-agnostic estimation of discounted stationary
distribution corrections.
Reinforcement Learning for Real Life Workshop (ICML),

[Nachum et al., 2019]
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale
Algaedice: Policy gradient from arbitrary experience.
arXiv preprint arXiv:1912.02074, 2019b.

[Naudts, 2011]
Jan Naudts.
Generalised thermostatistics.
Springer Science & Business Media, 2011.

[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.

[Ng et al., 2000]
Andrew Y Ng, Stuart J Russell, et al.
Algorithms for inverse reinforcement learning.
In International Conference on Machine Learning, 2000.

[Ortega & Lee, 2014]
Pedro Ortega and Daniel Lee.
An adversarial interpretation of information-theoretic bounded
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 28, 2014.

[Ortega & Braun, 2013]
Pedro A Ortega and Daniel A Braun.
Thermodynamics as a theory of decision-making with
information-processing costs.
Proceedings of the Royal Society A: Mathematical, Physical and
Engineering Sciences, 4690 (2153), 2013.

[Osborne & Rubinstein, 1994]
Martin J Osborne and Ariel Rubinstein.
A course in game theory.

[Peters et al., 2010]
Jan Peters, Katharina Mulling, and Yasemin Altun.
Relative entropy policy search.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 24, 2010.

[Puterman, 1994]
Martin L Puterman.
Markov Decision Processes: Discrete Stochastic Dynamic
John Wiley & Sons, Inc., 1994.

[Puterman & Shin, 1978]
Martin L Puterman and Moon Chirl Shin.
Modified policy iteration algorithms for discounted markov decision
Management Science, 240 (11), 1978.

[Rawlik et al., 2013]
Konrad Rawlik, Marc Toussaint, and Sethu Vijayakumar.
On stochastic optimal control and reinforcement learning by
approximate inference.
In International Joint Conference on Artificial Intelligence,

[Scherrer et al., 2015]
Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and
Matthieu Geist.
Approximate modified policy iteration and its application to the game
of tetris.
Journal of Machine Learning Research, 160
(49):0 1629–1676, 2015.

[Schulman et al., 2015]
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp
Trust region policy optimization.
In International conference on machine learning, pp.  1889–1897. PMLR, 2015.

[Schulman et al., 2017]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal policy optimization algorithms.
arXiv e-prints, pp.  arXiv–1707, 2017.

[Syed et al., 2008]
Umar Syed, Michael Bowling, and Robert E Schapire.
Apprenticeship learning using linear programming.
In Proceedings of the 25th international conference on Machine
learning, pp.  1032–1039, 2008.

[Teh et al., 2017]
Yee Whye Teh, Victor Bapst, Wojciech Marian Czarnecki, John Quan, James
Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu.
Distral: robust multitask reinforcement learning.
In Proceedings of the 31st International Conference on Neural
Information Processing Systems, pp.  4499–4509, 2017.

[Tsallis, 2009]
Constantino Tsallis.
Introduction to nonextensive statistical mechanics: approaching
a complex world.
Springer Science & Business Media, 2009.

[Wang et al., 2021]
Ziyi Wang, Oswin So, Jason Gibson, Bogdan Vlahov, Manan S Gandhi, Guan-Horng
Liu, and Evangelos A Theodorou.
Variational inference mpc using tsallis divergence.
arXiv preprint arXiv:2104.00241, 2021.

[Zahavy et al., 2021]
Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh.
Reward is enough for convex mdps.
Advances in Neural Information Processing Systems, 2021.

[Zhu & Rohwer, 1995]
Huaiyu Zhu and Richard Rohwer.
Information geometric measurements of generalisation.
Technical report, Aston University, 1995.

§ IMPLICATIONS OF CONJUGATE DUALITY OPTIMALITY CONDITIONS

In this section, we show several closely-related results which are derived from the conjugate optimality conditions.   We provide additional commentary in later Appendix sections which more closely follow the sequence of the main text.

First, recall from <ref> the definition of the conjugate optimizations for functions over $\mathcal{X} \coloneqq \mathcal{A} \times \mathcal{S}$.  We restrict $\mu \in \mudomainfn$ to be a nonnegative function over $\mathcal{X}$, so that

\begin{equation}
\begin{aligned}
\frac{1}{\beta} \Omega^{*}(\dualvar) = \sup_{\primalvar \in \mudomainfn} \big \langle \primalvar, \dualvar \big \rangle - \frac{1}{\beta} \Omega(\primalvar),
% \label{eq:conjstar22}
\end{aligned} \hspace*{.05\textwidth}
\begin{aligned}
\frac{1}{\beta} \Omega(\primalvar) = \sup_{\dualvar \in \rprimedomain} \big \langle \primalvar, \dualvar \big \rangle - \frac{1}{\beta} \Omega^{*}(\dualvar),
% \label{eq:conjomega22}
\end{aligned}
\label{eq:conj_app}
\end{equation}

and the implied optimality conditions are

\begin{equation}
\begin{aligned}
\dualvar(a,s) = \frac{1}{\beta} \nabla_{\primalvar} \Omega(\primalvar) = \bigg( \nabla_{\dualvar} \frac{1}{\beta} \Omega^{*} \bigg)^{-1}(\primalvar)
% \label{eq:conj_optimality_app1}
\end{aligned} \hspace*{.05\textwidth}
\begin{aligned}
\primalvar(a,s) = \frac{1}{\beta} \nabla_{\dualvar} \Omega^*(\dualvar) = \bigg( \nabla_{\primalvar} \frac{1}{\beta} \Omega \bigg)^{-1}(\dualvar) \, .
% \label{eq:conj_optimality_app2}
\end{aligned}
\label{eq:conj_optimality_app}
\end{equation}

\begin{equation}
\begin{aligned}
\dualvar = \frac{1}{\beta} \nabla_{\primalvar} \Omega(\primalvar) = \bigg( \nabla_{\dualvar} \frac{1}{\beta} \Omega^{*} \bigg)^{-1}(\primalvar)
% \label{eq:conj_optimality_app1}
\end{aligned} \hspace*{.05\textwidth}
\begin{aligned}
\primalvar = \frac{1}{\beta} \nabla_{\dualvar} \Omega^*(\dualvar) = \bigg( \nabla_{\primalvar} \frac{1}{\beta} \Omega \bigg)^{-1}(\dualvar) \, .
% \label{eq:conj_optimality_app2}
\end{aligned}
\label{eq:conj_optimality_app}
\end{equation}

§.§ Proof of optimal_perturbations : Policy Form Worst-Case Reward Perturbations

The reward perturbations are defined via conjugate optimization for $\Omega(\primalvar)$ in <ref>,
where $\pr \in \rprimedomain$.

The proposition follows directly from the optimality condition in <ref>, and we focus on the $\dualvar(a,s) = \frac{1}{\beta} \nabla_{\primalvar} \Omega(\primalvar)$
$\dualvar = \frac{1}{\beta} \nabla_{\primalvar} \Omega(\primalvar)$
condition for convenience.

In conjugates, we derive the explicit forms for the worst-case reward perturbations for kl and $\alpha$-divergence regularization from any_policy of the main text.  See conjugates <ref> for references to particular derivations.

Note that we do not consider further
constraints on $\mu$ in the conjugate optimization.    Instead, we view the Bellman flow constraints $\mu(a,s) \in \mathcal{M}$ (and normalization constraint $\mu(a,s) \in \Delta^{|\mathcal{A}| \times |\mathcal{S}|}$) as arising from the overall (regularized) MDP optimization in <ref> or (<ref>), as we discuss in the next subsection.

§.§ Optimal Policy in a Regularized MDP