← Back to Lesson 1

Asteroid Hop — Solution & Post-mortem

This is the worked solution to the Lesson 1 exercise — the code Owen wrote during the session, lightly cleaned up — followed by what the run shows, and an honest list of the mistakes made along the way. The mistakes are the valuable part: each one is a standard RL implementation bug, met here on an 11-state toy where the right answer is computable by hand.

The solution

Download lesson_1_asteroid_hop_solution.py

"""Lesson 1 solution — Asteroid Hop: value iteration.

See lesson_1_asteroid_hop.py for the full assignment. This is the
solution Owen wrote during Session 1, lightly cleaned up.

Converged result (59 sweeps to delta < 1e-9; the greedy policy stopped
changing at sweep 6 -- see the lesson's "policy freezes before values
converge" point):

    V* = [0.522, 0.548, 0.571, 0.619, 0.667,
          0.709, 0.780, 0.855, 0.900, 1.000]   (V[10] = 0, terminal)

    policy: JUMP for states 0-7, THRUST for 8-9
"""

GAMMA = 0.9
N_STATES = 11  # positions 0..10
TERMINAL = 10
THRUST = "THRUST"
JUMP = "JUMP"
ACTIONS = [THRUST, JUMP]


def outcomes(s, a):
    """All (prob, s_next, reward) outcomes of taking action `a` in state `s`.

    The +1 is collected on the transition INTO the terminal state;
    the terminal state itself is never updated and keeps V = 0.
    """
    if a == THRUST:
        s_next = min(s + 1, TERMINAL)
        return [(1.0, s_next, 1.0 if s_next == TERMINAL else 0.0)]
    # JUMP: +3 with p = 0.6, misfire -2 (floored at 0) with p = 0.4
    hit = min(s + 3, TERMINAL)
    miss = max(s - 2, 0)
    return [
        (0.6, hit, 1.0 if hit == TERMINAL else 0.0),
        (0.4, miss, 0.0),
    ]


def q_value(s, a, V):
    """One-step lookahead: E[r + GAMMA * V(s_next)] for action `a` in state `s`.

    GAMMA multiplies V[s_next] -- the future -- not the immediate reward.
    """
    return sum(p * (r + GAMMA * V[s_next]) for p, s_next, r in outcomes(s, a))


def value_iteration():
    """Sweep until the largest single-state change drops below 1e-9."""
    V = [0.0] * N_STATES
    sweep = 0
    while True:
        sweep += 1
        # Synchronous update: compute the whole sweep from the OLD values,
        # then swap. Updating V in place also converges (Gauss-Seidel
        # value iteration, often faster) -- but then later states in the
        # sweep would read this sweep's values, and the one-ring-per-sweep
        # picture printed below would lie to you.
        new_V = list(V)
        for s in range(TERMINAL):  # state 10 is terminal: V[10] stays 0
            new_V[s] = max(q_value(s, a, V) for a in ACTIONS)
        delta = max(abs(new_V[s] - V[s]) for s in range(N_STATES))
        V = new_V
        print(f"sweep {sweep:2d}: " + " ".join(f"{v:.3f}" for v in V))
        if delta < 1e-9:
            return V


def greedy_policy(V):
    """For each non-terminal state, the action with the highest Q."""
    return {s: max(ACTIONS, key=lambda a: q_value(s, a, V)) for s in range(TERMINAL)}


if __name__ == "__main__":
    V = value_iteration()
    print("Optimal policy:")
    for s, a in sorted(greedy_policy(V).items()):
        print(f"  state {s}: {a}")

What the run shows

Converged values (59 sweeps to a max change below 10−9):

state:   0      1      2      3      4      5      6      7      8      9     10
V*:    0.522  0.548  0.571  0.619  0.667  0.709  0.780  0.855  0.900  1.000  0.000

policy: JUMP for states 0–7, THRUST for states 8–9

The interesting boundary is state 8: Q(8, THRUST) = 0.9 · V[9] = 0.900 (certain) versus Q(8, JUMP) = 0.6 + 0.36 · V[6] = 0.881 (gamble) — the certain path wins by 0.019. Move one state left, to 7, and the gamble flips to winning. The game instinct "gamble when far from the goal, take the sure thing when close" is exactly what the math produces.

The deeper takeaway: the greedy policy stopped changing at sweep 6, while the values kept polishing digits until sweep 59. You don't need V to be right — only right enough to rank actions. That gap is part of why AlphaZero works at all with a sloppy learned value function.

Errors Owen submitted

The solution above is correct — but it didn't start that way. Here is everything that went wrong on the way there, in two piles: conceptual errors first, then typos and silly logic errors. (Predictions: P2 — the mixed JUMP-then-THRUST policy — was called exactly right, including both uncertain boundary states. P1 was wrong, in the single most instructive way available; see the first error below.)

Conceptual

  1. Discounting the immediate reward. P1 predicted V[9] = 0.9, reasoning that the win must be taxed by γ. Actually Q(9, THRUST) = 1 + 0.9 · V[10] = 1.0: γ multiplies V(s′) — the future — not the reward on the transition you're evaluating, which counts at full price. The expected 0.9 shows up one state earlier: V[8] = 0.9, a certain win two transitions away, taxed exactly once. This "when does the discount apply" off-by-one is a classic RL implementation bug. (The submitted code was correct; only the mental prediction was wrong.)
  2. Expected reward instead of expected return (diagnostic quiz, before the lesson). The proposed value definition counted only the next step's reward — which makes almost every mid-game action worth 0 in a sparse-reward game. The fix is one word: replace expected reward of the next state with expected return, i.e. the value of the next state. This gap is what the whole lesson was built to close.
  3. "Expected state" instead of "expected value of the state." States don't average — you push the expectation through V, not through the states. Average of values, not value of the average.
  4. Modeling the terminal state as a zero-reward self-loop — outcomes(10, ·) = [(1.0, 10, 0)] — instead of excluding it from updates. It happens to work here only because γ < 1 contracts the loop to 0. With γ = 1 — fine for win/lose games, per the lesson — a zero-reward self-loop makes any value of V[10] a fixed point. The skip-the-terminal-state convention survives both settings.
  5. No convergence criterion. The first submission ran a fixed range(99) of sweeps instead of tracking the per-sweep change and stopping below a threshold. Not pedantry: "how do I know it converged?" is the recurring question of this whole project — by Session 6 it becomes "has the network stopped improving?", and there is no range(99) answer there.
  6. In-place updates corrupting the experiment. Updating V mid-sweep (Gauss-Seidel value iteration) still converges — often faster — but later states in the sweep read this-sweep values, so the printed "value bleeds backward one ring per sweep" picture lies. The fix: compute each sweep synchronously from a copy and swap at the end.

Typos & silly logic errors

  1. delta + abs(...) — the convergence delta was computed and then thrown away (a bare expression, not an assignment). Combined with delta = 0 at the top of the loop, value iteration exited after exactly one sweep.
  2. delta =+ abs(...) — the attempted fix, still wrong: =+ parses as delta = +abs(...), so delta held only the last state's change — state 10's, which is always 0 — and the loop again exited after one sweep, printing a wrong policy. Note what kind of bug this was: no crash, no warning, plausible output. In Session 2, learning V from sampled play, this class of bug becomes nearly invisible because you can't eyeball "slightly wrong" anymore. The defense is tiny environments where you know ground truth — which is why Asteroid Hop sticks around as a regression test.
  3. Dead type-safety machinery that crashes when actually used. The original State(int) subclass had a range validator and an overridden __sub__ — and outcomes(State(1), JUMP) would crash, because in max(s - 2, 0) Python evaluates s - 2 first, lifting −1 back into State, and the validator raises before max ever sees it. The program only ran because the sweep loops used plain ints, bypassing the class everywhere. Machinery that reads like a guarantee but is dead code is worse than no machinery; the final version keeps the readable names and deletes the validation.
  4. Assorted small ones: printing a "best action" for the terminal state (no decisions happen there); raw 17-digit floats instead of :.3f; extracting the policy inside the update loop every sweep instead of once at the end.

The AlphaZero connection

You now own an 11-entry table of win-values, computed by exhaustive sweeps. In the AlphaZero paper, the network's value head v(s) is exactly this table — compressed into weights because the table can't be stored, and trained by regression toward sampled game outcomes (the (z − v)2 term in their loss) because the sweeps can't be run. Every concept in that loss term was just computed by hand here. Sessions 2 and 3 remove the two impossibilities — sweep everything and store everything — one at a time.

Continue to Lesson 2 — TD Learning & Self-Play →