いものやま。

雑多な知識の寄せ集め

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

技術 AI 強化学習

昨日はモンテカルロ-ES法を使ってブラックジャックのAIをプログラミングした。

今日は、開始点探査の仮定を外す方法について考えていく。

方策オン型手法と方策オフ型手法

まず、開始点探査の仮定を外す方法として、大きく分けて2通りの方法が考えられる。

一つは、方策 \piを決定論的なもの（＝各状態で選ばれる行動は常に同じ）からソフトなもの（＝各状態で選ばれる行動は確率に従う）へ変更して、任意の状態行動対 (s, a) \in \mathcal{S} \times \mathcal{A}(s)について \pi(s, a) \gt 0であることを保証する方法。
こうすることで、開始点探査の仮定を入れなくても、任意の状態行動対が観測されるようになる。

もう一つは、評価、改善しようとしている方策 \piとは別の方策 \pi'を使って状態行動対の列を観測し、その観測結果を使って方策 \piの評価/改善をする方法。
そのようなことが可能であれば、たとえ方策 \piが決定論的なものであったとしても、状態行動対の列を生む方策 \pi'としてソフトなものを使うことで、開始点探査の仮定を入れなくても、任意の状態行動対を観測することが可能になってくる。

前者の方法を方策オン型手法、後者の方法を方策オフ型手法と呼ぶ。
この「オン」/「オフ」というのは、状態行動対の列を観測するためのシミュレーションをするときに、評価、改善対象の方策を「使う」/「使わない」ということを意味している。

方策オン型モンテカルロ制御

方策オン型モンテカルロ法では、方策として決定論的な方策ではなく、ソフトな方策を用いる。
その一つとして、 \varepsilonグリーディ方策を使う方法がある。

\varepsilonグリーディ方策は、次のような方策：

 {
\pi(s, a) = \left\{\begin{array}{ll}
1 - \varepsilon + \frac{\varepsilon}{\left|\mathcal{A}(s)\right|} & \left(a\mbox{はグリーディな行動}\right) \\
\frac{\varepsilon}{\left|\mathcal{A}(s)\right|} & \left(\mbox{それ以外}\right)
\end{array}\right.
}

ただし、 \varepsilonは 0 \lt \varepsilon \lt 1の小さな定数。

照明は省略するけど（本を参照。ただし、けっこう分かりにくい・・・）、 \varepsilonグリーディ方策を使う場合も、ちゃんと方策が改善されるようになっている。

\varepsilonグリーディ方策を使った方策オン型モンテカルロ制御は、次のようなアルゴリズムになる：

  1. すべての (s, a) \in \mathcal{S} \times \mathcal{A}(s)に対して、以下のように初期化する：
    • Q_{s, a} \leftarrow \mbox{任意の値}
    • Returns(s, a) \leftarrow \mbox{空のリスト}
    • \pi \leftarrow \mbox{任意のソフト方策}
  2. 以下を繰り返す：
    1. 方策 \piに従ってエージェントを行動させ、状態行動対の列 (s_0, a_0), (s_1, a_1), (s_2, a_2), \cdots, (s_{T-1}, a_{T-1})と報酬の列 r_1, r_2, \cdots , r_Tを観測する。
    2. 方策評価
      観測された各状態行動対 (s_t, a_t) \: (t=0, 1, 2, \cdots, T-1)について、初回訪問なら：
      1. R \leftarrow \sum_{t' = t+1}^T r_{t'}
      2. Rを Returns(s_t, a_t)に追加する。
      3. Q_{s_t, a_t} \leftarrow \mbox{average}\left(Returns(s_t, a_t)\right)
    3. 方策改善
      観測された各状態 s_t \: (t=0, 1, 2, \cdots, T-1)について、初回訪問なら：
      1. a^{\ast} \leftarrow \mathop{\mbox{arg max}}_{a \in \mathcal{A}(s_t)} Q_(s_t, a)
      2. 各 a \in \mathcal{A}(s_t)について：
        • a=a^{\ast}なら、 \pi(s_t, a) \leftarrow 1 - \varepsilon + \frac{\varepsilon}{\left|\mathcal{A}(s_t)\right|}
        • a \neq a^{\ast}なら、 \pi(s_t, a) \leftarrow \frac{\varepsilon}{\left|\mathcal{A}(s_t)\right|}

方策オフ型モンテカルロ制御

方策オフ型モンテカルロ法では、評価、改善される方策 \piと、状態行動対の列を作るための方策 \pi'を分けて扱う。
前者の方策を推定方策、後者の方策を挙動方策と呼ぶ。

さて、では、どうやって挙動方策を使って推定方策を評価、改善すればいいのか？
というのも、方策が変わってしまえば、当然そこで得られた収益もあくまで「挙動方策での」収益であって、推定方策で同じ収益が得られるとは限らないから。

そこで、実際に観測された状態行動対の列がそれぞれの方策で観測される確率を比較して、それを収益を評価するときの重みとして使うということを考える。

例えば、挙動方策で状態行動対の列 (s, a), \cdotsと収益 Rが観測されたとする。
ここで、その状態行動対の列を観測する確率が、推定方策で p、挙動方策で p'だとすると、推定方策では確率的に \frac{p}{p'}回、収益 Rを観測するということになる。

これは、推定方策 \piで状態行動対の列 (s, a), \cdotsと収益 Rが1回観測されたときに、

  • R_{sum} \leftarrow R_{sum} + R
  • k \leftarrow k + 1
  • Q^{\pi}(s, a) \leftarrow \frac{R_{sum}}{k}

と評価していたところを、 \frac{p}{p'}回観測されたという意味で、

  • R_{sum} \leftarrow R_{sum} + \frac{p}{p'} R
  • k \leftarrow k + \frac{p}{p'}
  • Q^{\pi}(s, a) \leftarrow \frac{R_{sum}}{k}

と評価することになる。

ところで、ステップ時間tで状態行動対が (s_t, a_t)であるときに、方策 \piでそのあと状態行動対の列が (s_{t+1}, a_{t+1}), (s_{t+2}, a_{t+2}), \cdotsとなる確率を p^{\pi}(s_t, a_t)とすると、

 { \displaystyle
p^{\pi}(s_t, a_t) = \mathcal{P}_{s_{t} s_{t+1}}^{a_t} \prod_{k=t+1} \pi(s_k, a_k) \mathcal{P}_{s_k s_{k+1}}^{a_k}
}

であるから、挙動方策での収益の評価に対する、推定方策での収益の評価の重みを w(s_t, a_t)とすると、これは

 { \displaystyle
\begin{align}
w(s_t, a_t) &= \frac{p^{\pi}(s_t, a_t)}{p^{\pi'}(s_t, a_t)} \\
&= \frac{\mathcal{P}_{s_{t} s_{t+1}}^{a_t} \prod_{k=t+1} \pi(s_k, a_k) \mathcal{P}_{s_k s_{k+1}}^{a_k}}{\mathcal{P}_{s_{t} s_{t+1}}^{a_t} \prod_{k=t+1} \pi'(s_k, a_k) \mathcal{P}_{s_k s_{k+1}}^{a_k}} \\
&= \frac{\prod_{k=t+1} \pi(s_k, a_k)}{\prod_{k=t+1} \pi'(s_k, a_k)} \\
&= \prod_{k=t+1} \frac{\pi(s_k, a_k)}{\pi'(s_k, a_k)}
\end{align}
}

と計算できることが分かる。
このとき、どのように状態遷移するかという確率である \mathcal{P}は分子と分母で打ち消しあって不要になるので、モデルが分からなくても、方策の値だけで計算できるようになっているのがポイント。
これで、挙動方策を使って観測された状態行動対の列に対して推定方策の評価が出来るようになった。

さて、ここからは特に、推定方策 \piが決定論的な方策の場合を考えていく。
このとき、重みを計算するときの分子は

  • a_t = \pi(s_t)なら、1
  • a_t \neq \pi(s_t)なら、0

となる。
なので、観測された状態行動対の列を後ろから見ていって初めて a_t \neq \pi(s_t)となったステップ時間を \tauとすると、任意の t \lt \tauについて w(s_t, a_t) = 0となるので、 \tauより前の状態行動対については学習しても意味がないことが分かる。

そこで、次のような方策オフ型モンテカルロ制御のアルゴリズムが得られる：

  1. すべての (s, a) \in \mathcal{S} \times \mathcal{A}(s)に対して、以下のように初期化する：
    • Q_{s, a} \leftarrow \mbox{任意の値}
    • R_{sum}(s, a) \leftarrow 0
    • k(s, a) \leftarrow 0
    • \pi \leftarrow \mbox{任意の決定論的方策}
  2. 以下を繰り返す：
    1. 任意のソフト方策 \pi'に従ってエージェントを行動させ、状態行動対の列 (s_0, a_0), (s_1, a_1), (s_2, a_2), \cdots, (s_{T-1}, a_{T-1})と報酬の列 r_1, r_2, \cdots , r_Tを観測する。
    2. \tauを、以下を満たすような時刻とする：
      • a_{\tau} \neq \pi(s_{\tau})
      • \forall t \gt \tau, \; a_t = \pi(s_t)
    3. 方策評価
      観測された各状態行動対 (s_t, a_t) \: (t=\tau, \tau+1, \tau+2, \cdots, T-1)について、初回訪問なら：
      1. w \leftarrow \prod_{k=t+1}^{T-1} \frac{1}{\pi'(s_k, a_k)}
      2. R \leftarrow \sum_{k=t+1}^{T} r_k
      3. R_{sum}(s_t, a_t) \leftarrow R_{sum}(s_t, a_t) + w R
      4. k(s_t, a_t) \leftarrow k(s_t, a_t) + w
      5. Q_{s_t, a_t} \leftarrow \frac{R_{sum}(s_t, a_t)}{k(s_t, a_t)}
    4. 方策改善
      観測された各状態 s_t \: (t=\tau, \tau+1, \tau+2, \cdots, T-1)について、初回訪問なら：
      1. \pi(s_t) \leftarrow \mathop{\mbox{arg max}}_{a \in \mathcal{A}(s_t)} Q_(s_t, a)

なお、挙動方策 \pi'には、\varepsilonグリーディ方策などを使えばいい。

今日はここまで！

強化学習

強化学習

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