複数の選択肢からもっともよさそうなものを選ぶ方法を聞いてきた！

９月２２日
第１３回ステアラボ人工知能セミナー
にいってきて、

多椀バンディット問題：定式化と応用

を聞いてきたのでメモ

---

■紹介
　次回：１０月２０日
　今日は

■多椀バンディット問題：定式化と応用
・自己紹介

・多椀バンディット問題とは
　複数の選択肢からもっともよさそうなものを選ぶ

・定式化
　各ラウンドｔ＝１，２，３・・・Ｔに
　アルゴリズムがアームＩ（ｔ）　｛１、・・・、Ｋ｝を選択したとき
　報酬を最大化する

・バンディット問題
　Ｋ個のスロットマシンがある
　一番高い期待報酬を求める
　　→部分フィードバック

　→探索と活用のトレードオフ
　　探索：全部のアームを調べたい
　　活用：一番良いアームを選びたい

・例：オンライン広告　代理店Ａ－Ｚのどこに出したらよいか

・アルゴリズム：過去の報酬情報を見て、次に選ぶアームを決定する

・３つの定式化
　　　ベイズ的：事前分布仮定 Gittins指数
　　　確率的：頻度UCB/TS/MED
　　　敵対的：Exp3

・ベイズ的バンディット問題
　事前分布のもとで、期待報酬最大化
　入力：割引因子、事前分布
　Gittins指数：ＧＩＴを最大化する
　良い点：
　　　最適アルゴリズム有
　　　アームの既知な変化を扱える
　欠点？：
　　　事前分布、割引因子に依存
　　　計算大変　ベルマン方程式を解く必要がある

・確率的バンディット問題
　　報酬は各アームに対応した確率分布からのサンプル
　　リグレット　報酬最大化＝リグレット最小化
　　漸近最適アルゴリズム
　→いくつサンプルがあれば、いちばんいいアームを選択できるか？
　良い点
　　漸近最適アルゴリズム
　　効率的アルゴリズム
　悪い点
　　報酬変化扱いにくい

・敵対的バンディット問題
　敵が不利な報酬を設定
　乱択すると一番良いアームを選べる
　　乱択アルゴリズムで有名なものＥｘｐ３

　良い点
　　仮定が弱い
　悪い点
　　性能悪い

・どれが使われている？
　　確率的と敵対的
　　ベイズ的はあまり見ない：計算が重い、学習できるかに興味

・どんな問題を扱える
　　報酬の過程が適切で
　　目的が報酬の最適化なら

　確率的＝状態がない
　敵対的＝状態は何でもＯＫ

・応用事例：オンライン広告
　　コンテキストありバンディット問題
　　　敵対的形式化→特徴量なし
　　　確率的形式化→線形回帰みたいなの（特徴量あり）

・応用事例：モンテカルロ木探索
　　　ゲーム木で表現
　　　難しい点：木のサイズ、評価が難しい：ＵＣＴは評価フリー
　　　ＵＣＴ＝ＵＣＢオーバーツリー
　　　ランダムプレイ：末端に１，０を埋めてしまう
　　　→いらないのは、早めに打ち切れる
　　あるふぁご
　　　ＵＣＴ＋評価関数
　　　真相学習を用いた４つの評価関数

・応用事例：推薦システム

・応用事例：Ａ／Ｂテスト
　　決定：検定？統計検定は、データ数固定
　　→Ａ／Ｂテストは結論出るまでやる
　　　　→どこかのサンプルでたまたま大きい値が出ることがある
　　逐次選択問題：尤度比を利用した方法

・組み合わせバンディット
　　→ＡＲＭ間に相関

・最適化：機械学習は最適化に落とすものが多いけど
　　同じものが選ばれると・・・

技術的負債は全額返済しないといけないのか？

素朴な疑問。
「負債」は無借金経営する会社も確かにあるけど、
一般的に負債があるから、いけないとはいえない。
安全性を上回る負債が有る場合（債務超過が典型的な例）はアウトだけど・・

じゃあ、技術的負債は？
債務超過のようにプロジェクトの安全性に支障をきたす場合はまずいけど、
すべて、返済する必要ってあるの？利益を削ってまでも？
（私は答えを持っていません。
　　「はい、あります」
　　「いいえ、ありません」
　どちらが正解かはわかりません。問題提起だけです）