Q学習

環境のモデルを知らずに、最適な行動価値関数を直接学習する手法。 Watkins が 1989 年に提案した。

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha [r_{t+1}+\gamma \underset{a}{\max }Q(s_{t+1},a)-Q(s_t,a_t)]$$

方策外学習 (off-policy)#

更新式に ${\max }_{a}Q(s_{t+1},a)$ が入っている点が要点。

実際に取った行動とは無関係に、最良の行動を仮定して更新する。

そのため

• ランダムに探索しながら、最適方策を学習できる
• 過去の経験を再利用できる（経験再生）

これが SARSA（方策内学習、実際に取った次の行動を使う）との違い。

収束保証#

すべての状態行動対を無限回訪問し、 学習率が適切に減衰すれば、 $Q$ は最適 $Q^{\ast }$ に確率 1 で収束する。

モデルを知らなくても最適方策に到達できるという 理論的な保証があるのが強み。 ただし表形式（関数近似なし）の場合に限る。

DQN#

$Q$ を深層ニューラルネットワークで近似したもの。 Atari のゲームを画素入力から学習し、 人間のスコアを超えたことで注目された（2015 年）。

安定化のための 2 つの工夫。

工夫	目的
経験再生	経験をバッファに貯めてランダムに取り出す。時間相関を断つ
目標ネットワーク	目標値の計算に古い重みを使う。追いかけっこを防ぐ

限界#

• ${\max }_a$ を取るため離散行動にしか使えない
• $\max$ は $Q$ の推定誤差を系統的に過大評価する （Double DQN がこれを補正する）
• サンプル効率が悪い

参考文献#

• Christopher J. C. H. Watkins, Peter Dayan. Q-learning. Machine Learning 8, 1992. https://doi.org/10.1007/BF00992698
• Volodymyr Mnih et al. Human-level control through deep reinforcement learning. Nature 518, 2015. https://doi.org/10.1038/nature14236
• Hado van Hasselt, Arthur Guez, David Silver. Deep Reinforcement Learning with Double Q-learning. AAAI, 2016. https://arxiv.org/abs/1509.06461
• Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction, 2nd ed. MIT Press, 2018.（全文公開） http://incompleteideas.net/book/the-book-2nd.html