This is a quick refresher on the basic formulation and ideas of Hamilton-Jacobi-Bellman (“HJB”) in optimal control, including dynamic programming for both deterministic and stochastic formulations.

The notes and notation here are adapted from [1], with additional notes from [2] and [3]. (We keep mean field game theory in mind for down the road.) I go into much more detail to understand each aspect.

• I prioritize intuition/readability linking to references where appropriate.
• We will focus on the key equations, not go too deeply into proofs and may skip some parts for brevity.
• There may be imprecisions: all feedback and corrections are welcome.
• Long equations may not show up on mobile.

Lastly, this focuses solely understanding HJB through the dynamic programming perspective. Later topics around the calculus of variations, Euler-Lagrange, viscosity solutions, etc. will be covered in future posts.

In a nutshell: the HJB equation defines the optimal control

From Wikipedia:

The Hamilton-Jacobi-Bellman (HJB) equation is a nonlinear partial differential equation that provides necessary and sufficient conditions for optimality of a control with respect to a loss function. Its solution is the value function of the optimal control problem which, once known, can be used to obtain the optimal control by taking the maximizer (or minimizer) of the Hamiltonian involved in the HJB equation.

where the value function is the optimal cost, with some associated optimal trajectory of states.

Hamilton-Jacobi-Bellman, deterministic

Here we formulate the simplest, deterministic version of an agent’s optimal control problem.

The agent’s control problem

An agent faces the following deterministic optimal control problem:

The explanation is as follows. Over the finite time horizon \(t=0, \dots, T\), the agent wants to minimize the cost functional \(\mathcal{J}\), which consists of a “running” cost \(L(.)\) at each time \(t\), and then a “terminal” cost \(G(.)\) at the last time period \(T\).

At each time step \(t=0,\dots,T\), the mechanics are as follows:

• The agent begins with a vector of states \(x_t \in \mathcal{R}^d\).
• Subsequently the agent decides which actions to take, aka the vector of controls \(a_t \in \mathcal{R}^m\).
  • This vector \(a_t\) takes a measurable value within of a compact space \(\mathcal{A}\), called the set of admissible controls.
• Then, given the states \(x_t\) and the controls decided upon \(a_t\), this generates:
  • The running cost \(\mathcal{L}(x_t, a_t)\).
  • The incremental change to the state vector \(\dot{x}_t=f(x_t, a_t)\), and therefore the state vector \(x_{t+\varepsilon}\) for the next period \(t+\varepsilon\).
• Alternatively upon completion, this yields the terminal cost \(G(x_T)\).

Although this sequence of events occur forward in time, each step depends strictly on the previous step. So from the agent’s perspective, it is best to consider the whole sequence and optimize this sequence of events (costs, states, controls) backward. This is encapsulated in the principle of dynamic programming.

The value function

Define \(u(x_t,t)\) as the value function, aka, the optimal (best-achievable) cost starting from a particular time \(t\) and a particular state \(x_t\) [+].

It is notable that \(u(.)\), as the loose minimum (infinimum), no longer depends on the controls. Moreover, it is defined from a particular time \(t\). Hence, from any particular starting time \(t\) and starting state \(x\), we can compute the optimal cost (bound).

[+] A small abuse of notation: \(x_t\) is the state at time \(t\) but is not defined by \(t\). That is, we could write \(u(x,t)\) as in the original reference [4] and it would mean the same thing: (states X time).

Dynamic programming

Consider a value function \(u(x_t,t)\) at \((x,t)\). The principle of dynamic programming says, for any incremental time \(\tau: t < \tau \leq T\), the value function only needs to be computed incrementally from \(t \to \tau\), and thereafter will simply be \(u(x_\tau,\tau)\).

Intuitively, suppose we are at \((x,t)\). If we know the optimal running cost \(\int_t^\tau L(x_s, a_s) ds\) of moving from \((x,t) \to (x_\tau, \tau)\), and the subsequent optimal cost (value function) thereafter \(u(x_\tau, \tau)\), the sum of these give us our optimal cost \(u(x_t,t)\) that can be achieved at \((x,t)\). Hence, the value function can be efficiently computed backward-in-time: given \(u(x_\tau, \tau)\), we proceed backward to \((x_\tau, \tau)\) to compute the running cost from \((x,t) \to (x_\tau, \tau)\), and this yields \(u(x, t)\). (In addition to this, we will still have the terminal condition \(u(x, T)=G(.)\).)

So, if we choose the optimal path at any \((x,t)\), we will stay on the optimal path.

The HJB equation

So far we have formulated the optimal control problem in terms of (costs, states, controls), and we have introduced the idea of a optimal cost path (value function) that can be computed recursively backward-in-time. The next step will be to examine the dynamics of the value function. Then, we can optimize the controls and compute the resulting states trajectory, giving us the optimal (costs, states, controls) and therefore solving the control problem.

Assume the value function \(u(x_t,t)\) is continuous and differentiable in both \(x,t\), and now also, that an optimal control \(a^*_t\) exists for all \(t\) and is continuous in time. As above, let’s explicitly write \(\tau := t + h\) for some \(h > 0\). The value function is hence:

By continuity of \(u(x_t,t)\), we can expand \(u(x_{t+h},t+h)\) via its Taylor series w/the chain rule for \(x_{t+h}\), noting \(h \equiv \Delta t\):

Applying this expansion, the value function is:

Since we have assumed \(a_t\) is continuous in time, let \(h \to 0\). Note first the running cost term converges as follows (Limit of average integral - StackExchange):

noting for the StackExchange answer this follows the same format \(\lim_{b \to a} \frac{1}{b-a} \int_a^b q(x) dx\), with \(b=t+h\) and \(a=t\).

The \(o(h)/h\) term goes to zero, hence plugging this and rearranging we obtain the famous Hamilton-Jacobi-Bellman equation which gives the dynamics of the value function.

Intuitively, the Hamiltonian can be interpreted as the instantaneous version of the Lagrangian from static optimization (Wiki), combining your running cost from being in a state with the sensitivity to the changes in your state. This can be thought of as a tradeoff between your current cost vs. your (near-)future cost, which by the equation must match the change in the optimal cost (value function) at equilibrium.

The optimal controls (\(a^*_t\)) and optimal trajectory of states (\(x^*_t\)) are given indirectly as the solution to the following set of partial differential equations:

Simple analytical results are often not feasible, and moreover, this has assumed smoothness for the value function and controls.

Hamilton-Jacobi-Bellman, stochastic

Now, we reformulate the problem in a textbook way with stochastic drift and diffusion.

The agent’s control problem

Now the agent faces the following stochastic optimal control problem, defined over some time period \([t, T]\), and where \(s \in [t,T]\).

Immediately, we see the cost functional is now stochastic (and expressed in expectation). We also observe that the agent now controls the state dynamics via a non-stochastic “drift” \(f(.)ds\), and a stochastic “diffusion” \(\sigma(.)dB_s\).

As a stochastic process. In the deterministic case, if we chose the optimal control we would know (mechanically) how everything would unfold thereafter. However, in this case there is randomness following each time step, and so in considering a control \(a_s\) at time \(s\) we do not know exactly how the future will unfold. Therefore, it is important that our control process only use information available at the time (“point-in-time”). More formally, define the filtration of the control process as the (montonically expanding) set of information we acquire over time: \(\{\mathcal{F_s}\}_{s \geq t} = \{ \mathcal{F}_t \subseteq \mathcal{F}_{t+1} \subseteq \dots \}\). Hence, we say that our control process \(a_s\) is adapted to this filtration in that it only uses \(\mathcal{F}_s\), the set of information known up to time \(s\) (no peeking into the future!).

A note on randomness. Now, the randomness comes from \(B_s\), a Brownian on the probability space \(\left(\Omega, \mathcal{F}, \{\mathcal{F}_s\}_{s \geq t}, P\right)\). At each time step \(s\) it takes on the realization of a random outcome \(\omega \in \Omega\) (“possible outcomes,” specifically a sigma-algebra), according to the probability measure \(P\) and respecting the current filtration \(\mathcal{F}_s\). This (realized) random draw \(\omega \in \Omega\) impacts the states and controls thereafter, hence we write \(x_s(\omega)\) and \(a_x(\omega)\) to indicate they depend on this randomness.

Sequence of events at each time. Therefore, the sequence of events of time \(s\) proceeds as follows:

• The agent begins with a vector of states \(x_s(\omega) \in \mathcal{R}^d\) as well as that realized Brownian draw \(\omega \in \Omega\).
• On observing those the agent decides which actions to take, aka the vector of controls \(a_s(\omega) \in \mathcal{R}^m\).
  • This only uses the set of information known up to \(s\), aka \(\{\mathcal{F_s}\}_{s \geq t}\).
• Then, given the states \(x_t\) and the controls decided upon \(a_t\), this generates:
  • The running cost \(\mathcal{L}(x_s, a_t, s)\).
  • A new realization \(\omega \in \Omega\) of the Brownian \(B_s\).
  • Subsequently, the incremental change to the state vector \(\dot{x}_s=f(.) ds + \sigma(.)dB_s\).
  • This yields the state vector \(x_{s+\varepsilon}\) for the next period \(s+\varepsilon\), as well as \(\omega\).
• Or upon completion, this yields the terminal cost \(G(x_T)\).

The value function

As in the deterministic case, we can define the value function, noting that we must express it in expectation:

Dynamic programming

Following this logic, the dynamic programming relation is given by:

for \(t < \tau\) of c

The HJB equation

Here we proceed in a similar way as in the deterministic case, except that instead of the chain rule, we need to use Ito’s Lemma, and specifically for our state dynamics which is a multivariate drift-diffusion process. Adapted for our notation from Wikipedia:

Itô's lemma for a multivariate drift-diffusion process

For any time \(s \in [t, \tau]\), let \(X_s=(X_s^1, \dots, X_s^n)^T\) be a real-valued vector of Itô processes, following:

for a vector \(\mu_s\), matrix \(G_s\) and Brownian \(B_s\). Moreover, let \(f(s, X_s)\) be a twice differentiable function in both arguments. Then the lemma states:

where \(\nabla_x f\) is the gradient of \(f\) wrt. X, \(H_x f\) is the Hessian of \(f\) wrt. \(X\), and \(\text{Tr}\) is the trace operator. In essence, this lemma says: given the dynamics of random vector \(X_s\) that changes over time (\(s\)), we can find the dynamics of a transformation \(f(X_s, s)\). Note here in the case of drift-diffusion, the dynamics of the transformation also take on a drift-diffusion form. \(\square\)

Applying this to find a stochastic HJB equation. As before, our strategy is to obtain the dynamics of the value function \(u(.)\), which is a function of states \(X_s\) and time \(s\). These resulting dynamics (the stochastic HJB equation) will indirectly define the optimal controls and trajectory of states. Note we require \(u(.)\) to be twice differentiable in its arguments.

Let’s recall our state dynamics and dynamic programming relation, and label each component so it corresponds to the above format of Itô’s lemma. (Recall \(x_s, a_s, G_s, \dots\) are all vector and matrix quantities).

As before, our strategy is to obtain the dynamics of the value function \(u(.)\), which indirectly defines the optimal controls and trajectory of states. Consistent for the lemma, we require the \(u(.)\) to be twice differentiable in its arguments. With \(\tau\) analogous to \(t+h\) above, write out the expansion of \(u(x_\tau, \tau)\) via the lemma:

where \(H_x u(x_s, s)\) is the Hessian of \(u\) wrt. \(x\). Note also that the increment \(t \to \tau\) functions as the “differential change in time” here: we could mirror the chain rule formulation directly and write \(u(x_\tau, \tau) = u(x, t) + \dots\)

Now plug this into the dynamic programming formulation above:

Note the subtraction goes into the expectation because \(u(x_t, t)\) is an infimum. Now, let \(\tau := t+h\), divide by \(h\) and let \(h \to 0\):

This yields our desired HJB equation:

The interpretation is that at optimum, the instantaneous change in today’s cost can be decomposed into the incremental (running) cost to tomorrow plus tomorrow’s cost. As before, the Hamiltonian \(\mathcal{H}\) captures the tradeoff between “current” and “future” costs, which must be determined by the controls.

Lastly, to tie this back to the optimal controls and trajectory of states, we summarize our system dynamics as before to define the optimal controls and states indirectly:

where optimal controls and trajectory of states \((x_t^{*}, a_t^{*})\) satisfy the above system to yield the optimal cost \(u_t\). \(\square\).

Note that the HJB equation is a second-order differential equation via the Hamiltonian \(\mathcal{H}\), and so can be infeasible if not impossible to solve analytically. This motivates the idea of the Legendre transform to find a feasible solution via an extremal-preserving conjugate transformation, which we may cover in a future post.

References

[1] Ryzhik (2018)

[2] QING, YUTONG. “INTRODUCTION TO THE OPTIMAL CONTROL THEORY AND SOME APPLICATIONS.” (2019).