MDPs in reinforcement learning, explained in 5 lines

Module 16 · Advanced AI · 23 concepts

In depth / 15 lines

MDPs, in more detail

A Markov Decision Process is the formal frame that reinforcement learning is built on.

It has states, actions, transition probabilities, rewards and a discount factor.

The state is the situation the agent is in.

The action is what it can do, and the transition says where that leads.

Transitions are probabilistic, since the same action need not always have the same result.

The reward is the immediate feedback for that step.

The Markov property says the future depends only on the current state.

The path taken to get there does not matter, which is a strong assumption.

It is what makes the mathematics tractable and is often only approximately true.

The fix is usually to put more history into the state until it becomes true enough.

The discount factor makes distant rewards worth less than immediate ones.

A value near one makes the agent far-sighted, and a low value makes it greedy.

It also keeps the total finite when a task never ends.

Solving an MDP means finding a policy, which maps each state to the best action.

Real problems are partially observable, since the agent sees an observation rather than the true state.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath MDPs

The five things a problem needs to be an MDP

\langle \mathcal{S}, \; \mathcal{A}, \; P, \; R, \; \gamma \rangle

$\mathcal{S}$ : the set of states.
$\mathcal{A}$ : the set of actions.
$P(s' \mid s, a)$ : the probability of landing in $s'$ .
$R(s, a)$ : the reward for taking $a$ in $s$ .
$\gamma$ : the discount.

Writing a problem in this form is most of the work of applying reinforcement learning to it, and it is where most attempts go wrong.

P(s_{t+1} \mid s_t, a_t) = P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots)

The Markov property is the assumption that the current state contains everything relevant. The history adds nothing once you know where you are.

That is a claim about the state representation rather than about the world.

A state that omits something important makes the environment non-Markov, and the fix is a better state, not a better algorithm.

The Bellman equations

V^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s'} P(s' \mid s, a) \big[ R(s, a) + \gamma V^{\pi}(s') \big]

The value of a state is the immediate reward plus the discounted value of where you end up, averaged over the policy and the transitions.

V^{*}(s) = \max_{a} \sum_{s'} P(s' \mid s, a) \big[ R(s, a) + \gamma V^{*}(s') \big]

The optimality equation replaces the average over actions with a maximum, and its solution is the value of behaving optimally forever.

This is a recursion rather than a formula, and every method in the field is a way of solving it: exactly when the model is known, and by sampling when it is not.

Solving it when $P$ and $R$ are known

Initialise $V(s)$ to zero for every state.
Sweep every state, replacing $V(s)$ with the right-hand side of the optimality equation.
Repeat until the largest change in a sweep falls below a tolerance.
Read the optimal policy off as the action achieving each maximum.
Stop, since that policy is provably optimal.

\|V_{k+1} - V^{*}\|_{\infty} \leq \gamma \|V_k - V^{*}\|_{\infty}

Value iteration converges because the Bellman operator is a contraction with factor $\gamma$ , so the error shrinks geometrically and the fixed point is unique.

O(|\mathcal{S}|^{2} |\mathcal{A}|) \text{ per sweep}

That is also why it is unusable on real problems: the state space of a board game or a robot is astronomically large and cannot be swept once, let alone repeatedly.

When the assumptions fail

If the agent sees an observation rather than the state, the problem becomes a POMDP.

The standard response is to make the state a summary of the history, which is what a recurrent or attention-based policy does.

Unknown $P$ and $R$ call for model-free learning.

When the transition probabilities are unknown, the expectations cannot be computed and must be sampled instead, which is exactly what Q-learning and policy gradients do.

A continuous $\mathcal{S}$ calls for function approximation.

And when the state space is continuous or enormous, the table becomes a network.

That is the step from classical reinforcement learning to the deep version, and the step that gives up every convergence guarantee above.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What does the Markov property state?

Advanced AI

23 concepts in this module, then a graded test with every answer explained.

Study this module →