狠狠撸

多腕バンディット問題と処置効果の推定:
最适腕识别と多重検定
情報理工学系研究科コンピュータ科学専攻
修士課程2年加藤真大
Aug. 21th, 2019
1

発表の概要
多腕バンディット問題（Multi-armed Bandit Problem; MAB）と処置効果（Treatment Effect）
の推定に関する代表的な手法と最近の知見の紹介．
? 本発表では因果効果をある２つの処置に対する効果の差として定義（詳細は後述）．
?問題：逐次的に得られる情報からどのように「筋のいい」推論を行うか．
今回の発表のトピック
? ２つの問題設定：期待報酬最大化と最適腕識別．
? 最適腕識別の代表的な手法．
? 最适腕识别と多重検定．
※ 時間の都合上，理論的詳細は可能な限り省略します．
2

多腕バンディット問題
Aug. 21th, 2019 @CFML勉強会
3

多腕バンディット問題
多腕バンディット問題（Multi-armed Bandit Problem; MAB）：
? 期間? = 1,2, … .と?個のスロット（腕）が与えらている状況を考える．
? 各期において?個の腕のなかから一個を選ぶことができる．
? その腕はある確率分布に従ってプレイヤーに報酬を与える．
?最善の腕を探すためには各腕を適当に選んで探索（パラメータの推定）する必要がある．
探索（exploration）と最善の腕を引き続けること（exploitation）のバランスを最適化．
4

MABにおける２つの問題設定
? 各腕? = 1,2, … , ?からの報酬の確率分布??とし，報酬の期待値を??で表す．
? 期待値最大の腕：?? = arg max
?∈ 1,2,…,?
??．
? MABにおける２つの問題設定．
?累積報酬最大化（累積損失最小化）：
? ナイーブな設定では，期待値最大の腕??
，もしくは期待値最大の腕に限りなく近い期待値
の腕をできる限り多く引いて累積報酬を最大化することに関心がある．
?最適腕識別：
? なるべく少ない総選択数で期待値最大の腕??を高確率で識別することに関心がある．
5

最適腕識別
?固定予算の最適腕識別問題
? 総選択数（腕を引ける回数）が?回までと固定されている．
? プレイヤーの目的：合計?回腕を引いた後に??の推定値 ??(?)を回答し，その誤り確率（誤
識別率）?? = ?[ ??
? ≠ ??
]を最小化すること．
?固定信頼度の最適腕識別問題
? 総選択数をプレイヤーが可変で決められる．
? 事前に定められた? ∈ (0,1)に対して，誤識別率が?以内になるまで選択を続ける．
? 探索を終了するための停止時刻を適切に設定する必要がある．
? プレイヤーの目的：設定した停止規則のもとでの停止時刻を?とする時，? ?? ? ≠ ?? ≤
?を満たしつつ，?[?]を小さくする方策を構成すること．
6

累積報酬最大化との違い
? ? = 2本の腕からの報酬がそれぞれ分散既知の正規分布? ??, ?2 に従うとし，固定予算?
での最適腕識別を考える．?1 > ?2と仮定する．
? 最適方策：両方の腕を?/2回ずつ引いた後に標本平均 ??が大きい腕を最適腕とする．
? 誤識別率?? = ? ?～? ?2??1,4?2/? ? ≥ 0 = 1 ? Φ
? ?1??2
2?
≈ exp ?
? ?1??2
2
8?2 .
? 誤識別率の指数関数的な減衰 ? 累積報酬のregret = ?1 ? ?2 ?/2: 線形オーダー
? 累積報酬のリグレットではlog ?のオーダーになるアルゴリズムが知られている．
?語弊を恐れずに言えば，この違いは一番いい腕を発見するための努力に起因する．
累積報酬最大化の場合には，二番目以下の腕と僅差の一番いい腕を発見するために多くの
施行を必要とするぐらいなら，早々に切り上げて現状良さそうな腕を選んだ方がいい．
7

固定信頼度の最適腕識別の手法
8

最適腕識別の問題設定
? ? 個の処置（腕）と各期?においてそれらから1つを選ぶ．
? プレイヤーは各期?において? ∈ ? ? 1, … , ? を選び，報酬??,? ～ ??(?)を観測する．
? ??,? ∈ [0,1] かつ? ??,? = ??とする．
? ??(?): ?期までに腕?が引かれた回数．
? 期待報酬の差をΔ? = ??? ? ??とする．
? 文脈によってはこの差を処置効果や因果効果と呼ぶこともできる．
? 厳密に最適腕argmax
?
??を発見することは難しいので，「期待値が?? = max
?
?? ? ?以上
の腕を１つ以上発見する」という?-最適腕識別の問題を考えることにする．
?したがって，全てのアルゴリズムで信頼度?（ ? ??
? ≠ ??
≤ ? ）と?をハイパーパラ
メータとして事前に定める必要がある．
9

固定信頼度の最適腕識別の手法
? 固定信頼度の手法．
ある一定の誤識別率を達成する腕が1本になるまで引き続ける．
? 一様選択に基づく方法：逐次削除方策
? スコアに基づく方法：LUCB方策，UGapEc方策， lil’UCB方策
? 固定予算の手法
ある与えられた予算の範囲内で誤識別率を最小化する．
10

一様選択
? 腕の数が２本あり，２本の報酬の分散が等しい時には一様に（同じ確率で）腕を選ぶこ
とが最適になる．
? 無作為化比較実験と同じ．
? 分散が異なる場合，標準偏差の比で重みづけて，より分散の大きい腕を選ぶ方が良い．
（分散を推定して腕を選ぶ方法を後述する）
よって，最適腕である可能性が残っている腕を一様に選択していく方式が考えられる．
? 最適腕である可能性の低いものから順に削除していく．
→ 逐次削除方策．
11

逐次削除方策のアルゴリズム
? 入力：許容幅? ≥ 0, 誤識別率? > 0.
? パラメータ：? ?, ? : ? × 0,1 → 0, ∞ .
? ? ← 1,2, … , ? , ? ← 1.
? loop
?に含まれるすべての腕を1回ずつ引く．
各腕? ∈ ?のUCB?LCBスコア ??,? = ??,? +
? ?,?
2?
, ??,? = ??,? ?
? ?,?
2?
を計算．
? ? ← arg max
?∈?
??,? .
if ?? ?,? + ? > max
?≠ ? ?
??,? then
? ?を出力して終了．
else if ?? ?,? > ??,?なる? ≠ ? が存在 then
そのような?を全て?から削除
? ← ? + 1. 12

SR方策の実験１
? 候補として残っている腕の数の減少の挙動を確認した．
Qiita: https://qiita.com/MasaKat0/items/9cc8ba8ff2117f45427e
13
サンプル数
擬似データの作成候
補
と
し
て
残
っ
て
い
る
腕
の
数

SR方策の実験２
? 候補として残っている腕の数の減少の挙動を確認した．
14
候
補
と
し
て
残
っ
て
い
る
腕
の
数
サンプル数
擬似データの作成

UCB?LCB
前ページで現れたUCB (Upper Confidence Bound) ?LCB (Lower Confidence Bound)とは．
? 多腕バンディット問題でよく現れる概念．
? 引かれた回数の少ない腕の報酬の推定量を楽観的（悲観的）に見積もる．
? どのように見積もるのか？
? 確率集中不等式
Hoeffdingの不等式：確率変数の区間．
Bernsteinの不等式：分散．
? KLダイバージェンス（Chernoff? Hoeffdingの不等式）：分布の情報が必要．
? 繰り返し対数の法則（law of the iterated logarithm, LIL）．
15

腕へのスコアリング
? 一様選択を行うと無駄に多くの腕を引く可能性がある．
?そこでまず最適腕を予想し，ついで最適腕の候補の腕のLCBとそれ以外の腕のUCBとの差
が早く広がるように腕を選ぶ方策を考える．
推定された最適腕の期待値の下限：?? ?(?)，それ以外の腕の期待値の上限： ?? ?? ?
? ???? = ?? ? ? ? ?? ?? ? が早く大きくなってほしい．
? ????が?より大きくなれば良い．
16
最適腕
報
酬
腕
LCB
UCB
ここの差を広げていく．
現時点での最有力候補と
その次の候補を引き続ける．

LUCB方策のアルゴリズム
? 入力：許容幅? ≥ 0, 誤識別率? > 0.
? パラメータ：? ?, ? : ? × 0,1 → 0, ∞ .
? すべての腕を1回ずつ選択．? ← ?.
? loop
各腕?のUCB?LCBスコア ??(?) = ??(?) +
? ?,?
2? ? ?
, ??(?) = ??(?) ?
? ?,?
2? ? ?
を計算．
? ? ← arg max ??,? , ? ?? ← arg max
?≠ ? ?
??(?) .
if ?? ?? ? < ?? ?(?) + ? then
? ?を出力して終了．
else
腕 ? ? と腕 ? ?? を引く． ? ← ? + 2.
17

より効率的なスコアリングに基づく方策
? LUCB方策はスコアリングによって一様選択で発生する余分な施行を減らそうとした．
? しかし，「腕 ? ? と腕 ? ?? を引く」というプロセスが入っているために，逐次削除方策とは
逆に最適腕の選択数が過度に多くなってしまうという問題が生じる．
? UGapE方策では，反復ごとに腕 ? ?
と腕 ? ??
のうちサンプル数が小さい（期待値の不確かさ
が大きい）もののみを選択する．
V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: a unified approach to fixed
budget and fixed confidence. NeuIPS, 2012.
18

UGapEc方策のアルゴリズム
? 入力：許容幅? ≥ 0, 誤識別率? > 0.
? パラメータ：信頼度?? ?, ? : ? × 0,1 → 0, ∞ .
? すべての腕を1回ずつ選択．? ← ?.
? loop
各腕?のUCB?LCBスコア ??(?) = ??(?) +
?? ?,?
2? ? ?
, ??(?) = ??(?) ?
?? ?,?
2? ? ?
を計算．
? ? ∈ arg min
?∈ 1,2,…,?
max
?≠?
??(?) ? ? ?(?)
Pull ? ?
←. arg max ? ? ?, ? , ?? ?, ? ，ただし? = arg max
?≠? ?
? ?(?)， ? = arg max
?∈? ?
??(?)．
if max
?≠?
??(?) ? ? ? ? ≥ ? for ? ∈ ?(?) then
? ? を出力して終了．
else
? ← ? + 1.
19

LUCB方策とUGapEc方策の実験１
? ????がどのくらいの速さで小さくなるか実験した．
20
????
サンプル数
擬似データの作成

LUCB方策とUGapEc方策の実験１
? LUCB方策とUGapEc方策とで腕が停止するまでどの腕がどの程度引かれるかを示した．
LUCB方策では最適腕である腕0を（余分に）引きすぎていることがわかる．
21
腕
を
引
い
た
回
数
腕の番号
LUCB方策鲍驳补辫贰肠方策

標本複雑度からみた最適腕識別
? 標本複雑度：最適腕を発見するまでに必要なサンプルサイズ．
? 標本複雑度が小さいアルゴリズムほどいいアルゴリズム（早く最適腕を見つけられる）．
? 最適腕??の報酬の期待値??とそれ以外の腕?の報酬の期待値??との差をΔ?とする．
? これまでに述べた方策はおおよそ ?≠?? Δ?
?2
log Δ?
?2
程度のオーダーを持つ．
? つまり，最適腕とそれ以外の腕の報酬の期待値の差が小さくなるにつれて，以下のよう
に標本複雑度が増大する．
22

タイトなConfidence Bound: LIL
? その後の研究でアルゴリズムを改善すれば ?≠?? Δ?
?2
log log Δ?
?2
ぐらいのオーダーを達成
できることが分かった．これは ?≠?? Δ?
?2
log Δ?
?2
との比較で以下のような図で表せる．
? この結果，UCBやLCBのバウンドが緩い（楽観的or悲観的すぎる）可能性が指摘された．
? Hoeffdingの不等式よりもタイトなバウンドとして繰り返し対数の法則（law of the iterated
logarithm, LIL）を用いたものが以下の論文で提案された．
Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil’ucb: An optimal
exploration algorithm for multi-armed bandits. COLT, 2014.
23
Δ?
?2
が大きくなってもlog log であれば
サンプルサイズの増加は緩やか．

繰り返し対数の法則
? {??}を平均0と時間を通じて均一な分散?2の分布からのi.i.d.なサンプルとする．
?? = ?=1
?
??に対して，lim
?→∞
sup
±??
2?2 ? log log ?
= 1, a. s.
24
標準正規分布に従うサンプルを3000期間生成．
→
?3
2?23 log log 3
, … ,
?3000
2?23000 log log 3000
をプロット．
以上の確率過程を30個表示．
（左図の異なる色の確率過程）

標本複雑度の下界
? 報酬の差がΔの２つの腕を比較するとき，それぞれ等確率で引いて２つの腕の累積和の差
を確率変数とするとドリフトΔの確率過程を構築できる．
? この確率過程の分散を1とする．
? ?Δ = 2? log log ? の時，LILのバウンドを破る．?について解くと? ≈ 2Δ?2 log log Δ?2．
25
2? log log ?
平均1，分散1の正規分布に従うサンプルを1000期間生成．
→
?3
2?23 log log 3
, … ,
?1000
2?23000 log log 1000
をプロット．
以上の確率過程を10個表示．
（左図の異なる色の確率過程）
ここでΔ = 1であり，もしΔ = 0であるならば確率変数の
和が（漸近的には）超えないはずの黒線 2? log log ? を，
およそ2Δ?2
log log Δ?2
サンプルぐらいで破る．
→ 効果の有無を2Δ?2
log log Δ?2
サンプルほどで発見．
2Δ?2 log log Δ?2

lil’UCB方策の直観的説明
? lim
?→∞
sup
±??
2?2 ? log log ?
= 1の式から，平均?のある腕?の?期までの報酬の和??,? = ?=1
?
??,?に
対して，直観的かつ漸近的に次のような式が成り立つ．
??,?
?
≥ ? ?
2?2 log log ?
?
? ? ≤
??,?
?
+
2?2 log log ?
?
? つまり，
??,?
?
+ 2?2 ? log log ? ぐらいに見積もっておけば，平均?はそれ以下になる．
? この性質を用いてUCBを構築することができる．
? lil’UCB方策には以下の優れた性質がある．
? 通常の（期待報酬最大化の）アルゴリズムでΔ?2
log log Δ?2
のオーダーの標本複雑度を達
成できる．
? さらに期待報酬最大化のregretもlog ?のオーダーに従う．
つまり，最適腕識別としても高性能であり，かつ，期待報酬最大化にも使える（非推奨）．
26

lil’UCB方策のアルゴリズム
? ??,? ? ?
?
1
? ? ? ?=1
? ? ?
??,?
? lil’ UCB algorithm:
? 入力：信頼度? > 0，パラメーター?, ?, ? > 0．
? 初期化：それぞれの腕を一回サンプルする．??(?) = 1とする．? = ?とする．
? while ?? ? < 1 + ? ?≠i ??(?) for all ?
? ? = arg max
?∈ 1,…,?
??,? ? ? + 1 + ? 1 + ?
2?2 1 + ? log
log 1 + ? ?? ?
?
??(?)
.
腕 ? ?
を引く． ?? ? ? ← ?? ? ? + 1． ? ← ? + 1．
? else arg max
?∈ 1,…,?
??(?)を出力．
27

方策の比較
? 一様選択に基づく方法とスコアに基づく方法の比較
? 全ての腕で分散が等しく，腕の数が少ないときには一様選択の手法は有効．
? 腕の数が多い時に一様選択すると無駄に色々な腕を引くので，早めにスコアに基づいて
（ざっくりと）腕の候補を絞り込む必要がある．
? 一様選択に基づく方法の問題点
? 腕ごとに報酬の分散が違う場合は？→ 次のスライド．
? スコアに基づく方法
? LUCB方策では推定された最適腕 ??
を毎回引く→最適っぽい腕を多く引きすぎる．
? UGapE方策ではLUCB方策を改善し，最適腕の候補を複数選び，よりサンプル数が少ない
ものから腕を選択する．
? lil’UCBでは理論的に可能なギリギリのバウンドを作ってUCBアルゴリズムを動かすことで，
理論的に優れた性能を発揮する．
? 個人的には逐次削除方策が実装が簡単かつそこそこの性能なのでそれで十分な気も．
? 最適腕識別が失敗しても逐次削除方策は無作為化実験として機能する？ 28

適応的実験計画
? 最適腕識別のバンディットは，A/Bテストの他に，医療系で用いられる適応的実験計画と
も関係が深い．
適応的実験計画とは「試験の妥当性と完全性を損なうことなく，試験開始後に，そのいく
つかの特性を変更または修正することを許容する（実験の）デザイン」である．
? 前述した腕の分散が異なる場合の一様選択の議論も行われている．
? このような適当的実験は適当に行うとi.i.d.の仮定が崩れるので注意が必要．
? バンディットの例で言えば，前に引いた腕によって次に引く腕が影響を受ける．
Efficient Counterfactual Learning from Bandit Feedback, Narita, Yasui, and Yata, AAAI 2019もこの
辺を回避しようと頑張っている．
?i.i.d.の問題をうまく回避して分散と腕を引く重みを調整する手法が経済学の分野で提案さ
れている．
29

漸近効率な適応的実験計画
Hahn, Hirano, and Karlan. Adaptive Experimental Design Using the Propensity Score, Journal of
Business and Economic Statistics, 2009.
? HIR推定量（IPWとしばしば混同される）を用いて処置効果を処置効果を推定する．
? ?
HIR
=
1
?
?=1
?
? ?? = 1 ??
? ?? = 1|??
?
? ?? = 0 ??
? ?? = 0|??
.
? この時， ? ?? = 1|?? を以下の値にすると ? ?
HIR
の分散を小さくできる．
?OPT ?? = 1 ?? =
???(??
2
1 |??)
???(??
2
1 |??) + ???(??
2
0 |??)
.
? ただし， ???(??
2
1 |??)と???(??
2
0 |??)は未知．
? ?個のサンプルを２つに分ける．
１つ目のサンプルで?OPT
?? = 1 ?? を無視して???(??
2
1 |??)と???(??
2
0 |??)を推定.
２つ目のサンプルで?OPT ?? = 1 ?? に基づいて処置を割り振る（一様選択ではない）．
30

31

Jamieson, Kevin G and Jain, Lalit, A Bandit Approach to Sequential Experimental Design with False
Discovery Control, NeuIPS, 2018.
? 最適腕識別の多腕バンディット問題の手法と多重検定の手法を統合．
? 最適腕識別の多腕バンディット問題を統計的仮説検定の枠組みに拡張．
? 検定によって生じる多重検定の問題を考慮したアルゴリズムを提案．
アイデア：有意でない処置を有意であるとしてしまう割合（false alarm, false positive, 偽陰性，
第一種の過誤）を制御しつつ，少ないサンプルで処置効果が有意そうな腕を検出．
32

問題設定と仮説
? ? 個の処置（腕）と各期?においてそれらから1つを選ぶ．
? プレイヤーは各期?において? ∈ ? ? 1, … , ? を選び，報酬??,? ～ ??(?)を観測する．
? ??,? ∈ [0,1] かつ? ??,? = ??とする．
? ??(?): ?期までに腕?が引かれた回数．
? 既知の?0に対して以下の集合を定義する．
?1 = ? ∈ ? : ?? > ?0 , ?0 = ? ∈ ? : ?? = ?0 = ? ? ?1
? 処置? ∈ [?]に対する期待値?? と集合?1のサイズは未知である.
?集合?1に属する腕: ?0より大きい期待値を持つ．
?集合?0に属する腕: ?0と等しい期待値を持つ＝帰無仮説．
各期?においてプレイヤーは腕を要素とする集合?? ? [?]を返す．これは帰無仮説を棄却し
た腕の集合である（? ∈ ?? ならプレイヤーは? ∈ ?1と考えている）．
33

具体例? 広告の種類が?種類ある．
? 期待クリック率が?0 = 0である広告と，そうでない広告とに分けたい．
?1 = 期待クリック率が0より大きい広告 , ?0 = 期待クリック率が0の広告
? 期待クリック率が0より大きい広告がどのくらいあるか分からない（ ?1 が未知）．
? 有意水準?で１つ１つの広告?に?0? ∶ ?? = ?0検定しても，期待クリック率が0の広告が沢
山あると，誤って?0? を棄却する確率は?よりも大きくなる．
ナイーブに最適腕識別を用いて期待クリック率が0より大きい広告を発見しようとすると，
期待クリック率が0の広告を期待クリック率が0より大きい広告とする確率が高くなる．
→ 第1種の過誤
? 一方で，保守的すぎると期待クリック率が0より大きい広告を発見できないので，一定の
偽陰性を超えないように広告を期待クリック率が0より大きいと判断することが必要．
34
帰無仮説を保留帰無仮説を棄却
真の帰無仮説 ?? ∩ ?0 ?? ∩ ?0
偽の帰無仮説 ?? ∩ ?1 ?? ∩ ?1
合計 ? ? ?? = ?? ??
第1種の過誤

前章までの最適腕識別との違い
? 前章までの固定信頼度の最適腕識別：最適な腕は1個．
? Jamieson and Jain (2018): 最適な腕は複数存在する．
? 最適な腕が?本存在する場合，トップk多腕バンディット問題と呼ばれる．
トップk多腕バンディット問題では最適な腕が?個あることを知っている（? = ?1 ）．
?Jamieson and Jain (2018)では最適な腕の本数も分からない．
35

多重検定
? 全ての? = 1,2, … , ?, ? < ?に対して，
?0: ?1 = ?2 = ? = ? ? = ?0.
が成り立つとする．
? ?0を有意水準?で検定したいとする．
? そのために?? = ?0を? = 1,2, … , ?に対して個別に検定することを考える．
? 帰無仮説?0,?: ?? = ?0を個別に有意水準?の検定をした場合，１つ以上の帰無仮説?0,?が
棄却される確率は?以上になる．
36

多重検定の例
? 比較対象が３群以上存在して，検定の多重性の問題が生じる事例．
? 3群（?,?,?）を比較するとき「全体としての有意水準」を 5%で検定したいとする．
? ?と?，?と?について有意水準5%の2標本t検定を2回繰り返す．
? 母平均をそれぞれa, b, cとする．
? ? = ? and ? = ?，つまり? = ? = ?を満たしているなら，2つの帰無仮説のうちどちらか
一方が棄却されると? = ? = ?という帰無仮説は棄却されることになる．
? このとき，帰無仮説が棄却される確率は約9%であり，設定した5%より大きい．
? 多重検定：このようなことが起こらないように「全体としての有意水準」をあらかじめ
宣言した値に制御できるように一回一回の検定における個々の有意水準を調整．
37

統計的検定と偽陰性
? 可能な限り小さな? ∈ ?に対して，偽陰|?? ∩ ?0 | の数を全ての期間t ∈ ?で一定の値以下
に保ったまま，全ての?≥?において|?? ∩ ?1 | のサイズが|?1|と近似的に等しくなるような
アルゴリズムを構築することを目指す．
? 「偽陰|?? ∩ ?0 | の数を全ての期間t ∈ ?で一定の値以下に保つ」ことの「一定の値」と，
? 「全ての? ≥ ?において|?? ∩ ?1 | のサイズが|?1 |と近似的に等しくなる」ことの「近似」
について以下に述べるような指標が知られている．
38
??：アルゴリズムが帰無仮説を
棄却した選択肢の集合．
?0：効果のない選択肢の集合．?1：効果のある選択肢の集合．

偽陰性の制御
? 偽陰性を制御する指標について説明する．
39
? ∈ (0,1)は固定された値である．あるアルゴリズムにおいて全ての問題( ?? ?=1
?
, ?0)と全て
の? ∈ ?に対して?
??∩?0
?? ∨1
≤ ?が成立するとき，そのアルゴリズムはFDR-?である．
? ∈ (0,1)は固定された値である．あるアルゴリズムにおいて全ての問題( ?? ?=1
?
, ?0)に対し
て? ∪ ?=1
∞
?? ∩ ?0 ≠ ? ≤ ?が成立するとき，そのアルゴリズムをFWER-?である．
定義1 （False Discovery Rate, FDR-?）
定義2 （Family-wise Error Rate, FWER-?）

指標の解釈
Family-wise Probability of Detection （FWER）: ? ∪ ?=1
∞
?? ∩ ?0 ≠ ? ≤ ?
? 腕が何本あっても第1種の過誤が１つでも起こる確率が?を超えない．
? 非常に保守的 → 有意な腕を棄却しない第2種の過誤が起こりやすくなる．
False Discovery Rate（FDR）: ?
??∩?0
?? ∨1
≤ ?
? 棄却された全ての腕に対して第1種の過誤が起こる数の比率の期待値が?を超えない．
※ FWERの方がFDRよりも厳しい．
40
帰無仮説を保留帰無仮説を棄却
真の帰無仮説 ?? ∩ ?0 ?? ∩ ?0
偽の帰無仮説 ?? ∩ ?1 ?? ∩ ?1
合計 ? ? ?? = ?? ??
??：アルゴリズムが帰無仮
説を棄却した選択肢の集合．
?0：効果のない選択肢の集合．?1：効果のある選択肢の集合．
?? ∩ ?0
??

FWERとBonferroni法
? Bonferroni法はFWER制御のための手法の１つ．
? 個々の検定の有意水準を仮説の数で割る．
? 例えば全体の有意水準が?で仮説の数が?なら?/?．
? 原始的な実装の例として，腕に対し均一に処置を振り，それぞれの腕のp値??を調べる．
??: 全ての? ∈ (0,1]と? ∈ ?0 に対して?0 ?? ≤ ? ≤ ?．
?0は帰無仮説が正しい時の腕の報酬に関数する確率分布．
? ここで，p値??を用いて帰無仮説を棄却するルールを考える．
? Bonferroni法: p値?1 ≤ ?2 ≤ ? ≤ ??の集合に対して次のような?の帰無仮説を棄却する．
? ?? = ?: ?? ≤ ?/? .
41

FWERとFDR
? FWER（ ? ∪ ?=1
∞
?? ∩ ?0 ≠ ? ≤ ? ）はFDR（ ?
??∩?0
?? ∨1
≤ ? ）も制御する．
?
? ?? ∩ ?0
? ?? ∨ 1
≤ ? ? ?? ∩ ?0 ≤ ? ∪?∈?0
?? ≤ ?/? ≤ ?
?0
?
≤ ?.
→ FDRの方が条件が緩いので，FDRだけ考える時にはFDRに焦点を当てた手法を考えること
で，より高い検出力を達成しうる．
? FWERは保守的すぎる可能性がある．
? もう少し偽陰性の基準をゆるくすれば，より有意な腕を発見しやすくなる．
42

FDRとBenjamini-Hochberg法
1995年にBenjaminiとHochbergがfalse discovery rateを調整する方法（BH法）を発表．
? ?期における腕?のp値を??,? ?(?)とする．??(?)は腕?を?期までに引いた回数．
1. ?個の帰無仮説をp値の昇順に並べる．
?(1),? 1 (?) ≤ ? 2 ,? 2 ? ≤ ? ≤ ? ? ,? ? ? .
2. ? = max ?: ?(?),? ? (?) ≤ ?
?
?
,
3. 次の集合の腕を棄却する．? ?? = ?: ??,? ?(?) ≤ ?
?
?
.
FDRは腕の数が多くて，帰無仮説が棄却される数（ ?? ）が多い場合に有用．
? ?
? ?∩?0
? ? ∨1
の値はq値とも呼ばれる．
? 直観：?(?),? ? (?) ≤ ?
?
?
? ? ≤
?(?),? ? (?)×?
?
．?(?),? ? (?) × ? ≈ ?? ∩ ?0 ， ? ≈ ?? ∨ 1．
? 問題点：p値の分布に一様分布を仮定する必要などがある．
43

lil’UCB方策+BH法のアルゴリズム
? lil’IUCBアルゴリズムに基づいて棄却されていない腕の中（ ? ? ??）から腕を引く．
? BH法を適用して検定する．
実際のアルゴリズムは以下のように理論に基づいて細かくパラメータが設定されている．
44

全体のまとめ
? 多腕バンディット問題を用いて最適な腕（もっとも良いアイテム）を発見する．
? 最適腕識別の代表的手法
? 腕の数が多いと，一様に選択するアルゴリズム（SR方策）は余分に引く腕が多くなる．
? スコアリングを行なって引く腕の候補を絞っていく場合，最適腕と次善の腕の差を縮め
ることで効率的に腕を発見する（LUCB方策，UGapEc方策）．
? スコアリングをする際の信頼区間をLILに従って設定すると理論的に最小限のサンプルサ
イズで最適腕を発見できる（lil’UCB方策）．
? 最適腕の数が複数ある場合：最適腕の数を知っている場合
? トップk最適腕識別の手法
? 最適腕の数が複数ある場合：最適腕の数を知らない場合
? 統計的検定と組み合わせる必要がある．
? 検定の多重性の問題が生じる．
? 偽陰性の制御方法を決めてその制御のもとでlil’UCBを動かす．
45

参考和書
- 「バンディット問題の理論とアルゴリズム」本多?中村，2014年
- 「現代数理統計学の基礎」，久保川，2017年
- 「多重比較法の理論と数値計算」，白石?杉浦，2018年
- 大阪大学大学院医学系研究科の資料：
http://www.med.osaka-u.ac.jp/pub/kid/clinicaljournalclub1.html
46

参考洋書
- V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: a unified approach to fixed
budget and fixed confidence. In Advances in Neural Information Processing Systems (NIPS), 2012.
- K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. lil’UCB: an optimal exploration algorithm for
multi-armed bandits. In Conference on Learning Theory (COLT), 2014.
- Jamieson, Kevin G and Jain, Lalit, A Bandit Approach to Sequential Experimental Design with
False Discovery Control, NeuIPS, 2018.
- Hahn, Hirano, and Karlan. Adaptive Experimental Design Using the Propensity Score, Journal of
Business and Economic Statistics, 2009.
- Efficient Counterfactual Learning from Bandit Feedback, Yusuke Narita, Shota Yasui, and Kohei
Yata, AAAI 2019
47

狠狠撸

最适腕识别と多重検定

More Related Content

最适腕识别と多重検定