マルコフ決定過程
状態遷移確率 T ( s , a , s ′ ) {\displaystyle T(s,a,s')} や報酬関数 R ( s , a , s ′ ) {\displaystyle R(s,a,s')} が未知の場合,環境との相互作用を通じてこれらの情報を得ながら行動を決定する必要がしばしば生じる.このような問題は強化学習の枠組みで議論される.
強化学習における代表的な学習アルゴリズムはQ学習と呼ばれるものである。 Q学習では、行動価値関数 (action-value function) と呼ばれる関数 Q π ( s , a ) {\displaystyle Q^{\pi }(s,a)} に着目する。ここで Q π ( s , a ) {\displaystyle Q^{\pi }(s,a)} は次のように定義される:
いま,最適方策のもとでの行動価値関数 Q ∗ ( s , a ) = max π Q π ( s , a ) {\displaystyle Q^{*}(s,a)=\max _{\pi }Q^{\pi }(s,a)} は V ∗ ( s ) = max a Q ∗ ( s , a ) {\displaystyle V^{*}(s)=\max _{a}Q^{*}(s,a)} を満たす。
ただし R π ( s ) = ∑ a ∈ A ∑ s ′ ∈ S π ( s , a ) T ( s , a , s ′ ) R ( s , a , s ′ ) {\textstyle R^{\pi }(s)=\sum _{a\in A}\sum _{s'\in S}\pi (s,a)T(s,a,s')R(s,a,s')} は状態 s {\displaystyle s} において方策 π {\displaystyle \pi } を採用した場合における即時報酬の期待値である。
任意の π ′ {\displaystyle \pi '} および s ∈ S {\displaystyle s\in S} に対し V π ∗ ( s ) ≥ V π ′ ( s ) {\displaystyle V^{\pi ^{*}}(s)\geq V^{\pi '}(s)} を満たす方策 π ∗ {\displaystyle \pi ^{*}} を最適方策 (optimal policy) と呼ぶ。 π ∗ {\displaystyle \pi ^{*}} を採用したときの状態価値関数の最大値 V ∗ ( s ) = max π V π ( s ) {\displaystyle V^{*}(s)=\max _{\pi }V^{\pi }(s)} は次のベルマン方程式を満たす.