# The principle of optimality

Start from the end and work your way backwards: Words to live by. Yet our daily experience is lived *forwards in time* and not backwards. According to our experience, one thing happens after another:
$$x\_{k+1} = f\_k(x\_k,u\_k)$$
and if we are to affect it (by choosing \\(u_k\\) to modify \\(f_k\\)), then we are going to affect the future and not the past. Perhaps this is why some people naïvely think that an optimal policy can be determined through forward computation. Although I find this unintuitive, as do many others (more on this below), I have seen such opinions appear from time to time even in the most educated circles.

To formalize the naïve view, let us assume a cost functional,
$$F\_T(x\_k) + \sum\_{k=0}^{T−1} F\_k(x\_k,u\_k)$$
and ask if it is possible to determine an optimal policy forwards in time. Define, 
$$\tilde V\_k(x\_0,u\_0,\dots,u\_k) = \sum\_{i=0}^k F\_i(x\_i,u\_i)$$
so that,
$$\tilde V\_{k+1}(x\_0,u\_0,\dots,u\_k,u\_{k+1}) = \tilde V\_k(x\_0,u\_0,\dots,u\_k) + F\_{k+1}(x\_{k+1},u\_{k+1})$$

Suppose we want to find the minimum<sup>[1](#note1)</sup> of the function \\(\tilde V\_{k+1}\\). We would need to optimize over the variables \\(u\_0\\),...,\\(u\_{k+1}\\) without exception. There is in general no way to find the optimum of \\(\tilde V\_{k}\\) and use this information to optimize \\(\tilde V\_{k+1}\\). This is because the term \\(x\_{k+1}\\) in \\(F\_{k+1}(x\_{k+1},u\_{k+1})\\) depends on all variables \\(u\_k\\) preceding \\(u\_{k+1}\\), so determining the optimum of \\(\tilde V\_{k+1}\\) would necessarily influence the decision variables used in determining the optimum of \\(\tilde V\_{k}\\). Therefore, given a certain state, optimizing forwards in time can give us an optimum with respect to that state, but in no way can it generally be used to determine an optimal policy.

The inverse of this realization is encapsulated in the *principle of optimality*, which states that:

> An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

> **R.E. Bellman** ([1957](https://www.worldcat.org/search?q=9780486428093))

Bellman had more to say on the topic of determining an optimal policy:

> In place of determining the optimal sequence of decisions from the **fixed** state of the system, we wish to determine the optimal decision to be made at **any** state of the system. Only if we know the latter, do we understand the intrinsic structure of the solution.

> **R.E. Bellman** ([1957](https://www.worldcat.org/search?q=9780486428093))

The implication is that the principle of optimality leads to closed-loop *control laws*, as opposed to mere open-loop *control*. Previous to Bellman, various thinkers had encountered this principle and even dismissed it as trivial. Remarkably, Rufus Isaacs formulated his own, game-theoretic version and called it the *tenet of transition*:

> If the play proceeds from one position to a second and V is thought of as known at the second, then it is determined at the first by demanding that the players optimize (that is, make minimax) the increment of V during the transition.

> **R.P. Isaacs** ([1951](https://www.rand.org/pubs/papers/P257.html))

Isaacs, even with an intrinsic understanding that differential games require closed-loop control laws, later came to regret dismissing the importance of his tenet:

> Once I felt that here was the heart of the subject and cited it often in the early Rand seminars. Later I felt that it – like other mathematical hearts – was a mere truism. Thus, in Differential Games it is mentioned only by title. This I regret. I had no idea that Pontryagin's principle and Bellman's maximal principle (a special case of the tenet, appearing a little later in the Rand seminars) would enjoy such widespread citation.

> **R.P. Isaacs** ([1973](https://www.worldcat.org/search?q=9780720420807))

Let me now state my own understanding of the principle:

> An optimal policy remains optimal backwards in time.

Start from the end and work your way backwards: Words to live by.

The rest of this post contains derivations of the Bellman and Hamilton-Jacobi-Bellman (HJB) equations.

### Discrete time (Bellman equation)

Consider the optimal control problem,
$$\min\_u F\_T(x\_T) + \sum\_{i=0}^{T−1} F\_i(x\_i,u\_i)$$
where,
$$x\_{k+1}=f\_k(x\_k,u\_k)$$
for all \\(k \in \mathbb Z_T\\), and let,
$$V\_k(x') = \min\_u F\_T(x\_T)+ \sum_{i=k}^{T−1} F\_i(x\_i,u\_i)$$
where \\(x\_k = x'\\).

The Bellman equation follows easily,
\\[
\begin{align}
V\_k(x') &= \min\_u F\_T(x\_T) + \sum\_{i=k+1}^{T−1} F\_i(x\_i,u\_i) + F\_k(x',u\_k) \newline 
&= \min\_u V\_{k+1}(x\_{k+1})+F\_k(x',u\_k)
\end{align}
\\]
Replacing with the expression for \\(x\_{k+1}\\), we obtain the result: 
$$V\_k(x)= \min\_u V\_{k+1}(f\_k(x,u)) + F\_k(x,u)$$
with final condition \\(V\_T(x) = F\_T(x)\\).

#### Discounted time

Oftentimes, the cost functional is discounted in time: 
$$\min\_u \gamma^T \bar F\_T(x\_T) + \sum\_{i=0}^{T−1} \gamma^i \bar F\_i(x\_i,u\_i)$$

A direct application of the Bellman equation gives us the result,
$$V\_k(x) = \min\_u V\_{k+1}(f\_k(x,u)) + \gamma^k \bar F\_k(x,u)$$

To avoid the appearance of small terms \\(\gamma^k \bar F\_k\\) in the Bellman equation, we make a change of variables \\(V\_k = \gamma^k \bar V\_k\\), obtaining, 
$$\bar V\_k(x) = \min\_u \gamma \bar V\_{k+1}(f\_k(x,u))+\bar F\_k(x,u)$$

### Continuous time (HJB equation)

Consider the optimal control problem,
$$\min\_u F\_T(x(T)) + \int\_0^T F(x(t),u(t),t)dt$$
where,
$$\dot x(t) = f(x(t),u(t),t)$$
for all \\(t \in [0,T]\\), and let,
$$V(x',t) = \min\_u F\_T(x(T))+ \int\_t^T F(x(\tau),u(\tau),\tau)d\tau$$
where \\(x(t) = x'\\).

We begin as in the derivation of the Bellman equation, optimizing over a time-step \\(h\\),
\\[
\begin{align}
V(x',t) &= \min\_u F\_T(x(T)) + \int\_{t+h}^T F(x(\tau),u(\tau),\tau)d\tau + \int\_t^{t+h} F(x(\tau),u(\tau),\tau)d\tau \newline 
&= \min\_{u|\_{\[t,t+h\]}} V(x(t+h),t+h) + \int\_t^{t+h} F(x(\tau),u(\tau),\tau)d\tau
\end{align}
\\]

Taking \\(V(x(t),t+h)\\) away from both sides,
\\[
\begin{multline}
V(x',t)-V(x(t),t+h) \newline
= \min\_{u|\_{\[t,t+h\]}} V(x(t+h),t+h)-V(x(t),t+h) + \int\_t^{t+h} F(x(\tau),u(\tau),\tau)d\tau
\end{multline}
\\]
Dividing by \\(h\\) and taking the limit \\(h \to 0\\),
$$−\frac{\partial V}{\partial t}(x',t) = \min\_u \frac{\partial V}{\partial x}(x',t) \cdot \dot x + F(x',u,t)$$

Replacing with the expression for \\(\dot x\\), we obtain the result:
$$−\frac{\partial V}{\partial t}(x,t) = \min\_u \frac{\partial V}{\partial x}(x,t) \cdot f(x,u,t) + F(x,u,t)$$
with final condition \\(V(x,T) = F_T(x)\\).

#### Discounted time

When the cost functional is discounted in time, 
$$\min\_u e^{-\rho T}\bar F\_T(x(T)) + \int\_0^T e^{-\rho t}\bar F(x(t),u(t),t)dt$$
we can take a similar approach as in the case of discrete time. Specifically, we make a change of variables \\(V = e^{-\rho t} \bar V\\), obtaining,
$$−\frac{\partial \bar V}{\partial t}(x,t) = -\rho\bar V(x,t) + \min\_u \frac{\partial \bar V}{\partial x}(x,t) \cdot f(x,u,t) + \bar F(x,u,t)$$

### Postface

This post started when I sat down to re-derive the HJB equation for the umpteenth time. I figured it was about time to put a stop to that and write a note that I could refer to in the future. The history lesson is a bonus; I hope you enoyed it.

### References

* H.J. Pesch & R. Bulirsch, "[The maximum principle, Bellman's equation, and Carathéodory's work](https://doi.org/10.1007/BF02192933)," 1994
    
* D. Liberzon, "[Calculus of variations and optimal control theory: A concise introduction](http://liberzon.csl.illinois.edu/teaching/cvoc/cvoc.html)," 2011
    

---

<sup>1</sup> For convenience, I am assuming in this post that functions are well-behaved enough so that the extremum not only exists, but is unique.