# Equivalent definitions of Markov Decision Process

I'm currently reading through Sutton's Reinforcement Learning where in Chapter 3 the notion of MDP is defined.

What it seems to me the author is saying is that an MDP is completely defined by means of the probability $$p(s_{t+1},r_t | s_t, a_t)$$.

However according to wikipedia, and many other references I've found an MDP is a quadruple of set of states, set of actions, transition probability $$P_{s_{t+1,s_t}}^{a_t} = p(s_{t+1} | s_t, a_t)$$ and an expected reward $$R_{s_{t+1},s_t}^{a_t}$$.

Now I'm assuming one definition implies the other, unless I'm wrong so please tell me...

The thing is Sutton manages to derives from it's definitions the wikipedia one. However as I can't find the other way around I was trying to show the converse.

The only hunch I had was observing that

$$R_{s_{t+1},s_t}^{a_t} = \sum_{r_{t+1},s_{t+1}} r_{t+1} p(r_{t+1}, s_{t+1} | s_t, a_t)$$

and maybe there're conditions that actually would allow me to retrieve $$p(r_{t+1},s_{t+1} | s_t, a_t)$$ but I cannot honestly see it.

Can you tell me then if the two are equivalent and why?

I think the name of the question is a bit misleading...

In general in mathematics, the question of 'equivalent definitions' usually arises when there are two formally complete definitions of a thing that we actually expect to be the same thing.

Considering the case presented here I have the following feelings:

1. Sutton a bad reference because he does not formally define or prove most of the things. That makes this book really confusing to read. Example: They 'prove' the Bellman equation but actually they are missing out / leaving out / ignoring most of the proof which is quite complicated (see this answer of mine). NOTE: This is just my very personal point of view and I surely disagree with some people regading this opinion on this book. So whatever 'definition' Sutton uses, I am pretty sure it is ambiguous,misleading and/or confusing.

2. The same applies to Wikipedia. Thea say that there is a reward function $$R_a(s,s')$$ but what is that function supposed to do? How exactly does it integrate with the probability variables? What if the reward is not deterministic but rather a random thing as well (like in one of the very first examples in Reinforcement Learning, the bandit machine)? Do these random variables have a common density that somehow 'splits' or why exactly does wikipedia say that the MDP is completely described by the marginal distributions $$p(s_{t+1}|s_t, a_t)$$? What happens if we have two different points in time $$t,r$$ and $$a_t = a_r$$ and $$s_{t+1}=s_{r+1}$$ and $$s_t = s_r$$... is then $$p(s_{t+1}|s_t,a_t) = p(s_{r+1}|s_r,a_r)$$? This is not at all clear because formally, $$S_t$$ is a different random variable from $$S_r$$...

Summarized: We have two definitions, one is confusing and incomplete and the other one is rather thought of as a summary and is also incomplete. Hence, the question on whether or not they are equivalent is hard to answer. However, there is hope. There is one 'complete' definition that allows us to prove two things: The Bellman equation and the fact that is the state and action space are 'nice' then there is a provably best (surprisingly deterministic) policy! The proof for the Bellman equation can be found in the link above and the proof for the surprising fact that there exist a best policy can be found in the only book that I really found so far to be a valuable source of information about RL: Puterman, Markov Decision Processes.

This definition goes as follows:

Definition A Markov Decision process consists of sets $$\mathcal{S}, \mathcal{A}, \mathcal{R}$$ and a (potentially infinite) set of random variables $$(S_t, A_t, R_t)_{t \in \text{time}}$$ where $$\text{time}$$ is either $$\mathbb{N}_0 = \{0,1,2,...\}$$ or a set of the form $$\text{time} = \{0,1,2,...,T\}$$ for some $$T \in \mathbb{N}$$ and such that for all $$t \in \text{time}$$, the random variables $$S_t,A_t,R_t,S_{t-1},A_{t-1},R_{t-1}, ..., S_0, A_0, R_0$$ have a common density $$f_{S_t,A_t,R_t,S_{t-1},A_{t-1},R_{t-1}, ..., S_0, A_0, R_0}$$ and all $$S_t$$ map into $$\mathcal{S}$$, all $$A_t$$ map into the set $$\mathcal{A}$$ and all $$R_t$$ map into the set $$\mathcal{R}$$. We make the following assumptions on all of the common densities:

• For every $$t, s_{t+1}, r_t, a_t, s_t, r_{t-1}, a_{t-1}, s_{t-1}, ..., r_0, a_0, s_0$$ $$p(s_{t+1}, r_{t} ,a_t | s_t, r_{t-1}, a_{t-1}, s_{t-1}, ..., r_{0}, a_0, s_0) = p(s_{t+1}, r_{t}, a_t | s_t)$$ This property is called the Markov property.
• Let us denote the density of a random variable $$X$$ by $$f_X$$. Let $$t,q \in \text{time}$$ and let $$s, s' \in S, a \in A, r \in \mathcal{R}$$ then
• $$f_{S_{t+1} | A_t, S_t}(s' | a, s) = f_{S_{q+1} | A_{q}, S_{q}}(s' | a, s)$$
• $$f_{R_{t} | S_{t+1}, A_t, S_t}(r | s', a, s) = f_{R_{q} | S_{q+1}, A_{q}, S_{q}}(r | s', a, s)$$
• $$f_{S_t|A_t}(s|a) = f_{S_{q}|A_{q}}(s|a)$$
or rather formulated like this: if $$s_{t+1} = s_{q+1}, r_{t} = r_{q}, a_t = a_{q}$$ and $$s_t = s_{q}$$ then $$p(s_{t+1} | a_t, s_t) = p(s_{q+1} | a_{q}, s_{q})$$ $$p(r_{t} | s_{t+1}, a_t, s_t) = p(r_{q} | s_{q+1}, a_{q}, s_{q})$$ and $$p(s_t|a_t) = p(s_{q}|a_{q})$$

Notes:

1. It is not clear that the random variables have a common density, we must assume it because there are random variables without a density (not even talking about common density!).
2. It is not clear that these random variables are forgetful with respect to the 'past', we need to assume it!
3. It is not clear that the densities at different times coincide, we must assume it!
4. Let's say that we have two MDPs $$M = (S_t, A_t, R_t)$$ and $$M' = (S'_t, A'_t, R'_t)$$ over the same time index set. Then we say that $$M$$ and $$M'$$ are 'equal' if all their finite densities coincide, i.e. if for all $$t$$, $$f_{S_t,A_t,R_t,S_{t-1},A_{t-1},R_{t-1}, ..., S_0, A_0, R_0} = f_{S'_t,A'_t,R'_t,S'_{t-1},A'_{t-1},R'_{t-1}, ..., S'_0, A'_0, R'_0}$$ (as functions). Let's write $$p(x)$$ for the density $$f_X$$ in order to make things more simple. By definition and the first assumption, we have \begin{align*} &p(s_t,a_t,r_t,s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0) \\ &= p(s_t,a_t,r_t|s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0) * p(s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0) \\ &= p(s_t,a_t,r_t|s_{t-1}) * p(s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0) \end{align*} Decomposing the latter part inductively we see that we can write $$p(s_t,a_t,r_t,s_{t-1},a_{t-1},r_{t-1}, ..., s_0, a_0, r_0)$$ as product of the densities $$p(s_t,a_t,r_t|s_{t-1})$$ and $$p(s_0)$$. By a straightforward computation we see that $$p(s_{t+1}, r_t, a_t| s_t) = p(r_t|s_{t+1}, a_t, s_t) p(s_{t+1}|a_t,s_t)p(a_t|s_t)$$ By the second assumption, all these densities are the same (independently of the time). This leads to the following very important insight: Everything we know to describe a MDP up to 'equality' as defined above is the four densities $$p(r|s',a,s), p(s'|a,s), p(a|s)$$ (where $$s'$$ takes the role of $$s_{t+1}$$, $$s$$ is $$s_t$$, $$a$$ is $$a_t$$ and $$r$$ is $$r_t$$) and finally, $$p(s_0)$$. So in that sense, a MDP is completely described by saying how the situation develops from one step in time to the next (in the sense that if two MDP's have the same way of going from onestep in time to the next then they are equal). Now an interesting question arises: Given these four densities, can we create an MDP (in some sense 'the unique' MDP, because any two different with the same four densities would be 'equal') from them? The answer is yes, but it is not as easy as you might think: See my question on mathoverflow.

Based on the last note, there is one more thing that one should say about this setup: There also is the notion of a Markov Decision Automata (MDA). Everytime you search for MDP, you will definitely stumble upon MDA. People draw some kind of weird graph next to the definition of an MDP but it is totally unclear how these two things fit together. By the last note, the MDP is completely described by four densities (in two senses: given these densities, we can actually create an MDP from them and any two MDPs we create from them are equal) and what an MDA defines is exactly those four densities. That means: Given an MDA which is nothing else than describing the four densities: initial distribution of the state $$p(s_0)$$, a reward distribution $$p(r|s',a,s)$$, a state transition distribution $$p(s'|s)$$ and a policy $$p(a|s)$$ usually denotes as $$\pi(a|s)$$ then the MDA gives rise to an MDP.

Note that when people try to optimize the policy they are actually doing something quite complicated: They have fixed densities $$p(s_0), p(r|s',a,s), p(s'|s)$$ and they start with some policy $$\pi(a|s)$$. Then they give rise to the MDP with these densities and use it to evaluate the performance of the policy. Then they change the polica to something else $$\pi'(a|s)$$ and do this construction (giving rise to an MDP from an MDA) again and re-evaluate the performance, etc etc etc.

Sorry for the long answer but I invested a lot of time in order to understand what is actually going on under the hood and the sources that I found left me very very puzzled (e.g. by simply using assumptions without stating them, etc).

Final note: no measure theory neede din order to understand this answer ;-)

APPENDIX: I was asked what 'common density' means. A random variable (let's say $$X$$) is a function from a probablity space $$\Omega$$ into some other space $$\mathcal{X}$$. Notice that the 'P'-symbol in probability theory is not something 'bogus'/magical but rather has a very clear definition (it is a measure on (the sigma algebra on) $$\Omega$$). We say that $$X$$ has a density $$f$$ iff. the expressions $$P[X \in A]$$ can be expressed as $$\int_A f(x) dx$$ (here, dx is a 'natural' measure on $$\mathcal{X}$$, e.g. the Lebesgue measure if $$\mathcal{X}=\mathbb{R}$$ and the counting measure if $$\mathcal{X}$$ is finite) for all sets $$A$$ (in the sigma algebra on $$\mathcal{X}$$). If we are given a touple of random variables $$(X,Y)$$ then we can regard them as one single function into $$\mathcal{X} \times \mathcal{Y}$$ and if this random variable has a density then we say that $$X,Y$$ have a 'common density'. Intuitively that means not much more than being able to compute with expressions $$p(x,y)$$ instead of the clumsy $$P[X \in A, Y \in B]$$.

• I agree on the book, it's terrible. But it's the only reference I found for Reinforcement learning. Nov 5, 2020 at 11:20
• can you clarify what do you mean with "common density"? Nov 6, 2020 at 13:24
• Attempted to extend the answer... however, by the nature of things, a density is something heavily measure theory related ... :-( Nov 9, 2020 at 8:21
• Can we have a chat? Cause I have some understanding of measure theory. Nov 9, 2020 at 11:30
• @user8469759: Could you create a chat and link it here? I am really busy at work these days... might be that it takes a while for me to respond though :-( Nov 9, 2020 at 13:00