価値反復法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/05 04:50 UTC 版)
価値反復法 (value iteration)は後ろ向き帰納法 (backward induction) とも呼ばれ、ベルマン方程式を満たす価値関数を繰り返し計算により求める。 ロイド・シャープレー が1953年に発表した確率ゲーム（英語版）に関する論文には価値反復法の特殊な場合が含まれるが、このことが認知されたのは後になってからである． ステップ i {\displaystyle i} における価値関数の計算結果を V i ( s ) {\displaystyle V_{i}(s)} と表記すると、価値反復法における更新式はつぎのように記述される: V i + 1 ( s ) ← max a ∈ A s ∑ s ′ ∈ S T ( s , a , s ′ ) ( R ( s , a , s ′ ) + γ V i ( s ′ ) ) ∀ s ∈ S {\displaystyle V_{i+1}(s)\leftarrow \max _{a\in A_{s}}\sum _{s'\in S}T(s,a,s'){\Big (}R(s,a,s')+\gamma V_{i}(s'){\Big )}\quad \forall s\in S} 上式をすべての状態において値が収束するまで繰り返したときの値を V ∞ ( s ) {\displaystyle V^{\infty }(s)} とし、最適政策 π ∗ {\displaystyle \pi ^{*}} を次式で求める。 π ∗ ( s ) ← arg max a ∈ A s ∑ s ′ ∈ S T ( s , a , s ′ ) ( R ( s , a , s ′ ) + γ V ∞ ( s ′ ) ) ∀ s ∈ S {\displaystyle \pi ^{*}(s)\leftarrow \arg \max _{a\in A_{s}}\sum _{s'\in S}T(s,a,s'){\Big (}R(s,a,s')+\gamma V^{\infty }(s'){\Big )}\quad \forall s\in S}
※この「価値反復法」の解説は、「マルコフ決定過程」の解説の一部です。
「価値反復法」を含む「マルコフ決定過程」の記事については、「マルコフ決定過程」の概要を参照ください。
- 価値反復法のページへのリンク
