ベルマン方程式

ベルマン方程式は、リチャード・E・ベルマンにちなんで名付けられ、動的計画法として知られる数学的最適化手法に関連する最適性の必要条件です。^[1]これは、ある時点における決定問題の「価値」を、いくつかの初期選択からの利益と、それらの初期選択の結果としての残りの決定問題の「価値」で表します。^[2]これは、ベルマンの「最適性の原理」が規定するように、動的最適化問題を一連のより単純なサブ問題に分割します。 ^[3] この方程式は、全順序付けの代数構造に適用されます。部分順序付けの代数構造には、一般的なベルマン方程式を使用できます。^[4]

ベルマン方程式は、最初は工学制御理論や応用数学の他のトピックに適用され、その後経済理論の重要なツールになりました。動的計画法の基本概念は、ジョン・フォン・ノイマンとオスカー・モルゲンシュテルンの「ゲームと経済行動の理論」およびアブラハム・ワルドの逐次分析で事前に示されています。^{[要出典] 「ベルマン方程式」という用語は通常、}離散時間最適化問題に関連する動的計画法方程式 (DPE) を指します。^[5]連続時間最適化問題では、類似の方程式はハミルトン-ヤコビ-ベルマン方程式と呼ばれる偏微分方程式です。^{[6] [7]}

離散時間では、適切なベルマン方程式を解析することで、あらゆる多段階最適化問題を解くことができます。適切なベルマン方程式は、新しい状態変数 (状態拡張) を導入することで見つけることができます。^[8]しかし、結果として得られる拡張状態の多段階最適化問題は、元の多段階最適化問題よりも高次元の状態空間を持ちます。これは、「次元の呪い」により、拡張された問題を扱いにくくする可能性がある問題です。あるいは、多段階最適化問題のコスト関数が「後方分離可能」な構造を満たす場合、状態拡張なしで適切なベルマン方程式を見つけることができることが示されています。^[9]

ベルマン方程式を理解するには、いくつかの基本的な概念を理解する必要があります。まず、あらゆる最適化問題には、移動時間の最小化、コストの最小化、利益の最大化、効用の最大化など、何らかの目的があります。この目的を表す数学関数は目的関数と呼ばれます。^[要出典]

動的計画法は、複数期間の計画問題を、異なる時点におけるより単純なステップに分割します。したがって、意思決定状況が時間の経過とともにどのように変化しているかを追跡する必要があります。正しい決定を下すために必要な現在の状況に関する情報は、「状態」と呼ばれます。^{[10] [11]}たとえば、各時点でどれだけ消費し、どれだけ使うかを決定するには、人々は（他の情報の中でも）初期の富を知る必要があります。したがって、富は状態変数の 1 つになりますが、おそらく他にもあるでしょう。 ${\displaystyle (W)}$

任意の時点で選択される変数は、しばしば制御変数と呼ばれます。たとえば、現在の富が与えられれば、人々は今どれだけ消費するかを決めるかもしれません。今制御変数を選択することは、次の状態を選択することと同等かもしれません。より一般的には、次の状態は現在の制御に加えて他の要因によって影響されます。たとえば、最も単純なケースでは、今日の富 (状態) と消費 (制御) が明日の富 (新しい状態) を正確に決定する可能性がありますが、通常は他の要因も明日の富に影響します。^{[引用が必要]}

動的計画法は、状態がどのような値であっても、どのような制御を行うべきかを示す規則を見つけることで、最適な計画を記述する。例えば、消費（c）が富（W ）のみに依存する場合、消費を富の関数として与える規則を求める 。このような、制御を状態の関数として決定する規則は、政策関数と呼ばれる。^{[12] [10]}${\displaystyle c(W)}$

最後に、定義により、最適な決定ルールとは、目的の可能な限り最高の価値を達成するルールです。たとえば、富を与えられた人が幸福を最大化するために消費を選択した場合（幸福H は効用関数などの数学関数で表すことができ、富によって定義されるものと仮定）、富の各レベルは、可能な限り最高の幸福レベルに関連付けられます。目的の可能な限り最高の価値は、状態の関数として表され、価値関数と呼ばれます。^{[引用が必要]}${\displaystyle H(W)}$

ベルマンは、離散時間における動的最適化問題は、ある期間の価値関数と次の期間の価値関数の関係を書き出すことによって、逆方向帰納法と呼ばれる再帰的なステップバイステップの形式で記述できることを示しました。この 2 つの価値関数の関係は、「ベルマン方程式」と呼ばれます。このアプローチでは、最後の期間の最適なポリシーは、その時点の状態変数の値の関数として事前に指定され、その結果得られる目的関数の最適値は、状態変数の値によって表現されます。次に、最後から 2 番目の期間の最適化では、その期間の期間固有の目的関数と将来の目的関数の最適値の合計を最大化し、最後から 2 番目の期間の決定時点での状態変数の値に応じてその期間の最適なポリシーを決定します。^{[説明が必要]}このロジックは、最初の期間の決定ルールが、最初の期間固有の目的関数と、将来のすべての期間の値を与える 2 番目の期間の価値関数の値の合計を最適化することによって、初期状態変数値の関数として導出されるまで、時間を遡って再帰的に継続されます。したがって、各期間の決定は、将来のすべての決定が最適に行われることを明示的に認識することによって行われます。^{[引用が必要]}

を時刻 の状態とします。時刻 0 に始まる決定では、初期状態 が与えられたものとみなします。どの時点でも、可能なアクションの集合は現在の状態によって決まります。これを と表現します。ここで、特定のアクションは1 つ以上の制御変数の特定の値を表し、 は状態 で実行できるアクションの集合です。また、アクションが実行されると状態が から新しい状態に変化し、状態でア​​クションを実行することで得られる現在の利得がであると仮定します。最後に、割引率で表される焦りがあると仮定します。 ${\displaystyle x_{t}}$${\displaystyle t}$${\displaystyle x_{0}}$${\displaystyle a_{t}\in \Gamma (x_{t})}$${\displaystyle a_{t}}$${\displaystyle \Gamma (x_{t})}$${\displaystyle x_{t}}$${\displaystyle x}$${\displaystyle T(x,a)}$${\displaystyle a}$${\displaystyle a}$${\displaystyle x}$${\displaystyle F(x,a)}$ ${\displaystyle 0<\beta <1}$

これらの仮定の下では、無限期間の決定問題は次の形式になります。

${\displaystyle V(x_{0})\;=\;\max _{\left\{a_{t}\right\}_{t=0}^{\infty }}\sum _{t=0}^{\infty }\beta ^{t}F(x_{t},a_{t}),}$

制約を受ける

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

想定される制約の下でこの目的関数を最大化することによって得られる最適値を表すために表記法を定義していることに注意してください。この関数は値関数です。得られる最適な値は初期状況によって異なるため、 これは初期状態変数の関数です。${\displaystyle V(x_{0})}$${\displaystyle x_{0}}$

動的計画法では、この決定問題を小さなサブ問題に分割します。ベルマンの最適性原理では、これをどのように行うかを説明します。

最適性の原則：最適な政策とは、初期状態と初期決定が何であれ、残りの決定は最初の決定から生じる状態に関して最適な政策を構成するという性質を持つ。（ベルマン、1957、第III章3節を参照）^{[10] [11] [13]}

コンピュータサイエンスでは、このように分解できる問題は最適なサブ構造を持つと言われています。動的ゲーム理論の文脈では、この原理はサブゲーム完全均衡の概念に類似していますが、この場合の最適なポリシーを構成するものは、意思決定者の対戦相手が彼らの観点から同様に最適なポリシーを選択することを条件としています。

最適性の原則に従って、将来の決定をすべて脇に置いて、最初の決定を別々に検討します（新しい状態 で時間 1 から新たに開始します）。右側の括弧内に将来の決定をまとめると、上記の無限期間の決定問題は次と同等になります。^{[説明が必要]}${\displaystyle x_{1}}$

${\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\}}$

制約を受ける

${\displaystyle a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).}$

ここでは を選択していますが、その選択によって時刻 1 の状態が になることはわかっています。この新しい状態は時刻 1 以降の決定問題に影響します。将来の決定問題全体が右側の角括弧内に表示されます。^{[説明が必要] [さらに説明が必要]}${\displaystyle a_{0}}$${\displaystyle x_{1}=T(x_{0},a_{0})}$

これまでのところ、今日の決定を将来の決定から切り離すことで、問題がさらに複雑になっているように見えます。しかし、右側の角括弧内が状態から始まる時間 1 の決定問題の値であることに注目することで、 問題を単純化できます。${\displaystyle x_{1}=T(x_{0},a_{0})}$

したがって、この問題は価値関数の 再帰定義として書き直すことができます。

${\displaystyle V(x_{0})=\max _{a_{0}}\{F(x_{0},a_{0})+\beta V(x_{1})\}}$ただし、以下の制約が適用されます。${\displaystyle a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).}$

これはベルマン方程式です。時間の添え字を削除し、次の状態の値を代入すると、さらに簡略化できます。

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

ベルマン方程式は関数方程式に分類されます。これは、これを解くことが未知の関数、つまり価値関数を見つけることになるためです。価値関数は、状態の関数として、目的関数の可能な限り最高の値を表すことを思い出してください。価値関数を計算することで、最適なアクションを状態の関数として表す関数も見つかります。これをポリシー関数と呼びます。 ${\displaystyle V}$${\displaystyle x}$${\displaystyle a(x)}$

決定論的設定では、動的計画法以外の手法を使用して上記の最適制御問題に取り組むことができます。ただし、確率的最適制御問題を解決する最も便利な方法は、多くの場合、ベルマン方程式です。

経済学の具体的な例として、期間 に初期資産を保有する、寿命が無限の消費者を考えてみましょう。彼らは瞬間効用関数を持ち、 は消費を表し、次の期間の効用を の率で割り引くことになります。期間 に消費されなかったものは、金利 で次の期間に持ち越されると仮定します。この場合、消費者の効用最大化問題は、次の問題を解決する 消費計画を選択することです。${\displaystyle {\color {Red}a_{0}}}$${\displaystyle 0}$ ${\displaystyle u(c)}$${\displaystyle c}$${\displaystyle 0<\beta <1}$${\displaystyle t}$${\displaystyle r}$${\displaystyle \{{\color {OliveGreen}c_{t}}\}}$

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

対象となる

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

そして

${\displaystyle \lim _{t\rightarrow \infty }{\color {Red}a_{t}}\geq 0.}$

最初の制約は問題によって規定される資本蓄積/運動法則であり、2番目の制約は消費者が人生の終わりに負債を抱えないという 横断条件である。ベルマン方程式は

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

あるいは、例えばハミルトン方程式を使用してシーケンス問題を直接扱うこともできます。

ここで、金利が期間ごとに変化すると、消費者は確率的最適化問題に直面します。金利r が確率遷移関数を持つマルコフ過程に従うものとします。ここで、 は、現在の金利が である場合に次の期間の金利の分布を左右する確率測度を表します。このモデルでは、消費者は現在の期間の金利が発表された後に、現在の期間の消費を決定します。 ${\displaystyle Q(r,d\mu _{r})}$${\displaystyle d\mu _{r}}$${\displaystyle r}$

消費者は、単に単一のシーケンスを選択するのではなく、生涯の期待効用が最大化されるように、 の可能な実現ごとにシーケンスを選択する必要があります。${\displaystyle \{{\color {OliveGreen}c_{t}}\}}$${\displaystyle \{{\color {OliveGreen}c_{t}}\}}$${\displaystyle \{r_{t}\}}$

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

期待値は、 rのシーケンスに対してQによって与えられた適切な確率測度に関して取られます。r はマルコフ過程によって制御されるため、動的計画法によって問題が大幅に簡素化されます。ベルマン方程式は単純に次のようになります。 ${\displaystyle \mathbb {E} }$

${\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})\}.}$

ある合理的な仮定の下では、結果として得られる最適な政策関数g ( a , r )は測定可能である。

マルコフショックを伴う一般的な確率的逐次最適化問題では、エージェントは事後的に意思決定に直面するため、ベルマン方程式は非常に似た形をとる。

${\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')\}.}$

• 未定係数法は「推測と検証」としても知られ、無限時間にわたる自律ベルマン方程式を解くのに使用できます。^[14]
• ベルマン方程式は、いくつかの特殊なケースでは解析的に、またはコンピュータ上で数値的に、後方帰納法によって解くことができます。数値後方帰納法はさまざまな問題に適用できますが、次元の呪いのため、状態変数が多い場合は実行不可能な場合があります。DP BertsekasとJN Tsitsiklisは、ベルマン関数を近似するために人工ニューラル ネットワーク(多層パーセプトロン)を使用する近似動的計画法を導入しました。 ^[15]これは、空間領域全体の完全な関数マッピングの記憶を、ニューラル ネットワーク パラメータのみの記憶に置き換えることで、次元の影響を軽減する効果的な緩和戦略です。特に、連続時間システムでは、ポリシー反復とニューラル ネットワークの両方を組み合わせた近似動的計画法のアプローチが導入されました。 [16]離散時間では、値反復とニューラル ネットワークを組み合わせて HJB 方程式を解くアプローチが導入されました。 [ ^{17 ]}
• ベルマン方程式に関連する一次条件を計算し、包絡線定理を使用して値関数の導関数を除去することによって、「オイラー方程式」と呼ばれる差分方程式または微分方程式のシステムを得ることができます。^[18]差分方程式または微分方程式を解くための標準的な手法を使用して、最適化問題の状態変数と制御変数のダイナミクスを計算できます。

ベルマン方程式が経済学に初めて応用されたのは、マーティン・ベックマンとリチャード・ムスによるものです。^[19]マーティン・ベックマンは1959年にベルマン方程式を用いた消費理論についても広範囲にわたって執筆しました。彼の研究はエドマンド・S・フェルプスなどに影響を与えました。

ベルマン方程式の経済への応用として有名なのは、ロバート・C・マートンが1973年に発表した異時点間の資本資産価格モデルに関する論文である。^[20]（マートンのポートフォリオ問題も参照）。投資家が現在の収入と将来の収入またはキャピタルゲインのいずれかを選択するというマートンの理論モデルの解は、ベルマン方程式の一種である。動的計画法の経済への応用では通常、差分方程式であるベルマン方程式が得られるため、経済学者は動的計画法を「再帰的手法」と呼び、再帰的経済学のサブフィールドが現在では経済学内で認識されている。

ナンシー・ストーキー、ロバート・E・ルーカス、エドワード・プレスコットは、確率的および非確率的動的計画法をかなり詳細に説明し、特定の条件を満たす問題に対する解の存在に関する定理を展開しています。また、経済学における理論的問題をモデル化して再帰的手法を使用する多くの例についても説明しています。^[21]この本により、最適経済成長、資源抽出、プリンシパル・エージェント問題、公共財政、企業投資、資産価格設定、要素供給、産業組織など、経済学における幅広い理論的問題の解決に動的計画法が採用されるようになりました。ラース・リュングクヴィストとトーマス・サージェントは、金融政策、財政政策、課税、経済成長、探索理論、労働経済学におけるさまざまな理論的問題を研究するために動的計画法を適用しています。^[22] アビナッシュ・ディキシットとロバート・ピンディックは、資本予算について考えるための方法の価値を示しました。^[23]アンダーソンは、非上場企業を含む企業評価にこの手法を適用しました。^[24]

動的計画法を使用して具体的な問題を解決することは、観測不可能な割引率の選択など、情報上の困難によって複雑化します。また、計算上の問題もあります。主な問題は、最適な戦略を選択する前に考慮しなければならない膨大な数の可能なアクションと潜在的な状態変数から生じる次元の呪いです。計算上の問題に関する詳細な議論については、Miranda and Fackler、[ ^25]および Meyn 2007を参照してください。 ^[26]

マルコフ決定過程において、ベルマン方程式は期待報酬の再帰です。たとえば、特定の状態sにあり、ある固定されたポリシーに従う場合の期待報酬は、ベルマン方程式で表されます。 ${\displaystyle \pi }$

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

この式は、何らかのポリシーによって規定されたアクションを実行した場合に期待される報酬を表します。 ${\displaystyle \pi }$

最適ポリシーの方程式はベルマン最適性方程式と呼ばれます。

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

ここで、は最適なポリシーであり、 は最適なポリシーの価値関数を指します。上記の式は、最も高い期待収益をもたらすアクションを実行することに対する報酬を表します。 ${\displaystyle {\pi *}}$${\displaystyle V^{\pi *}}$

• ベルマン擬スペクトル法
• 動的計画法 - 問題最適化手法
• ハミルトン・ヤコビ・ベルマン方程式 – 最適制御理論における最適条件
• マルコフ決定過程 – 不確実性の下での連続的な意思決定の数学的モデル
• 最適制御理論 – 動的システムから望ましい出力を得るための数学的方法
• 最適部分構造 – 計算問題の特性
• 再帰的競争均衡 - 動的プログラムに関連する経済均衡概念Pages displaying wikidata descriptions as a fallback
• 確率的動的計画法 - 不確実性の下での意思決定の問題をモデル化するための 1957 年の手法