Reinforcement Learning

Definition: A learning paradigm where an agent learns to make decisions by taking actions in an environment and receiving rewards or penalties, aiming to maximize cumulative reward over time.

How It Works

Agent observes state → takes action → environment returns reward + new state
Over many episodes, the agent learns a policy (strategy) that maximizes long-term reward, via methods like Q-learning or policy gradients
The interaction loop is formalized as a Markov Decision Process (MDP): a tuple of states, actions, transition probabilities, and rewards, where the next state depends only on the current state and action, not the full history
Because rewards can be delayed, the agent must solve the credit assignment problem — figuring out which of the many actions taken earlier in an episode actually caused a reward received much later
Training alternates between exploration (trying new actions to discover their value) and exploitation (taking the action currently believed to be best) — an imbalance in either direction stalls learning
Training happens in episodes (or continuously, for non-episodic tasks) — one episode is a full sequence from an initial state to a terminal state (e.g., one game of chess, one attempt at a level)
The environment is often only partially observable — the agent’s “state” is really an observation that may not capture the full underlying situation, which is what motivates recurrent or memory-augmented policies in harder RL problems

The Agent-Environment Loop

The interaction described above is the single most important picture in RL — everything else in this note is detail layered on top of it. The agent and environment are strictly separate: the agent only ever sees states and rewards the environment hands it, and the environment only ever sees actions the agent hands back. Neither side has direct access to the other’s internals.

Every RL algorithm — tabular Q-learning, DQN, PPO, AlphaZero’s tree search — is a different answer to exactly one question inside this loop: given the states and rewards observed so far, how should the agent pick its next action? The loop itself never changes; only the rule inside the “choose action” step does.

Under the Hood

Policy (π): a function mapping states to actions (deterministic) or to a probability distribution over actions (stochastic). Learning RL means learning π
Value function (V): the expected cumulative future reward from a state, assuming the agent follows its current policy from there onward
Action-value function (Q): the expected cumulative future reward from taking a specific action in a specific state, then following the policy — this is what Q-learning learns directly
Discount factor (gamma): a number between 0 and 1 that shrinks the weight of future rewards relative to immediate ones; gamma close to 1 makes the agent far-sighted, gamma close to 0 makes it greedy for immediate payoff
Bellman equation: the recursive identity underlying almost all RL algorithms — the value of a state equals the immediate reward plus the discounted value of the next state. Q-learning, value iteration, and TD-learning are all different ways of approximating a solution to this equation
Temporal difference (TD) learning: updates value estimates using the difference between a predicted value and a better bootstrapped estimate one step later, rather than waiting for the full episode to end — this is what makes online, incremental RL possible
Advantage function (A): defined as Q(s,a) minus V(s) — how much better a specific action is than the average action in that state. Used in actor-critic and PPO to reduce the variance of policy updates versus using raw returns
Return (G): the actual discounted sum of rewards observed from a timestep onward during a rollout; the value function is trying to predict the expectation of this quantity before the episode plays out

Worked example — two Q-learning updates by hand. Using the update rule Q(s,a) := Q(s,a) + alpha * (r + gamma * max_a' Q(s',a') - Q(s,a)) with alpha = 0.1 and gamma = 0.9:

Reaching the goal: the agent takes an action that lands it on a terminal goal state and receives reward r = 1. Since the goal is terminal, max_a' Q(s',a') = 0 — there’s no future from a terminal state. If Q(s,a) was previously 0.2, the target is 1 + 0.9*0 = 1, the TD error is 1 - 0.2 = 0.8, and the update is 0.1 * 0.8 = 0.08 — so Q(s,a) becomes 0.28. One good outcome nudges the estimate up, but it takes many repeated visits before Q(s,a) converges close to 1.
A non-terminal step: the agent takes an action leading to a non-terminal state where the best already-learned value is max_a' Q(s',a') = 0.5, and receives a small step penalty r = -0.01. If Q(s,a) was 0.3, the target is -0.01 + 0.9*0.5 = 0.44, the TD error is 0.44 - 0.3 = 0.14, and the update is 0.1 * 0.14 = 0.014 — so Q(s,a) becomes 0.314.

Notice the second update never touched the reward at the goal directly — it only bootstrapped off Q(s'), which itself was only accurate because earlier updates had already propagated value backward from the goal, one step at a time. This step-by-step backward propagation, not any single update, is what eventually makes distant states “aware” of a reward many steps away.

Exploration Strategies

Epsilon-greedy: with probability epsilon take a random action, otherwise take the currently best-known action; epsilon is usually annealed from high (mostly explore) to low (mostly exploit) over training
Softmax / Boltzmann exploration: sample actions proportionally to their estimated value passed through a softmax, so better actions are more likely without fully discarding worse ones
Upper Confidence Bound (UCB): favors actions with high estimated value or high uncertainty (rarely tried), giving a principled way to explore under-sampled actions
Thompson sampling: maintains a probability distribution over each action’s expected reward and samples from it to decide what to try next, naturally balancing exploration and exploitation as uncertainty shrinks
Multi-armed bandits: the simplified special case of RL with a single state and no transitions — only the action-reward relationship matters — used to study exploration/exploitation in isolation and applied directly to A/B testing and ad placement

The epsilon-greedy decision, made fresh at every single timestep, is itself a small state machine:

As training progresses, epsilon is typically annealed downward on a schedule, so the same diagram increasingly resolves toward the “Exploit” branch — early training spends most of its time on the left path, late training almost all of it on the right.

Variants

Model-free vs. model-based: model-free agents (Q-learning, policy gradients) learn purely from trial-and-error interaction without ever building an explicit model of the environment’s dynamics; model-based agents learn or are given a transition model and can plan ahead by simulating future states
Value-based methods: learn a value or Q-function and derive the policy by acting greedily with respect to it (e.g., Q-learning, Deep Q-Networks/DQN)
Policy-gradient methods: directly parameterize and optimize the policy by gradient ascent on expected reward (e.g., REINFORCE, PPO, TRPO) — better suited to continuous action spaces than value-based methods
Actor-critic methods: hybrid approach where an “actor” network chooses actions and a “critic” network estimates the value function to reduce the variance of the actor’s gradient updates (e.g., A2C, A3C, SAC)
On-policy vs. off-policy: on-policy algorithms (SARSA, PPO) can only learn from data generated by the current policy; off-policy algorithms (Q-learning, DQN) can learn from any past experience, including data from older or different policies, which enables experience replay

This taxonomy is a simplification — actor-critic methods are arguably a special case of policy-based methods that happen to also learn a value function, and model-based planning can sit on top of any of the three model-free families rather than replacing them — but it’s a useful map for placing a new algorithm name relative to ones you already know.

From Tabular to Deep RL

The Q-learning code in this note’s Code Example section stores one value per (state, action) pair in an explicit table — that only works when the state space is small enough to enumerate. Real problems rarely cooperate: a robot’s joint angles are continuous, a game board like Go has more legal positions than atoms in the observable universe, and raw pixel input has one dimension per pixel channel. Tabular methods simply have nowhere to put that many entries.

Deep RL replaces the table with a Neural Network function approximator: instead of looking up Q(s,a) in a table, the network takes s as input and outputs an estimated Q(s,a) for every action. Nearby or similar states naturally produce similar outputs because they share network weights, so the agent can generalize to states it has never exactly visited before — something a lookup table structurally cannot do. This is exactly the substitution Deep Q-Networks made: a Convolutional Neural Network (CNN) reads raw Atari frames as input and outputs one Q-value per joystick action, learned end-to-end via the same Bellman update shown above, just with gradient descent on network weights standing in for a direct table write.

The tradeoff is that function approximation reintroduces every headache of training a neural network — non-stationary targets (the “correct” Q-value itself shifts as the network updates), sensitivity to learning rate, and the need for tricks like target networks and experience replay just to keep training stable — none of which a tabular agent with a handful of states ever has to worry about.

Why It Matters

Distinct from supervised learning — there’s no fixed “correct answer” per step, only delayed feedback
Powers game-playing AI (AlphaGo), robotics control, and RLHF used to align LLMs
The only major ML paradigm designed for sequential decision-making, where actions affect future opportunities, not just the current prediction
Underpins recommendation systems that optimize for long-term engagement rather than a single click, and resource allocation problems like ad bidding and datacenter cooling control
Provides a natural framework for problems with a feedback loop between the model’s own decisions and the data it sees next, which supervised learning’s static-dataset assumption can’t capture
The mathematical backbone (MDPs, Bellman equations) is shared with classical control theory and operations research, so RL absorbs decades of prior theory on optimal decision-making under uncertainty

Common Interview Questions

What’s the difference between value-based and policy-based methods? Value-based methods learn Q(s,a) or V(s) and derive a policy by acting greedily; policy-based methods directly parameterize and optimize the policy without necessarily learning an explicit value function
Why is the Bellman equation important? It expresses a state’s value recursively in terms of immediate reward plus the discounted value of the next state, which is what makes incremental, bootstrapped learning (rather than waiting for full episodes) possible
What is the exploration-exploitation tradeoff? The agent must balance trying new actions to gather information (exploration) against choosing the currently best-known action to maximize reward (exploitation) — too much of either produces a suboptimal policy
Why do policy-gradient methods have high variance? Because they estimate gradients from sampled returns, which are noisy; techniques like baselines, advantage estimation, and larger batches reduce this variance without introducing bias
What is experience replay and why does it help? Storing past transitions in a buffer and sampling randomly from it breaks the correlation between consecutive training samples and lets off-policy algorithms like DQN reuse data multiple times, improving sample efficiency
How does AlphaZero differ from AlphaGo? AlphaGo was pretrained on human expert games before self-play fine-tuning; AlphaZero learns entirely from self-play with no human data, using the same policy/value network plus Monte Carlo tree search architecture for Go, chess, and shogi alike
How would you debug an RL agent whose reward curve is flat? Check the reward signal is actually informative (not constant or misaligned with the goal) before touching the algorithm; then check the environment and action space are wired correctly by seeing whether even a random policy occasionally stumbles into reward; only after ruling both out should you suspect the learning algorithm or hyperparameters
Why does sample efficiency differ between on-policy and off-policy learning? On-policy methods must discard data as soon as the policy that generated it changes, since the data no longer reflects the current policy’s behavior; off-policy methods can reuse old data from any past policy via experience replay, which is why DQN-style off-policy methods are typically far more sample-efficient than on-policy methods like vanilla PPO

History

Rooted in animal-learning psychology (Pavlov, Thorndike) and formalized mathematically through dynamic programming (Bellman, 1950s) and temporal-difference learning (Sutton, 1980s)
Christopher Watkins introduced Q-learning in his 1989 PhD thesis Learning from Delayed Rewards (King’s College, Cambridge); Watkins and Dayan supplied the first rigorous convergence proof in a 1992 follow-up paper
Ronald Williams’ 1992 paper “Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning” introduced REINFORCE, the first policy-gradient algorithm, showing how gradient ascent on expected reward could be estimated without ever computing an explicit value function
TD-Gammon (1992) was an early landmark, learning backgammon to near-expert level purely from self-play
Deep Q-Networks (DeepMind, 2013-2015) combined Q-learning with CNNs to play Atari games directly from pixels, reigniting interest in deep RL
Sutton and Barto’s textbook Reinforcement Learning: An Introduction (1st edition 1998, substantially revised 2nd edition 2018) remains the field’s standard reference, synthesizing decades of scattered results into one coherent framework
Schulman et al. introduced Trust Region Policy Optimization (TRPO) in 2015 and its simpler, now-dominant successor Proximal Policy Optimization (PPO) in 2017; Mnih et al.’s 2016 A3C paper and Haarnoja et al.’s 2018 Soft Actor-Critic (SAC) paper rounded out the actor-critic algorithms in common use today
AlphaGo (2016) and AlphaZero (2017) combined policy/value networks with Monte Carlo tree search to beat world champions at Go, then generalized the same approach to chess and shogi without any human game data
RLHF (2017 onward, popularized by InstructGPT/ChatGPT) repurposed policy-gradient methods to align language model outputs with human preferences, becoming the dominant post-training step for modern LLMs — the technique traces to Christiano et al.’s 2017 paper “Deep Reinforcement Learning from Human Preferences,” which first showed a reward model trained on human comparisons between trajectories could substitute for a hand-written reward function; OpenAI’s 2022 InstructGPT paper (Ouyang et al.) then applied the same idea, with PPO, to fine-tune language models on human preference data, directly setting up ChatGPT’s late-2022 release

Common Pitfalls

Reward hacking — the agent finds an unintended shortcut that maximizes reward without achieving the real goal
Sample inefficiency — RL often needs vastly more trial-and-error than supervised learning to converge
Reward shaping done carelessly — dense intermediate rewards meant to speed up learning can accidentally teach the wrong behavior if they don’t align with the true objective
Non-stationarity during training — as the policy changes, the distribution of states it visits changes too, which can destabilize learning (especially in multi-agent settings where other agents are also learning)
High variance in policy-gradient estimates, requiring techniques like baselines, advantage estimation, or larger batch sizes to get a usable signal
Treating simulation results as directly transferable to the real world (“sim-to-real gap”) without accounting for physics or sensor differences
Poorly designed state/observation representations that omit information the agent actually needs to act well, capping performance regardless of which algorithm is used
Misjudging the discount factor gamma — too low makes the agent myopic and blind to long-term consequences, too high makes value estimates slow to converge and more sensitive to noise
Conflating “the agent achieved high reward in training” with “the agent learned the intended behavior” — always inspect rollouts qualitatively, not just the reward curve
Bootstrapping off a terminal state’s value as if it were non-terminal — forgetting to zero out max_a' Q(s',a') at episode boundaries silently corrupts every value estimate that depends on it, and the bug can stay invisible in the reward curve for a long time
Letting the state representation leak information the agent shouldn’t realistically have access to, producing a policy that looks superhuman in evaluation and never reproduces outside the exact test harness it was built against
Assuming a technique that worked on one environment (e.g., Atari) transfers untouched to a structurally different one (e.g., continuous robotics control) — the algorithm families in Variants above exist precisely because no single approach dominates across both discrete and continuous action spaces

Comparison

Paradigm	Feedback signal	Goal	Typical use case
Supervised Learning	Correct label per example	Minimize prediction error	Classification, regression
Unsupervised Learning	None	Discover structure	Clustering, dimensionality reduction
Reinforcement Learning	Scalar reward, often delayed	Maximize cumulative reward	Sequential decision-making, control
Self-Supervised Learning	Labels generated from the data itself	Learn representations	Pretraining (e.g., masked language modeling)
Imitation Learning	Expert demonstrations, no reward signal	Match demonstrated behavior	Robotics, autonomous driving, warm-starting RL

Code Example

A minimal tabular Q-learning update, the core of value-based RL:

import numpy as np

# Q-table: rows = states, columns = actions
Q = np.zeros((n_states, n_actions))
alpha = 0.1      # learning rate
gamma = 0.95     # discount factor
epsilon = 0.1    # exploration rate

for episode in range(num_episodes):
    state = env.reset()
    done = False
    while not done:
        # epsilon-greedy action selection
        if np.random.rand() < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(Q[state])

        next_state, reward, done, _ = env.step(action)

        # Bellman update
        best_next = np.max(Q[next_state])
        Q[state, action] += alpha * (reward + gamma * best_next - Q[state, action])

        state = next_state

Interactive Example — Q-Learning in a Tiny Grid World

The same update rule, runnable directly: a 1D grid world with 6 states (0 through 5), the goal fixed at state 5, and two actions (left, right). Run it and watch the Q-values for “right” climb toward the reward at every state.

Every state converges on “right” because it’s always the shortest path to the only positive reward — exactly the tabular update worked by hand earlier, just run a few hundred times instead of twice.

Real-World Example

Game-playing (AlphaGo/AlphaZero): DeepMind’s AlphaGo combined a policy network and a value network with Monte Carlo tree search, then beat 18-time world champion Lee Sedol 4 games to 1 in March 2016 — the first time a program had beaten a top professional at Go on a full-size board without a handicap. AlphaZero (2017) generalized the same self-play architecture to chess and shogi with no human game data at all, outperforming the strongest existing programs in each game after training from random play alone
RLHF for LLMs: models like ChatGPT and Claude are fine-tuned with policy-gradient methods (commonly PPO) against a learned reward model trained on human preference comparisons, steering outputs toward helpful, honest completions without hand-writing rules for every case
Datacenter cooling: DeepMind applied RL to Google’s datacenter cooling systems and reported roughly a 40% reduction in cooling energy use, with the agent discovering control policies beyond what human-tuned heuristics had found
Recommendation systems: large platforms have experimented with RL-based recommenders that optimize for long-term watch time or satisfaction rather than a single click, treating each recommendation as one action in a long-running episode. YouTube’s production recommender is a documented example — Chen et al.’s 2019 paper describes a REINFORCE-based policy trained on logged user feedback with off-policy correction, serving recommendations from an action space of millions of videos
Algorithmic trading: RL agents learn order-execution policies that minimize market impact while filling large orders over time, with reward tied to execution cost rather than a single labeled “correct” trade
Robotics and autonomous vehicles: RL is used for low-level control (balance, grasping) and, combined with simulation, for higher-level planning policies later validated or fine-tuned on real hardware. OpenAI’s Dactyl system (2019) trained a robotic hand entirely in simulation to solve a Rubik’s Cube one-handed, using a technique called Automatic Domain Randomization to make the policy robust enough to survive the transition to a physical hand

Benchmarks & Tools

Environments: OpenAI Gym / Gymnasium (standard API for RL environments), Atari 2600 suite, MuJoCo and PyBullet (continuous control/robotics physics simulation), StarCraft II and Dota 2 (large-scale multi-agent benchmarks)
Libraries: Stable-Baselines3 and RLlib provide tested implementations of DQN, PPO, SAC, and other standard algorithms rather than requiring a from-scratch implementation
Standard metrics: average episodic return, sample efficiency (return per environment step), and wall-clock training time are all tracked separately, since an algorithm can win on one and lose on another
Reproducibility challenges: RL results are notoriously sensitive to random seed, exact hyperparameters, and even library version — published RL benchmarks are harder to reproduce exactly than most supervised learning results

Comparison Notes

Supervised and unsupervised learning both assume a static dataset; RL’s data distribution depends on the agent’s own evolving behavior, which is what makes it inherently non-stationary
RL is the natural fit whenever the notion of “correct action” doesn’t exist in isolation — only a sequence of actions can be judged good or bad, via the cumulative reward they produce

Best Practices

Start with the simplest baseline (random policy, tabular Q-learning) to sanity-check the reward function and environment before reaching for deep RL
Normalize and clip rewards — unbounded reward scales destabilize gradient-based policy updates
Log episode return and episode length throughout training, not just the loss — RL loss curves are notoriously uninformative on their own
Use established libraries (Stable-Baselines3, RLlib) for algorithm implementations rather than hand-rolling PPO/DQN — subtle bugs in RL code fail silently as “just needs more training”
Set a hard evaluation protocol (fixed seeds, frozen policy, no exploration noise) separate from training rollouts, since training-time returns are a noisy and biased estimate of true policy quality
Shape rewards sparingly and validate that a hand-crafted intermediate reward actually correlates with the true objective before trusting it
Run multiple seeds for any RL experiment before drawing conclusions — RL training variance across random seeds is notoriously high compared to supervised learning
Separate the reward function from the evaluation metric wherever possible — optimizing directly on the metric you’ll be judged by tempts reward hacking, while a well-designed proxy reward that correlates with it is more robust
Version and log the environment definition alongside every model checkpoint — an RL policy is only meaningful paired with the exact environment dynamics it was trained against, unlike a supervised model that stays interpretable against any dataset with a matching schema

FAQ

Is RL the same as RLHF? No — RLHF is a specific application of RL (usually PPO) where the reward signal comes from a model trained to imitate human preference judgments, not from the environment directly
Why not just use supervised learning if I have expert demonstrations? You can (this is called imitation learning / behavior cloning), but it doesn’t let the agent discover strategies better than the demonstrator, and it degrades when the agent drifts into states never seen in the demonstrations
Does RL need a simulator? Not strictly, but training directly in the real world is usually too slow, expensive, or unsafe for the number of trials most RL algorithms need
What’s the difference between RL and a multi-armed bandit? A bandit has one state and no state transitions — every action is independent of prior ones — while full RL involves states that change based on past actions, requiring the agent to reason about long-term consequences
Can RL be combined with supervised learning? Yes — imitation learning pretrains a policy on expert demonstrations (a supervised step) before refining it with RL, and many RLHF pipelines start from a supervised fine-tuned model rather than a randomly initialized one
How is the reward function different from the loss function in supervised learning? A loss function is fully known and differentiable, computed directly from a label the model is trying to match; a reward function is typically a scalar signal from the environment that the agent cannot differentiate through directly — this is exactly why RL needs specialized machinery (policy gradients, value functions) that ordinary backpropagation-on-a-loss doesn’t require

Example

A robot learning to walk by being rewarded for forward progress and penalized for falling, through millions of simulated trial steps. Early in training it flails randomly; over time, the Q-values (or policy weights) shift toward action sequences that reliably produce forward displacement, and the agent converges on a stable gait — without ever being told explicitly what “walking” looks like.

Referenced by

Dig deeper

Spot an error in this note?