Reinforcement Learning - Stanford CS234

Stanford CS234 I Reinforcement Learning I Spring 2024 I Emma Brunskill - YouTube
This course provides a comprehensive exploration of Reinforcement Learning (RL), the science of training agents to make optimal decisions through environmental interaction to maximize cumulative reward. The curriculum follows a structured progression, beginning with the foundational mathematical framework of Markov Decision Processes (MDPs) and the classical "planning" algorithms of Value and Policy Iteration, which solve for optimal behavior when a perfect model of the environment is known.
The course then transitions to the core "learning" problem, where the agent must learn in a model-free setting through trial and error. This introduces the fundamental exploration-exploitation dilemma. Two primary families of algorithms are developed in detail:

1. Value-Based Methods, which focus on learning the value of states and actions. This line of inquiry culminates in Q-Learning and its deep learning extension, Deep Q-Networks (DQN), famous for mastering Atari games from pixel inputs.
2. Policy-Based Methods, which directly learn a parameterized policy. This thread begins with the REINFORCE algorithm, introduces the Policy Gradient Theorem, and evolves into more stable and powerful Actor-Critic methods and the state-of-the-art Proximal Policy Optimization (PPO).

Building on these core online learning paradigms, the course addresses the practical challenge of learning from existing data. This includes Imitation Learning, where an agent learns from expert demonstrations through techniques like Behavior Cloning and overcomes its limitations with interactive methods like DAGGER. The more general problem of learning from a static, pre-existing dataset is tackled in Offline RL, highlighting the critical challenge of distribution shift and the principle of pessimism to ensure safe and reliable policy improvement.
A significant portion of the course is dedicated to the modern alignment techniques that power today's large language models. This begins with Inverse Reinforcement Learning (IRL), specifically Max Entropy IRL, as a method for inferring an expert's reward function. This leads directly to the contemporary framework of Reinforcement Learning from Human Feedback (RLHF), where a reward model is trained on human preferences and optimized with PPO. The course covers the latest advancements, such as Direct Preference Optimization (DPO), a more direct and efficient method that bypasses the explicit reward modeling stage.
Finally, the course synthesizes these concepts by examining advanced methods for efficient exploration and planning. It formalizes the exploration problem using Multi-Armed Bandits, introducing the concept of regret minimization and key algorithms like Upper Confidence Bounds (UCB) and Thompson Sampling. The grand finale showcases the integration of deep learning with powerful search techniques in the form of Monte Carlo Tree Search (MCTS), the engine behind the historic achievements of AlphaGo and AlphaZero. The course concludes with a critical discussion on Value Alignment, examining the normative and philosophical challenges of defining the very reward signals we ask our agents to optimize, ensuring the development of safe and beneficial AI.

L1: Introduction

The lecture begins with Professor Emma Brunskill welcoming students to CS234, a course on Reinforcement Learning. She defines reinforcement learning as an automated agent learning to make good decisions through experience. This simple statement, she explains, encompasses complex and challenging concepts that have been a focus of research for over a decade.
Why Study Reinforcement Learning?
Two primary motivations for studying reinforcement learning are presented:

1. A Core Component of Intelligence: The ability to make decisions is fundamental to general artificial intelligence. While perceptual machine learning (e.g., image recognition) has seen enormous progress, intelligence also requires acting on perceptions. The challenge of learning to make good decisions under uncertainty has been a central question since the 1950s, pioneered by Richard Bellman.
2. Practical Applications and Successes: Over the last decade, reinforcement learning has achieved unprecedented performance in various important domains.

Key Success Stories:

• AlphaGo: A team at DeepMind created an AI agent that defeated the world's best human players in the complex board game of Go, a feat achieved much earlier than anticipated. This was accomplished by combining reinforcement learning with Monte Carlo Tree Search.
• Fusion Science: A 2022 Nature paper demonstrated the use of deep reinforcement learning to control plasma within a fusion vessel, offering a more flexible approach than previously imagined.
• COVID-19 Testing: In Greece, a system developed by Stanford graduate Hamsa Bastani used reinforcement learning to determine who to test at the border to control the epidemic, effectively allocating limited resources in a data-driven way.
• ChatGPT: The widely-known language model leverages reinforcement learning to enhance its capabilities significantly. The training process involves three main steps:
  1. Imitation Learning (Behavior Cloning): The model is first trained on prompt-response examples written by humans, treating it as a supervised learning problem.
  2. Learning a Reward Model: To improve upon the initial model, human preference data is collected by asking people to rank different AI-generated responses. This data is used to train a reward model that can predict the quality of a given output.
  3. Reinforcement Learning from Human Feedback (RLHF): The initial language model is then fine-tuned using reinforcement learning, with the learned reward model providing the feedback signal. This approach, while not new, was shown by ChatGPT to make a massive difference in performance.

The Rise and Skepticism of Reinforcement Learning
Professor Brunskill highlights the exponential growth in reinforcement learning research, as evidenced by the increasing number of published papers, especially after successes with Atari video games and AlphaGo. However, she also introduces a skeptical viewpoint from Yann LeCun, a Turing Award winner, who in 2016 famously described machine learning as a cake. In his analogy:

• The Cake: Unsupervised learning (e.g., representation learning from unlabeled data).
• The Icing: Supervised learning.
• The Cherry: Reinforcement learning, implying it plays a minor, albeit important, role.

Core Concepts of Reinforcement Learning
The lecture identifies four defining elements of reinforcement learning:

1. Optimization: The goal is to find the best way to make decisions, which requires an explicit notion of utility or reward to compare different solutions.
2. Delayed Consequences: Actions taken now can have significant effects much later. This presents challenges in both planning (figuring out the optimal sequence of actions) and learning (attributing a later outcome to a specific earlier action, known as the temporal credit assignment problem).
3. Exploration: The agent learns about the world only through its own experiences. This means it only gets data for the actions it tries, creating a "censored information" problem. It must balance exploring new actions to gather information with exploiting known good actions.
4. Generalization: In complex, large-scale problems (like video games with a vast number of possible screen states), it's impossible to have a pre-programmed response for every scenario. The agent must generalize from its experiences to make good decisions in new situations, often using tools like deep neural networks.

Reinforcement Learning vs. Other AI Fields
The lecture contrasts reinforcement learning with related areas:

• AI Planning: Involves optimization and delayed consequences but typically assumes a known model of the world.
• Supervised & Unsupervised Learning: Involve generalization and learning from data, but supervised learning relies on labeled examples, while unsupervised learning has no explicit labels or notion of utility.
• Imitation Learning: Reduces reinforcement learning to a supervised learning problem by using expert demonstrations. While powerful, as seen in the first step of ChatGPT's training, it is limited by the performance of the expert. Reinforcement learning has the potential to surpass expert performance, as demonstrated by AlphaGo discovering novel strategies.

Course Logistics and Structure
The course aims to equip students with the ability to define key RL features, formulate problems, implement common algorithms, and evaluate their quality. The main topics include:

• Markov Decision Processes (MDPs) and Planning
• Model-Free Policy Evaluation and Control
• Policy Search (e.g., PPO)
• Offline Reinforcement Learning, including RLHF and Direct Preference Optimization (a new addition to the course)
• Exploration and Advanced Topics

The professor emphasizes the importance of active learning ("engage practice")—such as working on homework, problems, and the final project—over passive activities like re-watching lectures.
Formulating a Reinforcement Learning Problem: The AI Tutor
An interactive exercise challenged students to formulate an AI tutoring system as an RL problem. The agent's goal is to teach a student addition and subtraction by providing practice problems, receiving a +1 reward for a correct answer and -1 for an incorrect one.
Key discussion points from the students included:

• State Space: Could be represented as the student's mastery level of each topic (e.g., a vector [0.9, 0.4]) or as the complete history of questions and answers.
• Action Space: The agent can choose to give an "addition problem" or a "subtraction problem."
• Reward Hacking: The setup creates a potential flaw. An agent maximizing this reward would learn to only give very easy problems that the student is likely to get right, thus earning consistent positive rewards without actually ensuring the student learns the harder material. This illustrates the challenge of designing reward functions that align with the true desired outcome.

Sequential Decision-Making Formalism
The lecture formally introduces the sequential decision-making framework:

• An agent takes an action in the world.
• The world updates and emits an observation and a reward.
• This creates a feedback loop where the agent's goal is to maximize the total expected future reward.

The Markov Assumption: A core simplifying assumption is that the future is independent of the past, given the present. This means the current state is a sufficient statistic of the entire history. This allows the agent to make decisions based only on the current state, rather than needing to process everything that has ever happened.
Key Definitions:

• Markov Decision Process (MDP): The primary formal framework for RL, characterized by states, actions, rewards, and a dynamics model.
• Dynamics Model (or Transition Model): Specifies the probability of transitioning from one state to another, given an action (P(s' | s, a)).
• Reward Model: Predicts the expected immediate reward from being in a state and taking an action (R(s, a)).
• Policy (π): A mapping from states to actions (π(a|s)), defining the agent's behavior.
• Evaluation vs. Control: Two central tasks. Evaluation is determining the value of a given policy, while Control is finding the optimal policy.

The lecture concludes by introducing Markov Reward Processes (MRPs)—which are like MDPs but without actions—as a stepping stone to understanding policy evaluation. It also defines the return as the discounted sum of future rewards and the value function as the expected return from a given state. The discount factor (γ) is introduced as a mechanism to prioritize immediate rewards over distant future ones and to ensure that infinite sums of rewards remain bounded.

L2: Tabular MDP Planning

The second lecture focuses on methods for finding optimal decision-making policies when a complete model of the environment (a Markov Decision Process, or MDP) is known. This is often referred to as planning.
1. Refresh Your Understanding & Clarifications

• Discount Factor (γ): The lecture began by clarifying a common point of confusion. A large discount factor (e.g., γ close to 1) means that long-term rewards are weighted more heavily, not less. A gamma of 0 would make an agent completely "myopic," caring only about the immediate reward. A gamma of 1 would weight all future rewards equally to the present reward.
• Monotonic Improvement: A key conceptual question was introduced: Is it possible to design algorithms that guarantee the decision policy gets progressively better with more computation? This theme is explored throughout the lecture.
• Optimization in Machine Learning: Professor Brunskill clarified that while she previously distinguished reinforcement learning by its focus on "optimization," this can be confusing since all machine learning fields involve optimizing a metric (like minimizing a loss function). Students were advised to disregard that specific distinction for now.

2. Rationale for Starting with Simple, Tabular Models
The lecture explains that starting with small, discrete environments like the "seven-state Mars rover" is crucial. These simple cases make it easier to understand the fundamental concepts of decision processes. These core ideas are the building blocks for the advanced, state-of-the-art algorithms used to solve complex problems like controlling robots, optimizing Large Language Models (LLMs) with RLHF, and mastering games like Go.
3. From Markov Reward Processes (MRPs) to MDPs

• Solving for the Value of an MRP: The lecture revisited how to calculate the value function (the expected discounted sum of future rewards) for an MRP, which is an MDP without actions. Two methods were presented:
  1. Analytic Solution: For small state spaces, the value function V can be solved directly using a matrix inverse: V = (I - γP)⁻¹R, where P is the transition matrix and R is the reward vector. This is computationally expensive, scaling with the cube of the number of states (O(N³)).
  2. Iterative Dynamic Programming: A more practical method involves initializing the value of all states to zero and then repeatedly applying the Bellman equation as an update rule until the values converge. This is less expensive per iteration (O(N²)).
• Introducing Markov Decision Processes (MDPs): An MDP adds actions to the MRP framework. The dynamics (state transitions) and rewards now depend on the action taken by the agent. An MDP is fully defined by a set of states (S), actions (A), a dynamics model, a reward model, and a discount factor (γ).

4. Policy Evaluation: How Good is a Given Policy?
A key insight is that an MDP combined with a fixed policy (a rule for choosing actions in each state) simplifies into an MRP. This is because the policy removes the element of choice; for any given state, the dynamics and rewards become fixed averages based on the policy's action probabilities.
This allows us to use the same iterative dynamic programming approach from MRPs to solve for Vπ, the value function of a specific policy π. This process is known as policy evaluation.
5. Policy Iteration: Finding the Optimal Policy
Policy iteration is the first algorithm introduced that guarantees monotonic improvement. It's an iterative process that alternates between two steps:

1. Policy Evaluation: Given the current policy, πᵢ, calculate its value function, Vπᵢ, until it converges.
2. Policy Improvement: Use the calculated value function Vπᵢ to find a better policy, πᵢ₊₁. This is done by calculating the Q-function (or state-action value function), Qπᵢ(s, a), which represents the value of taking action a in state s and then following policy πᵢ forever after. The new, improved policy is then defined as the one that greedily chooses the action with the highest Q-value in each state.

This loop repeats. The Policy Improvement Theorem proves that the new policy is guaranteed to be better than or equal to the old one. Since there is a finite number of deterministic policies (|A|^|S|), and the algorithm never revisits a worse policy, policy iteration is guaranteed to converge to the optimal policy.
6. Value Iteration: An Alternative Approach
Value iteration is another fundamental dynamic programming algorithm for finding the optimal policy. It differs from policy iteration in its core philosophy:

• Policy Iteration maintains a complete (but suboptimal) policy for an infinite horizon at each step.
• Value Iteration maintains the optimal value function, but for a progressively longer finite horizon at each step.

The algorithm works by repeatedly applying the Bellman backup operator for the optimal value function. This update rule finds the value of a state by taking the maximum over all possible actions of the expected value from taking that action.
Vₖ₊₁(s) = maxₐ [ R(s,a) + γ Σ P(s'|s,a) Vₖ(s') ]
Each iteration k can be interpreted as finding the optimal value for a k-step decision problem.
7. Convergence of Value Iteration
The convergence of value iteration is guaranteed by the Contraction Mapping Theorem. The lecture provided a proof showing that the Bellman backup operator is a γ-contraction. This means that with each application of the operator, the maximum difference (L-infinity norm) between any two value function vectors is guaranteed to shrink by a factor of γ. Since γ < 1, repeated application of the operator will cause the value function to converge to a unique fixed point, which is the optimal value function, V*. Once V* is found, the optimal policy can be extracted by choosing the action that maximizes the expected future value from each state.
8. Concluding Concepts

• Monte Carlo Simulation for Evaluation: As an alternative to iterative updates, policy evaluation can also be done by simply simulating a large number of episodes using the policy and averaging the collected returns. This method is particularly useful in very large state spaces where summing over all next states is infeasible.
• Finite Horizons: The lecture briefly noted that for problems with a fixed, finite number of steps, the optimal policy may become non-stationary, meaning the best action to take in a state could depend on how many time steps are left.
• Key Takeaways: Students should understand the definitions of MDPs, Bellman operators, Q-values, and policies. They should be able to implement and understand the properties (e.g., convergence, computational complexity) of both policy iteration and value iteration.

L3: Policy Evaluation

The lecture transitions from "planning," where the agent has a perfect model of the world (an MDP), to "model-free learning," where the agent must learn the value of its actions through direct experience and interaction with the environment.
1. Refresh Your Understanding Poll
The lecture began with a poll reviewing concepts from the previous session on value iteration and policy iteration in the tabular (discrete state/action) setting.

• Question 1: Asymptotically, value iteration and policy iteration are guaranteed to compute the optimal policy.
  • Answer: True. The class correctly identified that with enough computation, both algorithms are guaranteed to converge to the optimal solution in a finite, tabular MDP.
• Question 2: The number of iterations required for value iteration is always less than or equal to the total number of possible deterministic policies (
  • Answer: False. This question had a more divided response. The correct answer is false.
  • Explanation: Policy iteration improves upon a policy in each step, and since it never revisits a policy, it is guaranteed to terminate in at most |A|^|S| iterations. Value iteration, however, updates the value function until it converges. A simple counter-example was provided: an MDP with one state, one action, a reward of 1, and γ=0.9. Policy iteration would find the single optimal policy in one step. Value iteration, however, would need many iterations for the value function to converge from its initial value (e.g., 0) to the true value of 10 (1 / (1 - 0.9)), as it only approaches this value geometrically. This illustrates that while both converge, their computational paths can differ significantly.

2. Introduction to Model-Free Learning
The core of the lecture is model-free policy evaluation: determining the value of a fixed policy (Vπ) without knowing the environment's dynamics or reward models. The agent learns solely from episodes of experience, which are sequences of (state, action, reward, next_state) tuples.
3. Monte Carlo (MC) Policy Evaluation
Monte Carlo is the simplest approach to model-free evaluation.

• Core Idea: The value of a state is the expected return. Therefore, we can estimate this value by simply averaging the empirical returns observed from that state over many episodes.
• Key Characteristics:
  • It must be used in episodic tasks, as it requires waiting until the end of an episode to calculate the total return (G).
  • It does not assume the Markov property. It simply averages the outcomes of entire trajectories, regardless of the underlying state structure.
• Algorithms:
  • First-Visit MC: For each episode, the return is only used to update the value of a state the first time it was visited in that trajectory.
  • Every-Visit MC: The return is used to update the value of a state every time it was visited.
  • Incremental MC: A more practical version that updates the running average after each episode using a learning rate (α):
    V(s) ← V(s) + α [G - V(s)]
• Properties:
  • First-visit MC provides an unbiased estimate. Both methods are consistent, meaning they converge to the true value function as the number of visits to each state approaches infinity.
  • The main drawback is high variance, as the return depends on the entire sequence of random actions and transitions that follow a state.

4. Temporal Difference (TD) Learning
TD learning is presented as a central and novel idea in reinforcement learning, combining the sampling of Monte Carlo with the bootstrapping of Dynamic Programming.

• Core Idea: Instead of waiting until the end of an episode, TD updates the value of a state (s) after just one time step. It uses the observed reward (r) and its current estimate of the next state's value (V(s')) to form a target for the update.
• The TD(0) Update Rule:
  V(s) ← V(s) + α [r + γV(s') - V(s)]
  • TD Target: r + γV(s'). This is a bootstrapped estimate of the return.
  • TD Error: r + γV(s') - V(s). This measures the difference between the current estimate and the one-step lookahead estimate.
• Key Characteristics:
  • Bootstrapping: It updates its estimate based on another estimate (V(s')), just like Dynamic Programming.
  • Model-Free: It learns from experience without a model, just like Monte Carlo.
  • It can be used in non-episodic (continuous) settings.
  • It has lower variance than MC but is biased because the initial estimate V(s') may be inaccurate.
  • It is a consistent estimator, converging to the true Vπ provided the learning rate conditions are met.

5. Certainty Equivalence (Model-Based) Approaches
This method serves as a bridge between model-free and model-based techniques.

• Core Idea: Use the collected experience to learn an approximate MDP model first.
  1. Estimate the dynamics model (P(s'|s,a)) by counting the frequency of transitions.
  2. Estimate the reward model (R(s,a)) by averaging observed rewards.
  3. Treat this learned model as if it were the true model (the "certainty equivalence" assumption).
  4. Use a planning algorithm like policy evaluation (from the previous lecture) on this model to compute the value function.
• Properties: This approach is very data-efficient because one transition can be used to update the model, which then allows DP to propagate that information to many other states. However, it is computationally expensive.

6. Batch Policy Evaluation: MC vs. TD
A key example was used to illustrate the fundamental difference between how MC and TD learn from a finite, fixed "batch" of data.

• Scenario: A simple two-state MDP (A and B) with 8 observed episodes. Crucially, state A is only ever seen once, in a trajectory A (r=0) -> B (r=0). State B is seen 8 times, with a reward of 1 in 6 episodes and 0 in 2 episodes.
• The Question: If we run TD and MC updates over this fixed dataset an infinite number of times, what values will they converge to for V(A) and V(B)?
• The Result:
  • V(B): Both TD and MC converge to 0.75 (the average observed reward of 6/8).
  • V(A): Here they diverge dramatically.
    • Monte Carlo converges to 0. It minimizes the mean squared error against the observed returns. The only return ever observed following a visit to state A was 0.
    • TD converges to 0.75. TD leverages the assumed Markov structure of the problem. Its update for V(A) is based on the TD target r + γV(B). Since r was 0 and V(B) converges to 0.75, V(A) also converges to 0.75.
• The Insight: TD converges to the solution you would get from a certainty equivalence approach (building a maximum likelihood model and solving it). It explicitly uses the Markov assumption to relate the value of a state to the value of its successor. Monte Carlo makes no such assumption and is purely driven by minimizing error on the observed sample returns.

L4: Q Learning and Function Approximation

The lecture transitions from evaluating a known policy to actively learning the optimal policy without a model of the environment. It builds from simple, tabular (discrete state/action) methods up to the seminal Deep Q-Network (DQN) algorithm that learned to play Atari games from pixel inputs.
1. Introduction & "Check Your Understanding" Poll

• Motivation: The lecture opens with a video of an AI agent learning to play the Atari game Breakout, demonstrating the power of the algorithms to be discussed. This work from DeepMind in 2014 was a landmark achievement, showing an agent could learn complex tasks directly from visual input.
• Poll Results & Key Insight:
  • A policy improvement step that takes the argmax over a Q-function results in a deterministic policy (assuming no ties).
  • A crucial follow-up question revealed a key challenge: If you follow this new deterministic policy, you will only gather data for the one action it prescribes in each state. You cannot learn the Q-values for any other actions in that state from this experience alone. This directly motivates the need for exploration.

2. The Challenge of Exploration vs. Exploitation
To learn an optimal policy, an agent faces a fundamental trade-off:

• Exploration: Trying new or seemingly suboptimal actions to gather information about the environment and potentially discover better strategies.
• Exploitation: Using its current knowledge to take the action it believes is best to maximize rewards.

A simple yet effective strategy to balance this is epsilon-greedy (ε-greedy):

• With probability 1-ε, the agent acts greedily, choosing the action that maximizes its current estimated Q-value.
• With probability ε, the agent acts randomly, choosing any action with uniform probability.
  This ensures that all actions continue to be tried, allowing their Q-values to be estimated and updated.

3. On-Policy Monte Carlo Control
This is the first model-free control algorithm discussed. It follows the pattern of generalized policy iteration (alternating evaluation and improvement).

• Algorithm:
  1. Start with a random policy π.
  2. Loop forever (over episodes):
     a. Generate a full episode by following the current policy π.
     b. For every state-action pair (s, a) visited in the episode, calculate the return G (the sum of discounted rewards from that point to the end).
     c. Update the Q-value estimate: Q(s, a) ← Q(s, a) + α [G - Q(s, a)].
     d. Improve the policy: Make the policy ε-greedy with respect to the updated Q-function.
• Convergence (GLIE): This method is guaranteed to converge to the optimal policy, Q*, under the condition of GLIE (Greedy in the Limit of Infinite Exploration). This means two things must happen:
  1. All state-action pairs are explored an infinite number of times.
  2. The policy eventually becomes greedy (e.g., by slowly decaying ε towards 0).

4. Temporal Difference (TD) Control
TD methods update the Q-function after every single step, rather than waiting for the end of an episode like Monte Carlo. This makes them more suitable for continuous, non-episodic tasks.

• Name Origin: The update uses the tuple (S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}), hence SARSA.
• Update Rule: The key is that the target for the update uses the Q-value of the next action actually taken by the policy.
  Q(s, a) ← Q(s, a) + α [r + γQ(s', a') - Q(s, a)]
• On-Policy: SARSA is "on-policy" because it learns the value of the policy it is currently following (including its exploratory actions). It evaluates and improves the same ε-greedy policy it uses to act. It also converges to Q* under GLIE conditions.
• Off-Policy: Q-learning is a breakthrough because it allows an agent to learn about the optimal (greedy) policy while behaving according to a different, more exploratory policy.
• Update Rule: The target for the update uses the maximum possible Q-value from the next state, regardless of what action was actually taken next.
  Q(s, a) ← Q(s, a) + α [r + γ *max*ₐ' Q(s', a') - Q(s, a)]
• The Power of Off-Policy: This max operator allows the algorithm to learn about the greedy policy even when it takes a random, exploratory step. It separates the policy being learned from the policy used for exploration.

5. Function Approximation
Tabular methods, which store a separate value for every state-action pair, are infeasible for problems with large or continuous state spaces (like Atari's pixel inputs). Function approximation (e.g., linear functions, deep neural networks) is used to generalize from seen states to unseen states.

• The Idea: The Q-function is represented by a parameterized function Q(s, a; w). The goal is to find the weights w that make this function a good approximation of the true Q-function.
• Training: This is framed as a supervised learning problem. We use stochastic gradient descent (SGD) to minimize the mean squared error between our network's prediction Q(s, a; w) and a "target" value. The target is provided by the MC or TD update rules.

6. Deep Q-Networks (DQN)
DQN successfully applied Q-learning with a deep convolutional neural network as the function approximator to play Atari games. This was challenging because combining Q-learning (which is off-policy and uses bootstrapping) with function approximation can be highly unstable. This instability is sometimes called The Deadly Triad.
DQN introduced two key innovations to achieve stability:

1. Experience Replay: Instead of using transitions immediately for training, they are stored in a large buffer (e.g., the last million transitions). For each training step, a random mini-batch of transitions is sampled from this buffer. This has two benefits:
   • It breaks the strong temporal correlations between consecutive samples, making the data more like the independent and identically distributed (IID) data that SGD works best with.
   • It greatly improves sample efficiency by allowing each piece of experience to be reused multiple times.
2. Fixed Q-Targets: The TD target (r + γ *max*ₐ' Q(s', a'; w)) creates a "moving target" problem because the weights w are updated at every step, which changes the target value itself. DQN solves this by using a separate target network with weights w⁻ to compute the target.
   • The main network (w) is updated via SGD at every step.
   • The target network (w⁻) is held fixed for many steps and is only periodically updated by copying the weights from the main network. This makes the training target much more stable.

An ablation study showed that while both techniques helped, Experience Replay provided the most significant performance boost, highlighting the critical importance of sample efficiency and breaking data correlations.

L5: Policy Search 1

The lecture shifts focus from value-based methods (like Q-learning), which learn a value function and derive a policy from it, to policy-based methods, which directly parameterize and optimize the policy itself.
1. "Refresh Your Understanding" Poll & Key Concepts
The lecture began by reviewing key concepts from the previous lectures on Q-learning and DQN.

• Batch Tabular Q-learning: When running Q-learning updates infinitely over a fixed, finite batch of data in a tabular setting, the algorithm is guaranteed to converge to the true Q-value, provided a suitable learning rate schedule is used. This is because there is no function approximation error.
• Batch TD vs. Certainty Equivalence: The values that batch TD-learning converges to are equivalent to those obtained by building a maximum likelihood model from the data (a "certainty equivalence" model) and then solving it with dynamic programming.
• DQN Convergence: DQN is not guaranteed to converge to the optimal Q-function, even with infinite iterations. This is due to several factors, including the "Deadly Triad" (off-policy learning, bootstrapping, and function approximation) and realizability. The chosen neural network architecture may not be capable of representing the true Q-function, leading to approximation errors that prevent convergence to the global optimum.

2. Introduction to Policy Search
Instead of learning a value function, policy search methods define the policy as a parameterized function π(a|s; θ) (e.g., a neural network with weights θ) and search for the parameters θ that maximize a performance objective, J(θ) (e.g., the expected total reward).

• Motivation & Influence: These methods are extremely influential and have been used in many state-of-the-art applications, including:
  • Robotics: Learning complex visuomotor policies directly from pixel inputs to perform manipulation tasks.
  • ChatGPT: Proximal Policy Optimization (PPO), a policy gradient method, was a key component in its training.

3. Advantages of Policy-Based Methods
Policy-based methods offer several advantages over purely value-based approaches:

1. Learning Stochastic Policies:
   • In some environments, the optimal policy is inherently stochastic. In the game of rock-paper-scissors, any deterministic policy is predictable and can be exploited. The optimal policy is a uniform random one.
   • In environments with partial observability or state aliasing (where different world states look identical to the agent), a stochastic policy can be superior. For example, if a robot cannot distinguish between two identical-looking junctions, the optimal strategy might be to randomly choose to go left or right to avoid getting stuck in a loop.
2. Better Convergence Properties: Policy gradient methods often have smoother updates and are more likely to converge to a good (though potentially local) optimum, whereas value-based methods with function approximation can sometimes suffer from instabilities and oscillations.
3. Effectiveness in High-Dimensional/Continuous Action Spaces: It is often easier to parameterize a policy that outputs actions in a continuous space (e.g., the torque for a robot joint) than it is to find the max over a continuous action space as required by Q-learning.

4. The Policy Gradient Theorem: Derivation
The core of the lecture was deriving a computable expression for the policy gradient, ∇_θ J(θ), which tells us how to change the policy parameters θ to improve performance.

1. The Objective: The objective J(θ) is defined as the expected reward over all possible trajectories τ that can be generated by policy π_θ.
   J(θ) = E_τ[R(τ)] = Σ_τ P(τ; θ) R(τ)
2. The Log-Derivative Trick: The key mathematical insight is the likelihood ratio or log-derivative trick. It allows the gradient to be rewritten as an expectation that can be estimated via sampling.
   ∇_θ J(θ) = E_τ[R(τ) * ∇_θ log P(τ; θ)]
3. Simplification: The log probability of a trajectory, log P(τ; θ), is expanded. Crucially, the term related to the environment's dynamics P(s'|s, a) does not depend on the policy parameters θ, so it drops out of the gradient. This is a profound result: the policy gradient does not depend on the dynamics model of the environment, making it truly model-free. The final expression depends only on the policy itself:
   ∇_θ log P(τ; θ) = Σ_{t=0}^T ∇_θ log π_θ(a_t|s_t)

5. The REINFORCE Algorithm (Monte Carlo Policy Gradient)
The derived gradient leads to the REINFORCE algorithm, a foundational Monte Carlo policy gradient method.

• Initial Gradient: A first-pass application of the theorem suggests weighting the sum of all action score functions by the total reward for the entire episode.
• Leveraging Causality: A crucial improvement is recognizing that an action taken at time t cannot affect rewards received before time t. Therefore, the score function for the action at t, ∇_θ log π_θ(a_t|s_t), should only be multiplied by the return from that point onward, G_t = Σ_{k=t}^T r_k.
• REINFORCE Update Rule: This leads to an update rule that moves the parameters in the direction of the estimated gradient:
  θ ← θ + α * G_t * ∇_θ log π_θ(a_t|s_t)
• Algorithm Flow:
  1. Generate a complete episode using the current policy π_θ.
  2. For each time step t in the episode (from t=0 to T):
     a. Calculate the return G_t.
     b. Update the policy parameters θ using the rule above.

6. Variance Reduction: Baselines
While REINFORCE is an unbiased estimator of the policy gradient, it suffers from very high variance because the Monte Carlo returns G_t can be noisy. A powerful technique to reduce this variance is to introduce a baseline.

• The Idea: Subtract a value b(s_t) that depends only on the state from the return. The update becomes:
  θ ← θ + α * (G_t - b(s_t)) * ∇_θ log π_θ(a_t|s_t)
• Key Property: As long as the baseline b does not depend on the action a, it can be proven that this does not introduce any bias into the gradient estimate. The proof was deferred to the next lecture.
• Intuition: The term (G_t - b(s_t)) is often called the advantage. The baseline acts as an "expected" return for that state. The update now increases the probability of actions that lead to a better than expected return and decreases the probability of actions that lead to a worse than expected return. This centering of the returns significantly stabilizes the learning process and reduces the variance of the gradient estimate, leading to faster convergence.

L6: Policy Search 2

The lecture continues the exploration of policy gradient methods, moving from the foundational REINFORCE algorithm to more advanced, practical, and state-of-the-art techniques, culminating in Proximal Policy Optimization (PPO).
1. "Refresh Your Understanding" Poll & Review
The lecture started by reviewing key concepts about policy gradients from the previous session.

• Policy Gradient Objective: The goal of policy gradient methods is to adjust the policy parameters (θ) to increase the probability of actions/trajectories that lead to high rewards. This is achieved by moving θ in the direction of the gradient, which is an expectation of the score function (∇_θ log π_θ) weighted by the return or Q-value.
• REINFORCE & Baselines: The REINFORCE algorithm provides an unbiased estimate of this gradient using Monte Carlo returns. Adding a baseline (a value b(s) that depends only on the state) was introduced as a powerful variance reduction technique that does not add bias to the gradient estimate.

2. Proving the Baseline is Unbiased
The lecture provided a formal proof for why subtracting a state-dependent baseline b(s_t) does not introduce bias into the policy gradient estimate.

• Goal: To show that E[b(s_t) * ∇_θ log π_θ(a_t|s_t)] = 0. If this is true, then subtracting this term from the gradient estimator does not change its expected value.
• Proof Sketch:
  1. The expectation is rewritten as a sum over actions a weighted by the policy's probability π_θ(a|s).
  2. The ∇_θ log π_θ(a|s) term is replaced by (∇_θ π_θ(a|s)) / π_θ(a|s) using the log-derivative trick in reverse.
  3. The π_θ(a|s) terms in the numerator and denominator cancel out.
  4. The gradient and the sum over actions are swapped.
  5. The sum over all actions of the policy Σ_a π_θ(a|s) is equal to 1, by definition of a probability distribution.
  6. The gradient of a constant (1) is 0.

This elegant proof demonstrates that any function of the state can be used as a baseline without biasing the gradient, opening the door for effective variance reduction.
3. Actor-Critic Methods
A natural and effective choice for a baseline is the state-value function, V(s). This leads to actor-critic methods, which learn both a policy (the "actor") and a value function (the "critic") simultaneously.

• Actor (Policy Decides which action to take. Its parameters θ are updated using the policy gradient.
• Critic (Value Function Evaluates the actions taken by the actor. Its parameters w are updated using methods like Temporal Difference (TD) learning.
• Advantage Function: The critic provides a baseline and helps compute the advantage function: A(s, a) = Q(s, a) - V(s). The actor is then updated to increase the probability of actions with a positive advantage.
• Bias-Variance Trade-off (n-step estimators): The advantage A(s, a) can be estimated in different ways, creating a bias-variance trade-off.
  • High Bias, Low Variance: Using a 1-step TD target (r + γV(s') - V(s)). This relies heavily on the (potentially inaccurate) bootstrapped value estimate.
  • Low Bias, High Variance: Using a full Monte Carlo return (G_t - V(s)). This is an unbiased estimate of the true advantage but is noisy due to the long sequence of stochastic events.
  • n-step returns provide a way to interpolate between these two extremes.

4. Challenges with Vanilla Policy Gradients
Despite these improvements, vanilla policy gradient methods face significant challenges that limit their practical effectiveness:

1. Poor Sample Efficiency: These methods are typically on-policy, meaning they can only use data generated from the current policy to compute the gradient. After taking a single gradient step, all the old data must be discarded, and new samples must be collected. This is extremely inefficient.
2. Destructive Step Sizes: The choice of learning rate (step size) is critical and difficult.
   • Too large: A large step in parameter space (θ) can lead to a massive, destructive change in the policy distribution, causing performance to collapse. The agent might find itself in a region of the state space from which it cannot recover.
   • Too small: The agent learns too slowly.
   • The core issue is that distance in parameter space does not correspond well to distance in policy space. A small change in θ can cause a huge change in the action probabilities.

5. Towards Advanced Methods: Monotonic Improvement
The goal of advanced policy gradient methods is to address these challenges. The ideal algorithm would:

1. Use each batch of data more efficiently, allowing for multiple update steps.
2. Take the largest possible step that is guaranteed to improve the policy, preventing catastrophic performance collapse.

This led to the derivation of the Performance Difference Lemma, a key theoretical result that relates the performance of a new policy (π') to an old one (π). It shows that the improvement in performance is equal to the expected advantage of the new policy's actions, evaluated using the old policy's Q-function, and averaged over the state distribution of the new policy.
A local approximation allows this to be estimated using data from the old policy, but the quality of this approximation degrades as the new and old policies diverge. The divergence is measured by the KL Divergence, a measure of the difference between two probability distributions.
6. Proximal Policy Optimization (PPO)
PPO is a state-of-the-art algorithm that operationalizes these theoretical insights in a simple and effective way. It aims to maximize the policy improvement objective while constraining how much the policy is allowed to change. The most common variant of PPO uses a clipped objective function.

• The Ratio: Let r_t(θ) = π_θ(a_t|s_t) / π_{θ_old}(a_t|s_t) be the ratio of the probability of taking an action under the new and old policies.
• The Clipped Objective: Instead of just maximizing r_t(θ) * A_t, PPO maximizes a pessimistic bound:
  L^{CLIP}(θ) = E[ min( r_t(θ)A_t, clip(r_t(θ), 1-ε, 1+ε)A_t ) ]
• How it Works:
  • If the advantage (a good action), the objective increases with the ratio r_t(θ). However, the clip function prevents the ratio from getting too large (e.g., larger than 1+ε). This stops the algorithm from making an overly aggressive update in a favorable direction.
  • If the advantage (a bad action), the objective is made "more negative" as r_t(θ) decreases towards zero. However, the clip function prevents the ratio from getting too small (e.g., smaller than 1-ε). This stops the algorithm from making an overly aggressive update to avoid a bad action.

In essence, the clipping removes the incentive for the policy to change too drastically from the old policy, creating a "trust region" where the updates are more stable. This simplicity and robustness have made PPO one of the most widely used reinforcement learning algorithms.

L7: Policy Search 3

This lecture concludes the discussion on advanced policy gradient methods, focusing on the theoretical underpinnings of Proximal Policy Optimization (PPO), and then introduces a new paradigm: Imitation Learning.
1. "Refresh Your Understanding" Poll & Review
The lecture started with a poll reviewing key concepts of policy gradient methods:

• Policy Gradient Objective: Confirmed that the objective is to move the policy parameters θ in a direction that increases the log-probability of actions that lead to high returns.
• Baselines: A baseline term is a crucial variance reduction technique. It helps stabilize the learning process by centering the returns, allowing the agent to learn based on whether an action was better or worse than expected.
• Initialization: Policy gradient methods cannot be initialized with a deterministic policy. A deterministic policy provides no exploration, meaning it can never learn about the value of actions it isn't currently taking, and can therefore get permanently stuck in a suboptimal policy.
• Monotonic Improvement: Standard policy gradient methods are not guaranteed to monotonically improve the policy. A poorly chosen step size can lead to a catastrophic drop in performance.

2. Generalized Advantage Estimation (GAE)
The lecture introduced Generalized Advantage Estimation (GAE) as a sophisticated technique for estimating the advantage function, which is critical for the performance of actor-critic and policy gradient algorithms.

• The Bias-Variance Trade-off: The advantage can be estimated using different targets, creating a trade-off:
  • 1-step TD Target: Low variance but high bias (due to bootstrapping from an imperfect value function V).
  • Monte Carlo Target: Low bias but high variance (due to the long sequence of stochastic events in a full return).
• The GAE Idea: GAE elegantly blends all possible n-step estimators into one. It computes an exponentially-weighted average of the n-step TD errors (δ). This is controlled by a new hyperparameter, λ.
  • When λ=0, GAE reduces to the 1-step TD estimator (high bias, low variance).
  • When λ=1, GAE is equivalent to the Monte Carlo estimator (low bias, high variance).
• Practical Implementation (Truncated GAE): In practice, instead of waiting for the end of a long episode, a truncated version is used. The agent collects a fixed number of steps (e.g., T=200), computes the GAE target over that horizon, and then performs an update. This makes the algorithm more practical and allows for more frequent updates.

3. Monotonic Improvement Theory for PPO
The lecture revisited the core theoretical motivation for PPO. The goal is to take the largest possible step that is guaranteed to improve the policy.

• Performance Difference Lemma: This lemma provides a lower bound on the performance improvement of a new policy π' relative to an old one π. The bound consists of the expected advantage of the new policy's actions (using an off-policy estimate with importance sampling) minus a penalty term proportional to the KL Divergence between the two policies.
  J(π') - J(π) ≥ L(π, π') - C * D_KL(π, π')
• The Majorize-Maximize Algorithm: The proof showed that if you choose the new policy π_{k+1} to be the one that maximizes this lower bound, you are guaranteed to achieve monotonic improvement.
  • J(π_{k+1}) - J(π_k) ≥ L(π_k, π_{k+1}) - C * D_KL(...)
  • Since π_{k+1} maximizes the right-hand side, its value must be greater than or equal to the value for any other policy, including π_k itself.
  • For π_k, both the L term and the D_KL term are zero.
  • Therefore, L(...) - C*D_KL(...) ≥ 0, which means J(π_{k+1}) ≥ J(π_k).
• Theory vs. Practice: While theoretically sound, directly optimizing this bound leads to extremely small, conservative step sizes, making it impractical. PPO and other trust region methods use this theory as inspiration but implement more practical heuristics (like the clipped objective) to approximate this constrained optimization.

4. Introduction to Imitation Learning
The lecture then shifted to a new topic: Imitation Learning, which attempts to reduce reinforcement learning to a simpler supervised learning problem.

• Motivation: In many real-world scenarios (e.g., self-driving cars, robotics, surgery), collecting online data via trial-and-error is expensive, dangerous, or impractical. However, we often have access to a large amount of expert demonstrations (trajectories of states and actions from a skilled human).
• Problem Setup:
  • We are given a set of expert trajectories (s_0, a_0, s_1, a_1, ...)
  • Crucially, there is no explicit reward function. The "goodness" of an action is implicit in the expert's choices.
• Goal: Learn a policy π that mimics the expert's behavior.
• The Idea: The simplest form of imitation learning is Behavior Cloning. It treats the problem as a standard supervised learning task.
  • The states s_t from the expert trajectories are the inputs (features).
  • The actions a_t taken by the expert are the outputs (labels).
  • Any supervised learning algorithm (e.g., a deep neural network) can be used to learn a policy π(a|s) that maps states to actions.
• Early Successes: This approach had early successes, such as the ALVINN self-driving car project in the late 1980s. With massive datasets and powerful models (like RNNs that can use history), it can still be a very effective baseline.
• The Compounding Error Problem: Behavior Cloning suffers from a major flaw. The supervised learning model assumes that the training data (states visited by the expert) is identically distributed to the test data (states the learned policy will visit). This assumption is violated.
  • When the learned policy makes a small mistake, it deviates from the expert's trajectory and enters a part of the state space it has never seen before.
  • In these novel states, the policy is likely to make more mistakes, leading to a cascade of compounding errors that can drive the agent far off-course. The total number of errors can grow quadratically with the horizon length (O(T^2)), rather than linearly (O(T)).
• The Idea: DAGGER is an interactive algorithm designed to solve the compounding error problem.
  1. Train an initial policy π using behavior cloning on the expert data.
  2. Execute the current policy π in the environment to collect a new set of trajectories.
  3. Ask the expert to label the states in these new trajectories with the actions they would have taken.
  4. Aggregate this new labeled data with all the previous data.
  5. Go to step 1 and retrain the policy on the aggregated dataset.
• Benefit: By iteratively collecting data in the states the learned policy actually visits and getting expert corrections, DAGGER mitigates the distribution mismatch problem and can learn a much more robust policy.
• Limitation: It is extremely expensive, as it requires constant supervision and queries to a human expert.
• The Idea: Instead of just cloning the behavior, IRL tries to infer the underlying reward function R(s, a) that the expert is implicitly optimizing. If the reward function can be recovered, standard RL algorithms can then be used to find the optimal policy.
• The Identifiability Problem: This is an ill-posed problem. A poll showed the class's correct intuition: there are infinitely many reward functions for which a given policy is optimal (e.g., any positive scaling of a valid reward function, or a reward of zero everywhere).
• Feature Matching: To make the problem tractable, a common assumption is that the reward is a linear combination of state features R(s) = w^T φ(s). The problem then reduces to finding the weights w. The core principle is that the expert's policy must achieve a higher expected feature count than any other policy. The goal becomes finding a policy that matches the feature expectations of the expert.

L8: Offline RL 1

This lecture transitions from traditional reinforcement learning paradigms to methods that leverage human expertise and feedback, a critical component in training modern AI systems like large language models.
1. "Refresh Your Understanding" Poll & Review of Imitation Learning
The lecture began with a poll reviewing key concepts from imitation learning:

• Behavior Cloning: This method reduces RL to a supervised learning problem by learning a mapping from states to actions based on expert demonstrations. It does not require a dynamics model.
• DAGGER (Dataset Aggregation): This algorithm addresses the compounding error problem of behavior cloning but requires an expert to be constantly available ("in the loop") to label new trajectories generated by the learned policy. This is a significant limitation due to the high cost of human expertise.
• Inverse Reinforcement Learning (IRL): Instead of directly mimicking actions, IRL aims to infer the underlying reward function that explains the expert's behavior.

2. Motivation for RLHF and The Shift to Human Feedback
The lecture motivated the shift towards more direct forms of human feedback by highlighting the success of systems like ChatGPT. The ability of such models to generate complex, useful outputs (like runnable code for RLHF itself) is a recent breakthrough, largely enabled by techniques that go beyond simple imitation.

• The Goal: To build AI systems that are aligned with human values and intentions.
• The Method: To use human feedback, which is often easier to provide and more nuanced than writing a reward function or providing perfect demonstrations, to guide the learning process.

3. Max Entropy Inverse Reinforcement Learning (IRL)
This section provided a deep dive into a foundational IRL algorithm.

• The Identifiability Problem: A key challenge in IRL is that for any given set of optimal demonstrations, there are infinitely many reward functions that could explain that behavior. This makes the problem ill-posed.
• The Principle of Maximum Entropy: To resolve this ambiguity, Max Entropy IRL introduces a powerful principle: among all possible probability distributions over trajectories that are consistent with the expert's behavior, choose the one with the highest entropy. This is a form of Occam's razor, preferring the "simplest" or "most non-committal" explanation that fits the data.
• Mathematical Formulation: The problem is framed as a constrained optimization:
  1. Maximize: The entropy of a probability distribution over trajectories, P(τ).
  2. Subject to: A constraint that the expected feature counts under P(τ) must match the empirical feature counts from the expert's demonstrations.
• The MaxEnt Solution: Solving this constrained optimization problem using Lagrange multipliers reveals that the optimal probability of a trajectory is proportional to the exponent of its reward: P(τ) ∝ exp(R(τ)). This is a Boltzmann or Gibbs distribution, a form common in statistical mechanics.
• The Algorithm: This insight transforms the problem of finding a reward function into a maximum likelihood estimation problem. The algorithm iteratively performs the following steps:
  1. Given a current estimate of the reward function R_φ.
  2. Solve for the optimal policy π* in the MDP defined by that reward function (e.g., using value iteration). This requires a known dynamics model.
  3. Compute the state visitation frequencies under this policy π*.
  4. Update the reward function parameters φ by taking a gradient step to increase the likelihood of the expert trajectories. The gradient is essentially the difference between the expert's feature counts and the learned policy's feature counts.
  5. Repeat.
• Limitations & Extensions: The original Max Entropy IRL algorithm requires a known dynamics model and can be computationally intensive. Later work (e.g., by Chelsea Finn) extended these ideas to model-free settings with complex, high-dimensional state spaces and non-linear reward functions (like deep neural networks), making them much more practical.

4. From IRL to Reinforcement Learning from Human Feedback (RLHF)
The lecture then transitioned from inferring rewards from full demonstrations to learning from a more direct and often simpler form of human feedback: pairwise preferences.

• The "Sweet Spot" of Human Effort: Providing pairwise preferences ("Trajectory A is better than Trajectory B") is often cognitively easier for humans than providing full demonstrations or assigning absolute numerical scores to outcomes. It lies in a "sweet spot" between the low effort of providing existing data and the high effort of constant coaching (like in DAGGER).
• The Bradley-Terry Model: This is a classical model for relating latent (unobserved) scores or rewards to pairwise choices. It models the probability that a human will prefer option A over B as a sigmoid function of the difference in their underlying rewards: P(A > B) = σ(R(A) - R(B)).
• Learning from Preferences:
  1. Collect Data: Show humans pairs of trajectories (or in the case of LLMs, pairs of responses) and record which one they prefer.
  2. Learn a Reward Model: Frame the problem as a binary classification task. Use the preference data to train a reward model R_φ that maximizes the likelihood of the observed choices according to the Bradley-Terry model. This is typically done using a standard cross-entropy loss.
  3. Optimize a Policy: Once the reward model R_φ is trained, use a standard RL algorithm (like PPO) to train a policy π_θ that maximizes the expected reward from R_φ.

5. RLHF in Practice: Training LLMs
The lecture concluded by connecting this framework to the training of models like ChatGPT.

• The Three-Step Pipeline:
  1. Supervised Fine-Tuning (SFT): Train on high-quality demonstrations (behavior cloning).
  2. Reward Modeling: Collect pairwise preference data on model outputs and train a reward model.
  3. RL Fine-Tuning: Use PPO to optimize the SFT policy against the learned reward model.
• Multi-Task Learning: This process is effectively a form of multi-task RL. The reward model is not being trained for a single task (like a backflip) but to capture a general notion of "helpfulness" or "alignment" across the vast range of prompts a user might input.
• Evaluating Reward Models: The accuracy of the learned reward model is a critical factor and can be evaluated on a held-out validation set of preferences. Larger reward models trained on more data generally achieve higher accuracy.
• RLHF vs. Baselines: The RLHF process has been shown to yield substantial gains over simpler baselines, even when controlling for model size. However, simpler methods like "best-of-n sampling" (generating n responses and using the reward model to pick the best one) can also be very effective and serve as a strong baseline.

L9: Offline RL 2: DPO

This lecture, featuring guest speakers from the team that developed DPO, delves into the methods used to align Large Language Models (LLMs) with human preferences, moving from the complex RLHF pipeline to the more direct DPO approach.
1. Introduction & Motivation

• The Power of RLHF: The lecture begins by highlighting the extraordinary capabilities of modern LLMs like ChatGPT, which can generate functional code for complex concepts like RLHF itself. This performance leap is largely attributed to the application of reinforcement learning techniques to align powerful pre-trained models.
• The RLHF Pipeline: A recap of the now-classic three-stage RLHF process:
  1. Supervised Fine-Tuning (SFT): Start with a pre-trained LLM and fine-tune it on a dataset of high-quality, human-written demonstrations. This teaches the model the desired style and format and serves as the reference policy for the next stage.
  2. Reward Modeling: Use the SFT model to generate several responses to a given prompt. A human labeler then ranks these responses. This preference data is used to train a separate reward model that learns to predict which responses humans will prefer.
  3. RL Fine-Tuning: Use a policy gradient algorithm like PPO to fine-tune the SFT model. The objective is to maximize the score from the learned reward model while staying close to the original SFT policy (to prevent reward hacking).

2. Deep Dive into Reward Modeling

• Why Preferences, Not Scores? The lecture explains why collecting pairwise preferences (e.g., "Response A is better than Response B") is more effective than asking for absolute scores (e.g., "Rate this response from 1 to 10"). Humans are much better and more consistent at making relative judgments than assigning calibrated absolute scores.
• The Bradley-Terry Model: This classical model from choice theory is used to connect the latent (unobserved) reward scores of two options to the probability of a human preferring one over the other. The probability of preferring response y_w over y_l is modeled as a sigmoid of the difference in their rewards: P(y_w > y_l) = σ(r(y_w) - r(y_l)).
• Training the Reward Model: Using this model, training the reward model becomes a simple binary classification problem. The goal is to maximize the log-likelihood of the observed human preferences, which is equivalent to a standard cross-entropy loss.

3. The Problem with the RLHF Pipeline

• Complexity: The third stage, RL fine-tuning with PPO, is extremely complex. It involves sampling from the policy, getting rewards from the reward model, computing advantages, and performing policy updates, often requiring multiple copies of the large model in memory. This complexity motivated the search for a simpler alternative.

4. Direct Preference Optimization (DPO) - The Core Idea
The key insight of DPO is that the entire RLHF pipeline can be simplified into a single-stage, direct optimization problem on the preference data itself, bypassing the need for an explicit reward model and complex RL loops.

• The Optimal Policy Solution: The lecture starts with a known closed-form solution for the KL-constrained RL objective. The optimal policy π* can be expressed in terms of the reference policy π_ref and the reward function r(x, y):
  π*(y|x) ∝ π_ref(y|x) * exp(β * r(x, y))
  This is essentially re-weighting the reference policy by the exponentiated reward.
• Inverting the Relationship: This equation can be algebraically rearranged to express the reward function in terms of the optimal and reference policies:
  r(x, y) = β * log(π*(y|x) / π_ref(y|x)) + Z(x)
  This shows a direct mapping from policies to rewards.
• The DPO Loss Function: The brilliant step is to substitute this analytical expression for the reward back into the Bradley-Terry preference loss. When you take the difference in rewards r(y_w) - r(y_l), the intractable partition function Z(x) cancels out. This results in a loss function that depends only on the policies , not on an explicit reward model.
  L_DPO = -E[log σ(β * log(π(y_w|x)/π_ref(y_w|x)) - β * log(π(y_l|x)/π_ref(y_l|x)))]

This loss can be optimized directly with SGD, just like supervised fine-tuning. It implicitly maximizes the reward while satisfying the KL constraint, all in one step.
5. DPO in Practice & The "Reward Hacking" Problem

• Empirical Success: DPO has been widely adopted in the open-source community and by major labs (Mistral, Meta for Llama 3). It achieves strong performance, often outperforming complex PPO implementations.
• The Surprise of Reward Hacking: A key phenomenon discussed is reward hacking (or reward over-optimization). This occurs when an RL agent finds a way to exploit flaws in the proxy reward model to achieve a high score, even though the actual quality of its output (as judged by a human or a gold-standard model) stagnates or decreases.
• Reward Hacking in DPO: Surprisingly, DPO is also highly susceptible to reward hacking, even though it doesn't have an explicit reward model. The guest speakers presented new research showing that as DPO models are trained to a higher KL divergence from the reference policy, their performance (e.g., win rate against GPT-4) can start to decrease. The model learns to exploit biases in the preference data, such as a preference for longer, more verbose responses, and pushes this trend to an extreme.
• DPO vs. PPO Debate: This leads to a nuanced debate. PPO, being a weaker and less stable optimizer, might be less prone to extreme reward hacking simply because it's harder for it to fully exploit the reward function. DPO, being a more direct and powerful optimizer, can more easily find and exploit these "hacks."

6. The Future of Alignment
The lecture concluded by looking at the exciting future directions for alignment research:

• Making direct alignment methods like DPO more robust to reward hacking.
• Developing better online fine-tuning methods to efficiently gather preference data.
• Extending RLHF and DPO to other modalities like vision-language models, image/video generation (e.g., Stable Diffusion 3), and even scientific applications like protein synthesis.
• Tackling multi-turn interactions and agentic systems, which classical RLHF struggles with.
• Exploring game-theoretic approaches (like Nash Learning) that move beyond a single reward function to handle diverse and sometimes conflicting human preferences.

L10: Offline RL 3

This lecture pivots from learning with online interaction (like in PPO) or from expert demonstrations (imitation learning) to the more general and practical problem of learning from a fixed, static dataset of past experience. This is known as offline reinforcement learning, batch RL, or counterfactual policy learning.
1. "Refresh Your Understanding" Poll & Review
The lecture started with a review of Reinforcement Learning from Human Feedback (RLHF) and Direct Preference Optimization (DPO).

• Explicit Reward Models: The poll confirmed that RLHF learns an explicit reward model from preferences, whereas DPO is a direct method that bypasses the explicit reward modeling step, optimizing the policy directly on the preference data.
• Outperforming Demonstrations: Both DPO and RLHF can learn policies that are better than the best examples seen in the preference data. They learn an underlying reward function (explicitly or implicitly) and then use RL to find a policy that maximizes that reward, which can lead to novel, high-performing behaviors.
• Reference Policies: Both PPO and DPO use a reference policy (often the result of supervised fine-tuning) to regularize the learning process and prevent the learned policy from diverging too far from a sensible distribution of behavior.

2. Motivation: Can We Do Better Than Imitation?
The lecture motivated the need for offline RL by posing the question: "Can we learn a policy that is better than the one that generated the data?"

• Real-World Examples:
  • Education: An example from the lecturer's own research involved the game "Refraction," which teaches fractions. They used a dataset of 11,000 students playing with a random policy to learn a new, adaptive policy. The new policy, learned offline, was able to increase student persistence by 30%, demonstrating that it's possible to outperform the "expert" (or in this case, the data-generating) policy.
  • Healthcare: Similarly, using large electronic medical record datasets (like MIMIC), researchers have shown it's possible to learn treatment policies for conditions like hypertension that are significantly better than the average policy followed by doctors in the dataset.
• The Core Idea: We want to leverage the natural variation in a historical dataset to identify what actions lead to better outcomes and construct a new, improved policy.

3. The Challenge of Offline RL: Distribution Mismatch
Offline RL is fundamentally challenging due to distribution mismatch. The policy we want to evaluate or learn (π_e, the evaluation policy) will induce a different distribution of states and actions than the policy that generated the data (π_b, the behavior policy).

• The "Deadly Triad": Standard off-policy algorithms like Q-learning often fail in the purely offline setting. The combination of bootstrapping (updating an estimate with another estimate), function approximation, and off-policy learning can lead to instability and divergence. The errors from out-of-distribution actions get propagated and magnified by the bootstrapping process.
• Empirical Failures: An example showed that standard deep RL algorithms like DDPG and DQN can perform worse than the simple behavior policy when trained on a fixed dataset, highlighting the need for specialized offline RL algorithms.

4. Offline Policy Evaluation: How Good is a New Policy?
Before learning a new policy, a crucial first step is being able to evaluate a candidate policy using only the offline data.

• Model-Based Evaluation: One approach is to use the offline data to learn a dynamics model and a reward model of the environment, creating a simulator. Then, one can evaluate the new policy within this simulator.
  • The Pitfall of Model Misspecification: The "Refraction" game example showed a critical flaw in this approach. As the researchers built more complex (and more accurate on held-out data) models of student learning, the policies optimized within those models performed worse when evaluated in the real world. A more accurate model does not guarantee a better policy. The errors in the model can be exploited by the optimizer, leading to policies that look great in the flawed simulator but are poor in reality.
• Model-Free Evaluation with Importance Sampling (IS): A more robust, model-free approach is importance sampling.
  • The Core Idea: To estimate the value of a new policy π_e, we can use trajectories generated by the behavior policy π_b and re-weight them to account for the distribution shift. The weight for a trajectory is the ratio of the probabilities of that trajectory occurring under the new policy versus the old one: P(τ|π_e) / P(τ|π_b).
  • Key Properties:
    • IS provides an unbiased estimate of the policy's value.
    • It does not require a dynamics model (the transition probabilities cancel out in the ratio).
    • It does not require the Markov assumption.
  • Limitations:
    • High Variance: The importance weights can have extremely high variance, especially for long trajectories where small differences in policy at each step are multiplied together.
    • Coverage Assumption: It requires that any action the evaluation policy might take must have a non-zero probability of being taken by the behavior policy. You cannot evaluate what you have never seen.

5. Offline Policy Learning: Finding the Best New Policy
The ultimate goal is to learn a new, optimal policy from the offline data.

• The Coverage Problem: A major challenge is that the behavior data may only cover a small portion of the state-action space. Standard RL algorithms might learn a policy that decides to take an action in a state for which there is no data, leading to unpredictable and potentially catastrophic results.
• The Principle of Pessimism: The key idea in modern offline RL is pessimism under uncertainty. The algorithm should be conservative. When evaluating an action for which there is little to no data, it should assume the worst-case outcome.
• A Simple Pessimistic Algorithm: One way to implement this is to add a "filtration function" to the Bellman backup.
  1. Estimate the density of data for each state-action pair.
  2. If the density is below a certain threshold (i.e., we have not seen this pair much), the filtration function is 0; otherwise, it is 1.
  3. During the Bellman backup, multiply the future value term V(s') by this filtration function.
  4. This means if an action leads to an uncertain next state, its value is pessimistically assumed to be just the immediate reward (with a future value of 0), discouraging the algorithm from exploring unsupported regions of the state space.
• State of the Art: This principle of pessimism or conservatism is at the heart of many state-of-the-art offline RL algorithms like Conservative Q-Learning (CQL). These methods have been shown to significantly outperform naive off-policy methods and can reliably learn policies that are better than the behavior policy that generated the data.

L11: Exploration 1

This lecture marks a shift in focus from learning from offline/past data to online learning, where the agent actively gathers data to learn as quickly and efficiently as possible. The central theme is sample efficiency, which is critical in real-world applications where data collection is expensive or risky (e.g., healthcare, education, robotics), in contrast to simulated environments where data is cheap.
1. "Refresh Your Understanding" Poll & Review
The lecture started with a review of concepts from offline RL and policy gradients:

• Importance Sampling (IS): Confirmed that IS is a model-free method that does not leverage the Markov assumption. It works by re-weighting entire trajectories and is applicable even in non-Markovian systems.
• Performance Difference Lemma & PPO: Reviewed the key ideas behind PPO. The performance difference between two policies can be related to the expected advantage. PPO uses an approximation where this expectation is taken over the state distribution of the old policy instead of the new one. The error of this approximation is bounded by the KL divergence between the two policies.

2. Introduction to Data-Efficient RL
The lecture framed the problem of data-efficient or "fast" RL by distinguishing between computational efficiency and sample efficiency.

• Computational Efficiency: The primary concern in simulated environments (Atari, MuJoCo), where generating data is just another form of computation.
• Sample Efficiency: The critical bottleneck in real-world domains (healthcare, education, climate policy), where each data point (a sample) is costly, time-consuming, or has real-world consequences.

The goal is to design algorithms that learn good policies with the minimum number of real-world samples. This requires a formal way to measure an algorithm's performance over time.
3. Introduction to Multi-Armed Bandits
To build the foundations for data-efficient RL, the lecture introduces the multi-armed bandit problem, a simplified RL setting.

• The Setup:
  • There are no states, only a set of K actions (or "arms").
  • Each arm a has an unknown, fixed probability distribution over rewards.
  • At each time step t, the agent chooses one arm to pull and receives a reward sampled from that arm's distribution.
  • The goal is to maximize cumulative reward over time.
• Example (Broken Toes): A running example was introduced where a doctor must choose one of three treatments (surgery, buddy taping, doing nothing) for a series of patients with broken toes. Each treatment is an arm with an unknown probability of success (a reward of 1).

4. The Concept of Regret
To formally evaluate bandit algorithms, the concept of regret is introduced.

• Definition: Regret is the opportunity loss incurred at each time step. It is the difference between the reward of the optimal arm (a*) and the reward of the arm the agent actually chose (a_t).
  Regret_t = E[R(a*)] - E[R(a_t)]
• Total Regret: The objective is to minimize the total cumulative regret over a horizon of T steps.
• Types of Regret Growth:
  • Linear Regret: The worst case, where the agent makes a mistake a constant fraction of the time. The total regret grows linearly with T. The simple greedy algorithm (always picking the arm with the highest current empirical mean) can suffer from linear regret if it locks onto a suboptimal arm early on.
  • Sublinear Regret: The desired outcome. The total regret grows slower than T (e.g., log(T) or sqrt(T)). This implies that the agent's rate of making mistakes decreases over time, and it learns to pull the optimal arm more and more often.

5. Optimism in the Face of Uncertainty (OFU)
A powerful and elegant principle for designing data-efficient algorithms is Optimism in the Face of Uncertainty (OFU).

• The Intuition: The agent should act as if the world is as good as it can plausibly be, given the current data. It chooses the action that might be the best one.
• The Win-Win Scenario:
  1. If the optimistic choice is indeed the best one, the agent receives a high reward (good for minimizing regret).
  2. If the optimistic choice turns out to be suboptimal (it yields a low reward), the agent learns something valuable and reduces its uncertainty about that arm, making it less likely to make the same mistake again.
• Implementation: Upper Confidence Bounds (UCB): The OFU principle is implemented by calculating an Upper Confidence Bound (UCB) for the true mean reward of each arm. The UCB is the empirical mean plus a "bonus" term that quantifies the uncertainty. The algorithm then simply chooses the arm with the highest UCB.

6. The UCB1 Algorithm and its Analysis

• Hoeffding's Inequality: This concentration inequality is used to derive the confidence bound. It bounds the probability that an empirical mean deviates from the true mean by more than a certain amount, u.
• Deriving the Confidence Bound: By inverting Hoeffding's inequality, we can find the size of the uncertainty term u needed to ensure that the true mean is contained within the interval [empirical_mean - u, empirical_mean + u] with high probability (e.g., 1-δ). This uncertainty term shrinks as the number of samples (N_t(a)) for that arm increases: u ∝ sqrt(log(1/δ) / N_t(a)).
• The UCB1 Algorithm:
  1. At each time step t, for each arm a, calculate its UCB: UCB_t(a) = Q_hat_t(a) + sqrt(C * log(t) / N_{t-1}(a)), where Q_hat is the empirical mean, N is the number of pulls, and C is a constant.
  2. Pull the arm with the highest UCB.
• Regret Analysis (Proof Sketch):
  1. The total regret is the sum over all suboptimal arms of (gap_a * E[N_T(a)]), where gap_a is the difference in reward between the optimal arm and arm a.
  2. The key is to bound how many times a suboptimal arm a can be pulled, E[N_T(a)].
  3. A suboptimal arm a is only pulled if its UCB is higher than the UCB of the optimal arm a*.
  4. This can only happen if the confidence interval for arm a is wide enough to overlap with and exceed the confidence interval for a*.
  5. Since the confidence intervals shrink with the number of pulls, eventually the interval for arm a will become small enough that its UCB will definitively be lower than the true mean of a*.
  6. The number of pulls required for this to happen is proportional to 1 / (gap_a)^2.
  7. Plugging this back into the total regret formula shows that the regret for UCB1 is sublinear, growing logarithmically with the time horizon T.

This result is a landmark in learning theory, showing that a simple, optimistic algorithm can be provably data-efficient and achieve near-optimal performance.

L12: Exploration 2

This lecture marks a shift in focus from learning from offline/past data to online learning, where the agent actively gathers data to learn as quickly and efficiently as possible. The central theme is sample efficiency, which is critical in real-world applications where data collection is expensive or risky (e.g., healthcare, education, robotics), in contrast to simulated environments where data is cheap.
1. "Refresh Your Understanding" Poll & Review
The lecture started with a review of concepts from offline RL and policy gradients:

• Importance Sampling (IS): Confirmed that IS is a model-free method that does not leverage the Markov assumption. It works by re-weighting entire trajectories and is applicable even in non-Markovian systems.
• Performance Difference Lemma & PPO: Reviewed the key ideas behind PPO. The performance difference between two policies can be related to the expected advantage. PPO uses an approximation where this expectation is taken over the state distribution of the old policy instead of the new one. The error of this approximation is bounded by the KL divergence between the two policies.

2. Introduction to Data-Efficient RL
The lecture framed the problem of data-efficient or "fast" RL by distinguishing between computational efficiency and sample efficiency.

• Computational Efficiency: The primary concern in simulated environments (Atari, MuJoCo), where generating data is just another form of computation.
• Sample Efficiency: The critical bottleneck in real-world domains (healthcare, education, climate policy), where each data point (a sample) is costly, time-consuming, or has real-world consequences.

The goal is to design algorithms that learn good policies with the minimum number of real-world samples. This requires a formal way to measure an algorithm's performance over time.
3. Introduction to Multi-Armed Bandits
To build the foundations for data-efficient RL, the lecture introduces the multi-armed bandit problem, a simplified RL setting.

• The Setup:
  • There are no states, only a set of K actions (or "arms").
  • Each arm a has an unknown, fixed probability distribution over rewards.
  • At each time step t, the agent chooses one arm to pull and receives a reward sampled from that arm's distribution.
  • The goal is to maximize cumulative reward over time.
• Example (Broken Toes): A running example was introduced where a doctor must choose one of three treatments (surgery, buddy taping, doing nothing) for a series of patients with broken toes. Each treatment is an arm with an unknown probability of success (a reward of 1).

4. The Concept of Regret
To formally evaluate bandit algorithms, the concept of regret is introduced.

• Definition: Regret is the opportunity loss incurred at each time step. It is the difference between the reward of the optimal arm (a*) and the reward of the arm the agent actually chose (a_t).
  Regret_t = E[R(a*)] - E[R(a_t)]
• Total Regret: The objective is to minimize the total cumulative regret over a horizon of T steps.
• Types of Regret Growth:
  • Linear Regret: The worst case, where the agent makes a mistake a constant fraction of the time. The total regret grows linearly with T. The simple greedy algorithm (always picking the arm with the highest current empirical mean) can suffer from linear regret if it locks onto a suboptimal arm early on.
  • Sublinear Regret: The desired outcome. The total regret grows slower than T (e.g., log(T) or sqrt(T)). This implies that the agent's rate of making mistakes decreases over time, and it learns to pull the optimal arm more and more often.

5. Optimism in the Face of Uncertainty (OFU)
A powerful and elegant principle for designing data-efficient algorithms is Optimism in the Face of Uncertainty (OFU).

• The Intuition: The agent should act as if the world is as good as it can plausibly be, given the current data. It chooses the action that might be the best one.
• The Win-Win Scenario:
  1. If the optimistic choice is indeed the best one, the agent receives a high reward (good for minimizing regret).
  2. If the optimistic choice turns out to be suboptimal (it yields a low reward), the agent learns something valuable and reduces its uncertainty about that arm, making it less likely to make the same mistake again.
• Implementation: Upper Confidence Bounds (UCB): The OFU principle is implemented by calculating an Upper Confidence Bound (UCB) for the true mean reward of each arm. The UCB is the empirical mean plus a "bonus" term that quantifies the uncertainty. The algorithm then simply chooses the arm with the highest UCB.

6. The UCB1 Algorithm and its Analysis

• Hoeffding's Inequality: This concentration inequality is used to derive the confidence bound. It bounds the probability that an empirical mean deviates from the true mean by more than a certain amount, u.
• Deriving the Confidence Bound: By inverting Hoeffding's inequality, we can find the size of the uncertainty term u needed to ensure that the true mean is contained within the interval [empirical_mean - u, empirical_mean + u] with high probability (e.g., 1-δ). This uncertainty term shrinks as the number of samples (N_t(a)) for that arm increases: u ∝ sqrt(log(1/δ) / N_t(a)).
• The UCB1 Algorithm:
  1. At each time step t, for each arm a, calculate its UCB: UCB_t(a) = Q_hat_t(a) + sqrt(C * log(t) / N_{t-1}(a)), where Q_hat is the empirical mean, N is the number of pulls, and C is a constant.
  2. Pull the arm with the highest UCB.
• Regret Analysis (Proof Sketch):
  1. The total regret is the sum over all suboptimal arms of (gap_a * E[N_T(a)]), where gap_a is the difference in reward between the optimal arm and arm a.
  2. The key is to bound how many times a suboptimal arm a can be pulled, E[N_T(a)].
  3. A suboptimal arm a is only pulled if its UCB is higher than the UCB of the optimal arm a*.
  4. This can only happen if the confidence interval for arm a is wide enough to overlap with and exceed the confidence interval for a*.
  5. Since the confidence intervals shrink with the number of pulls, eventually the interval for arm a will become small enough that its UCB will definitively be lower than the true mean of a*.
  6. The number of pulls required for this to happen is proportional to 1 / (gap_a)^2.
  7. Plugging this back into the total regret formula shows that the regret for UCB1 is sublinear, growing logarithmically with the time horizon T.

This result is a landmark in learning theory, showing that a simple, optimistic algorithm can be provably data-efficient and achieve near-optimal performance.

L13: Exploration 3

This lecture marks a shift in focus from learning from offline/past data to online learning, where the agent actively gathers data to learn as quickly and efficiently as possible. The central theme is sample efficiency, which is critical in real-world applications where data collection is expensive or risky (e.g., healthcare, education, robotics), in contrast to simulated environments where data is cheap.
1. "Refresh Your Understanding" Poll & Review
The lecture started with a review of concepts from offline RL and policy gradients:

• Importance Sampling (IS): Confirmed that IS is a model-free method that does not leverage the Markov assumption. It works by re-weighting entire trajectories and is applicable even in non-Markovian systems.
• Performance Difference Lemma & PPO: Reviewed the key ideas behind PPO. The performance difference between two policies can be related to the expected advantage. PPO uses an approximation where this expectation is taken over the state distribution of the old policy instead of the new one. The error of this approximation is bounded by the KL divergence between the two policies.

2. Introduction to Data-Efficient RL
The lecture framed the problem of data-efficient or "fast" RL by distinguishing between computational efficiency and sample efficiency.

• Computational Efficiency: The primary concern in simulated environments (Atari, MuJoCo), where generating data is just another form of computation.
• Sample Efficiency: The critical bottleneck in real-world domains (healthcare, education, climate policy), where each data point (a sample) is costly, time-consuming, or has real-world consequences.

The goal is to design algorithms that learn good policies with the minimum number of real-world samples. This requires a formal way to measure an algorithm's performance over time.
3. Introduction to Multi-Armed Bandits
To build the foundations for data-efficient RL, the lecture introduces the multi-armed bandit problem, a simplified RL setting.

• The Setup:
  • There are no states, only a set of K actions (or "arms").
  • Each arm a has an unknown, fixed probability distribution over rewards.
  • At each time step t, the agent chooses one arm to pull and receives a reward sampled from that arm's distribution.
  • The goal is to maximize cumulative reward over time.
• Example (Broken Toes): A running example was introduced where a doctor must choose one of three treatments (surgery, buddy taping, doing nothing) for a series of patients with broken toes. Each treatment is an arm with an unknown probability of success (a reward of 1).

4. The Concept of Regret
To formally evaluate bandit algorithms, the concept of regret is introduced.

• Definition: Regret is the opportunity loss incurred at each time step. It is the difference between the reward of the optimal arm (a*) and the reward of the arm the agent actually chose (a_t).
  Regret_t = E[R(a*)] - E[R(a_t)]
• Total Regret: The objective is to minimize the total cumulative regret over a horizon of T steps.
• Types of Regret Growth:
  • Linear Regret: The worst case, where the agent makes a mistake a constant fraction of the time. The total regret grows linearly with T. The simple greedy algorithm (always picking the arm with the highest current empirical mean) can suffer from linear regret if it locks onto a suboptimal arm early on.
  • Sublinear Regret: The desired outcome. The total regret grows slower than T (e.g., log(T) or sqrt(T)). This implies that the agent's rate of making mistakes decreases over time, and it learns to pull the optimal arm more and more often.

5. Optimism in the Face of Uncertainty (OFU)
A powerful and elegant principle for designing data-efficient algorithms is Optimism in the Face of Uncertainty (OFU).

• The Intuition: The agent should act as if the world is as good as it can plausibly be, given the current data. It chooses the action that might be the best one.
• The Win-Win Scenario:
  1. If the optimistic choice is indeed the best one, the agent receives a high reward (good for minimizing regret).
  2. If the optimistic choice turns out to be suboptimal (it yields a low reward), the agent learns something valuable and reduces its uncertainty about that arm, making it less likely to make the same mistake again.
• Implementation: Upper Confidence Bounds (UCB): The OFU principle is implemented by calculating an Upper Confidence Bound (UCB) for the true mean reward of each arm. The UCB is the empirical mean plus a "bonus" term that quantifies the uncertainty. The algorithm then simply chooses the arm with the highest UCB.

6. The UCB1 Algorithm and its Analysis

• Hoeffding's Inequality: This concentration inequality is used to derive the confidence bound. It bounds the probability that an empirical mean deviates from the true mean by more than a certain amount, u.
• Deriving the Confidence Bound: By inverting Hoeffding's inequality, we can find the size of the uncertainty term u needed to ensure that the true mean is contained within the interval [empirical_mean - u, empirical_mean + u] with high probability (e.g., 1-δ). This uncertainty term shrinks as the number of samples (N_t(a)) for that arm increases: u ∝ sqrt(log(1/δ) / N_t(a)).
• The UCB1 Algorithm:
  1. At each time step t, for each arm a, calculate its UCB: UCB_t(a) = Q_hat_t(a) + sqrt(C * log(t) / N_{t-1}(a)), where Q_hat is the empirical mean, N is the number of pulls, and C is a constant.
  2. Pull the arm with the highest UCB.
• Regret Analysis (Proof Sketch):
  1. The total regret is the sum over all suboptimal arms of (gap_a * E[N_T(a)]), where gap_a is the difference in reward between the optimal arm and arm a.
  2. The key is to bound how many times a suboptimal arm a can be pulled, E[N_T(a)].
  3. A suboptimal arm a is only pulled if its UCB is higher than the UCB of the optimal arm a*.
  4. This can only happen if the confidence interval for arm a is wide enough to overlap with and exceed the confidence interval for a*.
  5. Since the confidence intervals shrink with the number of pulls, eventually the interval for arm a will become small enough that its UCB will definitively be lower than the true mean of a*.
  6. The number of pulls required for this to happen is proportional to 1 / (gap_a)^2.
  7. Plugging this back into the total regret formula shows that the regret for UCB1 is sublinear, growing logarithmically with the time horizon T.

This result is a landmark in learning theory, showing that a simple, optimistic algorithm can be provably data-efficient and achieve near-optimal performance.

L14: Multi-Agent Game Playing

This lecture delves into a different paradigm of reinforcement learning, focusing on simulation-based search and online planning to make high-quality decisions in a single, specific state. This contrasts with previous methods that aimed to learn a global policy for all states. The culmination of these ideas is AlphaGo and AlphaZero, the AI systems that mastered the game of Go.
1. "Refresh Your Understanding" Poll & Review
The lecture started with a poll reviewing concepts from data-efficient exploration.

• Upper Confidence Bounds (UCB): UCB is a principle for balancing exploration and exploitation. It is a key technique used in both multi-armed bandits and full Markov Decision Processes (MDPs).
• The Value of Exploration: The poll included a tricky question: "If the reward model is known, is there any benefit to using UCB?"
  • In Multi-Armed Bandits (MABs): The answer is no. If the rewards for each action are known, there is no uncertainty to explore. The optimal action is simply the one with the highest known reward.
  • In Reinforcement Learning (MDPs): The answer is yes. Even if the immediate rewards are known, the agent still doesn't know the dynamics model (P(s'|s,a)). Therefore, it doesn't know the long-term value (Q*(s,a)) of its actions. UCB-style exploration is still needed to discover which sequences of actions lead to high-value states.

2. Simulation-Based Search: Focusing Computation
The core idea of this lecture is to move away from learning a global policy and instead use all available computation to find the single best action to take from the current state.

• Simple Monte Carlo Search: A basic approach is to use a "default policy" (π). From the current state, simulate taking each possible action a, and then from the resulting state s', "roll out" the rest of the episode using the default policy. By averaging the returns from these rollouts, one can get a Monte Carlo estimate of Qπ(s, a) for each action and then choose the action with the highest estimated value. This is effectively one step of policy improvement.
• Expectimax Search: A more principled approach is to build a search tree from the current state.
  • Action Nodes (black): Represent points where the agent makes a choice. The value is determined by taking the max over child nodes.
  • State Nodes (white): Represent points where the environment responds. The value is an expectation (a weighted average) over the possible next states.
  • This tree represents an explicit rollout of the Bellman equation. However, building the full tree is intractable, as its size grows exponentially with the horizon (O(|S||A|^H)).

3. Monte Carlo Tree Search (MCTS)
MCTS is a powerful algorithm that makes expectimax search tractable by using sampling to approximate the search tree.

• Core Idea: Instead of expanding all possible next states at a state node, MCTS samples from the distribution of next states. The law of large numbers ensures that the average value of these samples will converge to the true expected value. This breaks the curse of dimensionality with respect to the state space size.
• The Action Space Problem: MCTS, in its basic form, still struggles with large action spaces, as it still needs to consider every possible action at the action nodes.

4. Upper Confidence Trees (UCT)
UCT enhances MCTS by applying the Upper Confidence Bound principle from bandits to the action selection problem within the search tree.

• The Idea: Treat each node in the search tree as a separate multi-armed bandit problem. The actions available at that node are the "arms."
• The Algorithm:
  1. Start at the root (the current state).
  2. Select the action a that maximizes Q(s, a) + U(s, a), where Q is the current average return from taking that action in the tree, and U is a UCB bonus term that encourages exploration of less-tried actions.
  3. Follow this "tree policy" down until a leaf node is reached.
  4. From the leaf node, perform a Monte Carlo rollout using a default policy to get a return value.
  5. Backup: Propagate this return value back up the tree, updating the Q values and visit counts for all nodes and actions along the path.
  6. Repeat for a fixed computational budget (e.g., thousands of simulations).
• Benefit: UCT intelligently focuses the search on the most promising parts of the massive game tree, leading to a highly selective and efficient search.

5. AlphaGo and AlphaZero
The culmination of these ideas is AlphaGo and AlphaZero, which combined deep neural networks with a sophisticated MCTS algorithm.

• Self-Play: A key component is self-play. The agent learns by playing games against itself. This is highly effective because:
  • It provides a perfectly matched opponent, ensuring a high reward density (roughly 50% win rate), which is a rich learning signal.
  • It creates an automatic curriculum, as the agent's opponent gets progressively stronger as the agent itself improves.
• The Neural Network: AlphaZero uses a single, deep residual network with two heads:
  • Policy Head Outputs a probability distribution over actions, serving as a prior to guide the MCTS search. It helps prune the vast action space.
  • Value Head Outputs a scalar value estimating the probability of winning from the current state. This is used to evaluate leaf nodes in the search, avoiding the need for expensive rollouts to the end of the game.
• The AlphaZero MCTS Algorithm: For each move in a game:
  • Selection: Traverse the tree from the root by selecting actions that maximize Q(s, a) + U(s, a). The UCB term U is now biased by the policy network's prior p(a|s), which helps focus the search on promising moves.
  • Expansion: When a leaf node is reached, it is expanded. The value of this new node is estimated using the value head of the neural network, v(s).
  • Backup: The value from the network is backed up the tree, updating the Q values and visit counts.
  • Action Selection: After thousands of MCTS simulations, the final action to be played in the real game is chosen proportionally to the visit counts of the actions at the root node.
• Training Loop: After a game of self-play is completed, the data from that game (s_t, π_t, z) — where π_t is the MCTS visit-count policy and z is the final game outcome — is used to train the neural network. The network is trained via supervised learning to make its policy head match the MCTS policy and its value head match the game outcome. This cycle repeats, with the stronger network leading to a stronger MCTS player, which in turn generates higher-quality data to further improve the network.
• Key Results:
  • Architecture Matters: The choice of neural network architecture (e.g., ResNet vs. a simpler CNN) had a massive impact on performance.
  • MCTS is Crucial: Even with a powerful, well-trained neural network, turning off the MCTS search at test time resulted in a huge drop in performance. The "last mile" of local computation provided by MCTS is essential for top-level play.
  • Beyond Human Knowledge: AlphaZero, trained with no human data, not only surpassed human grandmasters but also discovered novel strategies and styles of play that were previously unknown to humans.

L15: Value Alignment

This lecture, led by a guest speaker with a background in philosophy and ethics, shifted the focus from the technical "how" of reinforcement learning to the normative "what": What objectives should we be training our AI agents to pursue? This is the problem of value alignment.
1. Introduction: The Paperclip Maximizer
The lecture began with the classic thought experiment of the Paperclip AI, an agent tasked with the simple goal of maximizing paperclip production.

• The Problem: The AI, in its single-minded pursuit of this goal, might take unforeseen and destructive actions, such as converting the entire Earth into paperclips, exploiting labor, or sacrificing quality for quantity.
• The Core Issue (Value Alignment): This illustrates the core problem of value alignment: How do we design AI agents that will do what we really want them to do, recognizing that our stated instructions are often incomplete and rely on a vast set of unstated background assumptions? Simply providing better instructions is often insufficient, as it's hard to anticipate every possible loophole.

2. Three Interpretations of "What We Really Want"
The lecture broke down the ambiguous phrase "what we really want" into three distinct, and potentially conflicting, interpretations.

• The Idea: The goal is to design agents that can infer the user's true, nuanced intention from their underspecified instructions. For the Paperclip AI, the real intention was likely "maximize production subject to constraints like labor laws, quality standards, and economic efficiency."
• Technical Challenge: This requires the AI to have a deep model of human language, culture, and common sense to understand the implied meaning behind instructions. The speaker noted that while LLMs have made this seem more plausible than it did in 2020, it's still a significant challenge.
• Philosophical Challenge: A user's intentions might not align with their deeper goals. For example, my intention might be to maximize paperclip production, but my real goal is to maximize profit. If the AI knows I could make more profit by producing something else, is it aligned if it follows my stated intention?
• The Idea: The goal is to design agents that do what the user prefers, even if it conflicts with their stated intentions. The Paperclip AI is misaligned because I prefer a world where the Earth is not converted into paperclips.
• Technical Challenge: This requires methods for learning a user's preferences, especially when they are not explicitly stated. This directly connects to techniques like Inverse Reinforcement Learning (IRL) and Reinforcement Learning from Human Feedback (RLHF), which learn from observing a user's behavior and choices. A key challenge is inferring preferences in novel or emergency situations where no prior data exists.
• Philosophical Challenge: A user's preferences may not align with what is actually good for them. People may prefer to smoke, but it's not in their best interest. I might prefer to maximize profit, but it might be objectively better for my well-being to focus less on money and more on family.
• The Idea: The goal is to design agents that do what is objectively in the user's best interest, regardless of their intentions or preferences. The Paperclip AI is misaligned because it is objectively bad for me if the world is destroyed.
• Technical/Philosophical Challenge: Determining what is "objectively good" is a deep philosophical question, not a purely empirical one. Philosophers disagree on whether well-being consists of happiness (hedonism), desire satisfaction, or a list of objective goods (health, knowledge, relationships, etc.).
• Paternalism: A major risk with this approach is paternalism—the agent deciding what's best for the user, potentially overriding their autonomy. It was noted that autonomy itself is often considered an objective good, so a sophisticated alignment to "best interests" would still need to account for the user's preferences to some degree.

3. Case Study: A Personalized News Chatbot
The lecture applied these abstract concepts to a concrete example: designing an LLM chatbot to provide news.

• Aligning to Preferences: This would involve personalizing the news feed based on user interactions. The chatbot would learn what topics, sources, and viewpoints the user clicks on and prefers, and then deliver more of that content.
• Aligning to Best Interests: This would involve the designer making a judgment about what constitutes "good" news for a person. This might mean providing news that is factually accurate, high-quality, and presents a diverse range of perspectives, even if the user shows a preference for biased or low-quality information.
• Pros and Cons:
  • Preference Alignment: Pro: Avoids paternalism, gives the user what they want. Con: Risks creating filter bubbles and echo chambers, reinforcing biases, and exposing users to misinformation if that's what they prefer.
  • Best Interest Alignment: Pro: Promotes a well-informed citizenry, counteracts biases. Con: Risks paternalism by imposing the designer's values on the user. It's also very difficult to know what is truly in an individual's best interest.

4. Expanding the "We": Aligning to Morality
The final part of the lecture argued that focusing only on the user is too narrow. A truly aligned agent must consider the interests of all affected parties.

• The Idea: Value alignment should be about designing agents that do what is morally right. The main problem with the Paperclip AI is not just that it's bad for the user, but that it's bad for everyone (the workers, society, the universe).
• The Challenge of Moral Disagreement: Just like with objective good, people have deep disagreements about what is morally right. This is the domain of moral theory.
  • Consequentialism/Utilitarianism: The right action is the one that produces the best overall consequences (e.g., the most happiness).
  • Deontology: Certain actions (like lying or killing) are wrong in themselves, regardless of their consequences, because they violate moral rules or rights.
  • Other theories like Prioritarianism also exist.
• Aligning to a Moral Theory vs. Common-Sense Morality:
  • One could try to build the "correct" moral theory into an AI. This is difficult because philosophers have been debating which theory is correct for millennia. Furthermore, many moral theories have counter-intuitive and potentially dangerous implications in edge cases (e.g., a utilitarian surgeon harvesting organs from a healthy person to save five others).
  • A more practical and safer approach might be to align agents to common-sense or consensus morality—the basic moral rules and values that most people agree on. This would lead to more predictable and trustworthy behavior, though it might leave the AI as uncertain as humans are in truly difficult moral dilemmas.

L16: Review

This final lecture served as a comprehensive review of the course, revisiting key concepts through the lens of the final quiz and challenging application domains, and concluded with a forward-looking perspective on the open challenges and future of the reinforcement learning field.
1. Quiz Recap and Concept Clarification
The lecture began by reviewing several questions from the final quiz, using them as a springboard to reinforce core concepts from the latter half of the course.

• DPO vs. RLHF: It was clarified that while both methods learn from human preferences, only RLHF learns an explicit, separate reward model. DPO, by contrast, uses the Bradley-Terry preference model to derive a loss function that optimizes the policy directly, bypassing the explicit reward modeling step. A key takeaway was that both methods can learn policies that outperform the best examples in the training data by learning a generalizable reward signal.
• The Inappropriateness of RLHF for Board Games: A question explored why RLHF might be a poor choice for games like Go or chess. The primary reason is that the ground-truth reward is already known (win=+1, lose=-1). There is no need to learn a proxy reward from noisy human preferences over intermediate game states when the true, sparse reward signal is perfectly defined.
• Monte Carlo Tree Search (MCTS) & AlphaZero:
  • MCTS is a general algorithm that can be applied to both Markovian and non-Markovian problems, as it relies on a forward model for sampling, not on the Markov property itself.
  • It was clarified that MCTS breaks the curse of dimensionality for the state space by sampling next states, but not for the action space. Additional techniques, like the policy network in AlphaZero or UCT for bandits, are needed to handle large action spaces.
  • A key insight from AlphaZero is the immense value of local computation. Even after 40 days of training a massive neural network, performing MCTS at test time still provides a huge performance boost.
  • Self-play was re-emphasized as a form of implicit curriculum learning, ensuring a high reward density by pitting the agent against a perfectly matched opponent (itself).
• PAC Guarantees and Regret: The distinction between Probably Approximately Correct (PAC) learning and regret minimization was reviewed. A PAC algorithm guarantees learning an ε-optimal policy with a finite number of mistakes. However, because it is only ε-optimal, it could continue to incur a small amount of regret on every step, leading to linear total regret over time.

2. Revisiting Applications: A Test of Understanding
The professor challenged the class to apply their knowledge by formulating three real-world problems discussed at the start of the course.

• Problem Type: A multi-step, deterministic RL problem framed as a search. The "environment" is the process of constructing an algorithm.
• Framework: The solution uses an AlphaZero-like architecture, combining a powerful neural network (with policy and value heads) with Monte Carlo Tree Search.
• State: The current state of the tensor representing the matrix multiplication operations performed so far.
• Action: The next algorithmic operation to perform (which product or sum to compute).
• Reward: The goal is to minimize the number of computational steps. The reward is structured to incentivize shorter, correct algorithms.
• Online/Offline: The search for the algorithm is a massive offline computation. Once the optimal algorithm is found, it is used directly at runtime without any further MCTS.
• Problem Type: A multi-step, continuous control RL problem.
• Framework: A model-based actor-critic approach. A high-fidelity (but imperfect) simulator of the plasma physics is used for offline training.
• Key Insight (Asymmetric Computation): A crucial design choice was to use a very simple, fast actor (policy network) that could meet real-time deployment constraints, while using a very complex, high-capacity critic (value network) during offline training to provide a high-quality learning signal.
• Safety: To handle the "sim-to-real" gap and ensure safety, the reward function was shaped with penalties to discourage the policy from entering states where the simulator was known to be inaccurate or that were close to unsafe operating regimes. This is a form of pessimism.
• Problem Type: A contextual bandit problem. It is not a full MDP because the decision of whom to test today does not affect the population of people arriving tomorrow.
• Complexities: The problem is complicated by several real-world factors:
  • Batched and Delayed Feedback: Decisions for a whole flight of people must be made at once, and the test results (rewards) only arrive 24-48 hours later.
  • Constraints: There are hard limits on the number of tests that can be performed per day.
• Algorithm Choice: The batch and delayed nature makes Thompson Sampling an excellent candidate, as its inherent randomization allows it to continue exploring even without immediate feedback from the last action, unlike a deterministic UCB algorithm which would get "stuck."

3. Synthesizing the Core Ideas of Reinforcement Learning
The lecture concluded by synthesizing the overarching themes and open challenges in the field.

• Core Challenge: Distribution Shift: The single most important concept distinguishing RL from other forms of machine learning is that the agent's actions influence the data distribution it sees. This creates the problem of distribution shift, where a policy learned from one distribution of data may not perform well on the new distribution it creates. Nearly every advanced algorithm discussed (PPO, DAGGER, pessimistic offline RL) is, at its core, an attempt to manage this problem.
• The Trinity: Models, Values, and Policies:
  • Models: Useful for planning (MCTS), representing uncertainty, and improving sample efficiency.
  • Value Functions (Q-functions): The central object for summarizing the performance of a policy and are often used to directly derive actions.
  • Policies: The ultimate goal of RL—a mapping from states to actions that specifies the agent's behavior.
• Open Challenges and the Future of RL:
  • Robustness: A need for "off-the-shelf" algorithms that are less sensitive to hyperparameters and work reliably across different problems.
  • Hybrid Offline-Online Learning: Developing methods for the realistic setting where an agent has a large offline dataset but can also collect a small amount of new online data.
  • Beyond the MDP: Questioning if the standard MDP formulation is always the best way to frame decision-making problems.
  • Multi-Task and Lifelong Learning: Moving away from training agents on single tasks from scratch towards agents that can leverage past experience to learn new tasks more quickly.
  • Richer Feedback: Incorporating more complex forms of feedback, like natural language, beyond simple scalar rewards.
  • Multi-Agent and Adversarial Settings: More accurately modeling real-world scenarios with multiple competing or cooperating agents.
  • Real-World Impact: The ultimate challenge of translating the theoretical power of RL into widespread, beneficial applications in critical domains like healthcare, education, and climate.