More than 5 years have passed since last update.

Sutton本第5章モンテカルロ法まとめ

Last updated at 2019-07-30Posted at 2019-07-30

##前章で扱ったDPとの関係性

##MC法による方策評価
#####訪問MC法

状態の価値=その状態から開始した場合の期待収益
- 状態$s$を通過した全てのエピソードにおける収益の平均を取れば良さそう ➡︎ 訪問MC法
  - 逐一訪問MC法 : 各エピソードにおいて複数回sを訪問している場合その全てを加味する
  - 初回訪問MC法 : 各エピソードにおける初回のみ考慮する
初回訪問、逐一訪問共に大数の法則より(sへの訪問回数)→∞で$V^{\pi}(s)$に収束するらしい
ちなみに一つのエピソード(=対局)中に同じ状態が再び訪れることはないタスク(オセロとか)では初回訪問も逐一訪問も一緒

#####DPに対する強み

DPでは今見ている状態の価値を、その先にある状態の推定量から推定していた(ブートストラップ)
- つまり1つの状態の推定が他の状態に依存している
- 一部の状態についてだけ知りたいというときも他の不要なたくさんの状態も見る必要がある
MC法では各状態に対する推定は完全に独立である
- 1つの状態の価値推定にかかる計算量は状態数から独立
- 部分集合の価値だけを知りたい時に強力

##MC法による行動価値推定

環境についてのモデルがない場合、状態の価値だけでは方策は定まらない
- モデル = ある行動を行なった結果どの状態に遷移するかみたいなこと(？)
- 逆にモデルがある場合(行動1->状態A,行動2->状態B)状態の価値(状態A>状態B)のみによって方策(行動1を選ぼう)が得られる

#####じゃあどうすりゃいいの

基本は前節でやったことを(状態,行動)の対に対して行えば良い
- 前節では状態$s$を訪問したエピソード群の収益から$V^{\pi}(s)$を推定
- ここでは状態行動対$(s, a)$を訪問したエピソード群の収益から$Q^{\pi}(s, a)$を推定
ただし、方策$\pi$が決定論的である場合は全く訪問されない$(s,a)$が出てきてしまう
- ここで2章で扱った探査の考え方が出てくる

#####開始点探査

n本腕バンディットと似たようなはなし
任意の状態行動対についてそれが開始点として選ばれる確率がゼロにならないように定める
このもとでエピソード数無限大の極限をとれば全ての状態行動対が無限回行動されるという仮定(開始点探査の仮定)
- 一見当たり前に思えるが、環境との間での相互作用から学習を行う場合などは通用しないらしい(?)
シミュレーションでは開始点操作は可能だが、実際の経験から学習したいと思った時は通用しないという欠点がある
開始点探査の代替案として、単に方策$\pi$を非決定論的にすれば良いという説もある

##MC法による一般化方策反復

#####モンテカルロES

今までは方策評価が無限個のエピソードについて行われるという仮定でやってきた
- DPの時の1スイープしなきゃいけない仮定と似ている
これを取り払うには方策改善の前に方策評価を完全に完了させることを諦めれば良い
- 非同期DPと一緒
- 1エピソード見るたびに$Q$を更新して$\pi$も更新しちゃう

##方策オン型MC法

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

これまである一つの方策$\pi$で無限のエピソードを生成し、それによって$\pi$を方策評価していた
一般化方策反復を行うには現在の方策$\pi$とは別の方策$\pi'$によって生成された過去のエピソードも用いて$\pi$を方策評価できないか？（そうしないとサンプルが集まらない）
結論としては $\pi(s,a)>0\Rightarrow\pi'(s,a)>0$ がなりたてばよい
- つまり $\pi$ で取りうる全ての行動が $\pi'$ の時も出現すれば良い
- 前節のεソフト方策はこれを満たす
この時方策$\pi,\pi'$それぞれにおける状態$s$への$i$番目の初回訪問の生起確率を$p_i(s),p_i'(s)$とし、$\pi'$で生成された$s$への$i$番目の初回訪問を含むエピソードでの収益を$R_i(s)$とすれば、$\pi$の方策評価は$R_i(s)$を$p_i(s)/p_i'(s)$で重み付けした平均となる(p135(5.3)式)
- この時$p_i(s)/p_i'(s)$はp135の直後の式より環境のダイナミクスに依存しない形で計算が可能らしい

##方策オフ型MC法

オン型では制御(=探査?グリーディ?)が方策の中に組み込まれ、それを評価する形になっていた
オフ型では挙動方策と推定方策の二つに分離
- 挙動方策は挙動(=制御)を生成
- 推定方策は評価され改善される方策(今まで通りのやつ)
- 分離することで推定方策では決定論的な方策(例えばグリーディ)を探ることができる
ここでは挙動方策に従って生成されたエピソードを用いて推定方策を評価する必要があるので、前節の話が生きる
p136のアルゴリズムは正直よくわからない
- 今までの話とは違って各状態行動ついに対して収益$R_t$を定める必要がある
- エピソードごと、ではなく非グリーディ行動ごとに方策評価をしている
- 非グリーディ行動と非グリーディ行動の間のグリーディ行動を見て、前節のような重み付けを実行している...?

##漸進的実装

##まとめ

モンテカルロ法はDPと比べて,
- サンプリングされた経験から直接最適挙動を学習でき、
- 遷移確率などのモデルを必要とせず、
- 状態群の部分集合に対して効率的に推定ができるすごいやつ
一部の状態について十分な訪問を確保できないという欠点に対しては、
- エピソード群が全てをカバーするようにする開始点探査と、
- エージェントが探査を維持し続ける方策オン/オフ型MC法とがある

Sutton本 第5章 モンテカルロ法 まとめ