A Theory of Regularized Markov Decision Processes

Introduction

Many reinforcement learning algorithms make use of some kind of entropy regularization, with various motivations, such as improved exploration and robustness. Trust Region Policy Optimization (TRPO) (Schulman et al., 2015) is a policy iteration scheme where the greedy step is penalized with a Kullback-Leibler (KL) penalty between two consecutive policies. Dynamic Policy Programming (DPP) (Azar et al., 2012) is a reparametrization of a value iteration scheme regularized by a KL penalty between consecutive policies. Soft Q-learning, eg. (Fox et al., 2016; Schulman et al., 2017; Haarnoja et al., 2017), uses a Shannon entropy regularization in a value iteration scheme, while Soft Actor Critic (SAC) (Haarnoja et al., 2018a) uses it in a policy iteration scheme. Value iteration has also been combined with a Tsallis entropy (Lee et al., 2018), with the motivation of having a sparse regularized greedy policy. Other approaches are based on a notion of temporal consistency equation, somehow extending the notion of Bellman residual to the regularized case (Nachum et al., 2017; Dai et al., 2018; Nachum et al., 2018), or on policy gradient (Williams, 1992; Mnih et al., 2016).

This non-exhaustive set of algorithms share the idea of using regularization, but they are derived from sometimes different principles, consider each time a specific regularization, and have ad-hoc analysis, if any. Here, we propose a general theory of regularized Markov Decision Processes (MDPs). To do so, a key observation is that (approximate) dynamic programming, or (A)DP, can be derived solely from the core definition of the Bellman evaluation operator. The framework we propose is built upon a regularized Bellman operator, and on an associated Legendre-Fenchel transform. We study the theoretical properties of these regularized MDPs and of the related regularized ADP schemes. This generalizes many existing theoretical results and provides new ones. Notably, it allows for an error propagation analysis for many of the aforementioned algorithms. This framework also draws connections to convex optimization, especially to Mirror Descent (MD).

A unified view of entropy-regularized MDPs has already been proposed by Neu et al. (2017). They focus on regularized DP through linear programming for the average reward case. Our contribution is complementary to this work (different MDP setting, we do not regularize the same quantity, we do not consider the same DP approach). Our use of the Legendre-Fenchel transform is inspired by Mensch & Blondel (2018), who consider smoothed finite horizon DP in directed acyclic graphs. Our contribution is also complementary to this work, that does not allow recovering aforementioned algorithms nor analyzing them. After a brief background, we introduce regularized MDPs and various related algorithmic schemes based on approximate modified policy iteration (Scherrer et al., 2015), as well as their analysis. All proofs are provided in the appendix.

Background

Thus, the Bellman operator can also be written as $[T_{\pi}v](s)=\langle\pi(\cdot|s),q(s,\cdot)\rangle=\langle\pi_{s},q_{s}\rangle$. With a slight abuse of notation, we will write $T_{\pi}v=\langle\pi,q\rangle=(\langle\pi_{s},q_{s}\rangle)_{s\in\mathcal{S}}$.

Given this, we could derive value iteration, policy iteration, modified policy iteration, and so on. Basically, we can do all these things from the core definition of the Bellman evaluation operator. We’ll do so from a notion of regularized Bellman evaluation operator.

2 Legendre-Fenchel transform

We’ll make use of the following properties (Hiriart-Urruty & Lemaréchal, 2012; Mensch & Blondel, 2018).

Let $\Omega$ be strongly convex, we have the following properties.

Unique maximizing argument: $\nabla\Omega^{*}$ is Lipschitz and satisfies $\nabla\Omega^{*}(q_{s})=\operatorname*{argmax}_{\pi_{s}\in\Delta_{\mathcal{A}}}\langle\pi_{s},q_{s}\rangle-\Omega(\pi_{s})$.

Boundedness: if there are constants $L_{\Omega}$ and $U_{\Omega}$ such that for all $\pi_{s}\in\Delta_{\mathcal{A}}$, we have $L_{\Omega}\leq\Omega(\pi_{s})\leq U_{\Omega}$, then $\max_{a\in\mathcal{A}}q_{s}(a)-U_{\Omega}\leq\Omega^{*}(q_{s})\leq\max_{a\in\mathcal{A}}q_{s}(a)-L_{\Omega}$.

Monotonicity: $q_{s,1}\leq q_{s,2}\Rightarrow\Omega^{*}(q_{s,1})\leq\Omega^{*}(q_{s,2})$.

A classical example is the negative entropy $\Omega(\pi_{s})=\sum_{a}\pi_{s}(a)\ln\pi_{s}(a)$. Its convex conjugate is the smoothed maximum $\Omega^{*}(q_{s})=\ln\sum_{a}\exp q_{s}(a)$ and the unique maximizing argument is the usual softmax $\nabla\Omega^{*}(q_{s})=\frac{\exp q_{s}(a)}{\sum_{b}\exp q_{s}(b)}$. For a positive regularizer, one can consider $\Omega(\pi_{s})=\sum_{a}\pi_{s}(a)\ln\pi_{s}(a)+\ln|\mathcal{A}|$, that is the KL divergence between $\pi_{s}$ and a uniform distribution. Its convex conjugate is $\Omega^{*}(q_{s})=\ln\sum_{a}\frac{1}{|\mathcal{A}|}\exp q_{s}(a)$, that is the Mellowmax operator (Asadi & Littman, 2017). The maximizing argument is still the softmax. Another less usual example is the negative Tsallis entropy (Lee et al., 2018), $\Omega(\pi_{s})=\frac{1}{2}(\|\pi_{s}\|_{2}^{2}-1)$. The analytic convex conjugate is more involved, but it leads to the sparsemax as the maximizing argument (Martins & Astudillo, 2016).

Regularized MDPs

The core idea of our contribution is to regularize the Bellman evaluation operator. Recall that $[T_{\pi}v](s)=\langle\pi_{s},q_{s}\rangle$. A natural idea is to replace it by $[T_{\pi,\Omega}v](s)=\langle\pi_{s},q_{s}\rangle-\Omega(\pi_{s})$. To get the related optimality operator, one has to perform state-wise maximization over $\pi_{s}\in\Delta_{\mathcal{A}}$, which gives the Legendre-Fenchel transform of $[T_{\pi,\Omega}v](s)$. This defines a smoothed maximum (Nesterov, 2005). The related maximizing argument defines the notion of greedy policy.

We now define formally these regularized Bellman operators. With a slight abuse of notation, we write $\Omega(\pi)=(\Omega(\pi_{s}))_{s\in\mathcal{S}}$ (and similarly for $\Omega^{*}$ and $\nabla\Omega^{*}$).

that is, state-wise, $[T_{\pi,\Omega}v](s)=\langle\pi_{s},q_{s}\rangle-\Omega(\pi_{s})$. The regularized Bellman optimality operator is defined as

that is, state-wise, $\pi^{\prime}_{s}=\nabla\Omega^{*}(q_{s})$.

To be really useful, these operators should satisfy the same properties as the classical ones. It is indeed the case (we recall that all proofs are provided in the appendix).

The operator $T_{\pi,\Omega}$ is affine and we have the following properties.

2 Regularized value functions

The regularized operators being contractions, we can define regularized value functions as their unique fixed-points. Notice that from the following definitions, we could also easily derive regularized Bellman operators on $q$-functions.

Noted $v_{\pi,\Omega}$, it is defined as the unique fixed point of the operator $T_{\pi,\Omega}$: $v_{\pi,\Omega}=T_{\pi,\Omega}v_{\pi,\Omega}$. We also define the associated state-action value function $q_{\pi,\Omega}$ as

Thus, the regularized value function is simply the unregularized value of $\pi$ for the reward $r_{\pi}-\Omega(\pi)$, that is $v_{\pi,\Omega}=(I-\gamma P_{\pi})^{-1}(r_{\pi}-\Omega(\pi))$.

Noted $v_{*,\Omega}$, it is the unique fixed point of the operator $T_{*,\Omega}$: $v_{*,\Omega}=T_{*,\Omega}v_{*,\Omega}$. We also define the associated state-action value function $q_{*,\Omega}(s,a)$ as

The function $v_{*,\Omega}$ is indeed the optimal value function, thanks to the following result.

The policy $\pi_{*,\Omega}=\mathcal{G}_{\Omega}(v_{*,\Omega})$ is the unique optimal regularized policy, in the sense that for all $\pi\in\Delta_{\mathcal{A}}^{\mathcal{S}}$, $v_{\pi_{*,\Omega},\Omega}=v_{*,\Omega}\geq v_{\pi,\Omega}$.

When regularizing the MDP, we change the problem at hand. The following result relates value functions in (un)regularized MDPs.

Assume that $L_{\Omega}\leq\Omega\leq U_{\Omega}$. Let $\pi$ be any policy. We have that $v_{\pi}-\frac{U_{\Omega}}{1-\gamma}\mathbf{1}\leq v_{\pi,\Omega}\leq v_{\pi}-\frac{L_{\Omega}}{1-\gamma}\mathbf{1}$ and $v_{*}-\frac{U_{\Omega}}{1-\gamma}\mathbf{1}\leq v_{*,\Omega}\leq v_{*}-\frac{L_{\Omega}}{1-\gamma}\mathbf{1}$.

Regularization changes the optimal policy, the next result shows how it performs in the original MDP.

Assume that $L_{\Omega}\leq\Omega\leq U_{\Omega}$. We have that

3 Related Works

Some of these results already appeared in the literature, in different forms and with specific regularizers. For example, the contraction of $T_{*,\Omega}$ (Prop. 2) was shown in various forms, e.g. (Fox et al., 2016; Asadi & Littman, 2017; Dai et al., 2018), as well as the relation between (un)regularized optimal value functions (Th. 2), e.g. (Lee et al., 2018; Dai et al., 2018). The link to Legendre-Fenchel has also been considered before, e.g. (Dai et al., 2018; Mensch & Blondel, 2018; Richemond & Maginnis, 2017).

The core contribution of Sec. 3 is the regularized Bellman operator, inspired by Nesterov (2005) and Mensch & Blondel (2018). It allows building in a principled and general way regularized MDPs, and generalizing existing results easily. More importantly, it is the core building block of regularized (A)DP, studied in the next sections. The framework and analysis we propose next rely heavily on this formalism.

Regularized Modified Policy Iteration

Having defined the notion of regularized MDPs, we still need algorithms that solve them. As the regularized Bellman operators have the same properties as the classical ones, we can apply classical dynamic programming. Here, we consider directly the modified policy iteration approach (Puterman & Shin, 1978), that we regularize (reg-MPI for short):

Given an initial $v_{0}$, reg-MPI iteratively performs a regularized greedy step to get $\pi_{k+1}$ and a partial regularized evaluation step to get $v_{k+1}$.

With $m=1$, we retrieve a regularized value iteration algorithm, that can be simplified as $v_{k+1}=T_{*,\Omega}v_{k}$ (as $\pi_{k+1}$ is greedy resp. to $v_{k}$, we have $T_{\pi_{k+1},\Omega}v_{k}=T_{*,\Omega}v_{k}$). With $m=\infty$, we obtain a regularized policy iteration algorithm, that can be simplified as $\pi_{k+1}=\mathcal{G}_{\Omega}(v_{\pi_{k},\Omega})$ (indeed, with a slight abuse of notation, $(T_{\pi_{k},\Omega})^{\infty}v_{k-1}=v_{\pi_{k},\Omega}$).

Before studying the convergence and rate of convergence of this general algorithmic scheme (with approximation), we discuss its links to state of the art algorithms (and more generally how it can be practically instantiated).

Most existing schemes consider the negative entropy as the regularizer. Usually, it is also more convenient to work with q-functions. First, we consider the case $m=1$. In the exact case, the regularized value iteration scheme can be written

Getting a practical algorithm may require more work, for example for estimating $\Omega^{*}(q_{\bar{\theta}}(s^{\prime}_{i},\cdot))$ in the case of continuous actions (Haarnoja et al., 2017), but this is the core principle of soft Q-learning (Fox et al., 2016; Schulman et al., 2017). This idea has also been applied using the Tsallis entropy as the regularizer (Lee et al., 2018).

Alternatively, assume that $q_{k}$ has been estimated. One could compute the regularized greedy policy analytically, $\pi_{k+1}(\cdot|s)=\nabla\Omega^{*}(q_{k}(s,\cdot))$. Instead of computing this for any state-action couple, one can generalize this from observed transitions to any state-action couple through a parameterized policy $\pi_{w}$, by minimizing the KL divergence between both distributions:

This is done in SAC (Haarnoja et al., 2018a), with an entropic regularizer (and thus $\nabla\Omega^{*}(q_{k}(s,.))=\frac{\exp q_{k}(s,\cdot)}{\sum_{a}\exp q_{k}(s,a)}$). This is also done in Maximum A Posteriori Policy Optimization (MPO) (Abdolmaleki et al., 2018b) with a KL regularizer (a case we discuss Sec. 5), or by Abdolmaleki et al. (2018a) with more general “conservative” greedy policies.

Back to SAC, $q_{k}$ is estimated using a TD-like approach, by minimizingActually, a separate network is used to estimate the value function, but it is not critical here. for the current policy $\pi$:

Depending on the regularizer, $\Omega^{*}$ or $\nabla\Omega^{*}$ might not be known analytically. In this case, one can still solve the greedy step directly. Recall that the regularized greedy policy satisfies $\pi_{k+1}=\max_{\pi}T_{\pi,\Omega}v_{k}$. In an approximate setting, this amounts to maximizeOne could add a state-dependant baseline to $q_{k}$, eg. $v_{k}$, this does not change the maximizer but can reduce the variance.

This improvement step is used by Riedmiller et al. (2018) with an entropy, as well as by TRPO (up to the fact that the objective is constrained rather than regularized), with a KL regularizer (see Sec. 5).

To sum up, for any regularizer $\Omega$, with $m=1$ one can concatenate greedy and evaluation steps as in Eq. (21), with $m\geq 1$ one can estimate the greedy policy using either Eqs. (23) or (26), and estimate the q-function using Eq. 24, either performed $m$ times repeatedly or combined with $m$-step rollouts, possibly combined with off-policy correction such as importance sampling or Retrace (Munos et al., 2016).

2 Analysis

We analyze the propagation of errors of the scheme depicted in Eq. (19), and as a consequence, its convergence and rate of convergence. To do so, we consider possible errors in both the (regularized) greedy and evaluation steps,

with $\pi_{k+1}=\mathcal{G}^{\epsilon^{\prime}_{k+1}}_{\Omega}(v_{k})$ meaning that for any policy $\pi$, we have $T_{\pi,\Omega}v_{k}\leq T_{\pi_{k+1},\Omega}v_{k}+\epsilon^{\prime}_{k+1}$. The following analysis is basically the same as the one of Approximate Modified Policy Iteration (AMPI) (Scherrer et al., 2015), thanks to the results of Sec. 3 (especially Prop. 2).

The distance we bound is the loss $l_{k,\Omega}=v_{*,\Omega}-v_{\pi_{k},\Omega}$. The bound will involve the terms $d_{0}=v_{*,\Omega}-v_{0}$ and $b_{0}=v_{0}-T_{\pi_{1},\Omega}v_{0}$. It requires also defining the following.

We first state a point-wise bound on the loss. This is the same bound as for AMPI, generalized to regularized MDPs.

After $k$ iterations of scheme (27), we have

with $h(k)=2\sum_{j=k}^{\infty}\Gamma^{j}|d_{0}|$ or $h(k)=2\sum_{j=k}^{\infty}\Gamma^{j}|b_{0}|$.

Let $\rho$ and $\mu$ be distributions. Let $p$, $q$ and $q^{\prime}$ such that $\frac{1}{q}+\frac{1}{q^{\prime}}=1$. Define the concentrability coefficients $C_{q}^{i}=\frac{1-\gamma}{\gamma^{i}}\sum_{j=i}^{\infty}\gamma^{j}\max_{\pi_{1},\dots,\pi_{j}}\left\|\frac{\rho P_{\pi_{1}}P_{\pi_{2}}\dots P_{\pi_{j}}}{\mu}\right\|_{q,\mu}$. After $k$ iterations of scheme (27), the loss satisfies

with $g(k)=\frac{2\gamma^{k}}{1-\gamma}(C_{q}^{i})^{\frac{1}{p}}\min(\|d_{0}\|_{pq^{\prime},\mu},\|b_{0}\|_{pq^{\prime},\mu})$.

As this is the same bound (up to the fact that it deals with regularized MDPs) as the one of AMPI, we refer to Scherrer et al. (2015) for a broad discussion about it. It is similar to other error propagation analyses in reinforcement learning, and generalizes those that could be obtained for regularized value or policy iteration. The factor $m$ does not appear in the bound. This is also discussed by Scherrer et al. (2015), but basically this depends on where the error is injected. We could derive a regularized version of Classification-based Modified Policy Iteration (CBMPI, see Scherrer et al. (2015) again) and make it appear.

So, we get the same bound for reg-MPI that for unregularized AMPI, no better nor worse. This is a good thing, as it justifies considering regularized MDPs, but it does no explain the good empirical results of related algorithms.

With regularization, policies will be more stochastic than in classical approximate DP (that tends to produce deterministic policies). Such stochastic policies can induce lower concentrability coefficients. We also hypothesize that regularizing the greedy step helps controlling the related approximation error, that is the $\|\epsilon^{\prime}_{k-i}\|_{pq^{\prime},\mu}$ terms. Digging this question would require instantiating more the algorithmic scheme and performing a finite sample analysis of the resulting optimization problems. We left this for future work, and rather pursue the general study of solving regularized MDPs, with varying regularizers now.

Mirror Descent Modified Policy Iteration

Solving a regularized MDP provides a solution that differs from the one of the unregularized MDP (see Thm. 2). The problem we address here is estimating the original optimal policy while solving regularized greedy steps. Instead of considering a fixed regularizer $\Omega(\pi)$, the key idea is to penalize a divergence between the policy $\pi$ and the policy obtained at the previous iteration of an MPI scheme. We consider more specifically the Bregman divergence generated by the strongly convex regularizer $\Omega$.

Let $\pi^{\prime}$ be some given policy (typically $\pi_{k}$, when computing $\pi_{k+1}$), the Bregman divergence generated by $\Omega$ is

For example, the KL divergence is generated by the negative entropy: $\operatorname*{KL}(\pi_{s}||\pi^{\prime}_{s})=\sum_{a}\pi_{s}(a)\ln\frac{\pi_{s}(a)}{\pi_{s}^{\prime}(a)}$. With a slight abuse of notation, as before, we will write

This divergence is always positive, it satisfies $\Omega_{\pi^{\prime}}(\pi^{\prime})=0$, and it is strongly convex in $\pi$ (so Prop. 1 applies).

We consider a reg-MPI algorithmic scheme with a Bregman divergence replacing the regularizer. For the greedy step, we simply consider $\pi_{k+1}=\mathcal{G}_{\Omega_{\pi_{k}}}(v_{k})$, that is

This is similar to the update of the Mirror Descent (MD) algorithm in its proximal form (Beck & Teboulle, 2003), with $-q_{k}$ playing the role of the gradient in MD. Therefore, we will call this approach Mirror Descent Modified Policy Iteration (MD-MPI). For the partial evaluation step, we can regularize according to the previous policy $\pi_{k}$, that is $v_{k+1}=(T_{\pi_{k+1},\Omega_{\pi_{k}}})^{m}v_{k}$, or according to the current policy $\pi_{k+1}$, that is $v_{k+1}=(T_{\pi_{k+1},\Omega_{\pi_{k+1}}})^{m}v_{k}$. As $\Omega_{\pi_{k+1}}(\pi_{k+1})=0$, this simplifies as $v_{k+1}=(T_{\pi_{k+1}})^{m}v_{k}$, that is a partial unregularized evaluation.

To sum up, we will consider two general algorithmic schemes based on a Bregman divergence, MD-MPI types 1 and 2 respectively defined as

and both initialized with some $v_{0}$ and $\pi_{0}$.

To derive practical algorithms, the recipes provided in Sec. 4.1 still apply, just replacing $\Omega$ by $\Omega_{\pi_{k}}$. If $m=1$, greedy and evaluation steps can be concatenated (only for MD-MPI type 1). In the general case ($m\geq 1$) the greedy policy (for MD-MPI types 1 and 2) can be either directly estimated (Eq. (26)) or trained to generalize the analytical solution (Eq. (23)). The partial evaluation can be done using a TD-like approach, either done repeatedly while keeping the policy fixed or considering $m$-step rollouts. Specifically, in the case of a KL divergence, one could use the fact that $\Omega_{\pi_{k}}^{*}(q_{k}(s,\cdot))=\ln\sum_{a}\pi_{k}(a|s)\exp q_{k}(s,a)$ and that $\nabla\Omega_{\pi_{k}}^{*}(q_{k}(s,\cdot))=\frac{\pi_{k}(\cdot|s)\exp q_{k}(s,\cdot)}{\sum_{a}\pi_{k}(a|s)\exp q_{k}(s,a)}$.

This general algorithmic scheme allows recovering state of the art algorithms. For example, MD-MPI type 2 with $m=\infty$ and a KL divergence as the regularizer is TRPO (Schulman et al., 2015) (with a direct optimization of the regularized greedy step, as in Eq. (26), up to the use of a constraint instead of a regularization). DPP can be seen as a reparametrizationIndeed, if one see MD-MPI as a Mirror Descent approach, one can see DPP as a dual averaging approach, somehow updating a kind of cumulative q-functions directly in the dual. However, how to generalize this beyond the specific DPP algorithm is unclear, and we let it for future work. of MD-MPI type 1 with $m=1$ (Azar et al., 2012, Appx. A). MPO (Abdolmaleki et al., 2018b) is derived from an expectation-maximization principle, but it can be seen as an instantiation of MD-MPI type 2, with a KL divergence, a greedy step similar to Eq. (23) (up to additional regularization) and an evaluation step similar to Eq. (24) (without regularization, as in type 2, with m-step return and with the Retrace off-policy correction). This also generally applies to the approach proposed by Abdolmaleki et al. (2018a) (up to an additional subtelty in the greedy step consisting in decoupling updates for the mean and variance in the case of a Gaussian policy).

2 Analysis

Here, we propose to analyze the error propagation of MD-MPI (and thus, its convergence and rate of convergence). We think this is an important topic, as it has only been partly studied for the special cases discussed in Sec. 5.1. For example, DPP enjoys an error propagation analysis in supremum norm (yet it is a reparametrization of a special case of MD-MPI, so not directly covered here), while TRPO or MPO are only guaranteed to have monotonic improvements, under some assumptions. Notice that we do not claim that our analysis covers all these cases, but it will provide the key technical aspects to analyze similar schemes (much like CBMPI compared to AMPI, as discussed in Sec. 4.2 or by Scherrer et al. (2015); where the error is injected changes the bounds).

In Sec. 4.2, the analysis was a straightforward adaptation of the one of AMPI, thanks to the results of Sec. 3 (the regularized quantities behave like their unregularized counterparts). It is no longer the case here, as the regularizer changes over iterations, depending on what has been computed so far. We will notably need a slightly different notion of approximate regularized greediness.

Write $J_{k}(\pi)$ the (negative) optimization problem corresponding to the Bregman divergence-regularized greediness (that is, negative regularized Bellman operator of $\pi$ applied to $v_{k}$):

We write $\pi_{k+1}\in\mathcal{G}^{\epsilon^{\prime}_{k+1}}_{\Omega_{\pi_{k}}}(v_{k})$ if for any policy $\pi$ the policy $\pi_{k+1}$ satisfies

In other words, $\pi_{k+1}\in\mathcal{G}^{\epsilon^{\prime}_{k+1}}_{\Omega_{\pi_{k}}}(v_{k})$ means that $\pi_{k+1}$ is $\epsilon^{\prime}_{k+1}$-close to satisfying the optimality condition, which might be slightly stronger than being $\epsilon^{\prime}_{k+1}$-close to the optimal (as for AMPI or reg-MPI). Given this, we consider MD-MPI with errors in both greedy and evaluation steps, type 1

The quantity we are interested in is $v_{*}-v_{\pi_{k}}$, that is suboptimality in the unregularized MDP, while the algorithms compute new policies with a regularized greedy operator. So, we need to relate regularized and unregularized quantities when using a Bregman divergence based on the previous policy. The next lemma is the key technical result that allows analyzing MD-MPI.

Assume that $\pi_{k+1}\in\mathcal{G}^{\epsilon^{\prime}_{k+1}}_{\Omega_{\pi_{k}}}(v_{k})$, as defined in Def. 5. Then, the policy $\pi_{k+1}$ is $\epsilon^{\prime}_{k+1}$-close to the regularized greedy policy, in the sense that for any policy $\pi$

Moreover, we can relate the (un)regularized Bellman operators applied to $v_{k}$. For any policy $\pi$ (so notably for the unregularized optimal policy $\pi_{*}$), we have

We’re interested in bounding the loss $l_{k}=v_{*}-v_{\pi_{k}}$, or some related quantity, for each type of MD-MPI. To do so, we introduce quantities similar to the ones of the AMPI analysis (Scherrer et al., 2015), defined respectively for types 1 and 2: 1) The distance between the optimal value function and the value before approximation at the $k^{\text{th}}$ iteration, $d_{k}^{1}=v_{*}-(T_{\pi_{k},\Omega_{\pi_{k-1}}})^{m}v_{k-1}=v_{*}-(v_{k}-\epsilon_{k})$ and $d_{k}^{2}=v_{*}-(T_{\pi_{k}})^{m}v_{k-1}=v_{*}-(v_{k}-\epsilon_{k})$; 2) The shift between the value before approximation and the policy value a iteration $k$, $s_{k}^{1}=(T_{\pi_{k},\Omega_{\pi_{k-1}}})^{m}v_{k-1}-v_{\pi_{k}}=(v_{k}-\epsilon_{k})-v_{\pi_{k}}$ and $s_{k}^{2}=(T_{\pi_{k}})^{m}v_{k-1}-v_{\pi_{k}}=(v_{k}-\epsilon_{k})-v_{\pi_{k}}$; 3) the Bellman residual at iteration $k$, $b^{1}_{k}=v_{k}-T_{\pi_{k+1},\Omega_{\pi_{k}}}v_{k}$ and $b^{2}_{k}=v_{k}-T_{\pi_{k+1}}v_{k}$.

For both types ($h\in\{1,2\}$), we have that $l_{k}^{h}=d_{k}^{h}+s_{k}^{h}$, so bounding the loss requires bounding these quantities, which is done in the following lemma (quantities related to both types enjoy the same bounds).

Let $k\geq 1$, define $x_{k}=(I-\gamma P_{\pi_{k}})\epsilon_{k}+\epsilon^{\prime}_{k+1}$ and $y_{k}=-\gamma P_{\pi_{*}}\epsilon_{k}+\epsilon^{\prime}_{k+1}$, as well as $\delta_{k}(\pi_{*})=D_{\Omega}(\pi_{*}||\pi_{k})-D_{\Omega}(\pi_{*}||\pi_{k+1})$. We have for $h\in\{1,2\}:$

These bounds are almost the same as the ones of AMPI (Scherrer et al., 2015, Lemma 2), up to the additional $\delta_{k}(\pi_{*})$ term in the bound of the distance $d_{k}^{h}$. One can notice that summing these terms gives a telescopic sum: $\sum_{k=0}^{K-1}\delta_{k}(\pi_{*})=D_{\Omega}(\pi_{*}||\pi_{0})-D_{\Omega}(\pi_{*}||\pi_{K})\leq D_{\Omega}(\pi_{*}||\pi_{0})\leq\sup_{\pi}D_{\Omega}(\pi||\pi_{0})$. For example, if $D_{\Omega}$ is the KL divergence and $\pi_{0}$ the uniform policy, then $\|\sup_{\pi}D_{\Omega}(\pi||\pi_{0})\|_{\infty}=\ln|\mathcal{A}|$. This suggests that we must bound the regret $L_{K}$ defined as

Define $R_{\Omega_{\pi_{0}}}=\|\sup_{\pi}D_{\Omega}(\pi||\pi_{0})\|_{\infty}$, after $K$ iterations of MD-MPI, for $h=1,2$, the regret satisfies

with $h(k)=2\sum_{j=k}^{\infty}\Gamma^{j}|d_{0}|$ or $h(k)=2\sum_{j=k}^{\infty}\Gamma^{j}|b_{0}|$.

Let $\rho$ and $\mu$ be distributions over states. Let $p$, $q$ and $q^{\prime}$ be such that $\frac{1}{q}+\frac{1}{q^{\prime}}=1$. Define the concentrability coefficients $C_{q}^{i}$ as in Cor. 1. After $K$ iterations, the regret satisfies

with $g(k)=2\sum_{k=1}^{K}\frac{\gamma^{k}}{1-\gamma}(C_{q}^{k})^{\frac{1}{p}}\min(\|d_{0}\|_{pq^{\prime},\mu},\|b_{0}\|_{pq^{\prime},\mu})$.

This result bounds the regret, while it is usually the loss that is bounded. Both can be related as follows.

For any $p\geq 1$ and distribution $\rho$, we have $\min_{1\leq k\leq K}\|v_{*}-v_{\pi_{k}}\|_{1,\rho}\leq\frac{1}{K}\|L_{K}\|_{p,\rho}.$

This means that if we can control the average regret, then we can control the loss of the best policy computed so far. This suggests that practically we should not use the last policy, but this best policy.

From Cor. 2 can be derived the convergence and rate of convergence of MD-MPI in the exact case.

Both MD-MPI type 1 and 2 enjoy the following rate of convergence, when no approximation is done ($\epsilon_{k}=\epsilon^{\prime}_{k}=0$),

In classical DP and in regularized DP (see Cor. 1), there is a linear convergence rate (the bound is $\frac{2\gamma^{K}}{1-\gamma}\|v_{*}-v_{0}\|_{\infty}$), while in this case we only have a logarithmic convergence rate. We also pay an horizon factor (square dependency in $\frac{1}{1-\gamma}$ instead of linear). This is normal, as we bound the regret instead of the loss. Bounding the regret in classical DP would lead to the bound of Cor. 3 (without the $R_{\Omega_{\pi_{0}}}$ term).

The convergence rate of the loss of MD-MPI is an open question, but a sublinear rate is quite possible. Compared to classical DP, we slow down greediness by adding the Bregman divergence penalty. Yet, this kind of regularization is used in an approximate setting, where it favors stability empirically (even if studying this further would require much more work regarding the $\|\epsilon^{\prime}_{k}\|$ term, as discussed in Sec. 4.2).

As far as we know, the only other approach that studies a DP scheme regularized by a divergence and that offers a convergence rate is DPP, up to the reparameterization we discussed earlier. MD-MPI has the same upper-bound as DPP in the exact case (Azar et al., 2012, Thm. 2). However, DPP bounds the loss, while we bound a regret. This means that if the rate of convergence of our loss can be sublinear, it is superlogarithmic (as the rate of the regret is logarithmic), while the rate of the loss of DPP is logarithmic.

To get more insight on Cor. 2, we can group the terms differently, by grouping the errors.

With the same notations as Cor. 2, we have

with $E_{i}=\sum_{j=1}^{i}\|\epsilon_{j}\|_{pq^{\prime},\mu}$ and $E^{\prime}_{i}=\sum_{j=1}^{i}\|\epsilon^{\prime}_{j}\|_{pq^{\prime},\mu}$.

Compared to the bound of AMPI (Scherrer et al., 2015, Thm. 7), instead of propagating the errors, we propagate the sum of errors over previous iterations normalized by the total number of iterations. So, contrary to approximate DP, it is no longer the last iterations that have the highest influence on the regret. Yet, we highlight again the fact that we bound a regret, and bounding the regret of AMPI would provide a similar result.

To get further insight, we can express the bound using different concentrability coefficients.

Define the concentrability coefficient $C_{q}^{l,k}$ as $C_{q}^{l,k}=\frac{(1-\gamma)^{2}}{\gamma^{l}-\gamma^{k}}\sum_{i=l}^{k-1}\sum_{j=i}^{\infty}c_{q}(j)$, the regret then satisfies

with $f(k)=\frac{\gamma-\gamma^{K+1}}{(1-\gamma)^{2}}(C_{q}^{1,K+1})^{\frac{1}{p}}\min(\|d_{0}\|_{pq^{\prime},\mu},\|b_{0}\|_{pq^{\prime},\mu})+\frac{1-\gamma^{K}}{(1-\gamma)^{2}}R_{\Omega_{\pi_{0}}}$.

We observe again that contrary to ADP, the last iteration does not have the highest influence, and we do not enjoy a decrease of influence at the exponential rate $\gamma$ towards the initial iterations. However, we bound a different quantity (regret instead of loss), that explains this behavior. Here again, bounding the regret in AMPI would lead to the same bound (up to the term $R_{\Omega_{\pi_{0}}}$). Moreover, sending $p$ and $K$ to infinity, defining $\epsilon=\sup_{j}\|\epsilon_{j}\|_{\infty}$ and $\epsilon^{\prime}=\sup_{j}\|\epsilon^{\prime}_{j}\|_{\infty}$, we get $\limsup\limits_{K\rightarrow\infty}\frac{1}{K}\|L_{K}\|_{\infty}\leq\frac{2\gamma\epsilon+\epsilon^{\prime}}{(1-\gamma)^{2}}$, which is the classical asymptotical bound for approximate value and policy iterations (Bertsekas & Tsitsiklis, 1996) (usually stated without greedy error). It is generalized here to an approximate MPI scheme regularized with a Bregman divergence.

Conclusion

We have introduced a general theory of regularized MDPs, where the usual Bellman evaluation operator is modified by either a fixed convex function or a Bregman divergence between consecutive policies. For both cases, we proposed a general algorithmic scheme based on MPI. We shown how many (variations of) existing algorithms could be derived from this general algorithmic scheme, and also analyzed and discussed the related propagation of errors.

We think that this framework can open many perspectives, among which links between (approximate) DP and proximal convex optimization (going beyond mirror descent), temporal consistency equations (roughly regularized Bellman residuals), regularized policy search (maximizing the expected regularized value function), inverse reinforcement learning (thanks to uniqueness of greediness in this regularized framework) or zero-sum Markov games (regularizing the two-player Bellman operators). We develop more these points in the appendix.

This work also lefts open questions, such as combining the propagation of errors with a finite sample analysis, or what specific regularizer one should choose for what context. Some approaches also combine a fixed regularizer and a divergence (Akrour et al., 2018), a case not covered here and worth being investigated.

References

Appendix A Proofs of section 3

In this section, we prove the results of Sec. 3. We start with the properties of the regularized Bellman operators.

We can write $T_{\pi,\Omega}v=r_{\pi}-\Omega(\pi)+\gamma P_{\pi}v$, it is obviously affine (in $v$). Then, we show that the operators are monotonous. For the evaluation operator, we have

Then, we show the distributivity property. For the evaluation operator, we have

For the optimality operator, for any $s\in\mathcal{S}$, we have

Lastly, we study the contraction of both operators. For the evaluation operator, we have

So, the contraction is the same as the one of the unregularized operator. For the optimality operator, we have that

Pick $s\in\mathcal{S}$, and without loss of generality assume that $[T_{*,\Omega}v_{1}](s)\geq[T_{*,\Omega}v_{2}](s)$. Write also $\pi_{1}=\mathcal{G}_{\Omega}(v_{1})$ and $\pi_{2}=\mathcal{G}_{\Omega}(v_{2})$. We have

Then, we show that in a regularized MDP, the policy greedy respectively to the optimal value function is indeed the optimal policy, and is unique.

The uniqueness of $\pi_{*,\Omega}$ is a consequence of the strong convexity of $\Omega$, see Prop. 1. On the other hand, by definition of the greediness, we have

By direct induction, for any $n\geq 1$, $T_{*,\Omega}^{n}v\geq T^{n}_{\pi,\Omega}v$. Taking the limit as $n\rightarrow\infty$, we conclude that $v_{*,\Omega}\geq v_{\pi,\Omega}$. ∎

Next, we relate regularized and unregularized value functions (for a given policy, and for the optimal value function).

We work on the left inequality first. We have

Taking the limit as $n\rightarrow\infty$ we obtain

Then, the proof is the same as above, switching evaluation and optimality operators. ∎

Lastly, we show how good is the optimal policy of the regularized MDP for the original problem (unregularized MDP).

The right inequality is obvious, as for any $\pi$, $v_{*}\geq v_{\pi}$. For the left inequality,

Appendix B Proofs of section 4

The results of section 4 do not need to be proven. Indeed, we have shown in Sec. 3 that all involved quantities of regularized MDPs satisfy the same properties as their unregularized counterpart. Therefore, the proofs of these results are identical to the proofs provided by Scherrer et al. (2015), up to the replacement of value functions, Bellman operators, and so on, by their regularized counterparts. The proofs for Mirror Descent Modified Policy Iteration (Sec. 5) are less straightforward.

Appendix C Proofs of section 5

As a prerequisite of Lemma 1, we need the following result.

This is the classical three-point identity of Bregman divergences, and can be checked by calculus:

Now, we can prove the key lemma of MD-MPI.

and let $\pi_{k+1}\in\mathcal{G}^{\epsilon^{\prime}_{k+1}}_{\Omega_{\pi_{k}}}(v_{k})$, that is $\langle\nabla J_{k}(\pi_{k+1}),\pi-\pi_{k+1}\rangle+\epsilon^{\prime}_{k+1}\geq 0$. By convexity of $J_{k}$, for any policy $\pi$, we have

This is the first result stated in Lemma 1.

Next, we relate (un)regularized quantities. We start with the following decomposition

Taking the gradient of $J_{k}$ (by using the definition of the Bregman divergence), we get

where we used in the last inequality the fact that $\langle q_{k},\pi\rangle=T_{\pi}v_{k}$. From the definition of the regularized Bellman operator, we have that $T_{\pi_{k+1}}v_{k}-D_{\Omega}(\pi_{k+1}||\pi_{k})=T_{\pi_{k+1},\Omega_{\pi_{k}}}v_{k}$, so Eq. (99) is equivalent to the second result of Lemma 1:

As the Bregman divergence is positive, $-D_{\Omega}(\pi||\pi_{k+1})\leq 0$, and thus Eq. (99) implies the last result of Lemma 1:

Next, we prove the bounds for $b^{h}_{k}$, $s^{h}_{k}$ and $d^{h}_{k}$, for $h=1,2$ (if the bounds are the same, the proofs differ).

We start by bounding the quantities for MD-MPI type 1. First, we consider the Bellman residual:

In the previous equations, we used the following facts:

$T_{\pi_{k}}v_{k}=T_{\pi_{k},\Omega_{\pi_{k}}}v_{k}$ as $\Omega_{\pi_{k}}(\pi_{k})=0$.

We used two facts. First, $T_{\pi_{k}}v_{k}\geq T_{\pi_{k}}v_{k}-\Omega_{\pi_{k-1}}(\pi_{k})=T_{\pi_{k},\Omega_{\pi_{k-1}}}v_{k}$, as $\Omega_{\pi_{k-1}}(\pi_{k})\geq 0$. Second, by Lemma 1, $T_{\pi_{k},\Omega_{\pi_{k}}}v_{k}-T_{\pi_{k+1},\Omega_{\pi_{k}}}v_{k}\leq\epsilon^{\prime}_{k+1}$.

We used two facts. First, generally speaking, we have $T_{\pi,\Omega}(v_{1}+v_{2})=T_{\pi,\Omega}v_{1}+\gamma P_{\pi}v_{2}$ (as $T_{\pi,\Omega}$ is affine). Second, by definition $x_{k}=(I-\gamma P_{\pi_{k}})\epsilon_{k}+\epsilon^{\prime}_{k+1}$.

By definition, $v_{k}=(T_{\pi_{k},\Omega_{\pi_{k-1}}})^{m}v_{k-1}+\epsilon_{k}$.

In the previous equations, we used the following facts:

Generally speaking, if $\Omega\geq 0$ then $v_{\pi,\Omega}-v_{\pi}\leq 0$ (see Prop. 3).

In the previous equations, we used the following facts:

By definition of $d^{1}_{k}=v_{*}-(v_{k}-\epsilon_{k})$ and $y_{k}=-\gamma P_{\pi_{*}}\epsilon_{k}+\epsilon^{\prime}_{k+1}$.

The proofs for the quantities involved in MD-MPI type 2 are similar, even if their definition differ. First, we consider the Bellman residual

In the previous equations, we used the following facts:

This is because $\Omega_{\pi_{k}}(\pi_{k+1})\geq 0$ and by definition of $T_{\pi,\Omega}v=T_{\pi}v-\Omega(\pi)$.

It uses the fact that $T_{\pi_{k}}v_{k}=T_{\pi_{k},\Omega_{\pi_{k}}}v_{k}$ (as $\Omega_{\pi_{k}}(\pi_{k})=0$).

This is by definition of $x_{k}=\epsilon_{k}-\gamma P_{\pi_{k}}\epsilon_{k}+\epsilon^{\prime}_{k+1}$.

This is by definition of $v_{k}=(T_{\pi_{k}})^{m}v_{k-1}+\epsilon_{k}$.

Then, we bound the shift $s_{k}^{2}$, the technique being the same as before:

To finish with, we prove the bound on the distance

Now, we will show the component-wise bound on the regret $L_{k}$ of Thm. 4

The proof is similar to the one of AMPI (Scherrer et al., 2015, Lemma 2), up to the additional term $\delta_{k}(\pi_{*})$ and to the different bounded quantity. We will make use of the notation $\Gamma$, defined in Def. 4, and we will write $\Gamma_{*}$ if only the stochastic kernel induced by the optimal policy $\pi_{*}$ is involved. In other words, we write $\Gamma_{*}^{j}=(\gamma P_{\pi_{*}})^{j}$.

As the bound is the same for $h=1,2$, we remove the upperscript (and reintroduce it only when necessary, that is when going back to the core definition of these quantities). By direct induction, we get

Therefore, the loss $l_{k}$ can be bounded as (defining $\mathcal{L}_{k}$ at the same time)

The loss $\mathcal{L}_{k}$ is exactly of the same form as the one of AMPI, we’ll take advantage of this later. From this bound on the loss $l_{k}$, we can bound the regret as:

We will first work on the last double sum. For this, we define $\Delta_{j}(\pi_{*})=\sum_{k=0}^{j}\delta_{k}(\pi_{*})$. We have

For the last line, we used the fact that $\Gamma_{*}$ only involves the $P_{\pi_{*}}$ transition kernel, that does not depend on any iteration. Now, we can bound the term $\Delta_{k}(\pi_{*})$, for any $k\geq 0$ as follows. Let write $R_{\Omega_{\pi_{0}}}=\|\sup_{\pi}D_{\Omega}(\pi||\pi_{0})\|_{\infty}$, we have

Given the definition of $\Gamma$, we have that $\Gamma^{j}\mathbf{1}=\gamma^{j}\mathbf{1}$, so

Next, we work on the term $\mathcal{L}_{k}$. As stated before, it is exactly the same as the one of the AMPI analysis, and the proof of Scherrer et al. (2015, Lemma 2) applies almost readily, we do not repeat it fully here. The only difference that appears and that induces a slight modification of the bound (on $\mathcal{L}_{k})$) is how $b_{0}$ and $d_{0}$ are related, that will modify the $\eta_{k}$ term of the original proof. We will link $b_{0}$ and $d_{0}$ for both types of MD-MPI.

For MD-MPI type 1 (with the natural convention that $\epsilon_{0}=0$), we have that

where we used in the penultimate line the fact that $\delta_{0}(\pi_{*})=D_{\Omega}(\pi_{*}||\pi_{0})-D_{\Omega}(\pi_{*}||\pi_{1})\leq D_{\Omega}(\pi_{*}||\pi_{0})$ and in the last line the same bounding as before. So, the link between $b_{0}^{1}$ and $d_{0}^{1}$ is the same as for AMPI, up to the additional $R_{\Omega_{\pi_{0}}}\mathbf{1}$ term.

For MD-MPI type 2, we have (with the same convention)

Combining this with the part of the proof that does not change, and that we do not repeat, we get the following bound on $\mathcal{L}_{k}$:

Combining Eqs (158) and (168) into Eq. (152), we can bound the regret:

To prove Cor. 2, we will need a result from Scherrer et al. (2015), that we recall first.

Let $\mathcal{I}$ and $(\mathcal{J}_{i})_{i\in\mathcal{I}}$ be sets of non-negative integers, $\{\mathcal{I}_{1},\dots,\mathcal{I}_{n}\}$ be a partition of $\mathcal{I}$, and $f$ and $(g_{i})_{i\in\mathcal{I}}$ be functions satisfying

Then, for all $p$, $q$ such that $\frac{1}{p}+\frac{1}{q}=1$ and for all distributions $\rho$ and $\mu$, we have

with the following concentrability coefficients,

The proof is an application of Lemma 4 to Thm. 4. We define $\mathcal{I}=\{1,2,\dots,K^{2}+K+1\}$ and the associated trivial partition (that is, $\mathcal{I}_{i}=\{i\}$). For each $i\in\mathcal{I}$ we define

The results follows by applying Lemma 4 and using the fact that $\sum_{j\geq i}\gamma^{j}=\frac{\gamma^{i}}{1-\gamma}$ ∎

The proof of Prop. 4 is a basic application of the Hölder inequality.

We write $\circ$ the Hadamard product. Recall that $l_{k}=v_{*}-v_{\pi_{k}}\geq 0$ and that $L_{K}=\sum_{k=1}^{K}l_{k}$. Notice that the sequence $v_{\pi_{k}}$ is not necessarily monotone, even without approximation error. On one side, we have that

On the other side, with $q$ such that $\frac{1}{p}+\frac{1}{q}=1$ we have that

where we used the Hölder inequality. Combining both equations provides the stated result. ∎

Cor. 3 is a direct consequence of Cor. 2.

Taking the limit of Cor. 2 as $p\rightarrow\infty$, when the errors are null, gives

where we used the fact that $\sum_{k=1}^{K}\gamma^{k}=\gamma\frac{1-\gamma^{K}}{1-\gamma}$. The result follows by grouping terms and using $d_{0}=v_{*}-v_{0}$. ∎

The proof of Cor. 4 is mainly a manipulation of sums.

We only need to work on the first two sums. To shorten the notations, write $\alpha_{i}=\frac{\gamma^{i}}{1-\gamma}(C_{q}^{i})^{\frac{1}{p}}$, $\beta_{i}=\|\epsilon_{k-i}\|_{pq^{\prime},\mu}$ and $\beta^{\prime}_{i}=\|\epsilon^{\prime}_{k-i}\|_{pq^{\prime},\mu}$. We have:

The result follows by reinjecting this in Cor. 2 after having replaced $\alpha_{i}$, $\beta_{i}$ and $\beta^{\prime}_{i}$. ∎

The proof of Cor. 5 basically consists in the application of Lemma 4 to a rewriting of Thm. 4.

We start by rewriting the two first sums. For the first one, we have

Thus, the bound on the loss can be writen as

In order to apply Lemma 4 to this bound, we consider $\mathcal{I}=\{1,2,\dots 2K+1\}$ and the associated trivial partition $\mathcal{I}_{i}=\{i\}$. For each $i\in\mathcal{I}$, we define:

With the $c_{q}$ term defined in Lemma 4, using the fact that $\sum_{i=l}^{k-1}\sum_{j=i}^{\infty}\gamma^{j}=\frac{\gamma^{l}-\gamma^{k}}{(1-\gamma)^{2}}$, as well as the following concentrability coefficient,

we get the following bound on the regret:

Appendix D Perspectives on regularized MDPs

Here, we discuss in more details the perspectives briefly mentioned in Sec. 6.

We have shown how MPI regularized by a Bregman divergence is related to Mirror Descent. The computation of the regularized greedy policy is similar to a mirror descent step, where the $q$-function plays the role of the negative subgradient. In this sense, the policy lives in the primal space while the $q$-function lives in the dual space. It would be interesting to take inspiration from proximal convex optimization to derive new dynamic programming approaches, for example based on Dual Averaging (Nesterov, 2009) or Mirror Prox (Nemirovski, 2004).

For example, consider the case of a fixed regularizer. We have seen that it leads to a different solution than the original one (see Thm. 2). Usually, one considers a scaled negative entropy as such a regularizerThis is the case for SAC or soft Q-learning, for example. Sometimes, it is the reward that is scaled, but both are equivalent., $\Omega(\pi(\cdot|s))=\alpha\sum_{a}\pi(a|s)\ln\pi(a|s)$. The choice of this parameter is important practically and problem-dependent: too high and the solution of the regularized problem will be very different from the original one, too low and the algorithm will not benefit from the regularization. A natural idea is to vary the weight of the regularizer over iterations (Peters et al., 2010; Abdolmaleki et al., 2018a; Haarnoja et al., 2018b), much like a learning rate in a gradient descent approach.

More formally, in our framework, write $\Omega_{k}=\alpha_{k}\Omega$ and consider the following weighted reg-MPI scheme,

with $\mathcal{G}^{\epsilon^{\prime}_{k+1}}_{\Omega_{k}}(v_{k})$ as defined in Sec. 4.2: for any policy $\pi$, $T_{\pi,\Omega_{k}}v_{k}\leq T_{\pi_{k+1},\Omega_{k}}v_{k}+\epsilon^{\prime}_{k+1}$. By applying the proof techniques developed previously, one can obtain easily the following result.

Define $R_{\Omega}=\|\sup_{\pi}\Omega(\pi)\|_{\infty}$. Assume that the series $(\alpha_{k})_{k\geq 0}$ is positive and decreasing, and that the regularizer $\Omega$ is positive (without loss of generality). After $K$ iterations of the preceding weighted reg-MPI scheme, the regret satisfies

with $h(k)=2\sum_{j=k}^{\infty}\Gamma^{j}|d_{0}|$ or $h(k)=2\sum_{j=k}^{\infty}\Gamma^{j}|b_{0}|$.

The proof is similar to the one of MD-MPI, as it bounds the regret, but also simpler as it does not require Lemma 1. The principle is still to bound the distance $d_{k}$ and the shift $s_{k}$, that both require bounding the Bellman residual $b_{k}$. From this, one can bound the loss $l_{k}=d_{k}+s_{k}$, and then the regret $L_{K}=\sum_{k=1}^{K}l_{k}$. We only specify what changes compared to the previous proofs.

Bounding the shift $s_{k}$ is done as before, and one get the same bound:

The rest of the bounding is similar to MD-MPI, and we get

So, this is similar to the bound of MD-MPI, with the term $\alpha_{k}R_{\Omega}\mathbf{1}$ replacing the term $\delta_{k}(\pi_{*})$. For the Bellman residual, we have

where we used the facts that $\alpha_{k}\leq\alpha_{k-1}$ and that $\Omega\geq 0$ for bounding the first term:

The rest of the bounding is as before and gives $b_{k}\leq(\gamma P_{\pi_{k}})^{m}b_{k-1}+x_{k}$. From these bounds, one can bound $L_{k}$ as previously. ∎

D.2 Temporal consistency equations

Thanks to $\Omega$, the regularized greedy policies are unique, and thus is the regularized optimal policy. The pair of optimal policy and optimal value function can be characterized as follows.

The optimal policy and optimal value function in a regularized MDP are the unique functions satisfying

This provides a general way to estimate the optimal policy. For example, if $\Omega$ is the negative entropy, this set of equations simplifies to

This has been used by Nachum et al. (2017) or Dai et al. (2018), where it is called “temporal consistency equation”, to estimate the optimal value-policy pair by minimizing the related residual,

This idea has also been extended to Tsallis entropy (Nachum et al., 2018). In this case, the set of equations does not simplify as nicely as with the Shannon entropy. Instead, the approach consists in considering the Lagrangian derived from the Legendre-Fenchel transform (and the resulting temporal consistency equation involves Lagrange multipliers, that have to be learnt too). This idea could be extended to other regularizers. One could also replace the regularizer $\Omega$ by a Bregman divergence, and estimate the optimal policy by solving a sequence of temporal consistency equations.

D.3 Regularized policy gradient

Policy search approaches often combine policy gradient with an entropic regularization, typically to prevent the policy from becoming too quickly deterministic (Williams, 1992; Mnih et al., 2016). The policy gradient theorem (Sutton et al., 2000) can easily be extended to the proposed framework.

Write $d_{\nu,\pi}$ the $\gamma$-weighted occupancy measure induced by the policy $\pi$ when the initial state is sampled from $\nu$, defined as $d_{\nu,\pi}=(1-\gamma)\nu(I-\gamma P_{\pi})^{-1}\in\Delta_{\mathcal{S}}$. Slightly abusing notations, we’ll also write $d_{\nu,\pi}(s,a)=d_{\nu,\pi}(s)\pi(a|s)$.

We have to study the gradient of the value function. For this, the nabla-log trick is useful: $\nabla\pi=\pi\nabla\ln\pi$.

So, the components of $\nabla v_{\pi,\Omega}$ are the (unregularized) value functions corresponding to the rewards being the components of $q_{\pi,\Omega}(s,a)\nabla\ln\pi(a|s)-\nabla\Omega(\pi(.|s))$. Consequently,

Injecting this in the previous result concludes the proof. ∎

Even in the entropic case, it might be not exactly the same as the usual regularized policy gradient, notably because our result involves the regularized $q$-function. Again, the regularizer $\Omega$ could be replaced by a Bregman divergence, to ultimately estimate the optimal policy of the original MDP. It would be interesting to compare empirically the different resulting policy gradients approaches, we left this for future work.

D.4 Regularized inverse reinforcement learning

Inverse reinforcement learning (IRL) consists in finding a reward function that explains the behavior of an expert which is assumed to act optimally. It is often said that it is an ill-posed problem. The classical example is the null reward function that explains any behavior (as all policies are optimal in this case).

We argue that in this regularized framework, the problem is not ill-posed, because the optimal policy is unique, thanks to the regularization. For example, if one consider the negative entropy as the regularizer, with a null reward, the optimal policy will be that of maximum entropy, so the uniform policy, and it is unique.

Notice that if for a reward, the associated regularized optimal policy is unique, the converse is not true. For example, the uniform policy is optimal for any constant reward. More generally, reward shaping (Ng et al., 1999) still holds true for regularized MDPs (this being thanks to the results of Sec. 3, again).

This being said, assume that the model (dynamic, discount factor, regularizer) and that the optimal regularized policy $\pi_{*,\Omega}$ are known. It is possible to retrieve a reward function such that $\pi_{*,\Omega}$ is the unique optimal policy.

then the reward $\hat{r}(s,a)$ defined as

has $\pi_{*,\Omega}$ as the unique corresponding optimal policy.

If this result shows that IRL is well-defined in a regularized framework, it is not very practical (for example, in the entropic case, it tells that $\hat{r}(s,a)=\ln\pi_{*,\Omega}(s,a)$ is such a reward function). Yet, we think that the proposed general framework could lead to more practical algorithm.

For example, many IRL algorithms are based on the maximum-entropy principle, eg. (Ziebart et al., 2008; Finn et al., 2016; Fu et al., 2018). This maximum-entropy IRL framework can be linked to probabilistic inference, that can itself be shown to be equivalent, in some specific cases (deterministic dynamics), to entropy-regularized reinforcement learning (Levine, 2018). We think this to be an interesting connection, and maybe that our proposed regularized framework could allow to generalize or analyze some of these approaches.

D.5 Regularized zero-sum Markov games

As in the case of classical MDPs, everything can be constructed from an evaluation operator, defined as

of fixed point $v_{\mu,\nu}$. From this, the following operators are defined:

We also define the greedy operator as $\mu\in\mathcal{G}(v)\Leftrightarrow Tv=T_{\mu}v=\min_{\nu}T_{\mu,\nu}v$. Thanks to the Von Neumann’s minimax theorem (Morgenstern & Von Neumann, 1953), we have that

The modified policy iteration for this kind of games is

As in MDPs, we can regularize the evaluation operator, and construct regularized zero-sum Markov games from this. Let $\Omega_{1}$ and $\Omega_{2}$ be two strongly convex reguralizers on $\Delta_{\mathcal{A}_{1}}$ and $\Delta_{\mathcal{A}_{2}}$ , and define the regularized evaluation operator as

From this, we can construct a theory of regularized zero-sum Markov games as it was done for MDPs. The Von Neumann’s minimax theorem does not only hold for affine operators, but for convex-concave operators, so we’re fine.

Notably, the unregularized error propagation analysis of (227) by Perolat et al. (2015) could be easily adapted to the regularized case (much like how the analysis of AMPI directly led to the analysis of Sec. 4.2, thanks to the results of Sec. 3). We left its extension to regularization with a Bregman divergence as future work.