6.3. rl, decisions#
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
6.3.1. game trees - Russell & Norvig 5.2-5.5#
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
6.3.1.1. utilities / decision theory – Russell & Norvig 16.1-16.3, mazzonni quant finance book#
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
orderability - A>B, A~B, or A<B
transitivity
continuity
substitutability - can do algebra with preference eqns
monotonicity - if A>B then must prefer higher probability of A than B
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
6.3.1.2. utility functions#
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
6.3.2. decision theory / VPI – Russell & Norvig 16.5 & 16.6#
note: here we are just making 1 decision
decision network (sometimes called influence diagram)
chance nodes - represent RVs (like BN)
decision nodes - points where decision maker has a choice of actions
utility nodes - represent agent’s utility function
can ignore chance nodes
then action-utility function = Q-function maps directly from actions to utility
evaluation
set evidence
for each possible value of decision node
set decision node to that value
calculate probabilities of parents of utility node
calculate resulting utility
return action with highest utility
6.3.2.1. the value of information#
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\))
- \[ \begin{align}\begin{aligned}VPI(T) = \cgreen{\mathbb{E}_{T}\left[ EU(\alpha\vert e, T) \right]} - \underbrace{\corange{EU(\alpha \vert e)}}_{\text{original EU}}$$<!-- --> - <span class="cgreen">first term</span> 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\\- 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)\end{aligned}\end{align} \]
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
- \[ \begin{align}\begin{aligned}\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* - 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')}\end{aligned}\end{align} \]
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)\)
6.3.2.2. policy iteration#
another way to find optimal policies
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.) 2. *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
6.3.2.3. partially observable markov decision processes (POMDP)#
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
expected utility of executing p in belief state is just \(b \cdot \alpha_p\) (dot product)
- \[ \begin{align}\begin{aligned}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 <img style="width: 640px; max-width: 100%;" src="../assets/online_pomdp.svg" alt="Dynamic decision network"/> - 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\\- *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)\\- 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 2. *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]}\end{aligned}\end{align} \]
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)
6.3.2.4. active reinforcement learning#
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
6.3.2.4.1. 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
6.3.2.4.2. learning action-utility function \(Q(s, a)\)#
- \[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}\)$
6.3.2.5. policy search#
keep twiddling the policy as long as it improves, then stop
store one Q-function (parameterized by \(\theta\)) for each action
ex. $\(\pi(s) = \underset{a}{\max} \: \hat{Q}_\theta (s,a)\)$
this is discontinunous, instead often use stochastic policy representation (ex. softmax for \(\pi_\theta (s,a)\))
learn \(\theta\) that results in good performance
Q-learning learns actual Q* function - could be different (scaling factor etc.)
to find \(\pi\) maximize policy value \(p(\theta) = \) expected reward executing \(\pi_\theta\)
could do this with sgd using policy gradient
when environment/policy is stochastic, more difficult
could sample mutiple times to compute gradient
REINFORCE algorithm - could approximate gradient at \(\theta\) by just sampling at \(\theta\): \(\nabla_\theta p(\theta) \approx \frac{1}{N} \sum_{j=1}^N \frac{(\nabla_\theta \pi_\theta (s, a_j)) R_j (s)}{\pi_\theta (s, a_j)}\)
PEGASUS - correlated sampling - ex. 2 blackjack programs would both be dealt same hands - want to see different policies on same things
6.3.3. deep rl course#
6.3.3.1. “supervised rl” (imitation learning)#
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
6.3.3.2. rl algorithms overview#
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
6.3.3.3. other problems#
6.3.3.3.1. inverse rl#
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
6.3.3.3.2. 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
6.3.3.3.3. metalearning#
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)
6.3.3.3.4. offline rl#
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
6.3.4. RL for LLMs#
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)
6.3.4.1. on-policy distillation#
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
SDPO: RL via Self-Distillation (hübotter…krause, 2026)
ERL: Experiential RL (shi…zhao, 2026)
Training-Free GRPO (cai…sun, 2025)
SkillRL: Evolving Agents via Recursive Skill-Augmented RL (xia…yao, 2026)
Skill0: In-Context Agentic RL for Skill Internalization (lu…shen, 2026)
Skill1: Unified Evolution of Skill-Augmented Agents via RL (shi…zhang, 2026)
MemRL: Self-Evolving Agents via Runtime RL on Episodic Memory (zhang…wen, 2026)