Markov and Partially Observable Decision Processes › Worked Example: Solving a Two-State MDP by Hand

Michael BrenndoerferJune 7, 20265 min read
World Models HandbookAll chapters
Part 2 of 12Inference, Decisions, and Control
Chapter 7Markov and Partially Observable Decision Processes › Worked Example: Solving a Two-State MDP by Hand
Reading section 5 of 14 · Worked Example: Solving a Two-State MDP by Hand · 5 minSection 5 of 14 · 5 min

Book contents

World Models Handbook12 parts · 72 chaptersView the whole book →
Active chapter 7 of 72

Section 5 of 14 · 5 min read

Markov and Partially Observable Decision Processes › Worked Example: Solving a Two-State MDP by HandOne section · Sections in this chapter5 / 14 ↓
Sections in this chapter14
Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Before writing any code, let us solve a complete MDP analytically. The problem is small enough to do with algebra, which makes the Bellman machinery concrete.

A machine is either working (W) or broken (B). When working, you may operate it, earning reward 4 per step, but each step it breaks with probability 0.1. Alternatively you may service it, earning nothing but keeping it working. When broken, you may repair it at a cost of 2, returning it to working state in one step, or wait and earn nothing while it stays broken. The discount factor is γ=0.9\gamma = 0.9.

First, guess the structure of the optimal policy: operate when working, repair when broken. We will verify the guess afterward. This guess-and-verify pattern is a standard analytical technique: in small problems you can hypothesize the shape of the solution, solve the resulting linear system, and then check that no alternative action contradicts the hypothesis. Under this policy, the Bellman expectation equations read:

v(W)=4+0.9[ 0.9 v(W)+0.1 v(B) ],v(\mathrm{W}) = 4 + 0.9\big[\, 0.9\, v(\mathrm{W}) + 0.1\, v(\mathrm{B}) \,\big], v(B)=−2+0.9 v(W).v(\mathrm{B}) = -2 + 0.9\, v(\mathrm{W}).

Substituting the second equation into the first:

v(W)=4+0.81 v(W)+0.09[ 0.9 v(W)−2 ]=3.82+0.891 v(W).v(\mathrm{W}) = 4 + 0.81\, v(\mathrm{W}) + 0.09\big[\, 0.9\, v(\mathrm{W}) - 2 \,\big] = 3.82 + 0.891\, v(\mathrm{W}).

Solving, v(W)=3.82/0.109≈35.05v(\mathrm{W}) = 3.82 / 0.109 \approx 35.05, and then v(B)≈0.9×35.05−2≈29.54v(\mathrm{B}) \approx 0.9 \times 35.05 - 2 \approx 29.54.

Now verify the guess by checking that neither alternative action beats the assumed one. Servicing instead of operating when working yields 0+0.9×35.05≈31.550 + 0.9 \times 35.05 \approx 31.55, which is less than 35.05. Waiting instead of repairing when broken yields 0.9×29.54≈26.590.9 \times 29.54 \approx 26.59, less than 29.54. Both alternatives lose, so the guessed policy is indeed optimal, and the values are correct.

The guess-and-verify calculation has already certified that operating in W and repairing in B are the winning actions. We can therefore iterate the fixed-policy Bellman backup for those two actions from zero; it reaches the same values that the full max-based optimality operator T\mathcal{T} would compute.

In[5]:
Code
## Two-state maintenance MDP: states W(0), B(1); actions operate/repair taken optimally.
gamma_2s = 0.9
P_opt = np.array(
    [
        [0.9, 0.1],  # working, operating
        [1.0, 0.0],
    ]
)  # broken, repairing
r_vec = np.array([4.0, -2.0])

v_hand = np.array([35.05, 29.54])  # analytic solution from above

v_iter = np.zeros(2)
two_state_errors = []
for sweep in range(300):
    v_next = r_vec + gamma_2s * (P_opt @ v_iter)
    two_state_errors.append(np.max(np.abs(v_next - v_iter)))
    v_iter = v_next
    if two_state_errors[-1] < 1e-10:
        break

ref_line = two_state_errors[0] * gamma_2s ** np.arange(len(two_state_errors))
Out[6]:
Visualization
Log-scale convergence of the fixed-policy Bellman-backup error toward the analytic fixed point.
Repeated fixed-policy Bellman backups for the certified optimal actions converge to the analytic values 35.05 and 29.54, contracting geometrically at rate gamma = 0.9.

The iterates settle onto the exact fixed point computed by substitution, while the displayed hand values are rounded to 35.0535.05 and 29.5429.54. With the stopping rule used here, the remaining numerical fixed-point error is on the order of 10−910^{-9}; the larger dotted offset against the two-decimal hand value is therefore rounding, not failed convergence. The error falls along the γk\gamma^k reference slope.

Three observations are worth drawing out. First, the value of a working machine, about 35, vastly exceeds any single-step reward, because it prices in the entire expected future stream. Value is a stock of future income, not a flow, and the discount factor determines the exchange rate between them. Second, the value gap is exact: v(W)−v(B)=2+0.1v(W)=600/109≈5.5046v(W)-v(B)=2+0.1v(W)=600/109\approx5.5046. The immediate repair cost contributes 2, while the remaining term prices the repair transition against the working state's discounted future. Third, the same numbers would fall out of value iteration automatically: the algebra we did by hand is what the fixed-point iteration computes numerically. Starting from zeros, applying T\mathcal{T} repeatedly converges to these same two numbers without ever forming a linear system explicitly. When a problem is too large to solve as a linear system, iterative methods take its place.