強化学習　動的計画法

動的計画法を適用するには、以下の二つの条件が必要である。

• 環境モデル$${Pr(s',r|s,a)}$$が既知である

• エージェントはマルコフ性を持つ

ポリシーの改善

　前記事のベルマン方程式を用いて、任意のポリシー$${\pi}$$に対っする価値関数を計算する。$${\nu^{(0)}(s)=0}$$と初期化し、その後のイテレーション$${i+1}$$において、ベルマン方程式を用いて各状態の価値を更新する。
$${\nu^{(i+1)}(s)=\sum_{a}\pi(a|s)\sum_{r \in R, s' \in S } Pr(s',r|s,a)[r+\gamma \nu^{(i)}(s')]}$$
$${\lim_{i\to \infty}\nu^{i}(s)=\nu_{\pi}(s)}$$であり、これを用いて、既存のポリシー$${\pi}$$を状態ごと、つまり状態$${s}$$において、より高い価値を導く新たな$${\pi'}$$に更新する。
$${\nu_{\pi'}(s)\ge \nu_{\pi}(s)}$$
　この新しい$${\pi'}$$の特定は、行動価値関数を使って行う。
$${q_{\pi}(s,a)=\sum_{s' \in S, r \in R}Pr(s',r|s,a)[r+\gamma\nu_{\pi}(s')]}$$
から、上記で得られた$${\nu_{\pi}(s)}$$を使って$${q_{\pi}(s,a)}$$が計算される。
$${q_{\pi}(s,a)}$$は状態の行動のペアで価値が決まることから、最も高い状態価値を$${q_{\pi}(s,a)}$$から計算した後に、$${{\text{argmax}}_{a}q_{\pi}(s,a)}$$なる行動と、ポリシーが最も高い確率で提案する行動$${{\text{argmax}}_{a}\pi(a|s)}$$が違う場合、高い行動価値を実現する行動を選ぶポリシーに更新する。

価値反復法

$${\nu_{\pi}(s)}$$により、$${\nu_{\pi'}(s) \ge \nu_{\pi}(s), s \in S}$$なる$${\pi'}$$を更新していくにつれ、最善のポリシーに到達できるのと同様に、$${\nu^{(i+1)}(s)={\text{max}}_{a}\sum_{s'\in S , r\in R}Pr(s',r|s,a)[r+\gamma\nu^{(i)}(s')]}$$
をから、次のイテレーションの状態価値と即時報酬の荷重和を最大にする行動を選ぶことで、次の状態価値を更新する。