What is a Markov Decision Process (MDP)?

An MDP is a mathematical framework for modeling sequential decision-making where outcomes are partly random and partly under the control of a decision-maker. It involves states, actions, and a cost function.

What is the principle of optimality?

The principle of optimality states that if a sequence of decisions is optimal, then the remaining sub-sequence of decisions must also be optimal for the corresponding sub-problem.

How does dynamic programming solve decision-making problems?

Dynamic programming solves these problems by working backward from the end state, calculating the optimal cost for each sub-problem and using this information to solve larger problems, leveraging the principle of optimality.

What is the difference between deterministic and stochastic dynamic programming?

Deterministic dynamic programming assumes a predictable system, while stochastic dynamic programming accounts for randomness and uncertainty in system dynamics, often requiring the use of expected values.

What is the Markov property in stochastic models?

The Markov property assumes that the probability distribution of the next state depends only on the current state and control, not on past states or controls.

Why is dynamic programming computationally challenging?

Dynamic programming faces challenges like the curse of dimensionality, where the computational complexity grows exponentially with the number of state variables, and the curse of modeling, where accurate probability distributions can be hard to obtain.

What are the two main approaches for suboptimal dynamic programming (Reinforcement Learning)?

The two main approaches are approximating the problem in the value space (approximating the optimal future cost) and approximating in the policy space (choosing a policy from a restricted class of policies).

How does Reinforcement Learning differ from traditional Dynamic Programming?

Reinforcement learning often deals with situations where the full model is unknown or too complex, requiring approximations or learning from data, unlike traditional dynamic programming which assumes a known model.

What is the role of the Bellman equation in dynamic programming?

The Bellman equation is a recursive formula used in dynamic programming to break down the problem into smaller sub-problems, allowing for the calculation of optimal costs and policies.

Key Moments

Stanford AA274A Principles of Robotic Autonomy | Autumn 2019 | Decision Making Under Uncertainty

Stanford Online

Education5 min read72 min video

Nov 4, 2026|56 views|4

Stanford Stanford Online Robotics

Save to Pod

Key Moments

TL;DR

Robots can now make complex decisions under uncertainty using dynamic programming, but scaling these methods to real-world complexity remains a major challenge.

Key Insights

The core problem of sequential decision-making under uncertainty can be modeled using Markov Decision Processes (MDPs).

The principle of optimality states that an optimal path has optimal subpaths, forming the foundation for dynamic programming.

Dynamic programming solves sequential decision problems by working backward from the end, calculating optimal future costs for each state.

In the deterministic case, dynamic programming calculates a single optimal control sequence, which can be risky if the system deviates from the expected path.

The stochastic version of dynamic programming accounts for uncertainty by taking the expected value of future costs, leading to optimal closed-loop policies.

The curse of dimensionality, partial observability, and model uncertainty pose significant challenges to applying dynamic programming, leading to research in 'suboptimal' dynamic programming or reinforcement learning.

Framing decisions under uncertainty for robots

This lecture introduces advanced topics in robotic autonomy, focusing on high-level decision-making under uncertainty, such as deciding when to change lanes or cross an intersection. Unlike path planning which focuses on precise movements, these high-level decisions are critically influenced by uncertainty in perception and environmental reconstruction. Predicting human behavior, for instance, is inherently uncertain and must be factored into decisions that balance safety and efficiency. The mathematical framework for this is typically a Markov Decision Process (MDP), and the core algorithmic approach discussed is dynamic programming.

The mathematical model for sequential decision-making

The problem is modeled with a discrete-time, deterministic dynamical system: $x(k+1) = f(x(k), u(k))$, where $x$ is the state and $u$ is the control. Control constraints limit possible actions at each state. The objective is to minimize a cumulative cost function, defined as the sum of stage costs $g_k(x(k), u(k))$ plus a final cost $J_f(x_N)$. This formulation leads to an open-loop control strategy, where a sequence of controls is pre-calculated. While simple, open-loop control is generally unsafe because it doesn't account for state deviations due to unmodeled disturbances. The core challenge is the combinatorial explosion of possible control sequences, necessitating a more efficient approach than brute-force enumeration.

The principle of optimality as a computational shortcut

The principle of optimality, a cornerstone of dynamic programming, states that an optimal trajectory has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with respect to the state following the first decision. In simpler terms, if a path from A to E is optimal, then the portion of that path from B to E (where B is the state after the first step) must also be optimal for the subproblem of going from B to E. This is proven by contradiction: if a better path existed from B to E, it could be appended to the A-to-B segment to create a globally superior path from A to E, contradicting the initial assumption of optimality. This principle is crucial because it allows us to avoid re-calculating optimal solutions for subproblems that have already been solved.

Dynamic programming: working backward to find the optimal solution

Dynamic programming (DP) leverages the principle of optimality to solve sequential decision problems by working backward in time. It starts by defining the optimal cost-to-go from the final time step (usually zero). Then, iteratively, it calculates the optimal cost-to-go for each preceding time step by considering all possible actions and their immediate costs, plus the already computed optimal cost-to-go from the resulting next state. This process continues until the initial time step is reached. The algorithm essentially solves the Bellman equation: $J_k(x) = min_{u in U(x)} {g_k(x,u) + J_{k+1}(f(x,u))}$, where $J_k(x)$ is the optimal cost-to-go from state $x$ at time $k$. This approach guarantees a globally optimal solution but can be computationally intensive due to the 'curse of dimensionality'.

Extending dynamic programming to stochastic environments

In stochastic environments, the system dynamics include a random disturbance term $w_k$. The state transition becomes $x(k+1) = f(x(k), u(k), w_k)$. Crucially, the probability distribution of $w_k$ must be known and depend only on the current state and control (Markov assumption). The objective then shifts from finding an open-loop control sequence to finding a closed-loop control *policy* – a function that maps states to actions. The cost function is adapted by taking the expected value over the random disturbances. The dynamic programming equation is modified to $J_k(x) = min_{u in U(x)} {E_{w_k}[g_k(x,u,w_k) + J_{k+1}(f(x,u,w_k))] }$. This ensures that decisions are robust to uncertainty, aiming for optimal expected performance.

Challenges and suboptimal approaches

The primary challenge with dynamic programming is the 'curse of dimensionality': the computational cost grows exponentially with the number of state variables. This makes exact DP intractable for problems with high-dimensional state spaces or continuous state variables (requiring discretization and interpolation). Furthermore, partial observability (where the exact state is unknown) leads to Partially Observable MDPs (POMDPs), significantly increasing complexity. Model uncertainty, where the transition dynamics or cost functions are not precisely known and must be learned from data, presents another hurdle ('curse of modeling'). These challenges motivate research into 'suboptimal' dynamic programming, often referred to as reinforcement learning, which seeks approximate solutions that are computationally feasible.

Approximation strategies in reinforcement learning

Reinforcement learning tackles the limitations of exact DP through approximation. Two main strategies are discussed: 1) Value function approximation, where the optimal future cost function is approximated (e.g., using neural networks), thus simplifying the Bellman equation. This can involve approximating the problem itself or using function approximators. 2) Policy space approximation, where the search for an optimal policy is restricted to a simpler, parameterized class of policies. Instead of optimizing over all possible functions, the problem becomes optimizing a finite set of parameters. These approaches allow for scalable solutions to complex problems where exact DP is not feasible, especially when dealing with large state spaces or unknown system dynamics that must be learned online or offline.

Mentioned in This Episode

●Software & Apps

●Organizations

●Concepts

●People Referenced

Common Questions

This lecture focuses on decision-making under uncertainty, specifically using the framework of Markov Decision Processes and the core algorithm of Dynamic Programming.

Topics

AI & Machine Learning Technology & Innovation Science & Mathematics Decision Making Optimal Control

Mentioned in this video

People

Dimitri Bertsekas

Professor at MIT and author of a book on reinforcement learning and optimal control, which unifies these two fields.

Søren Kierkegaard

A philosopher quoted for his idea that life must be lived forwards but understood backwards, relating to dynamic programming.

Concepts

Partially Observable Markov Decision Processes

Problems arising from partial observability of states, making dynamic programming more complex.

Reinforcement Learning

Presented as an approximate solution to Markov decision problems, and a topic for future discussion.

Bayesian filtering

Mentioned as a similar concept to the dynamic model, but with the key difference being estimation versus control.

Markov Decision Processes

The framework used for decision making under uncertainty discussed in the lecture, forming the basis for dynamic programming.

Bellman Equation

The equation solved iteratively in dynamic programming to find optimal costs.

Dynamic Programming

The core algorithm discussed for solving sequential decision-making problems under uncertainty.

Organizations

Massachusetts Institute of Technology

The academic institution where Dimitri Bertsekas was a professor.

NASA

The agency where the speaker has to attend a review meeting, causing them to miss the next lecture.

Software & Apps

Hamilton-Jacobi-Bellman Equation

The continuous-time equivalent of the dynamic programming principle.

Locations

NASA Ames Research Center

The location where the speaker will be for a review meeting.

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