Upgrade to Pro — share decks privately, control downloads, hide ads and more …

The Multi-Armed Bandit Problem and Its Solutions

Haruka Kiyohara
December 06, 2020

The Multi-Armed Bandit Problem and Its Solutions

深層学習&ロボティクス勉強会 @ deeplab
https://deeplab-team.github.io/

Reference:
https://lilianweng.github.io/lil-log

Related:
https://speakerdeck.com/deeplab

Haruka Kiyohara

December 06, 2020
Tweet

More Decks by Haruka Kiyohara

Other Decks in Research

Transcript

  1. 深層学習&ロボティクス勉強会 deeplabは2019年4月に設立した学生による人工知能研究会である.東大,東工大,早 慶大をはじめとする都内の学部生を中心に20名以上が参加し,2019年度は5.4日に1 回ペース,年間60回を超える勉強会を開催し,人工知能関連分野 (ML, DL, CV, NLP, RL, Robotics,

    Speech, HCI, CognitiveScience, etc) を探究している. 今回は「深層学習の最新トレンドと強化学習,ロボティックス分野における発展」をテー マとし,勉強会を実施した.題材としてOpenAIのRoboticsチームの研究者であるLilian Wengさんのブログ (https://lilianweng.github.io/lil-log) を参考にし,資料作成,発表, ディスカッションを行った.
  2. Exploitation vs Exploration • 日常は非完全情報であふれている. ⇒常に探索と活用のジレンマが存在する. e.g., 近所の好きなレストランの隣に新しいレストランができたら,どっちに行く? ・好きなレストランに通い続ける: もっと良いレストランを見つける

    チャンスを逃すかもしれない. ・新しいレストランに行ってみる: もしかしたら,まずい昼食をとる ことになるかもしれない. • 長期的な視点で探索と活用をバランスよく行う必要がある. • 短期的な犠牲の上に長期的な最適化戦略が行われることも. Fig. UC Berkeley AI course slide, lecture 11.
  3. Applications • 推薦システム / 広告配信 e.g., Netflixによる映画のサムネイルの個別最適化 [F. Amat et

    al., RecSys’18] • ゲームの手選択 e.g., AlphaGoによる囲碁におけるモンテカルロ木探索 [D. Silver et al., Nature’16] • 最適化 / モデル選択 e.g., 文脈を考慮したパラメータ最適化 [A. Krause and C. Ong, NIPS’11]
  4. Bandit Strategies • 多腕バンディット問題へのアプローチは,大きく以下の3つに分かれる. • 探索なし: 短期的な報酬最大化を追求する貪欲的手法で,長期的には損をする 可能性もはらんでいる. • 確率的探索:

    主に貪欲に報酬最大化を行うが,一定割合のランダムな行動探索を することで探索も行えるようにする. • 効率的探索: 不確実性を定量的に評価し探索の優先順位を決定することで,効率 よく探索を行うことができる.
  5. Upper Confidence Bounds • 報酬は確率的に決定されるので,不確実性が大きい. • 不確実性を考慮した上で,期待報酬の上界を見積もったのがUCB. • 不確実性に依る上界ポテンシャル (UCB)

    を と置くと,以下の条件を満たす. ① が大きくなるほど は減少する. ②真の価値関数の上界が,推定価値関数とUCBの和で抑えられる. • このとき,効率的な貪欲行動選択は, • では,実際にUCBはどのように構築すれば良いのか? 真の価値関数の上界を最大化する行動選択 推定価値関数 + 不確実性項(UCB)
  6. Thompson Sampling (2/2) • 特にベルヌーイ分布に従う報酬確率 に対し,推定価値関数 を共役事前 分布のベータ分布で表現することで,ベイズ更新により価値関数を推定していく. • ベータ分布

    のパラメタは,以下のように解釈可能. : 報酬が得られたときの回数 : 報酬が得られなかったときの回数 e.g., のとき,不確実性が大きいが,報酬獲得確率は50%. のとき,かなり確からしく, 報酬獲得確率は10%. • 事後分布の推定は解析的でないので,ギブスサンプリングやラプラス近似,ブート ストラップ法などを用いて行う.
  7. Case Study • ベルヌーイバンディット問題における,手法の比較 Fig. 報酬獲得確率が {0.0, 0.1, .., 0.9}

    の10個の選択肢をもつベルヌーイバンディット問題 (左) 時間ステップと累積リグレット (中央) 真の報酬獲得確率と推定報酬獲得確率 (右) 10000ステップの学習において,各行動が選択された回数の割合
  8. Summary (revisit: Bandit Strategies) • 多腕バンディット問題へのアプローチは,大きく以下の3つに分かれる. • 探索なし: 短期的な報酬最大化を追求する貪欲的手法で,長期的には損をする 可能性もはらんでいる.

    • 確率的探索: 主に貪欲に報酬最大化を行うが,一定割合のランダムな行動探索を することで探索も行えるようにする. • 効率的探索: 不確実性を定量的に評価し探索の優先順位を決定することで,効率 よく探索を行うことができる. ⇒ベイズ的手法を取り入れていた.
  9. References (1/2) • Lilian Weng. Lil’Log The multi-armed bandit problem

    and its solutions. https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem- and-its-solutions.html • CS229 supplemental lecture notes: Hoeffding’s inequality. • RL Course by David Silver - Lecture 9: Exploration and exploitation. • Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. NeurIPS, 2011. • Daniel Russo et al. A tutorial on Thompson sampling. arXiv, 2017. • Fernando Amat et al. Artwork personalization at Netflix. RecSys, 2018. • David Silver et al. Mastering the game of Go with deep neural networks and tree search. Nature, 2016.
  10. References (2/2) • Andreas Krause and Cheng Soon Ong. Contextual

    gaussian process bandit optimization. NeurIPS, 2011. • 本田淳也,中村篤祥.バンディット問題の理論とアルゴリズム.講談社.2016.