【苦しみながら理解するReinforcement Learning】第5章 モンテカルロ法

モンテカルロ法は経験(experience)のみを必要とする(環境の完全な知識を仮定しない)。
この経験というのは、状態系列のサンプル、行動、そしてオンラインあるいはシミュレーションに基づく環境との相互作用からの報酬のことである。

経験はエピソード群に分解され、どのような行動が選択されようと全てのエピソードはやがて終了すると仮定する。

最初に方策評価(固定された任意の方策πに対してV^πとQ^πを計算)、その次に方策改善、そして最後に一般化方策反復を考える。
DPから取り入れられたこれらの考え方は、経験のサンプルのみが利用可能なモンテカルロ法の場合に対して拡張される。

モンテカルロ法による方策評価

経験から収益を見積もる方法は、その状態を訪れた後に観測された収益を単に平均化することである。

エピソード中において状態sが発生したなら、その各々をsへの訪問(visit)と呼ぶ。
逐一訪問MC法(every-visit MC method)は、エピソード群への集合において、sへの訪問全ての結果発生した収益の平均値としてV^π(s)を推定する。
初回訪問MC法は、sへの初回の訪問(first visit)の結果発生した収益を平均するだけである。

first visit

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

モデルを利用することが出来ないならば、状態の価値よりも行動の価値を推定した方が有用である。
モデルがあるなら、状態価値だけで方策を決定するのに十分である。

モデルがないなら価値が方策の示唆に有用であるため、各硬度王の価値を明示的に評価する必要がある。
モンテカルロ法の主たる目的はQ*を見積もることである。

逐一訪問MC法は、状態行動対の価値を、その行動がとられた状態への訪問の結果発生した収益の平均値として推定する。
初回訪問MC法は、各エピソードにおいてその状態が訪問され、行動が選択された初回の後に発生した収益を平均化する。

問題は、多くの関連する状態行動対が全く訪問されないだろうということ。
方策評価が行動価値に対して機能するためには、探索が継続されることを保証する必要がある。

これを実現する1つの方法として、各エピソードの最初のステップが状態行動対から始まること、そしてそのような状態行動対のあらゆるものが開始点として選ばれる確率がゼロではないこと、を指定することである。
これを開始点探索(explooring starts)と呼ぶ。

モンテカルロ法による制御

モンテカルロ法による推定が、制御においてどのように使われるのか?
DPと同じく一般化方策反復(GPI)に従う。

モンテカルロ法での収束の保証を容易に得るために、非現実的な仮定を2つ行った。

  1. エピソードの開始点探査を仮定する
  2. 方策評価を無限個のエピソード群に関して行えること

1. エピソードの開始点探査を仮定するは章の最後に考える。
まずは2. 方策評価を無限個のエピソード群に関して行えることについて。

解決する方法は2通りある。
1つ目は、各方策評価においてQ^πkを近似する考え方に固執すること。
推定における評価誤差の大きさと確率の範囲を得るために測定と仮定を行い、それらの値が十分に小さいことを保証するための各方策評価に十分なステップ数を費やす。

2つ目は、方策改善に戻る前に方策評価を完了させるのを見合わせること(完了させない)。
各評価ステップにおいて価値関数をQ^πkに向けて操作するが、実際に近づくことは期待しない。

実際の利用例として、開始点探査を行うモンテカルロ法であるモンテカルロES法(MonteCarlo ES)が挙げられる。
各状態行動対に対する全ての収益が(観測時にどのような方策の効力があったかには無関係に)累積され平均化される。
モンテカルロES法がどのよおうおな準最適方策にも収束できないことは容易に示せる。

es

方策オン型モンテカルロ法による制御

全ての行動が何度も選択されることを保証する一般的な方法はただ1つ、エージェントにそれらを選び続けさせることである。
これを保証するアプローチは2つある。
* 方策オン型(on-policy)手法
* 方策オフ型(off-policy)手法

方策オン型手法は、意思決定を行うために使われる方策の評価、改善が試みられる。
ここで示される方策オン型手法は、eグリーディ手法(e-greedy)を用いている。(eグリーディ手法は前に出てきましたよね!)
eグリーディ方策は、eソフト方策(e-soft)の例であり、以下のような方策であると定義される。

$$ \pi (s, a) ≧ \frac{e}{|A(s)|} $$

eソフト方策群のなかでの最良方策が達成されれば、開始点探査の仮定(1. エピソードの開始点探査を仮定する)は取り除かれる。

eソフト方策

他の方策に追従する方策評価

これまでのところ、無限このエピソード群が与えられたとして、ある方策の価値観数を推定する方法を考えてきた。
(エピソード群はこの方策によって生成される。)
ここで、エピソード群が異なる方策によって生成されたと仮定しよう。

方策から分離されたけいけんのみが与えられていても方策の価値関数を学習することはできる。
π’から得られたエピソード群をπの価値推定のために使うためには、πのもとで取られたあらゆる行動が、少なくともπ’のもとで、ときおり取られることが要求される。

pi(s)とpi'(s)がその完全な系列が起こる確率を示すものとする。
これらでpi(s)/pi'(s)のようにして重み付けすれば良い。

方策オフ型モンテカルロ法による制御

方策オン型手法では、方策を制御に用い、方策の価値を推定していた。
方策オフ型手法では、これらの機能が分離され、挙動を生成するために使われる挙動方策(behavior policy)と呼ばれる方策と、評価され改善される推定方策(estimation policy)と呼ばれる方策と関連付けられていない。

分離する利点としては、挙動方策が全ての行動をサンプリングし続ける場合でも、推定方策として決定論的なもの(グリーディなど)を用いることができるという点。
また、すべての可能性を探索するために、挙動方策はソフト方策でなければならない。

漸進的実装

n本腕のバンデットの問題を解くのと同じようにエピソード単位にモンテカルロ法を漸進的に実装することができる。

モンテカルロ法とバンディットで異なる点が2つある。
* モンテカルロ法の場合、典型的には複数の状況、つまり各状態に対して異なる平均化の仮定があるということ。
* モンテカルロ法では収益の分布は典型的には非定常であること。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です