Mar 2026

This post summarizes the basics of reinforcement learning (RL) from David Silver's RL course. It mainly covers the RL modeling, Q-learning, policy gradient, bandits (exploration and exploitation), and advanced RL methods (model-based RL, and inverse RL). For the application of RL in LLM training, please refer to this post.

• RL Basis
• Dynamic Programming
• Q Learning
• Policy Gradient Methods
• Bandits
• Model-based RL
• Offline RL
• Inverse RL

RL Agents and Environment

Reinforcement learning addresses sequential decision-making problems arising from interactions between an agent and its environment. Here, an agent refers to an autonomous system capable of understanding the state of its environment and taking different actions. The environment is the setting where the agent performs its tasks. For a self-driving car, the agent is the car itself, while the environment includes the road, traffic, and weather conditions. One task could be to navigate from location A to location B safely and efficiently. As shown in the figure, an RL system has the following quantitative components:

• Environment state \(s_t \in \mathcal{S}\): represents the full information about the environment and the agent itself. It can be either fully observable or partially observable to the agent. It is typically represented as a vector \(s_t \in \mathbb{R}^q\).
• Action \(a_t\): action taken by the agent at time \(t\). It is also represented as a vector \(a_t \in \mathbb{R}^p\), where each element is an action.
• Reward \(r_{t+1}\): scalar feedback given by the environment after taking action \(a_t\) in state \(s_t\), measuring the goodness of the action.

At every time step \(t\), the agent observes the current state \(s_t\) from the environment, selects an action \(a_t\) based on its policy \(\pi\), and receives a reward \(r_{t+1}\) along with the next state \(s_{t+1}\) from the environment. The goal of the agent is to learn a policy that maximizes the cumulative reward over time. The RL process is formally modeled as a Markov Decision Process (MDP).

MDP and Bellman Equations

An MDP is defined as \( \langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle\).

• \(\mathcal{S}\): state space, \(s_t \in \mathcal{S}\)
• \(\mathcal{A}\): action space, \(a_t \in \mathcal{A}\)
• \(\mathcal{T}: P(s' \mid s,a)= P(s_{t+1} = s' \mid s_t = s, a_t = a)\): state transition function, determining the next state given the current state and action. The state transition function is typically unknown for most problems. There is research on estimating the state transition function. RL with a known or learned/estimated state transition function is referred to as model-based RL.
• \(R(s,a)\): reward function, determining the reward of the agent's current action.
• \(\gamma \in [0,1)\): discount factor, applying decay to the rewards of future steps.

Under this model, the agent's policy is defined as \(\pi(a\mid s) = P(a_t = a \mid s_t = s)\): mapping from states to actions. The objective of the agent is to find an optimal policy \(\pi^*\) that maximizes the expected cumulative discounted reward. In the following we introduce two ways of measuring the cumulative reward and their relationships (Bellman equations).

Value functions

Bellman Equations express the recursive relationship between value functions, connecting the current state value to future states.

There are also Bellman Optimality Equations for the optimal value functions \(V^{*}(s)\) and \(Q^{*}(s,a)\), which replace the expectation over the policy with a maximization over actions, i.e.,

Maximum Entropy RL and Soft Bellman Equations

Maximum entropy RL modifies the standard RL objective by adding an entropy regularization term. This encourages exploration by preventing the policy from becoming too deterministic or collapsing. The agent aims to maximize not only the expected return but also the entropy of its policy, leading to more robust and exploratory behavior. Under maximum entropy RL, the value functions and Bellman equations are adjusted accordingly.

Soft Value Functions

Soft Bellman Equations extend the standard Bellman equations by incorporating the entropy regularization term.

The temperature parameter \(\alpha\) controls the trade-off between exploitation and exploration: when \(\alpha \to 0\), the soft policy approaches the deterministic optimal policy; when \(\alpha\) is large, the policy becomes more uniform and exploratory.

Dynamic Programming (DP) methods solve Markov Decision Processes (MDPs) under the assumption that the environment’s dynamics are fully known, i.e., \( \langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle \). DP forms a foundational pillar of Reinforcement Learning, providing the theoretical basis for many later algorithms. DP focuses on two core problems:
  • Prediction: computing the value function of a given policy in order to quantify its expected long-term return.
  • Control: searching for an optimal policy, along with its corresponding optimal value function, using only the known model of the environment.

Dynamic Programming methods can be categorized as synchronous or asynchronous based on how value function updates are performed across the state space. In synchronous DP, all states are updated together in each iteration using the value estimates from the previous iteration, resulting in a sequence of full sweeps over the state space. In contrast, asynchronous DP updates states individually or in small subsets, immediately incorporating newly computed values without waiting for a complete sweep. Both approaches rely on the same Bellman equations and converge under standard assumptions, but they differ in how updates are scheduled and in their practical computational efficiency.

Synchronous Dynamic Programming

The following methods are the fundamental building blocks of synchronous dynamic programming, ranging from evaluating a fixed policy to iteratively improving it until the optimal policy is reached.

• Policy evaluation: Given a fixed policy, repeatedly apply the Bellman expectation equation to compute the corresponding value function \(V^\pi\). This requires full sweeps over the state space and converges for finite MDPs.
• Policy improvement: Given a value function \(V^\pi\) or action-value function \(Q^\pi\), construct a new policy by greedily selecting actions that maximize expected return.
• Policy iteration: Alternates between policy evaluation and policy improvement. Each iteration produces a strictly better policy, and the process converges to the optimal policy in a finite number of steps.
• Value iteration: Applies the Bellman optimality update directly, effectively combining policy evaluation and improvement into a single update. The policy is obtained implicitly by acting greedily with respect to the converged value function.

Comparison of DP Methods

Asynchronous Dynamic Programming

Synchronous DP methods update all states in each iteration, which can be computationally expensive for large state spaces. Asynchronous DP methods selectively update states, improving computational efficiency while maintaining convergence guarantees. The key insight is that not all states need to be updated with equal frequency.

In-place Dynamic Programming

• Updates use the most recent values immediately, rather than waiting for a complete sweep
• Instead of maintaining two value arrays \(V_k\) and \(V_{k+1}\), use a single array updated in-place
• Order of state updates can affect convergence speed

Prioritized Sweeping

• Maintains a priority queue of states, where each state is ranked by the magnitude of its Bellman error.
• The Bellman error for a state \(s\) is defined as \[ \bigl|\max_a \sum_{s'} P(s' \mid s,a)\,[R(s,a) + \gamma V(s')] - V(s)\bigr|, \] measuring how inconsistent the current value estimate is with the Bellman optimality equation.
• States with the largest Bellman errors are updated first, allowing value changes to propagate efficiently.
• When a state’s value changes significantly, its predecessor states are inserted into the priority queue.
• This approach is particularly effective when value changes are localized to specific regions of the state space.

Real-time Dynamic Programming

• Updates only states that are visited by the agent during actual or simulated experience
• Focuses computational resources on states that are relevant to the current policy or trajectory
• Can be combined with trajectory sampling
• Guarantees convergence for states that are visited infinitely often

Asynchronous dynamic programming methods can be viewed as an important conceptual precursor to modern reinforcement learning. By updating value estimates incrementally, selectively, and often based on trajectories rather than full state sweeps, they introduce many of the computational ideas later adopted by model-free RL algorithms that learn from sampled experience.

Q-learning refers to methods that learn the action-value function \(Q(s,a)\) using a parametric function, most commonly a neural network, and then use an \(\epsilon\)-greedy policy for action selection. Below, we first introduce different ways to estimate value functions and then discuss \(\epsilon\)-greedy for control. We work in the model-free setting, meaning the agent does not assume or learn an explicit model of the environment’s transition dynamics or reward function.

Key terms: Skim these definitions before diving into value estimation so the vocabulary feels familiar.

• Return: total discounted reward from time \(t\) onward, \(G_t = \sum_{k=t}^T \gamma^{k-t} r_k\); its expectations are \(V^\pi(s)\) and \(Q^\pi(s,a)\) for states and state–action pairs.
• TD target: one-step lookahead \(r_t + \gamma\,\hat V(s_{t+1})\) that bootstraps off the current estimate \(\hat V\) instead of waiting for the full return.
• Bootstrapping: reusing a learned estimate such as \(\hat V(s)\) or \(\hat Q(s,a)\) in place of sampled future rewards.
• n-step target: accumulate \(n\) rewards then bootstrap, \(\sum_{k=0}^{n-1} \gamma^k r_{t+k} + \gamma^n \hat V(s_{t+n})\), trading variance for bias.
• TD(\(\lambda\)): weighted blend of all \(n\)-step targets, smoothly interpolating MC and TD behavior.
• Baseline: reference value (often \(V(s_t)\)) subtracted from returns/advantages to cut variance without changing the expectation.
• Advantage: how much better an action is than the baseline at a state, \(A_t = Q(s_t,a_t) - V(s_t)\).

Value Estimation

We start with value estimation given that the agent has no access to the environment’s dynamics or reward function beyond sampled experience, and therefore cannot reason directly about the long-term consequences of actions. Value estimation aims to predict long-term reward from a given state (or state–action pair), and different methods mainly differ in how they approximate this expectation.

There are three canonical value estimation strategies, which can be viewed along a bias–variance spectrum:

1. Monte Carlo (MC): Estimates value by waiting until an episode terminates and using the realized return. MC methods are unbiased, but can be high variance since they depend on complete future trajectories.
2. Temporal-Difference (TD): Updates value estimates after a single step by bootstrapping from the current estimate of the next state. TD methods typically have lower variance, but can be biased due to relying on the next-state value approximation.
3. TD(λ) / n-step methods: Interpolate between Monte Carlo and TD by using multi-step returns. These methods smoothly trade off bias and variance, blending full-trajectory returns with bootstrapped estimates.

In deep RL, we approximate the value function with a neural network and train it to match chosen targets (MC, n-step, TD(0), or TD(\(\lambda\))). The target you choose sets the bias–variance trade‑off. We will reuse these estimators later inside actor–critic and policy‑gradient methods.

Non-parametric control

So far we focused on value estimation (learning how good states or actions are). Control methods decide which action to actually take given those estimates. Here “non‑parametric” just means we use simple rules and tables, including \(\varepsilon\)-greedy, SARSA, or tabular Q‑learning, rather than using a learned neural policy network. These methods are the basic building blocks for exploration and policy improvement before we move on to deep, parametric control.

ε-Greedy

• With probability \(1-\varepsilon\): act greedily, i.e., pick the action with the highest current value estimate, \(\arg\max_a Q(s,a)\).
• With probability \(\varepsilon\): ignore the values and pick a random action, so the agent keeps exploring parts of the state space it is unsure about.
• In practice, start with a larger \(\varepsilon\) (more random exploration) and slowly decay it toward a small value, so the agent explores a lot early on and then exploits its learned value estimates later.

On-Policy vs Off-Policy Learning

Reinforcement learning algorithms differ in whether they learn only from the same policy they are currently using to act (on‑policy), or whether they can also learn from data generated by a different policy or a fixed dataset (off‑policy).

On-Policy Learning: An RL algorithm is on-policy if it learns the value of the policy that is currently being used to generate data. In other words, the agent runs its current (exploratory) policy to collect trajectories, then directly uses those trajectories to evaluate and improve that same policy.

• The agent must follow (or closely follow) the policy it is trying to learn.
• Exploration (e.g., \(\varepsilon\)-greedy, softmax) is part of the policy itself.
• It cannot freely learn from arbitrary experience unless the data comes from the same policy.

• SARSA (On-Policy Control):

  SARSA is an on-policy method for learning the action-value function \(Q(s,a)\). The name comes from the five variables used in each update step: \((S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})\).

  $$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \Big( R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \Big).$$
  • What it learns: \(Q(s,a)\) estimates “how good is it to take action \(a\) in state \(s\) if I keep following my current (typically \(\varepsilon\)-greedy) policy afterward?”
  • Target: the term \(R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})\) says “today’s reward plus the discounted value of what I actually plan to do next.”
  • On‑policy part: the next action \(A_{t+1}\) is sampled from the current behavior policy, so the update is tied to what the agent really did, not to an idealized greedy action.
  • Update pattern:
    1. Observe a transition \((S_t, A_t, R_{t+1}, S_{t+1})\) from interacting with the environment.
    2. Choose the next action \(A_{t+1}\) using your current (typically \(\varepsilon\)-greedy) policy.
    3. Compute the TD error: \(\delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)\).
    4. Update the Q-value: \(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\,\delta_t\).

Off-Policy Learning: An algorithm is off-policy if it learns the value of a target policy (often greedy) while using a different behavior policy to generate experience.

• The behavior policy can be more exploratory than the target policy.
• Enables learning from arbitrary data, e.g., replay buffers or demonstrations.

• Q-learning (Off-Policy Control) Q-learning updates the action-value function using the maximum over next-state actions, regardless of which action the behavior policy actually took:

  $$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \Big( R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t) \Big).$$

  This makes Q‑learning off‑policy because the update uses the optimal greedy action, not necessarily the action selected by the behavior policy.

Overview

Policy gradient methods directly optimize a parameterized policy \(\pi_\theta(a|s)\) rather than conducting non-parametric control. This approach offers several advantages:

• Continuous action spaces: Policy gradient naturally handles continuous actions without discretization
• Stochastic and continuous policies: Can learn stochastic policies following various distributions, such as Gaussian or Categorical
• Policy structure: Can incorporate domain knowledge through policy architecture design, e.g., using different types of neural networks

Learning Objective

The goal is to find parameters \(\theta\) that maximize the expected cumulative (long-term) reward:

where \(\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots)\) is a trajectory.

Policy Gradient

where \(A_t^{\pi_\theta}\) can take several forms (all yielding unbiased gradient estimates with different variance properties):

• \(A_t^{\pi_\theta} = G_t = \sum_{k=t}^{T} \gamma^{k-t} r_k\): Total return from time \(t\) (REINFORCE)
• \(A_t^{\pi_\theta} = G_t - V^{\pi_\theta}(s_t)\): Return with learned baseline (reduces variance)
• \(A_t^{\pi_\theta} = Q^{\pi_\theta}(s_t, a_t)\): Action-value function estimate
• \(A_t^{\pi_\theta} = A^{\pi_\theta}(s_t, a_t) = Q^{\pi_\theta}(s_t, a_t) - V^{\pi_\theta}(s_t)\): Advantage function (PPO, A2C)

Derivation of Policy Gradient

Actor-Critic Methods

Actor-Critic methods combine policy gradient (actor) with learned value functions (critic). The critic reduces variance by providing a learned baseline or advantage estimate, while the actor updates the policy using the critic's feedback.

Basic Actor-Critic Architecture

• Actor: Policy network \(\pi_\theta(a|s)\) with parameters \(\theta\)
• Critic: Value network \(V_w(s)\) (or \(Q_w(s,a)\)) with parameters \(w\)

A2C (Advantage Actor-Critic)

A2C uses the advantage function estimated via GAE (Generalized Advantage Estimation) for lower-variance updates (see above for the details of GAE).

A3C (Asynchronous Advantage Actor-Critic)

A3C runs multiple actor-learners in parallel, each interacting with its own copy of the environment. Workers asynchronously update shared global parameters, providing decorrelated updates and natural exploration through policy diversity. This improves the training speed and yields larger rollouts.

Trust Region Policy Optimization (TRPO)

TRPO enables monotonic improvement of the policy throughout training to improve learning stability and reduce variance.

TRPO Objective

TRPO maximizes this surrogate objective subject to a KL divergence constraint. The TRPO paper has two major parts: 1) deriving the objective function that ensures monotonicity; 2) applying a series of approximations to make the optimization tractable (mainly replacing the max KL constraint with an average KL constraint).

The constraint ensures the new policy stays close to the old policy, preventing catastrophic updates. TRPO uses conjugate gradient and line search to approximately solve this constrained optimization problem.

Derivation of Monotonic Improvement

The expected return \(\eta\) of a new policy \(\tilde{\pi}\) can be expressed in terms of the advantage over the old policy \(\pi\):

Define \(\rho_{\tilde{\pi}}(s) = \sum_{t=0}^{\infty} \gamma^t P(s_t = s \mid \tilde{\pi})\) as the (unnormalized) discounted state visitation frequency under \(\tilde{\pi}\). Then the per-time-step expectation can be rewritten as a sum over states:

The above requires sampling from \(\tilde{\pi}\), which is unavailable. Define a local approximation \(L_\pi\) using states from \(\pi\):

Note that \(L_\pi(\pi) = \eta(\pi)\) and \(\nabla_\theta L_\pi(\pi_\theta)|_{\theta=\theta_{old}} = \nabla_\theta \eta(\pi_\theta)|_{\theta=\theta_{old}}\) (first-order match).

Kakade & Langford (2002) showed that the difference between \(\eta(\tilde{\pi})\) and \(L_\pi(\tilde{\pi})\) can be bounded:

Define \(M_\pi(\tilde{\pi}) = L_\pi(\tilde{\pi}) - C \cdot D_{KL}^{\max}(\pi, \tilde{\pi})\). Then:

Thus, any policy \(\tilde{\pi}\) that improves \(M_\pi\) is guaranteed to improve \(\eta\). This yields a monotonically improving sequence: \(\eta(\pi_0) \leq \eta(\pi_1) \leq \eta(\pi_2) \leq \cdots\)

Proximal Policy Optimization (PPO)

PPO simplifies TRPO by replacing the hard KL constraint with a clipped surrogate objective. This achieves similar stability guarantees while being much simpler to implement and tune.

PPO-Clip Objective

Let \(r_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}\) be the probability ratio. The clipped objective is:

where \(\epsilon\) is typically 0.1 or 0.2. The clipping works as follows:

• When \(A_t > 0\) (good action): clip prevents \(r_t\) from exceeding \(1+\epsilon\), limiting how much we increase the action's probability
• When \(A_t < 0\) (bad action): clip prevents \(r_t\) from going below \(1-\epsilon\), limiting how much we decrease the action's probability

Full PPO Loss

The complete PPO objective typically includes value function and entropy terms:

where \(L^{VF}\) is the value function MSE loss and \(S\) is an entropy bonus for exploration.

Overview

The multi-armed bandit (MAB) problem is a fundamental framework for studying the exploration-exploitation trade-off. The name comes from imagining a gambler facing multiple slot machines ("one-armed bandits"), each with unknown reward distributions. The goal is to maximize cumulative reward by learning which arms are best while not spending too much time on suboptimal arms.

Problem Formulation

A stochastic \(K\)-armed bandit is defined by:

• \(K\) actions (arms): \(\mathcal{A} = \{1, 2, \ldots, K\}\)
• Each arm \(a\) has an unknown reward distribution \(P_a\) with mean \(\mu_a\)
• At each round \(t\), the agent selects an arm \(a_t\) and receives reward \(r_t \sim P_{a_t}\)
• Optimal arm: \(a^* = \arg\max_a \mu_a\) with optimal mean \(\mu^* = \max_a \mu_a\)

The key difference between Bandits and RL is that Bandits can be viewed as a special case of RL with a single state, or equivalently, an MDP where all states are terminal.

Regret Analysis

The standard measure of bandit algorithm performance is regret: the difference between the reward of always playing the optimal arm and the reward actually obtained.

Key regret bounds:

• Lower bound (Lai-Robbins): Any consistent algorithm has \(\mathbb{E}[R_T] = \Omega(\log T)\)
• UCB achieves: \(\mathbb{E}[R_T] = O\left(\sum_{a:\Delta_a > 0} \frac{\log T}{\Delta_a}\right)\) — logarithmic and thus near-optimal
• Worst-case: \(\mathbb{E}[R_T] = O(\sqrt{KT \log T})\) when gaps are unknown

Key Methods

1. ε-Greedy

The simplest exploration strategy: exploit most of the time, explore randomly with small probability.

• With probability \(1-\varepsilon\): choose \(a_t = \arg\max_a \hat{\mu}_a\) (greedy)
• With probability \(\varepsilon\): choose uniformly random arm

Properties:

• Simple to implement and understand
• Linear regret \(O(\varepsilon T)\) with fixed \(\varepsilon\)
• Decaying \(\varepsilon_t = \min(1, K/(d^2 t))\) can achieve \(O(\log T)\) regret
• Does not use uncertainty information — explores uniformly over all arms

2. Upper Confidence Bound (UCB)

The principle of "optimism in the face of uncertainty": construct upper confidence bounds on each arm's mean and select the arm with the highest UCB. This naturally balances exploitation (high estimated mean) with exploration (high uncertainty).

The confidence bonus \(\sqrt{\frac{2 \ln t}{N_t(a)}}\) comes from Hoeffding's inequality, ensuring the true mean lies below the UCB with high probability.

3. Thompson Sampling

A Bayesian approach: maintain a posterior distribution over each arm's mean, sample from the posterior, and act greedily with respect to the samples. This implements "probability matching" — arms are selected proportionally to their probability of being optimal.

For Bernoulli bandits with Beta prior:

Properties:

• Empirically often outperforms UCB
• Achieves \(O(\sqrt{KT \log T})\) Bayesian regret
• Naturally handles prior knowledge
• Can be extended to complex models (linear, neural network posteriors)

Advanced Topics

Contextual Bandits

Contextual bandits extend the basic setting by introducing context (features) that inform the reward distribution. At each round, the agent observes a context \(x_t\), selects action \(a_t\), and receives reward \(r_t \sim P(r | x_t, a_t)\). For linear contextual bandits where \(\mathbb{E}[r_t | x_t, a_t] = x_t^\top \theta_{a_t}\), the LinUCB algorithm selects: \(a_t = \arg\max_a [ x_t^\top \hat{\theta}_a + \alpha \sqrt{x_t^\top A_a^{-1} x_t} ]\). Applications include recommendation systems, clinical trials, ad placement, and LLM serving.

Bayesian Optimization

When arm rewards are correlated (e.g., nearby hyperparameters have similar performance), Bayesian optimization uses Gaussian Processes to model the reward function and guide exploration efficiently.

Adversarial Bandits

When rewards are chosen by an adversary rather than drawn from fixed distributions, algorithms like EXP3 (Exponential-weight algorithm for Exploration and Exploitation) achieve \(O(\sqrt{KT \log K})\) regret against any adversary.

Overview

Model-based RL learns a model of the environment dynamics and uses it for planning, in contrast to model-free methods that learn policies or value functions directly from experience. The key idea is to learn \(\hat{P}(s'|s,a)\) (transition model) and \(\hat{R}(s,a)\) (reward model), then use these to simulate trajectories for policy optimization.

Core Framework

Key Challenges

• Model error compounding: Small prediction errors accumulate over long rollouts
• Distribution shift: Model trained on old policy data may be inaccurate for new policies
• Computational cost: Planning through a learned model can be expensive

Overview

Offline RL (also called batch RL) learns policies entirely from a fixed dataset of previously collected experience, without any online interaction with the environment. The difference between offline RL and behavior cloning (SFT) is that offline RL aims to learn an optimal policy that maximizes expected return, while behavior cloning simply mimics the behavior policy that generated the data.

Problem Setting

Key Challenge: Distribution Shift

The fundamental challenge is distribution shift between the learned policy \(\pi\) and the behavior policy \(\pi_\beta\). When \(\pi\) selects actions outside the support of \(\mathcal{D}\), the Q-function has no data to learn from and can be arbitrarily wrong. This leads to overestimation of out-of-distribution actions and policy degradation.

Classic Offline RL Methods

• BCQ (Batch-Constrained Q-learning): Only consider actions similar to those in the dataset; uses a generative model to constrain action selection
• CQL (Conservative Q-Learning): Add a regularizer that penalizes Q-values for out-of-distribution actions:
  $$\min_Q \alpha \mathbb{E}_{s \sim \mathcal{D}} \left[ \log \sum_a \exp(Q(s,a)) - \mathbb{E}_{a \sim \pi_\beta}[Q(s,a)] \right] + \text{Bellman error}$$
• IQL (Implicit Q-Learning): Avoid querying OOD actions by learning V and Q separately using expectile regression
• Decision Transformer: Frame RL as sequence modeling; condition on desired return to generate actions

Overview

Inverse Reinforcement Learning (IRL) is a special line of approaches in offline RL. It explicitly learns the reward function together with the policy. This is useful when rewards are difficult to specify but expert demonstrations are available. The learned reward can be used for continued training.

Problem Formulation

Challenges

• Non-identifiability and ambiguity: many reward functions can explain the same behavior (e.g., \(R \equiv 0\) always works); expert behavior may be optimal under multiple reward functions.
• Computational cost: classic IRL requires solving an RL problem in the inner loop.

Maximum Entropy IRL

Maximum Entropy IRL (Ziebart et al., 2008) resolves the ambiguity by assuming the expert follows a stochastic policy that maximizes entropy while favoring high-reward trajectories. This leads to the Boltzmann distribution over trajectories:

Let the reward be parameterized as \(R_\theta(s,a)\) (any differentiable form). The objective is to maximize the likelihood of expert demonstrations:

The gradient compares reward sensitivities under expert trajectories and model trajectories, which involves solving an RL problem:

GAIL: Generative Adversarial Imitation Learning

GAIL (Ho & Ermon, 2016) reframes imitation learning as a GAN problem, bypassing explicit reward recovery. Instead of the two-step process (IRL → RL), GAIL directly learns a policy that matches expert behavior.

Key Insight: Occupancy Measure Matching

Define the occupancy measure as the distribution of state-action pairs visited by a policy:

GAIL matches the occupancy measure of the learned policy to that of the expert, using a discriminator to measure the difference.

GAIL Objective

• Generator (Policy \(\pi\)): The learned policy that generates state-action trajectories \((s,a)\).
• Expert policy \(\pi_E\): The demonstrator policy that generated expert trajectories; expectations \(\mathbb{E}_{\pi_E}[\cdot]\) are over expert state-action samples.
• Discriminator \(D(s,a)\): A binary classifier outputting the probability that \((s,a)\) came from the expert distribution (high for expert-like pairs, low for policy-generated pairs).
• Entropy bonus \(H(\pi)\): Encourages exploration and prevents mode collapse

Training Procedure

1. Sample trajectories from current policy \(\pi_\theta\)
2. Update discriminator \(D_w\) to classify expert vs. policy samples
3. Update policy using \(-\log(1 - D_w(s,a))\) as reward signal (via policy gradient)
4. Repeat until convergence

Advantages over Classical IRL

• Avoids explicitly solving RL in inner loop

  In classical IRL, each reward update often requires running a separate RL optimization to compute the policy induced by that reward (the "inner loop"), which is computationally expensive. In GAIL, the discriminator directly provides a learning signal, so policy and discriminator are updated jointly without repeatedly solving a full RL problem from scratch.

• Scales to high-dimensional continuous control tasks

  GAIL uses function approximators (neural policy + discriminator) and policy-gradient updates, so it avoids tabular state/action representations and explicit density estimation over trajectories. This makes it practical for large observation spaces (e.g., images) and continuous actions (e.g., robotics control), where exact dynamic programming style methods are intractable.

• Sample efficient in terms of expert demonstrations

  The method only needs expert state-action examples as supervision for the discriminator rather than dense labels for the reward at every step. Because the discriminator reuses all collected expert trajectories across many updates, GAIL can learn useful imitation behavior from relatively limited demonstration datasets.

• Model-free (no environment dynamics model required)

  GAIL never estimates \(P(s'\mid s,a)\) explicitly. It only needs sampled transitions from environment interaction to update policy and discriminator, so it can be applied when environment dynamics are unknown or too complex to model accurately.

Connection Between IRL and GANs

Finn et al. (2016) established a formal equivalence between maximum entropy IRL, GANs, and energy-based models. This connection unifies these approaches under a common mathematical framework.

The Equivalence

Mathematical Connection

In MaxEnt IRL, the optimal policy under reward \(R\) is:

This is analogous to the Boltzmann distribution in energy-based models:

The GAN discriminator optimal solution is:

When the generator density is available, the discriminator effectively learns an energy function that assigns low energy to real data and high energy to generated samples; this is exactly what the reward function does in IRL.

Implications

• Algorithmic transfer: Techniques from GANs (e.g., Wasserstein distance, spectral normalization) can improve IRL stability
• Theoretical grounding: GAIL's success is explained by its equivalence to MaxEnt IRL
• Unified view: All three frameworks learn to distinguish "good" samples from "bad" samples via an energy/reward/discriminator function

@article{guo2026rl,
  title   = {Reinforcement Learning: Foundation and Modern Algorithms},
  author  = {Guo, Wenbo and Zhang, Ying},
  journal = {henrygwb.github.io},
  year    = {2026},
  url     = {https://henrygwb.github.io/posts/rl.htm}
}