バンディット問題の理論とアルゴリズム読書会第1回 2019/8/23
Chapter1 バンディット問題とは
プレゼンテーションモード
https://gyazo.com/49ad6f1441587ea8c13c1b8b9a706239
1.1 はじめに
バンディット問題の例
カジノでスロットマシンに挑む
https://gyazo.com/8c2adb494d19aa7feecf38580a48e2e7
スロットマシンにはあたりが出る確率が0%〜100%で設定されている。
1回ごとにアームを選んで合計100回引く場合、どのようにアームを引くのがもっとも儲けられそうか？
（このスロットマシンは「当たり」「ハズレ」のどちらかの結果が得られる）
考え方
「もっとも当たりやすいアームを引きたい」
「でもどのアームが当たりやすいかわからない」
「ではまず各アームを何回かずつ(n回)引いて当たりやすさを調べて、一番良かったやつを引きまくろう」
table:はじめに何回ずつ引くか
n 合計 残りの回数 懸念
3 3*5=15回 85回 3回で見極められる？
17 17*5=85回 15回 残り15回ではあまり儲けなさそう
探索と知識利用のトレードオフ
あるアームが当たりやすいか否かの情報はそのアームを実際に引いた結果のみから得られる
そのため、もっとも当たりやすいアームを把握するには、情報の少ない（＝これまで選択回数の少ない）アームを選ぶこと（探索）が必要となる
しかし探索ばかりしていると儲けは大きくならない。それまでの情報から最も当たる確率の高そうなアームを引く知識利用を行う必要もある。
この探索と知識利用のバランスをどうするかという問題は「探索と知識利用のトレードオフ」「探索と知識利用のジレンマ」と呼ばれる
バンディット問題とは
選択肢の集合から1つの要素を選択し、
その選択肢に対する報酬を得るが他の選択肢の報酬情報は得られない
というプロセスを繰り返す設定において、得られる報酬の合計を最大化することを目指す、逐次決定問題
スロットマシン：1腕バンディット
K台のスロットで儲けを最大化する問題：多腕バンディット問題
用語
一般のバンディット問題において、選択肢を「アーム」と呼ぶ
それまでの情報を元に次に引くアームを決定する戦略のことを「方策」と呼ぶ
1.2 バンディット問題の例
ネット広告
あるWebページに広告を表示する。表示された広告がクリックされる回数の合計を最大化したい。
Webページ
https://gyazo.com/cc97bf4a946915e64185a50c7d2503bf
他の広告の例
https://gyazo.com/9cabc73a8b8e42343da1cad09f98f645
https://gyazo.com/3ec4c6862b230737e2f9ba647653a191
ネット広告
最大化したいこと：広告がクリックされる回数（利益のこともある。広告がクリックされた分だけ、Webメディアにお金が入る場合。）
選択肢：どの広告を表示するか。
ジレンマ
色々な広告を表示した方が、相性の良い（クリックされやすい）広告が見つかるかもしれない。（探索）
しかし知識利用の回数が少なくなってしまう
その他の例
治験
推薦システム
ゲーム機探索
オンライン経路制御
1.3 確率的バンディットと敵対的バンディット
バンディット問題は2つに分類できる
確率的バンディット：各アームからの報酬が何らかの確率分布に従って生成される
前述の広告の例はこちら
敵対的バンディット：プレイヤーの方策を知っている敵対者が報酬を決める場合を想定する
敵対的バンディット
プレイヤーの方策を知っている神のような能力を持つ敵対者が報酬を選ぶと仮定。
そんな状況で、プレイヤーはどのようにすれば良いか、うまくいく方策を考える。
ある弱小プレイヤーの例
3台のスロットがあり、報酬は0〜1の範囲の数値を取るとする。設定されている報酬は常に合計1とする。
https://gyazo.com/88ea5739b8f9a596ece7268336fc04ec
弱小プレイヤーの方策
引いたことないアームがあれば左から優先して引く。
全て1回引いた後はアームごとの引いた平均報酬が高いものを選ぶ。
平均報酬が全て等しい場合はまた左から優先して引く。
敵対者
敵対者は上のポリシーを知った上で報酬を決める。
どのような結果になるか（弱小）
table:プレイヤーの引くアーム、設定される報酬
スロット 1回目 2回目 3回目 3回目までの平均 4回目以降
左 0 ✅ 1 1 0 0✅
中央 1 0✅ 0 0 1
右 0 0 0✅ 0 0
反省（弱小）
プレイヤーが決定的な方策を用いる場合、敵対者はその方策を知っていると、選択アームが事前にわかってしまう。そしてその選択アームに報酬の最小値を設定できてしまう。プレイヤーは勝てない。
そのためプレイヤーは確率的な方策を用いるしかない。
（本来のスロットなら、平均報酬が0続きだと続けてもらえないのでこれは極端な例。）
中級プレイヤーの方策
引いたことないアームがあれば、全ての中からランダムに引く。
全て1回引いた後はアームごとの平均報酬の比率で引く。（平均報酬が高いものほど引かれやすいが、低いものも引かれることがある）
どのような結果になるか（中級）
table:プレイヤーの引くアーム、設定される報酬
スロット 1回目 2回目 3回目 4回目 4回目までの平均 5回目
左 0.3 0.3 0.3 0.3✅ 0.3 0.4
中央 0.3✅ 0.3✅ 0.3 0.3 0.3 0.4
右 0.4 0.4 0.4✅ 0.4 0.4 0.2✅
反省（中級）
確率的な方策を用いることで、弱小プレイヤーよりも報酬を得られた
敵対者(adversary)の分類
忘却型敵対者(oblivious)：プレイヤーの過去の選択に依存せず報酬を決める
適応型敵対者(adaptive)：プレイヤーの過去の選択に依存して次の報酬を決める
本書ではこちらのモデルを扱う。こっちの方が難しい。
他の資料では
忘却型敵対者は「前もって報酬を決めている」敵対者との説明があった。
takkii.icon「oblivious」は「気づかないで」という意味があるのでそちらの方が感覚にあってる気がする。（どのアームが引かれたか気づかない）
https://gyazo.com/7106f5811c2b3fd7cb434d8969a72ef7
https://www.youtube.com/watch?v=3A5zd-SaF9U
敵対的バンディットで扱う報酬モデルの特徴
確率的バンディットのものを含んでいるため、報酬の確率的な構造が未知である・あるいは存在しない場合も扱うことができる
🤔
プレイヤーがより広い報酬モデルを考慮しなければいけないため、性能は悪くなる
逆に確率的バンディットの手法は、報酬をうまく表現できる確率モデルが事前にわかっている場合には、大きな累積報酬が見込める
🤔
1.4 プレイヤー方策の評価法
アームiの時刻tにおける報酬を$ X_i(t)とする
時刻tにプレイヤーが選ぶアームを$ i(t)とする
ある時刻tにプレイヤーが選んだアームで得られる報酬は$ X_{i(t)}(t)
2つの累積報酬の計算方法
1つ目：有限時間区間における累積報酬
時刻Tまでの報酬の合計
$ \sum_{t=1}^{T} X_{i(t)}(t)
例えば広告であれば、サーバーごとに異なる方策が設定されているとき、決められた時間内でサーバーごとのクリック数合計を比較して方策を評価するような場合。
1つ目の「有限時間空間における累積報酬」に少し加工する。時間が1離れたら報酬に$ \gamma（$ 0 \leqq \gamma \leqq 1）をかける（将来得られる報酬は現在より価値が低い）。その後時刻無限まで足す。
$ \sum_{t=1}^{\infty} \gamma^{t-1} X_{i(t)}(t)
「2つの評価法」の評価
最近では1つ目の「有限時間空間における累積報酬」で方策を評価するのが主流。
累積報酬を元にした評価方法
累積報酬の大小で単純に比較してはいけない。
理由：方策の良し悪しだけでなく、報酬の組み合わせが全体として大きめだったかといった要素にも依存する。
そこで、純粋な方策の良さを評価するために下記の2つの差を見る。
試した方策による結果
最適な方策を取った場合の累積報酬
最適な方策は「到達しうる累積報酬の最大値」にすることも可能だが、目標として高すぎる…
そこで「同じ選択肢を選び続けた場合の累積報酬の最大値」を選ぶ
$ \operatorname{Regret}(T)=\max _{i \in\{1, \ldots, K\}} \sum_{t=1}^{T} X_{i}(t)-\sum_{t=1}^{T} X_{i(t)}(t)
右辺の左が、あるアームを常に選び続けるとしたときの累積報酬の最大値(アーム1〜Nのどれかに固定して、時刻1〜Tの報酬を合計している)
右辺の右が、ある方策による時刻1〜Tの累積報酬
takkii.iconリグレットがマイナスになることも理論的には有りうるということだな。
takkii.icon過去からRegretが求められることの方が少なそう。シミュレーションが主かな。
アームの1つ1つが広告であるなら、「あるアームを常に選び続ける」とは「同じ広告を選び続ける」ということになる。「ただ同じ広告を出してた時どれぐらいクリックされていたか」はわからない。
プレイヤーが「あの方策をとっておけばよかったのに…」という後悔の大きさを表している値と考えられる。
リグレットの別の捉え方
$ \operatorname{Regret}(T)=\max _{i \in\{1, \ldots, K\}} \sum_{t=1}^{T} X_{i}(t)-\sum_{t=1}^{T} X_{i(t)}(t)
右辺の左は「初めから最適なアームを知っていた時の報酬」
右辺の右は「最適なアームを知らないため探索が必要な時の報酬」
そのためリグレットは「最適なアームを知らないことのコスト」の指標とも言える。
各時刻tにおける「プレイヤー方策の選択(アーム)$ i(t)」も「報酬$ X_i(t)」も確率的な場合を扱うことが多いので、リグレットよりも期待リグレットや擬リグレットを用いることが多い
https://gyazo.com/5e4854b839e63bfc3d5a17f0b45f442f
https://gyazo.com/a7cbf5a23c75f96cc496edcd4e0d48a0
regretの弱い概念
結局リグレットって…
https://gyazo.com/9776095d88ebd6f276614e1aead8777d
期待リグレットと擬リグレットの関係
擬リグレットは期待リグレット以下の値を取ることが常に成り立つ
https://gyazo.com/6436a8d00d114e8f4ac84bed50305351
おまけ：常時停止可能アルゴリズム
takkii.icon例えば1時間だけ広告配信することがすでに決まっており、最初の30分はランダム、最後の30分は最初の30分でわかった「効率の良い広告」だけを配信するような仕組みは「常時停止可能アルゴリズム」ではないと思う。
1.5 バンディット問題の歴史
飛ばします。
重要なものは今後の章で触れられているはず。
1.6 関連分野
飛ばします。
1.7 本書の構成
https://gyazo.com/114cd2f98a736bcacc0bc75683759b38