試行回数の少ない悪腕存在チェックアルゴリズム
Bad Arm Existence Checking Algorithms with Small Sample Complexity
田畑公次
1∗中村篤祥
1本多淳也
2小松崎民樹
1Koji Tabata
1Atsuyoshi Nakamura
1Junya Honda
2Tamiki Komatsuaki
11
北海道大学
1
Hokkaido University
2
東京大学/理化学研究所
2
University of Tokyo/RIKEN
Abstract: In the loss version setting of a K-armed stochastic bandit problem, given a thresholdτ, (∆,δ )-bad arm existence checking algorithms is those that outputs “positive” with probability at least 1−δ if the mean loss of some arm is larger thanτ+∆, and outputs “negative” with probability at least 1−δif the mean losses of all arms are smaller thanτ− ∆. We analyze sample complexity of a family of algorithms that use the same stopping condition and compare the number of samples needed for three different arm-selection policies in simulations.
1
はじめに
病気や機械の故障の診断などでは，どこか一箇所で も異常があると問題があるものと診断される．そのよ うな診断では，最初に異常が見つかった時点で診断を 打ち切って，異常ありと結論づけることができる．こ のように異常のあるなしをできるだけ速く診断する問 題は，腕を引く毎に損失を被る，損失版 K 腕バンディッ ト設定において，損失平均がある閾値以上である腕が 存在するか否かを，できるだけ少ない試行回数 (腕を引 く回数) で判定する「悪腕存在チェック問題」として定 式化できる [5]． 悪腕存在チェック問題では，与えられた閾値τとグ レイゾーン幅1∆ > 0 に対し，損失平均µがτ+∆ より 大きければ正の腕，τ−∆ より小さな場合は負の腕とす る．与えられた許容誤り確率δ> 0 に対し，正の腕が 存在する場合には 1−δ 以上の確率で「正」，負の腕し か存在しない場合は 1−δ以上の確率で「負」と出力す るアルゴリズムを (∆,δ)-悪腕存在チェックアルゴリズ ムと呼び，できるだけ試行回数が少ない (∆,δ)-悪腕存 在チェックアルゴリズムの開発を目標とする．この設定 に近い研究としては，Locatelli らの閾値バンディット問 題 [4] がある．閾値バンディット問題が悪腕存在チェッ ク問題と異なる点は，すべての正と負の腕を正しく識 ∗連絡先： 北海道大学電子科学研究所 北海道札幌市北区北 20 条西 10 丁目 E-mail: [email protected] 1[τ−∆,τ+∆] をグレイゾーンとし，平均損失がこれに含まれる腕 は正でも負でもない中間と定義する．∆ は閾値バンディット [4] では 精度 (precision) と呼ばれεで表されている．) 別する問題であること，及び固定試行回数で誤識別確 率 (正と負の腕の中で誤識別される腕が存在する確率) 最小化を目標とすることが挙げられる．Kano らの良腕 識別問題 [2] は，∆ = 0 の設定で，固定信頼度 (与えら れたδ> 0 に対し，1−δ の確率) で正腕のみを全て出 力するアルゴリズム (δ-PAC アルゴリズム) を扱うが， 正腕の数以下の任意の正整数λ に対し，正腕と予測さ れる腕をλ 本出力するまでの試行回数τλ の最小化を 目標とする．良腕識別においては，与えられた正整数 λ に対し，正腕の数がλ 以上であれば，1−δ 以上の 確率で正腕のみをλ本出力し，正腕の数がλ 未満であ れば，1−δの確率で正腕のみをすべて出力して停止す るアルゴリズムは，(λ,δ)-PAC アルゴリズムと呼ばれ る．良腕識別問題の (1,δ)-PAC アルゴリズムは，正腕 と予測される腕を出力した場合は「正」，何も出力せ ずに停止した場合は「負」と出力するように変えれば， (0,δ)-悪腕存在チェックアルゴリズムになるが，(0,δ )-悪腕存在チェックアルゴリズムは，出力情報不足のた め良腕識別問題の (1,δ)-PAC アルゴリズムに変形する ことはできない．負の腕を誤って正の腕と認識しても， 他に正の腕がある場合は，悪腕存在チェック問題では正 しい出力をするが，良腕識別問題では正しい出力は得 られない．これらのことから，悪腕存在チェック問題は 良腕識別問題より簡単な問題であり，より少ない試行 回数のアルゴリズムが存在する可能性があるといえる． 本稿では (∆,δ)-悪腕存在チェックアルゴリズムにおい て，グレイゾーン幅∆ > 0 がある程度大きい場合に，腕 の正負の判定を少ないサンプル数で行える腕判定規則を もつアルゴリズムのサンプル複雑度を分析する．また， 人工知能学会研究会資料 SIG-FPAI-B509-16３つの類似問題に用いられた方策 APT[4]，LUCB[1], HDoC[2] を腕選択方策として採用した (∆,δ)-悪腕存在 チェックアルゴリズムの停止までのサンプル数を，シ ミュレーション実験により比較する．
2
準備
∆ ∈ [0,1/2) に対し，τ∈ (∆,1 − ∆) を閾値とする，以 下のような閾値バンディット設定を考える． 腕 1, ..., K とし，プレイヤーは各時刻 t = 1, 2, . . . に K 個の腕のどれか 1 つの腕 itを引く．任意の腕 i∈ {1,...,K} に対し，腕 i を n 回目に引いたとき損失 Xi(n)∈ [0,1] を生ずるものとする．ただし，Xi(1), Xi(2), . . . は平均が µi∈ [0,1] の確率分布νiに従う確率変数の i.i.d. シーケン スとする．また，異なる２腕 i, j(i̸= j) に関しては，任意 の (s,t)∈ {1,2,...}2に対し X i(s) と Xj(t) は互いに独立 であるとする．一般性を失うことなくµ1≥µ2≥ ··· ≥µK と仮定する．時刻 t の直前までに腕 i を引いた回数を ni(t) とする．各時刻 t において，プレイヤーは腕 itを 引き損失 Xit(nit(t) + 1) を観測したあと停止するか，ま たは次の時刻 t + 1 もプレイを続ける．プレイヤーの停 止時刻を T とする． プレイヤーの目的は，損失平均µiがτ+∆ より大きな 悪腕 i が存在するか否かのチェックを，できるだけ早い停 止時刻 T で行うことである．平均µiの値によって，以下のように腕を正 (positive)，中間 (neutral)，負 (negative) の三種類に分類する：腕 i は正⇔µi>τ+∆，腕 i は負 ⇔ µi<τ− ∆，腕 i は中間 ⇔τ− ∆ ≤µi≤τ+∆． 以下の定義を満たすアルゴリズムを考える． 定義 1 (悪腕存在チェックアルゴリズム) 与えられた∆ ∈ [0, 1/2)，τ∈ (∆,1 −∆) および，δ∈ (0,1/2) に対し，K 本の腕の１つの腕を引きその損失を観測することを時 刻 t = 1, 2, . . . に繰り返す設定において，有限時刻に停 止し，正の腕が存在するときには少なくとも 1−δ の 確率で「正」，すべての腕が負であるときには少なく とも 1−δ の確率で「負」を出力するアルゴリズムを (∆,δ)-悪腕存在チェックアルゴリズムという． ただし，正の腕が存在せず，少なくとも一つの中間 の腕が存在する場合には，(∆,δ)-悪腕存在チェックアル ゴリズムは「正」「負」いずれの回答をしてもよいもの とする．本研究の目標は，必要サンプル数が少ない (停 止時刻が早い)(∆,δ)-悪腕存在チェックアルゴリズムの 開発である．
3
必要サンプル数の下界
この節では，(∆,δ)-悪腕存在チェックアルゴリズムの 必要サンプル数の下界を示す． 分布νの分布ν′に対するカルバック・ライブラー情 報量を KL(ν,ν′) で表し， d(x, y) = x lnx y+ (1− x)ln 1− x 1− y と定義する．このとき，ν,ν′がそれぞれ平均がµi,µi′ のベルヌーイ分布であれば，KL(ν,ν′) = d(µi,µi′) が成 り立つ． 必要サンプル数の下界を証明するのに，以下の補題 を用いる． 補題 1 (Lemma 1 in [3]) ννν,ννν′ を K 腕の損失確率分布 集合とする．任意の i∈ {1,...,K} に対し，確率分布 ( 測度 )νiとνi′は互いに絶対連続であるとする．T をプ レーヤーのほとんど確実な (a.s.) 有限停止時刻，E をこ の確率過程の任意の事象とすれば， K∑
i=1 Eν[ni(T )]KL(νi,νi′)≥ d(Pννν(E ),Pννν′(E )) が成り立つ． 定理 1 {νi} をベルヌーイ分布集合とする．このとき， 任意の (∆,δ)-悪腕存在チェックアルゴリズムに対し，正 の腕が存在する場合は，停止時刻 T に関し E(T) ≥ 1− 2δ d(µ1,τ− ∆) ln1−δ δ (1) が成り立つ．すべて負の腕である場合には， E(T) ≥∑
K i=1 1− 2δ d(µi,τ+∆) ln1−δ δ (2) が成り立つ． (証明) 正の腕が存在する，つまりµ1>τ+∆ が成り立つ と仮定する．{νi} において，平均がτ−∆ 以上の腕の数 を m 本とする．つまりµ1≥ ··· ≥µm≥τ−∆ >µm+1≥ ··· ≥µKとする．任意のε> 0 に対し，{νi′} を，以下 のように定義される平均µi′のベルヌーイ分布νi′から なる集合とする． µi′= { τ− ∆ −ε (i≤ m) µi (i > m) 任意の (∆,δ)-悪腕存在チェックアルゴリズムに対し，そ の出力が「正」であるという事象をE とする．分布集合 ννν={νi} では正の腕が存在するので Pννν(E ) ≥ 1−δ，分 布集合ννν′={νi′} ではすべて負の腕であるので Pννν′(E ) < δ が成り立つ．よって補題 1 より， m∑
i=1 E[ni(T )]d(µi,τ− ∆ −ε)≥d(Pννν(E ),Pννν′(E ))≥d(1 −δ,δ) が成り立つ．maxi∈{1,...,m}d(µi,τ−∆−ε) = d(µ1,τ−∆− ε) であるから， K
∑
i=1 E[ni(T )]≥ d(1−δ,δ) d(µ1,τ− ∆ −ε) = 1− 2δ d(µ1,τ− ∆ −ε) ln1−δ δ が成立する．任意のε> 0 について成り立つので，ε→ +0 とすれば，不等式 (1) が導かれる． 次に，すべての腕が負である、つまりµ1<τ−∆ と仮 定する．j∈ {1,...,K} を任意に固定する．任意のε> 0 に対し，ννν′={νi′} を，以下のように定義される平均µi′ のベルヌーイ分布νi′からなる集合とする． µi′= { τ+∆ +ε (i = j) µi (i̸= j) 任意の (∆,δ)-悪腕存在チェックアルゴリズムに対し，そ の出力が「負」であるという事象をE とすると，Pννν(E ) ≥ 1−δおよびPννν′(E ) <δが成り立つ．よって補題 1 より， E[nj(T )]d(µj,τ+∆ +ε)≥d(Pννν(E ),Pννν′(E )) ≥d(1 −δ,δ) が成り立つ．つまり， j = 1, . . . , K の各々に対して E[nj(T )]≥ d(1−δ,δ) d(µj,τ+∆ +ε) = 1− 2δ d(µj,τ+∆ +ε) ln1−δ δ が成り立つ．よってε→ +0 として j = 1,...,K に関し て和をとると，不等式 (2) が導かれる． □4
アルゴリズム
(∆,δ)-悪腕存在チェックアルゴリズムとして，各時刻 t に引く腕 itを腕選択方策で選択し，それにより被る損 失 Xit(nit(t + 1)) により，腕判定規則を使って腕 itが正 か負と判定できる場合は判定する枠組み (Algorithm 1) を考える．腕判定規則による判定が正の場合は「正」を 出力して停止し，負の場合は腕 itを候補集合 A から外 し，判定できない場合は何もしないで処理を続行する． 候補集合が /0 になったら「負」を出力して停止する． 本稿では，グレイゾーン幅∆ が正である程度の大き さをもつとき， 腕判定規則として∆ を用いて以下のよ うに定義される値 T∆を利用する規則を考える． T∆= e 2(e− 1)∆2ln K 2∆2δ Algorithm 1 (∆,δ)-悪腕存在チェックアルゴリズム Input: K: 腕の数 ∆ ∈ (0,1/2): グレイゾーン幅 τ ∈ (∆,1 − ∆): 閾値 δ ∈ (0,1/2): 許容誤り確率 1:A← {1,2,...,K} 2:T∆←2(e−1)∆2e ln K 2δ∆2 3:for i∈ A do 4: ni(1)← 0, ˆµi(0)←τ 5:end for 6:t← 0 7:while A̸= /0 do 8: t← t + 1 9: it← arg max i∈A √ ni(t) ( ˆµi(ni(t))−τ) (APT-BC) arg maxi∈A µˆi(ni(t)) (LUCB-BC, t: odd)
arg max i∈A\{it−1} ˆ µi(ni(t)) + √ 1
2ni(t)ln5Kt44δ (LCUB-BC, t: even)
arg max i∈A µˆi(ni(t)) + √ 1 2ni(t)lnt (UCB-BC) 10: nit(t + 1)← { ni(t) + 1 (i = it) ni(t) (i̸= it) 11: 腕 itを引き損失 Xit(nit(t + 1)) を被る． 12: µˆit(nit(t + 1))← ˆ
µit(nit (t))×nit (t)+Xit (nit (t+1)) nit (t+1) 13: ifµ it= ˆµit(nit(t + 1))− √ 1 2nit (t+1)lnKT∆δ >τ − ∆ then 14: return「正」 ▷ 腕 itを正に判定 15: else ifµit= ˆµit(nit(t + 1)) + √ 1 2nit (t+1)lnKT∆δ <τ + ∆ then 16: A← A \ {it} ▷ 腕 itを負に判定 17: end if 18: end while 19: return「負」 時刻 t における腕判定規則は，その時刻に引いた腕 i = it に対するµiの T∆を用いた信頼下界 µi= ˆµi(ni(t + 1))− √ 1 2ni(t + 1) lnKT∆ δ がτ− ∆ より大きければ正，T∆を用いた信頼上界 µi= ˆµi(ni(t + 1)) + √ 1 2ni(t + 1) lnKT∆ δ がτ+∆ より小さければ負と判定し，それ以外の場合 は判定しない．腕 i を n 回引いた後のµi，µiをそれぞ れµ i(n)，µi(n) とも表記する． 腕選択方策としては，以下の 3 方策を考える． APT-BC (APT for the Bad arm existence Checking problem)
以下の値 Bi(ni(t)) が最大とする腕 i を選択する． Bi(ni(t)) =
√
ni(t) ( ˆµi(ni(t))−τ)
これは，APT(Anytime Parameter-free Threshholding
algo-rithm)[4] の腕選択のルール arg min i √ ni(t) (| ˆµi(ni(t))−τ| + ∆) を悪腕存在チェック問題用に変形したものである． オリジナルの APT は ˆµi(ni(t)) がτより大きいか 小さいかにかかわらず， ˆµi(ni(t)) がτに近い腕が
選ばれ易いが，APT-BC では ˆµi(0) =τとするた
め，ˆµi(ni(t)) >τとなるものはどの時刻 t でも高々
1 腕しかなく， ˆµi(ni(t)) >τである間，腕 i は引
かれ続ける．
LUCB-BC (LUCB for the Bad arm existence Checking problem)
ˆ µi(ni(t)) が最大の腕 i と，それを除いた腕で以下 で定義される UCB 値 Ci(t) が最大の腕 i を，ペア で (交互に) 選択する． Ci(t) = ˆµi(ni(t)) + √ 1 2ni(t) ln5Kt 4 4δ 最適 m 腕識別の LUCB アルゴリズム2[1] と停止 条件は異なるが，m = 1 のときの LUCB と腕選択 方策は同じ．
UCB-BC (UCB for the Bad arm existence Checking problem)
以下で定義される UCB 値 Di(t) が最大の腕 i を 選択する． Di(t) = ˆµi(ni(t)) + √ 1 2ni(t) lnt
良腕識別の HDoC(Hybrid algorithm for the Dilemma of
Confidence)[2] と停止条件・腕判定規則は異なる3が 腕選択方策は同じ．
5
アルゴリズムの解析
Algorithm 1 に関して，以下の定理が成り立つ． 定理 2 Algorithm 1 は，どのような腕選択方策を用いて も，(∆,δ)-悪腕存在チェックアルゴリズムとなっている． これを示すために命題 1 および補題 2, 3 を示す． 命題 1 任意の実数 a∈ (0,1 e) に対し，任意の実数 x≥ e (e−1)aln 1 aは，ax≥ lnx を満たす．ただし，e は自然対 数の底である． (証明) f (x) = ln x− ax とする． f′(x) = 1x− a より， x <1aでは f (x) は単調増加，x >1 aでは単調減少となっ ている．また，limx→0f (x) =−∞, limx→∞f (x) =−∞ な2LUCB は LCB(lower condidence bound, 信頼下界) と UCB(upper
confidence bound, 信頼上界) の両方使うアルゴリズムという意味で名 前がつけられており，実際 m≥ 2 のときは， ˆµi(ni(t)) の大きい方か ら m 腕の中で LCB が最小の腕 i を引く． 3良腕識別では正の腕すべてを出力するまで停止できないが，悪腕 存在チェックでは正の腕を１つ見つければ停止できる．また，HDoC の 腕判定規則ではµit= ˆµit(nit(t + 1))− √ 1 2nit(t+1)ln 4Knit(t+1)2 δ ，µit= ˆ µit(nit(t + 1)) + √ 1 2nit(t+1)ln 4Knit(t+1)2 δ ,∆ = 0 として同じ腕判定規則 が適用される． ので，ある x > 0 で f (x) > 0 になるなら， f (x) = 0 の 解は二つだけであることが分かる． f (1a) = ln1a− 1 なので，ln1a> 1 のときには，x < 1a と x >1 aの二つの範囲で f (x) = 0 は解をもつ． x =(e−1)ae ln1aを f (x) に代入すると， f ( e e−1 a ln 1 a ) = ln ln1 a− ( 1 e− 1ln 1 a− ln e e− 1 ) ≤ 0 最後の不等号は y = 1 e−1x−ln e e−1が y = ln x の x = e−1 における接線であるという事実から成り立つ．これよ り，x > e (e−1)aln1aのとき， f (x)≤ 0，つまり ax ≥ lnx が成り立つ． □ 補題 2 Algorithm 1 において各腕 i は，高々T∆回引かれ た後，正と判定され「正」を出力して停止するか，ま たは負に判定され正腕候補集合 A から除かれる． (証明) 背理法により示す．腕 i を T∆回引いた時点で 正負の判定ができていないと仮定する．正負の判定が できていないので，τ+∆ <µiかつτ− ∆ >µ iが成り 立っており， µi−µi> (τ+∆) − (τ− ∆) = 2∆ (3) が導かれる．一方，命題 1 において a =2∆K2δ とおくと， 任意の x≥ e (e−1)aln 1 a(= KT∆ δ ) に対して，ln x≤ ax が成 り立つ．特に x = KT∆ δ のときには lnKT∆ δ ≤ 2∆2δ K KT∆ δ √ 1 2T∆ln T∆K δ ≤ ∆ µi−µi 2 ≤ ∆ これは式 (3) に矛盾する． □ 補題 3 腕 i が正 (負) であるときは，Algorithm 1 は，少 なくとも 1−Kδ の確率で正 (負) と判定し，「正」を出力 する (正腕候補集合 A から i を除く)． (証明)µi(n) <τ+∆ が成り立つ確率は，µi>τ+∆ で ある事実と Hoeffding の不等式より P[µi(n) <τ+∆] = P [ ˆ µi(n)−µi<− √ 1 2nln KT∆ δ ] < δ KT∆ となる．補題 2 より，各腕は高々T∆回しか引かれない ので， P[i が負と判定される] =P[∃n ≤ T∆,µi(n) <τ+∆]
≤
∑
T∆ n=1 δ KT∆= δ K 負の腕に対しても同様である． □ (定理 2 の証明) 補題 2 より，Algorithm 1 は高々KT∆回 腕を引いた後、「正」または「負」を出力して停止する． また補題 3 より，正腕が存在する場合は，少なくとも 1−δ/K の確率で「正」と出力し，すべて負腕の場合 は少なくとも 1−δの確率で「負」と出力する．よって Algorithm 1 は，腕選択方策によらず，(∆,δ)-悪腕存在 チェックアルゴリズムである． □ 補題 2 より，最悪ケースでどの腕も高々T∆回しか引 かれないことがわかるが，平均的には以下の定理で示 すようにもっと少なくなる． 定理 3 Algorithm 1 において，腕 i が正または負と判定 されるまでに i を引く回数を Tiとすると， E[Ti]≤ 1 2(∆i+∆)2 lnKT∆ δ + O (( lnKT∆ δ )2/3) が成り立つ．ただし，∆i=|µi−τ| とする. (証明)µi>τの場合，任意の 0 <ε<∆/4 に対して n0=2(µ 1 i−τ+∆−2ε)2ln KT∆ δ とすれば， E[Ti] ≤∑
∞ n=1 nP[Ti= n] = ∞∑
n=1 P[Ti≥ n] = ∞∑
n=0 P[Ti≥ n + 1] ≤∑
∞ n=1 P[µi(n) <τ− ∆] + 1 ≤∑
∞ n=1 P[µi(n) <τ− ∆ +ε] + 1 ≤⌊n∑
0⌋ n=1 1 + ∞∑
n=⌊n0⌋+1 P [ ˆ µi(n)− √ 1 2n0 lnKT∆ δ <τ− ∆ +ε ] + 1 ≤n0+ ∞∑
n=⌊n0⌋+1 P[ ˆµi(n) <µi−ε] + 1 ≤n0+ ∞∑
n=1 e−2nε2+ 1 = n0+ 1 e2ε− 1+ 1 ≤ 1 2(µi−τ+∆ − 2ε)2 lnKT∆ δ + 1 2ε2+ 1 が成り立つ． 1 (µi−τ+∆−2ε)2 ≤ 1 (µi−τ+∆)2 + ε (µi−τ+∆)3 が成 り立つので，ε= O (( lnKTδ∆ )−1/3) とすれば， E[Ti]≤ 1 2(µi−τ+∆)2 lnKT∆ δ + O (( lnKT∆ δ )2/3) が成立する． µi<τの場合は，n0=2(τ−µ 1 i+∆−2ε)2ln KT∆ δ とし， E[Ti]≤ ∞∑
n=1 nP[Ti= n] = ∞∑
n=1 P[Ti≥ n] = ∞∑
n=0 P[Ti≥ n + 1] ≤∑
∞ n=1 P[µi(n) >τ+∆ −ε] + 1 を用いれば同様に証明できる． □ 各腕に対する上界を足し合わせれば，Algorithm 1 の 平均停止時間の上界は以下の式で得られる． K∑
i=1 E[Ti]≤ K∑
i=1 1 2(∆i+∆)2 lnKT∆ δ + O (( lnKT∆ δ )2/3) 分布がベルヌーイ分布の場合，負の腕しかない場合の 下界は，定理 1 にピンスカーの不等式 d(x, y)≥ 2(x−y)2 を適用して変形すると K∑
i=1 1− 2δ d(µi,τ+∆) ln1−δ δ ≤ K∑
i=1 1− 2δ 2(∆i+∆)2 ln1−δ δ となる．ピンスカーの不等式のタイト性を考えると，負 の腕しかない場合は，Algorithm 1 はどのような腕選択 方策を用いようともδの関数としてほぼ漸近最適になっ ていると言える．6
シミュレーション実験
∆ = 0.1 とし，τ= 0.2, 0.5, 0.8 の各々の値に対し，100 腕の損失平均{µi} を以下のようにランダムに生成し， 各腕の損失分布をベルヌーイ分布としてシミュレーショ ンにより３つのアルゴリズムの停止までのサンプル数を 比較した．(正腕数, 中間腕数, 負腕数) = (m, 0, 100− m) とし，m 本の正腕 i の µi は [τ+∆,1] 上の一様分布， (100− m) 本の負腕 i のµiは [0,τ− ∆] 上の一様分布に 従ってランダムに選んだ．m = 1, 25, 50, 100 に対してこ の方法で{µi} を発生させ，δ = 0.01 として３つのアル ゴリズム (APT-BC, LUCB-BC, LUCB-BC) 各々を用い て 100 回ずつシミュレーションを行い，停止するまで のサンプル数 (=停止時刻) の平均とその 95%信頼区間 を求めた． 結果を表 1 に示す．95%信頼区間による評価により有 意な差で最もサンプル数が少なかったアルゴリズムの サンプル数を太文字で示している．サンプル数では，少 ない順に APT-BC, LUCB-BC, UCB-BC の順になった． 特に APT-BC は，m = 1 のときを除き，有意な差で他の アルゴリズムよりサンプル数が少なかった．実験の設 定では，中間の腕がないため，正腕と負腕では損失平均表 1: 100 回のシミュレーションによる各アルゴリズムのサンプル数の平均とその 95%信頼区間． τ アルゴリズム m = 1 m = 25 m = 50 m = 100 0.2 APT-BC 234.89± 57.92 38.00± 8.56 29.48± 4.75 30.04± 5.62 LUCB-BC 309.06± 67.71 118.84± 1.52 118.36± 1.06 117.36± 0.39 UCB-BC 710.38± 132.03 280.58± 1.92 347.39± 3.23 506.63± 5.99 0.5 APT-BC 232.38± 52.43 50.18± 5.92 48.97± 6.53 48.23± 5.76 LUCB-BC 334.62± 52.76 154.86± 7.6 149.00± 5.58 147.44± 8.76 UCB-BC 638.35± 79.72 466.13± 8.12 696.22± 7.68 1142.26± 12.12 0.8 APT-BC 252.34± 27.91 128.26± 6.9 125.42± 6.9 121.77± 6.75 LUCB-BC 464.54± 31.07 316.38± 28.77 287.02± 10.45 272.38± 5.9 UCB-BC 930.09± 39.44 1968.27± 17.9 3300.47± 24.2 5900.62± 31.96 0 25 50 75 100 0.0 0.2 0.4 0.6 0.8 1.0 sample mean
APT-BC
0 25 50 75 100 0.0 0.2 0.4 0.6 0.8 1.0LUCB-BC
0 25 50 75 100 0.0 0.2 0.4 0.6 0.8 1.0UCB-BC
0.967
0.899
0.880
0.866
0.832
0.751
0.384
0.382
0.362
0.321
0.118
0.006
time 図 1: 停止するまでの各腕の標本平均の推移．∆ = 0.1，τ= 0.5，m = 6，δ= 0.01 の設定であり，正腕とその他を 分ける閾値τ+∆ = 0.6，及び負腕とその他を分ける閾値τ− ∆ = 0.4 は灰色の破線で示されている． に 0.2 のギャップがあり，m = 1 の場合は LUCB-BC や UCB-BC においても，少ないサンプルで唯一の正腕が 引かれやすくなり，APT-BC との差はあまりでないと考 えられる．正腕が多い場合は，トップのいくつかの腕 i のµiの値が近くなるため，LUCB-BC と UCB-BC はそ れらをすべて多く引いてしまう．それに対し，APT-BC は損失の標本平均 ˆµiがτよりも大きな腕 i を連続して 引き続けるという性質があるため，正腕が多い場合は どれかの正腕に対して、その損失の標本平均がずっと τより大きくなり，その腕を正と判定できるまで引き 続ける可能性が高くなり，その結果，早く停止すると 考えられる．実際，腕の数 K を 12 に減らして各腕の 標本平均の推移をグラフにしてみると図 1 になり，上 の考察の通りの動きになっている． 謝辞 本研究は、JST、CREST、JPMJCR1662 の支援を 受けたものてある．参考文献
[1] Kalyanakrishnan, S., Tewari, A., Auer, P., Stone, P.: PAC Subset Selection in Stochastic Multi-armed Bandits, Proceedings of the 29th International Con-ference on Machine Learning, pp.655–662 (2012) [2] Kano, H., Honda, J., Sakamaki, K., Matsuda, K.,
Nakamura, A., Sugiyama, M.: Good Arm Identifica-tion via Bandit Feedback, arXiv:1710.06360 (2017) [3] Kaufmann, E., Capp´e, O., Garivier, A.: On the
Com-plexity of Best-Arm Identification in Multi-Armed Bandit Models, Journal of Machine Learning Re-search, Vol. 17, No. 1, pp.1–42 (2016)
[4] Locatelli, A., Gutzeit, M., Carpentier, A.: An opti-mal algorithm for the Thresholding Bandit Problem, Proceedings of The 33rd International Conference on Machine Learning, PMLR Vol.48, pp.1690–1698 (2016)
[5] 中村篤祥: 悪腕存在チェック問題のアルゴリズム, 信学技報 117(110), pp.49–54 (2017)
