Bellman Equation

A Bellman equation, named after Richard E. Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. It writes the "value" of a decision problem at a certain point in time in terms of the payoff from some initial choices and the "value" of the remaining decision problem thatresults from those initial choices. This breaks a dynamic optimization problem into a sequence of simpler subproblems, as Bellman's “principle of optimality" prescribes. The equation applies to algebraic structures with a total ordering; for algebraic structures with a partial ordering, the generic Bellman's equation can be used.

Richard E. Bellman의 이름을 딴 Bellman equation은 동적 프로그래밍(수학적 최적화 방법이다)과 관련된 최적성을 위한 필요조건이다. Bellman equation은 몇몇 초기 선택으로 인한 보상 측면에서 특정 시점에서의 decision problem의 가치(value)와 그러한 초기 선택의 결과로 발생하는 나머지 decision problem의 가치(value)를 기술한다. Bellman equation은 Bellman의 최적성의 원리(principle of optimality)가 규정하는 것처럼 동적 최적화 문제를 일련의 단순한 하위문제(subproblems)로 분해한다. 이 방정식은 전체 순서를 갖는 대수 구조에 적용할 수 있고, 부분 순서를 갖는 대수 구조의 경우 일반적인 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; though the basic concepts of dynamic programming are prefigured in John von Neumann and Oskar Morgenstern's Theory of Games and Economic Behavior and Abraham Wald's sequential analysis. The term 'Bellman equation' usually refers to the dynamic programming equation associated with discrete-time optimization problems. In continuous-time optimization problems, the analogous equation is a partial differential equation that is called the Hamilton–Jacobi–Bellman equation.

 

Bellman equation은 처음에는 공학 제어 이론과 응용 수학의 다른 주제에 적용되었고, 이후 경제 이론에서 중요한 도구가 되었다: 비록 동적 프로그래밍의 기본 개념은 John von Neumann와 Oskar Morgenstern의 '게임과 경제적 행동의 이론'와 Abraham Wald의 순차 분석에서 미리 구성되었다. 'Bellman equation'이라는 용어는 일반적으로 이산 시간 최적화 문제(discrete-time optimization problem)와 관련된 동적 프로그래밍 방정식을 가리킨다. 연속 시간 최적화 문제(continuous-time optimization problems)에서는 편미분 방정식인 Hamilton–Jacobi–Bellman equation이 이와 유사하다.

In discrete time any multi-stage optimization problem can be solved by analyzing the appropriate Bellman equation. The appropriate Bellman equation can be found by introducing new state variables (state augmentation). However, the resulting augmented-state multi-stage optimization problem has a higher dimensional state space than the original multi-stage optimization problem - an issue that can potentially render the augmented problem intractable due to the “curse of dimensionality”. Alternatively, it has been shown that if the cost function of the multi-stage optimization problem satisfies a "backward separable" structure, then the appropriate Bellman equation can be found without state augmentation.

이산 시간의 모든 다단계(multi-stage) 최적화 문제는 적절한 Bellman equation을 분석하여 해결할 수 있다. 적절한 Bellman equation은 새로운 상태(state) 변수를 도입(state augmentation)함으로써 찾을 수 있다. 그러나 결과적으로 증강상태(augmented-state) 다단계(multi-stage) 최적화 문제는 원래 다단계 최적화 문제보다 더 높은 차원의 상태 공간을 가지고 있다. 이 문제는 차원성의 저주(curse of dimensionality)로 인해 증강 문제를 잠재적으로 다루기 어렵게 만들 수 있다. 또는 다단계 최적화 문제의 비용 함수가 backward separable한 구조를 만족하는 경우에는, 상태 증강 없이 적절한 Bellman equation을 찾을 수 있다.