Stanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 16: Fundamentals of RL

Overview

Stanford Online's Lecture 16 on Reinforcement Learning (RL) introduces model-free RL, contrasting it with imitation learning. The lecture recaps Markov Decision Processes (MDPs) and dynamic programming methods like value and policy iteration, highlighting their reliance on known system dynamics. It then delves into Monte Carlo (MC) and Temporal Difference (TD) learning as core model-free techniques for estimating value functions through interaction, exemplified by a Blackjack game scenario, and concludes by framing these as building blocks for generalized policy iteration.

Key takeaways

Model-free Reinforcement Learning methods like Monte Carlo and Temporal Difference learning estimate value functions by learning from environmental interactions, bypassing the need for known system dynamics.
Monte Carlo learning estimates value by averaging returns from complete episodes, while Temporal Difference learning uses bootstrapping (updating estimates based on other estimates) for more frequent, lower-variance updates.
The epsilon-greedy exploration strategy is crucial for model-free RL algorithms that learn from samples, ensuring that all state-action pairs are visited and preventing premature convergence to suboptimal policies.
Generalized Policy Iteration (GPI) provides a unifying framework for RL algorithms, involving iterative cycles of policy evaluation (estimating value) and policy improvement (updating the policy).
Blackjack serves as a practical example demonstrating how MC Q-function evaluation combined with epsilon-greedy policy improvement can derive an optimal policy and its value function without prior game knowledge.

Chapters

0:00 Introduction to Learning-Based Control and Reinforcement Learning

Distinguishes imitation learning (learning from demonstrations) from reinforcement learning (learning from interactions).
Imitation learning performance is capped by expert demonstrations.
Reinforcement learning uses trial and error to discover optimal control solutions.

1:57 Reinforcement Learning Problem Setting: Markov Decision Processes (MDPs)

MDPs defined by state space, action space, transition function, reward function, and discount factor.
Goal is to maximize expected cumulative discounted reward by finding an optimal policy.
Value functions (V and Q) and Bellman equations are introduced as tools for solving MDPs.

7:19 Bellman Equations and Q-Functions for Policy Optimization

Bellman optimality equation relates optimal value function V* to immediate reward and expected future value.
Bellman expectation equation defines value function for any policy pi.
Q-function represents expected future reward from a state-action pair, enabling implicit policy definition via argmax.

11:49 Exact Methods: Value Iteration and Policy Iteration

Value iteration and policy iteration are exact methods for solving MDPs.
These methods iteratively enforce Bellman equations until convergence.
They require knowledge of the system's dynamics (transition function).

13:53 Policy Iteration Algorithm Deep Dive

Policy iteration alternates between policy evaluation (using Bellman expectation equation) and policy improvement (greedy improvement).
Policy evaluation estimates the value of a given policy.
Policy improvement derives a better policy from the current value function estimate.

16:40 Gridworld Example: Policy Evaluation and Improvement

Illustrates policy iteration on a 16-cell gridworld with terminal goal states.
Initial random policy and zero-initialized value function are used.
Policy evaluation iteratively updates state values using the Bellman expectation equation.
Policy improvement derives a greedy policy pointing towards states with higher estimated values.

31:44 Limitations of Exact Methods and Introduction to Model-Free RL

Exact methods (value/policy iteration) require knowledge of MDP dynamics.
They also face challenges with large state-action spaces (memory, convergence).
Model-free RL addresses unknown dynamics by learning from interactions (samples).

33:59 Monte Carlo (MC) Learning for Value Estimation

MC learning estimates value functions directly from sampled episodes (rollouts).
Approximates expected future rewards using the 'return' (sum of rewards in a trajectory).
It's model-free and applies only to episodic MDPs.

42:31 First-Visit vs. Every-Visit Monte Carlo Methods

First-visit MC: considers return only the first time a state is visited in an episode.
Every-visit MC: considers returns from all visits to a state within an episode.
Both methods approximate expectations through empirical means of returns.

50:37 Blackjack Example: MC Policy Evaluation

Applies MC policy evaluation to estimate value functions in the game of Blackjack.
State includes player's sum, dealer's showing card, and presence of a usable ace.
Visualizes value function estimates based on 10,000 and 500,000 episodes, showing noise reduction with more data.

1:05:09 Temporal Difference (TD) Learning

TD learning combines MC sampling with dynamic programming bootstrapping.
It's model-free and learns from experience.
Updates value estimates based on other learned estimates, allowing learning before episode termination.

1:09:03 TD Target and TD Error

TD updates value estimates towards a 'TD target': immediate reward + discounted estimated future value (R + gamma * V(s')).
The difference between the current estimate and the TD target is the 'TD error'.
TD learning bootstraps by updating a guess towards a guess.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Stanford Online.