前回はモンテカルロ法の概要について解説しました。今回は、実際の環境で開始点探索ができない場合にどのように対処するかについてお話しします。
開始点探索を必要とした理由は、エージェントがあらゆる状態であらゆる行動を何度も選択することでサンプルから計算した平均値による状態価値や行動価値の予測が真の期待値に収束するからでした。
何度もサイコロを振れば各数字が平均6分の1で出現するのと同じ考え方です。これによって、状態遷移の確率分布を与えられなくても、状態価値関数や行動価値関数を推定することができます。
ただし、現実的には開始点探索を行うのが困難な場合があります。
例えば、凍った湖の環境ではスタート地点から移動してゴールを目指すのでランダムな状態を初期値として選ぶことができません。よって開始点探索は不可能です。
凍った湖の環境このような場合には、開始点探索を必要としない方法でモンテカルロ法の適用を実現できるようにする必要があります。
そのための手法としてイプシロン・グリーディ法を紹介します。イプシロン・グリーディ法は仕組みとしては簡単なので理解しやすくすんなりと受けることができるでしょう。この記事ではさらに踏み込んで、なぜイプシロン・グリーディ法がより一般的なソフトポリシーより優れているのかを証明するところまで解説します。
まずは、ソフトポリシーが何者なのかについての解説から始めます。
ソフトポリシーとは
あらゆる状態であらゆる行動を選択するためには、すべての状態s∈Sで可能なすべての行動a∈A(s)に対してポリシーが正の確率を持つことが必要となります。
π(a∣s)>0
このようなポリシーをソフトポリシーと呼びます。ソフトという言葉は「曖昧さ」のニュアンスがあります。つまり、一つの決断に絞るのではなく、判断を確率的に分散されたものとして表現します。ディープラーニングでソフトマックスと言うと一番確率の高いものを選ぶことを指しますが、ここでも「ソフト」という言葉が使われています。
あらゆる状態であらゆる行動を選択する可能性があるソフトポリシーは探索を実行するために必要です。ただし、最終的には決定論的なポリシーへと移行する必要があります。さもないと、いつまでもランダムな行動選択が無くならないので最適なポリシーとは言えないからです。
もちろん、決定論的なポリシーであっても、結果としてランダムな行動が生じることはあります。例えば、凍った湖の環境で slippery=True の時は選択した行動と実際に起きる行動が異なる可能性があります。
そのような場合でも、最適なポリシーは与えられた状態において確率的に期待される価値が一番高い行動を選択します。つまり、ある状態からの行動選択は決定論的に行われます。
まとめると、ソフトポリシーは各状態において確率分布に基づいて行動を選択することで探索をします。一方、最適なポリシーは状態から判断して決定論的に(固定されたルールまたは関数に基づいて)単一のアクションを選択します。
そして、この両方のポリシーをうまく使い分ける方法が必要になります。
イプシロン・グリーディ
イプシロン・グリーディは、探索(exploration)と搾取(exploitation)のバランスを取るために使用されます。
イプシロン(ϵ)はランダムな行動を選ぶかどうかを決める確率です。0から1の値の乱数を生成して、それがイプシロンの値以下ならばランダムな行動を選択します。
仮にϵ=0.3ならば30%の確率でランダムな行動を選択します。そして、残り70%(1−ϵ=0.7)の確率で行動価値関数(Q値)が一番高い行動を選びます。
この手法では各行動が選ばれる確率は、ϵを可能な行動の数で割った値になります。
∣A(s)∣ϵ
ここで、∣A(s)∣はある状態sにおける可能な行動の数を意味します。可能な行動の数だけ1を足し合わせたものと定義できるので∣A(s)∣=a∑1と表現できます。
例えば、イプシロンがϵ=0.3で、なおかつ5個の行動が可能であるならば、一つの行動に対して0.3/5=0.06となり6%の確率で各行動がランダムに選ばれます。
さらに、Q値が一番高い行動に関しては1−ϵの確率でも選ばれるので、Q値が一番高い行動が選ばれる確率は以下になります。
1−ϵ+∣A(s)∣ϵ
よって、ϵ=0.3だと1−ϵ+∣A(s)∣ϵ=0.7+0.06なので76%の確率でQ値が一番高い行動が選ばれることになります。
ϵ>0であるならば、イプシロン・グリーディによるポリシーはソフトポリシーです。なぜなら、すべての行動に対して正の確率が付与されておりπ(a∣s)>0になるからです。
また、ϵを徐々に小さくすることで探索を減らして決定論的なポリシーに移行することができます。ϵを減らす速度を調節することで十分な探索ができれば、たくさんのサンプルを習得できるので予測される行動価値関数が信頼できるものになります。よって、最終的にϵがゼロになった時にポリシーは最適化されたものになります。
つまり、イプシロン・グリーディな探索をするソフトポリシーと搾取する決定論的なポリシーのバランスをとるのに有効なポリシーです。
イプシロン・ソフト
ソフトポリシーにもさまざまな確率の割り当て方が考えられるはずです。なぜイプシロン・グリーディが特に有効なのでしょうか。
実は、イプシロン・グリーディの利点は最大のQ値を与える行動を選ぶ、つまりは搾取をより積極的に取り入れるところにあります。
その証明をするために、まずイプシロン・ソフトというポリシーを考えます。これは各行動が最低限∣A(s)∣ϵの確率かそれ以上で選ばれるものです。
π(s∣a)≥ ∣A(s)∣ϵ
このポリシーもϵが0より大きければソフトポリシーです。
なお、イプシロン・ソフトでは最低限の確率は保証されていますが、どの行動に対して最大の確率を与えるのかは定められていません。つまり、イプシロン・ソフトはイプシロン・グリーディよりもより制限の緩いポリシーだと言えます。
逆に言うとイプシロン・グリーディはイプシロン・ソフトでもあります。ただし、イプシロン・グリーディはQ値が最高になる行動に最大の確率を与えるのでイプシロン・ソフトよりも搾取をするようにしたものだと言えます。
なぜイプシロン・グリーディなのか
イプシロン・グリーディがより一般的なイプシロン・ソフトよりも最適であることを次のように数式で証明することができます。
まず、イプシロン・ソフトπによる行動価値関数をqπ(s,a)と呼びます。このポリシーπに従った場合、ある状態sにおける状態価値は次のように表現できます。
vπ(s)=a∑π(a∣s)qπ(s,a)
これはある状態sでイプシロン・ソフトπ(a∣s)が与える行動選択の確率による行動価値の期待値を計算しています。
また、イプシロン・ソフトでは確率がゼロでないことを次のように確率の最低値を設定しています。ここではもちろんϵ>0を想定しています。
π(s∣a)≥ ∣A(s)∣ϵ
さらに、π(a∣s)は以下のように最低値とその上積み部分に分解して捉えることができます。
π(s∣a)= ∣A(s)∣ϵ+(π(s∣a)−∣A(s)∣ϵ)
なお、上式に対してすべての行動における総和を計算すると1になります。
a∑ π(s∣a)=1
これは確率の総和が100%になるだけなので当然ですが、上式の右辺に注目してください。第二項が以下のように1−ϵになります。
a∑π(s∣a) = a∑ ∣A(s)∣ϵ+a∑(π(s∣a)−∣A(s)∣ϵ) = ϵ+(1−ϵ)
つまり、以下が成り立ちます。
a∑(π(s∣a)−∣A(s)∣ϵ)=1−ϵ
これによってイプシロン・ソフトがϵの確率でランダムな行動選択を行い、1−ϵの確率で上積み部分の確率で行動を選択すると解釈することができます。これがエプシロン・グリーディとの大きな違いです。エプシロン・グリーディは1−ϵの確率でQ値が最大になる行動だけを選びます。
なお、ここでϵ=1(100%でランダムに行動を選択するわけではない)とすれば両辺を1−ϵで割ることができます。
a∑1−ϵ1(π(s∣a)−∣A(s)∣ϵ)=1
この意味は1−ϵ1(π(s∣a)−∣A(s)∣ϵ)を確率として捉えることができると言うことです。なぜなら、それは0以上で総和が1だからです。
このことを覚えておいてください。すぐ後で登場します。
さて、π(s∣a)の式をイプシロン・ソフトの状態価値関数に当てはめると次のようになります。
vπ(s)=a∑π(a∣s)qπ(s,a)=a∑(∣A(s)∣ϵ+(π(s∣a)−∣A(s)∣ϵ))qπ(s,a)=∣A(s)∣ϵa∑qπ(s,a)+a∑(π(s∣a)−∣A(s)∣ϵ)qπ(s,a)
よってエプシロン・ソフトによる状態価値関数は次のようになります。
vπ(s)= ∣A(s)∣ϵa∑qπ(s,a)+ a∑(π(s∣a)−∣A(s)∣ϵ)qπ(s,a)
さらに、この式を次のように書き換えます。
vπ(s)= ∣A(s)∣ϵa∑qπ(s,a)+ (1−ϵ) a∑(1−ϵπ(s∣a)−∣A(s)∣ϵ)qπ(s,a)
このようにすると第二項はqπ(s,a)の期待値を1−ϵ1(π(s∣a)−∣A(s)∣ϵ)という確率を使って計算したものに1−ϵをかけていることになります。
なぜこんな面倒な変形をしているのかというと、エプシロン・グリーディを使った状態価値関数の計算式との比較が簡単になるからです。
では、次に行動価値関数をqπ(s,a)に固定したまま、ポリシーをイプシロン・グリーディπ′に置き換えます。これによってポリシーが改善されるのであればイプシロン・グリーディがイプシロン・ソフトよりもより最適であることが証明できます。
そのためにイプシロン・グリーディπ′の評価を行います。行動価値関数をqπ(s,a)に固定したまま、ポリシーをイプシロン・グリーディπ′に置き換えて状態価値関数vπ′(s)を計算します。
vπ′(s)=a∑π′(a∣s)qπ(s,a)
ここでπ′は∣A(s)∣ϵの確率でランダムな行動を選び、(1−ϵ)の確率で最大のQ値を持つ行動を選ぶので次のように展開できます。
vπ′(s)=a∑π′(a∣s)qπ(s,a)= ∣A(s)∣ϵa∑qπ(s,a)+(1−ϵ)amaxqπ(s,a)
このvπ′(s)が常にvπ(s)以上であることが次の関係を使って証明できます。
vπ′(s)=∣A(s)∣ϵa∑qπ(s,a)+(1−ϵ)amaxqπ(s,a)≥∣A(s)∣ϵa∑qπ(s,a)+(1−ϵ)a∑1−ϵ1(π(s∣a)−∣A(s)∣ϵ)qπ(s,a)
この不等式が成り立つのはqπ(s,a)の最大値は、どのような確率を使って計算したqπ(s,a)の期待値と等しいかそれより大きくなるからです。
最後の式はvπ(s)に置き換えれるので次が成り立ちます。
vπ′(s)≥vπ(s)
つまり、イプシロン・グリーディに従う行動選択をすることでポリシーが改善されイプシロン・ソフトによる状態価値関数以上の値を常に与えることが証明されました。
そしてその理由はイプシロン・グリーディがイプシロン・ソフト以上に搾取を行うからです。
まとめると、イプシロン・グリーディはより一般的なイプシロン・ソフトよりも優れたポリシーです。また、また単純であり直感的なので、よく使われる手法になっています。
なお、イプシロン・グリーディを使う方法にはオンポリシーとオフポリシーの二つがあります。次回に解説します。
(続く)