ベイズ方式による多腕バンディッドの論文を読む
テニススクール90分 英語できず
(1) ベイズ方式による多腕バンディッドの論文を読む
「Gaussian Process Optimization in the Bandit Setting:No Regret and Experimental Design」https://arxiv.org/abs/0912.3995
バンディッドとはスロットマシンのことで、この論文は複数のスロットマシンへ出来るだけ少ない投資で沢山の報酬を得る戦略を考えるものです。
一般に沢山投資すればする程よいスロットマシンが見つかるので、これは事前の予想を試行結果で改善するのでベイズモデルとなります。
確率過程で無条件下では、ある時点から次の時点に推移するにはガウス分布の乱数で推移すると考えるのは合理的です。但しガウス分布の裾の広さは経験的に分っているとします。
この確率過程で下図の様に実測が分っている場合はその点を通るモデルとしてガウス確率過程(GP:Gaussian Process)がります。
下図はx軸に各スロットマシンが並んでおりy軸に報酬とした場合、真の平均の報酬曲線を推定する過程を示しています。GPは観測データが無い所は報酬の分散が広くなり、観測データがあると分散が狭くなる特性があります。
上図の様に分散が大きい所を試行すればより正確な曲線を把握できることがわかります。この様にすれば出来るだけ少ない投資で最上のマシンを見つける戦略が立てられそうです。
上図の様に探索するには具体的には次式で探します。
この方式をGP-UCB(Gaussian Process-Upper Confidence Bound)アルゴリズムと云います。
ここで
は回までの平均の報酬
は回までの報酬の標準偏差
が大きいと霍乱項を重視してを選択します
逆にが少ないと経験を重視したグリィディな選択とります
上式の値を得るためにGPは次の式で算出します。導出は下記のPRML記述参照
①式
ここで
は時点で得られた報酬です
はのグラム行列です
ここで は実際のデータより最尤法で計算されます。
恒例のPRMLから①式を導出してみます。
ガウス過程は高次元へ写像した関数での線形回帰を考えます。即ち高次元へ写像した方が非線形的な回帰を実現して当てはめが良くなります。
まず損失関数を考え回帰係数で微分して極小値を採る様にします。
②式
これをで微分すると
③式
ここで ④式 と置くと
⑤式
但し
④式をベクトル表現すると
上式に⑤式を代入すると
これをについて解くと 但し
①式が導出された
但し