Answers.Body: <p>(This answer is based on info that you can find in the paper <a href="https://www.jmlr.org/papers/volume3/szita02a/html/Szita02a.html" rel="nofollow noreferrer"><span class="math-container">$\varepsilon $</span>-MDPs: Learning in Varying Environments</a>, 2002, by István Szita et al. and <a href="https://www.researchgate.net/profile/Csaba-Szepesvari/publication/245451971_Generalized_Markov_Decision_Processes_Dynamic_programming_and_Reinforcement-le_arning_Algorithms/links/00b4952921789cfd76000000/Generalized-Markov-Decision-Processes-Dynamic-programming-and-Reinforcement-le-arning-Algorithms.pdf" rel="nofollow noreferrer">[Szepesvári and Littman(1996)]</a>, the paper that proposed generalised MDPs. I just adapted the notation to be more consistent with <a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">Sutton &amp; Barto's book</a> and provided additional info and links).</p>
  <h3>What is an MDP?</h3>
  <p>Let's first start with the usual definition of an MDP.</p>
  <p>An MDP is defined by the tuple <span class="math-container">$\langle \mathcal{S}, \mathcal{A}, R, \color{blue}{P} , \gamma \rangle$</span>, where</p>
  <ul>
  <li><span class="math-container">$\mathcal{S}$</span> is the set of states</li>
  <li><span class="math-container">$\mathcal{A}$</span> is the set of actions</li>
  <li><span class="math-container">$R: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$</span> is the <a href="https://ai.stackexchange.com/q/10442/2444">reward function</a>; so <span class="math-container">$R(s, a, s')$</span> is the reward for taking action <span class="math-container">$a \in \mathcal{A}$</span> in state <span class="math-container">$s \in \mathcal{S}$</span> and ending up in <span class="math-container">$s' \in \mathcal{S}$</span>.</li>
  <li><span class="math-container">$\color{blue}{P}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1]$</span> is the <strong>transition model</strong>; so <span class="math-container">$\color{blue}{P}(s, a, s')$</span> is the probability of arriving in state <span class="math-container">$s'$</span> after having taken action <span class="math-container">$a$</span> in the state <span class="math-container">$s$</span>. You could also <a href="https://ai.stackexchange.com/q/10442/2444">define the transition model to include the reward</a>, denoted by <span class="math-container">$\color{blue}{P}(s', r \mid s, a)$</span> to emphasize that it's a conditional probability distribution), but let's ignore this for now.</li>
  <li><span class="math-container">$0 \leq \gamma &lt; 1$</span> is a discount factor, which can be useful for infinite-horizon problems</li>
  </ul>
  <p>Given this formulation of a decision problem, the goal is to maximize the expected reward. The objective function can be defined as follows
  <span class="math-container">$$
  \mathbb{E}\left[ \sum_{t=0}^{\infty} \gamma^{t} R_{t} \right] = \mathbb{E}\left[ G_{t} \right],
  $$</span>
  where <span class="math-container">$R_{t}$</span> is the reward that we get at <a href="https://ai.stackexchange.com/a/11605/2444">time step <span class="math-container">$t$</span></a>.</p>
  <p>There are multiple ways to solve this problem. The most common is probably Q-learning.</p>
  <h3>Q-learning</h3>
  <p>In Q-learning, we try to estimate the state-action (or action) value function. The optimal value function is defined as follows</p>
  <p><span class="math-container">$$
  Q^{*}(s, a)=\sum_{s'} \color{blue}{P}(s, a, s')\left(R(s, a, s')+\gamma \color{red}{\max} _{a^{\prime}} Q^{*}(s', a^{\prime})\right) \label{1}\tag{1}, 
  $$</span>
  for all <span class="math-container">$s \in \mathcal{S}$</span>.</p>
  <p>So, it's a function of the form <span class="math-container">$Q^{*}: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$</span>. To emphasize the main purpose of this function, it can be denoted/defined as <span class="math-container">$Q^{*}(s, a) = \mathbb{E}\left[G_t \mid a, s \right]$</span>, so it's the expected return (<span class="math-container">$G_t$</span> is the return or cumulative reward) for taking action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span> under the optimal policy <span class="math-container">$\pi^*$</span> (hence the <span class="math-container">$*$</span>).</p>
  <p>The equation (\ref{1}) is a recursive equation because <span class="math-container">$Q^{*}(s, a)$</span> is defined in terms of itself, i.e. we use <span class="math-container">$Q^{*}(s', a^{\prime})$</span> to define it. In this context, this type of recursive equation is also known as <a href="https://ai.stackexchange.com/q/11057/2444"><strong>Bellman equation</strong></a> (due to <a href="https://en.wikipedia.org/wiki/Richard_E._Bellman" rel="nofollow noreferrer">Richard Bellman</a>, who contributed to the theory of dynamic programming, which is related to MDPs, as dynamic programming algorithms can be used to solve MDPs, given a transition model).</p>
  <p>One thing to keep in mind is that the optimal policy can be derived from the optimal state-action value function by acting greedily with respect to it.</p>
  <h3>What is a Generalized MDP?</h3>
  <p>Now, there's one reason why I colored the transition model and the max operation in the Bellman equation \ref{1} in <span class="math-container">$\color{blue}{\text{blue}}$</span> and <span class="math-container">$\color{red}{\text{red}}$</span>, respectively, and this is related to generalized MDPs.</p>
  <p>The Bellman equation in \ref{1} is defined with respect to</p>
  <ul>
  <li><p>the transition model <span class="math-container">$\color{blue}{P}$</span>, which describes the dynamics of the environment,</p>
  </li>
  <li><p><span class="math-container">$\color{red}{\max}$</span>, which is related to the assumption that the optimal agent acts greedily with respect to the optimal value function (keep in mind that the max operation is <a href="https://ai.stackexchange.com/q/11244/2444">non-expansive</a>)</p>
  </li>
  </ul>
  <p>A <strong>generalised MDP</strong> <a href="https://www.researchgate.net/profile/Csaba-Szepesvari/publication/245451971_Generalized_Markov_Decision_Processes_Dynamic_programming_and_Reinforcement-le_arning_Algorithms/links/00b4952921789cfd76000000/Generalized-Markov-Decision-Processes-Dynamic-programming-and-Reinforcement-le-arning-Algorithms.pdf" rel="nofollow noreferrer">[Szepesvári and Littman(1996)]</a> is a generalisation of multiple versions/definitions of MDPs that circulate around in the literature, including the definition above. More specifically, 2 concepts are generalised: transition model and the max operator.</p>
  <p>Mathematically, we can define a generalised MDP as a tuple <span class="math-container">$\langle \mathcal{S}, \mathcal{A}, R, \color{blue}{\oplus}, \color{red}{\otimes}, \gamma \rangle$</span>, where <span class="math-container">$\mathcal{S}, \mathcal{A}$</span> and <span class="math-container">$R$</span> are defined as above and</p>
  <ul>
  <li><p><span class="math-container">$\color{blue}{\oplus}: (\mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}) \rightarrow(\mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R})$</span> is a &quot;<strong>expected value-type</strong>&quot; operator that generalises <span class="math-container">$\color{blue}{P}$</span>; the intuition of this operator is the same as the input of <span class="math-container">$\color{blue}{P}$</span> that I described above</p>
  </li>
  <li><p><span class="math-container">$\color{red}{\otimes}:(\mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}) \rightarrow(\mathcal{S} \rightarrow \mathbb{R})$</span> is a &quot;<strong>maximization-type</strong>&quot; operator that generalises <span class="math-container">$\color{red}{\max}$</span>; the intuition of <span class="math-container">$\color{red}{\otimes}$</span> is also the same as the intuition of <span class="math-container">$\color{red}{\max}$</span> (i.e. it represents how the optimal agent would behave).</p>
  </li>
  </ul>
  <p>So, these are <a href="https://ai.stackexchange.com/a/20380/2444"><em>operators</em></a> (like the gradient operator or the <a href="https://ai.stackexchange.com/q/11057/2444">Bellman operator</a>) because they take as input a function and produce another function.</p>
  <p>Now, if we set</p>
  <ul>
  <li><p><span class="math-container">$(\color{blue}{\oplus} U)(s, a)=\sum_{s'} \color{blue}{P}(s, a, s') U(s, a, s')$</span> (so, in this case, it takes as input the function <span class="math-container">$U$</span>; note that, in this case, <span class="math-container">$\color{blue}{\oplus}$</span> is an <strong>expected value</strong> operator, with respect to the probability distirbution <span class="math-container">$\color{blue}{P}(s, a, s')$</span>)</p>
  </li>
  <li><p><span class="math-container">$(\color{red}{\otimes} Q)(s)=\color{red}{\max}_{a} Q(s, a)$</span> (note that this just uses the <span class="math-container">$\color{red}{\max}$</span>)</p>
  </li>
  </ul>
  <p>Then we get the usual <strong>expected-reward MDP model</strong>.</p>
  <h3>What are the advantages of Generalised MDPs?</h3>
  <p>In the literature, there are <strong>different versions of MDPs</strong>, such as</p>
  <ul>
  <li>Markov games <a href="https://courses.cs.duke.edu/spring07/cps296.3/littman94markov.pdf" rel="nofollow noreferrer">[Littman(1994)]</a></li>
  <li>alternating Markov games <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.3103&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">[Boyan(1992)]</a></li>
  <li>discounted expected-reward MDPs <a href="https://link.springer.com/content/pdf/10.1007/BF00992698.pdf" rel="nofollow noreferrer">[Watkins and Dayan(1992)]</a></li>
  <li>risk-sensitive MDPs <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.8264&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">[Heger(1994)]</a></li>
  <li>exploration-sensitive MDPs <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.5630&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">[John(1994)]</a></li>
  </ul>
  <p>Generalised MDPs generalise all these MDPs for different values of <span class="math-container">$\color{blue}{\oplus}$</span> and <span class="math-container">$\color{red}{\otimes}$</span>.</p>
  <p>The paper <a href="https://www.researchgate.net/profile/Csaba-Szepesvari/publication/245451971_Generalized_Markov_Decision_Processes_Dynamic_programming_and_Reinforcement-le_arning_Algorithms/links/00b4952921789cfd76000000/Generalized-Markov-Decision-Processes-Dynamic-programming-and-Reinforcement-le-arning-Algorithms.pdf" rel="nofollow noreferrer">[Szepesvári and Littman(1996)]</a> (that introduced GMDPs) provides more info about how we should set <span class="math-container">$\color{red}{\otimes}$</span> and <span class="math-container">$\color{blue}{\oplus}$</span> to get these different MDPs (see table 1).</p>
  <h3>Bellman equations in Generalised MDPs</h3>
  <p>The Bellman equation for the state value function can be expressed as follows in the context of GMDP</p>
  <p><span class="math-container">$$
  V^{*}=\color{red}{\otimes} \color{blue}{\oplus} \left(R + \gamma V^{*}\right)
  $$</span></p>
  <p>For the state-action value function, you can have the following Bellman equation</p>
  <p><span class="math-container">$$
  K Q=\color{blue}{\oplus} (R+\gamma \color{red}{\otimes} Q)
  $$</span></p>
  <p>or the one that relates <span class="math-container">$Q^{*}$</span> to <span class="math-container">$V^{*}$</span></p>
  <p><span class="math-container">$$
  Q^{*}=\color{blue}{\oplus} \left(R+\gamma V^{*}\right)
  $$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-20T13:51:27.630Z
Answers.LastActivityDate: 2024-03-20T16:05:31.193Z
Answers.LastEditDate: 2024-03-20T16:05:31.193Z
Answers.UserDisplayName: nbro
Body: <p>What is a generalized MDP?</p>
  <p>Here are a few sub-questions.</p>
  <ol>
  <li>How is it different than a &quot;regular&quot; MDP?</li>
  <li>How does it generalize the notion of an MDP?</li>
  <li>Why do we need a generalized MDP?</li>
  <li>Do generalized MDPs have some practical usefulness or they are just theoretical tools?</li>
  </ol>
  
Tags: <reinforcement-learning><reference-request><definitions><markov-decision-process>
Title: What is a generalized MDP?
UserDisplayName: nbro
ThreadText: # What is a generalized MDP?
  
  (Asked by: username_0 on 2019-03-14)
  
  What is a generalized MDP?
  
  Here are a few sub-questions.
  
  1. How is it different than a "regular" MDP?
  2. How does it generalize the notion of an MDP?
  3. Why do we need a generalized MDP?
  4. Do generalized MDPs have some practical usefulness or they are just theoretical tools?
  
  **Tags:** reinforcement-learning, reference-request, definitions, markov-decision-process
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-12-20. Score: 1 | Accepted answer
  
  (This answer is based on info that you can find in the paper [$\varepsilon $-MDPs: Learning in Varying Environments](https://www.jmlr.org/papers/volume3/szita02a/html/Szita02a.html), 2002, by István Szita et al. and [[Szepesvári and Littman(1996)]](https://www.researchgate.net/profile/Csaba-Szepesvari/publication/245451971_Generalized_Markov_Decision_Processes_Dynamic_programming_and_Reinforcement-le_arning_Algorithms/links/00b4952921789cfd76000000/Generalized-Markov-Decision-Processes-Dynamic-programming-and-Reinforcement-le-arning-Algorithms.pdf), the paper that proposed generalised MDPs. I just adapted the notation to be more consistent with [Sutton & Barto's book](http://incompleteideas.net/book/RLbook2020.pdf) and provided additional info and links).
  
  ### What is an MDP?
  
  Let's first start with the usual definition of an MDP.
  
  An MDP is defined by the tuple $\langle \mathcal{S}, \mathcal{A}, R, \color{blue}{P} , \gamma \rangle$, where
  
  * $\mathcal{S}$ is the set of states
  * $\mathcal{A}$ is the set of actions
  * $R: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$ is the [reward function](https://ai.stackexchange.com/q/10442/2444); so $R(s, a, s')$ is the reward for taking action $a \in \mathcal{A}$ in state $s \in \mathcal{S}$ and ending up in $s' \in \mathcal{S}$.
  * $\color{blue}{P}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1]$ is the **transition model**; so $\color{blue}{P}(s, a, s')$ is the probability of arriving in state $s'$ after having taken action $a$ in the state $s$. You could also [define the transition model to include the reward](https://ai.stackexchange.com/q/10442/2444), denoted by $\color{blue}{P}(s', r \mid s, a)$ to emphasize that it's a conditional probability distribution), but let's ignore this for now.
  * $0 \leq \gamma < 1$ is a discount factor, which can be useful for infinite-horizon problems
  
  Given this formulation of a decision problem, the goal is to maximize the expected reward. The objective function can be defined as follows
  $$
  \mathbb{E}\left[ \sum\_{t=0}^{\infty} \gamma^{t} R\_{t} \right] = \mathbb{E}\left[ G\_{t} \right],
  $$
  where $R\_{t}$ is the reward that we get at [time step $t$](https://ai.stackexchange.com/a/11605/2444).
  
  There are multiple ways to solve this problem. The most common is probably Q-learning.
  
  ### Q-learning
  
  In Q-learning, we try to estimate the state-action (or action) value function. The optimal value function is defined as follows
  
  $$
  Q^{\*}(s, a)=\sum\_{s'} \color{blue}{P}(s, a, s')\left(R(s, a, s')+\gamma \color{red}{\max} \_{a^{\prime}} Q^{\*}(s', a^{\prime})\right) \label{1}\tag{1},
  $$
  for all $s \in \mathcal{S}$.
  
  So, it's a function of the form $Q^{\*}: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$. To emphasize the main purpose of this function, it can be denoted/defined as $Q^{\*}(s, a) = \mathbb{E}\left[G\_t \mid a, s \right]$, so it's the expected return ($G\_t$ is the return or cumulative reward) for taking action $a$ in state $s$ under the optimal policy $\pi^\*$ (hence the $\*$).
  
  The equation (\ref{1}) is a recursive equation because $Q^{\*}(s, a)$ is defined in terms of itself, i.e. we use $Q^{\*}(s', a^{\prime})$ to define it. In this context, this type of recursive equation is also known as [**Bellman equation**](https://ai.stackexchange.com/q/11057/2444) (due to [Richard Bellman](https://en.wikipedia.org/wiki/Richard_E._Bellman), who contributed to the theory of dynamic programming, which is related to MDPs, as dynamic programming algorithms can be used to solve MDPs, given a transition model).
  
  One thing to keep in mind is that the optimal policy can be derived from the optimal state-action value function by acting greedily with respect to it.
  
  ### What is a Generalized MDP?
  
  Now, there's one reason why I colored the transition model and the max operation in the Bellman equation \ref{1} in $\color{blue}{\text{blue}}$ and $\color{red}{\text{red}}$, respectively, and this is related to generalized MDPs.
  
  The Bellman equation in \ref{1} is defined with respect to
  
  * the transition model $\color{blue}{P}$, which describes the dynamics of the environment,
  * $\color{red}{\max}$, which is related to the assumption that the optimal agent acts greedily with respect to the optimal value function (keep in mind that the max operation is [non-expansive](https://ai.stackexchange.com/q/11244/2444))
  
  A **generalised MDP** [[Szepesvári and Littman(1996)]](https://www.researchgate.net/profile/Csaba-Szepesvari/publication/245451971_Generalized_Markov_Decision_Processes_Dynamic_programming_and_Reinforcement-le_arning_Algorithms/links/00b4952921789cfd76000000/Generalized-Markov-Decision-Processes-Dynamic-programming-and-Reinforcement-le-arning-Algorithms.pdf) is a generalisation of multiple versions/definitions of MDPs that circulate around in the literature, including the definition above. More specifically, 2 concepts are generalised: transition model and the max operator.
  
  Mathematically, we can define a generalised MDP as a tuple $\langle \mathcal{S}, \mathcal{A}, R, \color{blue}{\oplus}, \color{red}{\otimes}, \gamma \rangle$, where $\mathcal{S}, \mathcal{A}$ and $R$ are defined as above and
  
  * $\color{blue}{\oplus}: (\mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}) \rightarrow(\mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R})$ is a "**expected value-type**" operator that generalises $\color{blue}{P}$; the intuition of this operator is the same as the input of $\color{blue}{P}$ that I described above
  * $\color{red}{\otimes}:(\mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}) \rightarrow(\mathcal{S} \rightarrow \mathbb{R})$ is a "**maximization-type**" operator that generalises $\color{red}{\max}$; the intuition of $\color{red}{\otimes}$ is also the same as the intuition of $\color{red}{\max}$ (i.e. it represents how the optimal agent would behave).
  
  So, these are [*operators*](https://ai.stackexchange.com/a/20380/2444) (like the gradient operator or the [Bellman operator](https://ai.stackexchange.com/q/11057/2444)) because they take as input a function and produce another function.
  
  Now, if we set
  
  * $(\color{blue}{\oplus} U)(s, a)=\sum\_{s'} \color{blue}{P}(s, a, s') U(s, a, s')$ (so, in this case, it takes as input the function $U$; note that, in this case, $\color{blue}{\oplus}$ is an **expected value** operator, with respect to the probability distirbution $\color{blue}{P}(s, a, s')$)
  * $(\color{red}{\otimes} Q)(s)=\color{red}{\max}\_{a} Q(s, a)$ (note that this just uses the $\color{red}{\max}$)
  
  Then we get the usual **expected-reward MDP model**.
  
  ### What are the advantages of Generalised MDPs?
  
  In the literature, there are **different versions of MDPs**, such as
  
  * Markov games [[Littman(1994)]](https://courses.cs.duke.edu/spring07/cps296.3/littman94markov.pdf)
  * alternating Markov games [[Boyan(1992)]](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.3103&rep=rep1&type=pdf)
  * discounted expected-reward MDPs [[Watkins and Dayan(1992)]](https://link.springer.com/content/pdf/10.1007/BF00992698.pdf)
  * risk-sensitive MDPs [[Heger(1994)]](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.8264&rep=rep1&type=pdf)
  * exploration-sensitive MDPs [[John(1994)]](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.5630&rep=rep1&type=pdf)
  
  Generalised MDPs generalise all these MDPs for different values of $\color{blue}{\oplus}$ and $\color{red}{\otimes}$.
  
  The paper [[Szepesvári and Littman(1996)]](https://www.researchgate.net/profile/Csaba-Szepesvari/publication/245451971_Generalized_Markov_Decision_Processes_Dynamic_programming_and_Reinforcement-le_arning_Algorithms/links/00b4952921789cfd76000000/Generalized-Markov-Decision-Processes-Dynamic-programming-and-Reinforcement-le-arning-Algorithms.pdf) (that introduced GMDPs) provides more info about how we should set $\color{red}{\otimes}$ and $\color{blue}{\oplus}$ to get these different MDPs (see table 1).
  
  ### Bellman equations in Generalised MDPs
  
  The Bellman equation for the state value function can be expressed as follows in the context of GMDP
  
  $$
  V^{\*}=\color{red}{\otimes} \color{blue}{\oplus} \left(R + \gamma V^{\*}\right)
  $$
  
  For the state-action value function, you can have the following Bellman equation
  
  $$
  K Q=\color{blue}{\oplus} (R+\gamma \color{red}{\otimes} Q)
  $$
  
  or the one that relates $Q^{\*}$ to $V^{\*}$
  
  $$
  Q^{\*}=\color{blue}{\oplus} \left(R+\gamma V^{\*}\right)
  $$
  
  
  ---
  
  