Information about Bellman Equation

A Bellman equation (also known as a dynamic programming equation), named after its discoverer, Richard Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. Almost any problem which can be solved using optimal control theory can also be solved by analyzing the appropriate Bellman equation. The Bellman equation was first applied to engineering control theory and to other topics in applied mathematics, and subsequently became an important tool in economic theory.

Principle of optimality

Given an appropriate initial condition

the canonical infinite horizon dynamic programming problem is:

subject to the constraints

In this problem, x is a vector of state and control variables, indexed by discrete time t. 0≤β≤1 is the discount factor.

The recursive restatement of this problem as a Bellman equation is:

.

The function that solves the Bellman equation is called the value function. The value function describes the optimized value of the problem, as a function of the state variable x. The function y(x) that describes the optimal choice as a function of the state is called the policy function.

Stokey & Lucas (1989: 67-77) called the equivalence between these two forms of the problem the principle of optimality (a term taken from Bellman's 1952 paper^[1]). The principle asserts that if the policy function is optimal for the infinite summation, then it must be the case that whatever the initial state and decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from that first decision (as expressed by the Bellman equation). The principle of optimality is related to the concept of optimal substructure, and problems that exhibit optimal substructure can often be solved with dynamic programming.

Example

In reinforcement learning, a Bellman equation refers to a recursion for expected rewards. For example, the expected reward for being in a particular state s and following some fixed policy has the Bellman equation:

This equation describes the expected reward for taking the action prescribed by some policy .

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

It describes the reward for taking the action giving the highest expected return.

Solutions

• 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.
• 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 economic application of a Bellman equation is Merton's seminal 1973 article on the intertemporal capital asset pricing model.^[2] 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."

Lucas & Stokey describes stochastic and nonstochastic dynamic programming in considerable detail, giving many examples of how to employ dynamic programming to solve problems in economic theory.^[3] 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. Ljungqvist & Sargent apply dynamic programming to study a variety of theoretical questions in monetary policy, fiscal policy, taxation, economic growth, search theory, and labor economics.^[4] Dixit & Pindyck showed the value of the method for thinking about capital budgeting.^[5] Patrick L. Anderson used dynamic programming to develop methods to value closely held firms.^[6]

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 & Fackler.^[7]

See also

• Hamilton-Jacobi-Bellman equation
• Dynamic programming
• Markov decision process
• Optimal control theory

References