1多腕バンディット問題の理論とアルゴリズム
本多淳也
東京大学 新領域創成科学研究科 助教
IBIS2014
2014/11/18

多腕バンディット問題(multiarmed bandit problem)• 複数台のスロットマシンをプレイするギャンブラーのモデル• 得られる報酬の確率分布は台によって異なる• なるべく期待値の高い台をプレイしたい問題：• ある程度の回数プレイしないと台の良し悪しが分からない• 報酬の期待値の低い台を何度もプレイすると損

2

3

歴史
• 研究自体は1930年ごろからある– 農地への作付物の選択– 新薬や新療法の検証 (cf. one-armed bandit)• 最近になって急速に応用範囲が拡大– 囲碁などのゲーム木探索– 広告・ニュース記事推薦– ネットワークルーティング– 学習アルゴリズムの選択や最適化パラメータのチューニング

4概要• バンディット問題の分類• 報酬最大化のためのアルゴリズム– 理論限界– 決定的アルゴリズム： UCB アルゴリズム– ランダムアルゴリズム： Thompson sampling• 最適腕識別との関係• 種々の拡張

5概要• バンディット問題の分類• 報酬最大化のためのアルゴリズム– 理論限界– 決定的アルゴリズム： UCB アルゴリズム– ランダムアルゴリズム： Thompson sampling• 最適腕識別との関係• 種々の拡張

6

バンディット問題の分類• 報酬の性質– stochastic bandit （確率的）– adversarial bandit （敵対的）• 目的関数– 累計報酬の最大化 (regret 最小化)
– 期待値ベストの台の判定 (best arm identification)• 設定の拡張– linear bandit– contextual bandit （context: 閲覧履歴・エキスパート…）– 連続空間上のバンディット…

7

確率的バンディット≋ 台のスロットマシンを選んで計 ≮ 回プレイ
• 各台からの報酬が期待値 ⊹≩ の（例えば）ベルヌーイ分布に•したがう• 実際にプレイした台についてのみサンプルの情報が得られる

8

確率的バンディット≋ 台のスロットマシンを選んで計 ≮ 回プレイ
• 各台からの報酬が期待値 ⊹≩ のベルヌーイ分布にしたがう⊤ ∽ ≭≡≸≩ ⊹≩⊹reward 最大化 (= regret 最小化)：• 期待値最大の台を知っていた場合の報酬期待値： ≮⊹⊤≘⊹≩≔≩∨≮∩• それぞれ台 ≩ を ≔≩ ∨≮∩ 回選んだ場合の期待値：•≩• 目標：期待値の損失 (regret) の最小化≘≲≥≧≲≥≴∨≮∩ ∽ ∨⊹⊤ ⊡ ⊹ ∩≔ ∨≮∩≩ ≩≩9

確率的バンディット≋ 台のスロットマシンを選んで計 ≮ 回プレイ
• 各台からの報酬が期待値 ⊹≩ のベルヌーイ分布にしたがう•

最適腕識別 (best arm identification)：•≮ 回のプレイの後で期待値最大の台をなるべく高確率で判定(fixed budget)– 確率 ⊱ 以上で正解するための試行回数を最小化するという設定も （fixed confidence）• ある種の能動学習の問題• 理論解析の道具は regret 最小化と似ているが，実際にとるべき戦略は多少異なる

10

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目
台１台２台３

２回目

３回目

４回目

11

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目
台１0.8

台２

0.3

台３0.4

２回目

３回目

４回目

12

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目
台１0.8

台２

0.3

台３0.4

２回目

３回目

４回目

13

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目

２回目

台１

0.8

0.5

台２

0.3

0.9

台３

0.4

0.1

３回目

４回目

14

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目

２回目

台１

0.8

0.5

台２

0.3

0.9

台３

0.4

0.1

３回目

４回目

15

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目

２回目

３回目

台１

0.8

0.5

0.2

台２

0.3

0.9

0.1

台３

0.4

0.1

0.4

４回目

16

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目

２回目

３回目

台１

0.8

0.5

0.2

台２

0.3

0.9

0.1

台３

0.4

0.1

0.4

４回目

17

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目

２回目

３回目

４回目

台１

0.8

0.5

0.2

0.3

台２

0.3

0.9

0.1

0.8

台３

0.4

0.1

0.4

0.6

18

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目

２回目

３回目

４回目

台１

0.8

0.5

0.2

0.3

台２

0.3

0.9

0.1

0.8

台３

0.4

0.1

0.4

0.6

19

敵対的バンディット• 各マシンからの報酬 ≸≩∻≴ ∲ ≛∰∻∱≝ が adversary により敵対的に決められる

１回目

２回目

３回目

４回目

累計

台１

0.8

0.5

0.2

0.3

1.8

台２

0.3

0.9

0.1

0.8

2.1

台３

0.4

0.1

0.4

0.6

1.5

• Regret ＝ 同じ台を選び続けた場合の最大報酬 － 実際の報酬＝ 2.1 － 1.5 ＝ 0.6• 確率分布を仮定しなくていい20

概要• バンディット問題の分類• 報酬最大化のためのアルゴリズム– 理論限界– 決定的アルゴリズム： UCB アルゴリズム– ランダムアルゴリズム： Thompson sampling• 最適腕識別との関係• 種々の拡張

21理論限界• ある台に決め打ちしたりしない「真っ当な」戦略のみ考えたい– 真っ当な戦略： ベストでない台のプレイ回数が≯∨≐≯≬≹∨≮∩∩• このような戦略を用いた場合には≬≯≧≮≅≛≔≩∨≮∩≝ ⊸ ≄∨⊹≩≫⊹⊤∩ ∫ ≯∨≬≯≧≮∩
ベルヌーイ分布の KL ダイバージェンス(Lai & Robbins, 1985)– 分布≂≥≲∨⊹≩∩ と ≂≥≲∨⊹⊤∩ の「紛らわしさ」でプレイ回数が決まる• 逆にこれより良い性能を達成する（場合がある）戦略は設定次第
で regret が多項式オーダーに22漸近最適戦略の構成• 理論限界： ≔≩ ∨≮∩ ⊸ ≏∨≬≯≧≮∩– ベストでない台 を引いてしまう１ラウンドごとの確率は≩≏∨∱∽≮∩– 逆に≏∨∱∽≮∩ 程度の確率でダメっぽい台を選べばよさそう• UCB 戦略： 有意水準 ∱∽≮ での信頼区間の上限 (UpperConfidence Bound) が最大になる台をプレイ∲⊡∲≔∨≮∩∨⊹⊡≸∩≩≩⊹≩ ⊷ ≸≝ ⊷ ≥– Hoeffding の不等式： ≐≲≛≞– Hoeffding の不等式から導かれる UCB (Auer et al., 2002):∲⊡∲≔∨≮∩∨⊹⊡≞⊹∩≩≩≕≃≂≩ ∽ ≭≡≸≦⊹ ∺ ≥⊸ ∱∽≮≧≳≬≯≧≮∽ ⊹≞≩ ∫ ∲≔≩∨≮∩

23

漸近最適戦略の構成• 理論限界： ≔≩ ∨≮∩ ⊸ ≏∨≬≯≧≮∩– ベストでない台 を引いてしまう１ラウンドごとの確率は≩≏∨∱∽≮∩– 逆に≏∨∱∽≮∩ 程度の確率でダメっぽい台を選べばよさそう• UCB 戦略： 有意水準 ∱∽≮ での信頼区間の上限 (UpperConfidence Bound) が最大になる台をプレイ– Chebycheff の不等式： ≐≲≛≞⊹≩ ⊷ ≸≝ ⊷ ≥⊡≔≩∨≮∩≄∨≸≫⊹≩∩– Chebycheff の不等式から導かれる UCB (KL-UCB)(Burnetas+, 1996, Garivier+, 2011):≕≃≂≩ ∽ ≭≡≸≦⊹ ∺ ≥⊡≔≩∨≮∩≄∨≞⊹≩≫⊹∩ ⊸ ∱∽≮≧∽ ⊹ ∾ ⊹≞≩ ≳∮≴∮ ≄∨≞⊹≩≫⊹∩ ∽ ∨≬≯≧≮∩∽≔≩∨≮∩

24

UCB の性質• KL-UCB は理論限界を達成– ベルヌーイ分布・分散既知の正規分布 (Burnetas+, 1996)– １パラメーター指数型分布族の一部 (Garivier+, 2011)
問題点• KL ダイバージェンスの逆関数を計算するのが若干面倒– ある種の双対アルゴリズムを導入すると逆関数の計算は不要(DMED・IMEDアルゴリズム, Honda+, 2010, 2012)≛∰∻∱≝ あるいは ∨⊡∱∻∱≝ 上のノンパラメトリックモデルも可• 信頼区間の有意水準 ∱∽≮ とかいう謎のパラメーター•– 理論限界を知らないと出てこない– 完全に漸近論に依拠

25

Thompson sampling• ベイズ戦略の一種 (Thompson (1933) にちなむ)• その台が最適である事後確率に従って台をランダムに選択• 経験的には非常に高性能• あまり事前分布の取り方にも依存しない• (linear や contextual, 非定常の場合含めて) 事後分布が計算可能なモデルでさえあればとりあえず動かせる• 最近になって理論解析が整備• ベルヌーイ分布モデル (Agrawal & Goyal, 2013 ほか)• １変数指数型分布族 (Korda, Kaufmann & Munos, 2013)• 平均・分散未知の正規分布 (Honda & Takemura, 2014)

26

Thompson sampling の性能• 大抵の場合にUCBよりも高性能• 例： 10個のスロットマシン,
クリック率 10%×1台 ・ 5%×3台 ・ 2%×3台・1%×3台
KL-UCBTS[Kaufmann et al., 2012]

27

ランダムアルゴリズムの利点• TS ではそれぞれの台を「その台がベストである事後確率」にしたがってランダムに選択– この確率は計算困難⊼∨⊹≩ ⊸ ≭≡≸≪∶∽≩⊹∰≪ ≪≦≸≩≧∩∱≚ ⊵≩≚∱≙∽ ∰ ⊼∨⊵≩≪≸≩∩ ≀ ∰ ⊼∨⊵≪ ≪≸≪ ∩≤⊵≪ ≁ ≤⊵≩≪∶∽≩⊹≩ ∽ ⊵≩ となる確率 他の台で ⊹≪ ⊷ ⊵≩ となる確率– 実際にはこの確率の計算は不要：
各台から乱数 ≩ を事後分布≩ ≩ にしたがって生成して≩ が最大となった台 をプレイすれば同等な動作となる⊵⊵≩⊼∨⊹ ≪≸ ∩

28TS の実装
• 「事後分布のもとでの各台が期待値ベストな確率」は実際には計算が困難• 単に事後分布≩ ≩ にしたがって ≩ をそれぞれランダムにサンプリングし，それが最大になった台を選択すればよい⊼∨⊹ ≪≸ ∩⊵– 例： 事前分布 ⊼∨⊹≩ ∩ ∽ ≵≮≩≦∨∰∻∱∩ の場合
これまでの結果

台１台２

台３

1,0,1,10,01,0,1⊹≩ の事後分布 ≂≥∨∴∻∲∩ ≂≥∨∱∻∳∩ ≂≥∨∳∻∲∩
事後分布からのサンプル

29TS の実装
• 「事後分布のもとでの各台が期待値ベストな確率」は実際には計算が困難• 単に事後分布≩ ≩ にしたがって ≩ をそれぞれランダムにサンプリングし，それが最大になった台を選択すればよい⊼∨⊹ ≪≸ ∩⊵– 例： 事前分布 ⊼∨⊹≩ ∩ ∽ ≵≮≩≦∨∰∻∱∩ の場合
これまでの結果

台１台２台３

1,0,1,10,01,0,1⊹≩ の事後分布 ≂≥∨∴∻∲∩ ≂≥∨∱∻∳∩ ≂≥∨∳∻∲∩
事後分布からのサンプル

0.78

0.160.68

30TS の実装
• 「事後分布のもとでの各台が期待値ベストな確率」は実際には計算が困難• 単に事後分布≩ ≩ にしたがって ≩ をそれぞれランダムにサンプリングし，それが最大になった台を選択すればよい⊼∨⊹ ≪≸ ∩⊵– 例： 事前分布 ⊼∨⊹≩ ∩ ∽ ≵≮≩≦∨∰∻∱∩ の場合
これまでの結果

台１台２

台３

1,0,1,1,00,01,0,1⊹≩ の事後分布 ≂≥∨∴∻∳∩ ≂≥∨∱∻∳∩ ≂≥∨∳∻∲∩
事後分布からのサンプル

31

TS の実装• 「事後分布のもとでの各台が期待値ベストな確率」は実際には計算が困難• 単に事後分布≩ ≩ にしたがって ≩ をそれぞれランダムにサンプリングし，それが最大になった台を選択すればよい⊼∨⊹ ≪≸ ∩⊵– 例： 事前分布 ⊼∨⊹≩ ∩ ∽ ≵≮≩≦∨∰∻∱∩ の場合
これまでの結果

台１台２台３1,0,1,1,00,01,0,1⊹≩ の事後分布 ≂≥∨∴∻∳∩ ≂≥∨∱∻∳∩ ≂≥∨∳∻∲∩
事後分布からのサンプル

0.67

0.190.81

32

TS の実装• 「事後分布のもとでの各台が期待値ベストな確率」は実際には計算が困難• 単に事後分布≩ ≩ にしたがって ≩ をそれぞれランダムにサンプリングし，それが最大になった台を選択すればよい⊼∨⊹ ≪≸ ∩⊵– 例： 事前分布 ⊼∨⊹≩ ∩ ∽ ≵≮≩≦∨∰∻∱∩ の場合
これまでの結果

台１台２

台３

1,0,1,1,00,0

1,0,1,1⊹≩ の事後分布 ≂≥∨∴∻∳∩ ≂≥∨∱∻∳∩ ≂≥∨∴∻∲∩
事後分布からのサンプル

33

TS の実装• 「事後分布のもとでの各台が期待値ベストな確率」は実際には計算が困難• 単に事後分布≩ ≩ にしたがって ≩ をそれぞれランダムにサンプリングし，それが最大になった台を選択すればよい⊼∨⊹ ≪≸ ∩⊵– 例： 事前分布 ⊼∨⊹≩ ∩ ∽ ≵≮≩≦∨∰∻∱∩ の場合
これまでの結果

台１台２台３

1,0,1,1,00,0

1,0,1,1⊹≩ の事後分布 ≂≥∨∴∻∳∩ ≂≥∨∱∻∳∩ ≂≥∨∴∻∲∩
事後分布からのサンプル

0.58

0.61

0.77

34

TS の意味付け• 期待値ベストでない台を選んでしまった回数を最小化したい• 台 の損失への寄与：
台 がベストな台である事後確率≩≩≰≩ に対して台 を選んだ回数≩≅≛∨誤選択の回数∩≪≦≸≩≧≝ ∽ ∨∱ ⊡ ≰≩∩ ⊣ ≮≩ ∫ ≰≩ ⊣ ∨≮ ⊡ ≮≩∩台 ≩ がベストでない場合 台 ≩ がベストな場合• ２つの項がバランスするのは∨∱ ⊡ ≰≩∩ ⊣ ≮≩ ∽ ≰≩ ⊣ ∨≮ ⊡ ≮≩∩ ∬ ≮≩ ∽ ≰≩≮ のとき– 台 ≩ を計 ≮ 回中 ≰≩ ≮ 回プレイしているのが理想的な状態– 確率 ≰≩ で台 ≩ をプレイすればよい → Thompson sampling

35

UCB との関係 (1/2)
Thompson sampling• 台 が選ばれる確率＝台 がベストである事後確率≰≩≩≩• 台 ≩ が次にプレイされるまでの平均待ち時間 ∱∽≰≩• TS ≒ 前回のプレイから ∱∽≰≩ ラウンド経過したらその台をプレイ(１回プレイ後の待ち時間≪2回プレイ後の待ち時間≪ … なので)
≒ 累計で∱∽≰≩ ラウンド経過したらその台をプレイ＝ 期待値ベストである事後確率が ≰≩ ⊸ ∱∽≮ ならプレイ
UCB 戦略• UCB ＝ 有意水準∱∽≮ で見積もった期待値が大きい台をプレイ≒ 期待値ベストである尤度が ∱∽≮ 以上の台をプレイ

36

UCB との関係 (2/2)• Thompson sampling も UCB も（大雑把には）期待値ベストである尤度（あるいは事後確率）が以上の台を選択∱∽≮– KL-UCB ではこの尤度を Chebycheff の不等式≐≲≛≞⊹≩ ⊷ ≸≝ ⊷ ≥⊡≔≩∨≮∩≄∨≸≫⊹≩∩で大きめに近似– TSでは近似でなく正確な確率がベースになっているので余分な探索がない• 実は漸近展開の知識を使うと≣≐≲≛≞⊹≩ ⊷ ≸≝ ⊼ ≰≔≩∨≮∩ ≥⊡≔≩∨≮∩≄∨≸≫⊹≩∩• だったらUCBでも同種の改良ができる？

37

UCB のチューニング (1/2)• UCBでは「有意水準を ∱∽≮ から ≔≩ ∨≮∩∽≮ に置き換えると（何が何だかよく分からないけど）性能が上がるらしい」というテクニックが昔からまことしやかに伝わっている(Audibert+, 2010, Garivier+, 2011)– 元のKL-UCBスコア：≕≃≂≩ ∽ ≭≡≸≦⊹ ∺ ≥⊡≔≩∨≮∩≄∨≞⊹≩≫⊹∩ ⊸ ∱∽≮≧– チューニングを行った場合（KL-UCB+）：≕≃≂≩ ∽ ≭≡≸≦⊹ ∺ ≥⊡≔≩∨≮∩≄∨≞⊹≩≫⊹∩ ⊸ ≔≩∨≮∩∽≮≧∽ ≭≡≸≦⊹ ∺ ∨≔≩∨≮∩∩⊡∱≥⊡≔≩∨≮∩≄∨≞⊹≩≫⊹∩ ⊸ ∱∽≮≧

38

KL-UCB
TS50• KL-UCB+ も理論限界を達成 (Kaufmann, 2014)

KL-UCB
KL-UCB+
Thompson sampling
asymptotic boundregret100
150• TS は KL-UCB+ と
KL-UCB の中間くらいの性質に

200

UCB のチューニング (2/2)

0KL-UCB+

100

1000
plays

10000

• 一方で TS の事前分布の調整は確率の指数部を≥≸≰∨⊡∨≔≩∨≮∩ ∫ ⊮∩≄∨≞⊹≩≫⊹∩∩ とすることにほぼ対応（→大きな差は出にくい）39

チューニングと最適性の関係• KL-UCB では真の期待値⊹ の尤度をパラメーター ≣ を用いて∨≔≩∨≮∩∩⊡≣ ≥≸≰∨⊡≔≩∨≮∩≄∨≞⊹≩≫⊹∩∩と見積もることで性能をチューニング可• Thompson sampling は≣ ∽ ∱∽∲ に近い• 疑問：– TS では事前分布は全く気にしないでも大丈夫？
– むしろ UCB のチューニングもいつでもOK？
• 答え：どちらもダメな場合がある– ベルヌーイ分布はパラメータが１個かつ有界な特殊ケース

正規分布モデルのThompson sampling40• 分散既知： Jeffreys 事前分布で漸近最適 (Korda+, 2013)• 分散未知： reference・Jeffreys 事前分布ともにダメ
一様事前分布なら漸近最適 (Honda+, 2014)50

Jeffreys• 例：

40reference10

uniform0• 少ない試行回数では逆の結果になりやすい

α = − 1 2 (uniform)
α = 0 (reference)
α = 1 2 (Jeffreys)
asymptotic boundregret2030∨⊹∱∻⊹∲∩ ∽ ∨∱∻∰∩∨⊾∱∻⊾∲∩ ∽ ∨∳∺∰∻∰∺∳∩
事前分布 ⊼∨⊹≩ ∻⊾≩ ∩ ∯ ⊾ ⊡∱⊡∲⊮• ⊮ が大きいと探索減

1

10100
plays

100010000

41

概要• バンディット問題の分類• 報酬最大化のためのアルゴリズム– 理論限界– 決定的アルゴリズム： UCB アルゴリズム– ランダムアルゴリズム： Thompson sampling• 最適腕識別との関係• 種々の拡張

42

regret 最小化との違い• トータル≎ 回のプレイで期待値最大の台を高確率で判定したい• 基本的な方針：ダメそうな台のプレイは早めに打ち切って良さそうな台の比較に専念• よくある間違い：深く考えず regret 最小化のための戦略をそのまま使ってしまう– 通常の UCB や Thompson sampling は期待値最大でない台を回程度しかプレイしない→ プレイ数の偏りが大きすぎる≏∨≬≯≧≎∩– 例えば ≋ ∽ ∲ , 分散既知の正規分布の場合には明らかに両者を同じ回数プレイするのがベスト

43

最適腕識別のための戦略• UCB 等のアルゴリズムは有意水準を ∱∽≮ から ≥⊡≏∨≎∩ にすることで容易に修正可能 (Audibert+, 2010 ほか)• 現時点でベストな台については UCB よりも LUB (LowerConfidence Bound) を基準にするとうまくいきやすい（候補数が多い場合には枝刈りの基準としても有効）• TS は有意水準に対応するものを自由に設定できない– 「期待値最大である事後確率 ≩ が ⊡≏∨≎∩ より大きい台を選択」等の修正は考えられるが， ≩ の計算は大変≰ ≥≰– ただし，モデルが複雑になるとそもそも UCB でも信頼区間の構成が難しい場合があり，そのような場合には TS が相対的に高性能となる場合も

44

概要• バンディット問題の分類• 報酬最大化のためのアルゴリズム– 理論限界– 決定的アルゴリズム： UCB アルゴリズム– ランダムアルゴリズム： Thompson sampling• 最適腕識別との関係• 種々の拡張45

時間発展のある場合• 時刻 とともに各台の報酬分布が変化する （ニュース推薦など）≴• 時間発展のない場合の regret :⊶≮ ⊵≘≲≥≧≲≥≴∨≮∩ ∽≭≡≸ ≦⊹ ≧ ⊡ ⊹≩≩∲≦∱∻⊢⊢⊢∻≋≧≴∽∱≉≴• 時間発展のある場合：⊶≮ ⊵≘≭≡≸ ≦⊹ ≧ ⊡ ⊹≲≥≧≲≥≴∨≮∩ ∽≩∻≴≴∽∱ ≩∲≦∱∻⊢⊢⊢∻≋≧≉≴∻≴– 時間発展のない場合に比べて本質的に難しい– 例) 確率分布が途中で 回だけ変化する場合：
regret がに (Garivier & Moulines, 2011)≭≰≏∨ ≮∩

46

Linear bandit• 取り得る行動（マシン）： ≡ ∲ ≄ ⊽ ≒≤ ( ≄ : 有界集合)– プレイごとに≤ 次元のベクトルをスロットマシンとして選択• 報酬： ≙≴ ∽ ⊵≔ ≡≴ ∫ ⊲≴ ( ⊵ ∲ ≒≤ : 未知パラメータ)• 例： Web デザイン：∰ 広告の大きさ ∱≂≂フォントサイズ≃≃≡≴ ∽ ≂≂≀ レイアウト ≃≃≁∮∮

47

Linear bandit• 取り得る行動（マシン）： ≡ ∲ ≄ ⊽ ≒≤ ( ≄ : 有界集合)– プレイごとに≤ 次元のベクトルをスロットマシンとして選択• 報酬： ≙≴ ∽ ⊵≔ ≡≴ ∫ ⊲≴ ( ⊵ ∲ ≒≤ : 未知パラメータ)• UCB に似たアルゴリズムにより ≲≥≧≲≥≴ ∽ ≏∨≤≬≯≧≮∩ を高確率で達成可能 (Dani, Hayes & Kakade, 2008)– 行動の候補数 ≪≄≪ が大きくても（あるいは無限大でも）パラメータの次元数のみで regret が抑えられる48

Contextual bandit• 各試行ごとに補助情報 (context) ≸≴ が与えられる– 性別・年齢・位置情報・閲覧履歴……，またはエキスパートの助言等• 台 を選んだ場合の報酬：≙≩ ⊻ ≦∨⊢≪⊵≩∻≸≴∩– 例： ロジスティック回帰モデル∱≐≲≛≙≩ ∽ ∱≪≸≴≝ ∽ ∱ ∫ ≥⊵≩≔≸≴≩• bound が保証されるようなものはあまりないが ，ThompsonSampling が高性能

49

Contextual bandit における TS• Contextual bandit（ユーザ情報・閲覧履歴）• クリック率 (CTR: ClickThrough Rate) の比較• ロジスティック回帰モデル[Chapelle & Li, 2011]

50

その他の定式化• Combinatorial bandit– 単位時間ごとに複数本の腕（広告等）を選択– 単に期待値の和を最大化する・多様性を考慮する，等の目的の設定• Dueling bandit– 単位時間ごとに２つの候補を選択して優劣のみが提示される(映画の好み等)• Gaussian process 上の bandit– 腕の候補が大量 or 無限個ある （パラメータの最適化等）
といった場合で最近成功している

51

まとめ
• UCB :
– 有意水準をモデルに応じて適切に設計する必要– ある程度性質の分かっているモデルならチューニング次第で非常に高性能に– 最適腕識別にも自然に適用可能• Thompson sampling:– 理論限界を介さずにある程度自然な意味付けが可能– （事後分布からのサンプリングが出来れば）簡単に実装可能– 事前分布の選択にも左右されにくい（が，未知の部分も多い）– 最適腕識別には使いにくい52

References
概説• S. Scott, “A modern Bayesian look at the multi-armed bandit,” Applied
Stochastic Models in Business and Industry, 2010.
• S. Bubeck and Nicolo Cesa-Bianchi, “Regret Analysis of Stochastic andNonstochastic Multi-armed Bandit Problems,” Fundations and Trends inmachine Learning, 2012.
Thompson samplimg (理論)• E. Kaufmann, N. Korda and R. Munos, “Thompson sampling: anasymptotically optimal finite-time analysis”, ALT2012.
最適腕識別• J. Audibert, S. Bubeck and R. Munos, “ Best Arm Identification in MultiArmed Bandits”, COLT2010.

53References
Linear bandit• V. Dani, T. P. Hayes and S. M. Kakade, “Stochastic Linear
Optimization under Bandit Feedback”, COLT 2008.
Combinatorial bandit• Y. Gai, B. Krishnamachari and R. Jain, “Learning Multiuser Channel
Allocations in Cognitive Radio Networks: A Combinatorial Multi-Armed
Bandit Formulation”, IEEE DySPAN 2010.
Gaussian process 上のバンディット• N. Srinivas, A. Krause, S. Kakade, and M. Seeger, “InformationTheoretic Regret Bounds for Gaussian Process Optimization in theBandit Setting”, IEEE Transactions on Information Theory, 2012.