モンテカルロ法は経験(experience)
のみを必要とします(環境の完全な知識を仮定しない)。この経験というのは(状態系列のサンプル、行動、そしてオンラインあるいはシミュレーションに基づく環境との相互作用からの)報酬のことです。経験はエピソード群に分解され、どのような行動が選択されようと全てのエピソードはやがて終了すると仮定します。
最初に方策評価(固定された任意の方策πに対してV^πとQ^πを計算)、その次に方策改善、そして最後に一般化方策反復を考えていきます。DPから取り入れられたこれらの考え方は、経験のサンプルのみが利用可能なモンテカルロ法の場合に拡張されます。
モンテカルロ法による方策評価
経験から収益を見積もる方法は、その状態を訪れた後に観測された収益を単に平均化することです。エピソード中において状態sが発生したなら、それをsへの訪問(visit)と呼びます。逐一訪問MC法(every-visit MC method)
はエピソード群のsへの訪問全ての結果発生した収益の平均値としてV^π(s)を推定します。初回訪問MC法
はsへの初回の訪問(first visit)の結果発生した収益を平均するだけです。
モンテカルロ法による行動価値推定
モデルがあるなら、状態価値だけで方策を決定するのに十分です。モデルを利用することがない(出来ない)ならば、状態の価値よりも行動の価値を推定した方が有用です。モンテカルロ法の主たる目的はQ*(行動の価値)を見積もることです。
復習:
逐一訪問MC法は、状態行動対の価値をその行動がとられた状態への訪問の結果発生した収益の平均値として推定します。初回訪問MC法は、各エピソードにおいてその状態が訪問され、行動が選択された初回の後に発生した収益を平均化します。
強化学習を実施する上で多くの関連する状態行動対が全く訪問されないことが感がられ、これは問題と言えます。方策評価が行動価値に対して機能するためには、探索が継続されることを保証する必要があります。
これを実現する1つの方法として、各エピソードの最初のステップが状態行動対から始まること
、そしてそのような状態行動対のあらゆるものが開始点として選ばれる確率がゼロではないこと
、を指定すること方法があります。これを開始点探索
(explooring starts)と呼ぶ。
モンテカルロ法による制御
モンテカルロ法による推定が、制御においてどのように使われるのか?
DPと同じく一般化方策反復(GPI)に従います。
モンテカルロ法での収束の保証を容易に得るために、非現実的な仮定を2つ行います。
- 方策評価を無限個のエピソード群に関して行えること
- エピソードの開始点探査を仮定すること
まずは2. 方策評価を無限個のエピソード群に関して行えること
について。解決する方法は2通りあります。
1つ目は、各方策評価においてQ^πkを近似することです。推定における評価誤差の大きさと確率を得るために測定と仮定を行い、それらの値が十分に小さいことを保証するための(誤差があまりでないようにするための)各方策評価に十分なステップ数を実行します。
2つ目は、方策改善に戻る前に方策評価を完了させるのを完了させないこと。各評価ステップにおいて価値関数をQ^πkに向けて操作するが、実際に近づくことは期待しません。
実際の利用例として、開始点探査を行うモンテカルロ法であるモンテカルロES法
(MonteCarlo ES)が挙げます。各状態行動対に対する全ての収益が(観測時にどのような方策の効力があったかには無関係に
)累積され平均化されます。
方策オン型モンテカルロ法による制御
全ての行動が何度も選択されることを保証する一般的な方法はただ1つ、エージェントにそれらを選び続けさせることです。これを保証するアプローチは2つあります。
- 方策オン型(on-policy)手法
- 方策オフ型(off-policy)手法
方策オン型手法は意思決定を行うために使われる方策の評価、改善が行われます。ここで示される方策オン型手法は、eグリーディ手法(e-greedy)を用いています。(eグリーディ手法は前の章で出てきましたよね!)eグリーディ方策は、eソフト方策(e-soft)の例であり、以下のような方策であると定義されます。
$$ \pi (s, a) ≧ \frac{e}{|A(s)|} $$
eソフト方策群のなかでの最良方策が達成されれば、開始点探査の仮定(1. エピソードの開始点探査を仮定する
)は取り除かれます。
他の方策に追従する方策評価
これまでのところ、無限個のエピソード群が与えられたとして、ある方策の価値関数を推定する方法を考えてきました。(エピソード群はこの方策によって生成されます。)ここで、エピソード群が異なる方策によって生成されたと仮定してみましょう。
方策から分離された経験のみが与えられていても方策の価値関数を学習することはできます。π’から得られたエピソード群をπの価値推定のために使うためには、πのもとで取られたあらゆる行動が、少なくともπ’のもとで少しでも取られることが必要です。
方策オフ型モンテカルロ法による制御
方策オン型手法では方策を制御に用い、方策の価値を推定していました。方策オフ型手法ではこれらの機能が分離されます。挙動を生成するために使われる挙動方策(behavior policy)と呼ばれる方策と、評価され改善される推定方策(estimation policy)と呼ばれる方策に分離され、関連付けされていません。
分離する利点としては、挙動方策が全ての行動をサンプリングし続ける場合でも、推定方策として決定論的なもの(グリーディなど)を用いることができるという点です。また、すべての可能性を探索するために挙動方策はソフト方策でなければなりません。
漸進的実装
n本腕のバンデットの問題を解くのと同じようにエピソード単位にモンテカルロ法を漸進的に実装することができます。しかしモンテカルロ法とバンディットで異なる点が2つあります。
- モンテカルロ法の場合、典型的には複数の状況、つまり各状態に対して異なる平均化の仮定があるということ。
- モンテカルロ法では収益の分布は典型的には非定常であること。