Sequential optimization & control

Parent: optimization

Optimize over a sequence / over time / under uncertainty — not one static x but a policy.

Dynamic programming

• Bellman equation V(s)=max_a[r(s,a)+γV(s′)] — the value function defined self-referentially (a fixed point);
• Value / policy iteration converge because the Bellman operator is a γ-contraction (recursion-convergence-contraction);
• Curse of dimensionality → approximate DP.

Optimal control (continuous time)

• Calculus of variations → Euler–Lagrange (we touched this in Holmström);
• Pontryagin's Maximum Principle — the adjoint (costate) equation, solved backward (= backprop / the adjoint method);
• Hamilton–Jacobi–Bellman (HJB) PDE — the continuous-time Bellman; its solution is the value function. → dynamics-to-a-fixed-point.

Reinforcement learning

DP when the model is unknown and you sample: TD learning, Q-learning, policy gradients, actor-critic. RL = stochastic optimal control by trial.

Online optimization / learning

• Decisions arrive over time, adversarially; measure regret (vs the best fixed choice in hindsight);
• Online gradient descent, FTRL (follow-the-regularized-leader);
• Bandits (explore/exploit under partial feedback), UCB, Thompson sampling → the core of MCTS's UCT.

Robust / stochastic programming

Optimize under uncertainty: stochastic programming (expectation), robust optimization (worst case), chance constraints (probabilistic).

The theme

The object is a policy over a horizon under uncertainty; Bellman's self-referential fixed point + contraction is the backbone, and it's literally the math under our recursion/convergence thread.