Key Moments
Stanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 17: RL Value-Based Methods
Stanford OnlineWant to know something specific about what's covered?
We've already dissected every moment. Ask and we will deliver (with timestamps).
Key Moments
Value-based reinforcement learning methods like SARSA and Q-learning can learn optimal policies, but scaling them to complex environments requires function approximation and techniques like experience replay and fixed Q-targets to stabilize learning.
Key Insights
SARSA and Q-learning are value-based reinforcement learning algorithms that build upon Temporal Difference (TD) learning, offering advantages over Monte Carlo methods due to lower variance and the ability to learn online.
SARSA is an on-policy algorithm, meaning it evaluates and improves the policy currently being used for decision-making, while Q-learning is off-policy, capable of learning about a target policy (e.g., the optimal policy) while behaving according to a different exploration policy.
The 'windy grid world' example illustrates that SARSA converges to the optimal epsilon-greedy policy, which may be safer but not strictly optimal, whereas Q-learning converges to the optimal policy, even if its training path is riskier.
To handle high-dimensional state spaces, value function approximation is used, replacing tabular representations with parametric functions (e.g., neural networks) to generalize across states and reduce memory requirements.
Deep Q-Networks (DQN) combine deep neural networks with Q-learning, stabilizing learning through experience replay (decorrelating samples) and fixed Q-targets (using a delayed copy of the Q-network for target values).
Experience replay and fixed Q-targets are crucial for stabilizing deep reinforcement learning by addressing sample correlation and the moving target problem inherent in function approximation.
Foundations of Reinforcement Learning: Prediction vs. Control and TD Learning
The lecture begins by revisiting the distinction between prediction (estimating the value of a given policy) and control (learning the optimal policy). It recaps dynamic programming approaches like policy iteration and value iteration, highlighting their limitation: the requirement of a known system dynamics model. Reinforcement learning, particularly model-free approaches like Monte Carlo (MC) and Temporal Difference (TD) learning, addresses this by learning through interaction without a model. MC learning updates value estimates based on complete episode returns, while TD learning uses a one-step backup, incorporating bootstrapping (updating estimates based on other estimates). TD learning is presented as advantageous due to lower variance (sampling only once) and its ability to learn online and with incomplete episodes, unlike MC which requires complete rollouts until a terminal state.
From Monte Carlo Control to SARSA: An On-Policy Algorithm
The transition from Monte Carlo control to SARSA involves replacing the Monte Carlo estimation of the Q-function with TD updates. SARSA (State-Action-Reward-State-Action) is named after the quintuple of events required for its update: the current state (S), action (A), reward (R), next state (S'), and next action (A'). Specifically, it updates the Q-value for a state-action pair based on the immediate reward and the discounted Q-value of the next state-action pair, where the next action is chosen according to the current policy. The pseudocode illustrates that SARSA uses an epsilon-greedy policy for action selection, acting greedily with probability 1-epsilon and randomly with probability epsilon. This epsilon-greedy policy is the one being evaluated and improved, making SARSA an on-policy algorithm. The 'windy grid world' example demonstrates how SARSA can learn a policy, though it might converge to a safer, suboptimal epsilon-greedy policy rather than the absolute optimal one due to the exploration component.
Q-Learning: An Off-Policy Algorithm for Optimal Policy Learning
Q-learning represents a significant step towards learning the optimal policy directly. Unlike SARSA, Q-learning is an off-policy algorithm. This means it learns the value of a target policy (typically the greedy, optimal policy) while following a different behavior policy (often epsilon-greedy) to explore the environment. The key difference lies in the Q-learning update rule: it uses the maximum possible Q-value for the next state, irrespective of the action actually taken by the behavior policy. This is achieved by updating the Q-value of the current state-action pair towards the reward plus the discounted maximum Q-value achievable from the next state (Q(S', argmax_a' Q(S', a'))). This detachment allows Q-learning to converge to the optimal action-value function, even if the exploration policy is suboptimal. The cliff walking example highlights this: while SARSA might learn a cautious path to avoid the cliff during exploration, Q-learning, by considering the best possible future action in its update, learns a path closer to the cliff (as its target policy is greedy), which can lead to lower rewards during training if the exploration sometimes leads to falling off the cliff, but ultimately converges to the true optimal policy.
The need for function approximation in high-dimensional spaces
Traditional reinforcement learning algorithms, like SARSA and Q-learning, often represent value functions (V or Q) as lookup tables. This approach works well for small, discrete state and action spaces, as seen in grid-world examples. However, it becomes intractable for high-dimensional or continuous state/action spaces, such as those found in complex games (like Go with 10^170 states) or real-world robotics. The sheer memory required to store these tables is prohibitive, and the 'curse of dimensionality' makes learning inefficient, as each state-action pair must be visited numerous times to learn its value. Value function approximation addresses this by using a parametric function (e.g., a linear model or a neural network) with parameters theta to estimate the value function. This compresses the representation, storing only the parameters, and allows for generalization across similar states or state-action pairs, enabling learning in much larger and more complex environments.
Integrating function approximation with TD learning
When using function approximation, the goal shifts from updating discrete table entries to learning the optimal parameters (theta) of the approximation function. This is framed as a regression problem: minimizing the error between the predicted value (e.g., V_theta(x)) and the target value. The target can be derived from either Monte Carlo returns or, more commonly, TD targets. For TD learning with function approximation, the update rule involves taking a step in the direction of the negative gradient of the error function with respect to theta. The TD target, R + gamma * V_theta(S'), is used as the 'ground truth' for this regression. This process, often referred to as fitted Q-iteration when applied to Q-functions, iteratively updates the function approximator's parameters using sampled transitions and TD targets, effectively fitting the value function to the observed rewards and estimated future values.
Deep Q-Networks (DQN) and stabilizing deep RL
Deep Q-Networks (DQN) represent a landmark achievement in combining deep neural networks with Q-learning to tackle complex problems like playing Atari games directly from raw pixel inputs. The core idea is to use a convolutional neural network as the function approximator for the Q-function, outputting Q-values for each possible action. However, training deep neural networks in RL presents significant challenges: (1) high correlation between consecutive samples due to the agent's sequential interaction with the environment, and (2) the 'moving target' problem, where the target Q-values change as the network's parameters are updated. DQN addresses these issues with two key innovations: Experience Replay and Fixed Q-Targets.
Experience replay and fixed Q-targets for stability
Experience replay involves storing past transitions (state, action, reward, next state) in a large buffer. Instead of updating the network with the most recent, highly correlated transitions, DQN samples mini-batches of transitions randomly from this buffer. This random sampling decorrelates the data, making it more similar to the independent and identically distributed (i.i.d.) data assumed by supervised learning algorithms, thus stabilizing training. The fixed Q-target mechanism uses two copies of the Q-network: one for generating actions and performing updates (online network), and a separate, periodically updated 'target' network. The target network's parameters are frozen for a period, providing a stable target value for the regression updates, thereby mitigating the moving target problem. While initially implemented with periodic hard updates, smoother updates like Polyak averaging are now more common for the target network, further enhancing stability.
Mentioned in This Episode
●Software & Apps
●Books
●Concepts
●People Referenced
Common Questions
Prediction in RL involves estimating the value of a given policy, while control aims to find the policy that optimizes a measure of performance.
Topics
Mentioned in this video
The core topic of the lecture, focusing on learning through trial and error and optimizing policies.
An initial approach to learning-based control discussed in previous weeks, focusing on mimicking expert behavior.
A method used to solve Markov Decision Processes by relying on the principle of optimality, requiring knowledge of system dynamics.
The mathematical formalism used for reinforcement learning, involving states, actions, rewards, and transitions.
A control algorithm that alternates between Monte Carlo policy evaluation and epsilon-greedy policy improvement.
A reinforcement learning paradigm that learns through interaction with the environment by using sampling and updating value functions based on full episode returns.
A grid world environment with a wind effect that introduces challenges in finding the optimal policy, used to illustrate SARSA's behavior.
A grid world environment with a dangerous cliff region, used to compare the policies learned by SARSA (on-policy) and Q-learning (off-policy).
An off-policy temporal difference learning algorithm that learns the optimal action-value function, updating towards the maximum Q-value of the next state.
An on-policy temporal difference learning algorithm for control, named after the quintuple of events (State, Action, Reward, Next State, Next Action).
A groundbreaking deep reinforcement learning algorithm that uses deep neural networks to approximate Q-functions, enabling learning directly from images.
More from Stanford Online
View all 135 summaries
81 minStanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 13: Intro to Learning
74 minStanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 14: Intro to IL and RL
76 minStanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 12: Feasibility of MPC
74 minStanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 16: Fundamentals of RL
Ask anything from this episode.
Save it, chat with it, and connect it to Claude or ChatGPT. Get cited answers from the actual content — and build your own knowledge base of every podcast and video you care about.
Get Started Free