ベルマンの最適性の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/03 14:35 UTC 版)
「ベルマン方程式」の記事における「ベルマンの最適性の原理」の解説
動的計画法は、この決定問題をより小さな部分問題に分割する。リチャード・ベルマンの最適性の原理がその方法を示している： 最適性の原理（Principle of Optimality） ： 最適な方策は、初期状態と初期決定がどんなものであれ、その結果得られる次の状態に関して、以降の決定が必ず最適方策になっているという性質をもつ。 (参照： Bellman, 1957、Chap. III.3.) コンピュータ・サイエンスでは、このように分割できる問題の事を「部分構造最適性（英語版）（optimal substructure）を持つ」と表現する。 この原理は、動的ゲーム理論における部分ゲーム完全均衡（subgame perfect equilibrium）と相似な概念である。ただし、動的ゲーム理論における最適方策は、相手プレイヤーが同様に最適方策を選択するという前提に立つ。 最適性の原理から示唆されるように、我々は将来の選択（時刻1から新しい状態 x 1 {\displaystyle x_{1}} でスタートする）について一旦保留して、最初の決定だけを独立に検討する。将来の決定に関する項を大括弧の中に集めることにより、先の問題は次のように表現される。 max a 0 { F ( x 0 , a 0 ) + β [ max { a t } t = 1 ∞ ∑ t = 1 ∞ β t − 1 F ( x t , a t ) : a t ∈ Γ ( x t ) , x t + 1 = T ( x t , a t ) , ∀ t ≥ 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\}} ただし次の条件のもとで： a 0 ∈ Γ ( x 0 ) , x 1 = T ( x 0 , a 0 ) . {\displaystyle a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).} ここで時刻1での状態が x 1 = T ( x 0 , a 0 ) {\displaystyle x_{1}=T(x_{0},a_{0})} となることを知りつつ、アクション a 0 {\displaystyle a_{0}} を選ぶ。この新しい状態は、時刻1以降すべての決定に影響を与える。 未来全体の決定問題は、右側の角括弧の中に現れている。
※この「ベルマンの最適性の原理」の解説は、「ベルマン方程式」の解説の一部です。
「ベルマンの最適性の原理」を含む「ベルマン方程式」の記事については、「ベルマン方程式」の概要を参照ください。
- ベルマンの最適性の原理のページへのリンク
