shugo's kitchen

コンピュータサイエンスを美味しく調理していきたい

トップ > 強化学習 > 強化学習 Sutton本5章 モンテカルロ法について

強化学習 Sutton本5章 モンテカルロ法について

強化学習 読書メモ

[tex: ]

Sutton本の第5章の内容のメモです

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

  • 価値関数の計算や方策評価,改善といった基本的な考え方は一緒
  • DPと違って環境の完全な知識(期待報酬, 遷移確率など)は必要とせず、経験のみから価値を推定
  • エピソード的(=終わりがある)タスク限定
    • エピソードごとに価値と方策を更新

MC法による方策評価

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

スクリーンショット 2019-07-30 15.49.15.png

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法による一般化方策反復

  • 基本的に4.4節,4.6節あたりのことがMC法でも成立しますよ〜という感じ
  • 方策評価→方策改善(グリーディ)→方策評価→...の繰り返し
モンテカルロES
  • 今までは方策評価が無限個のエピソードについて行われるという仮定でやってきた
    • DPの時の1スイープしなきゃいけない仮定と似ている
  • これを取り払うには方策改善の前に方策評価を完全に完了させることを諦めれば良い
    • 非同期DPと一緒
    • 1エピソード見るたびにQを更新して\piも更新しちゃう

スクリーンショット 2019-07-30 17.18.24.png

方策オン型MC法

  • やっぱり開始点探査の仮定も取り払いたいらしい
    • その方法として方策オン型とオフ型があり、ここでは前者について説明
  • 前述の通り方策\piを非決定論的とすれば良い
εソフト方策
  • 全ての状態s,行動aについて \pi(s, a) \geq \frac{\epsilon}{|A(s)|} ( > 0) となる方策のこと
  • 今回はこの一例としてεグリーディ方策を用いている
  • 方策改善定理がこのεソフト方策についても成立することがこの節で示されている
    • つまり方策反復はεソフトについても機能する

スクリーンショット 2019-07-30 18.16.34.png

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

  • これまである一つの方策\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を定める必要がある
    • エピソードごと、ではなく非グリーディ行動ごとに方策評価をしている
    • 非グリーディ行動と非グリーディ行動の間のグリーディ行動を見て、前節のような重み付けを実行している...?

漸進的実装

  • 2.5節でも出てきた、報酬が得られるたびに保存して毎回全部の平均を取るのは計算量やメモリの無駄だから漸化式にしてしまえという話
  • 今回は(5.4)式のような重み付け和だからちょっと違うね〜というだけ
  • p136のアルゴリズムのように分母分子に分ける方法でもいいのでは？と思った

まとめ

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