Markov reward process

A Markov reward process is defined by the tuple $⟨\mathcal{S},\mathcal{P},\mathcal{R},\gamma ⟩$, where:

• $\mathcal{S}$ is the state space
• ${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}\left[S_{t+1}=s^{\prime }|S_t=s\right]$ is the state transition probability matrix
• $\mathcal{R}$ is the reward function, where ${\mathcal{R}}_s=\mathbb{E}[R_{t=1}|S_t=s]$.
• $\gamma \in [0,1]$ is discount factor for future rewards.

MRP vs Markov chain

The only difference between an MRP and a Markov chain is that there is now a reward associated with each state, and the agent will select an action $a$ that will get the most reward ${\mathcal{R}}_{s^{\prime }}$ at time $t$.

The return $G_t$ for an MRP is the total discounted reward from time-step $t$: $G_t=R_{t+1}+\gamma R_{t+2}+\dots ={\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$

The state-value function for an MRP is defined as: $v(s)=\mathbb{E}[G_t|S_t=s]$

Example: A student's MRP

with value function:

Apply the Bellman optimality equation: