Lesson overview | Previous part | Next part

Reinforcement Learning: Part 7: Control Algorithms to 8. Function Approximation and Deep RL

7. Control Algorithms

Control Algorithms is part of the core mathematical path from Markov chains to modern AI agents. The emphasis is on the object definitions and update equations a learner must be able to inspect in code.

7.1 SARSA

Purpose. SARSA focuses on on-policy TD control. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$L^{\mathrm{CLIP}}(\theta)=\mathbb{E}\left[\min(r_t(\theta)\hat{A}_t,\operatorname{clip}(r_t(\theta),1-\epsilon,1+\epsilon)\hat{A}_t)\right].$$

Operational definition.

Control algorithms learn how to choose actions, not just how to evaluate a fixed policy.

Worked reading.

SARSA uses the action actually sampled by the behavior policy; Q-learning uses a greedy target and is therefore off-policy.

Examples:

1. tabular gridworld control.
2. DQN-style value learning.
3. epsilon-greedy exploration.

Non-examples:

1. estimating $V^\pi$ only.
2. planning with a perfect model and no samples.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.

7.2 Q-learning

Purpose. Q-learning focuses on off-policy TD control with greedy targets. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\gamma),\qquad P(s'\mid s,a)=\Pr(S_{t+1}=s'\mid S_t=s,A_t=a).$$

Operational definition.

Control algorithms learn how to choose actions, not just how to evaluate a fixed policy.

Worked reading.

SARSA uses the action actually sampled by the behavior policy; Q-learning uses a greedy target and is therefore off-policy.

Examples:

1. tabular gridworld control.
2. DQN-style value learning.
3. epsilon-greedy exploration.

Non-examples:

1. estimating $V^\pi$ only.
2. planning with a perfect model and no samples.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.

7.3 Exploration schedules

Purpose. Exploration schedules focuses on epsilon greedy softmax and optimism. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$G_t=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1},\qquad 0\le \gamma<1.$$

Operational definition.

This concept is part of the bridge from sequential probability models to practical RL algorithms.

Worked reading.

The key habit is to name the state, action, reward, transition, policy, and value object before writing an update.

Examples:

1. small tabular MDPs.
2. neural value functions.
3. preference-optimized language policies.

Non-examples:

1. static regression.
2. uncontrolled simulation traces.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.

7.4 Double Q-learning

Purpose. Double Q-learning focuses on reducing maximization bias. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$V^\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s],\qquad Q^\pi(s,a)=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a].$$

Operational definition.

Control algorithms learn how to choose actions, not just how to evaluate a fixed policy.

Worked reading.

SARSA uses the action actually sampled by the behavior policy; Q-learning uses a greedy target and is therefore off-policy.

Examples:

1. tabular gridworld control.
2. DQN-style value learning.
3. epsilon-greedy exploration.

Non-examples:

1. estimating $V^\pi$ only.
2. planning with a perfect model and no samples.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.

7.5 Convergence conditions

Purpose. Convergence conditions focuses on what tabular guarantees assume. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$V^\pi(s)=\sum_a\pi(a\mid s)\sum_{s'}P(s'\mid s,a)\left(r(s,a,s')+\gamma V^\pi(s')\right).$$

Operational definition.

This concept is part of the bridge from sequential probability models to practical RL algorithms.

Worked reading.

The key habit is to name the state, action, reward, transition, policy, and value object before writing an update.

Examples:

1. small tabular MDPs.
2. neural value functions.
3. preference-optimized language policies.

Non-examples:

1. static regression.
2. uncontrolled simulation traces.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.

8. Function Approximation and Deep RL

Function Approximation and Deep RL is part of the core mathematical path from Markov chains to modern AI agents. The emphasis is on the object definitions and update equations a learner must be able to inspect in code.

8.1 Why tables fail

Purpose. Why tables fail focuses on large state spaces and generalization. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\gamma),\qquad P(s'\mid s,a)=\Pr(S_{t+1}=s'\mid S_t=s,A_t=a).$$

Operational definition.

This concept is part of the bridge from sequential probability models to practical RL algorithms.

Worked reading.

The key habit is to name the state, action, reward, transition, policy, and value object before writing an update.

Examples:

1. small tabular MDPs.
2. neural value functions.
3. preference-optimized language policies.

Non-examples:

1. static regression.
2. uncontrolled simulation traces.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.

8.2 Linear value approximation

Purpose. Linear value approximation focuses on projected Bellman equations. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$G_t=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1},\qquad 0\le \gamma<1.$$

Operational definition.

Value functions summarize future consequences. Advantage functions compare an action with the policy's average behavior at the same state.

Worked reading.

Occupancy measures explain why RL gradients weight states by how often the current policy visits them.

Examples:

1. $V^\pi$.
2. $Q^\pi$.
3. $A^\pi$.

Non-examples:

1. instant reward only.
2. a metric computed on states never reached by the policy.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.

8.3 The deadly triad

Purpose. The deadly triad focuses on bootstrapping off-policy learning and approximation. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$V^\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s],\qquad Q^\pi(s,a)=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a].$$

Operational definition.

This concept is part of the bridge from sequential probability models to practical RL algorithms.

Worked reading.

The key habit is to name the state, action, reward, transition, policy, and value object before writing an update.

Examples:

1. small tabular MDPs.
2. neural value functions.
3. preference-optimized language policies.

Non-examples:

1. static regression.
2. uncontrolled simulation traces.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.

8.4 DQN stabilization

Purpose. DQN stabilization focuses on replay buffers and target networks. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$V^\pi(s)=\sum_a\pi(a\mid s)\sum_{s'}P(s'\mid s,a)\left(r(s,a,s')+\gamma V^\pi(s')\right).$$

Operational definition.

Function approximation replaces tables with parameterized models so the agent can generalize across large state spaces.

Worked reading.

Deep RL is powerful because neural networks share statistical strength, but unstable because approximate bootstrapping can amplify errors.

Examples:

1. DQN target networks.
2. experience replay.
3. critic networks.

Non-examples:

1. exact dynamic programming in a tiny known MDP.
2. memorizing every state-action value in a table.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.

8.5 Representation learning for policies and critics

Purpose. Representation learning for policies and critics focuses on how neural networks change the math. This is not optional vocabulary: it determines which variables are random, which distribution creates the data, and which recursive target is valid.

$$Q^*(s,a)=\sum_{s'}P(s'\mid s,a)\left(r(s,a,s')+\gamma\max_{a'}Q^*(s',a')\right).$$

Operational definition.

This concept is part of the bridge from sequential probability models to practical RL algorithms.

Worked reading.

The key habit is to name the state, action, reward, transition, policy, and value object before writing an update.

Examples:

1. small tabular MDPs.
2. neural value functions.
3. preference-optimized language policies.

Non-examples:

1. static regression.
2. uncontrolled simulation traces.

Derivation habit.

1. State whether the policy is fixed, greedy-improved, or being optimized.
2. Write the return or Bellman target before writing code.
3. Identify whether the target is sampled, model-based, bootstrapped, or exact.
4. Check whether the data are on-policy or off-policy.
5. Mask terminal states so that value is not propagated beyond the episode.

Implementation lens.

In a small tabular MDP, every object can be printed: transition matrices, reward vectors, value arrays, and greedy actions. In a deep RL system, the same objects exist but are represented by neural networks, replay buffers, sampled rollouts, and approximate losses. The names should not change just because the implementation becomes larger.

For LLM work, the state is usually a prompt plus generated prefix, the action is the next token or structured action, and the policy is an autoregressive distribution. The reward may arrive only after a full response, which means the return is sequence-level even though actions are token-level.

Useful checks:

• Does the transition or sample contain the next state?
• Is the update using $V$, $Q$, an advantage, or a reward-only signal?
• Is the current policy also the data-collection policy?
• Does discounting express time preference or just numerical convenience?
• Is the reward model being optimized beyond its trustworthy region?

A common failure mode is to copy an update rule while silently changing the sampling assumption. For example, SARSA and Q-learning can look nearly identical in code, but one updates from the action actually taken and the other updates from a greedy next action. That distinction changes both the mathematics and the behavior.

The notebook version of this idea keeps the environment small enough to inspect by hand. If a concept is unclear, compute it first in the chain MDP and only then move to neural approximators.