2. Markov Chains

Markov Chain

A Markov Chain is a finite set of discrete states, each of which has a probability distribution of how to transition between them.

Link to original

Markov Property

The Markov Property / Markov Assumption (Limited Horizon) is that we do not factor the history of previous states / transitions depend only on current state: $P(X_t|X_1,\dots ,X_{t-1})\approx P(X_t|X_{t-1})$

Link to original

Markov Decision Process

A Markov Decision Process is the process of looking at actions influencing state transitions. It is a sequential decision making problem for a fully observable yet stochastic environment.

Markov Chain holds, but now with probability of actions between states and rewards for action execution. This is reliant on two principles:

• Assume Markov property holds for action transitions.
• Probability distributions are stationary and don’t change.

We encode a reward for each state. Total utility of the agent is the sum of all rewards from all states visited.

A negative reward incentives optimality.

The MDP components for all states $s\in S$:

• transition model: $T(s,a,s^{\prime })$
• initial state of the problem: $s_0$
• reward function for a given state: $R(s)$

The MDP solution is not a plan of actions. The MDP solution is a policy $\pi$ which denotes the action $\pi (s)$ that should be taken for any state $s\in S$. The optimal policy (${\pi }^{\ast }$) will yield the highest expected utility in any given situation.

Link to original

Example Computations

Going back to our example, we can see computed optimal policies for different action probabilities, you can see that it is quite sensitive:

$R(s)=-0.04$	$R(s)=-0.01$	$R(s)=-1.65$

Solving MDPs

We use different approaches to solve MDPs:

• value iteration
• policy iteration
• linear programming

There are also situations where we are in a partially observable Markov Decision Process where we are unsure of what state we are in and are reliant on observations to build a history of states visited.