What are 'exact methods' in the context of solving MDPs?

Exact methods, like value iteration and policy iteration, are dynamic programming techniques that leverage the known dynamics of the system to compute optimal solutions. They assume the transition probabilities and reward functions are fully understood.

How do Monte Carlo methods estimate value functions in reinforcement learning?

Monte Carlo methods estimate value functions by averaging the returns (cumulative discounted rewards) from complete episodes of experience. They are model-free, meaning they don't require knowledge of the environment's dynamics, and learn directly from sampled interactions.

What is the main limitation of Monte Carlo methods in RL?

A key limitation is that Monte Carlo methods strictly apply to episodic MDPs, meaning episodes must have a defined termination point. This is because the return is the sum of all rewards throughout the trajectory.

How does Temporal Difference (TD) learning differ from Monte Carlo learning?

TD learning combines aspects of Monte Carlo and dynamic programming. Unlike Monte Carlo, which waits for the end of an episode, TD learning updates estimates based on other learned estimates (bootstrapping) after each step, allowing it to learn online and from incomplete sequences.

Why is exploration crucial in reinforcement learning?

Exploration is crucial because deterministic policies, which always choose the action with the highest estimated value, can get stuck in suboptimal solutions if they don't initially explore all possibilities. Techniques like epsilon-greedy exploration ensure that all actions are tried with non-zero probability.

What is the 'generalized policy iteration' framework?

Generalized policy iteration (GPI) refers to the general structure of reinforcement learning algorithms that iteratively alternate between policy evaluation (estimating the value of a policy) and policy improvement (updating the policy based on the value estimates).

What are the main components of a reinforcement learning algorithm skeleton?

Most RL algorithms follow a skeleton involving: 1) Generating samples through interaction with the environment. 2) Using these samples to either fit a model or estimate value functions. 3) Improving the policy based on the computations from step 2.

What is the advantage of TD learning over Monte Carlo learning for continuous tasks?

TD learning can learn online and work in continuing or non-terminating environments because it doesn't require waiting for the end of an episode. Monte Carlo methods, requiring full episodes, are better suited for episodic tasks.

What is the difference between sampling and bootstrapping in RL?

Sampling involves using interactions with the environment to approximate expectations (like Monte Carlo and TD learning do). Bootstrapping involves updating estimates based on other learned estimates (like TD learning and dynamic programming do), effectively updating a guess towards a guess.

Key Moments

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

Stanford Online

Education6 min read74 min video

Aug 13, 2026|186 views|6|1

Stanford Stanford Online Robotics

Save to Pod

Want to know something specific about what's covered?

We've already dissected every moment. Ask and we will deliver (with timestamps).

Key Moments

TL;DR

Reinforcement learning learns through trial and error, outperforming imitation learning but requiring careful exploration to avoid suboptimal strategies.

Key Insights

Exact methods like value iteration and policy iteration require knowledge of the system's dynamics, which is often unavailable in real-world reinforcement learning scenarios.

Monte Carlo methods estimate value functions by averaging returns from complete episodes, making them suitable only for episodic MDPs.

Temporal Difference (TD) learning combines Monte Carlo sampling with dynamic programming's bootstrapping, allowing for updates after each step without waiting for episode termination.

TD learning generally has lower variance than Monte Carlo methods because its updates depend on fewer random samples.

Epsilon-greedy exploration is crucial for reinforcement learning algorithms when using sampled Q-functions; it balances exploiting current knowledge with exploring unknown actions to avoid suboptimal policies.

Generalized Policy Iteration (GPI) is a unifying framework for RL algorithms, involving sample generation, value estimation or model fitting, and policy improvement.

Limitations of exact methods and the shift to model-free RL

The lecture begins by contrasting reinforcement learning (RL) with imitation learning. While imitation learning learns from expert demonstrations, its performance is capped by the expert's skill. RL, in contrast, learns through trial and error by interacting with an environment. Previous methods like value iteration and policy iteration, discussed in the context of dynamic programming, are termed 'exact methods' because they assume complete knowledge of the system's dynamics (transition function). These methods are effective for solving Markov Decision Processes (MDPs) by iteratively enforcing Bellman equations. However, a key limitation is their reliance on this known dynamics model, which is often impractical. The lecture pivots to model-free RL, which learns solely from interactions, making it applicable to scenarios where system dynamics are unknown or too complex to model.

Markov Decision Processes and Bellman equations

The foundation of RL problems is the Markov Decision Process (MDP), defined by states, actions, a transition function, a reward function, and a discount factor. The goal is to find an optimal policy that maximizes the expected cumulative discounted reward. Value functions (state-value V and state-action Q) are introduced as key tools to quantify the expected future reward from a given state or state-action pair, following a specific policy. These value functions satisfy Bellman equations, which represent recursive relationships between the value of a state and the values of its successor states. The Bellman optimality equation specifically relates to the optimal value function (V* or Q*).

Monte Carlo learning for episodic tasks

Monte Carlo (MC) methods are introduced as a model-free approach to estimate value functions. Instead of using the dynamics model, MC learns directly from samples collected through interactions with the environment, forming complete 'rollouts' or episodes. To estimate the value of a state, MC methods compute the empirical mean of the 'returns' (discounted sum of all rewards) observed from that state across multiple episodes. A crucial aspect is that MC methods can only be applied to episodic MDPs, meaning tasks that have a defined end state, because the return is summed over the entire trajectory. Two variants, 'first-visit' and 'every-visit' MC, differ in how they count state visits within an episode, but both aim to approximate expectations through averaging observed returns.

Temporal Difference learning: Bootstrapping and online updates

Temporal Difference (TD) learning is presented as another fundamental model-free RL technique that combines aspects of MC and dynamic programming. Like MC, TD learning is model-free and learns from experience. However, unlike MC, TD learning employs 'bootstrapping,' similar to dynamic programming, by updating value estimates based on other learned estimates. Specifically, TD updates a value estimate using the immediate reward plus the discounted estimated value of the next state (the TD target), rather than waiting for the final outcome of an episode. This 'one-step' update allows TD learning to learn online, potentially after every step, and can be applied to continuing or non-terminating environments. This 'bootstrapping' property generally leads to lower variance estimates compared to Monte Carlo returns.

Comparing Monte Carlo and TD learning

Key differences between MC and TD learning lie in their update mechanisms and applicability. MC methods require complete episodes to calculate returns, making them unsuitable for continuous tasks. TD learning, by using bootstrapping, can update estimates after a single step and is thus more versatile, applicable to both episodic and continuing tasks, and can learn online. While the true TD target is unbiased if the value function is exact, using an estimated value function introduces bias. Conversely, MC returns are unbiased estimates of the true value, but they tend to have higher variance because they depend on the entire sequence of random states, actions, and rewards within an episode. TD updates, relying on fewer samples, typically exhibit lower variance.

Generalized Policy Iteration and the exploration-exploitation dilemma

The lecture introduces Generalized Policy Iteration (GPI) as a unifying framework encompassing various RL algorithms. GPI involves iteratively alternating between policy evaluation (estimating the value of a policy) and policy improvement (updating the policy based on the value estimates). When implementing model-free GPI, using Monte Carlo methods for policy evaluation is feasible. However, directly using greedy policy improvement (picking the action with the highest Q-value) can lead to a critical problem: the exploration-exploitation dilemma. If the Q-values are estimated from samples, a deterministic policy might only explore a subset of the state-action space, potentially missing better strategies. The epsilon-greedy strategy is introduced as a solution, where with probability epsilon, a random action is chosen, ensuring that all state-action pairs are eventually explored.

Towards optimal policies with exploration

The lecture demonstrates how combining Monte Carlo policy evaluation of Q-functions with epsilon-greedy policy improvement can lead to learning optimal policies. Using the game of Blackjack as an example, the process shows how an agent, starting with no prior knowledge and a random policy, can interact with the environment, collect data, update Q-values, and gradually discover effective strategies. The resulting learned policy, derived through extensive simulation, shows a nuanced approach to standing or hitting based on the player's hand, the dealer's visible card, and whether the player has a usable ace. This highlights RL's ability to derive complex, optimal behaviors solely from interaction and reward signals, without explicit programming of rules.

Unifying RL algorithms: Sampling, bootstrapping, and backup diagrams

The lecture concludes by synthesizing the concepts discussed. Exact methods (like dynamic programming) compute exact expectations using known dynamics, while MC and TD learning use sampling to approximate expectations due to unknown dynamics. TD learning and dynamic programming utilize bootstrapping (updating estimates based on other estimates), whereas MC does not. These properties can be visualized using backup diagrams: dynamic programming and exhaustive search have broad backups (exploring many future states), while TD and MC typically have narrower backups. TD and dynamic programming use one-step backups, relying on bootstrapping, while MC and exhaustive search require reaching terminal states. This spectrum illustrates how various RL algorithms can be understood and constructed by combining sampling, bootstrapping, and different backup strategies (width and height).

Mentioned in This Episode

●Concepts

Common Questions

Imitation learning focuses on mimicking expert demonstrations to learn a policy. Reinforcement learning, on the other hand, learns through trial and error by interacting with the environment to discover solutions for optimal control problems.

Topics

Reinforcement Learning AI & Machine Learning Technology & Innovation Science & Mathematics Exploration Vs Exploitation Markov Decision Processes Value Functions Model-free Learning Policy Iteration Monte Carlo Methods TD Learning

Mentioned in this video

Concepts

Bellman optimality equation

A specific Bellman equation that characterizes the optimal value function in a Markov Decision Process.

Monte Carlo learning

A model-free reinforcement learning method that learns value functions by averaging the returns from complete episodes of experience.

Markov decision process

A mathematical framework used in reinforcement learning to model decision-making in situations where outcomes are partly random and partly under the control of a decision-maker.

Bellman expectation equation

A Bellman equation that describes the value function for a given policy, averaging over possible next states and actions.

Bellman equations

A set of equations used in dynamic programming and reinforcement learning that describe the relationship between the value of a state and the values of its successor states.

Media

Blackjack

A card game used as an example to illustrate Monte Carlo policy evaluation, demonstrating state representation, actions, rewards, and policy evaluation visualization.

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