REASONING FROM SCRATCH · CHAPTER 03

RL vocabulary
& bandits

Prompting can elicit reasoning. Training it needs a different language: actions, rewards, and a reason to try the snack nobody has bought yet.

~16 min read1 interactiveTested Python

What you'll learn

  • The words: agent, environment, action, reward, policy, value
  • The incremental update that every later algorithm reuses
  • ε-greedy, UCB, and Thompson sampling on one 4-armed kiosk
  • Why a completion is a contextual bandit, and why that is not enough

Before you start

  • Test-time search — why we want to learn a verifier’s taste
  • Mean and expectation

The kiosk that cannot see the next passenger

A station kiosk can display one snack at a time: pretzel, tea, a folded map, or candy. Each passenger either buys (reward 1) or walks past (reward 0). True buy-rates are 0.40, 0.25, 0.15, 0.10. The clerk does not know that.

If they always show the pretzel after one lucky sale, they never learn that tea is decent and candy is not. If they shuffle at random, they waste the pretzel. That tension is explore versus exploit. It is the whole of a bandit. There is no “state” that carries over. The next passenger does not depend on the last snack.

A language model that writes one reply and gets one score is this kiosk, with the prompt as extra context. One prompt, one completion, one reward: a contextual bandit. Multi-step reasoning needs the next chapter’s MDPs.

Six words, then four elements

WordKioskLLM later
AgentThe clerkThe policy we train
EnvironmentPassengersThe prompt plus a checker
ActionWhich snack to showA token, or a whole reply
RewardBought or notA preference score or a pass/fail
Policy \(\pi\)How they pick the snack\(\pi_\theta(y \mid x)\)
Value \(Q\)Expected buy-rate of a snackExpected reward of a reply

Sutton & Barto name four elements of an RL problem: the policy, the reward signal, the value function, and (optionally) a model of the environment. A bandit has no useful model and no next state. Reward is immediate. Value is just “how good is this arm?”

kiosk · reward · explore · vocab

MANIM Bandits: reward without a next room — explore vs exploit.

Supervised

A labeled answer. The loss is on that answer. No explore.

Bandit / RL

A score after you act. You only see the snack you showed.

Unsupervised

No score. Structure only.

Move a little toward what just happened

new estimate = old estimate, plus a step toward the reward you just saw.

Worked numbers: \(Q = 0.50\), \(R = 1\), \(\alpha = 0.10\). Then \(Q\) becomes \(0.50 + 0.10 \times 0.50 = 0.55\).

If \(\alpha = 1/n\) after \(n\) pulls of that arm, this is the sample mean in disguise. If \(\alpha\) stays constant, old rewards fade. Use a constant \(\alpha\) when the world is non-stationary — a tea sale that used to work in winter and does not in July.

This “move toward the target” line comes back as TD, as the critic, and as every PPO/GRPO step. Remember it here, while it is one number.

ε-greedy, UCB, Thompson

ε-greedy

With probability \(1-\varepsilon\) take the current best arm. Else pick uniformly. On 4 arms with \(\varepsilon = 0.10\), the greedy snack is shown with probability 0.925. Each of the others gets 0.025.

UCB

Play \(\arg\max_a \big(Q(a) + c\sqrt{\ln t / N(a)}\big)\). The bonus is large when an arm is rarely pulled. At \(t = 20\), \(N = 4\), \(Q = 0.35\), \(c = 2\), the bonus is 1.73 and the score is 2.08.

Thompson

Keep a posterior per arm (Beta for buy/pass). Sample one number from each. Show the max. Exploration comes from posterior uncertainty, not from a coin flip.

Interactive · The kiosk

After a few pulls, does greedy lock onto an early fluke?

Greedy (\(\varepsilon = 0\)) often freezes on whichever snack sold first. A little \(\varepsilon\) keeps tea in play long enough to see its 0.25 rate. UCB does the same with a formula instead of a coin.

A completion is a contextual bandit

Give the model a prompt \(x\). It writes a reply \(y\). A checker returns a number. That is one pull of a contextual arm: the “arm” is the reply, the “context” is the prompt. RLHF and GRPO both start here. They treat a whole completion as one action when the reward is only known at the end.

It is not enough for multi-step thinking. The tokens inside \(y\) are a sequence of actions, and the useful reward often arrives only at the last one. That needs a state (the prefix so far) and a return. Next chapter.

Mistakes learners make

Calling every LLM problem a bandit. One prompt → one score is a contextual bandit. A chain of tokens with a late reward is an MDP.

Using \(\alpha = 1/n\) in a drifting world. The sample mean never forgets a January fluke. Constant \(\alpha\) forgets on purpose.

UCB with a mismatched brace in the square root. The term is \(\sqrt{(\ln t)/N(a)}\), not a broken \(\sqrt{\ln t / N(a}\).

What to remember

  • Policy picks actions. Reward scores them. Value predicts future reward.
  • \(Q \leftarrow Q + \alpha(R-Q)\). With \(Q=0.50\), \(R=1\), \(\alpha=0.10\), the new \(Q\) is 0.55.
  • ε-greedy, UCB, and Thompson are three ways not to freeze on the first pretzel.
  • One prompt, one completion, one reward is a contextual bandit. Sequences need MDPs.

Check yourself

1. \(Q = 0.50\), \(R = 1\), \(\alpha = 0.10\). What is the new \(Q\)?

0.55.

2. Four arms, \(\varepsilon = 0.10\). What is the probability the greedy arm is pulled?

0.925. Each other arm gets 0.025.

3. What extra thing does a contextual bandit have that a kiosk does not?

A context \(x\) (the prompt) that the policy conditions on.

4. Why is UCB’s bonus infinite for an arm that has never been pulled?

So every arm is tried once before we trust the \(Q\) ranking.

The code

kiosk_bandit.py0.55 update, UCB 2.08, ε-greedy 0.925
"""The station kiosk — a 4-armed bandit of our own.

Each arriving passenger sees one snack. They buy (reward 1) or walk past
(reward 0). True buy-rates are unknown to the agent. The incremental
update and the three exploration rules live here so the page can quote
exact numbers.
"""
import math


# Pretzel, tea, map, candy. The agent does not know these.
TRUE_RATES = (0.40, 0.25, 0.15, 0.10)
NAMES = ("pretzel", "tea", "map", "candy")


def incremental_update(q, reward, alpha):
    """Move Q a fraction alpha of the way toward the new reward.

    This is the same 'move toward the target' rule that later becomes
    TD and every actor-critic update in the series.
    """
    return q + alpha * (reward - q)


def ucb_score(q, t, n, c=2.0):
    """Upper confidence bound. Unvisited arms (n = 0) are +inf."""
    if n == 0:
        return float("inf")
    return q + c * math.sqrt(math.log(t) / n)


def epsilon_greedy_probs(k, epsilon):
    """Probability of picking each arm under ε-greedy, ties broken evenly."""
    # The greedy arm gets 1 - ε plus a share of the random mass.
    # Used on the page as a worked 4-arm case, not as a simulator.
    return (1 - epsilon) + epsilon / k, epsilon / k


# Worked numbers printed on the page.
Q_BEFORE, REWARD, ALPHA = 0.50, 1.0, 0.10
Q_AFTER = incremental_update(Q_BEFORE, REWARD, ALPHA)   # 0.55

# UCB at t = 20, arm pulled 4 times, Q = 0.35, c = 2.
UCB_T, UCB_N, UCB_Q, UCB_C = 20, 4, 0.35, 2.0
UCB_BONUS = UCB_C * math.sqrt(math.log(UCB_T) / UCB_N)
UCB_VALUE = UCB_Q + UCB_BONUS

# ε = 0.10 on 4 arms.
EPS = 0.10
GREEDY_P, EXPLORE_P = epsilon_greedy_probs(4, EPS)


if __name__ == "__main__":
    assert abs(Q_AFTER - 0.55) < 1e-12
    assert abs(UCB_BONUS - 1.730818) < 1e-5
    assert abs(UCB_VALUE - 2.080818) < 1e-5
    assert abs(GREEDY_P - 0.925) < 1e-12
    assert abs(EXPLORE_P - 0.025) < 1e-12
    print("kiosk bandit ok")

Go to the source

Keep going