Markov decision processes: states, actions, rewards and the Bellman equations

Let

1. S be a finite non-empty set (the set of states),
2. A be a finite non-empty set (the set of actions),
3. P : S × A × S → [0, 1], (s, a, s′) ↦ P(s′ | s, a), be a function such that ∑_{s′ ∈ S} P(s′ | s, a) = 1 for all s ∈ S and a ∈ A (the transition probabilities — for every pair (s, a), P(· | s, a) is a distribution on S),
4. R : S × A × S → ℝ be a function (the reward for the transition from s via action a to s′),
5. γ ∈ [0, 1) be a number (the discount factor).

A Markov decision process (MDP) is the five-tuple

(S, A, P, R, γ).

How the process runs: at times t = 0, 1, 2, … the agent is in state s_t ∈ S, chooses an action a_t ∈ A, the world moves it to state s_t+1 and the agent receives the reward r_t+1 = R(s_t, a_t, s_t+1). The states s_t and actions a_t are random variables and the Markov property holds: for every t ∈ ℕ₀ and all s₀, …, s_t−1, s, s′ ∈ S, a₀, …, a_t−1, a ∈ A for which the condition has positive probability,

P(s_t+1 = s′ | s_t = s, a_t = a, s_t−1, a_t−1, …, s₀, a₀) = P(s′ | s, a).

The next state thus depends only on the current state and action, not on the history — just as in a Markov chain, except that the transition is also influenced by the agent’s choice. A state s ∈ S is terminal if and only if P(s | s, a) = 1 and R(s, a, s) = 0 for every a ∈ A: whoever enters it stays there and receives nothing more — this models the end of an episode (here the cliff and both goals).

The agent stands on the square right of the start (a wall above it, the cliff below) and chooses “right”, p = 0.2:

• 0.8 — the next square to the right,
• 0.1 — the cliff (reward −10, the end),
• 0.1 — the square right of the start (slips up into the wall and stays where it is),

together 0.8 + 0.1 + 0.1 = 1 (colours as in the formula above: the intended step and slipping sideways). The expected immediate reward of this move is 0.8 · 0 + 0.1 · (−10) + 0.1 · 0 = −1: on average one in ten such steps ends in a fall.

Let (S, A, P, R, γ) be an MDP and r₁, r₂, … ∈ ℝ the rewards the agent successively receives. The return from time t ∈ ℕ₀ is the discounted sum of future rewards

G_t = ∑_k=0^∞ γ^k r_t+k+1 = r_t+1 + γ r_t+2 + γ² r_t+3 + …

(the series converges, see the theorem below; after entering a terminal state all further rewards are 0).

A policy is a rule by which the agent chooses an action based on the current state:

1. a deterministic policy is a function π : S → A; at time t the agent chooses a_t = π(s_t);
2. a stochastic policy is a function π : A × S → [0, 1], (a, s) ↦ π(a | s), such that ∑_{a ∈ A} π(a | s) = 1 for every s ∈ S; the agent chooses an action at random with P(a_t = a | s_t = s, history) = π(a | s).

A deterministic policy is a special case of a stochastic one with π(a | s) = 1 if and only if a = π(s). A fixed policy π turns the MDP into a Markov chain on S with transition probabilities p_ss′ = ∑_{a ∈ A} π(a | s) P(s′ | s, a). The goal is a policy with the largest possible expected return (made precise in the definition of the value function below).

Let (S, A, P, R, γ) be an MDP with γ ∈ [0, 1) and R_max = max_{s, s′ ∈ S, a ∈ A} |R(s, a, s′)| (the maximum exists because S and A are finite). Then for every policy, every t ∈ ℕ₀ and every run of the process, the series G_t converges absolutely and

|G_t| ≤ R_max (1 + γ + γ² + …) = R_max/1 − γ,

even if the episode never ended.

Proof. Every reward is r_t+k+1 = R(s_t+k, a_t+k, s_t+k+1), so |r_t+k+1| ≤ R_max. The triangle inequality gives |G_t| ≤ ∑_{k ≥ 0} γ^k |r_t+k+1| ≤ R_max ∑_{k ≥ 0} γ^k, and a geometric series with ratio 0 ≤ γ < 1 sums to 1/1 − γ. ∎

Here R_max = 10 and γ = 0.9, so |G| ≤ 10/0.1 = 100. Without a cost per step it is much less still: a nonzero reward comes only from entering a goal or the cliff, and at most once per episode, so |G| ≤ 10. That is why γ = 1 can be used only where the episode is certain to end.

On a solid floor the shortest path to the +10 goal takes 6 steps. The first five steps give reward 0, the sixth (entering the goal) +10. With γ = 0.9:

G₀ = 0 + 0.9 · 0 + 0.9² · 0 + 0.9³ · 0 + 0.9⁴ · 0 + 0.9⁵ · 10 = 0.59049 · 10 = 5.9049.

On a solid floor nothing random happens, so this is directly the value of the start — and value iteration in the section on policies does indeed give 5.90. The small +1 goal, even 3 steps away, would give only 0.9² · 1 = 0.81.

Let (S, A, P, R, γ) be an MDP with γ ∈ [0, 1), π a policy, and let E_π denote the expected value when behaving according to π. The value function of the policy π is the function V^π : S → ℝ and the action value is the function Q^π : S × A → ℝ,

V^π(s) = E_π[G_t | s_t = s],   Q^π(s, a) = E_π[G_t | s_t = s, a_t = a]

(thanks to the Markov property they do not depend on t). V^π(s) is thus the expected return when the agent starts in s and follows π; for Q^π(s, a) we choose the first action a ourselves and only then does the agent follow π. The optimal values are

V*(s) = max_π V^π(s),   Q*(s, a) = max_π Q^π(s, a)   for all s ∈ S, a ∈ A,

and a policy π* is optimal if and only if V^π*(s) = V*(s) for all s ∈ S. (For a finite MDP with γ < 1 the maxima exist and there is an optimal deterministic policy.)

The following holds (Richard Bellman, 1957):

1. the Bellman equation for a deterministic policy π: for all s ∈ S V^π(s) = ∑_{s′ ∈ S} P(s′ | s, π(s)) [R(s, π(s), s′) + γ V^π(s′)];
2. the Bellman optimality equation: for all s ∈ S and a ∈ A Q*(s, a) = ∑_{s′ ∈ S} P(s′ | s, a) [R(s, a, s′) + γ V*(s′)],   V*(s) = max_{a ∈ A} Q*(s, a), and V* is the only function S → ℝ that satisfies these equations;
3. every deterministic policy π* with π*(s) ∈ argmax_{a ∈ A} Q*(s, a) for all s ∈ S is optimal.

The finished optimal values of the start’s neighbours: the square above the start V* = 3.325, the square to the right V* = 2.260, the start itself V* = 2.854; the cliff is terminal (value 0, reward −10). We plug them into the right-hand side for each action (colours as in the Bellman equation above):

• ↑: 0.8 · (0 + 0.9 · 3.325) + 0.1 · (0 + 0.9 · 2.260) + 0.1 · (0 + 0.9 · 2.854) = 2.854,
• →: 0.8 · (0 + 0.9 · 2.260) + 0.1 · (−10 + 0.9 · 0.000) + 0.1 · (0 + 0.9 · 3.325) = 0.926,
• ↓: 0.8 · (−10 + 0.9 · 0.000) + 0.1 · (0 + 0.9 · 2.854) + 0.1 · (0 + 0.9 · 2.260) = −7.540,
• ←: 0.8 · (0 + 0.9 · 2.854) + 0.1 · (0 + 0.9 · 3.325) + 0.1 · (−10 + 0.9 · 0.000) = 1.354,

The results are Q*(start, a). The largest (max_a) is ↑ with 2.854, and that is exactly V*(start) — the equation holds (the difference in the last digit is rounding). The action “up” is worth something even despite the 10% chance that the agent slips to the left, hits the edge and stays on the start: that is why V*(start) also appears on the right-hand side. The action “down” leads into the cliff 80% of the time and comes out deeply negative.

The Bellman operator of the MDP (S, A, P, R, γ) is the mapping B that assigns to every function V : S → ℝ the function BV : S → ℝ,

(BV)(s) = max_{a ∈ A} ∑_{s′ ∈ S} P(s′ | s, a) [R(s, a, s′) + γ V(s′)].

Value iteration is the algorithm:

• input: an MDP (S, A, P, R, γ) with γ ∈ [0, 1) and a tolerance ε > 0;
• output: approximate optimal values V : S → ℝ and a deterministic policy π : S → A.

1. Set V₀(s) = 0 for all s ∈ S and k = 0.
2. Compute V_k+1 = BV_k, i.e. V_k+1(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V_k(s′)] for all s ∈ S.
3. If max_{s ∈ S} |V_k+1(s) − V_k(s)| < ε, continue with step 4; otherwise increase k by 1 and go back to step 2.
4. Return V = V_k+1 and π(s) ∈ argmax_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V(s′)] for every s ∈ S.

For γ < 1, B is a contraction in the maximum norm: for all U, V : S → ℝ, max_s |(BU)(s) − (BV)(s)| ≤ γ · max_s |U(s) − V(s)|. Since BV* = V* (the Bellman optimality equation), it follows that max_s |V_k(s) − V*(s)| ≤ γ^k · max_s |V₀(s) − V*(s)|: the error falls at least as fast as γ^k and the algorithm terminates for every ε > 0. By the definition of an MDP, terminal states have V_k = 0 in every round, which is why the pseudocode below does not recompute them at all.

We follow two squares in the middle row: A right to the left of the big +10 goal and B one square further, right to the right of the small +1 goal. Above B there is a wall, above A free space, below both an ordinary floor.

Round 1 (V₀ = 0 everywhere): from A a step to the right leads into the goal with probability 0.8, i.e. 0.8 · 10 = 8.000. From B nothing distant is visible yet; the best is a step to the left towards the small goal: 0.8 · 1 = 0.800.

Round 2: from B going right leads into A, which already has value 8: 0.8 · 0.9 · 8 = 5.76, plus 0.1 · 0.9 · 0.8 = 0.072 for slipping up (a wall, so it stays in B with V₁ = 0.8) and 0 for slipping down — in total 5.832 (colours as in the Bellman equation in the previous section; the new value V_k+1 has the colour of V*). The best action in B has flipped from ← to →: the information about the big goal has travelled one square further.

Policy iteration (Ronald Howard, 1960) is the algorithm:

• input: an MDP (S, A, P, R, γ) with γ ∈ [0, 1) and an initial deterministic policy π₀ : S → A;
• output: an optimal deterministic policy π and its value function V^π = V*.

1. Set i = 0.
2. Evaluation: compute V^π_i : S → ℝ as the (unique) solution of the system of |S| linear equations V(s) = ∑_{s′ ∈ S} P(s′ | s, π_i(s)) [R(s, π_i(s), s′) + γ V(s′)],   s ∈ S.
3. Improvement: for every s ∈ S choose π_i+1(s) ∈ argmax_{a ∈ A} Q^π_i(s, a), where Q^π_i(s, a) = ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V^π_i(s′)]; if π_i(s) is among the maximizers, keep π_i+1(s) = π_i(s).
4. If π_i+1 = π_i (i.e. π_i+1(s) = π_i(s) for all s ∈ S), stop and return π = π_i; otherwise increase i by 1 and go back to step 2.

That the returned policy is optimal and that the algorithm always terminates is stated by the policy improvement theorem below.

Let (S, A, P, R, γ) be an MDP with γ ∈ [0, 1), π : S → A a deterministic policy and π′ : S → A a deterministic policy such that π′(s) ∈ argmax_{a ∈ A} Q^π(s, a) for all s ∈ S. Then

1. V^π′(s) ≥ V^π(s) for all s ∈ S;
2. if Q^π(s, π(s)) = max_{a ∈ A} Q^π(s, a) for all s ∈ S (the improvement has nothing to change, π′ = π), then V^π satisfies the Bellman optimality equation, V^π = V* and π is optimal;
3. otherwise there exists s ∈ S with V^π′(s) > V^π(s).

Proof sketch. By the choice of π′, V^π(s) = Q^π(s, π(s)) ≤ Q^π(s, π′(s)) = E[r + γ V^π(s′)]. We substitute the same inequality into V^π(s′), then again… After unrolling, what remains is the expected return of the policy that plays π′ in all steps, i.e. V^π′(s). ∎

There are finitely many deterministic policies — here 4 actions on 19 non-terminal squares, i.e. 4¹⁹ ≈ 2.7 · 10¹¹. None can repeat (every round either improves the value or ends), so policy iteration always terminates. In practice surprisingly few rounds are needed: here 6.