強化学習: ノート8

読んでいる本(出典): 強化学習 : Richard S.Sutton, Andrew G.Barto, 三上 貞芳, 皆川 雅章 : 本 : Amazon.co.jp

前回:ノート7 / 次回:ノート9
目次:強化学習

今日読んだページ: 72~92ページ
以下、自分の解釈・感想・雑談。

  • (前回)「状態」は(ほぼ)マルコフ性をもつように設計する。強化学習の枠組みがそう要請しているので。
  • マルコフ性をもつ強化学習タスクで必要なのは、現在の状態  s_t=s に対して行動 a_t=a をとったときに、
    • ありうる次の状態 s_{t+1} の確率分布(状態が離散的なら、遷移確率 \mathcal{P}^a_{ss'} を完全に決めればよい)。
    • ある  s_{t+1}=s' となったときの報酬  r_{t+1} の期待値 \mathcal{R}^a_{ss'}(分布までは興味はない)。
  • 上記2つを後々「環境のダイナミクス(84ページ)」とよんでいるもよう。環境がどう応答してくるか、を指すからか。
  • マルコフ決定過程の理解と練習問題 3.7 を兼ねてタスク設定の例を自分で考える(転職するか残留するか判断するエージェント)。しかし現実的にはきっとマルコフ性はない。

    f:id:cookie-box:20160403143322p:plain:w700

    • 状態集合は勤務先に「満足」か「不満」とする。
    • 勤務先に「満足」なときは必ず「残留」し、「不満」なときは「残留」か「転職」かを判断するものとする。
    • 現在「満足」で残留して次の状態でも「満足」な確率が  \alpha で、「不満」に遷移する確率が  1-\alpha とする。
    • 現在「不満」で残留すれば次の状態も必ず「不満」とする(満足に転じることはないとする)。
    • 現在「不満」で転職して「満足」に遷移する確率を \beta 、また不満な勤務先を引いてしまう確率を 1-\beta とする。
    • 次ステップにもらえる報酬は次ステップの勤務先が満足か不満かに応じて  \mathcal{R}^{\rm sat}, \; \mathcal{R}^{\rm unsat} と考えてもいいだろう。 \mathcal{R}^{\rm unsat} は負かもしれない。ただし、行動として「転職」を判断する場合は色々疲弊しそうなので  c を差し引くとする。
  • 75ページからは価値関数、つまり、状態行動対の関数であって、その選択がどれくらいよいのかを与える関数。価値関数は、次ステップ以降の総報酬(収益)の期待値である。価値関数は方策(状態から行動への写像)に対して定義される。
    • AlphaGo の価値関数はその方策の下での状態行動対に対する勝利の期待値らしいです。
    • 価値関数が方策に対して定義されるというのは、あるステップでの選択の価値は当然、その後どんな方策で行動していくかに依存するから。例えば、自分の初手7六歩と、羽生名人の初手7六歩とでは、もうこの時点で勝利への太さ(AlphaGo であったらイコール価値)が違うのは確定的に明らか。
  • いま状態 s にいるとき、状態価値関数  V^{\pi}(s) 、行動価値関数  Q^{\pi}(s, a) が定義できる。これからただちに方策  \pi にしたがうか、まず行動  a を取った後に方策  \pi にしたがうかの違い。
    • AlphaGo 論文の冒頭に、完全情報ゲームは最適な  V^{\ast}(s) をもつと書いてありましたね(それを現実的な時間内に求めきって利用できるとはいっていない)。
      • もう少し先まで読むと、まさに81ページから最適価値関数が出てくる。
    • これまで遭遇した状態の平均からこれらの価値関数を見積もるのがモンテカルロ法
      • スロットマシンを引くバンディットタスクでは過去にアームを引いた結果を保持していた。
    • しかし状態数が非常に増えると上記の方法は現実的ではないので、パラメータを含む価値関数のパラメータを調整していくことになる。
      • AlphaGo はこちら。
  • 状態価値関数は、定義から以下の Bellman 方程式を満たす(76ページ)。逆に、これを解くと  V^{\pi} が求まる。
     \displaystyle V^{\pi}(s)=\sum_a \pi(s,a) \sum_{s'} \mathcal{P}^{a}_{ss'} [\mathcal{R}^{a}_{ss'} + \gamma V^{\pi}(s')]
  • 有限MDP(マルコフ決定過程)には最適方策(群)が存在する。最適方策群は最適価値関数をもつ。
    要は最適価値関数を最大にする方策  \pi (1つとは限らない)は最適方策である。
    • AlphaGo の論文に、囲碁も最適方策をもつが、その探索は "infeasible" と書いてあった。
  • 79ページの図のゴルフでは、左からカップに近い順に、以下のクラブを選択するのが最適ということと理解。
    ゴルフをやったことがないので、パターは正確に狙える範囲が広いものというのをはじめて知りました。
    パターでも
    ドライバー
    でも1打
    パターなら
    1打
    パターでも
    ドライバー
    でも2打
    ドライバー
    なら2打
    ドライバー
    なら3打
    以降、ずっと
    ドライバーが
    最適
  • 最適価値関数を求めるには最適価値関数に対する Bellman 方程式を解けばよい。
  • 最適価値関数が求められたら、最適方策も得られる。つまり、常に価値関数が最大になる行動を0より大きい確率で選択するように  \pi(s, a) を構成すればよい。
  • 価値関数が最適価値関数ならば、価値関数に関してグリーディな方策は最適方策となる。最適価値関数には将来の報酬がちゃんと織り込まれているから。
  • と聞くと、Bellman 方程式を解いて最適価値関数を求めれば強化学習タスクが解けるように思えるが、通常、このアプローチは全然有効ではない。なぜなら往々にして、
  • といっても実際的な解法で Bellman 方程式は大いに利用されている。
    種々の強化学習問題の解法は4章以降で!



以下、練習問題への自分なりの回答。

  • 練習問題 3.8
    • 行動価値関数についての Bellman 方程式はどうなるか。
      • 式変形していけばいいんじゃないでしょうか。
         \displaystyle Q^{\pi}(s,a)= \, E_{\pi} \left[ \sum_{k=0}^{\infty} \gamma ^k r_{t+1+k} \middle| s_t=s, \, a_t=a \right]
         \displaystyle \qquad \qquad =E_{\pi} \left[ r_{t+1} + \gamma \sum_{k=0}^{\infty} \gamma ^k r_{t+2+k} \middle| s_t=s, \, a_t=a \right]
         \displaystyle \qquad \qquad =E_{\pi} \biggl[ r_{t+1} \Bigg| s_t=s, \, a_t=a \biggr] + \gamma E_{\pi} \left[ \sum_{k=0}^{\infty} \gamma ^k r_{t+2+k} \middle| s_t=s, \, a_t=a \right]
         \displaystyle \qquad \qquad = \sum_{s'} \mathcal{P}^a_{ss'} \mathcal{R}^a_{ss'} + \gamma \sum_{s'} \mathcal{P}^a_{ss'} E_{\pi} \left[\sum_{k=0}^{\infty} \gamma ^k r_{t+2+k} \middle| s_{t+1}=s' \right]
         \displaystyle \qquad \qquad = \sum_{s'} \mathcal{P}^a_{ss'} \mathcal{R}^a_{ss'} + \gamma \sum_{s'}  \mathcal{P}^a_{ss'} \sum_{a'} \pi(s', a') E_{\pi} \left[\sum_{k=0}^{\infty} \gamma ^k r_{t+2+k} \middle| s_{t+1}=s', \, a_{t+1}=a' \right]
         \displaystyle \qquad \qquad = \sum_{s'} \mathcal{P}^a_{ss'} \mathcal{R}^a_{ss'} + \gamma \sum_{s'}  \mathcal{P}^a_{ss'} \sum_{a'} \pi(s', a') Q^{\pi}(s', a')
         \displaystyle \qquad \qquad = \sum_{s'} \mathcal{P}^a_{ss'} \sum_{a'} \pi(s', a') \biggl[ \mathcal{R}^a_{ss'} + \gamma Q^{\pi}(s', a') \biggr]
  • 練習問題 3.9
    • テキストの、格子世界を移動する例で Bellman 方程式が成り立つことを確認せよ、という問題。およそ 0.7 になる。
      > V <- c(2.3, 0.4, -0.4, 0.7)
      > R <- c(0, 0, 0, 0)
      > P <- c(1, 1, 1, 1)
      > pi <- c(0.25, 0.25, 0.25, 0.25)
      > sum(pi * P * (R + 0.9 * V))
      [1] 0.675
  • 練習問題 3.10 & 3.11
    • 毎ステップの報酬にオフセットを付けても問題がない場合と、問題がある場合がある。
    • 例えば、迷路から抜け出すエピソード的タスクで、あらゆる時間ステップで -1 の報酬を与えるケースについて、毎ステップの報酬にオフセットを付けてこれを 0 にしたり 1 にしたら「より短いステップ数で脱出すると収益が大きくなる」にならず、意図通りの学習をさせることができない。
  • 練習問題 3.12 & 3.13
    • いまいるノードの価値は、次のノードの価値の式でかけるという話。ボードゲームっぽい話になってきたような。たぶん以下。
      •  \displaystyle V^{\pi}(s) = E_{\pi} \Bigl[ Q^{\pi}(s_t, a_t) \bigg| s_t=s \Bigr] = \sum_{a'} \pi(s, a') Q^{\pi}(s, a')
      •  \displaystyle Q^{\pi}(s, a) = E_{\pi} \Bigl[ r_{t+1} + V^{\pi}(s_{t+1}) \bigg| s_t=s, \, a_t=a \Bigr] = \sum_{s'} \mathcal{P}^{a}_{ss'} \bigl[ \mathcal{R}^a_{ss'} + V^{\pi}(s') \bigr]
  • 3.8 節の練習問題はパス。

3章まで終わった。2章はやたらプログラミング問題があったけど逆に3章はなくて最近手を動かしていない。
4章はぱらぱらみるとプログラミング問題があるのでやりたい。