Intro to Reinforcement Learning

Introduction

So far, we have studied supervised learning and unsupervised learning. We now turn to a third paradigm. Reinforcement Learning (RL) is a machine learning framework in which an agent interacts with an environment to learn a behavior that maximizes a scalar reward signal over time.

Formally, the environment is typically modeled as a Markov Decision Process (MDP), defined by a tuple \[ (\mathcal{S}, \mathcal{A}, \mathcal{T}, r, \gamma) \] where \(\mathcal{S}\) is the state space, \(\mathcal{A}\) is the action space, \(\mathcal{T}\) is the transition kernel (a conditional distribution \(\mathcal{T}(s' \mid s, a)\)), \(r\) is the reward function, and \(\gamma\) is the discount factor. The MDP definition below gives a more detailed probabilistic formulation. It writes the transition kernel as \(p_T\), separates the stochastic reward kernel \(p_R\) from the expected reward function \(R\), and includes the initial state distribution explicitly. The discount factor \(\gamma\) is then treated as part of the objective rather than of the environment.

At each time step, the agent observes a state \(s_t \in \mathcal{S}\) and selects an action \(a_t \in \mathcal{A}\). The environment then transitions to a new state \(s_{t+1}\) according to the transition dynamics \(\mathcal{T}(s_{t+1} \mid s_t, a_t)\) and emits a reward \(r_t\). The goal of the agent is to learn a policy \(\pi(a \mid s)\) that maximizes the expected cumulative reward: \[ \mathbb{E}_\pi \left[ \sum_{t=0}^\infty \gamma^t r_t \right]. \]

Reinforcement learning differs fundamentally from other machine learning paradigms:

• Supervised learning trains models on ground-truth input-output pairs with explicit correct labels for each input.
• Unsupervised learning discovers hidden structure or representations in unlabeled data without any feedback signal.
• Reinforcement learning uses only a scalar reward signal that provides evaluative feedback based on the agent's interaction with an environment.

In RL, learning is typically driven by trial-and-error interaction rather than by labeled examples, and the objective is a policy that maximizes expected cumulative reward rather than a model of the data. The offline (or batch) setting, in which an agent learns from a fixed pre-collected dataset instead of interacting, is a notable exception.

RL has been successfully applied in domains such as robotics, recommendation systems, and game-playing. RL has also been used in the training of large language models (LLMs). In particular, a method called Reinforcement Learning from Human Feedback (RLHF) is used to fine-tune LLMs to follow human preferences, aiming to make outputs more helpful, safe, and better aligned with user intent.

The diversity of RL applications has led to a rich classification of algorithms, each designed for a different aspect of the learning problem.

Classification of RL Algorithms

Model-Based vs Model-Free Methods

The most fundamental distinction in RL concerns whether the agent learns an explicit model of the environment.

Model-based RL methods estimate the following from data:

• the transition dynamics \(p_T(s' \mid s, a)\), and
• the reward model \(p_R(r \mid s, a, s')\).

Once learned, the agent uses planning algorithms to compute an optimal policy \(\pi_*\). Classical planning is based on dynamic programming such as value iteration (VI) and policy iteration (PI). The main advantage is environment-sample efficiency. The agent can simulate many trajectories using the learned model without additional environment interaction. However, model learning introduces model bias. If the learned model is inaccurate, the agent may perform well in simulation but poorly in the real environment.

Model-free RL methods bypass explicit environment modeling and directly learn value functions or policies from experience. These methods are generally simpler to implement and more robust to model errors, but typically require more environment interactions compared to model-based approaches.

Value-Based vs Policy-Based

This taxonomy classifies algorithms based on what they learn within model-free RL.

Value-based methods learn the optimal action-value function \(Q_*\) (or its approximator \(Q_w\), typically a neural network trained iteratively) from experience, and then act greedily with respect to it: \(\pi_*(s) \in \arg\max_a Q_*(s, a)\). Given a transition \((s, a, r, s')\), we define the temporal difference (or TD error) as \[ r + \gamma \max_{a'} Q_w(s', a') - Q_w(s, a), \] whose conditional expectation given \((s, a)\) is the Bellman optimality residual at \((s, a)\). When \(Q_w = Q_*\), the TD error is zero on average by Bellman's optimality equation, so a non-zero expected TD error provides a learning signal.

Examples include Q-learning, SARSA, and Deep Q-Networks (DQN). These methods differ in their bootstrap target. For instance, SARSA replaces the \(\max_{a'}\) above with the actually-taken next action \(a'\). The precise update rules are given in the TD-learning sections below.

Policy-based methods directly optimize the expected-return objective \[ J(\pi_{\boldsymbol{\theta}}) := \mathbb{E}_{\pi_{\boldsymbol{\theta}}} \left[ \sum_{t=0}^{\infty} \gamma^t r_t \right] \] with respect to the policy parameter \(\boldsymbol{\theta}\) using policy gradient, and can naturally handle continuous action spaces and stochastic policies.

Examples include REINFORCE, Trust Region Policy Optimization (TRPO), and actor-critic methods such as Advantage Actor-Critic (A2C), Deep Deterministic Policy Gradient (DDPG), Soft Actor-Critic (SAC), and Proximal Policy Optimization (PPO).

On-Policy vs Off-Policy Methods

This taxonomy concerns the data usage strategy during learning.

On-policy methods learn from data generated by the current policy that is being improved. The agent explores the environment and makes updates to its policy based on the actions it has taken.
(for example, SARSA, REINFORCE, A2C, and PPO.)

Off-policy methods learn from data generated by a different policy than the one being improved. This allows the agent to reuse old data or learn from data collected by other agents. The policy used to collect data is called the behavioral policy, and the policy being learned is called the target policy. Off-policy methods typically offer higher sample efficiency than on-policy methods. Some of them must correct for the mismatch between the behavioral and target distributions, for example with importance-sampling weights in off-policy policy-gradient estimators. One-step Q-learning needs no such correction, because its target does not depend on the behavioral policy.
(for example, Q-learning, DQN, DDPG, and SAC.)

Exploration vs. Exploitation

The exploration-exploitation tradeoff is fundamental to reinforcement learning. An agent must balance between:

• Exploitation. Choosing actions that yield high rewards based on current knowledge.
• Exploration. Trying new actions to potentially discover better strategies.

All strategies in this section assume access to action-value estimates \(Q(s, a)\), the action-value function formally defined in the Value Functions section below. Here we use it operationally as "the agent's current estimate of how good action \(a\) is in state \(s\)."

\(\varepsilon\)-Greedy Strategy

The simplest exploration strategy chooses: \[ a_t = \begin{cases} \arg\max_a Q(s_t, a) & \text{with probability } 1-\varepsilon \\ \text{uniformly random action over } \mathcal{A} & \text{with probability } \varepsilon \end{cases} \] where \(\varepsilon \in [0,1]\) controls the exploration rate. Often \(\varepsilon\) is decayed over time. Note that the random branch samples uniformly from all actions (including the greedy one), so, when the greedy action is unique, it is selected with total probability \(1 - \varepsilon + \varepsilon / |\mathcal{A}|\).

Softmax Action Selection

A more sophisticated approach uses the Boltzmann (softmax) distribution: \[ P(a_t = a \mid s_t) = \frac{\exp(Q(s_t, a)/\tau)}{\sum_{a'} \exp(Q(s_t, a')/\tau)} \] where \(\tau \gt 0\) is the temperature parameter. Higher temperatures lead to more exploration.

Optimistic Initialization

Initializing Q-values optimistically (higher than realistic values) encourages exploration of all actions early in learning, as the agent will be "disappointed" by actual rewards and try other actions. This technique is most effective in the tabular setting. With neural-network function approximators, the notion of a uniform "optimistic" initialization is harder to enforce, and the trick does not transfer cleanly to deep RL.

The choice of exploration strategy significantly affects learning performance and is often problem-dependent. More advanced methods like UCB (Upper Confidence Bound) and Thompson sampling provide principled approaches to this tradeoff.

Markov Decision Process (MDP)

Before we turn to RL algorithms, this section presents a detailed probabilistic formulation of Markov Decision Processes (MDPs), where both transitions and rewards are modeled as random variables. This perspective extends the classical deterministic view and is particularly useful for analyzing trajectory distributions and gradient-based learning methods used in reinforcement learning.

An agent sequentially interacts with an initially unknown environment to obtain a trajectory or multiple trajectories. A trajectory of length \(T\) (that is, consisting of \(T\) transitions) is defined as: \[ \boldsymbol{\tau} = (s_0, a_0, r_0, s_1, a_1, r_1, s_2, \ldots, a_{T-1}, r_{T-1}, s_T), \] where \(s_t\) is a state, \(a_t\) is an action, and \(r_t\) is a reward.

The objective is to optimize the agent's action-selection policy so as to maximize the expectation \(\mathbb{E}[G_0]\) of the discounted cumulative reward \[ G_0 = \sum_{t = 0}^{T -1} \gamma^t r_t, \] where \(\gamma \in [0, 1]\) is the discount factor. We assume the environment follows a Markov Decision Process (MDP), where the trajectory distribution can be factored into single-step transition and reward models. The process of estimating an optimal policy from trajectories is referred to as learning.

At time \(t = 0\), the initial state is sampled as \(s_0 \sim p_0\). At each step \(t \geq 0\), the agent observes state \(s_t \in \mathcal{S}\), selects action \(a_t \sim \pi(a_t \mid s_t)\), and receives reward \(r_t \sim p_R(r \mid s_t, a_t, s_{t+1})\), where the next state is drawn from \(s_{t+1} \sim p_T(s_{t+1} \mid s_t, a_t)\). The agent's decision-making is governed by a stochastic policy \(\pi(a \mid s)\).

This interaction at each step is called a transition, represented as the tuple: \[ (s_t, a_t, r_t, s_{t+1}), \] where:

• \(a_t \sim \pi(a \mid s_t)\)
• \(s_{t+1} \sim p_T(s_{t+1} \mid s_t, a_t)\)
• \(r_t \sim p_R(r \mid s_t, a_t, s_{t+1})\)

The transition kernel \(p_T(s_{t+1} \mid s_t, a_t)\) depends only on the current state and action, not on prior history. This is the first-order Markov property in its state-action form, and it makes the trajectory distribution factorize cleanly. In continuous time the same idea, sharpened to hold at random stopping times, becomes the strong Markov property of Itô diffusions, developed rigorously in the probability section.

Under policy \(\pi\), the joint distribution of a trajectory \(\boldsymbol{\tau}\) of length \(T\) is given by: \[ p(\boldsymbol{\tau}) = p_0(s_0) \prod_{t = 0}^{T -1} \pi(a_t \mid s_t) \, p_T(s_{t+1} \mid s_t, a_t) \, p_R(r_t \mid s_t, a_t, s_{t+1}). \]

We define the expected reward function from the reward model \(p_R\) as the marginal average immediate reward for taking action \(a\) in state \(s\), integrating over possible next states: \[ R(s, a) = \mathbb{E}_{p_T(s' \mid s, a)} \left[ \mathbb{E}_{p_R(r \mid s, a, s')}[r] \right]. \]

While classical RL literature often starts with a deterministic reward function \(r(s, a)\) as a primitive, our probabilistic formulation derives \(R(s, a)\) by taking the expectation under the stochastic reward kernel \(p_R\). Writing the trajectory distribution out in full is also useful for gradient-based RL methods. The environment factors \(p_0\), \(p_T\), and \(p_R\) do not depend on the policy, which is why only policy terms survive in the policy gradient derived below.

Value Functions and Bellman Equations

Convention. Throughout this section, the subscript on \(\mathbb{E}\) names the distribution being averaged over: \(\mathbb{E}_\pi[\,\cdot\,]\) abbreviates expectation over full trajectories generated by \(\pi\), while \(\mathbb{E}_{\pi(a \mid s)}[\,\cdot\,]\) is expectation over the action variable alone, drawn from \(\pi(\cdot \mid s)\). For the exact results on this page (the Bellman equations, the dynamic-programming analysis, and the policy gradient theorem) we also make three standing assumptions: \(\mathcal{S}\) and \(\mathcal{A}\) are finite, rewards are bounded, and \(\gamma \in [0, 1)\). An episodic task fits this setting by treating its terminal state as absorbing with zero reward, so the return of an episode that ends at time \(T\) is the finite sum in the definition of the return. These assumptions make every value function below well defined and bounded.

Under the standing assumptions the discount factor keeps the return finite even for infinite-horizon problems. It also gives higher weight to short-term rewards, thereby encouraging the agent to achieve goals sooner.

A policy \(\pi_*\) is called an optimal policy if it yields the highest value for every state: \[ \forall s \in \mathcal{S}, \quad V_{\pi_*}(s) \geq V_{\pi}(s), \quad \forall \pi. \]

Although multiple optimal policies may exist, their value functions are the same: \(V_*(s) = V_{\pi_*}(s)\) and \(Q_*(s, a) = Q_{\pi_*}(s, a)\). Moreover, since the action space \(\mathcal{A}\) is finite, the maximum in the Bellman optimality equation (stated immediately below) is attained at every state, so selecting any maximizer \[ \pi_*(s) \in \arg\max_a \left[ R(s, a) + \gamma \, \mathbb{E}_{p_T(s' \mid s, a)} \left[ V_*(s') \right] \right] \] yields a deterministic optimal policy. Indeed, \(V_*\) then solves the Bellman expectation equation of this policy, whose solution is unique by the policy-evaluation analysis below, so the policy's value function is \(V_*\).

We state these equations without proof. The uniqueness part is the contraction argument carried out for value iteration below, and the fact that \(V_*\) and \(Q_*\) satisfy them rests on Bellman's principle of optimality (discussed below), which we also take as given.

An optimal policy can then be derived by: \[ \begin{align*} \pi_*(s) &\in \arg \max_a Q_*(s, a) \\\\ &= \arg \max_a \left[ R(s, a) + \gamma \, \mathbb{E}_{p_T(s' \mid s, a)} \left[ V_*(s') \right] \right]. \end{align*} \] Solving for \(V_*\), \(Q_*\), or \(\pi_*\) is known as policy optimization, while computing \(V_{\pi}\) or \(Q_{\pi}\) for a given policy \(\pi\) is called policy evaluation.

Both Bellman optimality and Bellman expectation equations follow the same recursive structure. The value of a state equals the immediate reward plus the discounted value of successor states. The two families differ only in how the action is chosen. The optimality equations maximize over it, \(\max_a[\,\cdot\,]\), which gives the value of acting optimally. In the expectation equations, the action is averaged over \(\pi\), \(\mathbb{E}_{\pi(a \mid s)}[\,\cdot\,]\), and the result is the value of following the fixed policy \(\pi\).

Dynamic Programming Algorithms for RL

Dynamic programming (DP) is a technique for solving optimization problems by breaking them down into simpler subproblems and storing the results to avoid redundant computations. In the context of reinforcement learning, DP methods solve MDPs when the complete model (transition probabilities and rewards) is known.

The key insight of DP for MDPs is that optimal policies have the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. This is known as Bellman's principle of optimality, which leads to the recursive Bellman equations.

Value Iteration (VI) and Policy Iteration (PI) are the two classical dynamic programming methods for solving MDPs. These algorithms are fundamental to model-based reinforcement learning, where an agent first learns the MDP model from experience and then applies these DP methods to compute optimal policies.

Value Iteration (VI)

Let the initial estimate be \(V_0\). We update it as follows: \[ V_{k+1}(s) = \max_a \left[ R(s, a) + \gamma \sum_{s'} p_T(s' \mid s, a) V_k (s') \right]. \] This is called a Bellman backup. The backup operator is a \(\gamma\)-contraction in the \(\ell_\infty\) norm, and in particular each iterate satisfies \[ \| V_{k+1} - V_* \|_\infty \leq \gamma \| V_k - V_* \|_\infty \] where \( \| V \|_\infty = \max_{s \in \mathcal{S}} |V(s)| \).

Because \( 0 \leq \gamma \lt 1 \) and \(\mathbb{R}^{|\mathcal{S}|}\) is complete under \(\| \cdot \|_\infty\), the Banach Fixed-Point Theorem guarantees that the backup operator has a unique fixed point, which is \(V_*\) by Bellman's optimality equation, and that \(V_k\) converges to it as \(k \to \infty\). The inequality above gives the rate \(\| V_k - V_* \|_\infty \leq \gamma^k \| V_0 - V_* \|_\infty\).

For all possible states \(s\), value iteration approximates \(V_*(s)\) and \(\pi_*(s)\), averaging over all possible next states \(s'\) at each iteration. (Note: If we need the value and policy for only certain starting states, other methods can be used such as real-time dynamic programming). The pseudocode below overwrites \(V(s)\) in place, a form of asynchronous value iteration. This variant also converges to \(V_*\), which we state without proof.

Policy Iteration (PI)

Let \(\mathbf{v} \in \mathbb{R}^{|\mathcal{S}|}\) be the value function vector where \(v_i = V_{\pi}(s_i)\). We define the expected reward vector \(\mathbf{r}\) and the state transition matrix \(\mathbf{T}\) as: \[ \mathbf{r}(s) = \sum_a \pi(a \mid s) R(s, a), \quad \mathbf{T}(s' \mid s) = \sum_a \pi(a \mid s) p_T(s' \mid s, a). \] The Bellman expectation equation for policy evaluation then forms a linear system: \[ \mathbf{v} = \mathbf{r} + \gamma \mathbf{T}\mathbf{v}. \]

Theoretically, the exact solution is \(\mathbf{v} = (\mathbf{I} - \gamma \mathbf{T})^{-1} \mathbf{r}\). Since \(\mathbf{T}\) is a row-stochastic matrix, its maximum absolute row sum is \(1\), which bounds every eigenvalue in modulus, so the spectral radius \(\rho(\gamma \mathbf{T}) = \gamma \rho(\mathbf{T}) \leq \gamma \lt 1\). This guarantees that \(\mathbf{I} - \gamma \mathbf{T}\) is non-singular and that the Neumann series \(\sum_{k=0}^{\infty} (\gamma \mathbf{T})^k = (\mathbf{I} - \gamma \mathbf{T})^{-1}\) converges. In practice, we solve this iteratively using the update \(\mathbf{v}_{k+1} = \mathbf{r} + \gamma \mathbf{T} \mathbf{v}_k\).

Once \(V_{\pi}\) is evaluated, the policy improvement step sets \[ \pi'(s) \in \arg \max_a \left\{ R(s, a) + \gamma \, \mathbb{E}_{p_T(s' \mid s, a)} [V_{\pi}(s')] \right\} \] This guarantees \(V_{\pi'} \geq V_{\pi}\) componentwise.

To see why, write \(\mathbf{r}', \mathbf{T}'\) for the reward vector and transition matrix induced by \(\pi'\) (analogous to \(\mathbf{r}, \mathbf{T}\) for \(\pi\)). By the definition of \(\pi'\) as the greedy improvement, \(\mathbf{r}' + \gamma \mathbf{T}' \mathbf{v} \geq \mathbf{r} + \gamma \mathbf{T} \mathbf{v} = \mathbf{v}\) componentwise, where the equality is the Bellman expectation equation for \(\pi\). Iterating this inequality, using that \(\mathbf{T}'\) has non-negative entries (so it preserves componentwise inequalities), gives \[ \begin{align*} \mathbf{v} &\leq \mathbf{r}' + \gamma \mathbf{T}'\mathbf{v} \\\\ &\leq \mathbf{r}' + \gamma \mathbf{T}'(\mathbf{r}' + \gamma \mathbf{T}'\mathbf{v}) \\\\ &\leq \cdots \leq \sum_{k=0}^{n-1} (\gamma \mathbf{T}')^k \mathbf{r}' + (\gamma \mathbf{T}')^n \mathbf{v}. \end{align*} \] Let \(n \to \infty\). The partial sum converges to \((\mathbf{I} - \gamma \mathbf{T}')^{-1}\mathbf{r}' = \mathbf{v}'\) by the Neumann-series argument above (since \(\rho(\gamma \mathbf{T}') \lt 1\)), and the residual \((\gamma \mathbf{T}')^n \mathbf{v} \to \mathbf{0}\) for the same reason. Therefore \(\mathbf{v} \leq \mathbf{v}'\), that is, \(V_{\pi} \leq V_{\pi'}\) componentwise.

In the policy iteration algorithm, starting from an initial policy, we alternate between the policy evaluation step and the policy improvement step. Assume \(\mathcal{S}\) and \(\mathcal{A}\) are finite. There are at most \(|\mathcal{A}|^{|\mathcal{S}|}\) deterministic policies. Suppose ties in the \(\arg\max\) are broken consistently, as the pseudocode does by keeping the current action whenever it is among the maximizers. Then every iteration either strictly improves the policy or leaves it unchanged, so the algorithm terminates after finitely many iterations. When the policy is unchanged, Bellman optimality holds at every state, so the final policy is optimal. These guarantees assume exact policy evaluation. The pseudocode stops evaluating at the threshold \(\theta\), so they hold only approximately there.

Monte Carlo Control

Having established the theoretical foundations of MDPs and dynamic programming, we now turn to model-free methods that learn directly from experience. We begin with Monte Carlo (MC) control, a fundamental value-based method that estimates value functions by sampling complete episodes and using actual returns. The averaging of sampled returns is an instance of the general Monte Carlo estimator, and, for a fixed policy, its convergence is guaranteed by Monte Carlo consistency (an application of the strong law of large numbers).

Monte Carlo control implements generalized policy iteration (GPI). GPI is a unifying name for any scheme that interleaves policy evaluation and policy improvement at any granularity (also called generalized policy improvement in some texts). At iteration \(k\), with current policy \(\pi_k\), the three steps are:

1. Rollout. Starting from state \(s\), take action \(a\), and sample the rest of the trajectory by following policy \(\pi_k\) until a terminal state is reached.
2. MC Q-estimate. Compute the realized return \(G_0 = \sum_{t=0}^{T-1} \gamma^t r_t\) from this rollout and average it (over many such rollouts) into the running estimate \(Q_k(s, a)\) of \(Q_{\pi_k}(s, a)\). Steps 1 and 2 together perform policy evaluation.
3. Policy improvement. Update the policy greedily with respect to the current Q-estimate, \[ \pi_{k+1}(s) \in \arg \max_{a} Q_k (s, a), \] where \(Q_k\) is the MC estimate of \(Q_{\pi_k}\) accumulated so far.

To keep exploring every action, the rollouts can follow an \(\varepsilon\)-greedy policy built from the current Q-estimate. With a fixed \(\varepsilon\), the method can at best find the best policy among \(\varepsilon\)-greedy ones. Letting \(\varepsilon\) decay to zero while every state-action pair is still visited infinitely often (the GLIE condition discussed with SARSA below) is the standard way to target \(\pi_*\) itself.

Monte Carlo methods provide unbiased estimates of \(Q_\pi\) since they use actual returns. However, MC methods are not efficient for value-based RL because they require unrolling complete trajectories whose returns are sums of random rewards generated by stochastic state transitions, leading to high variance in value estimates. Moreover, MC methods are most natural for episodic tasks (or for continuing tasks via finite-horizon truncation), since they need a complete trajectory to form each update. This makes them unsuitable for step-by-step online updates.

To address these limitations, we now turn to bootstrapping, which updates estimates from other estimates. This sense of the word is distinct from the statistical bootstrap used in other areas of machine learning.

Temporal Difference Learning

Temporal Difference (TD) learning methods address the limitations of Monte Carlo methods through bootstrapping. Each update uses a single transition plus the current estimate of the successor state, rather than waiting for a complete return. In other words, TD methods incrementally reduce the Bellman expectation residual for sampled states by learning from individual transitions rather than complete trajectories.

Theoretical Foundation

The TD target \(r_t + \gamma V(s_{t+1})\) is a single-sample approximation of the right-hand side of the Bellman expectation equation introduced above, \[ V_{\pi}(s) = \mathbb{E}_{\pi(a \mid s)} \left[ R(s, a) + \gamma \, \mathbb{E}_{p_T(s' \mid s, a)} \left[ V_{\pi}(s') \right] \right], \] obtained by replacing the expectations with a single observed transition \((s_t, a_t, r_t, s_{t+1})\) drawn from the agent's actual interaction. The TD update then adjusts the current estimate \(V(s_t)\) toward this target. This establishes TD learning as a method for solving the Bellman equations through successive approximation, without requiring knowledge of transition probabilities.

Tabular TD(0) converges with probability \(1\) to the true value function \(V_{\pi}(s)\) of the policy being followed under appropriate conditions: bounded rewards, a finite state space whose states are all visited infinitely often, and a learning-rate schedule \(\{\alpha_t\}\) satisfying the Robbins-Monro conditions \(\sum_{t=0}^{\infty} \alpha_t = \infty\) and \(\sum_{t=0}^{\infty} \alpha_t^2 \lt \infty\). We state this stochastic-approximation result without proof.

TD(0): One-Step Temporal Difference

The simplest TD method, TD(0), updates value estimates after each single step. Suppose the agent learns the value function \(V_\pi\) for a fixed policy \(\pi\). Given a state transition \((s_t, a_t, r_t, s_{t+1})\) where \(a_t \sim \pi(\cdot \mid s_t)\), we update the estimate \(V(s_t)\) as follows:

n-Step TD Methods

TD methods can be generalized to look ahead multiple steps. The n-step return is defined as: \[ G_{t:t+n} = r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1} + \gamma^n V(s_{t+n}) \] If the episode ends at a time \(T \leq t + n\), the sum stops at \(r_{T-1}\) and the bootstrap term is dropped, so \(G_{t:t+n} = G_t\). The corresponding n-step TD update becomes: \[ V(s_t) \leftarrow V(s_t) + \alpha [G_{t:t+n} - V(s_t)] \]

Varying \(n\) provides a spectrum of methods. The case \(n=1\) recovers TD(0), with target \(G_{t:t+1} = r_t + \gamma V(s_{t+1})\). As \(n\) increases toward the episode length, the method approaches Monte Carlo behavior by using longer actual return sequences.

TD(\(\lambda\)) and \(\lambda\)-returns

Rather than using a fixed n-step lookahead, TD(\(\lambda\)) methods use a weighted average of all n-step returns. The \(\lambda\)-return is defined as: \[ G_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n} \] where \(\lambda \in [0,1]\) controls the weighting between different n-step returns.

The parameter \(\lambda\) creates a different type of interpolation than n-step methods:

• When \(\lambda = 0\): Only the 1-step return is used, reducing to TD(0)
• When \(\lambda = 1\): For episodic tasks, \(G_t^{\lambda} \to G_t\) as \(\lambda \to 1\) by the convention above, and \(G_t^{1}\) is taken to be \(G_t\). This gives Monte Carlo behavior
• For \(0 \lt \lambda \lt 1\): Creates a weighted blend that emphasizes shorter-term returns but includes longer-term effects

Note that TD(\(\lambda\)) with \(\lambda = 1\) achieves Monte Carlo-equivalent behavior through a different mechanism than n-step TD with large \(n\). While n-step methods extend the lookahead horizon, TD(\(\lambda\)) is usually implemented with eligibility traces, a backward-view mechanism not developed on this page. The traces distribute credit backward through time and allow online updates even in continuing tasks.

The \(\lambda\)-return provides a principled way to interpolate between the low variance but biased estimates of TD(0) and the high variance but unbiased estimates of Monte Carlo methods. TD(0) is thus a special case of the more general TD(\(\lambda\)) framework.

Function Approximation

More generally, for function approximation where \(V_\mathbf{w}(s)\) is parameterized by weights \(\mathbf{w}\), the TD(0) update becomes: \[ \mathbf{w} \leftarrow \mathbf{w} + \alpha [ r_t + \gamma V_{\mathbf{w}}(s_{t+1}) - V_{\mathbf{w}}(s_t)]\nabla_{\mathbf{w}}V_{\mathbf{w}}(s_t) \] Note that with function approximation, TD methods may not always converge, unlike the tabular case.

Key Advantages

TD methods offer several key advantages:

• Online learning. Updates occur after each time step, enabling continuous learning without waiting for episode completion.
• Computational efficiency. No need to store or process entire episode returns.
• Lower variance. TD(0) has lower variance due to bootstrapping, though this comes at the cost of introducing bias.
• Applicability to continuing tasks. Can learn in non-episodic environments where episodes never terminate.

TD Control Methods: Q-Learning & SARSA

The previous section used TD learning for policy evaluation (learning \(V_\pi\)). TD control algorithms extend it to the control problem by estimating action-value functions and deriving policies from them.

Both Q-learning and SARSA are temporal difference methods that bootstrap using single-step transitions, but they differ fundamentally in their approach to policy learning. Q-learning learns the optimal Q-function directly (off-policy), while SARSA learns the Q-function of the policy it follows (on-policy).

SARSA (On-Policy TD Control)

The agent follows policy \(\pi\) at every step to select actions, and learns its Q-function from the resulting transitions. Under a transition \((s, a, r, s')\), the TD update rule is:

SARSA is named after the transition tuple \((s, a, r, s', a')\).

Q-Learning (Off-Policy TD Control)

Instead of the sampled next action \(a' \sim \pi(\cdot \mid s')\) in SARSA, Q-learning uses the greedy action in \(s'\):

Key Differences

• Convergence. Q-learning provably converges to the optimal action-value function \(Q_*\) in the tabular case, provided every state-action pair is visited infinitely often and the learning rates satisfy the Robbins-Monro conditions. SARSA, viewed as pure policy evaluation, converges to \(Q_\pi\) for the policy \(\pi\) being followed. When combined with a GLIE (Greedy in the Limit with Infinite Exploration) policy, such as \(\varepsilon\)-greedy with \(\varepsilon\) at each state decaying as \(c/n\), where \(0 \lt c \lt 1\) and \(n\) is the number of visits to that state, SARSA also converges to \(Q_*\) and the optimal policy \(\pi_*\).
• Policy dependence. SARSA accounts for the actual exploration policy in its updates, while Q-learning's target \(\max_b Q(s', b)\) ignores the behavioral policy entirely.
• Behavioral differences. In some environments, SARSA may learn different policies than Q-learning because it considers the exploration policy's actual behavior, while Q-learning optimizes assuming greedy action selection.

Both algorithms require exploration to discover good actions, leading us to the fundamental challenge of balancing exploration and exploitation.

Policy Gradient Methods

Unlike value-based methods that learn value functions and derive policies implicitly, policy-based methods directly parameterize and optimize policies without necessarily learning value functions. These methods address fundamental limitations of value-based approaches, particularly in continuous action spaces and when stochastic policies are desired.

Our objective is the expected return of a policy: \[ \begin{align*} J(\pi) &= \mathbb{E}_{p_0(s_0)}[V_{\pi}(s_0)] \\\\ &= \mathbb{E}_{p_0(s_0)\pi(a_0 \mid s_0)}[Q_{\pi}(s_0, a_0)]. \end{align*} \]

Let \(\pi_{\boldsymbol{\theta}}\) be parameterized by \(\boldsymbol{\theta}\). Differentiating the objective with respect to \(\boldsymbol{\theta}\) gives \[ \begin{align*} \nabla_{\boldsymbol{\theta}} J(\pi_{\boldsymbol{\theta}}) &= \mathbb{E}_{p_0(s_0)} \left[\nabla_{\boldsymbol{\theta}} \left(\sum_{a_0}\pi_{\boldsymbol{\theta}}(a_0 \mid s_0)Q_{\pi_{\boldsymbol{\theta}}}(s_0, a_0) \right) \right] \\\\ &= \mathbb{E}_{p_0(s_0)} \left[\sum_{a_0} \nabla_{\boldsymbol{\theta}} \pi_{\boldsymbol{\theta}}(a_0 \mid s_0)Q_{\pi_{\boldsymbol{\theta}}}(s_0, a_0) \right] + \mathbb{E}_{p_0(s_0)\pi_{\boldsymbol{\theta}}(a_0 \mid s_0)} [\nabla_{\boldsymbol{\theta}}Q_{\pi_{\boldsymbol{\theta}}}(s_0, a_0)]. \end{align*} \] Here, since \(R(s_0, a_0)\) does not depend on \(\boldsymbol{\theta}\), we have \[ \begin{align*} \nabla_{\boldsymbol{\theta}}Q_{\pi_{\boldsymbol{\theta}}}(s_0, a_0) &= \nabla_{\boldsymbol{\theta}}\left[R(s_0, a_0) + \gamma \mathbb{E}_{p_T(s_1 \mid s_0, a_0)} [V_{\pi_{\boldsymbol{\theta}}}(s_1)]\right] \\\\ &= \gamma \nabla_{\boldsymbol{\theta}} \mathbb{E}_{p_T(s_1 \mid s_0, a_0)} [V_{\pi_{\boldsymbol{\theta}}}(s_1)]. \end{align*} \]

We sketch the remaining step. Substituting this back, we unroll the recursion across all timesteps. Each level of recursion contributes a factor of \(\gamma\) and shifts the state distribution one step forward under \(\pi_{\boldsymbol{\theta}}\). Collapsing the resulting infinite sum with the discounted state-visitation distribution \(p_{\pi_{\boldsymbol{\theta}}}^\infty\), we obtain the policy gradient theorem:

The third equality uses the log-derivative trick \(\nabla_{\boldsymbol{\theta}} \pi_{\boldsymbol{\theta}}(a \mid s) = \pi_{\boldsymbol{\theta}}(a \mid s) \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}(a \mid s)\), converting the gradient of a probability into an expectation under that probability. The quantity \(\nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}(a \mid s)\) is precisely the conditional score function of the policy distribution, which makes the policy gradient an instance of score-function estimation. The theorem is stated for finite \(\mathcal{A}\), where the inner sums range over actions. For a continuous action space the sums become integrals against a policy density, and the same identity holds under integrability and differentiability conditions that we do not develop here.

To reduce the high variance of policy-gradient estimates, we can subtract a state-dependent baseline \(b(s)\) from \(Q_{\pi_{\boldsymbol{\theta}}}(s, a)\) inside the expectation. A key invariance property is that this subtraction does not change the gradient in expectation, because \(\mathbb{E}_{a \sim \pi_{\boldsymbol{\theta}}(\cdot \mid s)}[\nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}(a \mid s)] = \mathbf{0}\) for any \(s\), so the baseline term integrates to zero. The policy gradient theorem then becomes: \[ \nabla_{\boldsymbol{\theta}}J(\pi_{\boldsymbol{\theta}}) = \frac{1}{1 -\gamma} \mathbb{E}_{p_{\pi_{\boldsymbol{\theta}}}^{\infty}(s) \pi_{\boldsymbol{\theta}}(a \mid s)} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}(a \mid s) (Q_{\pi_{\boldsymbol{\theta}}}(s, a) - b(s)) \right]. \]

A common choice is \(b(s) = V_{\pi_{\boldsymbol{\theta}}}(s)\), which makes the multiplier the advantage function \(A_{\pi_{\boldsymbol{\theta}}}(s, a) = Q_{\pi_{\boldsymbol{\theta}}}(s, a) - V_{\pi_{\boldsymbol{\theta}}}(s)\). Intuitively, this re-centers each action's value relative to the policy's average performance at that state. In practice this choice often reduces variance substantially, although \(V_{\pi_{\boldsymbol{\theta}}}\) is not in general the variance-minimizing baseline.

REINFORCE is the fundamental policy gradient algorithm that uses Monte Carlo estimation: \[ \begin{align*} \nabla_{\boldsymbol{\theta}} J(\pi_{\boldsymbol{\theta}}) &= \frac{1}{1 -\gamma} \mathbb{E}_{p_{\pi_{\boldsymbol{\theta}}}^{\infty}(s) \pi_{\boldsymbol{\theta}}(a \mid s)} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}(a \mid s) Q_{\pi_{\boldsymbol{\theta}}}(s, a) \right]\\\\ &\approx \sum_{t=0}^{T-1} \gamma^t G_t \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}(a_t \mid s_t) \end{align*} \] where \(G_t\) is the return from time \(t\): \[ G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots + \gamma^{T-t-1} r_{T-1}. \] The factor \(\gamma^t\) comes from the discount on the state at time \(t\) in \(p_{\pi_{\boldsymbol{\theta}}}^\infty\). Here, using a baseline in the gradient estimate, we obtain the REINFORCE update rule: \[ \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \alpha \sum_{t = 0}^{T -1} \gamma^t (G_t - b(s_t)) \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (a_t \mid s_t). \]

Actor-Critic Methods

Actor-critic methods are hybrid algorithms that combine both policy-based and value-based approaches to address the high variance problem of pure policy gradient methods like REINFORCE. These methods maintain two separate function approximators that work together:

• Actor \(\pi_{\boldsymbol{\theta}}(a \mid s)\): A parameterized policy that selects actions, where \(\boldsymbol{\theta}\) are the policy parameters.
• Critic \(V_{\mathbf{w}}(s)\): A parameterized state-value function that evaluates states, where \(\mathbf{w}\) are the value function parameters.

The actor updates the policy parameters \(\boldsymbol{\theta}\) using gradients weighted by the advantage estimates provided by the critic, while the critic updates the value function parameters \(\mathbf{w}\) to more accurately estimate expected returns through temporal difference learning.

Consider the use of the one-step TD(0) method to estimate the return in the episodic case. Specifically, we replace the Monte Carlo return \(G_t\) (used in REINFORCE) with the 1-step TD target \[ G_{t:t+1} = r_t + \gamma V_{\mathbf{w}} (s_{t+1}), \] and use \(V_{\mathbf{w}}(s_t)\) as the baseline. The REINFORCE update from the previous section then becomes: \[ \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \alpha \sum_{t=0}^{T-1} \gamma^t (G_{t:t+1} - V_{\mathbf{w}}(s_t))\nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}(a_t \mid s_t). \]

Here, the increment \(r_t + \gamma V_{\mathbf{w}}(s_{t+1}) - V_{\mathbf{w}}(s_t)\) is a single-sample approximation to the advantage function \[ A_{\pi_{\boldsymbol{\theta}}}(s_t, a_t) = Q_{\pi_{\boldsymbol{\theta}}}(s_t, a_t) - V_{\pi_{\boldsymbol{\theta}}}(s_t), \] and its conditional expectation given \((s_t, a_t)\) equals this advantage when \(V_{\mathbf{w}} = V_{\pi_{\boldsymbol{\theta}}}\). This method is therefore called the advantage actor-critic (or A2C).

Note that the n-step advantage estimate can be expressed as: \[ A_{\pi_{\boldsymbol{\theta}}}^{(n)}(s_t, a_t) = G_{t:t+n} - V_{\mathbf{w}}(s_t) \] where \[ G_{t:t+n} = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots + \gamma^{n-1} r_{t+n-1} + \gamma^n V_{\mathbf{w}}(s_{t+n}). \] We can control the bias-variance tradeoff by adjusting \(n\).

Actor-critic methods have three main advantages:

• Reduced variance. Lower variance than REINFORCE, thanks to the value-function baseline.
• Sample efficiency. More efficient learning through bootstrapping compared to Monte Carlo methods.
• Broad applicability. Can handle both discrete and continuous action spaces with online learning capability.

Among the many actor-critic methods developed in the deep reinforcement learning literature, Proximal Policy Optimization (PPO) deserves special mention. PPO clips the probability ratio between the new and old policies in its surrogate objective, which discourages updates that move far from the old policy. This cheap stand-in for the trust region of TRPO substantially improves training stability while remaining simple to implement. PPO became a standard baseline in continuous-control benchmarks and was the reinforcement-learning algorithm used in the original RLHF pipelines for large language models.