Markov decision processes

A Markov decision process is the formal frame for sequential decision making. Five parts:

Symbol	Means
$S$	the states — everything the agent needs to know
$A$	the actions
$P(s'\mid s,a)$	the transition probabilities
$R(s,a)$	the reward
$\gamma$	the discount factor, 0 ≤ γ < 1

The Markov property: the future depends only on the current state, not on the whole history. If that does not hold, you have chosen the wrong state representation — not the wrong algorithm.

The discounting γ makes infinite sums finite and expresses that a reward now is worth more than a reward later. γ = 0.9 gives an effective horizon of about 10 steps; γ = 0.99 about 100.

The return: $G_t = \sum_{k=0}^{\infty}\gamma^k R_{t+k+1}$.

The value functions for a policy $\pi$: $V^\pi(s) = \mathbb E_\pi[G_t \mid S_t = s], \qquad Q^\pi(s,a) = \mathbb E_\pi[G_t\mid S_t=s, A_t=a]$

The Bellman equation — the whole field rests on it: $V^\pi(s) = \sum_a \pi(a|s)\sum_{s'} P(s'|s,a)\big[R(s,a) + \gamma V^\pi(s')\big]$

The value now = the immediate reward + the discounted value of the next state. The recursion is what makes it solvable.

Optimality: $V^*(s) = \max_a \sum_{s'}P(s'|s,a)[R(s,a)+\gamma V^*(s')], \qquad \pi^*(s) = \arg\max_a Q^*(s,a)\ .$

Two classic solution methods when the model is known: value iteration (update V until it converges) and policy iteration (alternate between evaluating and improving the policy). Both are guaranteed to converge for finite MDPs with $\gamma<1$.

When $P$ and $R$ are unknown — which is the normal case — you learn from experience instead: Q-learning, policy gradient, actor–critic.

import numpy as np

# A 4×4 grid: the goal at (3,3) gives +1, a hole at (1,1) gives -1, every step -0.04
N, GAMMA = 4, 0.9
GOAL, HOLE = (3, 3), (1, 1)
ACTIONS = [(-1,0), (0,1), (1,0), (0,-1)]

def nxt(s, a):
    r, c = s[0] + a[0], s[1] + a[1]
    return s if not (0 <= r < N and 0 <= c < N) else (r, c)

def reward(s):
    return 1.0 if s == GOAL else (-1.0 if s == HOLE else -0.04)

def value_iteration(tol=1e-6):
    V = {(r, c): 0.0 for r in range(N) for c in range(N)}
    while True:
        delta = 0.0
        for s in V:
            if s in (GOAL, HOLE):
                continue
            new = max(reward(nxt(s, a)) + GAMMA * V[nxt(s, a)] for a in ACTIONS)
            delta = max(delta, abs(new - V[s])); V[s] = new
        if delta < tol:
            return V

V = value_iteration()
for r in range(N):
    print(" ".join(f"{V[(r,c)]:6.2f}" for c in range(N)))
#  0.28  0.42  0.58  0.76
#  0.42 -1.00  0.76  0.96
#  0.58  0.76  0.96  1.18
#  0.76  0.96  1.18  0.00

The values grow towards the goal and fall towards the hole — the policy is read off by moving, in every square, to the neighbour with the highest value.