Key Moments
Stanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 9: Stochastic Dyn. Program
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
Dynamic programming can handle system uncertainty by incorporating expected costs, but this significantly increases computational complexity and may require approximations for continuous or high-dimensional state spaces.
Key Insights
The Markov Decision Process (MDP) setting extends deterministic optimal control to handle stochastic disturbances (WK) where the transition dynamics are S_K+1 = F(S_K, U_K, W_K), and W_K is a random variable conditional on the current state and control.
In a risk-neutral formulation, the objective is to minimize the expected total cost, where the expectation is taken over all possible realizations of disturbance variables.
The principle of optimality still holds in stochastic dynamic programming, allowing the problem to be broken down into tail subproblems, enabling a backward recursion similar to the deterministic case.
For a stochastic LQR problem, the optimal control policy remains the same as the deterministic case (linear feedback), but the cost is increased by a constant term related to the noise magnitude.
Infinite horizon MDPs assume stationary dynamics and use a discount factor (gamma) to manage infinite sums of rewards, transforming the recursive Bellman equation into a fixed-point equation.
Q-functions (Q(X, U)) represent the cumulative reward of taking action U in state X and then acting optimally, offering a direct way to find optimal actions, especially when transition dynamics are unknown in learning settings.
Extending optimal control to stochastic environments
This lecture introduces closed-loop optimal control methods within discrete-time formulations, extending previous deterministic models to incorporate system uncertainty. The core extension is the introduction of a disturbance term, W_K, into the state transition equation, making it S_K+1 = F(S_K, U_K, W_K). This disturbance can represent various real-world uncertainties like wind gusts in aircraft control or market volatility in financial systems. Crucially, W_K is modeled as a random variable whose probability distribution can depend on the current state (S_K) and control (U_K), but not on the history of states or controls. This Markovian assumption simplifies computation while retaining significant generality. The objective remains to find an optimal control policy, a function that maps states to actions, aiming to minimize a cumulative cost that now includes stage-wise costs potentially dependent on the disturbance. To handle this stochasticity, the cost is defined as the expectation over all possible disturbance realizations, ensuring a deterministic quantity for optimization.
Markov Decision Processes and risk-neutrality
The framework discussed is that of Markov Decision Processes (MDPs), characterized by state transitions that depend only on the current state and control, and disturbances that are Markovian. The problem formulation assumes a risk-neutral approach, meaning the optimization targets the expected value of the cost. This contrasts with risk-sensitive formulations that might also consider the variance of the cost. The risk-neutral approach is favored due to its computational tractability; the linearity of the expectation operator allows the problem to be decomposed into stages, making dynamic programming applicable. While other communities use different notations (e.g., 'A' for action instead of 'U', 'S' for state instead of 'X'), the underlying mathematical principles are consistent. A key assumption is the additive cost structure and the Markovian nature of disturbances, which are essential for dynamic programming to apply effectively. The lecture clarifies that while the current state's evolution depends on the current disturbance, all historical dependencies are mediated through the current state, preserving the Markov property.
The principle of optimality in stochastic settings
Despite the introduction of uncertainty, the principle of optimality, fundamental to dynamic programming, still holds. This principle states that an optimal policy for the entire process must consist of optimal policies for all its subproblems. In the stochastic context, this means that if we are at a certain state S_K at time K and follow an optimal policy from that point onwards, the sequence of actions taken will be optimal for the remaining horizon. This property allows for a backward recursion, similar to the deterministic case. The Bellman equation for stochastic dynamic programming is formulated by minimizing the sum of the immediate expected cost (which accounts for the disturbance) and the expected cost-to-go from the next state. While the structure of the recursion is similar to the deterministic version, the calculations involve expectations over the disturbance distributions at each step. This enables computation of the optimal cost-to-go function J_K(S_K) and, consequently, the optimal policy. A practical implication is that once an optimal policy is computed, it can be applied without re-optimization, even if subsequent disturbance realizations differ from expectations.
Inventory control: A practical example
An illustrative example of an inventory control problem demonstrates the application of stochastic dynamic programming. The state S_K represents the stock level, the control U_K is the amount of new stock purchased, and the disturbance W_K is the customer demand. The state transition accounts for stock purchased, demand met, and unmet demand, with a capacity constraint on the warehouse. The stage-wise cost includes a purchase cost and a penalty for holding excess stock or failing to meet demand, all weighted by probabilities of different demand levels (e.g., 10% for 0 demand, 70% for 1 unit, 20% for 2 units). The terminal cost is zero. Solving this problem involves a backward recursion, calculating the optimal control U_K for each state S_K at each time step K. For instance, at stage 2, with stock S_2=0, the optimal purchase decision U_2 is found by minimizing the expected cost over possible demands, balancing the cost of purchasing stock against the risk of unmet demand. This example highlights how to manually compute Bellman recursions for discrete states and probabilities.
Stochastic LQR: Maintaining structure under uncertainty
The lecture also examines the Linear Quadratic Regulator (LQR) problem with stochastic dynamics. Here, the state transition is S_K+1 = A S_K + B U_K + W_K, where W_K is a Gaussian disturbance with zero mean and covariance Sigma. Remarkably, the dynamic programming solution for stochastic LQR retains a similar structure to its deterministic counterpart. By assuming the cost-to-go function J_K(S_K) is quadratic in S_K, the Bellman equation can be solved. The expectation over W_K introduces a term involving the trace of Sigma multiplied by the next state’s quadratic cost matrix (P_{K+1}). This leads to the conclusion that the optimal control policy remains a linear feedback of the state, just as in the deterministic LQR. The primary difference is that the overall cost is increased by a constant term related to the noise covariance, reflecting the inherent cost of operating under uncertainty.
Infinite horizon Markov Decision Processes
The discussion then shifts to infinite horizon MDPs, which are crucial for reinforcement learning. These problems optimize operations over an infinite number of stages, often used as an approximation for problems with a very large but finite number of stages. Key characteristics include stationary dynamics (transition probabilities do not depend on time) and the use of rewards instead of costs. An additional element is the discount factor, gamma (0 < gamma < 1), which multiplies future rewards. This factor serves two purposes: it intellectually models that future outcomes are less valuable than immediate ones, and pragmatically, it ensures that the total expected reward converges to a finite value, preventing infinite sums. The goal is to find a stationary policy (one that doesn't depend on time) that maximizes the discounted cumulative reward. The recursive Bellman equation for finite horizons transforms into a fixed-point equation in the infinite horizon setting, where V*(X) = max_U [R(X,U) + gamma * E[V*(X')]].
The role of Q-functions in learning
A powerful reformulation for infinite horizon MDPs involves the Q-function, Q(X, U), which represents the expected cumulative reward obtained by taking action U in state X and then following an optimal policy thereafter. The Q-function satisfies its own fixed-point equation derived from the Bellman equation. This formulation is particularly influential for learning-based control methods where the system's transition dynamics might be unknown. If an oracle provides the optimal Q-function, finding the optimal action in state X is simply a matter of maximizing Q(X, U) over all possible actions U. This is simpler than using the value function V*(X), which would require knowledge of the transition dynamics T(X'|X,U) to determine the optimal action. The Q-function formulation simplifies action selection in scenarios where only learning algorithms can estimate optimal policies without explicit knowledge of the environment's model.
Computational challenges and future directions
A significant challenge in dynamic programming, both deterministic and stochastic, is the 'curse of dimensionality.' The computational complexity grows exponentially with the number of state variables. For continuous state spaces, direct application of dynamic programming is impossible, necessitating discretization or other approximation techniques. The lecture previews that the next steps will involve algorithms like value iteration and policy iteration to solve infinite horizon Bellman equations and Q-function equations. These algorithms provide practical methods for finding optimal policies, particularly in scenarios where exact analytical solutions are not feasible. The discussion concludes by noting that continuous-time optimal control and extensions to learning-based control will be explored in subsequent lectures, building upon the foundational concepts of stochastic dynamic programming.
Mentioned in This Episode
●Software & Apps
●Organizations
●Books
●Concepts
●People Referenced
Common Questions
In deterministic optimal control, the system's future states are perfectly predictable given current states and controls. In stochastic optimal control, uncertainty is introduced through disturbances (random variables) that affect the system's dynamics or costs, requiring methods like dynamic programming with expectation.
Topics
Mentioned in this video
A mathematical framework used for modeling decision-making in situations where outcomes are partly random and partly under the control of a decision maker. It's central to the lecture's discussion on optimal control with uncertainty.
A probability distribution characterized by its bell-shaped curve, used to model the disturbance W in the stochastic LQR example.
More from Stanford Online
View all 126 summaries
75 minAStanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 8: Nonlinearity
78 minStanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 10: Reachibility Analysis
81 minStanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 6: Optimal Control
76 minStanford AA203 Optimal and Learning-Based Control | Spring 2026 | Lecture 7: Dynamic Programming
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