RL Fundamentals

Every RL algorithm — from tabular Q-learning to PPO powering RLHF — is solving the same formal problem, defined precisely below. Get this formulation solid, and every named algorithm becomes "one specific way to solve this equation," not a new thing to memorize from scratch each time.

Intuition: One Loop, Four Values

Strip away the vocabulary and RL is one small, repeating exchange: the agent is in some state, it picks an action, and the environment hands back a reward and a new state. Every concept on this page — policies, value functions, the Bellman equations, Q-learning — exists to answer one question about that loop: given this loop repeats forever, what should the agent do at each state to make the rewards it collects as large as possible?

Markov Decision Processes (MDPs)

An MDP formalizes "an agent interacting with an environment over time" as a tuple $(S, A, P, R, \gamma)$:

• States ($S$): everything about the environment relevant to decision-making at a given moment — a board position, a robot's joint angles, a conversation's history so far.
• Actions ($A$): what the agent can do at a given state.
• Transition function ($P(s' \mid s, a)$): the probability of ending up in state $s'$, given the agent took action $a$ in state $s$ — often stochastic (the same action from the same state doesn't always lead to the same outcome), which is exactly what separates RL from simple planning over a known, deterministic world.
• Reward function ($R(s, a, s')$): the immediate numeric feedback the agent receives for that transition — the only signal telling the agent whether an action was good, and often sparse (a reward of zero for many steps, then a single meaningful reward far later — see the credit assignment problem below).
• Discount factor ($\gamma \in [0, 1]$): how much the agent values future reward relative to immediate reward.
• The Markov property: the defining assumption that makes this tractable — the transition and reward at time $t$ depend only on the current state $s_t$ and action $a_t$, not on the full history of states/actions that led there. This is why "state" has to be defined carefully in practice: if the true next-outcome distribution genuinely depends on history beyond the current state, the state representation is incomplete, and the Markov assumption is being (silently, often harmfully) violated.

Policies and Value Functions

• Policy ($\pi(a \mid s)$): the agent's strategy — a (possibly stochastic) mapping from states to actions. The entire goal of RL is finding a good policy.
• Return: the total discounted future reward from a given point onward, $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$ — what the agent actually cares about maximizing, not any single immediate reward. $\gamma$ isn't just an abstract knob — drag it below and watch it decide, concretely, how much a reward 8 steps away is actually worth right now:

• State-value function ($V^\pi(s)$): the expected return starting from state $s$, following policy $\pi$ thereafter — "how good is it to be in this state, given how I'll behave from here."
• Action-value function ($Q^\pi(s, a)$): the expected return starting from state $s$, taking action $a$, then following $\pi$ thereafter — "how good is it to take this specific action here, given how I'll behave afterward." $Q$ is the more directly useful quantity for choosing an action: the best action in a state is simply $\arg\max_a Q^\pi(s, a)$, no separate policy needed if you have an accurate $Q$.

The Bellman Equations

The Bellman equations are the recursive structure that makes RL solvable at all — they express a state's value in terms of its immediate reward plus the (discounted) value of whatever state comes next, rather than requiring the entire infinite future to be considered explicitly every time:

$V^\pi(s) = \mathbb{E}_{a \sim \pi}\left[R(s,a) + \gamma \, \mathbb{E}_{s' \sim P}\left[V^\pi(s')\right]\right]$

The analogous equation for $Q$:

$Q^\pi(s,a) = \mathbb{E}_{s'}\left[R(s,a,s') + \gamma \, \mathbb{E}_{a' \sim \pi}\left[Q^\pi(s', a')\right]\right]$

This recursive "value now = immediate reward + discounted value of what's next" structure is exactly the same self-referential idea as dynamic programming — the optimal solution to a larger problem is built from optimal solutions to smaller subproblems. Solving it directly, by repeatedly applying the Bellman optimality equation ($V(s) \leftarrow \max_a [R + \gamma V(s')]$) to every state until the values stop changing, is called value iteration — watch it actually converge, one full sweep of the grid at a time:

This is the mathematical basis every value-based RL algorithm (Q-learning, DQN, and their descendants) is built directly on top of — the difference is how the backup gets computed when the transition function $P$ isn't known in advance, which is exactly what Q-learning addresses next.

Q-Learning

A model-free algorithm (no need to know the transition function $P$ explicitly — it learns purely from experienced transitions) that directly learns the optimal action-value function $Q^*$ via the update rule:

$Q(s,a) \leftarrow Q(s,a) + \alpha \left[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\right]$

The term in brackets is the TD (temporal difference) error — the gap between the current estimate $Q(s,a)$ and a better, bootstrapped target ($r$ plus the discounted best estimate of the next state's value) — the update nudges $Q$ toward that better target by a step size $\alpha$. Step through this exact update on a real 4-state corridor, using the same trace from the loop diagram above:

Q-learning is off-policy: the update uses $\max_{a'} Q(s', a')$ — the value of the best next action — regardless of which action the agent actually took next while exploring, letting it learn the optimal policy's values even while behaving more randomly/exploratorily than that optimal policy would.

SARSA

Nearly identical to Q-learning, with one crucial difference — SARSA (State-Action-Reward-State-Action, named for the quintuple its update uses) is on-policy:

$Q(s,a) \leftarrow Q(s,a) + \alpha \left[r + \gamma\, Q(s',a') - Q(s,a)\right]$

Here $a'$ is the action the agent actually took next (following its current, possibly-exploring policy), not the best possible action. This makes SARSA learn the value of the policy it's actually following (including its exploration behavior), which tends to produce more conservative, safer learned behavior in risky environments.

On-Policy vs. Off-Policy Learning, Made Concrete

The distinction generalizes to every RL algorithm, and there's no better place to see it produce a genuinely different outcome than the classic Cliff Walking task: a grid with a deadly cliff along one edge, trained for real, with both algorithms:

• On-policy: the algorithm learns about (and improves) the exact same policy currently being used to generate experience — every past experience becomes stale for training the moment the policy changes even slightly, since it was collected under a different (now-outdated) policy.
• Off-policy: the algorithm can learn about a different (often better/optimal) target policy than the one generating experience — this is what makes experience replay (storing and reusing past experience for many training updates, well after it was collected — see DQN) possible at all, since off-policy methods aren't invalidated by that experience having been collected under an older policy.

Code: Value Iteration and Q-Learning, For Real

import numpy as np

# Value iteration -- the exact backup the grid diagram animates above.
def value_iteration(P, R, gamma, n_states, n_actions, iterations=100):
    V = np.zeros(n_states)
    for _ in range(iterations):
        Q = R + gamma * P @ V          # Q(s,a) = R(s,a) + gamma * sum_s' P(s'|s,a) V(s')
        V = Q.max(axis=1)              # V(s) = max_a Q(s,a)
    return V

# Tabular Q-learning -- the exact update the corridor diagram steps through.
def q_learning_update(Q, s, a, r, s_next, alpha=0.5, gamma=0.9):
    td_target = r + gamma * np.max(Q[s_next])
    Q[s, a] += alpha * (td_target - Q[s, a])
    return Q

Next: Advanced RL — scaling these tabular ideas up with deep learning, and the variants (offline RL, imitation learning) that relax this section's core assumptions.