マルコフ決定過程
価値反復法 (value iteration)は後ろ向き帰納法 (backward induction) とも呼ばれ、ベルマン方程式を満たす価値関数を繰り返し計算により求める。 ロイド・シャープレー が1953年に発表した確率ゲーム(英語版)に関する論文には価値反復法の特殊な場合が含まれるが、このことが認知されたのは後になってからである.
ステップ i {\displaystyle i} における価値関数の計算結果を V i ( s ) {\displaystyle V_{i}(s)} と表記すると、価値反復法における更新式はつぎのように記述される:
上式をすべての状態において値が収束するまで繰り返したときの値を V ∞ ( s ) {\displaystyle V^{\infty }(s)} とし、最適方策 π ∗ {\displaystyle \pi ^{*}} を次式で求める。
有限マルコフ決定過程 (finite Markov decision process; finite MDP) は4つの要素の組 ⟨ S , A , T , R ⟩ {\textstyle {\big \langle }S,A,T,R{\big \rangle }} で表される。ここで各要素はそれぞれ次を意味する。
S = { s 1 , s 2 , ... , s N } {\displaystyle S=\{s^{1},s^{2},\ldots ,s^{N}\}} : 状態の有限集合
A = { a 1 , a 2 , ... , a K } {\displaystyle A=\{a^{1},a^{2},\ldots ,a^{K}\}} : 行動の有限集合
T : S × A × S → [ 0 , 1 ] {\displaystyle T:S\times A\times S\to [0,1]} : 遷移関数 (transition function)
R : S × A × S → R {\displaystyle R:S\times A\times S\to \mathbb {R} } : 報酬関数 (reward function)