# What is the Markov decision process' mathematical formulation of reinforcement learning?

I have it from relevant authority that MDP formulation of reinforcement learning is:

1. At time step t = 0 environemnt samples initial state $s_0 \sim p(s_0)$
2. Then, for t = 0 until done:
• Agent selects action $a_t$
• Environment samples reward $r_t \sim R(.|s_t, a_t)$
• Environment samples next state $s_{t+1} \sim P(.|s_t, a_t)$
• Agent receives reward $r_t$ and next state $s_{t+1}$

Question: Is the reward not a single number given $a_t, s_{t+1}$ and $s_t$? If we are sampling $s_{t+1}$ then sampling reward as well does not make sense to me. I think the process should instead be:

1. At time step t = 0 environemnt samples initial state $s_0 \sim p(s_0)$
2. Then, for t = 0 until done:
• Agent selects action $a_t$
• Environment samples reward $\require{enclose} \enclose{horizontalstrike}{r_t \sim R(.|s_t, a_t)}$
• Environment samples next state $s_{t+1} \sim P(.|s_t, a_t)$
• Agent receives reward $\require{enclose}\enclose{horizontalstrike}r_t$ $r_t|(s_t, s_{t+1}, a_t)$ and next state $s_{t+1}$
• The reward you get at stage $t$ does not depend on $s_{t+1}$. It may depend on the action $a_t$. It may also be random. Your definition allows for non-Markovian processes, because the reward you receive at a given stage depends on state occupancies at different stages. Jun 3, 2018 at 15:42
• en.wikipedia.org/wiki/Markov_decision_process#Definition Jun 3, 2018 at 15:52
• That formulation is not actually correct. Consider a one-period MDP, where there is no future state, or the reward you get at the final stage of a finite MDP, where again there is no future state. The definition as given compresses two distinct concepts - receiving the reward and transitioning into the next state - into one. It is true that for, probably, the vast majority of MDPs, the Wikipedia definition will work just fine, but, referring to Puterman (in the next comment)... Jun 3, 2018 at 16:03
• "As a result of choosing action $a \in A_s$ in state $s$ at decision epoch $t$, 1) The decision-maker receives a reward $r_t(s,a)$ and 2) the system state at the next epoch is determined by the probability distribution $p_t(\cdot|s,a)$." (Markov Decision Processes, p. 19 of my edition). Jun 3, 2018 at 16:04
• @jbowman Letting $r_t$ depend only on $s_t$ and $a_t$, or additionally letting it also depend on $s_{t+1}$, is kind of equivalent. $s_{t+1}$ itself is determined by $s_t$ and $a_t$, so any influence that $s_{t+1}$ may have on $r_t$ can be considered to be, say "baked in" in the influence that $s_t$ and $a_t$ have on $r_t$. Jun 4, 2018 at 10:57

## 1 Answer

For the theoretical basis of reinforcement learning, in the MDP model we care about the Markov property - that the state $s_t$ captures all necessary information to define the distributions of $r_t$ [many sources would use $r_{t+1}$ conventionally] and $s_{t+1}$ given $a_t$.

The two values $r_t$ and $s_{t+1}$ can be derived in multiple different ways, and don't have to be sampled separately. They can be sampled separately, or they can be correlated - the important detail is that the knowable distribution of $r_t$ and $s_{t+1}$ only depends on $s_t$.

The reward system can be set up fairly arbitrarily depending on the goals of the agent. Your idea that reward should be deterministic single value based on the observed $(s_t, a_t, s_{t+1})$ defines a valid MDP, but does not cover all possible MDPs.

The slide from the tutorial you link and quote is also a valid MDP. It is not showing how the elements $r_t$ and $s_{t+1}$ are being sampled. The notation implies independent uncorrelated samples generated from the environment, which is an option. However, I think that is just a detail that has been skipped over - in practice the environment progresses according to its rules, and the sampling of reward and next state are correlated in time.

In addition to depending on any combination of $(s_t, a_t, s_{t+1})$, a reward $r_t$ may have a stochastic element. Reward schemes can be stochastic for a variety of reasons, although the situation does not often turn up in the toy examples used to teach RL.

There are two subtly different cases I can think of:

• The reward is not a direct property of the state, but a consequence of it, subject to unmeasurable and unknowable fluctuations. For instance, in a chemical reactor vessel, you might have actions to add reagents, heat and/or stir the mixture at a certain rate. The reward could be the amount of a desired product that is made. The state would be the measurable concentrations of reagents, current temperature and motion. The reward would fluctuate depending on things you cannot realistically measure or know (you might also try to model these as a POMDP, but it is relatively common to treat physical measurement limitations as stochastic variation).

• The reward is determined randomly by the environment. For instance, in a fantasy fighting game, where your goal is to collect gold by fighting monsters, the treasure dropped by a defeated monster might be randomly chosen according to the type of monster.

There are probably other similar cases and examples.

• Amazing explanation. Directly addresses the question asked. But, I am afraid what i wanted to ask is not exactly what i ended up asking in the question. It is that i know the $a_t$ before sampling the reward so the deterministic single value reward that i suggest will be a function of $a_t$ as well. Please read the edit. I apologize i wasted your time. Kindly, edit the answer accordingly Jun 3, 2018 at 20:30
• Can you provide me an example where given $(a_t, s_t, s_{t+1})$ there might be different rewards for different runs? Jun 4, 2018 at 8:17
• I did not get that example in its essence the way i got others. Not a man of finance. anyhow, speaking of : $r_t$ determined by $s_{t}$ and independent of both $a_t$ and $s_{t+1}$ Is this not a function of $a_t$ and $s_{t+1}$? for example $f(x) = 5$ Jun 4, 2018 at 9:55
• @MiloMinderbinder I have updated the answer to focus more on this "rewards may also be stochastic" aspect. Jun 4, 2018 at 16:21