
Gymで強化学習⑭モンテカルロ法:後編
前回はモンテカルロ法で開始点探索を前提としないイプシロン・グリーディ法を紹介しました。探索をするためのソフト・ポリシーを改善できることを数式で証明もしました。
今回はモンテカルロ法でイプシロン・グリーディを利用する方法としてオンポリシーとオフポリシーについて解説します。これらは後に登場するSARSAとQ学習にもつながる概念でもあります。
ただし、前回の記事で数式の羅列がたくさん登場したので、まずは最初にモンテカルロ法の全体像を再訪します。特に、動的計画法で学んだポリシー反復法と照らし合わせてモンテカルロ法の特徴を再確認します。
その上で、オンポリシーとオフポリシーという動的計画法にはなかった概念の意味について解説します。
モンテカルロ法とポリシー反復法
動的計画法で学んだポリシー反復法では、ポリシーの評価とポリシーの改善を交互に繰り返します。
ポリシーの評価::ポリシーを固定して状態価値関数を更新すること。
ポリシーの改善:状態価値関数を固定してポリシーを更新すること。
動的計画法では環境のモデルが与えられているので状態遷移の確率を利用してポリシーの最適化を行うことができます。また、最適化はエピソードが始まる以前に完了しました。最適なポリシーは状態価値関数と状態遷移の確率に従って行動価値を最大にする行動を選択します。

モンテカルロ法では環境のモデルを持たないので、環境との相互作用を通して得た経験から行動価値関数を更新します。よってモンテカルロ法によるポリシーの最適化はたくさんのエピソードからの経験の積み重ねを必要とします。つまり、モンテカルロ法ではサンプルを使って行動価値関数を予測するので環境のモデルを必要としません。また、ブートストラッピングも行いません。これは動的計画法が状態遷移の確率とブートストラッピングを使って行動価値関数を計算するのと大きく異なる点です。
なお、モンテカルロ法のように環境のモデルを使わないポリシーをモデルフリー(Model-free)ポリシーと呼びます。これに対して、動的計画法のように環境のモデルを使うポリシーをモデルベース(Model-based)ポリシーと呼びます。
なお、行動の価値を予測するには、エピソードから経験を通して集めたサンプル(状態、行動、報酬)を使って計算した生涯報酬の平均値を使います。そのため、たくさんのサンプルを集める必要があり、また予測された行動価値は「真の状態遷移確率を用いて計算した行動価値の期待値」の近似となります。つまり、モンテカルロ法はサンプルを集めることで「暗に状態遷移の確率を予測している」と捉えることもできます。
ただし、サンプルによる予測値が真の期待値へ収束するにはあらゆる状態であらゆる行動を何度も繰り返す必要があります。そのために開始点探索が提案されました。開始点探索では本来のスタート地点ではなく、ランダムに選ばれた状態からエピソードを開始します。開始点探索を無限に続けることで理論的にはモンテカルロ法による行動価値の予測は真の期待値に収束します。

ただし、凍った湖のように開始点探索が実行できない環境があるので開始点探索を条件から外すためにイプシロン・グリーディが導入されました。前回の記事では、数式を使ってイプシロン・グリーディがポリシーを改善することを示しました。これによって、ポリシーの改善を繰り返せばどんどんより最適化されたポリシーになるという理屈です。どのくらい繰り返すのかは、イプシロンを0に近づける速度を調節することでコントロールします。
なお、サンプルを使った行動価値の予測を更新するには、エピソードが終了してから生涯報酬の計算を行う必要があります。よって、エピソード中は行動価値は固定されています。その際、イプシロン・グリーディによってポリシーは改善されています。

以上より、モンテカルロ法では、エピソードごとにポリシーの評価(行動価値の更新)とポリシーの改善(イプシロン・グリーディ)が行われます。これがモンテカルロ法におけるポリシー反復法です。動的計画法によるポリシー反復法とは異なりますが、やっていることはポリシーの評価と改善を繰り返して最適化していることにほかありません。
オンポリシーとオフポリシー
オンポリシーとオフポリシーの違いはサンプルを集めるために使うポリシーと評価・改善の対象となるポリシーが同じかどうか決まります。これまで見てきた開始点探索やイプシロン・グリーディによるモンテカルロ法はオンポリシーになります。
開始点探索とイプシロン・グリーディではサンプルの集め方が異なりますが、サンプルを集めるためのポリシーと評価・改善の対象となるポリシーが同一である点が共通しています。具体的に見ていきましょう。
開始点探索では、初期状態とその状態における行動がランダムに選ばれます。そのあとはポリシーに従って行動しサンプルを集めます。このようにして集められたサンプルを使ってポリシーが評価・改善されるので、サンプルを集めるポリシーと評価・改善の対象となるポリシーが同じです。
イプシロン・グリーディでは、決められた初期状態からポリシーに従って行動します。ここでいうポリシーとはイプシロンによってランダムに行動する部分も含めたものです。よってサンプルを集めるポリシーと評価・改善されるポリシーは同じものです。
なお、オンポリシーの手法についてよく考えてみると、そこにはある妥協が含まれているのがわかります。なぜなら、オンポリシーによって集められたサンプルはランダムな行動による状態遷移を含むので、それを使って行動価値を予測するのは最適なポリシーにランダムな行動が混じったポリシーを予測しているのと同じだからです。
もちろん、イプシロンの値が0に近くなっていけばランダムな行動が混じる可能性も小さくはなります。しかし、イプシロンの低減のスケジュールの調整に慎重になる必要もあります。
そこで、他の方法として探索をするポリシーと評価・改善されるポリシーを別々にすることが考えられます。つまり、探索しながらサンプルを集める際にはランダムな行動を取るが、ポリシーの評価・改善の過程ではランダムな行動からの悪影響が及ばないようにするわけです。これがオフポリシーを使う主な動機です。
なお、オフポリシーでは探索するポリシーを挙動ポリシー(Behavior Policy)と呼び、評価・改善されるポリシーをターゲットポリシー(Target Policy)と呼びます。挙動ポリシーをターゲットポリシーと切り離すことでターゲットポリシーの評価・改善を邪魔することなく、より自由な探索が可能となることです。
その反面、オフポリシーはオンポリシーよりも複雑になります。なぜなら、挙動ポリシーはターゲットポリシーとは異なる確率で行動を選ぶため、集めたサンプルを使って単純に平均を計算すると最適なポリシーの行動価値関数の予測にならないからです。
そのため、次のセクションで見るように、ある調整を必要とします。
オフポリシーと重点サンプリング
オフポリシーでは、挙動ポリシーとターゲットポリシーを利用して状態価値関数や行動価値関数を更新します。
なお、状態価値関数や行動価値関数を更新するには、挙動ポリシーによるサンプルを使います。よって、挙動ポリシーはターゲットポリシーが選べるすべての行動選択に対して正の確率を持つ必要があります。
数式にすると以下になります。
つまり、ある状態において、ターゲットポリシーが正の確率をもつ行動に対しては、挙動ポリシーも正の確率を持たなければなりません。
なお、挙動ポリシーがソフトポリシーであるならば、どの状態におけるどの行動に対して正の確率を持ちます。
よって、上記のの条件も満たされます。また、挙動ポリシーの目的が探索(exploration)であることからソフトポリシーがよく使われます。例えば、イプシロン・グリーディを使うことができます。その際、上記の条件を満たすためにイプシロンは正の値である必要があります。
一方、ターゲットポリシーは最適ポリシーを目指すので決定論的なポリシーになります。ターゲットポリシーは予測された行動価値関数に従って行動価値が最大になるように行動選択を行います。つまり、搾取(exploitation)するわけです。
ただし、挙動ポリシーはターゲットポリシーとは異なる確率で行動選択するので、挙動ポリシーによるサンプルで計算した生涯報酬はターゲットポリシーに従って行動した場合の生涯報酬と必ずしも一致しません。つまり、行動価値関数の予測が最適になるとは限らないという問題があります。
例えば、下図を見てください。状態9で挙動ポリシーは上下左右どの行動も選ぶ可能性があります。

これによって選ばれたサンプルを使って状態9からの生涯報酬を計算すれば、それは挙動ポリシーによる行動価値関数の予測にはなりますが、最適ポリシーの行動価値関数の近似になるとは限りません。むしろ、大きくズレることが考えられます。それでは、最適ポリシーを目指すターゲットポリシーのための行動価値関数を更新する役には立ちません。
挙動ポリシーによるサンプルが役に立たない具体例を見てみましょう。例えば、凍った湖の環境で滑らない(slippery = False)設定を考えます。そこで10回のエピソードを行った場合に、挙動ポリシーは下図の左のようにランダムな行動を選択したとします。

しかし、決定論的な最適ポリシー(上図の右)は状態に応じて毎回同じ行動を選択するので10回のエピソードで常に下への移動を選ぶとします。この二つのポリシーを別々に使ってエピソードを繰り返し行動価値関数をそれぞれ予測したら全く異なるものになるのは明白です。つまり、行動価値関数の予測はポリシーの行動選択に依存するわけです。
もう一つの例として、滑りやすい環境(slippery = True)で挙動ポリシーが下図の左のようなサンプルを得たとします。しかし、最適ポリシーなら右のようなサンプルを得るでしょう。

なぜなら、最適ポリシーは決定論的に下への行動を選択します。そうすることで上の穴に落ちないで済むからです。また、滑りやすい環境では下への移動を選択しても左右に移動する確率が各々3分の1あるので上記のようにランダムに状態遷移が生じます。実際のサンプルが必ずしも3分の1に近くなるとは限りませんが、状態遷移の確率がそのように設定されているので、おおよそそうなる傾向があるはずです。
つまり、いずれの環境においても、挙動ポリシーに従った行動で集めたサンプルによる生涯報酬で予測をした行動価値関数が最適なポリシーによるものから大きく異なってもおかしくはありません。このままでは、最適ポリシーを目指しているターゲットポリシーにとって不都合です。挙動ポリシーが集めたサンプルをそのまま使ったのでは最適な行動価値を予測することができないからです。
よって、挙動ポリシーが集めたサンプルで計算した生涯報酬をそのまま状態・行動ごとに単純平均するのではなく、何らかの調整をほどこしてあたかもターゲットポリシーが生成したサンプルの回数によって平均したのに近くなるようにする必要があります。つまり、確率の調節を行います。
幸なことにポリシーはある状態におけるある行動の確率を返すので、ターゲットポリシーと挙動ポリシーの確率比を計算するのは可能です。そして、それを利用した手法を重要サンプリングと呼びます。
重要サンプリングの基本的な考え方は単純です。ある状態において挙動ポリシーが行動を選んだ時の確率はです。また、同じ状態で、ターゲットポリシーが行動を選ぶ確率はなります。よって確率の比は次になります。
ここで、挙動ポリシーがソフトポリシーならばなので0で割り算する恐れはありません。仮に、挙動ポリシーがソフトポリシーではなくが保証されないとしても、であることは保証しないといけないのでであるところでは上記の確率の比が存在することになります。また、後で述べますがになる状態がある状態遷移に関しては生涯報酬の計算に含めないようにします。
まとめると、サンプルによる平均を計算する際に上記の確率の比を使って生涯報酬のサンプル値を調節すれば、ターゲットポリシーの確率で行動価値の期待値を計算しているのと同じになります。
ただし、重点サンプルを計算する時には、いくつか注意が必要になります。
重点サンプリングの計算
あるエピソード内で、挙動ポリシーに従って次のように状態からへと遷移したとします。

各状態における行動選択の確率はに従います。また、状態において行動を選んだ時に、状態に状態遷移する確率をと表現します。ここでは、仮に環境のモデルがあるとしていますが、後でその必要がなくなります。
上記の設定から、挙動ポリシーが状態で行動を選ぶ確率はであり、それによって状態から状態へ遷移する確率はとなります。以上を踏まえて上記の一連の状態遷移が生じる確率は以下になります。
さらに、上記の状態遷移がターゲットポリシーでも可能であるとします。つまり、が成り立つならば、ターゲットポリシーによる上記の状態遷移の確率は次になります。
この二つの状態遷移の比をとして以下のように定義します。
長い式ですが、状態遷移の項は共通なので取り除くことができます。
つまり挙動ポリシーとターゲットポリシーによる一連の状態遷移の確率の比を計算するのに環境のモデルである状態遷移の確率は必要ありません。
さらに積の記号を使えば次のように短縮できます。
なお、積の記号は次のように定義されています。
状態でエピソードが終わったとすると状態からの生涯報酬は次のようになります。
は割引率です。また、報酬は状態で行動を選んだ結果として状態に遷移することで得られるとしています。
この生涯報酬の期待値は挙動ポリシーによる状態価値関数に等しくなります。
つまり、挙動ポリシーからのサンプルでそのまま生涯報酬の平均を取ると最適ポリシーの状態価値関数にはなりません。もちろん、行動価値関数も最適にはなりません。しかし、ターゲットポリシーは最適ポリシーを目指しており、行動価値関数から最大の価値がある行動を選ぶ決定論的なポリシーです。なので挙動ポリシーが集めたサンプルから最適な状態価値や行動価値を計算できる仕組みが必要です。
よって、上記の生涯報酬をあたかもターゲットポリシーによるサンプルとみなすために、を掛け合わせます。つまり挙動ポリシーが生成したサンプルが生じる確率をターゲットポリシーによる確率で置き換えたかのように生涯報酬の値を調節するわけです。このようにして調整したサンプルの期待値はターゲットポリシーによる状態価値に等しくなります。
こうしてターゲットポリシーによる期待値が、挙動ポリシーによる期待値として表現されました。このことは、挙動ポリシーによって集められたサンプルを使っても、による生涯報酬の調節を行えばターゲットポリシーによる期待値と同値になることを意味します。
別の見方をすると、上記のように挙動ポリシーとターゲットポリシーによる確率比を挙動ポリシーによる生涯報酬に掛け合わせるのは、挙動ポリシーによって生じたサンプルの回数を調節しているのと同じ効果があります。
例えば、状態価値が大きくなるように調節されるのは、より大きな生涯報酬のサンプル数が相対的に増えた(あるいは、より小さな生涯報酬のサンプル数が相対的に減った)のと同様です。また、状態価値が小さくなるように調節されるのは、より小さな生涯報酬のサンプル数が相対的に増えた(あるいは、より大きな生涯報酬のサンプルが減った)のと同様になります。
ターゲットポリシーが使うための行動価値関数の予測も挙動ポリシーとターゲットポリシーによる確率比を使うことで計算できます。
最後に注意点として、仮にだったとしても、ならば、からへの状態遷移はサンプルから除外する必要があります。

なぜならターゲットポリシーは状態において行動を選択する確率が0なので、上記の状態遷移全体の確率が0になってしまうからです。
この場合は状態で行動を選んで状態へ遷移したサンプルを無視して、状態からのサンプルだけを使用します。つまり、挙動ポリシーが集めたサンプルによる生涯報酬の計算ではターゲットポリシーにとって起こり得ない状態、行動、状態遷移の組み合わせが含まれないようにする必要があります。
以上まとめると、モンテカルロ法におけるイプシロン・グリーディはそのままオンポリシーとしても使えるし、オフポリシーの挙動ポリシーにもなります。
次回は、モンテカルロ法を実装して凍った湖の環境で実験します。
(続く)