強化学習　文献まとめ2

リレー解説 強化学習の最近の発展 第2回
「探索と利用のトレードオフとベイズ環境モデル」
計測と制御 第52巻 第2号 2013年2月号 P154~161
牧野 貴樹
https://www.jstage.jst.go.jp/article/sicejl/52/2/52_154/_article/-char/ja/
をまとめた個人用めも

※この記事をまとめたのは2021年5月あたりで、強化学習について勉強し始めのときにまとめたもので、間違った内容が含まれている可能性があります

前回：https://qiita.com/he-mo/items/ec86c0b18dd193ef3aaa
次回：https://qiita.com/he-mo/items/65e0505243934423a966

多腕バンディット問題

バンディッド問題の定義とリグレットの説明

• バンディッド問題・・・腕が何個もあるルーレットマシーン、腕ごとにルーレットが当たる確率が割り当てられてる
• リグレット・・・はじめから一番いいものを選択していればいくら得したか

探索をしすぎたらリグレットが大きくなるし、探索しなさすぎたら最適な腕が見つからない

ランダム探索

要するにイプシロングリーディー

不確かなときは楽観的に: UCB アルゴリズム

その腕の良さだけでなく、どれだけ知っているかを考慮する
選んだ回数が少ない・・・分散が大きい
分散も含め一番いいものを選択（報酬の期待値＋分散の半分）

Thompson サンプリング

「ある腕の報酬の期待値が他のどの腕の報酬の期待値よりも高い」確率に従って，その腕を選択
https://cafeunder.github.io/rosenblock-chainers-blog/2018/03/08/thompson-sampling-gaussian-sicq-prior.html

その他のバンディット問題

バンディット問題にもいろいろある

• 敵対的 (adversarial) バンディッ ト (相手が自由に設定を変えられる場合に相当し，確率的仮 定が通用しない)
• 文脈つきバンディット
• 連続バンディット (腕が離散ではなく d 次元実数空間上の点で表わされる場合)

強化学習における探索コスト最小化

探索と利用のトレードオフについて
探索すべき未知の状態につながる行動も探す必要がある

楽観的初期価値法

Q学習でいう、最初に与えるQ値を大きくしておく
効率的とは言えない

サンプル複雑性: モデルベース手法

定義

• サンプル複雑性・・・行動履歴全体の中で最適なものではなかったものの数
• PAC-MDP・・・サンプル複雑性が小さく抑えられている

PAC-MDPであると認められたアルゴリズム　E3、Rmax

一定回数(m回)探索してない選択肢は探索してない物と扱い、高い価値を与える
mが非常に大きくなければならないため実用的ではない

効率的に探索するアルゴリズム　モデルベース区間推定 (MBIE, Model-based interval estimation)

各状態–行動ペアに対する報酬と遷移確率に関する信頼区間（分散）を求め，その信頼区間のなかで最大 の価値となるような行動を，モデル上の計算で解く

サンプル複雑性: モデルフリー手法

q学習のようなサンプル複雑性を抑えるアルゴリズム　
Delayed Q- learning
一定回数探索してない選択肢に関しては、その時点ではQ値を更新しない
一定回数後に一気に更新する

ベイズ主義的アプローチ

事前知識を活用できたら探索回数が少なく済む
ベイジアン強化学習と呼ぶ

部分観測マルコフ決定過程

マルコフ決定過程を拡張したもので、環境を全て観測できない
環境を[θ,s]で表し、θは観測できない

ベイジアン強化学習においては、θが事前知識に対応する

手法として、以下の3つがある

共役分布表現を直接利用する方法

事前知識を直接利用、操作
BEETLE、BVRがある

環境モデルのサンプリングに基づく手法

事前知識をサンプリング
Bayesian DP、MBBE、BOSS、MC-BRLがある

モンテカルロ木探索法

θを探索木の探索であると解釈し、モンテカルロ法を用いる
UCT、FSSS、BFS3がある