『バンディット問題の理論とアルゴリズム』購入。
本多淳也/中村篤祥・著 講談社
ISBN:9784061529175
本体 2800円(税別)
http://www.kspub.co.jp/book/detail/1529175.html
なんだか凄そうである。
http://qiita.com/yuku_t/items/6844aac6008911401b19
◯
バンディット問題とは、選択肢の集合から1つの要素を選択し、その選択肢に対する報酬を得るが、他の選択肢の報酬情報は得られない、というプロセスを繰り返す設定において、報酬和の最大化を目指す逐次決定問題である。
◯『人生は選択の繰り返しです。...本当にもっと良い現在があったかどうか確かではありません。....1つ言えることは、
「探索」と「知識利用」のバランスが重要であることです。
...最適な選択をするために、もっと良い道を探す「探索」と今までの経験を生かす「知識利用」のバランスをとることが重要です。まさにこれがバンディッド問題の本質でもあるのです。』
◯バンディッド問題は大別して、
確率的バンディットと
敵対的バンディットに分けられる。
前者は各アームから何らかの確率分布に従って生成され、
後者はプレイヤーの方策を知っている敵対者が報酬を決める場合を想定する。バンディッドとは盗賊という意味で、
1台のアームが付いた古典的なスロットマシーンで、プレイヤーに賭けをさせることにちなんで
1腕バンディットといい、複数のスロットマシンを選んでアームを引くことを反復することで儲けの最大化を図ること
多腕バンディット問題という。プレーヤーがスロットを引く戦略を
方策という。
◯現実への問題では、治験、インターネット広告配信、推薦システム、ゲーム木探索、オンライン経路制御など多岐にわたる。
◯プレイヤー方策の評価方法として、
有限時間区間における累積報酬と
無限時間区間における幾何割引された累積報酬がある。累積報酬の他に、
リグレット(後悔)という評価値があり、これは
「あの時ああしていればよかった」という後悔の大きさの値である。(面白い!)
◯機械学習でバンディット問題が取り上げられたのは、
UCB方策(2002年)。コンピュータ囲碁で使われるモンテカルロ木を取り入れた
UCTアルゴリズム (2006年)で囲碁の性能が向上。推薦システムには
LinUCB方策というものが提案され、これは
コールドスタート問題(新しいユーザ又は新しい商品に関してパーソナライズされた適切な推薦が行われるまで時間がかかる)という問題の解決手段となる。
敵対的バンディッドでは、ブースティングにも関係ある
Hedgeアルゴリアウムを適用した
Exp3方策(1995年)がありリグレット解析を行った。その後 2009年の改良された
INF方策が提案された。
◯この書籍の構成は2章から5章で、基本的なバンディット問題の設定。2章は、大偏差原理など、3章では効率的な方策の構成、4章では厳密なリグレット解析、5章では敵対的バンディット。6章からは発展で、6章は最適腕識別。7章バンディッド問題の基本的な拡張として、報酬の構造の線形モデルへの一般化。8章では非線形、無限個のアームがる状況の連続腕バンディッド。9章では、非定常的な確率モデル、観測モデルの一般化。10章では現実の問題、インターネット広告配信やゲーム木探索の効果的な方策を取り扱っている。
プログラム
https://iridge.jp/blog/201412/5508/