A Relation Analysis of Markov Decision Process Frameworks

Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.

44,294 characters · 9 sections · 41 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

abstractWe study the relation between different Markov Decision Process (MDP) frameworks in the machine learning and econometrics literatures, including the standard MDP, the entropy and general regularized MDP, and stochastic MDP, where the latter is based on the assumption that the reward function is stochastic and follows a given distribution. We show that the entropy-regularized MDP is equivalent to a stochastic MDP model, and is strictly subsumed by the general regularized MDP. Moreover, we propose a distributional stochastic MDP framework by assuming that the distribution of the reward function is ambiguous. We further show that the distributional stochastic MDP is equivalent to the regularized MDP, in the sense that they always yield the same optimal policies. We also provide a connection between stochastic/regularized MDP and constrained MDP. Our work gives a unified view on several important MDP frameworks, which would lead new ways to interpret the (entropy/general) regularized MDP frameworks through the lens of stochastic rewards and vice-versa. Given the recent popularity of regularized MDP in (deep) reinforcement learning, our work brings new understandings of how such algorithmic schemes work and suggest ideas to develop new ones.

Introduction

Markov decision processes (MDPs) are appealing for various problems involving sequential decision-making. Beside the standard MDP framework Puterman2014markov, which is already popular in the machine learning, operations research and econometrics communities, the literature has seen several variant MDP frameworks proposed over the recent decades, with various motivations. For example, relative entropy regularizers have been added to the reward function to improve exploration and compositionality in reinforcement learning (RL), e.g., Soft-Q learning Fox2015taming,Schulman2017equivalence,Haarnoja2017RL_ER and Sotf-Actor-Critic Haarnoja2018softa,Haarnoja2018softb. Kullback-Leibler (KL) divergence regularizers have been used to penalize the “divergence” between two conservative policies, with the motivation of preventing earlier convergence to sub-optimal policies in a policy iteration algorithm. This idea have been implemented in many state-of-the-art RL algorithms, e.g., Dynamic Policy Programming (DPP) Azar2012dynamic, Maximum A Posteriori Policy Optimization (MPO) Abdolmaleki2018maximum,Abdolmaleki2018relative,Mankowitz2019robust. Lee2018sparse,Chow2018path add a Tsallis entropy to the Markov problem with the motivation of having sparse and non-deterministic policies, and a theory a general regularized MDP framework has been studied in Geist2019theory. The use of entropy-regularizers in MDP is also advantageous in removing ambiguity in some imitation learning/inverse reinforcement learning (IRL) applications ziebart2010_IRL_Causal,Ho2016generative,Fu2017RobustIRLlearning,Finn2016_connectionIRL.

In the econometrics community, the stochastic MDP framework (a.k.a dynamic discrete choice modeling) have been proposed and intensively studied since 1980s Rust1987GMC,Rust1988MLE (see Aguirregabiria2010dynamic for a survey). This framework is based on the assumption that the reward function is no-longer deterministic but stochastic and follows a given distribution, and decisions are made according to each realization of the random rewards. The main motivation is to overcome the deterministic notation of optimal policies resulting from the standard MDP by allowing the agent to make different decisions when the rewards vary, thus improve exploration. Such stochastic Markov models, under some settings, yield randomized/soft policies, which is helpful in casting some behavioral learning procedures as probabilistic inference problems Rust1988MLE. From this viewpoint, the stochastic MDP framework shares some common motivations with the entropy-regularized MDP one ziebart2010_IRL_Causal.

In this paper, we make the first attempt to thoroughly study the relation between aforementioned MDP frameworks, aiming at providing new ways to view each MDP modeling scheme through different angles and perspectives. We consider a broad class of MDP frameworks, including the standard MDP, entropy-regularized MDP ziebart2010_IRL_Causal, general regularized MDP Geist2019theory, stochastic MDP with i.i.d Gumbel distributed rewards (a.k.a logit dynamic discrete choice), and general stochastic MDP Rust1987GMC. We summarize our contributions as follows.

itemize• We propose a new MDP framework, called distributional stochastic MDP, by assuming that the distribution of the reward function in stochastic MDPs is not given certainly, but belongs to an ambiguity set of distributions. We then show that the corresponding Markov problem is more general and more tractable, as compared to the standard stochastic MDP, in the sense an optimal policy can be found by value iteration and convex optimization, under some distributional settings with marginal information. • We show that, interestingly, there is a nested relation between these MDP frameworks, that is, (i) the entropy-regularized MDP and stochastic MDP with i.i.d Gumbel distributed rewards are “equivalent” and strictly covered by the stochastic MDP, and (ii) the general regularized MDP and the distributional stochastic MDP are equivalent and strictly cover other frameworks. Here, “equivalence” means that the uses of these MDP frameworks are equivalent, in both RL and IRL perspectives. There are many interesting points that can be seen from this nested relationship, namely, we can view (entropy) regularized MDP through the lens of stochastic-reward MDP and vice-versa. This also indicates the robustness of regularized MDP from a viewpoint of stochastic-reward with ambiguous distribution. The results also lead to new regularizers with interpretations from stochastic-reward perspectives. • We also make a connection between regularized/stochastic MDP and constrained MDP Altman1999constrained by showing that any aforementioned MDP model can be equivalently represented by a constrained MDP model. That is, adding regularizers or random noises to the reward function is equivalent to imposing some constraints on the desired optimal policies. We also provide discussions on how this constrained-MDP viewpoint would be beneficial to develop generalized RL algorithms.

The equivalence between entropy-regularized MDP and logit dynamic discrete choice in the finite-horizon case was recognized previously by Ermon2015learning and in our work we show it holds for the infinite case as well. Indeed, we cover a much broader class of MDP frameworks. Our work generally gives a unified picture of several useful MDP frameworks in the literature, thus brings new understandings of how they work and suggests ideas to develop new algorithms.

The paper is structures as follows. In Section (ref) we revisit some well-known MDP frameworks in the literature. Section (ref) introduces the distributional stochastic MDP framework. Section (ref) presents the nested relationship between regularized and stochastic MDP. We show a connection between constrained MDP and other frameworks in Section (ref) and finally, Section (ref) concludes. Proofs and some relevant discussions are given in the supplementary material. We use $|{\mathcal{S}}|$ to denote the cardinality of set ${\mathcal{S}}$. Boldface characters represent matrices (or vectors) or a collection of values/functions.

Preliminaries

Consider a infinite-horizon Markov decision process (MDP) for an agent with finite states and actions, defined as $({\mathcal{S}},{\mathcal{A}},\pmb{\Pi},\textbf{q}, \textbf{r},\gamma)$, where ${\mathcal{S}}$ is a set of states ${\mathcal{S}} = \{1,2,\ldots,|{\mathcal{S}}|\}$, ${\mathcal{A}}$ is a finite set of actions, $\pmb{\Pi} = \{\pmb{\pi}^0,\pmb{\pi}^1,\ldots\}$ is a policy function where $\pi^t(a_t|s_t)$ is the probability of making action $a_t\in{\mathcal{A}}$ in state $s_t\in{\mathcal{A}}$ at time $t\in \{0,\ldots,\infty\}$, $\textbf{q}:{\mathcal{S}}\times {\mathcal{A}}\times{\mathcal{S}} \rightarrow [0,1]$ is a transition probability function, i.e., $q(s'_t|a_t,s_t)$ is the probability of moving to state $s'_t\in{\mathcal{S}}$ from $s_t\in {\mathcal{S}}$ by performing action $a_t\in {\mathcal{A}}$ at time $t$, $\textbf{r}$ is a vector of reward functions such that $r(a_t|s_t)$ is a reward function associated with state $s_t\in{\mathcal{S}}$ and action $a_t\in{\mathcal{A}}$ at time $t$, and $\gamma\in[0,1]$ is a discount factor.

In the following we review different MDP frameworks, including the standard one, regularized MDP ziebart2010_IRL_Causal, stochastic MDP Rust1988MLE,Rust1987GMC (a.k.a dynamic discrete choice). We also briefly discuss how optimal policies can be computed. They are important ingredients to study the relation.

{Standard MDPs.} In a standard MDP model, the aim is to find an optimal sequential policy $\pmb{\Pi}$ that maximizes the expected discounted reward

align[align omitted — 218 chars of source]

where $\tau$ is a trajectory $\tau = (s_0,a_0,\ldots,s_{\infty},a_{\infty})$ and $\Delta^\pi$ is the set of all possible policy functions, i.e., $\Delta^\pi = \{\pmb{\pi}|\ \pi(a_t|s_t)\geq 0,\ \sum_{a_t}\pi(a_t|s_t) = 1\}$. Here, $\gamma^{[t]}$ refers to “$\gamma$ to the power of $t$” to distinguish it from a superscript $t$. It is well-known the problem admits a deterministic notion of optimality, i.e., optimal policies are deterministic.

{Regularized MDPs.} In a general regularized MDP model Geist2019theory, a set of regularizers ${\pmb{\phi}}$ are added to the rewards; ${\pmb{\phi}} = \{\phi_{s}(\pmb{\pi}_{s}),\ s\in{\mathcal{S}} \}$, where $\pmb{\pi}_{s} = \{\pi(a|s),\forall a\in {\mathcal{A}}\}$, for any $s\in {\mathcal{S}}$. The Markov decision problem can be stated as

align[align omitted — 259 chars of source]

It is typically assumed that $\phi_s(\pmb{\pi}_s)$ is (strictly) concave. To compute an optimal policy, we define, for any $s\in {\mathcal{S}}$, the value functions

align[align omitted — 266 chars of source]

and the Bellman update $ {\mathcal{T}}^{\textsc{RE},{\pmb{\phi}}}[V](s) = \sup_{\pmb{\pi}_s}\mathbb{E}_{\pmb{\pi}_s}[ r(a|s)+ \gamma\sum_{s'}q(s'|s,a)V(s')] + \phi_s(\pmb{\pi}_s). $ Then one can show that ${\mathcal{T}}^{\textsc{RE},{\pmb{\phi}}}[V]$ is a contraction Geist2019theory, guaranteeing that the Bellman equation always have a unique fixed point solution. Furthermore, $V^{\textsc{RE},{\pmb{\phi}}}$ defined above is the unique solution to ${\mathcal{T}}^{\textsc{RE},{\pmb{\phi}}}[V] = V$. Moreover, if we denote by $\phi^*_s(\textbf{w}_s)$ the Legendre-Fenchel transform (or convex conjugate) of $-\phi_s(\pmb{\pi}_s)$, i.e.,

equation[equation omitted — 213 chars of source]

then the value iteration can be updated as ${\mathcal{T}}^{\textsc{RE},{\pmb{\phi}}}[V](s) = \phi^*_s(\textbf{w}_s)$, where $\textbf{w}_s\in \mathbb{R}^{|{\mathcal{A}}|}$ with elements $w_{sa} = r(a|s)+\sum_{s'}q(s'|s,a)V(s')$. If $\phi_s(\pmb{\pi}_s) = -\sum_{a\in{\mathcal{A}}} \pi(a|s)\ln \pi(a|s)$ (relative entropy), the model becomes the entropy-regularized one. We call this MDP framework as Entropy-Regularized MDP (ER-MDP).

{Stochastic MDPs (a.k.a. Dynamic Discrete Choice Modeling).} This framework has been developed and widely studied in the econometrics community for the problem of learning/predicting people behavior from observations (a.k.a IRL) Rust1987GMC. In this framework, it is assumed that the reward function is stochastic and can be written as $\widetilde{r}(a|s) = r(a|s)+\epsilon(a|s)$, where $r(a|s)$ is deterministic and $\epsilon(a|s)$ is a random noise. Let ${\pmb{\epsilon}}_s =\{\epsilon(a|s)|\ a\in {\mathcal{A}}\}$. We further assume that the distributions of ${\pmb{\epsilon}}_s$, $\forall s\in{\mathcal{S}}$, are continuous and independent over states. We define a sequence of decision rule ${\pmb{\Psi}} = \{{\pmb{\psi}}^0,{\pmb{\psi}}^1,\ldots\}$, where ${\pmb{\psi}}^t$ is a set of decision rules at time $t$, i.e., ${\pmb{\psi}}^t = \{\psi(s_t|{\pmb{\epsilon}}_{s_t}),\ s_t\in{\mathcal{S}}\}$, where $\psi(s_t|{\pmb{\epsilon}}_{s_t}):\mathbb{R}^{|{\mathcal{A}}|}\rightarrow {\mathcal{A}}$ is a deterministic policy at state $s_t$ under a realization of the random noise ${\pmb{\epsilon}}_{s_t}$. The aim is to select a decision rule to maximize the expected discounted stochastic reward

align[align omitted — 253 chars of source]

To solve the above Markov problem, we also define the value function

align[align omitted — 322 chars of source]

Then Rust1988MLE shows that $V^{\textsc{S}}$ is a solution to the contraction mapping $ {\mathcal{T}}^{\textsc{S}}[V](s) = \sup_{{\pmb{\psi}}_s}\{\mathbb{E}_{{\pmb{\epsilon}}_s}[z(s,a|V)] \} $ where $z(s,a|V) = r(a|s)+ \epsilon(a|s) +\mathbb{E}[V(s')]$, and there is an memory-less optimal decision rule specified as $ \psi(s|{\pmb{\epsilon}}_s) = \text{argmax}_{a\in {\mathcal{A}}} \left\{ z(s,a,V^{\textsc{S}})\right\}. $ Basically, a set of decision rule $\{{\pmb{\psi}}_s,s\in{\mathcal{S}}\}$ can be viewed as a policy where the probability of making action $a$ at state $s$ is also the density of making action $a$, i.e., $\pi(a|s)= \mathbb{P}_{{\pmb{\epsilon}}}(\phi(s|{\pmb{\epsilon}}_s) = a)$. In particular, if $\epsilon(a|s)$ are i.i.d and follow the Gumbel distribution (or Extreme Value Type I distribution), we obtain a MDP framework so-called the logit-based dynamic discrete choice model Rust1988MLE. We call this model as Stochastic EV MDP (or EV-MDP for short).

Distributional Stochastic MDPs

The Bellman update in a stochastic MDP model involves an expectation of the form $\mathbb{E}_{{\pmb{\epsilon}}_s}\left[\max_{a\in{\mathcal{A}}} \{w_{sa}+\epsilon(a|s))\} \right]$, which is typically difficult to evaluate even when the distribution of ${\pmb{\epsilon}}_s$ is well specified steele1997probability. To over come this, inspired by the persistent model studied in Bertsimas2006persistence,Natarajan2009persistency, we introduce a new MDP framework, called Distributional Stochastic MDP (DS-MDP), by extending the S-MDP framework by assuming that the distribution of the random terms ${\pmb{\epsilon}}$ is not given certainly, but belongs to a set of distributions $\Xi$. This new setting makes the corresponding Markov problem easier to solve by convex optimization, under some classes of distributions with marginal information. We will show later this new framework is strongly related to the regularized MDP one.

Under the ambiguity setting, we define a Markov problem where the objective is to select a sequence of distributions $\textbf{D} = \{\textbf{d}^0,\textbf{d}^1,\ldots\}$ and a sequence of decision rules ${\pmb{\Psi}} = \{{\pmb{\psi}}^0,{\pmb{\psi}}^1,\ldots\}$ in such a way that the following expected reward function is maximized.

align[align omitted — 402 chars of source]

where ${\pmb{\epsilon}}$ the random noise vector at time $t$. That is, at time step $t$, we select a distribution $\textbf{d}^t\in\Xi$ describing how the random noises ${\pmb{\epsilon}}$ vary and a decision rule ${\pmb{\psi}}^t$ to select action according to each realization of the random noise vector. To make the Markov problem tractable, we assume that $\Xi$ is state-wise decomposable, i.e., $\Xi = \otimes_{s\in{\mathcal{S}}}\Xi_s$, where $\Xi_s$ is an ambiguity set for the distributions of the noise vector ${\pmb{\epsilon}}_s$ at state $s$. This assumption allows to solve the Markov problem by value iteration or policy iteration, similarly to other MDP frameworks.

We define the value function (expected accumulated discounted reward) $V^{\textsc{DS},\Xi}: {\mathcal{S}} \rightarrow \mathbb{R}$ as

equation[equation omitted — 412 chars of source]

and the mapping

equation[equation omitted — 263 chars of source]

The following theorem shows that basic theoretical properties that hold for other MDP frameworks also hold for the DS-MDP.

theoremFor any nonempty set of distributions $\Xi$, we have the following properties \begin{itemize} • ${\mathcal{T}}^{\textsc{DS},\Xi}[V]$ is monotonically increasing and translation invariant, i.e., ${\mathcal{T}}^{\textsc{DS},\Xi}[V] \geq {\mathcal{T}}^{\textsc{DS},\Xi}[V']$ for any $V,V'\in\mathbb{R}^{|{\mathcal{S}}|}, V\geq V'$, and ${\mathcal{T}}^{\textsc{DS},\Xi}[V + \alpha {\textbf{e}}] = {\mathcal{T}}^{\textsc{DS},\Xi}[V] + \alpha$, where $\alpha$ is a scalar and ${\textbf{e}}$ is a unit vector of size $|{\mathcal{S}}|$. • ${\mathcal{T}}^{\textsc{DS},\Xi}[V]$ is a contraction mapping of parameter $\gamma$ w.r.t. the infinity norm, i.e., for any $V,V'\in\mathbb{R}^{|{\mathcal{S}}|}$ we have $||{\mathcal{T}}^{\textsc{DS},\Xi}[V] - {\mathcal{T}}^{\textsc{DS},\Xi}[V']||_\infty \leq \gamma ||V-V'||_\infty$. • If $\sup_{d_s\in\Xi}\mathbb{E}_{{\pmb{\epsilon}}_s\sim d_s}[\max_a\{r(a|s)+\epsilon(a|s)\}]$ are bounded from above for all $s\in{\mathcal{S}}$, then $V^{\textsc{DS},\Xi}$ is the unique fixed point solution to the system ${\mathcal{T}}^{\textsc{DS},\Xi}[V] = V$. • The densities of the optimal decision rules (i.e. optimal policy) ${\pmb{\psi}}_s , \forall s\in {\mathcal{S}}$, can be computed as \[ \pi^{\textsc{DS},*} (a|s) =\partial \varphi_s(\textbf{w}_s)/\partial w_{sa}, \ \forall a\in{\mathcal{A}}, s\in{\mathcal{S}} \] where $\textbf{w}_s$ is a vector of size $|{\mathcal{A}}|$ with entries $ w_{sa} = r(a|s)+ \gamma\sum_{s'}q(s'|s,a)V^{\textsc{DS},\Xi}(s')$ and \begin{align} \varphi_s(w_s) &= \sup_{d_s\in\Xi_s}\left\{\mathbb{E}_{{\pmb{\epsilon}}_s \sim d_s}[\max_a \{ w_{sa}+\epsilon(a|s)\}]\right\}. \end{align} \end{itemize}

Theorem (ref)-(i) is quite obvious to validate. The contraction property (ii) can be done by looking at the structure of the mapping (ref) and (iii) can be validated by extending (ref) recursively. The assumption in (iii) generally holds if the noise ${\pmb{\epsilon}}_s$ has a finite first moment for any distribution $d_s\in\Xi$ for any $s\in{\mathcal{S}}$, i.e., $\sup_{d_s \in\Xi}\mathbb{E}_{{\pmb{\epsilon}}_s\sim d_s}[{\pmb{\epsilon}}_s]<\infty$. Given (ii) and (iii), one can find an optimal decision rule by solving the Bellman equation (ref). Hence, we can make use of the properties of the semi semi-parametric choice model propose by Natarajan2009persistency to obtain the optimal decision rule (iv). Note that in the S-MDP framework, the optimal policy is defined similarly, but for only one distribution $d_s$. Let $d_s(\textbf{w}_s)$ denote the distribution or a limit of a sequence of distributions (in case that the set $\Xi_s$ is not compact) that attains the optimal value $\varphi_s(\textbf{w}_s)$, the optimal policy can be expressed as $ \pi^{\textsc{DS},*} (a|s) = \mathbb{P}_{{\pmb{\epsilon}}_s\sim d_s(\textbf{w}_s)}\left[a = \text{argmax}_{a\in{\mathcal{A}}}\{w_{sa}+\epsilon(a|s)\} \right]. $ It is also interesting to look at a relevant version of the DS-MDP, where we take an inf over the distribution set $\Xi$, instead of sup as in (ref), i.e., $ \inf_{\textbf{d}^0,\textbf{d}^1,\ldots } \sup_{{\pmb{\psi}}^0,{\pmb{\psi}}^1,...}\{\cdot\}$. In this case, an optimal decision rule is more difficult to identify, even for one-stage problems, thus less interesting Natarajan2009persistency.

Nested Relation between Stochastic and Regularized MDP Frameworks

In this section we analyze the relation between the stochastic and regularized MDP frameworks mentioned above. First, we summarize all the MDP frameworks considered in Tab. (ref). The constrained MDP one on the last row will be discussed in the next section.

minipage{\textwidth} \begin{minipage}[b]{0.49\textwidth} \begin{tabular}{l|l} MDP frameworks & Abbreviation \\ \hline Standard MDP & MDP \\ Stochastic EV MDP & EV-MDP \\ Stochastic MDP & S-MDP \\ Distributional Stochastic MDP & DS-MDP \\ Regularized MDP & R-MDP \\ Entropy Regularized MDP & ER-MDP \\ Constrained MDP & CT-MDP \end{tabular} \captionof{table}{Summary of MDP frameworks } \end{minipage} \begin{minipage}[b]{0.49\textwidth} \captionof{figure}{Nested relation between MDP frameworks } \end{minipage}

In general, we will validate the diagram in Fig. (ref), which says that (i) the R-MDP are equivalent to DS-MDPs and strictly covers other frameworks, (ii) the ER-MDP is equivalent to the S-MDP with Gumbel distributed random noises and both are strictly covered by the S-MDP. This diagram shows a broad and insightful connection/relation between regularized and stochastic MDP frameworks, thus provides new ways to interpret each MDP framework through others. To facilitate our exposition, we need the following definitions.

definition[Equivalent MDP models] Two MDP models $\textbf{X}$ and $\textbf{Y}$ are said to be “equivalent”, denoted by $X\equiv Y$, if and only if they are specified by the same tuple $({\mathcal{S}},{\mathcal{A}},\textbf{q}, \gamma)$ and there are a constant vector $\pmb{\alpha}$ of size ($|{\mathcal{S}}|\times|{\mathcal{A}}|$) such that for any reward functions $\textbf{r}^{X},\textbf{r}^{Y}\in \mathbb{R}^{|{\mathcal{S}}|\times|{\mathcal{A}}|}$, $\textbf{r}^X- \textbf{r}^Y = \pmb{\alpha}$, model $\textbf{X}$ with rewards $\textbf{r}^X$ and model $\textbf{Y}$ with rewards $\textbf{r}^Y$ always yield the same the value function and a common stationary optimal policy $\{\pi^*(a|s),\ \forall a,s\}$.

The equivalence property between two MDP models implies that the two models are identical to use, in both perspectives of RL and IRL. Under this definition, two ER-MDP models based on a relative entropy regularizer $\eta_1 \sum_{a}\pi(a|s)\ln(\pi(a|s))$ and a KL divergence $\eta_2\text{KL}(\pmb{\pi}_s||\overline{\pmb{\pi}}_s)$ are equivalent if $\eta_1=\eta_2$, but not equivalent if $\eta_1 \neq \eta_2$.

We can view a MDP framework as a set of MDP models, e.g., the S-MDP framework contains S-MDP models, each is specified by a distribution set $\{d_s,\ s\in{\mathcal{S}}\}$ of the random noises $\{{\pmb{\epsilon}}_s,\ s\in{\mathcal{S}}\}$. We define “equivalent” MDP frameworks as follows.

definition[Equivalent MDP frameworks] Two MDP frameworks ${\mathcal{X}}$ and ${\mathcal{Y}}$ are said to be “equivalent” if and only if for any MDP model $\textbf{X}\in{\mathcal{X}}$, there is a MDP model $\textbf{Y} \in {\mathcal{Y}}$ such that $\textbf{X}\equiv \textbf{Y}$, and vice-versa.

In other words, the “equivalence” between two MDP frameworks implies that they share the same set of equivalent MDP models, and the uses of these MDP frameworks are indeed identical. We also define when a framework is strictly subsumed by another one.

definition[Subsumed MDP framework] Given two MDP frameworks ${\mathcal{X}}$ and ${\mathcal{Y}}$, we say “${\mathcal{X}}$ strictly subsumes ${\mathcal{Y}}$” if and only if for any MDP model $\textbf{Y}\in{\mathcal{Y}}$ there is always $\textbf{X}\in{\mathcal{X}}$ such that $\textbf{X} \equiv \textbf{Y}$, but there is $\textbf{X} \in {\mathcal{X}}$ such that there is no $\textbf{Y} \in {\mathcal{Y}}$ such that $\textbf{X}$ and $\textbf{Y}$ are equivalent.

So if a MDP framework ${\mathcal{X}}$ subsumes another ${\mathcal{Y}}$, it means ${\mathcal{X}}$ is more flexible to use. It is clear that the R-MDP subsumes the EV-MDP and standard MDP, and the DS-MDP subsumes the S-MDP and EV-MDP ones (but not sure the subsumption is strict). The question now is what is the relation between two modeling approaches: stochastic and regularized. We start investigating this by the following proposition.

propositionThe ER-MDP and EV-MDP frameworks are equivalent and strictly subsume the standard unconstrained MDP one.

The equivalence between ER-MDP and EV-MDP in the finite-horizon case has been shown in Ermon2015learning and can be validated easily by looking at the formulations used to compute optimal policies in previous studies ziebart2010_IRL_Causal, Rust1988MLE. The claim that ER-MDP and EV-MDP strictly subsumes the standard one is also easy to verify, using the fact the standard MDP typically yields deterministic policies while the other frameworks give randomized and soft optimal policies.

There is a well-known similarity between Shannon's entropy Shannon1948mathematical and the multinomial logit model Anas1983discrete. Proposition (ref) extends this similarity to a multi-stage decision-making setting. It also indicates a connection between EV-MDPs and the maximum causal entropy principle ziebart2010_IRL_Causal, which implies that an optimal decision rule given by an EV-MDP model will maximize a causal entropy function and satisfy a prediction log-loss guarantee.

An application of the ER-MDP framework is to add a KL divergence $\phi_s(\pmb{\pi}_s) = -\eta\text{KL}(\pmb{\pi}_s||\overline{\pmb{\pi}}_s) = \eta\sum_{a}\pi(a|s)\ln \frac{\pi(a|s)}{\overline{\pi}(a|s)}$ to control the divergence between a desired optimal policy and a given policy Haarnoja2017RL_ER,Abdolmaleki2018maximum. According to Theorem (ref), this ER-MDP model is equivalent to a stochastic MDP model with rewards $r'(a|s) = r(a|s) -\eta \overline{\pi}(a|s)$ and Gumbel distributed i.i.d random noises. In other words, by adding stochastic noises to the reward function, we can penalize the divergence between two policies.

We now move to the S-MDP framework and have Proposition (ref). It is obvious to see that the EV-MDP is just special case of the S-MDP when the random noises follow the Gumbel distribution. Thus S-MDP subsumes both the EV-MDP and ER-MDP. However, it is not straightforward to see that the S-MDP strictly subsumes the other frameworks, as one can show that an ER- or EV-MDP model can yield any optimal optimal policy in $\Delta^\pi$ when varying the reward function. We do this by giving a counter example where the random noises in the S-MDP model are no-longer i.i.d.

propositionThe S-MDP strictly subsumes the EV-MDP and ER-MDP frameworks.

We now look at broader frameworks. The R-MDP is the most general frameworks among regularized ones, and the DS-MDP covers all other stochastic MDP frameworks. Interestingly, Theorem (ref) below tells use that the two general frameworks are actually equivalent. The proof makes use of Theorem (ref) and some results in Feng2017relationDC. The equivalence provides a new way to view regularized MDPs through the lens of stochastic MDPs. That is, adding (concave) regularizers to the MDP model is equivalent to assuming that the reward function contains some random noises of ambiguous distribution. This also shows the robustness of the R-MDP framework from a stochastic-reward viewpoint.

theoremThe R-MDP and DS-MDP frameworks are equivalent and strictly subsume the S-MDP framework if $|{\mathcal{A}}|\geq 3$.

We also see that, given an ambiguity set of continuous distributions $\Xi$, the DS-MDP model is equivalent to a R-MDP model with regularizers $\phi_s(\pmb{\pi}_s) = - \varphi^*_s(\pmb{\pi}_s)$, where $\varphi^*_s(\pmb{\pi}_s)$ is the convex conjugate of function $\varphi_s(\textbf{w}_s)$ defined in (ref), i.e., $\phi_s(\pmb{\pi}_s) = -\varphi^*_s(\pmb{\pi}_s) = -\sup_{\textbf{w}_s \in \mathbb{R}^{|{\mathcal{A}}|}} \{\pmb{\pi}^\text{\tiny T}_s \textbf{w}_s - \varphi_s(\textbf{w}_s) \}$. Under some ambiguity settings with marginal information, one can obtain a closed form to compute the convex conjugate functions $\varphi^*_s(\pmb{\pi}_s)$ and we provide some examples in Proposition (ref) below, which may suggest new regularizers with interpretations from a stochastic-rewards viewpoint. Proposition (ref) below provides some examples of DS-MDP models and their equivalent R-MDP ones. These examples extend some results developed for the persistent model Natarajan2009persistency to our MDP settings.

propositionThe DS-MDP models on the left column are equivalent to the corresponding R-MDP models on the right column. \begin{table}[htb] \begin{tabular}{l|l|l} Case&DS-MDP, for any $s\in{\mathcal{S}}$ & R-MDP, for any $s\in{\mathcal{S}}$ \\ \hline (i)&$\Xi_s = \Bigg\{d_s\Big| \epsilon(a|s)\sim F_{sa}(\cdot), \forall a\in{\mathcal{A}}\Bigg\}$ & $\phi_s (\pmb{\pi}_s) = \sum_{a\in{\mathcal{A}}} \int_{1-\pi(a|s)}^1 F_{sa}^{-1}(t) dt$ \\\hline (ii)&$\Xi_s = \left\{d_s \middle\vert \begin{array}{@{}ll@{}} \text{dev}(\epsilon(a|s)) = \sigma(a|s) \\ \mathbb{E}[\epsilon(a|s)]=0\end{array} \right\}$ & $\phi_s (\pmb{\pi}_s) = \sum_{a\in{\mathcal{A}}} \sigma(a|s)\sqrt{\pi(a|s)(1-\pi(a|s))}$ \\\hline (iii)&$\Xi_s = \left\{d_s \middle\vert \begin{array}{@{}ll@{}} \text{Cov}({\pmb{\epsilon}}_s) = \Sigma_s \\ \mathbb{E}[{\pmb{\epsilon}}_s]=0\end{array} \right\}$ & $\phi_s (\pmb{\pi}_s) = \text{trace}\Big( \Sigma_s^{1/2}\big(\text{Diag}(\pmb{\pi}_s) - \pmb{\pi}_s\pmb{\pi}_s^\text{\tiny T} \big)\Sigma_s^{1/2} \Big)^{1/2}$ \\\hline \end{tabular} \end{table} where $F_{as}(\cdot)$ is the marginal (continuous) cumulative distribution function of $\epsilon(a|s)$, $\text{dev}(\epsilon(a|s))$ is the marginal standard deviation of $\epsilon(a|s)$, $\text{trace}(\textbf{A})$ is the trace of matrix $\textbf{A}$, $\text{Diag(\textbf{v})}$ is the diagonal matrix with the elements of vector $\textbf{v}$ on the main diagonal, and $\text{Cov}({\pmb{\epsilon}}_s)$ is the covariance matrix of the random vector ${\pmb{\epsilon}}_s$. Here we assume that $\Sigma_s$ is positive definite.

For (i) and (ii), the models are based on the the marginal distribution and marginal moment models considered Natarajan2009persistency, in which only the cumulative distribution, or the first and moments of the marginal distributions of the random noises are known. Example (iii) concerns models in which only the covariance information of the distribution in $\Xi$ is known and the equivalent R-MDP model is derived using mishra2014theoretical.

Connection to Constrained MDPs

We investigate a relation between the MDP frameworks considered above and the constrained MDP (CT-MDP) one, an extension of the standard MDP where constraints are imposed on the policy. A typically CT-MDP model has constraints on a long-term performance of the policy Altman1999constrained. In this section, we only consider constraints on state policies, i.e., the policy variables at each state belong to a feasible set, and these sets are independent over states. This allows to solve the constrained MDP problem by value iteration or policy iteration as in the case of standard MDPs.

Constrained MDPs

The constrained version requires that the policy $\pmb{\pi}$ belong to a set $ \pmb{\pi} \in {\mathcal{D}}^{\pi} \subset \Delta^{\pi}. $ We further assume that ${\mathcal{D}}^\pi$ is state-wise decomposable, i.e., ${\mathcal{D}}^{\pi} = \otimes_{s\in{\mathcal{S}}}{\mathcal{D}}^{\pi}_{s}$, where ${\mathcal{D}}^{\pi}_{s} \subset \Delta(|{\mathcal{A}}|)$ is an support set for the policy $\{\pi(a|s),\ a\in{\mathcal{A}}\}$, for any $s\in {\mathcal{S}}$. We further assume that ${\mathcal{D}}^{\pi}_s$ is nonempty. The Markov decision problem becomes

align[align omitted — 203 chars of source]

We can then define a value function $V^{\textsc{CT},{\mathcal{D}}^\pi}$ and Bellman equation ${\mathcal{T}}^{\textsc{CT},{\mathcal{D}}^\pi}[V]$ analogously to the standard MDP, except that the policy $\pmb{\pi}$ are required to lie in the set ${\mathcal{D}}^\pi$. Note that the Bellman update in this case ${\mathcal{T}}^{\textsc{CT},{\mathcal{D}}^\pi}$ is contraction for any non-empty set ${\mathcal{D}}^{\pi}$.

CT-MDP and other MDP frameworks

We first note that the CT-MDP covers the standard MDP framework when ${\mathcal{D}}^\pi_s$ is the simplex in $\mathbb{R}^{|{\mathcal{A}}|}$. Even-though the CT-MDP looks general, as we can introduce any feasible set ${\mathcal{D}}^\pi_s$, Theorem (ref) below shows that, in the context of Definitions (ref) and (ref), the CT-MDP framework is not subsumed or cover any stochastic or regularized MDP frameworks considered above, except the standard one. On the other hand, the R-MDP and DS-MDP frameworks are the most general among those presented in Fig. (ref), but cannot cover the CT-MDP.

theoremThere is an ER-MDP model $\textbf{X}$ with parameter $\eta>0$ such that there is no CT-MDP model that is equivalent to $\textbf{X}$. On the other hand, there is also a CT-MDP model $\textbf{Y}$ such that there is no R-MDP model being equivalent to $\textbf{Y}$.

However, if we fix the reward function, then we can show that, even though the CT-MDP framework does not cover the R-MDP one, but for any R-MDP model, there is a CT-MDP model specified by convex constraints that yields an identical optimal policy.

propositionGiven a R-MDP model defined by a tuple $({\mathcal{S}},{\mathcal{A}},\textbf{q}, \textbf{r},\gamma)$ and the set of strictly concave functions $\{\phi_s|\ s\in{\mathcal{S}}\}$, there exists a set of constants $\{c_s,\ s\in{\mathcal{S}}\}$ such that the CT-MDP model defined by the same tuple but with a shifted reward function $\textbf{r}'_s = \textbf{r}_s - c_s$ and feasible sets ${\mathcal{D}}^{\pi}_s = \{\pmb{\pi}_s\in \Delta(|{\mathcal{A}}|)|\ -\phi_s(\pmb{\pi}_s) \leq c_s\}$ will yield an identical optimal policy.

It is important to note that $\{c_s,\, \forall s\}$ specified in Proposition (ref) depend on the reward vector $\textbf{r}$, thus the CT-MDP model cannot yield identical optimal policies for any reward function. The reverse is also true, that is, for any CT-MDP model specified by a set of convex constraints, we always can find a R-MDP model that yield an identical optimal policy (see the supplementary material for details).

Discussion

In general, we have seen that a stochastic MDP model can be interpreted as a regularized one and vice-versa. Proposition (ref) shows that any R-MDP or DS-MDP model can be always represented by a CT-MDP one. In other words, adding regularizers or random noises to the reward function is equivalent to constraining the desired optimal policies. Let us illustrate this by some examples.

A popular and useful regularizer in RL is a KL divergence $-\eta \text{KL}(\pmb{\pi}_s||\overline{\pmb{\pi}}_s)$ between two consecutive policies. We have shown that this regularized model is equivalent to a stochastic model with shifted rewards and Gumbel distributed random noises. From Proposition (ref) we see that these ER-MDP and EV-MDP models can be equivalently represented by a CT-MDP with constraints $\text{KL}(\pmb{\pi}_s||\overline{\pmb{\pi}}_s) \leq c_s/\eta$, where $c_s \geq 0$ for all $s\in {\mathcal{S}}$. Clearly, if $c_s\rightarrow 0$ then the optimal policy should converge to $\overline{\pmb{\pi}}_s$ and if we increase $c_s$, the feasible set ${\mathcal{D}}^\pi_s$ will converge to $\Delta(|{\mathcal{A}}|)$ (i.e. the simplex in $\mathbb{R}^{|{\mathcal{A}}|}$) and we will retain a deterministic policy as in the unconstrained MDP model.

Several RL and IRL algorithms make use of soft policies resulting from relative entropy regularizers $\phi_s(\pmb{\pi}_s) =-\eta \sum_{a}\pi(a|s)\ln \pi(a|s)$ ziebart2010_IRL_Causal. Let $\widetilde{\pmb{\pi}}^*_s = \text{argmax}_{\pmb{\pi}_s \in\Delta(|{\mathcal{A}}|)} \phi_s(\pmb{\pi}_s)$, we see that (i) $\widetilde{\pmb{\pi}}^*_s = {\textbf{e}}/|{\mathcal{A}}|$ (a random walk, ${\textbf{e}}$ is a unit vector of size $|{\mathcal{A}}|$) and (ii) for any $\pmb{\pi}_s$ \[ \text{KL}(\pmb{\pi}_s||\widetilde{\pmb{\pi}}^*_s) = \sum_{a\in{\mathcal{A}}}\pi(a|s)\ln \pi(a|s) - \ln |{\mathcal{A}}| = -\phi_s(\pmb{\pi})/\eta - \ln |{\mathcal{A}}|. \] Thus the constraint $-\phi_s(\pmb{\pi}_s) \leq c_s$ becomes $\text{KL}(\pmb{\pi}_s||\widetilde{\pmb{\pi}}^*_s) \leq c_s/\eta - \ln |{\mathcal{A}}|$. So, we see that by adding the relative entropy terms and varying the parameter $\eta$, we are controlling the KL divergence between a desired policy and the random walk vector $\widetilde{\pmb{\pi}}^*_s$. Making the optimal policy closer to the random walk indeed helps improve exploration.

This analysis can be extended to a general R-MDP model with (strictly) concave regularizers $\{\phi_s,s\in{\mathcal{S}}\}$. Also let $\widetilde{\pmb{\pi}}^*_s = \text{argmax}_{\pmb{\pi}_s \in\Delta(|{\mathcal{A}}|)} \phi_s(\pmb{\pi}_s)$, which are always uniquely determined. We can show that if $\widetilde{\pmb{\pi}}^*_s$ contain non-zero elements, then we can write $\nabla \phi_s(\widetilde{\pmb{\pi}}^*_s) = \alpha {\textbf{e}}$, where $\alpha$ is a scalar. The Bregman divergence ($\text{BD}$) generated by $-\phi_s(\cdot)$ between two policies becomes \[ \text{BD}^{-\phi_s}(\pmb{\pi}_s||\pmb{\pi}^*_s) = -\phi_s(\pmb{\pi}_s) + \phi_s(\widetilde{\pmb{\pi}}^*_s) + \alpha - \alpha {\textbf{e}}^\text{\tiny T} \widetilde{\pmb{\pi}}^*_s. \] Thus, the constraints $-\phi_s(\pmb{\pi}_s) \leq c_s$ becomes $\text{BD}^{-\phi_s}(\pmb{\pi}_s||\pmb{\pi}^*_s) \leq c_s + \phi_s(\widetilde{\pmb{\pi}}^*_s) + \alpha - \alpha {\textbf{e}}^\text{\tiny T} \widetilde{\pmb{\pi}}^*_s$. This generally implies that using a regularized MDP model is equivalent to imposing a Bregman divergence requirement on the desired policies.

The idea of using KL or Bregman divergence to control the distance between two consecutive policies in a policy iteration is interesting and useful Azar2012dynamic,Abdolmaleki2018maximum,Abdolmaleki2018relative,Mankowitz2019robust,Lee2018sparse,Chow2018path. The CT-MDP framework provides a flexible and general way to implement it. For example, one can consider other types distance measures at a greedy step, i.e., we solve a constrained Bellman update with feasible sets defined as ${\mathcal{D}}^\pi_{s} = \{\pmb{\pi}_s\in\Delta(|{\mathcal{A}}|),\ ||\pmb{\pi}_s - \pmb{\pi}^k_s||\leq \xi\}$, where the norm $||\cdot||$ can be L1, L2 or L-infinity norm. If the norm is L1 or L-infinity, we greedy step can be efficiently performed by solving a linear program. If the norm is L2, then the greed step is still a convex optimization problem, which is generally easy to solve. We can incorporate several previous policies to have a more robust greedy step, i.e., ${\mathcal{D}}^\pi_{s} = \{\pmb{\pi}_s\in\Delta(|{\mathcal{A}}|),\ \max_{i\in {\mathcal{K}}}||\pmb{\pi}_s - \pmb{\pi}^i_s||\leq \xi\}$, where ${\mathcal{K}}$ is a set of indexes of previous policies considered. The constraints require that a desired policy after the greedy step should not be too far from a set of some policies computed from previous iterations. Moreover, different types of distance measures can be combined, e.g., KL divergence or different norms, while keeping the constrained Bellman update tractable. We provide some computational complexity analyses for such constrained models in the supplementary material.

Conclusion

In this paper we study the relation between stochastic, regularized and constrained MDP frameworks. We first propose the DS-MDP by assuming the distribution of the random noises in the S-MDP is ambiguous and we validate some basic properties of the new framework, which allows to solve a DS-MDP problem by value iterations. We show that there is a nested relationship between stochastic and regularized MDP frameworks, which provides new ways to interpret regularized MDP frameworks through the lens of stochastic ones and vice-versa. We also show a strong connection between stochastic/regularized MDPs and constrained MDPs, and show how this finding would be useful in some well-known algorithmic schemes.