What it actually does
Keep a table of "how good is taking action a in state s", then wander the environment updating each entry toward the reward you just got plus the best value you think is available from wherever you landed. The bootstrapping is the whole trick: you never wait to see how the episode ends, you update toward your own current estimate of the future. Do that enough times and the estimates converge on the truth — and acting greedily on them is the optimal policy.
- The environment is a Markov decision process — the current state is sufficient, history adds nothing
- State and action spaces are discrete and small enough to enumerate
- Every state-action pair is visited infinitely often, which exploration must actually deliver
- The dynamics are stationary; a shifting environment invalidates the fixed point being converged to
Fixed-point condition
This is not a loss to minimize over a dataset — it is a self-consistency condition. Q is correct exactly when it equals its own one-step lookahead. The Bellman operator is a gamma-contraction, so repeatedly applying it drives any starting table toward the unique fixed point. Naming this correctly matters: calling it a "loss function" would suggest a fixed target and i.i.d. samples, and it has neither.
- optimal action-value — expected discounted return from taking a in s, then acting optimally
- discount factor; how much a reward one step later is worth
- immediate reward observed on this transition
- the greedy max that makes this OFF-policy — it ignores what the agent actually did next
How it is minimized
Stochastic approximation — incremental updates toward a bootstrapped target
- learning rate — how far to move toward the new target
- temporal-difference error: how wrong the current estimate was
- the target, which itself contains Q — hence bootstrapping
The target depends on the parameters being updated, which is what separates this from every supervised method here. There is no gradient of a fixed objective; this is stochastic approximation, and the Robbins-Monro conditions on the learning rate are what guarantee convergence. Crucially the max is over the greedy action rather than the one actually taken, which makes it off-policy: the agent can explore randomly and still learn the optimal policy, and it can learn from data generated by any policy at all. That single property is what makes replay buffers and offline RL possible.
learning rate (alpha)
Step toward the TD target; must decay for tabular convergence (0.01 to 0.5, decaying)
discount (gamma)
Effective horizon, roughly 1/(1-gamma) steps (0.9 to 0.99)
epsilon
Exploration rate; annealed from near 1 toward near 0 (1.0 down to 0.01)
initial Q values
Optimistic initialization drives systematic early exploration for free (0, or above the max plausible return)
Tabular Q-learning converges to the optimal Q with probability 1, given every state-action pair is visited infinitely often and the learning rate satisfies the Robbins-Monro conditions — sum of alpha diverges, sum of alpha squared converges. Those conditions are strong and routinely violated in practice, since a constant learning rate is normal. The characteristic failure is not divergence but maximization bias: the max operator over noisy estimates systematically overestimates, because taking a max over noise selects for whichever entry got lucky. That bias is exactly what Double Q-learning was invented to remove, and it compounds badly once function approximation replaces the table.
O(|A|) per update for the max, O(|S| x |A|) memory for the table. The table is the binding constraint: it is exact and it does not generalize, so it becomes impossible somewhere around a few million discrete states — which is precisely the wall DQN was built to break.
How, where, and why it is used
Time-Series Forecasting
Not applicableQ-learning optimizes a policy, and forecasting has no actions to optimize over. The objective is expected return under a behaviour, not the accuracy of a prediction, and there is no sense in which a forecast "acts" on the series to change what comes next. It becomes relevant only one step downstream, once a forecast feeds a decision — which is the control-and-operations case, not this one.
Anomaly Detection
Not applicableDetection is a scoring problem with no action and no state transition, so the entire RL apparatus has nothing to optimize. A high TD error indicates a state the agent has not learned yet, which is a training diagnostic rather than a finding about the data — treating it as an anomaly score would flag the agent's own ignorance.
Optimization
Primary fitFormulate the decision problem as an MDP — states, actions, transition dynamics, reward — then learn the value of each action by interaction. Acting greedily on the converged table is the optimal policy, and it optimizes cumulative discounted return directly rather than through any proxy loss.
- Inventory and reordering policies where today's order changes tomorrow's state
- Elevator, traffic-light and queue scheduling with discrete action sets
- Job-shop and resource allocation where the consequence of an assignment is delayed
This is the category built for sequential decisions with delayed consequences, and Q-learning is its clearest expression. The distinction from a supervised approach is sharp: a classifier can learn which action a human took, but only a value method can discover an action sequence better than the one in the data. The cost is that it needs an environment to interact with — a simulator, or a system safe to explore in — and that requirement is what rules it out far more often than any algorithmic limitation does.
- Discretize the state space carefully — too coarse loses the signal, too fine makes the table intractable
- Shape the reward to the true objective; the agent optimizes exactly what you wrote, not what you meant
- Include enough state that the Markov property roughly holds, or bootstrapping is chasing a moving target
Regret against the best fixed policy, plus offline policy evaluation before any live deployment. Constraint violations counted separately as hard failures rather than averaged into the return.
- Reward shaping that admits a degenerate policy — the agent will find it, reliably and fast
- A non-Markov state means bootstrapping toward a target that does not exist
- Maximization bias makes learned values systematically optimistic, so the expected return is overstated
Control & Operations
Primary fitThe canonical application. State is the physical or logistical configuration, actions are the available interventions, and reward encodes throughput minus cost. Learn in simulation, then transfer with a safety layer that can override the policy.
- Warehouse routing and robotic picking with discrete action sets
- HVAC and energy dispatch scheduling against a demand forecast
- Traffic signal control where each phase change alters the queue state
The MDP definition — state, actions, dynamics, long-horizon reward — is a literal description of an operations problem, which is why RL keeps arriving here first. The realistic pattern in production is model-based: forecast the system, then optimize the action sequence against the forecast, using Q-learning's machinery inside a planner rather than learning purely from live interaction.
- Discretize actions to a menu the operator would actually accept
- Bound the state space to a validated operating envelope
Simulation first with an explicit sim-to-real gap estimate, then shadow-mode recommendation before the policy is ever allowed to act.
- Online exploration on a live physical system is a safety incident, not a learning strategy
- Sim-to-real gap means a policy optimal in simulation can be actively harmful in deployment
Recommendation & Ranking
AdaptedTreat a session as an episode: state is the interaction history, actions are items to surface, reward is engagement. This captures the sequential structure that a pointwise ranker discards entirely.
- Session-based recommendation where the sequence of items matters more than any single one
- Long-horizon engagement optimization rather than next-click prediction
The right framing in principle, because ranking genuinely is a feedback loop where today's recommendations shape tomorrow's training data. In practice contextual bandits capture most of the value at a fraction of the complexity, and full Q-learning is rarely worth it outside very large platforms — the honest recommendation is to start with the bandit.
- State must summarize the session compactly, since the raw history is unbounded
- Reserve explicit exploration traffic, or the policy only ever learns about what it already shows
Off-policy evaluation on logged data first, then online A/B — offline gains routinely fail to transfer here.
- The action space is the entire catalogue, so a max over actions is intractable without candidate generation
- Logged data reflects the previous policy, so off-policy estimates carry large variance
What it costs to run
Cheap per update — one table lookup and a max. Expensive in *samples*: convergence needs every state-action pair visited many times, which is why a simulator is usually mandatory.
A single argmax over the action row. Microseconds, and trivially explainable: you can print the value of every action considered.
Continuous in a stationary simulator; on a real system, re-learn whenever the dynamics change — a re-layout, a new SKU mix, a hardware change all invalidate the learned values.
- Track the TD error distribution — a rising average means the environment has moved out from under the table
- Monitor state-visitation coverage; states the policy stopped visiting have stale, untrustworthy values
- Watch realized return against the value the table predicts, since maximization bias makes the prediction optimistic
- Epsilon must actually be annealed to near zero at serving, or the deployed policy keeps taking random actions in production
- An unseen state has no entry — the fallback behaviour is a design decision, not an implementation detail
- The reward function is the specification; any mismatch between it and the real objective is silently and enthusiastically exploited
Pros and cons, in context
Off-policy — learns the optimal policy from data generated by any behaviour
The single most consequential property. It means exploration and learning are decoupled, which is what makes replay buffers, offline RL, and learning from logged or human data possible at all. SARSA, its on-policy sibling, cannot do this.
Converges to the optimal policy with a real guarantee
Rare in RL, and it holds only in the tabular case under conditions that practice routinely violates. Still worth knowing precisely, because it is the reference point against which every approximate method is judged.
Fully inspectable
You can read the value of every action in every state, which makes debugging tractable and makes it a genuine teaching model. Deep variants lose this entirely.
No model of the environment required
Learns purely from sampled transitions, so it works where the dynamics are unknown or too complex to write down. It pays for that in sample efficiency, which model-based methods recover.
The table does not generalize and does not scale
Every state-action pair is learned independently, so nothing transfers between similar states and memory grows as |S| x |A|. This is the exact wall that motivated DQN.
Maximization bias makes values systematically optimistic
Taking a max over noisy estimates selects for whichever got lucky. The learned value overstates the achievable return, which matters whenever the number is used for planning rather than just ranking actions.
Very sample-inefficient
Needs many visits to every state-action pair, which effectively mandates a simulator. This is the practical reason RL fails to ship far more often than any algorithmic shortcoming.
Requires discretization
Continuous states must be binned and continuous actions cannot be handled at all, since the max is over an enumerable set. Continuous control needs an actor-critic formulation instead.
Intuitive, idiomatic, optimized
The same algorithm in three languages, each progressing through Kent Beck's three stages. Every optimization names the lever it pulls and the trade-off it accepts — cost profiles are illustrative, not measured benchmarks.
The math, transcribed literally. No dependencies.
"""Tabular Q-learning - the update rule, transcribed.
Note what is NOT here: no dataset, no epochs, no loss. The agent generates its
own data by acting, and the target contains Q itself.
"""
import random
def train(env, n_states, n_actions, episodes=5_000, alpha=0.1, gamma=0.99, epsilon=0.1):
# Q[s][a] = expected discounted return from taking a in s, then acting well.
Q = [[0.0] * n_actions for _ in range(n_states)]
for _ in range(episodes):
state = env.reset()
done = False
while not done:
# epsilon-greedy: explore sometimes, otherwise take the best known
# action. Without exploration the agent never discovers anything
# better than whatever it stumbled into first.
if random.random() < epsilon:
action = random.randrange(n_actions)
else:
action = max(range(n_actions), key=lambda a: Q[state][a])
next_state, reward, done = env.step(action)
# The max is over the GREEDY action, not the one we will actually
# take next. That is what makes this off-policy.
best_next = 0.0 if done else max(Q[next_state])
td_target = reward + gamma * best_next
td_error = td_target - Q[state][action]
Q[state][action] += alpha * td_error
state = next_state
return Q
def greedy_policy(Q):
"""Acting greedily on a converged Q IS the optimal policy."""
return [max(range(len(row)), key=lambda a: row[a]) for row in Q]O(|A|) per step for the max. Python lists; no vectorization anywhere.
How this language actually wants it written.
"""Tabular Q-learning - typed, annealed, with convergence diagnostics."""
from dataclasses import dataclass, field
from typing import Protocol
import numpy as np
from numpy.typing import NDArray
QTable = NDArray[np.float64]
class Environment(Protocol):
def reset(self) -> int: ...
def step(self, action: int) -> tuple[int, float, bool]: ...
@dataclass
class QLearningConfig:
n_states: int
n_actions: int
alpha: float = 0.1
gamma: float = 0.99
epsilon_start: float = 1.0
epsilon_end: float = 0.01
epsilon_decay_episodes: int = 1_000
# Optimistic init makes every unvisited action look attractive, so the
# agent explores systematically instead of relying on random epsilon hits.
optimistic_init: float = 0.0
def __post_init__(self) -> None:
if not 0.0 <= self.gamma < 1.0:
raise ValueError(f"gamma must be in [0, 1), got {self.gamma}")
if not 0.0 < self.alpha <= 1.0:
raise ValueError(f"alpha must be in (0, 1], got {self.alpha}")
if self.n_states < 1 or self.n_actions < 1:
raise ValueError("state and action spaces must be non-empty")
@dataclass
class TrainingResult:
q_table: QTable
episode_returns: list[float] = field(default_factory=list)
mean_abs_td_error: list[float] = field(default_factory=list)
visit_counts: QTable | None = None
@property
def has_converged(self) -> bool:
"""Falling TD error, not rising return, is the convergence signal -
return can plateau while the values are still badly wrong."""
if len(self.mean_abs_td_error) < 20:
return False
recent = float(np.mean(self.mean_abs_td_error[-10:]))
earlier = float(np.mean(self.mean_abs_td_error[-20:-10]))
return recent < earlier * 1.05 and recent < 0.01
@property
def coverage(self) -> float:
"""Fraction of state-action pairs ever visited. The convergence
guarantee assumes this reaches 1.0; it usually does not."""
if self.visit_counts is None:
return 0.0
return float((self.visit_counts > 0).mean())
def train(env: Environment, config: QLearningConfig, episodes: int = 5_000) -> TrainingResult:
q = np.full((config.n_states, config.n_actions), config.optimistic_init, dtype=np.float64)
visits = np.zeros_like(q)
rng = np.random.default_rng(0)
result = TrainingResult(q_table=q, visit_counts=visits)
for episode in range(episodes):
# Linear anneal. A constant epsilon means the deployed policy keeps
# taking random actions forever.
progress = min(1.0, episode / config.epsilon_decay_episodes)
epsilon = config.epsilon_start + progress * (config.epsilon_end - config.epsilon_start)
state = env.reset()
done = False
episode_return = 0.0
td_errors: list[float] = []
while not done:
if rng.random() < epsilon:
action = int(rng.integers(config.n_actions))
else:
action = int(np.argmax(q[state]))
next_state, reward, done = env.step(action)
visits[state, action] += 1
# Terminal states have no future - bootstrapping past a terminal
# is the single most common bug in a Q-learning implementation.
best_next = 0.0 if done else float(q[next_state].max())
td_error = reward + config.gamma * best_next - q[state, action]
q[state, action] += config.alpha * td_error
episode_return += reward
td_errors.append(abs(td_error))
state = next_state
result.episode_returns.append(episode_return)
result.mean_abs_td_error.append(float(np.mean(td_errors)) if td_errors else 0.0)
return resultWhat changed: Epsilon is annealed rather than fixed, which is what stops the deployed policy from acting randomly forever. The terminal-state bootstrap is handled explicitly — bootstrapping past a terminal is the most common bug in a Q-learning implementation. And the result carries TD error and visitation coverage, because falling TD error is the real convergence signal while episode return can plateau with the values still badly wrong.
O(|A|) per step via argmax; the table is one contiguous array.
Faster, and the justification for each change.
"""Q-learning - vectorized over parallel environments, Double-Q debiased."""
import numpy as np
from numpy.typing import NDArray
QTable = NDArray[np.float64]
def batched_update(
q_a: QTable,
q_b: QTable,
states: NDArray[np.intp],
actions: NDArray[np.intp],
rewards: NDArray[np.float64],
next_states: NDArray[np.intp],
dones: NDArray[np.bool_],
alpha: float,
gamma: float,
) -> None:
"""Double Q-learning update across many environments at once, in place.
Two tables, and the fix is subtle but total: A picks the best next action,
B evaluates it. Because the noise in the two tables is independent, the max
can no longer select for whichever entry got lucky - which is exactly the
maximization bias that makes single-table Q-learning optimistic.
"""
# argmax over A, value from B. One fancy-indexed gather each, no loop.
best_next_actions = np.argmax(q_a[next_states], axis=1)
next_values = q_b[next_states, best_next_actions]
next_values[dones] = 0.0 # no future past a terminal
targets = rewards + gamma * next_values
current = q_a[states, actions]
# np.add.at, not q_a[states, actions] += ...: when two environments visit
# the SAME (s, a) in one batch, plain fancy-index assignment keeps only the
# last write. add.at accumulates both, which is the correct semantics and
# a genuinely easy bug to ship.
np.add.at(q_a, (states, actions), alpha * (targets - current))
def run_vectorized(
envs, n_states: int, n_actions: int, steps: int = 100_000,
alpha: float = 0.1, gamma: float = 0.99, epsilon: float = 0.1,
) -> QTable:
"""Step many independent environments in lockstep.
The per-step work is tiny, so a single-environment loop is dominated by
Python interpreter overhead. Running n_envs environments in lockstep
amortizes that over the whole batch - the same reason vectorized envs are
standard in every serious RL library.
"""
rng = np.random.default_rng(0)
n_envs = len(envs)
q_a = np.zeros((n_states, n_actions), dtype=np.float64)
q_b = np.zeros((n_states, n_actions), dtype=np.float64)
states = np.array([env.reset() for env in envs], dtype=np.intp)
# Scratch buffers reused every step rather than reallocated.
actions = np.empty(n_envs, dtype=np.intp)
for step in range(steps // n_envs):
# Vectorized epsilon-greedy: one RNG draw covers every environment.
explore = rng.random(n_envs) < epsilon
greedy = np.argmax(q_a[states] + q_b[states], axis=1) # sum both tables to act
actions[:] = np.where(explore, rng.integers(n_actions, size=n_envs), greedy)
results = [env.step(int(a)) for env, a in zip(envs, actions)]
next_states = np.fromiter((r[0] for r in results), dtype=np.intp, count=n_envs)
rewards = np.fromiter((r[1] for r in results), dtype=np.float64, count=n_envs)
dones = np.fromiter((r[2] for r in results), dtype=np.bool_, count=n_envs)
# Alternate which table is updated, so both stay independent.
if step % 2 == 0:
batched_update(q_a, q_b, states, actions, rewards, next_states, dones, alpha, gamma)
else:
batched_update(q_b, q_a, states, actions, rewards, next_states, dones, alpha, gamma)
states = np.where(dones, [env.reset() for env in envs], next_states)
return (q_a + q_b) / 2.0What changed: Two changes, one for speed and one for correctness. Many environments step in lockstep so the tiny per-step work is amortized over a batch instead of being drowned in interpreter overhead. And the single table becomes Double Q-learning, which removes the maximization bias — A selects the action, B values it, so the max can no longer select for lucky noise. The `np.add.at` detail matters: two environments hitting the same state-action in one batch would silently lose an update under plain fancy-index assignment.
Batch work to amortize interpreter overhead
Per-step work is a lookup and a max, so a single-environment loop is almost entirely Python overhead. Stepping n environments in lockstep amortizes it across the batch.
Trade-off: Environments must be steppable in lockstep and roughly balanced in episode length, or fast ones idle waiting for slow ones.
Vectorize to NumPy/BLAS (@, np.dot, einsum)
Epsilon-greedy action selection and the whole target computation become array operations over the batch instead of per-environment branches.
Trade-off: The greedy argmax is computed for every environment including the ones that will explore, so a fraction of that work is discarded.
Pre-allocate output arrays and use in-place operations
The action buffer is reused and np.add.at updates the table in place, so the hot loop allocates nothing per step.
Trade-off: np.add.at is notably slower per element than plain fancy indexing — a deliberate correctness-for-speed trade, since the fast version is wrong on duplicate indices.
One batched update per n_envs steps. Illustrative, not a measured benchmark.