---
tag: WA3974X06N
kind: definition
name: Differential dynamic programming
msc: [49M15, 49L20, 93C55]
defines: 5D0J26E619
uses: [0693Y2METT, 0ABK9V9Y64, 07EXVNF9VP]
sources:
  - url: https://en.wikipedia.org/wiki/Differential_dynamic_programming
---

## Definition

Let $F \colon \R^n \times \R^m \to \R^n$, $\ell \colon \R^n \times \R^m \to \R$ and $\ell_f \colon \R^n \to \R$ be twice continuously differentiable, and let $N \ge 1$.
Consider the problem of minimising $\sum_{k=0}^{N-1} \ell(x_k, u_k) + \ell_f(x_N)$ over $u_0, \dots, u_{N-1} \in \R^m$, where $x_{k+1} = F(x_k, u_k)$ and $x_0$ is given.
Subscripts denote partial derivatives, $\nabla^2$ a [[Hessian|0693Y2METT]] and $\nabla$ a [[gradient|0ABK9V9Y64]].
One iteration of *differential dynamic programming* starts from controls $\bar u_k$ with states $\bar x_k$ and does the following.

1. Backward pass: set $V_x = \nabla \ell_f(\bar x_N)$ and $V_{xx} = \nabla^2 \ell_f(\bar x_N)$. For $k = N - 1, \dots, 0$, take all derivatives at $(\bar x_k, \bar u_k)$ and $V_x, V_{xx}$ from step $k + 1$. Compute
$$Q_x = \ell_x + F_x^T V_x, \quad Q_u = \ell_u + F_u^T V_x,$$
$$Q_{xx} = \ell_{xx} + F_x^T V_{xx} F_x + V_x \cdot F_{xx}, \quad Q_{uu} = \ell_{uu} + F_u^T V_{xx} F_u + V_x \cdot F_{uu}, \quad Q_{ux} = \ell_{ux} + F_u^T V_{xx} F_x + V_x \cdot F_{ux},$$
where $V_x \cdot F_{xx}$ is the matrix $\sum_i (V_x)_i \nabla_x^2 F_i$ and similarly for the others. If $Q_{uu}$ is positive definite, set $d_k = -Q_{uu}^{-1} Q_u$, $K_k = -Q_{uu}^{-1} Q_{ux}$, and update $V_x \leftarrow Q_x - Q_{ux}^T Q_{uu}^{-1} Q_u$ and $V_{xx} \leftarrow Q_{xx} - Q_{ux}^T Q_{uu}^{-1} Q_{ux}$.
2. Forward pass: set $x_0^{\text{new}} = x_0$ and, for $k = 0, \dots, N - 1$, set $u_k^{\text{new}} = \bar u_k + d_k + K_k (x_k^{\text{new}} - \bar x_k)$ and $x_{k+1}^{\text{new}} = F(x_k^{\text{new}}, u_k^{\text{new}})$.

The new controls replace $\bar u_k$, and the iteration is repeated until the corrections $d_k$ are small.

## Remarks

The function $Q$ is the second-order expansion of $\delta x, \delta u \mapsto \ell(\bar x_k + \delta x, \bar u_k + \delta u) + V_{k+1}(F(\bar x_k + \delta x, \bar u_k + \delta u))$, where $V_{k+1}$ is the quadratic model of the cost-to-go.
The correction $\delta u = d_k + K_k \delta x$ minimises this quadratic model in $\delta u$, and the update of $V_x, V_{xx}$ gives the model of the minimum.
Dropping the terms with second derivatives of $F$ gives the iterative linear-quadratic regulator.
In practice one scales $d_k$ by a step size and adds a multiple of the identity to $Q_{uu}$ for robustness.

Example: if $F(x, u) = A x + B u$ and $\ell$, $\ell_f$ are quadratic forms with $\ell_{uu}$ positive definite, the expansions are exact.
Then the backward pass is the discrete Riccati recursion of the linear-quadratic regulator, and one iteration gives the optimal controls from any starting guess.

Non-example: take $\ell = -u^2$, $F(x, u) = x$ and $\ell_f = 0$, so that $Q_{uu} = -2$ is not positive definite.
The quadratic model has no minimiser in $\delta u$, and the step of clause 1 is not defined.

## Explanations

### L1 human

Each iteration fits quadratic models of the costs around the current trajectory, solves them backward in time, and then simulates the improved controls forward.