How the algorithms actually work

Reinforcement learning papers assume you can place a method in a family and know why it has the shape it does. This section gives you that: the split between learning what states are worth and learning behaviour directly, the recursive definition that makes credit assignment possible at all, and why the standard algorithm's main feature is a limit on how far one update may move. It closes on why the field is unstable, which is also why a reported improvement on a single seed is not a result.

Two families#

• Value methods learn how good a state or action is, then act greedily with respect to that. Q-learning is the canonical example. They suit discrete action spaces.
• Policy methods learn the behaviour directly, adjusting the probability of actions according to the reward that followed. They handle continuous actions and are what language model post-training uses.
• Actor-critic combines both: a policy that acts and a value estimate that reduces the variance of its updates. Most modern methods are in this family.

Placing a method takes three questions, and a paper's abstract usually answers all three in its first two sentences.

question                          answer            what it tells you

what does the network output?     action values     value method: DQN, Rainbow, double DQN
                                  action probs      policy method: REINFORCE, TRPO, PPO, GRPO
                                  both              actor-critic: A2C, SAC, DDPG, TD3

can it learn from old data?       yes               off-policy: replay buffers, sample-efficient,
                                                    prone to divergence with a network
                                  no                on-policy: fresh rollouts each update,
                                                    stable, expensive in experience

what are the actions?             discrete          argmax is available, value methods work
                                  continuous        argmax over actions is not available,
                                                    so policy or actor-critic

The Bellman idea#

The value of a state is the immediate reward plus the discounted value of wherever you end up next. That recursive definition lets you propagate information backwards from rewards to the states that led to them, which is how credit assignment is done in practice.

value(state) = reward + discount x value(next state)

The discount factor decides how much the future counts. Near 1
means far-sighted and slow to learn. Near 0 means short-sighted.

Two properties make that definition useful rather than merely circular. Applying it as an assignment — compute the right-hand side from your current guesses and overwrite the left — shrinks the largest error in the value table by a factor of gamma every pass, so repeated sweeps converge to a unique answer from any starting guess. And the algorithms differ mainly in what they put on the right. Value iteration takes the exact expectation because it has the environment's transition probabilities; Q-learning replaces that expectation with a single sampled next state and takes a small step towards it; policy-gradient methods drop the recursion entirely and use a whole episode's return. Sampled, model-free versions of the same line are what you use when nobody will give you the transition probabilities, which is almost always.

Why PPO constrains the step#

In supervised learning a bad update makes the loss worse and the next batch corrects it. In RL a bad update changes the policy, which changes the data you collect next, which can make recovery impossible. The system can destroy itself in a way supervised learning cannot.

PPO clips how far the policy is allowed to move in one update. That is essentially the whole idea, and it is why it became the default: not because it is clever but because it is hard to blow up.

Why RL is hard#

• The data distribution depends on the policy, so it shifts as you learn. Nothing is stationary.
• Rewards are sparse and delayed, so credit assignment is genuinely ambiguous.
• Exploration is unsolved in general. Too little and you never find the good behaviour; too much and you never exploit it.
• Variance is high, so results need many seeds and reported RL improvements have a poor reproducibility record.

Those four are usually read as cautions. They are better read as numbers, and small experiments produce them honestly. Sample inefficiency first: on the 4-by-4 slippery gridworld in this topic's Q-learning section, value iteration reaches the optimal policy in 36 sweeps of 13 squares by 4 actions, which is 1,872 backups, because it is handed the transition probabilities. Q-learning on the same grid, with only sampled transitions, needs about 54,000 environment steps to land within one and a half per cent of the same policy. Twenty-nine times the work for a problem with thirteen states, and the gap widens with the state space rather than narrowing.

Balancing a pole described by four numbers cost about 110,000 environment steps across 400 episodes with REINFORCE, and roughly 42,000 to 58,000 before the pole stayed up reliably. Hold that next to a supervised problem of comparable difficulty, which is a few thousand labelled examples, and the rule of thumb writes itself: reinforcement learning buys you the ability to learn without labels, and it pays for it in orders of magnitude of experience. That is affordable in a simulator and rarely affordable against the real world.

Seed sensitivity is the one that damages careers. In that same cart-pole run, the identical code at three seeds ended at 293, 500 and 14 steps per episode. The third seed is not a slow seed, it is a collapsed one: it found a good region, took a large update, and never recovered. Any of those three numbers could have been reported as the result of the method. This is why RL papers are expected to show several seeds with a spread, why a single learning curve is not evidence, and why you should distrust your own first good run as much as anyone else's.

Reward hacking is not an exotic failure#

The optimiser has no idea what you meant. It has your reward function, and if there is a way to score well that you did not intend, enough optimisation will find it. This is easiest to believe once you have caused it deliberately, which takes about thirty lines. The environment is a 4-by-4 grid with a goal worth 1, a hole worth -1 and a small cost per step. To help the agent along, someone adds what looks like a harmless progress bonus: 0.3 for stepping onto a square on the way.

import random

GRID = ["S...",
        ".#.H",
        "..b.",
        "...G"]          # b is an ordinary square; the shaping bonus is attached to it
MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]
GAMMA, STEP_COST = 0.95, -0.04
BONUS_SQUARE = 2 * 4 + 2

def at(s):
    r, c = divmod(s, 4)
    return GRID[r][c]

def arrive(s):
    return {"G": 1.0, "H": -1.0}.get(at(s), STEP_COST)

def move(s, a):
    r, c = divmod(s, 4)
    dr, dc = MOVES[a]
    nr, nc = r + dr, c + dc
    if not (0 <= nr < 4 and 0 <= nc < 4) or GRID[nr][nc] == "#":
        return s
    return nr * 4 + nc

def train(seed, bonus, episodes=3000, alpha=0.1):
    rng = random.Random(seed)
    Q = [[0.0] * 4 for _ in range(16)]
    eps = 1.0
    for ep in range(episodes):
        s = 0
        for t in range(100):
            a = rng.randrange(4) if rng.random() < eps else max(range(4), key=lambda x: Q[s][x])
            ns = move(s, a)
            r = arrive(ns) + (bonus if ns == BONUS_SQUARE else 0.0)
            done = at(ns) in "GH"
            Q[s][a] += alpha * (r + (0.0 if done else GAMMA * max(Q[ns])) - Q[s][a])
            s = ns
            if done: break
        eps = max(0.05, eps * 0.999)
    return Q

def rollout(Q):
    s, path, bonus_visits = 0, [0], 0
    for t in range(60):
        s = move(s, max(range(4), key=lambda a: Q[s][a]))
        path.append(s)
        if s == BONUS_SQUARE: bonus_visits += 1
        if at(s) in "GH": break
    return path, bonus_visits, at(s)

for bonus in (0.0, 0.3):
    for seed in range(3):
        Q = train(seed, bonus)
        path, bv, end = rollout(Q)
        print(f"bonus {bonus}: seed {seed} steps {len(path)-1:3d} "
              f"visits to the bonus square {bv:3d} ends on '{end}'")
# bonus 0.0: seed 0 steps   6 visits to the bonus square   0 ends on 'G'
# bonus 0.0: seed 1 steps   6 visits to the bonus square   0 ends on 'G'
# bonus 0.0: seed 2 steps   6 visits to the bonus square   0 ends on 'G'
# bonus 0.3: seed 0 steps  60 visits to the bonus square  29 ends on 'b'
# bonus 0.3: seed 1 steps  60 visits to the bonus square  29 ends on 'b'
# bonus 0.3: seed 2 steps  60 visits to the bonus square  29 ends on 'b'

Nothing went wrong. The agent maximised the reward it was given: a repeatable 0.3 beats a one-off 1.0 that ends the episode. Notice also what the metrics would have said. Average reward per episode went up, which is the number you would have plotted, and the completion rate went to zero, which is the number you cared about. Every real reward-hacking story has that shape — the proxy improves and the thing you wanted gets worse — whether the agent is a boat driving in circles through a bonus pickup or a language model padding its answers because the reward model likes length.

The fix is not a cleverer bonus. Potential-based shaping, where the bonus is a difference of some function of the state, is the one form provably unable to change the optimal policy, and that is the shape to reach for if you must shape at all. Otherwise, score the outcome you actually want, and audit with a held-out measure the optimiser never sees.