The parcel that pays twice

A warehouse shuttle reaches a fork. The express aisle offers a nearby parcel worth three points. The service lane costs one point because it requires a detour. A controller that scores the next movement chooses the express aisle.

Two turns later, the express aisle ends behind a one-way barrier. The shuttle misses an urgent collection and loses eight points. The service lane opens a return corridor to the urgent collection, worth ten. Nothing about the first reward changed. What changed was the set of futures made reachable by the first action.

This is the small causal fact from which reinforcement learning grows. An action can alter both the reward received now and the distribution of states in which later decisions will be made. Once that happens, an action cannot be evaluated as an isolated prediction. Its quality includes the consequences it makes possible, the consequences it makes impossible and the evidence available before choosing.

The reverse experiment makes the boundary clear. Suppose both aisles rejoin before the urgent collection, so the first action has no effect on later states. The express aisle now genuinely dominates because its extra three points carry no downstream cost. If changing the current action does not change future observations, options or consequences, the problem may be a bandit, a supervised decision or a rule, rather than reinforcement learning.

The core answer therefore arrives before any algorithm: reinforcement learning addresses a problem of sequential dependence under uncertain consequence. The Markov decision process gives that problem a clean form. Value summarises the future consequence attached to a state. Bellman recursion carries the summary backwards. Exploration determines which branches have been observed rather than imagined.

Part IThe future hidden inside an action

A classifier receives an input and predicts a label. Its prediction normally does not alter the input distribution within the same decision. A planner receives a model and searches possible action sequences. Reinforcement learning occupies a different corner: the agent acts, the world changes, evidence arrives, and the policy may change before the next action. The data-generating process includes the learner's own behaviour.

That feedback creates two debts. The first is consequence debt: an early action may not reveal its value until much later. The second is evidence debt: choosing one branch hides the outcomes of branches not taken. Value propagation pays consequence debt; exploration pays evidence debt. Most of the apparent machinery of reinforcement learning serves one of those two jobs.

The smallest useful world model

A Markov decision process, or MDP, is commonly written as the tuple (S, A, P, R, γ). S is the set of states. A is the set of actions. P describes how an action changes the probability of the next state. R describes the reward produced by a transition. γ, gamma, discounts rewards that arrive further in the future. Bellman's early formulation established the recursive structure of such multi-period decisions, while Sutton and Barto provide the standard modern learning treatment.[1][2]

The word state carries the largest hidden assumption. A state is not every fact about the universe. It is the smallest representation that makes the next transition and reward conditionally predictable once the action is known. If two histories produce the same state representation, the model assumes their relevant futures are equivalent. That assumption can be engineered well, approximated badly or violated completely.

Value flows backwards through a Markov decision process A branching Markov decision process shows forward transitions and rewards, with dotted value waves flowing from terminal outcomes back towards the starting state. forward experience backward value propagation s₀ s₁ s₂ s₃ s₄ s₅ +8 +3 −5 a, p=.7 b, p=.3 r + γV(s′) backup backup
Figure 2. Value flow through an MDP. Illustrative topology and rewards. Experience moves forward through sampled transitions; estimated consequence is backed up towards earlier choices.

Reward is an event; return is a trajectory

The immediate reward after action At is usually written Rt+1. The return Gt combines that reward with later rewards along the same trajectory:

Gt = Rt+1 + γRt+2 + γ²Rt+3 + … (1)

Here γ lies between zero and one in the usual discounted setting. At zero, only the next reward matters. As it approaches one, distant rewards retain more influence. Gamma can also keep an infinite sum finite and express uncertainty about continuation. It should not be used to make distant harms disappear by convention. In the warehouse fork, a high enough gamma lets the urgent collection outweigh the nearby parcel.

A policy, written π(a|s), specifies the probability of choosing action a in state s. The state-value function Vπ(s) is the expected return after starting in state s and then following policy π. The action-value function Qπ(s,a) additionally fixes the first action. Value is therefore a forecast under a policy and a transition process, not a permanent property of the state. Change the policy, reward or dynamics and the value changes.

This distinction prevents a common category error. A predicted outcome such as “probability of late delivery” is descriptive. A value such as “expected cumulative service utility if we dispatch van B now and follow policy π afterwards” is decision-relative. The second claim inherits every assumption in the policy, horizon, reward and state model.

A policy is a contingent commitment

A plan names a sequence before events unfold. A policy names what to do for each state that may be encountered. In the warehouse, “take the service lane, collect the urgent parcel, then return” is a plan. A policy also says what to do if the lane is blocked, the urgent parcel disappears or the battery warning arrives early. It may be deterministic, selecting one action, or stochastic, assigning probabilities across actions.

This matters because value is always conditional on what happens after the first choice. The service lane may be attractive if the later policy reliably collects the urgent parcel, but unattractive if the controller frequently abandons that branch. The causal unit in reinforcement learning is the continuing interaction of policy and environment, not an isolated action-reward pair. Optimising a single action while leaving the continuation policy implicit can make two teams attach different meanings to the same Q-value.

Time sometimes belongs inside the state. The same loading bay with two minutes left in a shift does not offer the same future as the bay with two hours left. In a finite-horizon task, a physical observation without the remaining horizon can merge states with different optimal actions. Likewise, an episode that ends because the task truly terminated differs from one cut off by an evaluation time limit: the first has no continuation value, while the second may still have one. Gymnasium's current interface exposes termination and truncation separately for this reason.[11]

Part IIHow value moves backwards

Suppose the shuttle reaches the urgent collection only after ten moves. Waiting until the whole trip finishes gives an honest target, but learning is slow and noisy. The alternative is to use the current estimate of the next state's value. This is the decisive fold in the argument: a long future can be represented as one reward plus a shorter future.

For a fixed policy, the Bellman expectation equation is:

Vπ(s) = Eπ[ Rt+1 + γVπ(St+1) | St = s ] (2)

The expectation averages over the policy's action probabilities and the world's transition probabilities. The first term is observed reward. The second is the discounted value of the next state. If the next state becomes more promising, the current state becomes more valuable in proportion to gamma. If the next state is terminal, its continuation value is zero.

This is recursion without circular hand-waving. For finite discounted MDPs, repeatedly applying the Bellman operator contracts differences between bounded value estimates, yielding a unique fixed point for a fixed policy. The important intuition is simpler: every state borrows a priced claim on the futures reachable from its next step. Learning revises those claims as experience changes the evidence.

The Bellman fold turns a long future into a local target A long reward timeline folds at the next state, replacing the remaining tail with the next state's current value estimate. full trajectory s s′ r₁ r₂ r₃ r₄ fold the tail observed now r + estimated continuation γV(s′) local target The estimate is useful because it can be revised after every transition.
Figure 3. The Bellman fold. Conceptual, not measured. A trajectory tail is replaced by the current estimate of the next state's value, producing a local learning target.

Bellman optimality is a local consistency test

The expectation equation evaluates one fixed policy. Control asks a stronger question: which first action, followed by the best available continuation, has the greatest expected return? The optimal state value satisfies:

V*(s) = maxa E[ Rt+1 + γV*(St+1) | St = s, At = a ] (3)

Every symbol keeps the earlier meaning. The new maximum compares actions at the current state. Raising gamma gives the continuation estimate more leverage; changing the transition distribution changes which futures each action can reach; changing the reward changes what those futures are worth. A value estimate is Bellman-consistent when its current number agrees with the one-step reward plus the value it assigns downstream.

If the transition and reward model are known, this recursion can be solved by dynamic programming or used inside planning. No trial-and-error learner is required. If the model is unknown but transitions can be sampled, temporal-difference methods replace the expectation with experience. Bellman recursion explains sequential credit assignment; reinforcement learning is one family of ways to estimate or improve the resulting values and policies. This separates mechanism from implementation.

The distinction also exposes a failure mode. Bootstrapping learns from an estimate that was itself learned from earlier estimates. That makes updates efficient, but errors can travel backwards with value. A falsely high next-state value raises predecessor values; a policy then visits those predecessors more often; the resulting data can reinforce the original mistake. Tables in small, repeatedly explored MDPs permit clean convergence arguments. Function approximation, correlated samples and moving target policies require additional stabilisation and empirical controls.

From state value to action value

Control requires comparing actions, so Q-learning estimates the optimal action value directly. After observing transition (s, a, r, s′), tabular Q-learning applies:

Qt+1(s,a) = Qt(s,a) + α[ r + γ maxa′Qt(s′,a′) − Qt(s,a) ] (4)

α is the learning rate. The expression in square brackets is the temporal-difference error. It compares the old estimate with a new target made from the observed reward and the best currently estimated continuation. A positive error raises the action value; a negative error lowers it. The max makes Q-learning off-policy: it can explore with one behaviour while learning values for a greedy target policy.

Watkins and Dayan proved almost-sure convergence for the tabular setting under important conditions, including repeated sampling of every state-action pair and appropriate representation assumptions.[3] The familiar one-line update is therefore attached to a demanding evidence contract. Finite data, constant learning rates, function approximation, changing dynamics or incomplete coverage remove the simple guarantee.

Published evidence

Q-learning's theorem applies to controlled Markovian domains with repeated sampling and discrete action values. It does not certify an arbitrary neural network trained from a fixed operational log, and it does not establish that the chosen reward represents the real objective.

Minimal worked example: a delayed grid

Consider a six-by-six grid. The agent starts at the lower-left corner, the goal sits at the upper-right, walls force a ten-step route, and each ordinary move costs 0.02. Reaching the goal pays 1.0. A trap ends the episode with minus 1.0. Most states provide no clue about the correct direction from their immediate reward because every non-terminal move looks equally costly.

A myopic learner sets gamma to zero. It can learn to avoid the trap and recognise the final move into the goal, but that information does not travel to states nine steps away. Q-learning with gamma 0.97 repeatedly backs the goal value through predecessor states. In the supplied experiment, both learners receive the same exploration schedule, state representation and update rule. Only the continuation term changes.

Delayed value propagation solves the synthetic gridworld A six by six grid shows the learned ten-step path around walls, beside a measured comparison in which gamma point nine seven achieves one hundred percent success and gamma zero achieves thirty-eight point three percent. learned route trap goal start greedy evaluation success 100% 50% 0% 100% 38.3% γ=.97 γ=0 30 training seeds · 15,000 evaluation episodes per method Same environment and exploration schedule; only gamma changes.
Figure 4. Delayed value propagation in the supplied gridworld. Measured synthetic result over 30 training seeds and 500 greedy evaluation episodes per seed. Gamma 0.97: 100.0% success, mean 10.0 steps, mean return 0.82. Gamma 0: 38.3% success, mean 84.8 steps, mean return minus 1.30. These figures describe this script and schedule only.

The result does not prove Q-learning is generally superior. It isolates the mechanism. The environment contains a delayed terminal reward and a state representation that makes predecessor relationships learnable. Removing the Bellman continuation term prevents information from travelling beyond the final transition. In a stochastic or larger environment, the same backup can also propagate noise, bias and overestimation.

Deep Q-Networks replaced the table with a neural approximator and demonstrated learning from high-dimensional Atari observations.[5] More recent world-model systems learn dynamics and improve behaviour in imagined trajectories across diverse control tasks.[10] Those systems change representation, sampling and planning. They do not remove the original burden: estimates of future consequence still need data, a horizon, a policy and an objective.

Part IIILearning what has not been tried

The best-looking action is also the action that produces the next batch of evidence. If the policy always exploits its current estimate, early luck can become permanent belief. Exploration deliberately pays a near-term cost to reduce uncertainty about alternatives. The multi-armed bandit makes that trade visible, and finite-time analyses show that even the simplest setting carries unavoidable regret while information is gathered.[4]

Sequential environments deepen the problem. Trying an action can move the agent into a region from which other actions become possible, impossible or dangerous. A random action at the start of a maze is not equivalent to a random action beside a cliff. Exploration must be evaluated as a trajectory policy, not as a percentage of random moves.

Exploration policy should change with uncertainty and experiment cost A two-axis decision field maps uncertainty and cost of experimentation to exploit, online exploration, simulator or offline learning, and human-led control. exploit or use rules explore online simulate or learn offline human-led / constrained cheap reversible trials irreversible effects cost and irreversibility of experimentation → uncertainty about alternatives →
Figure 5. Exploration is an authority decision as well as a learning decision. Illustrative decision field. Boundaries are qualitative; local experiment cost, uncertainty and reversibility must be measured.

Epsilon-greedy exploration, used in the gridworld, chooses a random action with probability epsilon and otherwise chooses a currently best action. It is easy to understand and often wasteful. Optimistic methods act as though uncertain actions may be better than observed. Posterior-sampling methods sample a plausible model and act consistently within it. Entropy bonuses preserve action diversity. These are different ways to price ignorance; none makes unsafe experimentation acceptable.

Exploration creates the evidence it later cites

Suppose a routing policy sends nearly every easy parcel through corridor A because A looked slightly better during its first week. The resulting log will contain abundant evidence about A and little about B. A supervised predictor trained on that log may estimate outcomes accurately for the behaviour it repeatedly observed. It cannot thereby establish what would have happened had comparable parcels taken B. The missing branch is a counterfactual, not a null value.

Exploration intervenes on this selection process. In a one-step bandit, an upper-confidence method can prefer an action because its plausible upside remains high, then reduce that bonus as observations accumulate.[4] In an MDP, information has location and timing. Reaching a poorly understood state may require several earlier actions, and leaving it may be costly. The policy must therefore value both task return and the future information made reachable by a trajectory.

There are four common ways to obtain that evidence. Online exploration samples the live environment and offers the strongest behavioural relevance at the highest consequence cost. A simulator permits wider intervention but inherits a reality gap. Historical logs are operationally cheap but cover only actions chosen by earlier policies. Expert demonstrations cover purposeful behaviour yet often omit recovery, rare failures and inferior actions. Coverage is a property of state-action consequences under a data-generating policy, not a count of rows in a dataset.

For consequential systems, the exploration set should be mechanically narrower than the action set. A cooling policy might vary a setpoint within approved rate and temperature limits, while emergency shutdown, maintenance locks and equipment sequencing remain unavailable to the learner. Uncertainty can decide which authorised experiment to run; it cannot grant authority to run an experiment. Where no acceptably bounded intervention, simulator or informative log exists, abstaining from RL is an evidence-respecting result.

Thought experiment: the identical dashboard

Two delivery robots show the same dashboard: location 14, battery 40%, one parcel remaining. Robot A reached 40% after a slow discharge in cool air. Robot B reached 40% after rapid discharge while its battery overheated. The available actions and visible reward are identical. Sending A through the long tunnel is sensible. Sending B may trigger shutdown.

Now vary only the hidden thermal history. If the observation remains “40%”, a value learner must average two incompatible futures into one Q-value. More data does not remove the aliasing because the representation identifies states that require different actions. Add temperature and recent discharge rate, or use a belief state over hidden conditions, and the prediction problem changes.

One observation can hide two decision-relevant states Two hidden battery histories converge on an identical visible dashboard, but their safe actions diverge, illustrating state aliasing and partial observability. cool slow drain hot rapid drain visible dashboard battery 40% same observation o take tunnel stop and cool Same observation, different futures: more data cannot repair the missing state.
Figure 6. State aliasing defeats the Markov shortcut. Illustrative thought experiment. The visible observation is held constant while hidden thermal history changes the appropriate action.

This is the explicit representational boundary. The Markov property is not a metaphysical claim that history never matters. It is a modelling claim that the chosen state already contains the history needed for the next prediction. When that is false, a partially observable MDP, recurrent state estimator or explicit history window may help. If the missing variable cannot be inferred or observed, the optimal policy may be unidentifiable.

Three ways a high value becomes fiction

First, the policy may visit too narrow a slice of the state-action space. Values for unseen actions then depend on generalisation rather than direct evidence. Offline RL makes this acute because the new policy may select actions absent from the behaviour log. Conservative Q-learning was proposed to lower estimated values for such unsupported actions rather than trusting extrapolation.[7]

Second, the reward may be a poor proxy. A contact-centre controller rewarded only for short calls may transfer work, suppress useful questions or create repeat contacts. Bellman recursion will faithfully propagate the wrong objective. Optimisation cannot recover values that the reward and constraints never represent. Multi-objective outcomes, hard constraints and human decision rights must remain visible rather than being hidden inside one convenient scalar.

Third, evaluation may overstate confidence. Deep RL results can vary materially across seeds, tasks and reporting choices. Agarwal et al. showed that few-run point estimates can support different conclusions from interval-aware analysis.[8] A mean return without uncertainty, tail failures and task-level profiles is weak evidence for a release decision.

Historical logs do not automatically solve the safety problem. Off-policy evaluation estimates a target policy using data from another policy, but importance weights can have high variance and models can introduce bias. Doubly robust estimators combine both sources and still face inherent hardness when coverage is poor.[6] If a consequential action was never taken in comparable states, the log contains no hidden experiment waiting to be extracted.

Part IVWhen reinforcement learning earns its complexity

The strongest negative control is a world that resets after every action. One state offers two buttons. Button A pays 0.2, button B pays 0.7, and either choice terminates the episode. Gamma can be zero or 0.97; the Q-learning target is still the observed reward because the terminal continuation value is zero. A sample-average bandit learns the same preference with less machinery.

In a one-step reset world the Bellman continuation term vanishes One state branches to two terminal rewards. Both branches end immediately, so gamma times next value equals zero and reinforcement learning reduces to a bandit estimate. one state A 0.2 B 0.7 terminal reset V(s′)=0 target = r + γ × 0 = r Negative control: sequential machinery has no work to do.
Figure 7. The reset-world negative control. Synthetic construction. The supplied code produces identical Q-values for gamma 0 and gamma 0.97 because every action terminates.

This control matters because many products labelled “RL” are repeated one-step choices. If today's recommendation does not alter tomorrow's user state in the model, a contextual bandit may be sufficient. If transition dynamics are known, stable and small, dynamic programming or model-predictive control may solve the sequential problem without learning values from trial and error. If expert demonstrations already cover the operating envelope, imitation or supervised policy learning may be the stronger baseline.

Production-shaped worked scenario: thermal control

Consider a synthetic cooling controller operating every fifteen minutes. Its intent is to reduce energy while keeping room temperature inside an approved band. The world state includes temperatures, humidity, equipment availability, current setpoints and recent thermal trends. Context adds weather forecasts, electricity tariffs and maintenance windows. The policy proposes a small setpoint change; it does not directly command arbitrary equipment states.

The action has delayed consequence because thermal inertia carries the effect across several intervals. Immediate energy savings can cause a later temperature breach. A purely myopic optimiser may repeatedly defer cooling until recovery becomes expensive. This is a legitimate sequential structure. It does not yet justify online RL.

The identity of the controller service, the human owner and the environment must be explicit. A deterministic authority layer checks operating limits, rate-of-change limits, maintenance locks and emergency overrides. The action is the accepted setpoint, not the model proposal. Evidence includes the state snapshot, policy version, proposed action, constraint decision and sensor readback. The outcome is measured energy and temperature over the agreed horizon. Release begins in replay and shadow mode, then a bounded canary, with the existing controller as recovery.

A reinforcement policy belongs inside a bounded control and evidence loop A temporal loop shows world state and context entering a policy proposal, passing through a deterministic authority boundary, changing the plant, and returning verified sensor evidence, with a fallback controller below. worldstate policyproposal authorityand limits plantresponse verifiedreadback reward andevidence fallback controller takes over on breach Model proposes; deterministic control defines authority. Sensor readback establishes outcome.
Figure 8. A bounded RL control loop. Worked scenario, not a deployment. The topology separates intent, world state, context, reasoning, authority, action, evidence, outcome and recovery.

The reward might combine energy and comfort for learning, but hard temperature and equipment constraints should remain independent controls. The initial baseline is model-predictive control or the existing rule controller, not a weak random policy. The RL candidate must improve consequence-weighted outcomes under the same limits, including rare weather, sensor faults and changed occupancy. A good average reward cannot compensate for a new unsafe tail.

The real-world RL literature catalogues exactly these frictions: limited samples, offline data, partial observability, delayed effects, constraints, non-stationarity and multi-objective rewards.[9] They are not implementation details to handle after algorithm selection. They decide whether the MDP is a useful abstraction and whether learning can be authorised at all.

A release test must separate learning from control

The first evaluation freezes the candidate policy. Otherwise continued learning changes the object being measured while evidence is collected. Replay or simulation should compare that frozen policy with the incumbent controller on matched initial conditions, disturbances and horizons. Multiple seeds matter because training itself is stochastic. Report the distribution of returns, constraint breaches, recovery time and action frequency, not only the best run or mean reward.

Episode boundaries require the same discipline as state design. A genuine terminal outcome, such as task completion or irreversible failure, has zero continuation. A truncated record, such as a logging window ending at midnight, does not. Treating every truncation as terminal systematically undervalues actions whose effects cross the boundary. The evaluation manifest should record termination reason, remaining obligations and how outcome windows align with the reward horizon.

Shadow operation then tests the live observation and decision pipeline without applying the proposal. It can expose missing state, stale sensors, infeasible actions and disagreement with the incumbent, but it cannot reveal the effect of actions that were never executed. A bounded canary is the first causal test in the live plant. It needs deterministic admission limits, an independent fallback, predeclared stop conditions and readback that proves which action actually took effect.

Finally, distinguish model proposal, accepted action and verified outcome. A policy may propose a one-degree change, an authority kernel may clip it to half a degree, the actuator may reject it, or the sensor may fail after acceptance. Learning from the proposal as though it caused the outcome corrupts the transition record. The experience tuple must contain the action that changed the world and evidence of its effect, not merely the action the policy intended. This is where reinforcement learning meets operational control rather than replacing it.

Explicit failure boundary

Bellman learning ceases to be decision-worthy when there is no stable, action-conditioned state from which future outcome can be estimated with adequate coverage. It may still fit a return curve, but the value no longer supports a trustworthy counterfactual choice. Hidden state, policy-induced distribution shift, reward misspecification and prohibited exploration are boundary failures, not tuning problems.

The sequential choice fit record

The decision instrument below separates two questions. Gates one and two ask whether the problem is genuinely sequential. Gates three to six ask whether reinforcement learning is a feasible and preferable way to solve it. A “no” is an architecture result, not a failed ambition.

Six gates narrow a broad automation idea into an RL candidate A funnel contains six gates: action changes future state, immediate feedback is insufficient, state is sufficient, reward and constraints are valid, exploration or coverage is acceptable, and reinforcement learning beats simpler baselines. 1. Action changes later state or options 2. Immediate feedback cannot rank actions 3. State preserves decision-relevant history 4. Reward and hard constraints match intent 5. Coverage can be obtained acceptably 6. RL beats planning, bandit, rules and imitation bounded RL candidate bandit redesign redefine defer
Figure 9. The sequential choice fit record. Design inference. The first two gates establish the causal need; later gates establish identifiability, authority and comparative value.
1. Counterfactual state effectWould replacing the current action change later observations, available actions or transition probabilities?
2. Delayed evaluabilityCan immediate feedback rank the actions, or does the decision require a trajectory-level outcome?
3. State sufficiencyDoes the state preserve the history needed to predict reward and transition under each action?
4. Objective integrityAre reward, horizon, risk, constraints and human decision rights faithful to the actual intent?
5. Coverage and experimentationCan alternatives be explored, simulated or evaluated from logs without unacceptable harm or extrapolation?
6. Baseline dominanceDoes the RL policy beat rules, planning, control, bandits and imitation on outcomes, tails, cost and recovery?

Record each answer with evidence, owner and invalidation trigger. “Action changes future state” might be supported by a causal process model or intervention data. “State sufficient” needs predictive tests across histories that map to the same state. “Reward valid” needs outcome owners and adversarial scenarios. “Coverage acceptable” needs visitation counts, uncertainty and prohibited regions. “RL beats baselines” needs repeated runs and confidence intervals. The artefact is a release argument, not a scorecard that turns six uncertain judgements into one green number.

Executable artefact: delayed consequence laboratory

The dependency-free Python program below operates only on synthetic data. Its positive case compares Q-learning with gamma 0.97 against the same learner with gamma zero in the delayed grid. Its negative case makes every action terminal, so the continuation term vanishes. The expected qualitative output is: value propagation solves the grid, while gamma makes no difference in the reset world.

Assumptions and boundary

The grid is finite, deterministic and fully observed. Training uses a fixed episode budget, a constant learning rate and a decaying epsilon schedule. The result demonstrates credit propagation; it is not a convergence proof, benchmark claim or recommendation for continuous control.

Run the complete standard-library experiment
"""Small, dependency-free experiments for delayed consequence.

Positive case: a gridworld in which reward must move backwards through several
states. Negative control: a one-step choice in which every action terminates,
so the Bellman continuation term is always zero.

The script is educational, not a convergence proof or deployment recipe.
"""

from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass
import random
from statistics import mean
from typing import DefaultDict, Iterable, Sequence

State = tuple[int, int]
QTable = DefaultDict[State, list[float]]
ACTIONS: tuple[int, ...] = (0, 1, 2, 3)
DELTAS: tuple[State, ...] = ((-1, 0), (0, 1), (1, 0), (0, -1))


@dataclass
class GridWorld:
    rows: int = 6
    cols: int = 6
    start: State = (5, 0)
    goal: State = (0, 5)
    walls: tuple[State, ...] = (
        (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (1, 4), (2, 4)
    )
    trap: State = (2, 3)
    step_cost: float = -0.02
    goal_reward: float = 1.0
    trap_reward: float = -1.0
    max_steps: int = 100

    def reset(self) -> State:
        self.state = self.start
        self.steps = 0
        return self.state

    def step(self, action: int) -> tuple[State, float, bool, bool]:
        if action not in ACTIONS:
            raise ValueError(f"invalid action: {action}")

        self.steps += 1
        dr, dc = DELTAS[action]
        candidate = (self.state[0] + dr, self.state[1] + dc)
        outside = not (0 <= candidate[0] < self.rows and 0 <= candidate[1] < self.cols)
        self.state = self.state if outside or candidate in self.walls else candidate

        if self.state == self.goal:
            return self.state, self.goal_reward, True, False
        if self.state == self.trap:
            return self.state, self.trap_reward, True, False
        if self.steps >= self.max_steps:
            return self.state, self.step_cost, False, True
        return self.state, self.step_cost, False, False


def greedy_action(values: Sequence[float], rng: random.Random) -> int:
    best = max(values)
    ties = [action for action, value in enumerate(values) if value == best]
    return rng.choice(ties)


def train_grid(seed: int, gamma: float, episodes: int = 3_000) -> QTable:
    """Tabular Q-learning with a linear epsilon schedule."""
    rng = random.Random(seed)
    env = GridWorld()
    q: QTable = defaultdict(lambda: [0.0] * len(ACTIONS))
    alpha = 0.2

    for episode in range(episodes):
        state = env.reset()
        epsilon = 0.05 + 0.95 * max(0.0, 1.0 - episode / (episodes * 0.8))

        for _ in range(env.max_steps):
            action = rng.randrange(len(ACTIONS)) if rng.random() < epsilon else greedy_action(q[state], rng)
            next_state, reward, terminated, truncated = env.step(action)
            # A true terminal state has no future. A time-limit truncation is an
            # observation boundary, so the value target still bootstraps.
            continuation = 0.0 if terminated else gamma * max(q[next_state])
            target = reward + continuation
            q[state][action] += alpha * (target - q[state][action])
            state = next_state
            if terminated or truncated:
                break

    return q


def evaluate_grid(q: QTable, seed: int, episodes: int = 500) -> dict[str, float]:
    rng = random.Random(seed)
    env = GridWorld()
    successes = timeouts = traps = 0
    lengths: list[int] = []
    returns: list[float] = []

    for _ in range(episodes):
        state = env.reset()
        total = 0.0
        for step in range(1, env.max_steps + 1):
            action = greedy_action(q[state], rng)
            state, reward, terminated, truncated = env.step(action)
            total += reward
            if terminated or truncated:
                successes += state == env.goal
                traps += state == env.trap
                timeouts += truncated
                lengths.append(step)
                returns.append(total)
                break

    return {
        "success": successes / episodes,
        "trap": traps / episodes,
        "timeout": timeouts / episodes,
        "mean_steps": mean(lengths),
        "mean_return": mean(returns),
    }


def aggregate_grid(gamma: float, seeds: Iterable[int] = range(30)) -> dict[str, float]:
    results = [
        evaluate_grid(train_grid(seed, gamma), seed=10_000 + seed)
        for seed in seeds
    ]
    return {name: mean(run[name] for run in results) for name in results[0]}


def one_step_negative_control(gamma: float, seed: int = 7) -> tuple[float, float]:
    """Every action terminates, so gamma cannot affect the update target."""
    rng = random.Random(seed)
    q = [0.0, 0.0]
    rewards = (0.2, 0.7)
    alpha = 0.2

    for episode in range(600):
        epsilon = max(0.02, 0.5 * (1.0 - episode / 500))
        action = rng.randrange(2) if rng.random() < epsilon else greedy_action(q, rng)
        terminated = True
        continuation = 0.0 if terminated else gamma * max(q)
        target = rewards[action] + continuation
        q[action] += alpha * (target - q[action])

    return q[0], q[1]


def main() -> None:
    sequential = aggregate_grid(gamma=0.97)
    myopic = aggregate_grid(gamma=0.0)
    terminal_long = one_step_negative_control(gamma=0.97)
    terminal_zero = one_step_negative_control(gamma=0.0)

    print("Positive case: delayed gridworld")
    print(
        "  gamma=0.97 | success={:.1%} | mean steps={:.1f} | mean return={:.2f}".format(
            sequential["success"], sequential["mean_steps"], sequential["mean_return"]
        )
    )
    print(
        "  gamma=0.00 | success={:.1%} | mean steps={:.1f} | mean return={:.2f}".format(
            myopic["success"], myopic["mean_steps"], myopic["mean_return"]
        )
    )

    print("\nNegative control: one-step reset world")
    print(f"  gamma=0.97 | q={terminal_long} | best action={max(range(2), key=terminal_long.__getitem__)}")
    print(f"  gamma=0.00 | q={terminal_zero} | best action={max(range(2), key=terminal_zero.__getitem__)}")
    maximum_q_difference = max(
        abs(a - b) for a, b in zip(terminal_long, terminal_zero)
    )
    print(f"  maximum Q difference={maximum_q_difference:.6f}")

    # Executable checks make the intended causal contrast explicit.
    assert sequential["success"] >= 0.95, "delayed learner did not solve the grid"
    assert sequential["success"] >= myopic["success"] + 0.40, (
        "removing continuation did not materially weaken the delayed task"
    )
    assert maximum_q_difference < 1e-12, (
        "gamma changed a one-step terminal problem, which should be impossible"
    )


if __name__ == "__main__":
    main()
Positive case: delayed gridworld gamma=0.97 | success=100.0% | mean steps=10.0 | mean return=0.82 gamma=0.00 | success=38.3% | mean steps=84.8 | mean return=-1.30 Negative control: one-step reset world gamma=0.97 | q=(0.1999999789, 0.7000000000) | best action=1 gamma=0.00 | q=(0.1999999789, 0.7000000000) | best action=1 maximum Q difference=0.000000

The positive case changes only gamma. The negative control changes the environment so that actions have no future state effect. Together they answer two different questions. The first shows how a Bellman backup can move terminal reward through a chain. The second shows that the same mechanism becomes algebraically unnecessary when the horizon is one step.

Compact glossary

State
A representation intended to retain the history needed to predict the next transition and reward after an action.
Policy
A rule or distribution that selects actions from states.
Reward
The immediate scalar feedback attached to a transition. It is part of the problem specification, not proof of real value.
Return
The discounted accumulation of rewards along a trajectory.
Value
Expected return from a state or state-action pair under specified policy and dynamics.
Bellman backup
An update that combines immediate reward with an estimate of next-state value.
Exploration
Action selection intended to reduce uncertainty about alternatives, with its own consequence and authority cost.
Off-policy evaluation
Estimating a target policy from data generated by a different behaviour policy.

The decision changes before the algorithm does

Reinforcement learning is often introduced as learning by reward. That description is too broad. A recommender, classifier or optimiser can also learn from a score. The distinctive burden appears when an action reshapes the future in which later actions will be judged.

The durable intuition is that value is delayed consequence made locally usable. Bellman recursion performs the transport. Exploration supplies evidence about branches the policy would otherwise ignore. State design decides whether histories with different futures have been separated. Reward and constraints decide which consequences count. Evaluation decides whether the apparent gain survives seeds, shift and unsupported actions.

The architecture decision should therefore start with the sequential choice fit record, not an algorithm catalogue. Reject RL when actions do not change future state, when immediate outcomes are sufficient, or when a simpler planner, controller, bandit or rule wins. Redesign the state when relevant history is hidden. Refuse online learning when exploration exceeds authority. Keep hard constraints, effect verification and recovery outside the learned policy.

When those gates pass, Q-learning's small equation becomes more than a classroom formula. It is a precise answer to a precise causal problem: how can a consequence observed later revise the choice that made it reachable? The right next experiment is then discriminating and modest. Hold the environment, state and exploration schedule fixed; remove the continuation term; compare trajectory outcomes with uncertainty. If performance does not change, sequential value may not be the mechanism the system needs.

Source ledger

Open the source register and extended notes
  1. Primary Richard Bellman, A Markovian decision process. Early recursive formulation for multi-period stochastic choice. The article uses it for historical mechanism, not for modern implementation claims.
  2. Authoritative Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, second edition. Standard source for MDPs, returns, values, temporal-difference learning and control.
  3. Primary Chris Watkins and Peter Dayan, Q-learning. Convergence theorem for tabular Q-learning under repeated state-action sampling and stated conditions.
  4. Primary Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem. Exploration-exploitation and regret in the one-step setting.
  5. Primary Volodymyr Mnih et al., Human-level control through deep reinforcement learning. Evidence that action values can be approximated from high-dimensional observations in the Atari evaluation setting.
  6. Primary Nan Jiang and Lihong Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning. Bias, variance and hardness boundaries when evaluating a policy from another policy's data.
  7. Primary Aviral Kumar et al., Conservative Q-Learning for Offline Reinforcement Learning. Conservative value estimation for actions weakly supported by fixed data.
  8. Primary Rishabh Agarwal et al., Deep Reinforcement Learning at the Edge of the Statistical Precipice. Interval-aware, robust evaluation across few-run deep RL experiments.
  9. Peer-reviewed synthesis Gabriel Dulac-Arnold et al., Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Operational boundary conditions including limited samples, delays, constraints and non-stationarity.
  10. Primary Danijar Hafner et al., Mastering diverse control tasks through world models. Recent evidence for a world-model RL algorithm evaluated across diverse control domains with a fixed configuration.
  11. Official Farama Foundation, Gymnasium basic usage and time-limit handling. Current environment interface and the distinction between termination and truncation.