Open drills notebook (interactive)

Short problems for Volume 1. Aim for under 5 minutes per problem. All solutions are in collapsible sections.

Recall (R) — State definitions and rules

R1. Write the Bellman expectation equation for V^π(s) in words: “The value of state s under policy π is ___.”

Answer

“The value of state s under policy π is the expected immediate reward plus the discounted expected value of the next state, averaged over actions (weighted by the policy) and transitions.”

Formally: V^π(s) = Σ_a π(a|s) Σ_{s’} P(s’|s,a) [R(s,a,s’) + γ V^π(s’)].

R2. What are the five components of an MDP? Write the tuple notation.

Answer
(S, A, P, R, γ): S = state space, A = action space, P = transition probabilities P(s’|s,a), R = reward function R(s,a,s’), γ = discount factor.

R3. What is the Markov property? Why does RL need it?

Answer

The Markov property: P(S_{t+1}|S_0,…,S_t, A_0,…,A_t) = P(S_{t+1}|S_t, A_t). The future depends only on the current state and action, not the full history.

Why RL needs it: Without the Markov property, the agent would need to remember its entire history to make good decisions. The Markov property allows decision-making based only on the current state — making the problem tractable.

R4. What is the difference between policy evaluation and policy iteration?

Answer

Policy evaluation: compute V^π for a fixed policy π (using Bellman expectation equations iteratively).

Policy iteration: alternate between policy evaluation and policy improvement (act greedily w.r.t. V^π) until the policy stops changing. Converges to the optimal policy π*.

R5. When does value iteration converge, and how do you know?

Answer

Value iteration converges when the maximum change in V across all states in one sweep is less than a threshold ε (e.g. 1e-6): max_s |V_new(s) - V_old(s)| < ε.

The Bellman optimality operator is a contraction mapping (with factor γ), guaranteeing convergence to V*.

Compute (C) — Numerical exercises

C1. Compute the discounted return for rewards = [2, 0, -1] and γ = 0.9.

Try it — edit and run (Shift+Enter)
Answer
G = 2×1 + 0×0.9 + (-1)×0.81 = 2 - 0.81 = 1.19.

C2. In a 2-state MDP (A and B), both non-terminal: from A, go to B with probability 1, reward = 0. From B, go to A with probability 1, reward = 1. γ = 0.9. Current estimates: V(A) = 0.5, V(B) = 0.4.

Compute one Bellman backup: V_new(A) and V_new(B).

Try it — edit and run (Shift+Enter)
Answer
V_new(A) = 0 + 0.9 × 0.4 = 0.36. V_new(B) = 1 + 0.9 × 0.5 = 1.45.

C3. A 3×3 gridworld. Reaching state (2,2) terminates the episode with reward +1. All other transitions give reward 0. Discount γ=0.99. In an episodic MDP, what is V*(2,2) (at the terminal state), and what is V*(2,1) for the state one step before the goal?

Answer

By definition of episodic MDPs, the value of a terminal state is identically zero: V*(terminal) = 0, because no future rewards can be received after termination.

The reward +1 is earned on the transition entering the goal: V*(2,1) = R + γ × V*(2,2) = 1.0 + 0.99 × 0.0 = 1.0.

(From one step further back, e.g. state (2,0), the value is discounted: V*(2,0) = 0 + 0.99 × 1.0 = 0.99).

C4. Policy iteration step: given V^π(A)=0.3, V^π(B)=0.8, and transitions: from state S, action “go to A” gives R=0, action “go to B” gives R=0.1. γ=0.9. What is the greedy action?

Answer

Q(S, go-to-A) = 0 + 0.9 × 0.3 = 0.27. Q(S, go-to-B) = 0.1 + 0.9 × 0.8 = 0.1 + 0.72 = 0.82.

Greedy action: go to B (Q=0.82 > Q=0.27).

C5. One step of value iteration for a 2-action state: actions up and down, both deterministic.

  • up → reward 0, next state has V=0.5
  • down → reward 1, next state has V=0.2
  • γ=0.9

Compute V*(s).

Try it — edit and run (Shift+Enter)
Answer
Q(up) = 0 + 0.9×0.5 = 0.45. Q(down) = 1 + 0.9×0.2 = 1.18. V*(s) = max(0.45, 1.18) = 1.18 (optimal action: down).

Code (K) — Implementation

K1. Implement discounted_return(rewards, gamma) without using NumPy.

Try it — edit and run (Shift+Enter)
Solution
1
2

def discounted_return(rewards, gamma=0.9):
    return sum(gamma**t * r for t, r in enumerate(rewards))

K2. Implement iterative policy evaluation for a linear chain of 3 states (A, B, C) where C is terminal. Policy: always go right. Transitions: A→B gives reward 0, B→C gives reward +1 and terminates. γ=0.9. (Recall: V(C)=0 identically for the terminal state).

Try it — edit and run (Shift+Enter)
Solution
After 20 iterations: V(C)=0.0, V(B)=1.0, V(A)=0.9 (since V(A) = 0 + 0.9 × 1.0 = 0.9).

Debug (D) — Find and fix the bug

D1. Find and fix the bug in this synchronous value iteration implementation. It is supposed to perform synchronous (two-array) updates across sweeps, but mutates values in place during the sweep.

1
2
3
4
5
6
7

def value_iteration(V, transitions, gamma=0.9, n_iter=100):
    for _ in range(n_iter):
        for state in V:
            # transitions[state] = list of (reward, next_state)
            V[state] = max(r + gamma * V[next_s]
                          for r, next_s in transitions[state])
    return V
Try it — edit and run (Shift+Enter)
Answer
The bug: in-place mutation of V during a sweep means earlier states (already updated) are used when computing later states in the same sweep. While in-place (Gauss-Seidel) iteration can still converge in MDPs, synchronous value iteration requires computing all updates from the previous sweep’s values. Fix: compute V_new for all states in each sweep, then assign V = V_new.

D2. Find the bug in this epsilon-greedy implementation:

1
2
3
4
5

def epsilon_greedy(Q, epsilon=0.1):
    import random
    if random.random() > epsilon:    # Bug!
        return random.randrange(len(Q))
    return Q.index(max(Q))
Answer
The condition is reversed. random.random() > epsilon is True ~90% of the time (with ε=0.1), so the code mostly does random exploration (not greedy). Fix: if random.random() < epsilon: for exploration, else: return Q.index(max(Q)) for exploitation.

Challenge (X)

X1. Implement full policy iteration on a 3×3 gridworld: start at (0,0), goal at (2,2) with reward +1, -1 per step, walls give -1. Use a tabular representation. Report the optimal policy (one arrow per cell) and number of iterations until convergence.

Try it — edit and run (Shift+Enter)
Hint
  1. Initialize V=0, π=random for all states.
  2. Policy evaluation: iterate Bellman expectation until convergence.
  3. Policy improvement: for each state, set π(s) = argmax_a Q(s,a) using current V.
  4. Repeat until π doesn’t change. Expected result: arrows pointing toward (2,2) along the optimal path.