Bellman equation

Let the state at time ${\displaystyle t}$ be ${\displaystyle x_{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 can write this as ${\displaystyle a_{t}\in \Gamma (x_{t})}$, where the action ${\displaystyle a_{t}}$ represents one or more control variables. We also assume 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})\;=\;\max _{\left\{a_{t}\right\}_{t=0}^{\infty }}\sum _{t=0}^{\infty }\beta ^{t}F(x_{t},a_{t}),}$

subject to the constraints

${\displaystyle a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\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.

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.)[6][7][8]

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 \max _{a_{0}}\left\{F(x_{0},a_{0})+\beta \left[\max _{\left\{a_{t}\right\}_{t=1}^{\infty }}\sum _{t=1}^{\infty }\beta ^{t-1}F(x_{t},a_{t}):a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t\geq 1\right]\right\}}$

subject to the constraints

${\displaystyle a_{0}\in \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.

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, we can rewrite the problem as a recursive definition of the value function:

${\displaystyle V(x_{0})=\max _{a_{0}}\{F(x_{0},a_{0})+\beta V(x_{1})\}}$, subject to the constraints: ${\displaystyle a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).}$

This is the Bellman equation. It can be simplified even further if we drop time subscripts and plug in the value of the next state:

${\displaystyle V(x)=\max _{a\in \Gamma (x)}\{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 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 x. By calculating the value function, we will also find the function a(x) that describes the optimal action as a function of the state; this is called the policy function.

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 {\color {Red}a_{0}}}$ at period ${\displaystyle 0}$. He has 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 \{{\color {OliveGreen}c_{t}}\}}$ that solves

${\displaystyle \max \sum _{t=0}^{\infty }\beta ^{t}u({\color {OliveGreen}c_{t}})}$

subject to

${\displaystyle {\color {Red}a_{t+1}}=(1+r)({\color {Red}a_{t}}-{\color {OliveGreen}c_{t}}),\;{\color {OliveGreen}c_{t}}\geq 0,}$

and

${\displaystyle \lim _{t\rightarrow \infty }{\color {Red}a_{t}}\geq 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 his life. The Bellman equation is

${\displaystyle V(a)=\max _{0\leq c\leq a}\{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 his current period consumption after the current period interest rate is announced.

Rather than simply choosing a single sequence ${\displaystyle \{{\color {OliveGreen}c_{t}}\}}$, the consumer now must choose a sequence ${\displaystyle \{{\color {OliveGreen}c_{t}}\}}$ for each possible realization of a ${\displaystyle \{r_{t}\}}$ in such a way that his lifetime expected utility is maximized:

${\displaystyle \max _{\left\{c_{t}\right\}_{t=0}^{\infty }}\mathbb {E} {\bigg (}\sum _{t=0}^{\infty }\beta ^{t}u({\color {OliveGreen}c_{t}}){\bigg )}.}$

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)=\max _{0\leq c\leq a}\{u(c)+\beta \int V((1+r)(a-c),r')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 his decision ex-post, the Bellman equation takes a very similar form

${\displaystyle V(x,z)=\max _{c\in \Gamma (x,z)}\{F(x,c,z)+\beta \int V(T(x,c),z')d\mu _{z}(z')\}.}$