Markov Process

Markov process

A Markov process assumes that the world is always in one of a set of possible states.

• The word “Markov” implies that the probability of being in a state depends only on the previous states and not on the states before.
• The changes between states are captured by the transition probabilities $Pr(s_{t+1}|s_t)$ of moving to the next state $s_{t+1}$ given the current state $s_t$, where $t$ indexes the timestep.
• Hence, a Markov process is an evolving system that produces a sequence $s_1,s_2,s_3,\dots$ of states.

Markov Reward Process

A Markov reward process extends the Markov process to include a distribution $Pr(r_{t+1}|s_t)$ over the possible rewards $r_{t+1}$ received at the next time step, given that we are in state $s_t$. This produces a sequence $s_1,r_2,s_2,r_3,s_3,r_4,\dots$ of states and the associated rewards.

The Markov reward process also includes a discount factor $\gamma \in (0,1]$ that is used to compute the return $G_t$ at time $t$:

$$G_t=\sum _{k=0}^{\infty }{\gamma }^k{r}_{t+k+1}$$

The return is the sum of the cumulative discounted future rewards; it measures the future benefit of being on this trajectory. A discount factor of less than one makes rewards that are closer in time more valuable than rewards that are further away.

Markov Decision Process

A Markov Decision Process or MDP adds a set of possible actions at each timestep.

• The action $a_t$ changes the transition probabilities, which are now written as $Pr(s_{t+1}|s_t,a_t)$.
• The rewards can also depend on the action and are now written as $Pr(r_{t+1}|s_t,a_t)$.
• An MDP produces a sequence of $(s_1,a_1,r_2),(s_2,a_2,r_3),\dots$ of states $s_t$, actions $a_t$ and rewards $r_{t+1}$ which are received at the subsequent timestep.
• The entity that performs the actions is known as the agent.

Partially observable Markov decision process

In a partially observable Markov decision process or POMDP, the state is not directly visible. Instead, the agent receives an observation drawn from $Pr(o_t|s_t)$. Hence, a POMDP generates a sequence $s_1,o_1,a_1,r_2,s_2,o_2,a_2,r_3,\dots$ of states, observations, actions, and rewards. In general, each observation will be more compatible with some states than others but insufficient to identify the state uniquely.