# What is a generalized MDP?

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?

(This answer is based on info that you can find in the paper $$\varepsilon$$-MDPs: Learning in Varying Environments, 2002, by István Szita et al. and [Szepesvári and Littman(1996)], the paper that proposed generalised MDPs. I just adapted the notation to be more consistent with Sutton & Barto's book and provided additional info and links).

### What is 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; 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, 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$$.

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 optional 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 (due to Richard Bellman which 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)

A generalised MDP [Szepesvári and Littman(1996)] 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 (like the gradient operator or the Bellman operator) 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

Generalised MDPs generalise all these MDPs for different values of $$\color{blue}{\oplus}$$ and $$\color{red}{\otimes}$$.

The paper [Szepesvári and Littman(1996)] (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)$$