[論文紹介]Best Arm Identification in Multi-Armed Bandits

Best Arm Identification in Multi-Armed Bandits 加藤まる at FUN AI 輪講

アジェンダ ● ● ● ● ● 前提知識 概要 手法 議論 次に読むべき論文

関連するキーワード ● ● ● ● 機械学習 ゲームAI クラウドソーシング 意思決定

アジェンダ ● ● ● ● ● 前提知識 概要 手法 議論 次に読むべき論文

多腕バンディット問題とは 一人のギャンブラーが報酬の確率分布が未知の複数台のスロットマシンを繰り返 しプレイするときに、どのような方策に従うのがベストなのかを考える問題

多腕バンディット問題とは 各段階でギャンブラーが１つの”腕”を選択し、そこから報酬を受取る。 確率的バンディット問題では、報酬は固定確率分布から引き出される。 （一般の多腕バンディット問題の）目標は「報酬の累積合計を最大化する」こと。

多腕バンディット問題とは 「選択肢はいくつもあるけど、どの選択肢が効果が高いのか事前にわからない」 「限られた試行回数でできる限り良い選択肢を選んでいき、トータルの報酬を最 大化したい」 実際に使われる場面：web広告

web広告での使われ方 ・Webサイトの目的は、ユーザに対して広告や商品・サービスを配信・推薦し、閲覧 /購入/予約（CV） ・ユーザに提供する広告/商品/サービスをスロットマシンに見立て、ユーザのCVを 報酬と考える →ユーザに広告等を配信により多くのCVを獲得する問題や、CVに至る可能性が最も 大きい広告を探す問題は、 累積報酬最大化や最適腕識別などの基本的な多腕バン ディット問題としてみることができる

“後悔”という概念 regret = [最も報酬が得られる台からの報酬]-[予測した台からの報酬]

アジェンダ ● ● ● ● ● 前提知識 概要 手法 議論 次に読むべき論文

概要 最適腕識別とは、報酬の期待値が最大である”腕”を探す枠組み。（報酬の最大化 ではない） →この最適腕識別について、逐次削除方策を提案する。

累積報酬最大化と最適腕識別（使用用途） ・累積報酬最大化→本稼働 ・最適腕識別→試用期間

累積報酬最大化と最適腕識別（方策） ・累積報酬最大化→期待値最大の腕と推定される”腕”を多く探索するため、選 択数の偏りが非常に大きい。 ・最適腕識別→各腕の選択数を同程度のオーダーにする

問題設定 ● ● ● ● ● K : スロットマシンの台数（腕の本数） i : マシンの番号 t : ラウンド数（台数を選べる回数） μi : 報酬の期待値 μ* : max k()

標本複雑度 達成可能な性能について理論限界が存在する。 所定の誤識別率を達成するのに必要な試行回数の指標を標本複雑度という。

標本複雑度

標本複雑度

アジェンダ ● ● ● ● ● 前提知識 概要 手法 議論 次に読むべき論文

UCB-E(Upper Confidence Bound Exploration) スコアを計算し、最も良いスコアの腕を選択するアルゴリズム（既存）

UCB-E(Upper Confidence Bound Exploration) ・信頼上限を腕の選択の基準として用いる ・一様選択 ・探索をするほどに後悔が減る ・誤差enに上限がある

UCB-E(Upper Confidence Bound Exploration)

もとになったUCBアルゴリズム Reference : https://jeremykun.com/2013/10/28/optimism-in-the-face-of-uncertainty-the-ucb1-algorithm/

UCB-Eの問題 選択された回数が偏る。最適腕識別では各アームの選択数が同程度のオーダーに なることが望ましい。

UCB-Eの問題

逐次拒絶アルゴリズム SRは探索範囲を狭めながら、各腕を満遍なく探索するアルゴリズム

逐次拒絶アルゴリズム 基準１：期待値の上界μi,nが最適腕の期待値の下界μより小さい腕は最適腕である 見込みがないとみなして除外 基準２：最適腕の期待値の現時点での下界μに許容幅を加えたものが、それ以外の 腕の期待値の上界μを上回った時点で、それを最適腕として出力する。

逐次拒絶アルゴリズム

アジェンダ ● ● ● ● ● 前提知識 概要 手法 議論 次に読むべき論文

議論 ● ● 経験的分散を考慮した場合の複雑度の良い尺度はなにか 単一のアームだけでなく、上位mのアームを推奨することに関心がある場 合、アルゴリズムと分析をどのように変更する必要があるか

アジェンダ ● ● ● ● ● 前提知識 概要 手法 議論 次に読むべき論文

次に読む論文 バンディット問題関連 ● ● ● ● ● Thompson sampling A modern Bayesian look at the multi-armed bandit Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems Stochastic Linear Optimization under Bandit Feedback Finite-time Analysis of the Multiarmed Bandit Problem