Practice · One Gridworld for Everything

0. The practice grid

We will use this world for every calculation on this page.

A

B

G · +5

C

D

P · −5

\(G\): goal terminal state
\(P\): penalty terminal state
Actions: \(\mathcal{A}=\{\uparrow,\downarrow,\leftarrow,\rightarrow\}\)
Movement is deterministic
Hitting a wall means staying in the same state
Every normal movement gives \(r=-1\)
Entering \(G\) gives \(+5\); entering \(P\) gives \(-5\)
Discount: \(\gamma=0.9\)
After reaching \(G\) or \(P\), the episode ends

1. Representing it as an MDP

An MDP is the tuple

(1) \[ \mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma). \]

State space:

(2) \[ \mathcal{S}=\{A,B,C,D,G,P\}. \]

From \(B\), for example:

Action	Next state	Reward
↑	\(B\) (wall)	\(-1\)
↓	\(D\)	\(-1\)
←	\(A\)	\(-1\)
→	\(G\)	\(+5\)

Because movement is deterministic,

(3) \[ P(G\mid B,\rightarrow)=1, \]

meaning a \(100\%\) probability of reaching \(G\) when we take right from \(B\).

2. One trajectory and return

Suppose the agent follows

(4) \[ C \;\rightarrow\; D \;\rightarrow\; B \;\rightarrow\; G. \]

C → D → B → G

Rewards along the way:

(5) \[ -1,\;\; -1,\;\; +5. \]

The return from \(C\) is

(6) \[ G_0 = -1 + 0.9\,(-1) + 0.9^2\,(5) = -1 - 0.9 + 4.05. \]

\(G_0 = 2.15\)

Remember this number. It will reappear as the optimal value of \(C\).

3. Policy evaluation

Start with a random (uniform) policy:

(7) \[ \pi(a\mid s)=0.25 \qquad\text{for every action \(a\).} \]

Initialize non-terminal values to zero:

(8) \[ V_0(A)=V_0(B)=V_0(C)=V_0(D)=0, \qquad V(G)=V(P)=0. \]

Why terminals are zero

After termination no further rewards occur, so the expected remaining return is \(0\). We hold \(V(G)=V(P)=0\) forever.

The synchronous Bellman expectation update (deterministic \(P\)) is

(9) \[ V_{k+1}(s) = \sum_{a}\pi(a\mid s) \Big[ r(s,a) + \gamma V_k(s') \Big]. \]

Because transitions are deterministic we do not need an extra sum over \(s'\).

Iteration 1

State \(A\)

From \(A\):

↑ — stay at \(A\), reward \(-1\)
↓ — move to \(C\), reward \(-1\)
← — stay at \(A\), reward \(-1\)
→ — move to \(B\), reward \(-1\)

Since all initial values are zero:

(10) \[ V_1(A) = \tfrac14\Big[ (-1+0.9\cdot 0) + (-1+0.9\cdot 0) + (-1+0.9\cdot 0) + (-1+0.9\cdot 0) \Big] = -1. \]

\(V_1(A)=-1\)

State \(B\)

(11) \[ V_1(B) = \tfrac14\big[ -1 + (-1) + (-1) + 5 \big] = 0.5. \]

\(V_1(B)=0.5\)

The positive value appears because one action reaches the goal.

State \(C\)

All four actions currently produce reward \(-1\) into zero-valued successors:

\(V_1(C)=-1\)

State \(D\)

Three normal actions give \(-1\); right enters the penalty \(-5\):

(12) \[ V_1(D) = \tfrac14\big[-1-1-1-5\big] = -2. \]

\(V_1(D)=-2\)

After iteration 1
State	\(V_1\)
\(A\)	\(-1\)
\(B\)	\(0.5\)
\(C\)	\(-1\)
\(D\)	\(-2\)

Iteration 2 — example for \(A\)

Now use the previous values:

(13) \[ V_2(A) = \tfrac14\Big[ (-1+0.9 V_1(A)) + (-1+0.9 V_1(C)) + (-1+0.9 V_1(A)) + (-1+0.9 V_1(B)) \Big]. \]

(14) \[ V_2(A) = \tfrac14\big[ -1.9 - 1.9 - 1.9 - 0.55 \big] = -1.5625. \]

\(V_2(A)=-1.5625\)

After evaluating all states through iteration 2
State	\(V_1\)	\(V_2\)
\(A\)	\(-1\)	\(-1.5625\)
\(B\)	\(0.5\)	\(-0.0625\)
\(C\)	\(-1\)	\(-2.125\)
\(D\)	\(-2\)	\(-2.5625\)

Repeating until convergence under the random policy gives approximately

(15) \[ V^{\pi}(A)\approx -5.22,\quad V^{\pi}(B)\approx -2.32,\quad V^{\pi}(C)\approx -6.00,\quad V^{\pi}(D)\approx -5.00. \]

Reading the result

These values are poor: the random policy frequently hits walls and sometimes walks into the penalty. Evaluation did its job — it told the truth about a bad policy.

4. Policy improvement

Now calculate one-step action values under the converged \(V^{\pi}\):

(16) \[ q(s,a)=r(s,a)+\gamma V^{\pi}(s'). \]

At state \(B\)

(17) \begin{align*} q(B,\uparrow) &= -1 + 0.9(-2.32) = -3.09, \\ q(B,\downarrow) &= -1 + 0.9(-5.00) = -5.50, \\ q(B,\leftarrow) &= -1 + 0.9(-5.22) = -5.70, \\ q(B,\rightarrow) &= 5. \end{align*}

Therefore

(18) \[ \pi_{\mathrm{new}}(B) = \arg\max_a q(B,a) = \rightarrow. \]

Doing this for every state yields the greedy policy

→

G · +5

→

↑

P · −5

(19) \[ \pi(A)=\rightarrow,\quad \pi(B)=\rightarrow,\quad \pi(C)=\rightarrow,\quad \pi(D)=\uparrow. \]

5. Evaluate the improved policy

The policy is now deterministic, so evaluation collapses to a short chain of equations.

State \(B\)

\(B\) goes directly to the goal:

\(V(B)=5\)

State \(A\)

(20) \[ V(A)=-1+0.9\,V(B)=-1+0.9(5)=3.5. \]

\(V(A)=3.5\)

State \(D\)

(21) \[ V(D)=-1+0.9\,V(B)=3.5. \]

\(V(D)=3.5\)

State \(C\)

(22) \[ V(C)=-1+0.9\,V(D)=-1+0.9(3.5)=2.15. \]

\(V(C)=2.15\)

Same number as the trajectory return in Section 2 — because that path is what the improved policy does from \(C\).

A3.50

B5.00

G—

C2.15

D3.50

P—

6. Policy Iteration

Policy Iteration alternates

(23) \[ \text{evaluate }\pi \;\longrightarrow\; \text{improve }\pi. \]

Random policy \(\pi\)

↓

Evaluate its values \(V^{\pi}\)

↓

Choose better actions (greedy)

↓

Evaluate the new policy

↓

No better action exists → \(\pi^*\)

Therefore the final policy is optimal. At \(C\), two paths are equally good:

(24) \[ C\rightarrow D\rightarrow B\rightarrow G \qquad\text{or}\qquad C\rightarrow A\rightarrow B\rightarrow G. \]

(25) \[ -1 + 0.9(-1) + 0.9^2(5) = 2.15. \]

So \(\pi^*(C)\) may be either \(\rightarrow\) or \(\uparrow\) — both are optimal.

7. Value Iteration

Value Iteration folds evaluation and improvement into one update:

(26) \[ V_{k+1}(s) = \max_a \Big[ r(s,a)+\gamma V_k(s') \Big]. \]

Instead of averaging actions, we immediately take the best one. Initialize \(V_0(s)=0\) for non-terminals.

Iteration 1

For \(B\):

(27) \[ V_1(B)=\max(-1,-1,-1,5)=5. \]

For \(A\), every action currently looks like \(-1\). Same for \(C\). For \(D\), the best action avoids the penalty and also yields \(-1\):

After VI iteration 1
State	\(V_1\)
\(A\)	\(-1\)
\(B\)	\(5\)
\(C\)	\(-1\)
\(D\)	\(-1\)

Iteration 2

(28) \[ V_2(A)=-1+0.9\,V_1(B)=-1+4.5=3.5, \qquad V_2(D)=3.5. \]

But \(C\) still does not yet “see” the goal clearly:

(29) \[ V_2(C)=-1.9. \]

After VI iteration 2
State	\(V_2\)
\(A\)	\(3.5\)
\(B\)	\(5\)
\(C\)	\(-1.9\)
\(D\)	\(3.5\)

Iteration 3

Now \(C\) sees that both \(A\) and \(D\) are valuable:

(30) \[ V_3(C)=-1+0.9(3.5)=2.15. \]

\(V_3(C)=2.15\)

Final \(V^*\) — values no longer change
State	\(V^*\)
\(A\)	\(3.5\)
\(B\)	\(5\)
\(C\)	\(2.15\)
\(D\)	\(3.5\)

8. Policy Iteration vs Value Iteration

Policy Iteration

Fully evaluate the current policy,
then improve it.

evaluate → improve → repeat

Value Iteration

One optimal Bellman update,
then repeat.

\(V\leftarrow\mathcal{T}^*V\) until fixed

Both produce the same optimal policy:

→

G · +5

↑ / →

↑

P · −5

The most important observation

The goal value spreads backward:

Iteration 1: \(B\) discovers the goal
Iteration 2: \(A\) and \(D\) discover \(B\)
Iteration 3: \(C\) discovers \(A\) and \(D\)

That backward propagation of reward information is the core mechanism behind every Bellman-based reinforcement learning algorithm — DP, TD, and Q-learning all live inside this picture.

A B ✓ G

Step 1 — goal lights \(B\)

A ✓ B G

C D ✓ P

Step 2 — \(A\) and \(D\) light up

A B G

C ✓ D P

Step 3 — \(C\) finally sees the path

Dynamic Programming

You just did a full PI and VI by hand. The chapter formalizes it.

Open DP →

One gridworld for everything

0. The practice grid

1. Representing it as an MDP

2. One trajectory and return

3. Policy evaluation

Iteration 1

State \(A\)

State \(B\)

State \(C\)

State \(D\)

Iteration 2 — example for \(A\)

4. Policy improvement

At state \(B\)

5. Evaluate the improved policy

State \(B\)

State \(A\)

State \(D\)

State \(C\)

6. Policy Iteration

7. Value Iteration

Iteration 1

Iteration 2

Iteration 3

8. Policy Iteration vs Value Iteration

Policy Iteration

Value Iteration

See also

Dynamic Programming