Lesson 1 — From Bandits to Value Functions

In a bandit problem, an action's value is simple: Q(a) = 𝔼[r | pull a] — the expected reward of pulling that arm. In a multi-turn game like Star Realms, that definition falls apart, and fixing it leads to the single most important object in this whole project: the value function. This lesson builds it from scratch.

The punchline first

Suppose someone handed you a perfect oracle that, for any Star Realms state s, returned the probability you'd win from that state if both players played optimally — call it V^*(s). How should you play? At each decision, for each legal action, average the oracle's value over the states you might land in, weighted by their probability — then take the action with the highest average. That's called acting greedily with respect to V^*, and it is provably optimal play.

Hold onto this, because it's the punchline of the entire project: if you have a good V, playing well is trivial. Everything we'll build — TD learning, neural networks, MCTS, AlphaZero — is machinery for getting a good V (and compensating when it's imperfect).

A tempting — but wrong — definition

Here's a natural first guess at what an action is worth mid-game: the expected reward of the next state, weighted by the probability of reaching it.

Q(s, a) =? ∑_s′ P(s′ | s, a) · r(s, a, s′)

The problem: in our game, every reward is 0 except the final winning move. So under this definition, almost every mid-game action has value 0 — buying a battleship on turn 3 is "worth" nothing, because no immediate reward follows. That obviously can't be the right notion of value. Something is flowing backward from that final +1 to turn 3, and this definition doesn't capture it. Fixing it gives us the Bellman equation.

Reward, return, value

Three words that sound alike but mean different things. Getting these straight resolves the confusion entirely.

Reward r — what the environment hands you on a single step. In our game: 0, 0, 0, …, 0, +1. Myopic, instantaneous.

Return G — the sum of all rewards from now until the game ends:

G_t = r_t+1 + r_t+2 + ⋯ + r_T

In our game the return is brutally simple: G = 1 if you go on to win, 0 if you lose, no matter where in the game you are. (General RL adds a discount factor γ that shrinks far-future rewards —

G_t = r_t+1 + γ·r_t+2 + γ²·r_t+3 + ⋯

— but for a game that always ends with a win or loss, we can use γ = 1 and ignore it.)

Value V(s) — the expected return starting from state s, given how both players behave from there on:

V^π(s) = 𝔼[G | start in s, follow policy π thereafter]

With our 0/1 rewards: V(s) is just the probability you win from s. That's why the oracle above was called V^*. The ^* means "under optimal play by everyone."

So the fix to the tempting definition is one word: replace expected reward of the next state with expected return — equivalently, the value of the next state. Buying the battleship on turn 3 has no immediate reward, but it lands you in a state with a higher win probability, and that is its value.

The Bellman equation — the tempting definition, made recursive

Write the action value down properly. The value of taking action a in state s (this is what Q(s, a) idiomatically means):

Q(s, a) = ∑_s′ P(s′ | s, a) · [ r(s, a, s′) + V(s′) ]

In words: over every state s′ you might land in, weight by the probability of landing there, and count both the immediate reward and the value of where you end up. (If states were continuous this sum would be an integral — Star Realms states are discrete, so sums.)

And what is V(s) itself? If you act greedily — the oracle strategy from the top — then:

V^*(s) = max_a ∑_s′ P(s′ | s, a) · [ r(s, a, s′) + V^*(s′) ]

That's the Bellman optimality equation. Notice the strange loop: V^* is defined in terms of itself, at other states. It's not a formula you evaluate; it's a consistency condition — a fixed-point equation that the true win probabilities must satisfy. The reason no other function satisfies it is the same reason "value flows backward": terminal states pin the recursion down (V = 1 at won states, 0 at lost states), and consistency propagates those anchors backward through the whole game.

Value iteration

The fixed-point view suggests an algorithm, almost insolently simple:

Initialize V(s) arbitrarily — all zeros, say.
Sweep over every state, replacing
V(s) ← max_a ∑_s′ P(s′ | s, a) · [ r + V(s′) ]
i.e., force each state to be consistent with its neighbors' current estimates.
Repeat until nothing changes.

This is value iteration, and it's guaranteed to converge to V^*. The intuition for why: each sweep propagates correct information one more step backward from the terminal states — after one sweep, states one move from the end are exactly right; after two sweeps, states two moves out; and so on.

Saying `Q`(`s`, `a`) in English

Q(s, a) = "how good is it to take action a from state s?" — precisely: the expected return (total future reward) if you take a now and play on from there. And since our game's only reward is +1 for winning: Q(s, a) = "the probability I eventually win, given that I do a right now."

One phrasing trap to avoid: it is not "the expected state" you reach. States don't average — there's no "average of BattleBlob-in-my-discard and no-BattleBlob." It's the expected value of the state you land in — push the expectation through V, don't average the states themselves: Q(s, a) = 𝔼[r + V(s′)]. Average of values, not value of the average. That one formula is the whole thing.

The discount factor, properly

The exercise below uses γ = 0.9, so the discount stops being a footnote. Two things to internalize:

γ multiplies V(s′) — the future — not r. The reward on the transition you're currently evaluating counts at full price; γ only taxes rewards that arrive after the next state. In general, a certain win k steps away is worth γ^k−1. (Off-by-one errors about "when does the discount apply" are a classic RL implementation bug.)
With γ < 1, V(s) stops meaning "win eventually" and starts meaning roughly "win soon." Without it, every policy that wins eventually has value 1.0 and there's nothing to choose between them; with it, speed versus risk becomes a real tradeoff.

Check questions

In Star Realms terms: it's mid-game, you have V^* on tap, and you're choosing between AcquireFromTradeRow(BattleBlob) and EndTurn. Both have immediate reward 0. Why does Q(s, a) still distinguish them — where does the difference come from, mechanically, in the formula?
Value iteration sweeps over every state. Give a back-of-envelope reason this is a non-starter for Star Realms. (The state is five 48-card count vectors per player, plus scalars.) The answer is the entire motivation for the next two lessons: learning V from sampled games instead of sweeps, and compressing V into a neural network instead of a table.

The exercise — Asteroid Hop

Time to run value iteration with your own hands. The game is a single-player toy — no opponent to worry about yet: you pilot a ship across an asteroid field of positions 0–10, choosing every step between a guaranteed THRUST (+1) and a risky JUMP (+3 with probability 0.6, slide back −2 with probability 0.4). Reaching 10 wins: reward +1. Discount γ = 0.9, which is what makes the speed-versus-risk choice real.

The assignment is the stub below — download lesson_1_asteroid_hop.py, implement the four functions, and run it. Write down your P1/P2 predictions before the first run; watching the values bleed backward from state 10, one ring per sweep, is the whole point.

"""Lesson 1 exercise — Asteroid Hop: value iteration by hand.

THE GAME (single player, so no opponent to worry about yet)

  You pilot a ship across an asteroid field of positions 0..10.
  You start at position 0. Reaching position 10 (or past it -- cap
  at 10) wins the game: reward +1, episode over. Every other reward
  is 0. State 10 is terminal: nothing happens there, ever again.

  Two actions are available in every non-terminal state:

    THRUST -- move +1, guaranteed.
    JUMP   -- move +3 with probability 0.6;
              misfire and slide back -2 with probability 0.4
              (position floors at 0).

  Discount factor GAMMA = 0.9. The discount is what makes the choice
  interesting: without it, every policy wins eventually and all values
  are 1.0. With it, V(s) means roughly "win SOON," so speed vs. risk
  is a real tradeoff.

YOUR JOB

  Implement the three functions below, then run this file. You should
  see value bleed backward from state 10, one ring of states per
  sweep -- the "anchors propagate" claim from the lesson, live.

BEFORE YOU RUN IT, write down two predictions:

  P1: What does V[9] converge to, exactly?
      (You can compute both Q(9, THRUST) and Q(9, JUMP) in your
      head -- which wins?)
  P2: Will the optimal policy be all-THRUST, all-JUMP, or mixed?
      If mixed, which end of the board jumps? Think about what you'd
      do in a real game when you're far behind versus one step from
      winning.

ONE TRAP TO AVOID

  Leave V[10] = 0 forever. The +1 was collected on the transition
  INTO 10 -- terminal states have no future, hence no value. (This
  same off-by-one bites people in real AlphaZero implementations,
  so meet it now on an 11-state toy.)
"""

GAMMA = 0.9
N_STATES = 11  # positions 0..10; state 10 is terminal
THRUST = "THRUST"
JUMP = "JUMP"
ACTIONS = [THRUST, JUMP]


def outcomes(s, a):
    """Return the transition model for taking action `a` in state `s`.

    Returns a list of (prob, s_next, reward) tuples -- every state you
    might land in, the probability of landing there, and the reward
    collected on that transition.

    THRUST has one outcome; JUMP has two. Landing on (or past) 10
    caps at 10 and earns reward +1 -- the +1 belongs in the returned
    tuple's `reward` slot, NOT in V[10] (see the trap above). A
    misfire that would go negative floors at 0, with reward 0.
    The probabilities in the returned list must sum to 1.

    You may assume `s` is non-terminal (s < 10); the caller never
    passes s = 10.
    """
    # your code here
    raise NotImplementedError


def q_value(s, a, V):
    """Expected value of taking action `a` in state `s`, judged by the
    current value estimates `V` (a list of N_STATES floats).

    This is the one-step lookahead from the lesson:

        Q(s, a) = sum over outcomes of  prob * (reward + GAMMA * V[s_next])

    Don't forget the discount.
    """
    # your code here
    raise NotImplementedError


def value_iteration():
    """Run value iteration to convergence and return the final V.

    - Start with V = [0.0] * N_STATES.
    - Sweep: for each NON-terminal state s, replace V[s] with
      max over actions of q_value(s, a, V). (State 10 stays 0 -- see
      the trap in the module docstring.) Compute each sweep from a
      fresh copy of V (a "synchronous" update): updating V in place
      also converges, but then the printout below won't show the
      clean one-ring-per-sweep picture the lesson promised.
    - Track the largest single-state change in each sweep; stop when
      it drops below 1e-9.
    - Print V after every sweep, each value formatted to ~3 decimals.
      Watching the values fill in backward IS the point of the
      exercise, so don't skip the printing.
    """
    # your code here
    raise NotImplementedError


def greedy_policy(V):
    """Return the greedy policy as a dict {state: action} -- for each
    non-terminal state, the action whose q_value is highest.
    """
    # your code here
    raise NotImplementedError


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

See the solution → (the worked code, the converged values, and an honest post-mortem of the mistakes made the first time through)