What is the Markov decision process' mathematical formulation of reinforcement learning? I have it from relevant authority that MDP formulation of reinforcement learning is:


*

*At time step t = 0 environemnt samples initial state $s_0 \sim p(s_0)$

*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:


*

*At time step t = 0 environemnt samples initial state $s_0 \sim p(s_0)$

*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}$


 A: 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.
