Course Syllabus
Sequential Decision Problems
Foundations, Finite Horizon & Basic DP.
Principle of Optimality
Tail Sub-problems & Backward Induction.
Scheduling Example
Discrete-State DP in Action.
DP Algorithm & Examples
General Algorithm & Real-world Applications.
Optimal Control & Shortest Path
Forward Pass & Graph Representation.
Q-Factors & TSP
Alternative DP form & Traveling Salesman Problem.
TSP Algorithm
Python Implementation & Discrete Optimization.
Approx. in Value Space
Overcoming computational limits with approximations.
Lookahead Approx.
One-Step vs Multistep Lookahead and Chess Example.
Rollout with Base Heuristic
On-line approximation using base policy simulation.
TSP with Rollout
Improving Nearest Neighbor heuristic with Rollout.
Infinite Horizon Problems
Value Iteration, Policy Iteration, and Bellman Equation.
Linear Quadratic Problems
Riccati Equation, Newton's Method, and Rollout.
DP with Time Delays
State Augmentation and Non-additive Costs.
DP with Forecast
Augmented System and Conditional Expectation.
Uncontrollable States
Simplifying DP by Averaging Out.
DP for Tetris
Stochastic Formulation and Challenges.
POMDP & Belief State
Partial Information and Sufficient Statistics.
Bidirectional Parking
Belief State DP and Multiagent Teaser.
Multiagent Rollout
Efficient Control for Multiagent Systems.
Model Predictive Control
Optimization, Constraints, and Applications.
Exercising an Option
Optimal Stopping and Rollout Comparison.
RL vs DP Terminology
The Rosetta Stone of Sequential Decision Making.
Approximation in Value Space
Bridging Exact DP and RL.
Four Queens Problem
Constraint Satisfaction & DP.
General Discrete Optimization
Sequential View of Optimization.
Approx. in Value Space
Deterministic Problems & Q-Factors.
Rollout Algorithms
Discrete Optimization & Routing.
Cost Improvement
Sequential Consistency & Improvement.
Advanced Rollout
Parallel & Simplified Strategies.
Model-Free Rollout
Truncated, Expert-Guided & LLMs.
DeepSeek & GRPO
Group Relative Policy Optimization.
RNA Folding
Discrete Optimization in Biology.
Value & Policy Approx.
Training Nonlinear Architectures.
Fitted Value Iteration
Sequential Backward Training.
Linear Programming
Exact & Approximate LP Methods.
Policy Space Approx.
Parametrization & Expert Training.
Optimization Framework
Random Search & Cross Entropy.
Policy Gradient Methods
Deterministic vs Stochastic Problems.
Approx. Gradient Methods
Log-Likelihood Ratio & Cost Shaping.