Reinforcement Learning from Scratch

01An action changes what is observed next

A supervised classifier receives an input and a target. A reinforcement-learning agent chooses an action, then observes a consequence. Its choice changes which experience it collects. Learning must account for rewards that arrive after several decisions, and an agent can improve its measured reward while doing something the designer did not intend.

A Markov decision process, or MDP, specifies states, actions, and a transition distribution over next states and rewards. A policy chooses actions. The state's defining assumption is predictive sufficiency: given the state and action, earlier history adds no information about the next transition. An image that hides velocity or an opponent's intentions may be only a partial observation.^[1]

G_t is return: the discounted sum of future rewards. γ, the discount factor, lies between zero and one in the examples here. An episodic return ends at the terminal transition.

A state value V(s) is an expected return starting at s under a specified policy. An action value Q(s,a) also fixes the first action. A high value is not a probability of success; it has units set by the reward definition and can be negative. Changing reward scale changes values even when the best policy remains the same.^[1]

All grid demos use a 4×4 deterministic environment. States are numbered 0–15, left to right across each row. State 5 is a wall. Actions attempt to move up, right, down, or left; hitting the boundary or wall leaves the position unchanged. Entering state 15 gives +1 and ends the episode; other transitions give −0.04. This explicit model makes the updates checkable. It does not model game-engine movement, hidden information, or stochastic physics.

02Plan with the transition model

A Bellman backup relates an immediate consequence to future value. When the full transition model is known, a planner can evaluate every action and possible outcome. In the deterministic grid, one action has one next state, so the expectation reduces to a single term.^[1]

The maximum selects the best action according to the current values. For a transition into the goal, the future term is zero. Terminal-state value is fixed at zero.

Value iteration applies this update across states. The synchronous version below reads every next-state value from the previous sweep and writes a separate next array. Updating in place gives an asynchronous variant whose intermediate values can differ. Neither the sweep count nor the intermediate arrows should be treated as an environment-time trajectory.^[1]

Initially all values are zero. The first sweep puts the positive goal reward in states that can enter it. Further sweeps propagate useful estimates to more distant states. For 0≤γ<1, the discounted Bellman optimality operator is a contraction in the maximum norm; repeated backups on a finite MDP converge to its fixed point. The statement depends on that model and operator. It is not a convergence guarantee for an arbitrary neural network trained from replay.^[1]

The demo reports a residual rather than claiming that a fixed number of sweeps is enough for every problem. A planner can compute a policy from the current values, but whether those values represent the real environment depends on the transition model. A precise solution to the wrong model can choose the wrong action.

03Learn action values from sampled transitions

An agent often cannot enumerate the real transition model. It can still observe a tuple (state, action, reward, next state). Q-learning moves one action-value estimate toward a one-step target formed from that experience.^[1]

The learning rate α controls the size of this update. The bootstrap term is zero on true termination. A nonterminal transition uses an estimate of future value.

The error is a temporal-difference error, or TD error. The target can change as the estimates change. This is different from fitting a fixed table of supervised labels. Here the agent updates the chosen state-action entry and leaves the other entries alone.

Q-learning is off-policy: its target uses a greedy next action even if exploration selected the observed action. That allows the behavior policy to collect experience while the target estimates a greedy policy. It does not mean that arbitrary missing experience can be ignored. If an important state-action pair is never observed, its value cannot be established from these updates.^[1]

Classical tabular convergence results require conditions such as sufficient visitation and suitable decreasing step sizes. The widget uses a constant learning rate of 0.4 to keep changes visible. A finite run with that rate demonstrates the update; it is not evidence that the conditions of a convergence theorem were satisfied.^[1]

04Exploration is a policy, not noise added to Q

An ε-greedy policy chooses exploration with probability ε. On exploration, select uniformly among all actions, including actions that are already greedy. The exploitation branch selects an action with the largest estimate.^[1]

With four actions and one uniquely best action, its probability is 1−ε+ε/4. Each other action has probability ε/4. With tied best actions, this widget splits the exploitation mass uniformly among them. A different tie rule changes the behavior policy even though the Q-learning target's maximum is unchanged.

A higher ε can reveal useful transitions. When some actions have lower estimates, increasing ε gives them more probability; when all actions tie, changing ε leaves this widget's distribution unchanged. Evaluating a policy under ε=0.3 asks a different question from evaluating its greedy behavior. Record the evaluation policy, seeds, episode limits, and reward definition. A single successful training episode says little about reliability.

Exploration also depends on the state representation and available actions. If a reward is reachable only through a long coordinated sequence, independent random actions can be inefficient. The ε-greedy calculation is an explicit baseline, not a universal solution to sparse-reward exploration.

05Add guidance without changing the optimal policy

A reward for "moving closer to the goal" looks helpful, but arbitrary bonuses can change the task. An agent may collect bonuses in a loop rather than complete the intended objective. Potential-based shaping gives a precise alternative.^[2]

Φ is a fixed scalar potential over states. The same discount γ must be used in the shaping term and return. In these episodic examples, terminal potential is zero.

Sum the shaping terms along a trajectory of T steps, with discounting. Interior terms cancel, leaving −Φ(start)+γᵀΦ(terminal). Setting terminal potential to zero makes the change in complete-episode return a constant determined by the start state. It therefore preserves the ordering of policies from that start. For a continuing problem with 0≤γ<1, a bounded potential makes the far-future boundary term vanish.^[2]

Path A visits states 0→1→2→3→7→11→15. Path B visits 0→4→8→9→8→9→10→14→15. The demo uses negative Manhattan distance times the selected scale as its potential. This fixed distance heuristic ignores the wall. Its invariance calculation holds because the potential is fixed and the terminal boundary is handled correctly. Changing the potential during training adds another issue that this fixed-potential proof does not cover.

Shaping may alter how quickly a learner discovers a useful policy without changing the optimal-policy set under the stated assumptions. It cannot fix an original reward definition that measures the wrong task, or turn insufficient observations into a Markov state.

06Termination and truncation have different targets

The goal ends the task, so there is no later reward from that episode. A data-collection time limit can instead stop observation while the underlying task would continue. Treating both events as "done" and zeroing every bootstrap term trains different value targets.^[3]

terminated means the underlying task reached a terminal state. External truncation alone does not zero the bootstrap term for the continuing task.

Gymnasium separates terminated and truncated for this reason.^[4] On external truncation, bootstrap from the final observation of the interrupted trajectory. In Gymnasium's same-step autoreset mode, the returned observation belongs to the new episode and the trajectory's final observation is stored separately. Using the reset state in the target mixes two episodes. Retrieve the actual final observation before updating, and check the autoreset mode used by the environment.^[5]

A fixed horizon that defines the task is different from an arbitrary training cutoff. If success before a deadline is the objective, time remaining can affect the best action and belongs in the state. Reaching that true task horizon is a terminal event. Pardo et al. distinguish these cases; "always bootstrap on a time limit" is too broad.^[3]

07Optimize a policy directly

An alternative learns action probabilities directly. For a differentiable policy, a score-function estimator multiplies the derivative of the log action probability by a return signal. A state-dependent but action-independent baseline can be subtracted without changing the expected gradient.^[6]

The baseline must not depend on the sampled action for this simple unbiasedness argument. The baseline is held constant with respect to the policy parameters when forming this estimator.

The cancellation is explicit: sum over actions of baseline×π(a|s)×∇logπ(a|s) equals baseline×∇sum π(a|s), which is zero. Variance can still change. A poor baseline can increase variance; a value estimate is a useful choice, not a guarantee that the variance is minimal for every parameterization.^[6]

The widget uses a two-action bandit with deterministic rewards 1 and 4. If the probability of action one is p, the derivative of log probability with respect to its logit is 1−p for action one and −p for action zero. Enumerating both outcomes gives the exact expectation and variance, without sampling error.

Full episodic policy gradients need a consistent treatment of discounting and which states are weighted in the objective. This one-state bandit has no temporal discount factors. It isolates the baseline calculation so a change in estimator variance cannot be mistaken for a different expected update.

08Make the terminal rule explicit in code

These complete programs implement one tabular Q-learning update. The caller supplies the final next-state action values and the true terminal flag. Assertions distinguish a terminal transition from external truncation and verify that the target is read before modifying the current row.

#include <array>
#include <algorithm>
#include <cassert>
#include <cmath>
using Actions = std::array<double,4>;
double update(Actions& current, int action, double reward,
              const Actions& next, double discount, double learningRate,
              bool terminated) {
    assert(action >= 0 && action < 4);
    assert(discount >= 0 && discount <= 1);
    assert(learningRate > 0 && learningRate <= 1);
    // next refers to the final observation, not an auto-reset observation.
    const double bootstrap = terminated ? 0.0 : *std::max_element(next.begin(),next.end());
    const double target = reward + discount*bootstrap;
    const double error = target-current[action];
    current[action] += learningRate*error; // Read the whole target before modifying Q.
    return error;
}
int main() {
    Actions current{0,0,0,0};
    const Actions next{2,5,1,0};
    const double error = update(current,1,1,next,0.9,0.4,false);
    assert(std::abs(error-5.5) < 1e-12);
    assert(std::abs(current[1]-2.2) < 1e-12);
    Actions terminal{0,0,0,0};
    update(terminal,1,1,next,0.9,0.4,true);
    assert(std::abs(terminal[1]-0.4) < 1e-12);
    // An external time limit has terminated=false and retains bootstrapping.
    Actions truncated{0,0,0,0};
    update(truncated,1,1,next,0.9,0.4,false);
    assert(truncated == current);
    // Aliased current/next is safe because the target is evaluated first.
    Actions self{1,2,3,4};
    update(self,0,0,self,0.9,1.0,false);
    assert(std::abs(self[0]-3.6) < 1e-12);
}

type Actions = [f64;4];
fn update(current: &mut Actions, action: usize, reward: f64,
          next: &Actions, discount: f64, learning_rate: f64,
          terminated: bool) -> f64 {
    assert!(action < 4);
    assert!((0.0..=1.0).contains(&discount));
    assert!(learning_rate > 0.0 && learning_rate <= 1.0);
    // next refers to the final observation, not an auto-reset observation.
    let bootstrap = if terminated { 0.0 }
        else { next.iter().copied().fold(f64::NEG_INFINITY,f64::max) };
    let target = reward + discount*bootstrap;
    let error = target-current[action];
    current[action] += learning_rate*error; // Read the whole target before modifying Q.
    error
}
fn main() {
    let mut current = [0.0;4];
    let next = [2.0,5.0,1.0,0.0];
    let error = update(&mut current,1,1.0,&next,0.9,0.4,false);
    assert!((error-5.5).abs() < 1e-12);
    assert!((current[1]-2.2).abs() < 1e-12);
    let mut terminal = [0.0;4];
    update(&mut terminal,1,1.0,&next,0.9,0.4,true);
    assert!((terminal[1]-0.4).abs() < 1e-12);
    // An external time limit has terminated=false and retains bootstrapping.
    let mut truncated = [0.0;4];
    update(&mut truncated,1,1.0,&next,0.9,0.4,false);
    assert_eq!(truncated,current);
    let mut self_state = [1.0,2.0,3.0,4.0];
    let previous = self_state; // Rust separates the immutable target from the mutable row.
    update(&mut self_state,0,0.0,&previous,0.9,1.0,false);
    assert!((self_state[0]-3.6).abs() < 1e-12);
}

The kernel omits the environment loop, experience storage, schedules, and evaluation. A neural Q function replaces the table with a prediction model, introducing shared parameters and additional stability issues. Mnih et al.'s DQN uses a replay buffer and a separate, periodically copied target network. Replay randomizes which stored transitions form a training batch; the lagged target reduces the immediate feedback between the updated prediction and its bootstrap target.^[7]

Those components do not establish convergence of arbitrary deep Q-learning. They also introduce choices about replay distribution, stale data, terminal handling, and target-update schedules. Test the tabular update first, then compare the learned function to small environments with known values before attributing a failure to network capacity.

09Evaluation must match the intended behavior

A reward curve combines the learner, behavior policy, environment, and evaluation procedure. Record them separately. Compare against a simple fixed policy, use multiple independent seeds, and inspect actual actions. A high return can result from an exploitable reward rather than the intended behavior.

Count environment transitions separately from gradient updates. Replay can train repeatedly on the same experience, so "steps" is ambiguous. The widgets explicitly count sweeps or sampled transitions; they do not present either count as elapsed game time.

10What's next

Diffusion Models learns a different function: a prediction about a corrupted sample. Repeated reverse steps use that predictor to generate a sample. Training fits the predictor to targets formed by corrupting clean samples.

11Sources

The cited equations define the algorithms. Widget readouts report the displayed toy arrays and settings; they are not hardware benchmarks.

1. Richard S. Sutton and Andrew G. Barto, 2018, second edition. Reinforcement Learning: An Introduction. Chapters 2–6: returns, Markov decision processes, planning, and Q-learning; chapter 13: policy gradients.
2. Andrew Y. Ng, Daishi Harada, Stuart Russell, 1999. Policy invariance under reward transformations: Theory and application to reward shaping. Potential-based shaping and the policy-invariance conditions.
3. Fabio Pardo, Arash Tavakoli, Vitaly Levdik, Petar Kormushev, 2018. Time Limits in Reinforcement Learning. Task horizons, external truncation, and bootstrapping.
4. Farama Foundation, Gymnasium documentation. Handling Time Limits. The separate terminated and truncated flags and their targets.
5. Farama Foundation, 2025. Deep Dive: Autoreset Modes in Gymnasium v1.1 Vector Environments. Same-step reset observations and retrieving the actual final observation.
6. Richard S. Sutton, David McAllester, Satinder Singh, Yishay Mansour, 1999. Policy Gradient Methods for Reinforcement Learning with Function Approximation. Policy-gradient expectations and action-independent baselines.
7. Volodymyr Mnih et al., 2015. Human-level control through deep reinforcement learning. Replay sampling, lagged target networks, and learned Q functions.