Bellman equation

Derivation

A dynamic decision problem

Let ${\displaystyle x_t}$ be the state at time ${\displaystyle t}$. For a decision that begins at time 0, we take as given the initial state ${\displaystyle x_0}$. At any time, the set of possible actions depends on the current state; we express this as ${\displaystyle a_t\in \mathrm{\Gamma }(x_t)}$, where a particular action ${\displaystyle a_t}$ represents particular values for one or more control variables, and ${\displaystyle \mathrm{\Gamma }(x_t)}$ is the set of actions available to be taken at state ${\displaystyle x_t}$. It is also assumed that the state changes from ${\displaystyle x}$ to a new state ${\displaystyle T(x,a)}$ when action ${\displaystyle a}$ is taken, and that the current payoff from taking action ${\displaystyle a}$ in state ${\displaystyle x}$ is ${\displaystyle F(x,a)}$. Finally, we assume impatience, represented by a discount factor ${\displaystyle 0<\beta <1}$.

Under these assumptions, an infinite-horizon decision problem takes the following form:

${\displaystyle V(x_0)=\underset{{\left\{a_t\right\}}_{t=0}^{\mathrm{\infty }}}{max}\sum _{t=0}^{\mathrm{\infty }}{\beta }^{t}F(x_t,a_t),}$

subject to the constraints

${\displaystyle a_t\in \mathrm{\Gamma }(x_t),x_{t+1}=T(x_t,a_t),\mathrm{\forall }t=0,1,2,\dots }$

Notice that we have defined notation ${\displaystyle V(x_0)}$ to denote the optimal value that can be obtained by maximizing this objective function subject to the assumed constraints. This function is the value function. It is a function of the initial state variable ${\displaystyle x_0}$, since the best value obtainable depends on the initial situation.

Bellman's principle of optimality

The dynamic programming method breaks this decision problem into smaller subproblems. Bellman's principle of optimality describes how to do this:

Principle of Optimality: 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. (See Bellman, 1957, Chap. III.3.)

In computer science, a problem that can be broken apart like this is said to have optimal substructure. In the context of dynamic game theory, this principle is analogous to the concept of subgame perfect equilibrium, although what constitutes an optimal policy in this case is conditioned on the decision-maker's opponents choosing similarly optimal policies from their points of view.

As suggested by the principle of optimality, we will consider the first decision separately, setting aside all future decisions (we will start afresh from time 1 with the new state ${\displaystyle x_1}$). Collecting the future decisions in brackets on the right, the above infinite-horizon decision problem is equivalent to:

${\displaystyle \underset{a_0}{max}\left\{F(x_0,a_0)+\beta \left[\underset{{\left\{a_t\right\}}_{t=1}^{\mathrm{\infty }}}{max}\sum _{t=1}^{\mathrm{\infty }}{\beta }^{t-1}F(x_t,a_t):a_t\in \mathrm{\Gamma }(x_t),x_{t+1}=T(x_t,a_t),\mathrm{\forall }t\ge 1\right]\right\}}$

subject to the constraints

${\displaystyle a_0\in \mathrm{\Gamma }(x_0),x_1=T(x_0,a_0).}$

Here we are choosing ${\displaystyle a_0}$, knowing that our choice will cause the time 1 state to be ${\displaystyle x_1=T(x_0,a_0)}$. That new state will then affect the decision problem from time 1 on. The whole future decision problem appears inside the square brackets on the right.

The Bellman equation

So far it seems we have only made the problem uglier by separating today's decision from future decisions. But we can simplify by noticing that what is inside the square brackets on the right is the value of the time 1 decision problem, starting from state ${\displaystyle x_1=T(x_0,a_0)}$.

Therefore, the problem can be rewritten as a recursive definition of the value function:

${\displaystyle V(x_0)=\underset{a_0}{max}\{F(x_0,a_0)+\beta V(x_1)\}}$, subject to the constraints: ${\displaystyle a_0\in \mathrm{\Gamma }(x_0),x_1=T(x_0,a_0).}$

This is the Bellman equation. It may be simplified even further if the time subscripts are dropped and the value of the next state is plugged in:

${\displaystyle V(x)=\underset{a\in \mathrm{\Gamma }(x)}{max}\{F(x,a)+\beta V(T(x,a))\}.}$

The Bellman equation is classified as a functional equation, because solving it means finding the unknown function ${\displaystyle V}$, which is the value function. Recall that the value function describes the best possible value of the objective, as a function of the state ${\displaystyle x}$. By calculating the value function, we will also find the function ${\displaystyle a(x)}$ that describes the optimal action as a function of the state; this is called the policy function.

In a stochastic problem

In the deterministic setting, other techniques besides dynamic programming can be used to tackle the above optimal control problem. However, the Bellman Equation is often the most convenient method of solving stochastic optimal control problems.

For a specific example from economics, consider an infinitely-lived consumer with initial wealth endowment ${\displaystyle a_0}$ at period ${\displaystyle 0}$. They have an instantaneous utility function ${\displaystyle u(c)}$ where ${\displaystyle c}$ denotes consumption and discounts the next period utility at a rate of ${\displaystyle 0<\beta <1}$. Assume that what is not consumed in period ${\displaystyle t}$ carries over to the next period with interest rate ${\displaystyle r}$. Then the consumer's utility maximization problem is to choose a consumption plan ${\displaystyle \{c_t\}}$ that solves

${\displaystyle max\sum _{t=0}^{\mathrm{\infty }}{\beta }^{t}u(c_t)}$

subject to

${\displaystyle a_{t+1}=(1+r)(a_t-c_t),c_t\ge 0,}$

and

${\displaystyle \underset{t\to \mathrm{\infty }}{lim}{a}_t\ge 0.}$

The first constraint is the capital accumulation/law of motion specified by the problem, while the second constraint is a transversality condition that the consumer does not carry debt at the end of their life. The Bellman equation is

${\displaystyle V(a)=\underset{0\le c\le a}{max}\{u(c)+\beta V((1+r)(a-c))\},}$

Alternatively, one can treat the sequence problem directly using, for example, the Hamiltonian equations.

Now, if the interest rate varies from period to period, the consumer is faced with a stochastic optimization problem. Let the interest r follow a Markov process with probability transition function ${\displaystyle Q(r,d{\mu }_r)}$ where ${\displaystyle d{\mu }_r}$ denotes the probability measure governing the distribution of interest rate next period if current interest rate is ${\displaystyle r}$. In this model the consumer decides their current period consumption after the current period interest rate is announced.

Rather than simply choosing a single sequence ${\displaystyle \{c_t\}}$, the consumer now must choose a sequence ${\displaystyle \{c_t\}}$ for each possible realization of a ${\displaystyle \{r_t\}}$ in such a way that their lifetime expected utility is maximized:

${\displaystyle \underset{{\left\{c_t\right\}}_{t=0}^{\mathrm{\infty }}}{max}\mathbb{E}(\sum _{t=0}^{\mathrm{\infty }}{\beta }^{t}u(c_t)).}$

The expectation ${\displaystyle \mathbb{E}}$ is taken with respect to the appropriate probability measure given by Q on the sequences of r's. Because r is governed by a Markov process, dynamic programming simplifies the problem significantly. Then the Bellman equation is simply:

${\displaystyle V(a,r)=\underset{0\le c\le a}{max}\{u(c)+\beta \int V((1+r)(a-c),r^{\prime })Q(r,d{\mu }_r)\}.}$

Under some reasonable assumption, the resulting optimal policy function g(a,r) is measurable.

For a general stochastic sequential optimization problem with Markovian shocks and where the agent is faced with their decision ex-post, the Bellman equation takes a very similar form

${\displaystyle V(x,z)=\underset{c\in \mathrm{\Gamma }(x,z)}{max}\{F(x,c,z)+\beta \int V(T(x,c),z^{\prime })d{\mu }_z(z^{\prime })\}.}$

Solution methods

• The method of undetermined coefficients, also known as 'guess and verify', can be used to solve some infinite-horizon, autonomous Bellman equations.
• The Bellman equation can be solved by backwards induction, either analytically in a few special cases, or numerically on a computer. Numerical backwards induction is applicable to a wide variety of problems, but may be infeasible when there are many state variables, due to the curse of dimensionality. Approximate dynamic programming has been introduced by D. P. Bertsekas and J. N. Tsitsiklis with the use of artificial neural networks (multilayer perceptrons) for approximating the Bellman function. This is an effective mitigation strategy for reducing the impact of dimensionality by replacing the memorization of the complete function mapping for the whole space domain with the memorization of the sole neural network parameters. In particular, for continuous-time systems, an approximate dynamic programming approach that combines both policy iterations with neural networks was introduced. In discrete-time, an approach to solve the HJB equation combining value iterations and neural networks was introduced.
• By calculating the first-order conditions associated with the Bellman equation, and then using the envelope theorem to eliminate the derivatives of the value function, it is possible to obtain a system of difference equations or differential equations called the 'Euler equations'. Standard techniques for the solution of difference or differential equations can then be used to calculate the dynamics of the state variables and the control variables of the optimization problem.

Applications in economics

The first known application of a Bellman equation in economics is due to Martin Beckmann and Richard Muth. Martin Beckmann also wrote extensively on consumption theory using the Bellman equation in 1959. His work influenced Edmund S. Phelps, among others.

A celebrated economic application of a Bellman equation is Robert C. Merton's seminal 1973 article on the intertemporal capital asset pricing model. (See also Merton's portfolio problem). The solution to Merton's theoretical model, one in which investors chose between income today and future income or capital gains, is a form of Bellman's equation. Because economic applications of dynamic programming usually result in a Bellman equation that is a difference equation, economists refer to dynamic programming as a "recursive method" and a subfield of recursive economics is now recognized within economics.

Nancy Stokey, Robert E. Lucas, and Edward Prescott describe stochastic and nonstochastic dynamic programming in considerable detail, and develop theorems for the existence of solutions to problems meeting certain conditions. They also describe many examples of modeling theoretical problems in economics using recursive methods. This book led to dynamic programming being employed to solve a wide range of theoretical problems in economics, including optimal economic growth, resource extraction, principal–agent problems, public finance, business investment, asset pricing, factor supply, and industrial organization. Lars Ljungqvist and Thomas Sargent apply dynamic programming to study a variety of theoretical questions in monetary policy, fiscal policy, taxation, economic growth, search theory, and labor economics. Avinash Dixit and Robert Pindyck showed the value of the method for thinking about capital budgeting. Anderson adapted the technique to business valuation, including privately held businesses.

Using dynamic programming to solve concrete problems is complicated by informational difficulties, such as choosing the unobservable discount rate. There are also computational issues, the main one being the curse of dimensionality arising from the vast number of possible actions and potential state variables that must be considered before an optimal strategy can be selected. For an extensive discussion of computational issues, see Miranda and Fackler, and Meyn 2007.

Example

In Markov decision processes, a Bellman equation is a recursion for expected rewards. For example, the expected reward for being in a particular state s and following some fixed policy ${\displaystyle \pi }$ has the Bellman equation:

${\displaystyle V^{\pi }(s)=R(s,\pi (s))+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,\pi (s))V^{\pi }(s^{\prime }).}$

This equation describes the expected reward for taking the action prescribed by some policy ${\displaystyle \pi }$.

The equation for the optimal policy is referred to as the Bellman optimality equation:

${\displaystyle V^{\pi \ast }(s)=\underset{a}{max}\left\{R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)V^{\pi \ast }(s^{\prime })\right\}.}$

where ${\displaystyle \pi \ast }$ is the optimal policy and ${\displaystyle V^{\pi \ast }}$ refers to the value function of the optimal policy. The equation above describes the reward for taking the action giving the highest expected return.