いものやま。

雑多な知識の寄せ集め

強化学習について学んでみた。（その23）

技術 AI 強化学習

すごく久々に。
前回の内容、覚えてるかなw

前回まではTD学習について説明していて、最後に○×ゲームに対してQ学習を使ったAIを実装した。

今日からはTD( \lambda)について説明していく。

動的計画法、モンテカルロ法、TD学習のおさらい

まずは、これまでのおさらいから。

動的計画法、モンテカルロ法、TD学習（Sarsa、Q学習）とやってきたわけだけど、これらはそれぞれ次のような特徴があった。

  • 動的計画法
    • モデルが分かっている場合に使える
    • Bellman方程式を方策反復や価値反復で解いていく
  • モンテカルロ法
    • モデルが分かっていなくても使える
    • 実際に何度も試行して、何度も収益を観測して平均化することで、状態行動対の価値を学習していく
    • 収益が観測されるまで（＝終端状態になるまで）学習は行えない
  • TD学習
    • モデルが分かっていなくても使える
    • 行動した次の状態行動対の推定価値と、現在の状態行動対の推定価値の差分を使って、学習する
    • 推定価値の差分は、直前の状態行動対の推定価値の学習にしか使われない

モデルが分かっている場合、計算に時間はかかるだろうけど、Bellman方程式を解いていく動的計画法を使うのが確実と言える。
ただ、実際にはモデルが分かっている場合というのは、少ないことが多い。
例えば、将棋とかで、この手を指したたら p%の確率でこの局面に遷移するとか、明確に言えるはずもない。

一方、モデルが分かっていない場合には、モンテカルロ法とTD学習（Sarsa、Q学習）を使うことで、実際に何度も試行しながら価値を推定し、行動を改善していくことが出来る。
けど、それぞれに弱点があって、

  • モンテカルロ法は、終端状態にならないと学習が行えない
  • TD学習は、推定価値の差分が直前の状態行動対の学習にしか使われない

という問題があった。

モンテカルロ法とTD学習の融合

そこで、モンテカルロ法とTD学習を融合させたような学習方法を考えていく。

nステップTD予測

方策 \piの元での行動価値 Q_{s, a}^{\pi}というのは、次のように定義されていた：

 {
Q^{\pi}_{s, a} = E \left\{ \left. R_t \right| s_t = s, a_t = a \right\}
}

ここで、収益 R_tというのは、

 {
\begin{align}
R_t &= \sum_{k=0} \gamma^k r_{t+k+1} \\
&= r_{t+1} + \gamma \sum_{k=0} \gamma^k r_{t+k+2} \\
&= r_{t+1} + \gamma Q_{s_{t+1}, a_{t+1}}^{\pi}
\end{align}
}

と再帰的に表現でき、1段目の式を用いて価値の推定を行うーーすなわち、最終的に得られた報酬の合計（＝収益）を価値の推定に使うーーのがモンテカルロ法で、3段目の式を用いて価値の推定を行うーーすなわち、直後に得られた報酬と次に観測された状態行動対の推定価値の和を価値の推定に使うーーのがTD学習だった。

けど、よく考えてみれば、これはさらに再帰的に展開することが出来る。

具体的には、

 {
\begin{align}
R_t &= r_{t+1} + \gamma Q_{s_{t+1}, a_{t+1}}^{\pi} \\
&= r_{t+1} + \gamma r_{t+2} + \gamma^2 Q_{s_{t+2}, a_{t+2}}^{\pi} \\
&= r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \gamma^3 Q_{s_{t+3}, a_{t+3}}^{\pi} \\
&= \cdots \\
&= r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{n-1} r_{t+n} + \gamma^n Q_{s_{t+n}, a_{t+n}}^{\pi} \\
&= \cdots \\
&= \sum_{k=0} \gamma^k r_{t+k+1}
\end{align}
}

そこで、 nステップ先の推定価値を使う収益 R^{(n)}_tを、

 {
R^{(n)}_t = r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{n-1} r_{t+n} + \gamma^n Q_{s_{t+n}, a_{t+n}}^{\pi}
}

とし、これを nステップ収益と呼ぶことにする。

そうすると、 nステップ収益を使って、行動価値 Q_{s, a}を

 {
Q_{s, a} \leftarrow Q_{s, a} + \alpha \left( R^{(n)}_t - Q_{s, a} \right)
}

と改善する方法が考えられて、これをnステップTD法と呼ぶ。

なお、 n=1とすれば、 R^{(1)}_t = r_{t+1} + \gamma Q_{s_{t+1}, a_{t+1}}なので、これはTD学習と一致することになる。

また、 nを限りなく大きくして全部展開すると、それはモンテカルロ法と一致することになる。
（ただし、厳密に平均をとる方法ではなく、ステップサイズを使う方法になる）

つまり、nステップTD法という枠で考えると、TD学習もモンテカルロ法もその一実装となって、その両端に存在するアルゴリズムであることが見えてくる。

ところで、実はまだ話は終わっていない。
というのも、さらに融合させる方法を考えることが出来るから。
これについては、明日見ていく。

今日はここまで！

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本（ソフトカバー）
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る