価値関数

その状態（や行動）がどれだけ良いかを、将来の累積報酬で測る。

$$V^{\pi }(s)={𝔼}_{\pi }[G_t|s_t=s]$$ $$Q^{\pi }(s,a)={𝔼}_{\pi }[G_t|s_t=s,a_t=a]$$

即時報酬ではなく将来まで含めた見込みを表すので、 遅延報酬の信用割当を担う。

ベルマン方程式#

価値関数は再帰的な関係を満たす。

$$V^{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime }}P(s^{\prime }|s,a)[r+\gamma V^{\pi }(s^{\prime })]$$

今の価値 = 即時報酬 + 割引した次の価値。 動的計画法の構造そのもので、 部分問題の解を再利用する形になっている。

最適価値関数はベルマン最適方程式を満たす。

$$V^{\ast }(s)=\underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }|s,a)[r+\gamma V^{\ast }(s^{\prime })]$$

TD 学習#

環境のモデル $P$ が分からなくても、 経験から価値を更新できるのが時間差分学習。

$$V(s_t)\leftarrow V(s_t)+\alpha \underset{\text{TD 誤差}}{\underbrace{[r_{t+1}+\gamma V(s_{t+1})-V(s_t)]}}$$

エピソードの終了を待たず、1 ステップごとに更新できる。 モンテカルロ法（終了まで待つ）と動的計画法（モデルが要る）の 中間に位置する。

関数近似#

状態空間が大きいと表で持てない。 ニューラルネットワークで $V_{\theta }(s)$、$Q_{\theta }(s,a)$ を近似する。

ただし「関数近似 + ブートストラップ + 方策外学習」の 3 つが揃うと 発散しうることが知られている（死の三徴）。 DQN の経験再生と目標ネットワークは、この不安定さへの対処。

参考文献#

• Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction, 2nd ed. MIT Press, 2018.（全文公開） http://incompleteideas.net/book/the-book-2nd.html
• Richard S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning 3, 1988. https://doi.org/10.1007/BF00115009
• Volodymyr Mnih et al. Human-level control through deep reinforcement learning. Nature 518, 2015. https://doi.org/10.1038/nature14236