Stanford AA203 Optimal and Learning‑Based Control ｜ Spring 2026 ｜ Lecture 9： Stochastic Dyn. Program— Annotated Lecture Notes & Key Takeaways

Course Information

Institution: Stanford

Original Course: Stanford AA203 Optimal and Learning‑Based Control ｜ Spring 2026 ｜ Lecture 9： Stochastic Dyn. Program

Instructor Bio: Delivered by Prof. Marco Pavone and Dr. Daniele Gammelli, whose key research focus is optimal control for stochastic dynamical systems.

Course Description: This session focuses on stochastic dynamic programming. It introduces Markov Decision Processes, derives stochastic versions of value and policy iteration, and explains the HJB equation and solution frameworks for stochastic optimal control.

This set of notes covers lecture nine of Stanford’s AA203 course, focused on stochastic dynamic programming. The instructor walks through how we take familiar discrete‑time optimal control ideas and adapt them for systems with real‑world random uncertainty. We move past fully predictable deterministic dynamics and build up the Markov Decision Processes (MDP) framework step‑by‑step. I tried to capture both the core technical setup and moments where concepts felt tricky, as well as small asides from in‑class student questions.
 

Shifting from deterministic to stochastic system models

 

The lecture opens by revisiting the course’s existing roadmap. Up to this point, the class worked with deterministic discrete‑time optimal control. Every state transition could be perfectly calculated if you knew your starting state and chosen control input. Now we add random disturbances that mess with how states evolve forward in time.
 

In the old setup, the next state came purely from a function of current time step, current state, and current control action. We now insert a disturbance term \(w_k\) into this update rule. Disturbances represent outside random influences acting on our system (00:25). The instructor gave simple, tangible examples. For aircraft flight control, disturbances could be wind gusts. For stock trading decision problems, disturbances stand in for unpredictable market shifts.
 

The operational flow works like this: you observe the current state \(x_k\), pick a control \(u_k\), and then “nature” samples a disturbance value \(w_k\). The ordering of these steps is somewhat arbitrary, but you have to fix this sequence to make the mathematical model usable. Just like in the deterministic case, our control inputs still must sit within a predefined allowed set.
 

Disturbances are treated as random variables. They can follow nearly any probability distribution; Gaussian is one possibility but not a requirement. A disturbance’s probability law can depend on the present‑day state and the control you just selected. However, here comes the critical Markov rule. A disturbance’s distribution cannot depend on older states from previous time steps. It cannot look back at \(x_{k‑1}\), \(x_{k‑2}\) or the full history of the system (00:41).
 

I found this rule a little confusing on first pass. Past disturbances absolutely do shape future states indirectly. A past disturbance changes \(x_{k+1}\), and then that new current state influences what future disturbances might look like. All historical information gets funneled exclusively through the value of the present‑day state. The system does not get separate, direct access to old measurements. The lecturer called this a mild restriction. The trade‑off is practical: we sacrifice some possible real‑world model flexibility so we get math we can actually compute solutions with.
 

A student raised a clarifying question about this exact nuance. The student wanted to know if disturbances at one time step directly link to disturbances from prior steps. The professor clarified there is no direct dependency. Any connection works only through the intermediate state variable. Even though later states carry echoes of every earlier disturbance, each new disturbance sample only sees the right‑now state and control (08:00). This distinction is easy to mix up when first learning MDPs.
 

Problem formulation for Markov Decision Processes

 

This section lays out all building blocks that define a Markov Decision Process for optimal control. Our goal remains closed‑loop control policies. In stochastic settings, feedback policies become even more important. Random noise pushes the system around in unexpected directions, so we need rules that react to whatever state we land in. A policy \(\pi\) maps any possible state to a suitable control action.
 

Cost functions still follow the additive structure we saw in deterministic problems. We have a terminal cost term for the final time step plus running stage costs for every intermediate step. One new twist: stage costs are permitted to depend on the disturbance itself. Since disturbances are random, the total accumulated cost is no longer a fixed number — it becomes a random variable.
 

You cannot directly minimize or maximize a random variable. You need to convert it into a deterministic value you can optimize over. The approach taught in this lecture uses expected value. We optimize the expected total cost, averaging across every possible sequence of disturbance realizations (06:44). This is called a risk‑neutral formulation.
 

Risk‑neutral does not account for variance or worst‑case bad outcomes. The professor used a relatable betting analogy. If you place a bet, risk‑neutral optimization only cares about average payout. It does not try to shield you from catastrophic losses, even if those bad outcomes happen rarely. The lecture notes mention more advanced risk‑sensitive formulations that add variance or other risk terms. Those are mathematically harder. The standard optimality principle and classic dynamic programming equations stop working in those settings, requiring brand‑new analysis. The instructor noted he has done research in this area, but the class will stick with risk‑neutral MDPs for simplicity (14:50).
 

The lecture also briefly contrasts two alternative problem paradigms that will not be covered. One is risk‑sensitive stochastic optimization mentioned above. The other is adversarial minimax formulation. Instead of sampling disturbances from probability distributions, you imagine an adversarial opponent picks the worst‑possible disturbance each step. That becomes a zero‑sum game‑against‑nature, a completely different mathematical setup.
 

Terminology mismatch across research communities gets a quick shout‑out. Control theory uses \(u_k\) for controls and \(x_k\) for states. Computer science reinforcement learning literature typically writes \(a_k\) for actions and \(s_k\) for states. The professor points to a well‑known review paper nicknamed a “Rosetta Stone for stochastic optimization” that translates notation between control, operations research and AI fields. He joked that today you might just ask an LLM to sort notation confusion out, but the paper remains a useful reference (16:40).
 

Optimality principle and stochastic dynamic programming algorithm

 

With the full MDP definition established, we move to the optimality principle extended to stochastic systems. An optimal policy \(\pi^*\) is a whole sequence of decision rules, one for each time index from start until one step before termination. Each rule takes a state and returns the optimal control for that moment.
 

We examine tail subproblems. Imagine we arrive at time i, observe state \(x_i\), and only care about performance from time i all the way to the final horizon N. The optimality principle says: if your full‑horizon policy is optimal, then the tail segment of that policy must also be optimal for this shorter subproblem starting at time i.
 

The intuition mirrors deterministic dynamic programming, but the proof involves more steps. The instructor points readers toward Dimitri Bertsekas’ textbooks on optimal control, listed in the course syllabus, for formal proof. In lecture, they skip walking through the proof because it does not add much conceptual insight.
 

The optimality principle itself is mostly conceptual knowledge. It does not immediately give you usable computer code. Its real value is justifying why we can apply backwards recursion for stochastic dynamic programming.
 

The algorithm structure looks very similar to deterministic dynamic programming. We solve starting at the final time horizon and work backwards one time stage at a time.
 

At the final time N, the cost‑to‑go function \(J_N(x_N)\) equals our predefined terminal cost. Then we step backward recursively. For each time step k and each possible state \(x_k\), we search for the control \(u_k\) that strikes the best balance between immediate stage cost and the expected future cost‑to‑go from subsequent states. The expectation here averages over all possible next‑state outcomes caused by random disturbance draws.
 

One point that was hard to follow here is how exactly expectation integrates into each backward step. In deterministic DP you just look up the exact next‑state cost. Stochastic DP forces you to compute an expectation over many possible next states, each weighted by their probability of occurring. Every backward pass mixes minimization over controls and expectation over stochastic transitions.
 

Key assumptions and their practical limits

 

This section collects implicit and explicit assumptions built into this MDP framework, along with limitations the lecturer called out.
 

First, the Markov property. All random disturbance distributions condition only on current state and control. They cannot draw information from the full historical trajectory. Indirect history influence is okay, but must flow entirely through the present state value. This is convenient mathematically, but real‑world systems sometimes violate this assumption. Some real‑world noise processes genuinely do depend on past states in ways you cannot capture just using today’s state. In those cases this vanilla MDP model would be misspecified. You could expand your state vector to encode history, but that inflates computational difficulty.
 

Second, risk‑neutral expected‑cost objective. This treats lucky and unlucky outcomes symmetrically. If your application cannot tolerate rare but devastating failures, risk‑neutral MDP will produce suboptimal real‑world behavior. The lecturer flagged this as an unanswered question within the scope of the course: how do you properly balance average performance against avoiding terrible scenarios? Risk‑sensitive formulations answer this, but break the standard dynamic programming recursion. There is no simple drop‑in fix, and computation becomes much heavier.
 

Third, we assume full state observation. Every time step we perfectly observe the true current state \(x_k\). The lecture does not cover partial observability. In many real‑world deployments you only get noisy sensor readings, not true state values. That would become a POMDP (Partially Observable Markov Decision Process), which is significantly harder. This lecture stays strictly within fully observed MDP territory.
 

The lecturer emphasizes these assumptions represent a deliberate compromise. We want models rich enough to capture real‑world randomness, yet simple enough that we can derive actionable computational recipes. We give up some modeling expressiveness to gain tractable algorithms.
 

Closing takeaways from stochastic dynamic programming

 

We wrap up by circling back to the core keyword stochastic dynamic programming. The big takeaway is that many structural patterns you learned for deterministic optimal control carry over to stochastic settings. Backward recursion still works, but every step adds an expectation operation over random state transitions driven by disturbances.
 

All the machinery builds on the MDP setup: discrete time, Markov property, full state access, additive cost, risk‑neutral expected‑value optimization. Student questions in lecture helped tease apart subtle gotchas, especially the difference between direct dependence versus indirect, state‑mediated dependence on past disturbances.
 

While the optimality principle is intellectually satisfying, practical value lies in the backwards recursive algorithm. It gives us concrete steps to compute optimal closed‑loop feedback policies for systems hit by random noise. The lecture also points out boundaries. This framework is not universal. It cannot handle partial observation, risk aversion, or adversarial disturbance without switching to entirely different mathematical tools.

Content Disclaimer: This article is for general reference only and does not constitute professional R&D guidance, production process advice or quality certification. All material performance data has specific test premises; readers should verify parameters against actual equipment and working conditions.