RL and decisions#

Some notes on decision theory based on Berkeley's CS 188 course and "Artificial Intelligence" Russel & Norvig 3rd Edition

About this chapter

The chapter goes from one decision to many. Game trees cover adversarial search with minimax and alpha-beta pruning. Decision theory then says how a rational agent picks a single action: maximize expected utility, where the utility function follows from a few axioms about preferences, and information is worth gathering when it might change the plan.

Markov decision processes chain these decisions over time. Value iteration and policy iteration solve an MDP when the transition model \(P(s' \vert s, a)\) and the reward \(R(s)\) are known, and POMDPs add uncertainty about the state. Reinforcement learning drops the known model and learns from observed rewards, with TD learning, Q-learning or policy search. The last sections are notes from Sergey Levine’s deep RL course and on training LLMs with RL (PPO, DPO, GRPO, on-policy distillation).

Chapter outline: 6 sections
  1. Game trees - Russell & Norvig 5.2-5.51 interactiveMinimax backs values up a game tree: each player picks the move that is best for them, assuming the opponent does the same.
  2. Decision theory / VPI -- Russell & Norvig 16.5 & 16.61 figureA decision network adds decision nodes and a utility node to a Bayesian network.
  3. MDPs and rl - Russell & Norvig 17.1-17.41 interactive1 figureAn MDP fixes states, actions, a transition model P(s' \vert s,a) and a reward R(s).
  4. Reinforcement learning -- Russell & Norvig 21.1-21.61 interactiveNow the agent does not know P(s' \vert s, a) or R(s).
  5. Deep rl course1 figure
  6. RL for LLMsHere the policy is a language model.
  • Means–ends analysis - for planning subgoals, use the distance-to-the-goal as a continuous reward signal (and basically do greedy search with backtracking)

  • at test-time, we solve an optimization problem

Game trees - Russell & Norvig 5.2-5.5#

Minimax backs values up a game tree: each player picks the move that is best for them, assuming the opponent does the same. The rest of the section is about making that affordable: pruning, cutting the search off with a heuristic evaluation, and handling chance nodes.

Interactive 1. Minimax with alpha-beta pruning on a 3-ply tree with random leaf values. Drag the step slider back to 0 and step through: each node keeps a window [α, β], and once a node's value falls outside it, its remaining branches are pruned (dashed). Switch the move ordering: with the best moves first only 11 of the 27 leaves are evaluated, with the worst first none are pruned.
  • like search (adversarial search)

  • minimax algorithm

    • ply - half a move in a tree

    • for multiplayer, the backed-up value of a node n is the vector of the successor state with the highest value for the player choosing at n

    • time complexity - \(O(b^m)\)

    • space complexity - \(O(bm)\) or even \(O(m)\)

  • alpha-beta pruning cuts in half the exponential depth

    • once we have found out enough about n, we can prune it

    • depends on move-ordering

      • might want to explore best moves = killer moves first

    • transposition table can hash different movesets that are just transpositions of each other

  • imperfect real-time decisions

    • can evaluate nodes with a heuristic and cutoff before reaching goal

    • heuristic uses features

    • want quiescent search - consider if something dramatic will happen in the next ply

      • horizon effect - a position is bad but isn’t apparent for a few moves

      • singular extension - allow searching for certain specific moves that are always good at deeper depths

    • forward pruning - ignore some branches

      • beam search - consider only n best moves

      • PROBCUT prunes some more

  • search vs lookup

    • often just use lookup in the beginning

    • program can solve and just lookup endgames

  • stochastic games

    • include chance nodes

    • change minimax to expectiminimax

    • \(O(b^m numRolls^m)\)

    • cutoff evaluation function is sensitive to scaling - evaluation function must be a positive linear transformation of the probability of winning from a position

    • can do alpha-beta pruning analog if we assume evaluation function is bounded in some range

    • alternatively, could simulate games with Monte Carlo simulation

Utilities / decision theory – Russell & Norvig 16.1-16.3, mazzonni quant finance book#

A rational agent picks the action with maximum expected utility. The six axioms are the conditions on preferences under which such a utility function exists. The risk bullets show how the shape of the utility of money (sublinear, linear, supralinear) sets an agent’s attitude to gambles.

  • lottery - any function of a random variable

  • utility function - lottery that satisfiers certain properties (e.g. transitivity)

    • expected utility = von Neumann-Morgenstern utility

  • goal: maximize utility by taking actions (focus on single actions)

    • utility function U(s) gives utility of a state

    • actions are probabilistic: \(P[RESULT(a)=s' \vert a,e]\)

      • s - state, e - observations, a - action

  • soln: pick action with maximum expected utility

    • expected utility \(EU(a\vert e) = \sum_{s'} P(RESULT(a)=s' \vert a,e) U(s')\)

  • notation

    • A>B - agent prefers A over B

    • A~B - agent is indifferent between A and B

  • preference relation has 6 axioms of utility theory

    1. orderability - A>B, A~B, or A<B

    2. transitivity

    3. continuity

    4. substitutability - can do algebra with preference eqns

    5. monotonicity - if A>B then must prefer higher probability of A than B

    6. decomposability - 2 consecutive lotteries can be compressed into single equivalent lottery

  • these axioms yield a utility function

    • isn’t unique (ex. affine transformation yields new utility function)

    • value function = ordinal utility function - sometimes ranking, numbers not needed

    • agent might not be explicitly maximizing the utility function

Utility functions#

Preference elicitation finds a utility function by asking the agent to compare a state with a lottery between the best and the worst outcome. For money, the curvature of the utility function sets the attitude to risk. The descriptive-theory bullets list ways real people depart from the normative theory.

  • preference elicitation - finds utility function

    • normalized utility to have min and max value

    • assess utility of s by asking agent to choose between s and \((p: \min, (1-p): \max)\)

  • people have complicated utility functions

    • ex. micromort - one in a million chance of death

    • ex. QALY - quality-adjusted life year

  • risk

    • agents exhibits monotonic preference for more money

    • gambling has expected monetary value = EMV

    • risk averse = when utility of money is sublinear

      • risk premium = value agent will accept in lieu of lottery = certainty equivalent= insurance premium

    • risk-neutral = linear

    • risk-seeking = supralinear

    • absolute risk aversion \(ARA(x) = - \frac{u''(x)}{u'(x)}\) : higher is more risk averse

    • relative risk aversion \(ARA(x) = - \frac{x \cdot u''(x)}{u'(x)}\)

  • optimizer’s curse - tendency for E[utility] to be too high because we keep picking high utility randomness

  • normative theory - how idealized agents work

  • descriptive theory - how actual agents work

    • certainty effect - people are drawn to things that are certain

    • ambiguity aversion

    • framing effect - wording can influence people’s judgements

    • anchoring effect - buy middle-tier wine because expensive is there

Decision theory / VPI – Russell & Norvig 16.5 & 16.6#

A decision network adds decision nodes and a utility node to a Bayesian network. To evaluate it, set the evidence, try each value of the decision node, compute the expected utility of each, and return the best action.

  • note: here we are just making 1 decision

  • decision network (sometimes called influence diagram)

    1. chance nodes - represent RVs (like BN)

    2. decision nodes - points where decision maker has a choice of actions

    3. utility nodes - represent agent’s utility function

  • can ignore chance nodes

    • then action-utility function = Q-function maps directly from actions to utility

The airport-siting problem as a decision network. Left: the decision node Airport Site (rectangle) and the chance nodes Air Traffic, Litigation and Construction feed the outcomes Deaths, Noise and Cos

Fig. 82 Figure 1. The airport-siting problem as a decision network. Left: the decision node Airport Site (rectangle) and the chance nodes Air Traffic, Litigation and Construction feed the outcomes Deaths, Noise and Cost, which feed the utility node U (diamond). Right: the outcome nodes are dropped and U depends directly on the decision and the other chance nodes, an action-utility function.#

  • evaluation

    1. set evidence

    2. for each possible value of decision node

    • set decision node to that value

    • calculate probabilities of parents of utility node

    • calculate resulting utility

    1. return action with highest utility

The value of information#

VPI is the expected gain from learning a variable’s value before acting: the expected best utility after seeing \(T\), minus the best utility now. The two intuition bullets say when it is large.

  • information value theory - enables agent to choose what info to acquire

    • observations only affect agent’s belief state

    • value of info = difference in best expected value with/without info

    • maximum \(EU(\alpha\vert e) = \underset{a}{\max} \sum_{s'} P(Result(a)=s'\vert a, e) U(s')\)

  • value of perfect information VPI - assume we can obtain exact evidence for a variable (ex. variable \(T=t\))

    • \(VPI(T) = \cgreen{\mathbb{E}_{T}\left[ EU(\alpha\vert e, T) \right]} - \underbrace{\corange{EU(\alpha \vert e)}}_{\text{original EU}}\)

    • first term expands to \(\sum_t P(T=t \vert e) \cdot EU(\alpha \vert e, T=t) \)

      • within each of these EU, we take a max over actions

    • VPI not linearly additive, but is order-independent

    • intuition

      • info is more valuable when it is likely to cause a change of plan

      • info is more valuable when the new plan will be much better than the old plan

  • information-gathering agent

    • myopic - greedily obtain evidence which yields highest VPI until some threshold

    • conditional plan - considers more things

MDPs and rl - Russell & Norvig 17.1-17.4#

An MDP fixes states, actions, a transition model \(P(s' \vert s,a)\) and a reward \(R(s)\). A policy \(\pi(s)\) picks an action in each state, and the discount \(\gamma\) turns an infinite sequence of rewards into a finite utility.

  • sequences of actions

  • fully observable - agent knows its state

  • markov decision process - all these things are given

    • set of states s

    • set of actions a

    • stochastic transition model \(P(s' \vert s,a)\)

    • reward function \(R(s)\)

      • utility aggregates rewards, for models more complex than mdps reward can be a function of past sequences of actions / observations

  • want policy \(\pi (s)\) - what action to do in state s

    • optimal policy yields highest expected utlity

  • optimizing MDP - multiattribute utility theory

    • could sum rewards, but results are infinite

    • instead define objective function (maps infinite sequences of rewards to single real numbers)

      • ex. discounting to prefer earlier rewards (most common)

        • discount reward n steps away by \(\gamma^n, 0<\gamma<1\)

      • ex. set a finite horizon and sum rewards

        • optimal action in a given state could change over time = nonstationary

      • ex. average reward rate per time step

      • ex. agent is guaranteed to get to terminal state eventually - proper policy

  • expected utility executing \(\pi\): \(U^\pi (s) = \mathbb E_{s_1,...,s_t}\left[\sum_t \gamma^t R(s_t)\right]\)

    • when we use discounted utilities, \(\pi\) is independent of starting state

    • \(\pi^*(s) = \underset{\pi}{\text{argmax}} \: U^\pi (s) = \underset{a}{\text{argmax}} \sum_{s'} P(s' \vert s,a) U(s')\)

  • experience replay - instead of learning from samples one by one, want to reduce correlation between subsequent samples

    • take a large batch of samples and sample randomly from it, rather than going sequentially

Value iteration#

Value iteration applies the Bellman update to every state until the utilities stop changing. It converges because the update is a contraction: each iteration shrinks the error by a factor of \(\gamma\).

Interactive 2. Russell & Norvig's 4×3 grid world. Each Bellman update sets \(U(s)\) to the reward \(R(s)\) plus the discounted expected utility of the next state under the best action; the arrows show that action. Step \(k\) up and watch the values spread out from the +1 and −1 squares one step per update and then settle (the bottom-left state converges to 0.705). Then change the reward. A large penalty per step sends the agent to the nearest exit, even −1. A positive reward makes it avoid both exits (lower \(\gamma\) below 1 so the values stay finite).
  • value iteration - calculates utility of each state and uses utilities to find optimal policy

    • bellman eqn: \(U(s) = \cblue{R(s)} + \cgreen{\gamma \: \underset{a}{\max} \sum_{s'} P(s' \vert s, a) U(s')}\)

      • immediate reward + discounted expected utility of next state under best action

    • start with arbitrary utilities

    • recalculate several times with Bellman update to approximate solns to bellman eqn

  • value iteration eventually converges

    • contraction - function that brings variables together

      • contraction only has 1 fixed point

      • Bellman update is a contraction on the space of utility vectors and therefore converges

      • error is reduced by factor of \(\gamma\) each iteration

    • also, terminating condition: if \( \vert \vert U_{i+1}-U_i \vert \vert < \epsilon (1-\gamma) / \gamma\) then \( \vert \vert U_{i+1}-U \vert \vert <\epsilon\)

    • what actually matters is policy loss \( \vert \vert U^{\pi_i}-U \vert \vert \) - the most the agent can lose by executing \(\pi_i\) instead of the optimal policy \(\pi^*\)

      • if \( \vert \vert U_i -U \vert \vert < \epsilon\) then \( \vert \vert U^{\pi_i} - U \vert \vert < 2\epsilon \gamma / (1-\gamma)\)

Policy iteration#

Instead of iterating on utilities, alternate two steps: evaluate a fixed policy, which is a set of linear equations with no max, then improve the policy greedily using those utilities.

  • another way to find optimal policies

    1. policy evaluation - given a policy \(\pi_i\), calculate \(U_i=U^{\pi_i}\), the utility of each state if \(\pi_i\) were to be executed

    • like value iteration, but with a set policy so there’s no max

      • \(U_i(s) = R(s) + \gamma \: \sum_{s'} P(s' \vert s, \pi_i(s)) U_i(s')\)

      • can solve exactly for small spaces, or approximate (set of lin. eqs.)

    1. policy improvement - calculate a new MEU policy \(\pi_{i+1}\) using \(U_i\)

    • same as above, just \(\pi^*(s) = \underset{\pi}{\text{argmax}} \: U^\pi (s) = \underset{a}{\text{argmax}} \sum_{s'} P(s' \vert s,a) U'(s)\)

  • asynchronous policy iteration - don’t have to update all states at once

Partially observable markov decision processes (POMDP)#

When the agent cannot see its state, it keeps a belief \(b(s)\) and updates it after each action and observation, like filtering in an HMM. The optimal action depends only on \(b\), so a POMDP is an MDP over the continuous space of beliefs.

  • agent is not sure what state it’s in

  • same elements but add sensor model \(P(e \vert s)\)

  • have distr \(b(s)\) for belief states

    • updates like the HMM: \(b'(s') = \alpha \cblue{P(e \vert s')} \sum_s \corange{P(s' \vert s, a)} \cgreen{b(s)}\)

      • sensor model, transition model, previous belief

    • changes based on observations

  • optimal action depends only on the agent’s current belief state

    • use belief states as the states of an MDP and solve as before

    • changes because state space is now continuous

  • value iteration

    1. expected utility of executing p in belief state is just \(b \cdot \alpha_p\) (dot product)

    2. \(U(b) = U^{\pi^*}(b)=\underset{p}{\max} \: b \cdot \alpha_p\)

    • belief space is continuous [0, 1] so we represent it as piecewise linear, and store these discrete lines in memory

      • do this by iterating and keeping any values that are optimal at some point

        • remove dominated plans

    • generally this is far too inefficient

  • dynamic decision network - online agent

    A dynamic decision network unrolled three steps into the future. Shaded nodes are known: past actions, evidence and rewards. To choose $A_t$ the agent looks ahead over states $X$, evidence $E$ and rew

    Fig. 83 Figure 2. A dynamic decision network unrolled three steps into the future. Shaded nodes are known: past actions, evidence and rewards. To choose \(A_t\) the agent looks ahead over states \(X\), evidence \(E\) and rewards \(R\), with a utility \(U_{t+3}\) for the state at the horizon.#

    • the generic structure of a dynamic decision network. Variables with known values are shaded. The current time is t and the agent must decide what to do—that is, choose a value for A_t. The network has been unrolled into the future for three steps and represents future rewards, as well as the utility of the state at the look-ahead horizon

Reinforcement learning – Russell & Norvig 21.1-21.6#

Now the agent does not know \(P(s' \vert s, a)\) or \(R(s)\). Passive RL evaluates a fixed policy; active RL also chooses actions, which brings in the trade-off between exploring and exploiting. Model-based agents learn the model and plan with it; model-free agents learn \(Q(s, a)\) or a policy directly.

  • reinforcement learning - use observed rewards to learn optimal policy for the environment

    • in ch 17, agent had model of environment (\(P(s'\vert s, a)\) and \(R(s)\))

  • 2 problems

    • passive - given \(\pi\), learn \(U^\pi (s)\)

    • active - explore states to find utilities and exploit to get highest reward

  • 2 model types, 3 agent designs

    • model-based: can predict next state/reward before taking action (for MDP, requires learning \(P(s'\vert s,a)\))

      • utility-based agent - learns \(U(S)\) - utility function on states

        • requires model of the environment

    • model-free

      • Q-learning agent: learns \(Q(s, a)\) - action-utility function = Q-function maps actions \(\to\) utility

      • reflex agent: learns \(Q(s)\) - policy that maps directly from states to actions

Passive reinforcement learning (estimate value function given policy)#

The policy is fixed and the agent must learn \(U^\pi(s)\) without knowing the model. Three ways: average the observed returns from each state (direct utility estimation), learn the model and solve the Bellman equations (ADP), or move each estimate toward the reward plus the estimate at the next state (TD learning).

  • given policy \(\pi\), learn \(U^\pi (s) = \mathbb E\left[ \sum_{t=0}^{\infty} \gamma^t R(S_t)\right]\)

    • like policy evaluation, but transition model / reward function are unknown

  • direct utility estimation: treat states independently

    • run trials to sample utility

    • average to get expected total reward for each state = expected total reward from each state

  • adaptive dynamic programming (ADP) - 2 steps

    • sample to estimate transition model \(P(s'\vert s, a)\) and rewards \(R(s)\)

    • find \(U^\pi(s)\) with the Bellman eqn (plug in at each step)

    • we might want to enforce a prior on the model (two ways)

      1. Bayesian reinforcement learning - assume a prior \(P(h)\) on transition model h

      • use prior to calculate \(P(h \vert e)\)

      • use \(P(h\vert e)\) to calculate optimal policy: \(\pi^* = \underset{\pi}{\operatorname*{argmax}} \sum_h P(h \vert e) u_h^\pi\)

        • \(u_h^\pi\)= expected utility over all possible start states, obtained by executing policy \(\pi\) in model h

      1. robust control theory - give best outcome in the worst case over H

      • \(\pi^* = \underset{\pi}{\operatorname*{argmax}}\: \underset{h}{\min} \: u_h^\pi\)

  • temporal-difference learning - adjust utility estimates towards local equilibrium for correct utilities

    • like an approximation of ADP

    • when we transition \(s \to s'\), update \(U^\pi(s) = \cgreen{U^\pi (s)} + \cpurple{\alpha} \cblue{\left[R(s) - U^\pi (s) + \gamma \:U^\pi (s') \right]}\)

      • old estimate + learning rate × TD error

      • \(\alpha\) should decrease over time to converge

    • prioritized sweeping - prefer adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates (speeds things up)

Active reinforcement learning#

Now the agent chooses its actions. Acting greedily on its current estimates can lock in a poor policy, so it also has to explore. Bandit problems study the same trade-off with a single state, and GLIE schemes explore every state infinitely often but become greedy in the limit.

  • no longer following set policy

    • explore states to find their utilities and exploit model to get highest reward

    • must explore all actions, not just those in the policy

  • bandit problems - determining exploration policy

    • n-armed bandit - pulling n levelers on a slot machine, each with different distr.

    • Gittins index - function of number of pulls / payoff

  • coorect schemes should be GLIE - greedy in the limit of infinite exploration - visits all states infinitely, but eventually become greedy

Agent examples#

  • ex. choose random action \(1/t\) of the time

  • ex. active adp agent

    • give optimistic utility to relatively unexplored states

    • uses exploration function f(u, numTimesVisited) around the sum in the bellman eqn

      • high utilities will propagate

  • ex. active TD agent

    • now must learn transitions (same as adp)

    • update rule same as passive TD

Learning action-utility function \(Q(s, a)\)#

Learning \(Q(s, a)\) instead of \(U(s)\) removes the need for a model, because the best action is just \(\text{argmax}_a Q(s, a)\). Q-learning is the TD update applied to \(Q\). It is off-policy: its target uses the best next action, whatever the agent actually does next, while SARSA uses the action actually taken.

Interactive 3. Q-learning with ε-greedy exploration on the 4×3 grid world from the value iteration figure, without a model of the transitions. Each cell shows \(\max_a Q(s, a)\), the true utility \(U\) below it, and the greedy action (green if it is optimal). With ε = 0 the agent always takes its current best action; in this run it settles on a worse route and never finds out. A little exploration (ε from about 0.05 to 0.2) finds the optimal policy and still collects high reward. With ε = 1 the agent acts at random. Because Q-learning is off-policy its greedy policy still improves, but the reward it collects while learning is poor. Press "another run" to see how much single runs vary.
  • \(U(s) = \underset{a}{\max} \: Q(s,a)\)

    • ADP version: \(Q(s, a) = R(s) + \gamma \sum_{s'} P(s'\vert s, a) \underset{a'}{\max} Q(s', a')\)

    • TD version: \(Q(s,a) = \cgreen{Q(s,a)} + \cpurple{\alpha} [R(s) - Q(s,a) + \gamma \: \corange{\underset{a'}{\max} Q(s', a')}]\) - this is what is usually referred to as Q-learning

    • this is off-policy (only uses best Q-value, doesn’t pay attention to actualy policy being followed) - more flexible

  • SARSA (state-action-reward-state-action) is related: \(Q(s,a) = \cgreen{Q(s,a)} + \cpurple{\alpha} [R(s) + \gamma \: \corange{Q(s', a')} - Q(s,a) ]\)

    • here, \(a'\) is action actually taken

    • SARSA is on-policy (pays attention to actual policy being followed)

  • can approximate Q-function with something other than a lookup table

    • ex. linear function of parameters \(\hat{U}_\theta(s) = \theta_1f_1(s) + ... + \theta_n f_n(s)\)

      • can learn params online with delta rule = wildrow-hoff rule: \(\theta_i = \theta - \alpha \: \frac{\partial Loss}{\partial \theta_i}\)

Deep rl course#

berkeley (sergey levine)

“supervised rl” (imitation learning)#

Imitation learning treats control as supervised learning on an expert’s (observation, action) pairs. Plain behavioral cloning is usually not enough. DAgger has humans label the observations the learned policy actually reaches, and goal-conditioned cloning learns \(\pi_\theta(a \vert s, g)\).

  • imitation learning / behavioral cloning – given pairs of observations / actions, learn policy to take action given observation \(\pi_\theta(a_t\vert o_t)\)

    • basic example: cost function is 0 when action is same as human’s in data and 1 otherwise

    • usually inefficient / insufficient

  • one improvement: DAgger (ross et al. 2011) - use learned policy to generate synthetic observations and have humans label those

    • we can query observations when deviate slightly from expert trajectory

  • goal-conditioned behavioral cloning - subdivides data based on different goals - learn \(\pi_\theta(a\vert s, g)\)

    • example - given a goal location, take actions to move a robot there

  • Learning to Reach Goals via Iterated Supervised Learning (ghosh … levine, 2020)

    • move robot arm based on policy (initially random)

    • see which random goals are met

    • use this as goal-conditioned behavioral cloning

    • update policy and repeat

RL algorithms overview#

Every algorithm repeats three steps: run the policy to generate samples, fit a model or estimate the return, and improve the policy. The table shows how value-based methods, policy gradients, actor-critic and model-based RL fill in the last two.

  • 3 general steps (iterated)

    • fit a model / estimate the return

    • improve the policy

    • generate samples (i.e. run the policy)

  • \(\theta^{\star}=\arg \max _{\theta} E_{\tau \sim p_{\theta}(\tau)}\left[\sum_{t} r\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)\right]\)

    • Value-based: estimate value function or \(Q\)-function of the optimal policy (no explicit policy)

    • Policy gradients: directly differentiate the above objective

      • policy network \(\pi_\theta(a\vert s)\)

      • gradients are extremely noisy compared to supervised learning

    • Actor-critic: estimate value function or Q-function of the current policy (critic), use it to improve policy (actor)

    • Model-based RL: estimate the transition model, and then…

      • just use the model to plan (no plicy)

        • trajectory optimization/optimal control (continuous space) - optimize over actions

        • discrete planning - e.g. monte carlo tree search

      • backpropagate gradients into the policy

      • use the model to learn a value function

fit model / estimate return

improve policy

value-based

fit \(V(s)\) or \(Q(s, a)\)

\(\pi(s) = \text{argmax}_a Q(s, a)\)

(direct) policy gradients

evaluate returns \(R_\tau = \sum_t r(s_t, a_t)\)

\(\theta = \theta + \alpha \nabla_\theta E[\sum_t r(s_t, a_t)]\)

actor-critic

fit \(V(s)\) or \(Q(s, a)\)

\(\theta = \theta + \alpha \nabla_\theta E[Q(s, a)]\)

model-based

maybe model \(P(s'\vert s, a)\)

  • sample efficiency

    • on policy - must generate new samples each time the policy is changed

    • off policy - can improve policy without generating new samples from it (so look at a bunch of samples then update)

    • offline rl - data collected only once with any policy, then want to learn good policy from that

RL methods ordered by how many samples they need, from model-based methods (fewest) to evolutionary and gradient-free methods (most). Off-policy methods sit left of actor-critic, on-policy methods rig

Fig. 84 Figure 3. RL methods ordered by how many samples they need, from model-based methods (fewest) to evolutionary and gradient-free methods (most). Off-policy methods sit left of actor-critic, on-policy methods right.#

Other problems#

Inverse rl#

Inverse RL runs the problem backward: from an agent’s behavior, infer the reward function it is optimizing. The same idea is the main proposal for value alignment in the AI futures chapter.

Inverse RL - learning reward functions from example

  • ai should be uncertain about utitilies

  • utilties should be inferred from human preferences

  • in systems that interact, need to express preferences in terms of game theory

  • can solve it with a GAN: e.g. A Connection between Generative Adversarial Networks, Inverse Reinforcement Learning, and Energy-Based Models (finn et al. 2016)

  • Apprenticeship learning via inverse reinforcement learning | Proceedings of the twenty-first international conference on Machine learning (abbeel & ng, 2004) - good intro to inverse RL

Planning#

  • Efficient Learning in Cellular Simultaneous Recurrent Neural Networks - The Case of Maze Navigation Problem (ilin et al. 2007) - explored connections between planning algorithms and recurrent NNs

  • Value Iteration Networks (tamar…levine, & abbeel, 2017)

    • represent value iteration as a fully differentiable DNN using recurrence

Metalearning#

Learning to learn: train across many tasks so that a new task needs only a few samples. The learned part can be the optimizer, the representation or the way to explore.

  • learning to learn (very close to multi-task learning)

    • e.g. learn optimizer, representation

    • e.g. learn how to explore

    • e.g. learn how to do RL for various different walking tasks and then generalize to new walking task with few samples

    • Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks (finn, levine, & abbeel, 2017) - treat metalearner itself as an RL algorithm

  • multitask learning

    • sometimes have the ability to decide which new tasks to add (e.g. by changing simulator)

Offline rl#

Offline RL learns from data collected once, by any policy. The new policy should improve on the one that collected the data, but it cannot move far from it because of distribution shift.

  • core issue with offline RL: want policy that improves over the training policy, but can’t deviate from the training policy due to distr. shift

  • one idea: instead of collecting new samples with policy, reweight samples using importance sampling based on policy

  • IQL: Implicit Q-learning (ashvin’s paper, 2021)

    • IQL - foregoes need to evaluate unseen actions

RL for LLMs#

Here the policy is a language model. The signal comes from a separate reward model, from preference pairs, or from a checker such as a code solver. On-policy distillation keeps the student’s own rollouts but has a teacher grade every token.

  • basic intuition: though RL gives less bits than finetuning, the bits are higher signal than all the misc stuff in next-token prediction (beren, 2026 blog post)

  • PPO: Proximal Policy Optimization (schulman et al. 2017)

    • uses a policy gradient method to update the policy based on the reward from a separate reward model

  • DPO: Direct Preference Optimization (rafailov…manning, finn, 2023) - simpler technique that eliminates the need for a separate reward model using preference data directly

    • essentially frames the problem as a classification task between the chosen and rejected responses

  • GRPO: Group Relative Policy Optimization (deepseek-r1, 2025) - groups similar samples together and compares them as a group (can evaluate them in different ways, e.g. with reward model or function like a code solver)

On-policy distillation#

SFT trains on the teacher’s outputs; RL trains on the student’s own rollouts with a reward. On-policy distillation combines them: the student samples its own rollouts and the teacher grades every token by reverse KL. The self-distillation variants use the student itself, given privileged information such as the answer, as the teacher.

  • some basic thoughts from “On SFT, RL, and on-policy distillation” tweet (will brown)

    • SFT helps quickly get to teacher ceiling, works better with matched tokenizer / general training recipe

      • SFT before RL is generally more efficient, as it sets it up to get better samples

      • Rejection-sampled SFT (SFT-RS, sometimes RFT) - sample from the teacher or the student, filter for correctness, train on the survivors) - better than standard SFT, but saturates based on your filter (often some reward model)

    • On-policy distillation (thinking machines blog post, 2025; +Qwen3 tech report)

      • student samples its own rollouts — so you get RL’s compounding in the sampling distribution — but each token in the rollout is graded by the teacher via per-token reverse KL (probability of token under teacher - probability of token under student)

    • to avoid different tokenizers/model for teacher/student, we can use student with priveleged info as the teacher

      • ex. SDFT (Self-Distillation Enables Continual Learning (shenfeld, damani, hübotter & agrawal, 2026)) - condition on expert demonstration (possibly for a different task)

      • ex. OPSD = On-policy self-distillation (zhao…grover, 2026) - condition on groundtruth answer

        • note: OPSD can have very large gradients on individual tokens, where models differ, sometimes leading the model astray – to fix this, often cap the update for an individual token (“point-wise KL clipping”)

        • Latent On-Policy Self-Distillation (zhang…yan, 2026) - instead of conditioning on groundtruth answer, let model learn what to condition on

      • RL via Self-Distillation (hübotter…krause, 2026) - self-distillation + privileged information (feedback)

  • RL Teachers of Test Time Scaling (cetin, zhao, & tang, 2025) - rather than learning through exploration, give teacher models the correct explanation and ask them to “connect-the-dots” with explanations for their students

    • this yields more accurate teachers, and better distillation data from the teachers for student models

  • nice blog post on scaling RL/RLVR: https://yidingjiang.github.io/blog/post/exploration/

  • without updating parameters

Key ideas

  • Minimax backs values up a game tree, and alpha-beta pruning skips branches that cannot change the decision; how much it skips depends on move ordering.

  • A rational agent picks the action with maximum expected utility, and information is worth gathering when it might change that action.

  • In an MDP the Bellman equation ties each state’s utility to its successors’, and value iteration or policy iteration solves it when the model is known.

  • Without a model, TD learning and Q-learning move each estimate toward the observed reward plus the estimate at the next state.

  • An agent that learns while acting must trade off exploring and exploiting. Q-learning is off-policy, so it can learn the optimal \(Q\) while following an exploratory policy.

  • {‘In RL for LLMs the policy is the language model, and the methods differ in the signal’: ‘a reward model (PPO), preference pairs (DPO), comparisons within a group of samples (GRPO), or a teacher grading each token (on-policy distillation).’}