メインコンテンツへスキップ
見出し画像

Gymで強化学習⑫モンテカルロ法:前編

    前回は動的計画法を実際にコーディングしました。今回はモンテカルロ法の理論(前編)を解説します。

    まず、簡単に動的計画法の理論をおさらいします。その次にモンテカルロ法の理論を導入することで動的計画法との違いを明確にします。

    あらかじめネタバレしてしまいますが、主な違いは次のようになります。動的計画法では環境のモデルを使って状態価値関数と最適ポリシーを計算しますが、モンテカルロ法は環境との相互作用から得た経験を使って行動価値関数と最適ポリシーを予測します。

    では、さっそく始めましょう。

    動的計画法のおさらい

    動的計画法では環境に関してのモデルが与えられている場合にブートストラッピングを使ってポリシーの評価とポリシーの改善を交互に行いました。

    ポリシーの評価とは現在のポリシーを固定して各状態の価値を計算することでこのポリシーによる状態価値関数を更新することです。

    vπ(s)=∑s′,rp(s′,r∣s,π(s))[r+γvπ(s′)]v_\pi(s) = \sum\limits_{s', r} p(s', r | s, \pi(s)) [r + \gamma v_\pi(s')]

    状態価値関数がより正確になるためには、ポリシーが改善される必要があります。

    ポリシーの改善は状態価値関数を固定して各状態における最善な行動を選択するようにポリシーを更新します。

    π(s)←arg⁡max⁡a∑s′,rp(s′,r∣s,a)[r+γv(s′)]\pi(s) \leftarrow \arg\max\limits_a \sum\limits_{s', r} p(s', r | s, a) [ r + \gamma v(s')]

    ここで最善な行動とは、ある状態から最も価値のある状態へと遷移することを指します。よって状態価値関数がより正確であるほどポリシーの行動選択がより最適となります。

    このようにポリシーの評価(ポリシーを固定して状態価値関数を更新)とポリシーの改善(状態価値関数を固定してポリシーを更新)は互いに関連し合っています。交互に更新を繰り返すことで状態価値関数とポリシーの両方が徐々に最適化されます。これをポリシー反復法と呼びました。

    また、ポリシーの評価と改善を一つに組み合わせた価値反復法では最新の状態価値関数に基づいて価値が一番大きい状態へ移るように行動選択を行うとした上で状態価値関数を更新します。

    v(s)←max⁡a∑s′,rp(s′,r∣s,a)[r+γv(s′)]v(s) \leftarrow \max\limits_a \sum\limits_{s', r} p(s', r | s, a) [ r + \gamma v(s') ]

    最終的に収束した状態価値関数に従って最適な行動選択することが最適なポリシーになります。

    π∗(s)=arg⁡max⁡a∑s′,rp(s′,r∣s,a)[r+γV∗(s′)]\pi_*(s) = \arg\max\limits_a \sum\limits_{s', r} p(s', r | s, a) [ r + \gamma V_*(s')]

    ポリシー反復法あるいは価値反復法では、全ての状態に対して何度も繰り返し計算を行います。上記の4つの式から分かるように、どちらの反復法でも環境における状態遷移の確率を必要とします。

    しかし、モンテカルロ法では状態遷移の確率を必要としません。

    モンテカルロ法による状態価値

    まずはモンテカルロ法による状態価値の予測について解説します。

    モンテカルロ法は環境との相互作用(行動して状態が変わり報酬を受けるなど)による経験を使って状態価値を予測します。

    ポリシーπ\piによる状態価値とはある状態st=ss_t = sから受けられる生涯報酬の期待値です。

    vπ(s)=E[gt​∣st=s] v_\pi(s) = E[ g_t​ | {s_t = s} ]  

    状態sts_tで報酬rtr_tを受け取り、γ\gammaを割引率とすると生涯報酬gtg_tは次のように定義されます。

    gt=rt+γrt+1+ γ2rt+2+…g_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + …

    これはあくまでもあるエピソードにおける、あるステップからの生涯報酬です。ポリシーの行動選択や状態遷移の確率によって各状態からの生涯報酬がエピソードごとに異なる値になる可能性があります。

    期待値を計算するには状態遷移の確率が必要ですが、モンテカルロ法では状態遷移の確率を知らないことを前提としています。その代わりに、たくさんのエピソードから得た状態遷移のサンプルを使って、各状態からの生涯報酬を計算します。たくさんのエピソードから得た生涯報酬のサンプルの平均値をとることで各状態における価値を予測します。

    具体例で見ていきましょう。

    エピソードを行うとマルコフ行動過程における一連の状態、行動、報酬の値をサンプルとして得ることができます。

    例えば、あるエピソードが下図のように展開したとします。

    画像
    エピソードでの経験

    なお、この例での環境は slippery=False としています。よって選んだ方向へ100%の確率で移動します(もちろん、グリッドの外には出れませんが)。

    そこで、上記のエピソードからの経験、つまり各ステップにおける状態、行動、報酬は以下になります。

    ステップ1:(状態s1= 0 s_1=\ 0\ 、行動a1=1a_1=1、報酬r1=0r_1=0)
    ステップ2:(状態s2= 4 s_2=\ 4\ 、行動a2=1a_2=1、報酬r2=0r_2=0)
    ステップ3:(状態s3= 8 s_3=\ 8\ 、行動a3=2a_3=2、報酬r3=0r_3=0)
    ステップ4:(状態s4= 9 s_4=\ 9\ 、行動a4=1a_4=1、報酬r4=0r_4=0)
    ステップ5:(状態s5=13s_5=13、行動a5=2a_5=2、報酬r5=0r_5=0)
    ステップ6:(状態s6=14s_6=14、行動a6=2a_6=2、報酬r6=1r_6=1)

    状態14で行動2を選択すると状態15はゴールなので terminated=True となって終了です。その際に報酬1を受け取ります。

    このようにして得た経験を使って各状態における生涯報酬を計算します。これが各状態における生涯報酬の1つのサンプルとなります。このようなサンプルをたくさん集めて平均を計算すれば各状態において期待される生涯報酬、つまりは価値が予測できるわけです。

    仮に、slippery=True の場合でも同様です。エージェントは状態遷移の確率を知らないのですが、たくさんの経験を通して集めた生涯報酬のサンプルの平均を計算することで期待値を予測できます。たくさんの経験があるほど予測の精度が上がります。

    では、上記のエピソードを使って具体的に各状態における生涯報酬を計算しましょう。

    まずステップ1では状態は0です。その状態0の生涯報酬は次になります。

    g1=r1+γ r2+γ2 r3+γ3r4+γ4r4+γ5r6g_1 = r_1 + \gamma \, r_2 + \gamma^2 \, r_3 + \gamma^3 r_4 + \gamma^4 r_4 + \gamma^5 r_6

    ステップ2、状態4の価値は次になります。

    g2=r2+γ r3+γ2r4+γ3r4+γ4r6g_2 = r_2 + \gamma \, r_3 + \gamma^2 r_4 + \gamma^3 r_4 + \gamma^4 r_6

    しかし、このようにステップ1から計算していくと何度も重複した計算を行うことになります。よって次のようにg1g_1をr1r_1とg2g_2を使って計算することを考えます。

    g1=r1+γ r2+γ2 r3+γ3r4+γ4r4+γ5r6=r1+γ (r2+γ r3+γ2r4+γ3r4+γ4r6)=r1+γ g2\begin{aligned} g_1 &= r_1 + \gamma \, r_2 + \gamma^2 \, r_3 + \gamma^3 r_4 + \gamma^4 r_4 + \gamma^5 r_6 \\ &= r_1 + \gamma \, ( r_2 + \gamma \, r_3 + \gamma^2 r_4 + \gamma^3 r_4 + \gamma^4 r_6 ) \\ &= r_1 + \gamma \, g_2 \end{aligned}

    つまり、ステップ2を先に計算しておけばステップ1の計算は簡単になります。よって、最後のステップから逆方向に計算していきましょう。

    ステップ6では状態14で右に移動し報酬1を得ました。つまり、ステップ6の価値は1です。

    g6=1g_6 = 1

    ステップ5からの生涯報酬は割引率を0.9とすると以下になります。

    g5=r5+γ g6    =0+0.9∗1.0    =0.9\begin{aligned} g_5 &= r_5 + \gamma \, g_6 \\         &= 0 + 0.9 * 1.0 \\         &= 0.9 \end{aligned}

    ステップ4では生涯報酬は以下になります。

    g4=r4+γ g5    =0+0.9∗0.9    =0.81\begin{aligned} g_4 &= r_4 + \gamma \, g_5 \\         &= 0 + 0.9 * 0.9 \\         & = 0.81 \end{aligned}

    このように、最後のステップから計算することですでに計算された値を利用することができます。このやり方は実装の時にも使います。

    以上、一つのエピソードにおける各状態での生涯報酬を計算しました。たくさんのエピソードを行えば、各状態での生涯報酬のサンプル値をたくさん集めることができます。そして各状態での生涯報酬の平均値を計算したものが状態価値の予測値となります。

    なお、slippery=True でも各状態の価値予測の方法は同じです。その場合には、指定した行動通りに状態が移らなかったりするわけですが、たくさんのエピソードを通して得たサンプルでさまざまな状態遷移として反映されるので平均値を計算する方法に変わりはありません。

    なぜなら、ある状態ssで同じ行動aaを取っても移動した先の状態や得られる報酬が異なったりするのですが、たくさんのサンプルを平均をすることで予測値が真の状態遷移の確率を使った期待値に近づくからです。

    モンテカルロ法の特徴

    モンテカルロ法ではエピソードが終了して初めて生涯報酬の計算ができることになります。つまり、エピソードが有限である必要があります。また、エピソードが有限であることをエピソディック(Epsodic)と呼びます。モンテカルロ法が扱う環境はエピソディックでなければなりません。

    エピソードが終わるまでは平均値を計算できず経験から学ぶことができません。このことはモンテカルロ法ではエピソードが終わった時点でポリシーの更新が行われることを意味します。

    動的計画法では最初のエピソードがはじまる以前にポリシーの最適化が終了していました。それが可能なのは状態遷移の確率を完全に把握しているからです。モンテカルロ法では経験から学ぶ必要があるのでポリシーをあらかじめ最適化することはできません。エピソードごとにポリシーを改善していく必要があります。

    また、SARSAやQ学習のようにエピソード内での経験をすぐにポリシーの改善に利用することもできません。

    なお、モンテカルロ法ではブートストラッピングを行いません。各状態における生涯報酬の予測は実際の経験から得たサンプルの平均であり、ブートストラッピングのように状態価値の予測に以前の状態価値の予測を使うことはありません。つまり、状態価値関数を何らかの値で初期化してから予測に予測を重ねていくようなことは行いません。

    同じ状態を訪れた際の対処

    以下の図では同じ状態が繰り返されるループが生じています。

    画像
    同じ状態が繰り返される

    状態が次のように移り変わっています。

    0→4→8→9→13→14→10→9→13→14→15

    よってエージェントは状態9、13、14を各2回ずつ訪れています。場合によってはこのようなループや行ったり来たりが何度も繰り返される可能性もあります。

    モンテカルロ法では同じ状態が繰り返される際の対処法が二つあります。

    初回訪問モンテカルロ法(First-visit Monte Carlo Method)ではある状態を初めて訪問(First-visit)したステップからの生涯報酬を計算してその状態における生涯報酬のサンプルとします。それ以降に同じ状態を訪れてもその状態に対するサンプルにしません。

    この理由は、たくさんのサンプルから平均を計算する時に各々のサンプルは独立であることを前提としているからです。

    例えば、状態9からの状態の移り変わりを見ていくと以下の二つがあります。

    0→4→8→9→13→14→10→9→13→14→15
    0→4→8→9→13→14→10→9→13→14→15

    ここで、9→13→14→10→9→13→14→15と9→13→14→15はお互いに関係があります。なぜなら後者は前者の一部だからです。つまり、サンプル間に相関があることになります。

    よってこの二つをサンプルとして含めてしまうと状態9に対して重複した情報を含めることになり、単純な平均ではなく不公平な平均の計算になってしまいます。

    このことを統計ではバイアスがあると言います。バイアスとは先入観とか偏見などの意味があります。よって初回訪問モンテカルロではバイアスを避けるという動機があります。しかし、ある状態への訪問が初回であるかどうかチェックが必要となります。

    逐一訪問モンテカルロ法(Every-visit Monte Carlo Method)では同じ状態を訪れる度(Every-visit)にその状態からの生涯報酬をサンプルとして加えます。このやり方ではバイアスがある代わりに初回訪問のチェックが不要になります。また、各エピソードからのサンプルの数が多くなるので場合によっては最適なポリシーへの収束が速くなる可能性があります。

    どちらの手法もたくさんのエピソードを行うことで収束することが知られています。

    モンテカルロ法による行動価値

    これまでモンテカルロ法による状態価値の予測について解説しました。何らかのエージェントが環境との相互作用を通してマルコフ決定過程のエピソードを生成し各状態における生涯報酬のサンプルを集めます。この平均値を計算することで各状態における価値を予測しました。ここでいくつか疑問が湧きます。

    まず、何らかのエージェントとはどのようなものなのか。そして、状態価値関数の予測だけでどのように行動選択を行うのかという疑問です。

    何らかのエージェントとは、環境におけるあらゆる状態であらゆる行動を行うものを想定しています。このようなエージェントはあらゆる状態でランダムな行動を選択するようなものが考えられます。

    しかし、凍った湖の環境では、ランダムな行動だけだとあらゆる状態であらゆる行動を試すどころか途中で穴に落ちてばかりでなかなかゴール付近に近づくこともできません。

    もちろん無限にエピソードを行えばいつかはすべての状態と行動から十分なサンプルを得ることはできますが、時間がかかり過ぎる可能性があります。この点についてはさらに後述します。

    もう一つの問題は「状態価値関数の予測だけでどのように行動選択を行うのか」です。状態遷移の確率がないと「ある状態でどの行動を選ぶとどの状態へ遷移するのかが分からない」ので行動の選択ができません。

    slippery=False ならば右を選択すれば右へ行くと分かりますが、slippery=True だと3分の1の確率で右、上、下へ移動するわけです。このような状態遷移の確率を知らないでどの行動を選ぶべきかは決められないわけです。

    前回の実装でも動的計画法で最適化されたポリシーでは slippery=True の環境で穴に落ちないために行きたい状態へ直接向かう行動を取らない様子が観測されました。

    このためモンテカルロ法で行動選択するためには状態価値関数ではなく行動価値関数の予測を行う必要があります。正確な行動価値関数があるならば、最適なポリシーとは、あらゆる状態で行動価値を最大にする行動を選択することとなります。

    π(s)≐arg⁡max⁡aqπ(s,a)\pi(s) \doteq \arg\max\limits_{a} q_\pi(s, a)

    ≐\doteqはポリシーπ(s)\pi(s)を右辺のように定義すると言う意味です。

    しかし、初期の行動価値関数の予測は正確ではありません。よってモンテカルロ法ではたくさんの状態と行動の組み合わせのサンプルを集めていく必要があります。

    つまり、ある状態である行動を取った時に得た生涯報酬をサンプルとして集めて、その平均を行動価値の予測値とします。

    たくさんのサンプルを集めることで行動価値関数がより正確になれば、その行動価値関数を使ったポリシーはより最適になります。つまりサンプルを集めることでポリシーを改善することができるわけです。

    ポリシーの改善は、現在の行動価値関数qπkq_{\pi_{k}}を使って次のように表現できます。

    ππk+1=arg⁡max⁡aqπk(s,a)\pi_{\pi_{k+1}} = \arg\max\limits_a q_{\pi_k}(s, a)

    これによって更新されたポリシーは現在の行動価値関数qπkq_{\pi_{k}}による最適なものです。この改善されたポリシーによる行動価値は次のように計算できます。

    qπk(s,πk+1(s))= qπk(s,arg⁡max⁡aqπk(s,a))=max⁡aqπk(s,a)\begin{aligned} q_{\pi_k}(s, \pi_{k+1}(s)) &= q_{\pi_k}(s, \arg\max\limits_a q_{\pi_k} (s, a)) \\ &= \max\limits_a q_{\pi_k} (s, a) \end{aligned}

    つまり、現在の行動価値関数で予測できる最適なポリシーは行動価値を最大にする行動を選ぶものになります。

    よって、改善されたポリシーによる行動価値は以前のポリシーによる行動価値と同等かそれ以上になります。

    qπk(s,πk+1(s))≥qπk(s,πk(s))\begin{aligned} q_{\pi_k}(s, \pi_{k+1}(s)) &\ge q_{\pi_k}(s, \pi_k(s)) \end{aligned}

    よって動的計画法が状態価値関数とポリシーの更新をしたように、モンテカルロ法では行動価値関数を改善し続けることで最適なポリシーにいつかは到達することが理論的に示されたわけです。

    これによってモンテカルロ法は環境のモデル(状態遷移の確率)が無くとも、サンプルから最適ポリシーを見つけられることになります。言い換えると、行動価値関数の予測があらゆる状態と行動の組み合わせに対して正確にできるのであれば状態遷移の確率を与えられる必要はありません。

    開始点探索モンテカルロのポリシー反復

    これまでの議論で、モンテカルロ法では何らかのポリシーを使ってさまざまな状態と行動を探索する必要があるのが明確になりました。あらゆる状態と行動の組み合わせを何度も訪れることでサンプルの平均値がより正確になります。

    しかし、どのようにしてあらゆる状態と行動の組み合わせを探索するのでしょうか。

    ここでは、思考実験としてエピソードを開始する状態と行動をランダムに選択できると仮定します。

    例えば、いきなり状態10で行動3(上)を行うことからエピソードを始めることができるとします。

    画像
    エピソード開始時点の状態と行動をランダムに選択

    実際の環境ではそんなことはできませんが、ここではそれが可能だとします。

    このため毎回のエピソードでランダムな状態と行動から開始します。そうして得られた経験からのサンプルを使ってポリシーの評価と改善を行うわけです。開始点を探索することになるので開始点探索(Exploring Starts)のモンテカルロ法と呼びます。

    ランダムに選ばれた状態と行動で開始して、現在のポリシーによる行動をエピソードが終了するまで行います。これを繰り返せば、あらゆる状態であらゆる行動を選択することができることになります。

    ポリシーの評価と改善はエピソードの終了後に行います。訪れた状態と行動の組み合わせに関して行動価値関数が更新されポリシーが改善されます。

    また、ポリシーの改善では常に更新されたポリシーが以前のポリシー以上になることは証明されているので、無数のエピソードを行うことができればやがてはポリシーが最適化されることが期待されます。

    なぜならばたくさんのサンプルが集まることで平均値が安定化するので行動価値関数も収束し最適なポリシーも収束するからです。もちろん環境における状態遷移の確率分布が毎回変化するようなことがないことが前提ですが。

    しかし、実際の環境で開始点探索が可能でないとしたらこの手法は使えません。また、無数のエピソードというのも引っ掛かります。

    次回はモンテカルロ法の理論(後編)の続きとして開始点探索なしで行う手法を解説します。

    (続く)




     
     
    「わかりやすく、具体的に」AIとサイエンスの情報を発信中

    あなたへのおすすめ