DEIM Forum 2019 P2-125

ブラックボックス関数の閾値以上の値の存在チェックのアルゴリズム
伊藤直輝†

中村篤祥††

工藤 峰一††† 北海道大学工学部情報エレクトロニクス学科 札幌市北区北 14 条西 9 丁目†† 北海道大学大学院情報科学研究科 札幌市北区北 14 条西 9 丁目
E-mail: †naokiito@ist.hokduai.ac.jp, ††{atsu,kudo}@ist.hokudai.ac.jp
あらまし

連続的な定義域を持つブラックボックス関数が，ある閾値以上の関数値を持つか否かを判定する問題を考える．最適値の近似値を取る点を求める DOO(Deterministric Optimistic Optimization) アルゴリズムを改造したDOO-BAEC(Deterministric Optimistic Optimization for Bad Arm Existence Checking) アルゴリズム及び更にガウシアンプロセスの仮定を導入した DOO-BAEC-GP アルゴリズムを提案する．DOO-BAEC アルゴリズムは，決定的関数に対し DOO アルゴリズムと同じ滑らかさの仮定の下，空間分割及び値の取得を，閾値以上の値を持つ点の有無が判断できるまで行うアルゴリズムである．本稿では，DOO-BAEC アルゴリズム及び DOO-BAEC-GP アルゴリズ
ムを論理的・実験的に評価する．
キーワード

ブラックボックス関数，ブラックボックス最適化，バンディット問題, 最適腕識別, 悪腕存在チェック問題
定し，その事後分布を用いて次の観測点を決定する方法である．

1 はじめに
1. 1 研究の背景
ブラックボックス最適化問題は，ブラックボックス関数についてその関数値の最大 (小) 値などを探索する最適化問題とし

しかし，この方法では次の観測点の決定に毎回非凸最適化問題を解く必要があり計算コストがかかる．それに対し１回の計算コストが低い方法として，関数の滑らかさの仮定を用いるもの(DOO[1] , SOO[1] ) がありいくつかの拡張方法が検討されている [5][6][7] ．て広く考えられている．ブラックボックス関数とは入力に対してその出力である関数値の情報しか取得することが出来ず，そ1. 2 研究の目的れ以外の情報が与えられない設定の関数である．しかしこれら異常の基準が存在する病気の診断や機械の故障の診断などのが用いられる実用の例では関数値の最大値の探索を目的とせず，実用例では，どこか一ヵ所でも異常が存在すると問題があるとある閾値以上の関数値を目的とする場合がある．例えば機械学して判定することが可能である．本研究では最適腕識別の亜種

習モデルのハイパラメータ設定では性能を最大にする値ではなとして，無限個の選択肢から最適な選択肢ではなくある閾値以

くてもある程度以上にする値であればよく，病気や事故の予備上の期待値を持つ選択肢が存在するかどうかを判定する「悪腕診断では最も高い異常値ではなくてもある程度以上の異常値を存在チェック問題」[9][10] を考える．

確認することが出来れば良い．このような閾値以上の関数値の本研究では連続腕バンディット問題設定の悪腕存在チェック探索については，多腕バンディット問題の文脈で研究がされて問題に対して，まず DOO-BAEC アルゴリズムを提案する．こいる．の理論的評価として関数値取得回数の上界を示す．
さらに DOO-BAEC-GP アルゴリズムを提案し，ガウシアン

多腕バンディット問題の文脈において，いくつかの選択肢 (腕)の中からプレイヤーが逐次的に選択を繰り返し，期待報酬が最も高い選択肢 (最適腕) を識別する問題を最適腕識別問題という．選択肢の集合を定義域とし，報酬を確率的な関数の選択された点における関数値とみなせば，最適腕識別はブラックボッ
クス最適化と同じである．選択肢が有限個の最適腕識別の問題
設定では閾値以上の値の探索について研究 [9][10][11] がされているが，連続的な定義域を持つブラックボックス関数について適用することは出来ない．
また，連続的な定義域を持つブラックボックス関数はバンディッ
ト問題の枠組みでも扱われており，連続腕バンディット [8] と呼ばれている．この連続腕バンディットの最適腕識別についての従来研究にはベイズ最適化に基づくもの (GP-UCB[3] , EI 方策) がある．これは関数が事前分布にしたがって発生すると仮プロセスの仮定を導入することによる効果を実験によって検証する．

1. 3 問 題 設 定
X を定義域とする (決定的) 実数値関数 f : X → R に対して，以下のように定義される悪腕存在チェック問題を考える．

[悪腕存在チェック問題]
与えられたしきい値 θ に対し，それ以上の関数値 f (x) >=θをもつ点 x が少なくともひとつ存在する (正) か，そうでないか(負) をできるだけ少ない関数値の取得により判定せよ．
1. 4 本論文の構成
本論文は本章を含めて，全六章で構成する．第二章では，提案アルゴリズムのベースとなる DOO アルゴリズムの概要について述べる．第三章では提案アルゴリズムである DOO-BAEC

及び DOO-BAEC-GP について述べる．第四章では，ガウシア

このときある ν > 0 が存在し，任意の h >= 0 に対し，任意のセンプロセスの仮定を導入することの効果を検証する実験の結果

ル Xh,i が l-ball(xh,j , νδ(h)) を含む．

について述べる．第五章では，結果を考察する．第六章では，本論文のまとめと今後の展望について述べる．

2 DOO アルゴリズム [1]DOO アルゴリズムは時刻 0 から始め，各時刻 t にある深さのセル 1 つを分割する．以下 Tt は時刻 t における X の階層的な分割を表す木とし Lt は Tt の葉ノードの集合とする．Tt の要素 (h, j) をセル Xh,j に対応するノードとし，Xh,j を分割しこの説では連続腕バンディットの最適腕識別において，関数て得られるセル Xh+1,Kj , . . . , Xh+1,Kj+K−1 に対応するノードの滑らかさの仮定を用いる DOO アルゴリズム [1] を紹介する．

(h + 1, Kj), . . . , (h + 1, Kj + K − 1) が Tt に含まれている場

2. 1 関数に関する仮定
仮定 1 (f の局所的な滑らかさ). 少なくとも一つ x∗ ∈ Xが 存 在 し,f (x∗ ) = supx∈X f (x) を 満 た す．ま た ，半 距 離l : X × X → R が存在し，この x∗ 及びすべての x ∈ Xについて合，それらを (h, j) の子ノードといい，(h, j) との間に枝があるとみなす．含まない場合は (h, j) は葉ノードであるという．

Algorithm 1 DOO アルゴリズム [1]
1: T0 ← {(0, 0)}(root node)
2: for t = 1 to n do∗∗f (x ) − f (x) <= l(x, x )3:(ht , jt ) ← arg max (f (xh,j ) + δ(h))

を満たす．ただし半距離 l とは任意の x, y ∈ X に対し以下の条

4:

Tt ← Tt−1 ∪ {(ht + 1, Kjt ), . . . , (ht + 1, Kjt + K − 1)}件を満たす関数のことである．

5:f (xht +1,Kjt ), . . . , f (xht +1,Kjt +K−1 ) の値を取得(h,j)∈Lt−1

6: end for(1) l(x, y) >=0(2) x = y ⇔ l(x, y) = 0

7: (h∗ , j ∗ ) ← arg max f (xh,i )(h,j)∈Tn

8: return xh∗ ,j ∗(3) l(x, y) = l(y, x)
2. 2 空間分割に関する仮定
この手法は探索空間を階層的に分割しながら関数の最大値をとる点を探索する．X ⊆ RD を K D 個に分割するとき，

D = 2, K = 2 の例を以下の図に示す．X を階層的に分割し，DOO アルゴリズムの性能評価をするにあたり重要な概念が最適点近傍次元 (near-optimality dimension)[1][8] である．
定義 1. 仮定 1-3 を満たす X, f, l, ν に対し，以下の条件 NODを満たす最小の d を最適点近傍次元という．
条件 NOD: ある C > 0 が存在し，任意の ϵ について中心がXϵ 内にあり重なりを持たない半径 νϵ の l-ball の最大数が Cϵ−dより小さい．ただし任意の ϵ について Xϵ = {x ∈ X, f (x) >=f (x∗ ) − ϵ} である．
一方，C∑h−d >= t を満たす最小の h を h(t) とする．
l=0 δ (l)すると以下の定理 1 が成り立つ．
図 1 DOO アルゴリズムの定義域の分割例h
各深さ h >= 0 において X を以下のように K 個のセル Xh,iに分割する．X0,0 = X とする．セル Xh,i を K 分割すること

定理 1 (論文 [1] の Theorem1). DOO アルゴリズムの時刻 t 終了時点において h(t) の深さのセルは少なくとも 1 つは分割されており，x̂∗t = arg max f (xh,j ) とすれば(h,j)∈Tt

により得られる K セルを Xh+1,Ki , ..., Xh+1,Ki+K−1 とする．

f (x∗ ) − f (x̂∗t ) <= δ (h(t))

各々のセル Xh,j の中心を xh,j とする．f 及び仮定 1 により存在が仮定された半距離 l，階層的に分割された各々のセル Xh,jを満たす．

およびその中心 xh,j に対し以下の仮定 2, 3 を満たす実数値関数 δ ，実数 ν > 0 が存在するものとする．
仮定 2 (セルの直径の限定). ある減少関数 δ (h) > 0 が存在し，任意の深さ h >= 0，任意のセル Xh,i について以下を満たす．

3 提案手法3. 1 DOO-BAEC アルゴリズム
DOO アルゴリズムでは関数 f が最大値をとる点の探索を目sup l(xh,i , x) <= δ (h)x∈Xh,i的としていた．この節では DOO アルゴリズムを，「関数 f がある閾値 θ 以上の値をとる点を，X において少なくともひとつ持仮定 3 (セルの形). 中心 xcenter 半径 r の l-ball(xcenter , r) を以下のように定義する．

l-ball(xcenter , r) = {x ∈ X|l(x, xcenter ) <= r}つかどうかの判定」を目的とした DOO-BAEC(Deterministic

Optimistic Optimization for Bad Arm Existence Checking)アルゴリズムに改造する．

Algorithm 2 に DOO-BAEC アルゴリズムを示す．
分割する葉ノードの選択は DOO アルゴリズムと同じである．DOO アルゴリズムは n 回葉ノードを分割すれば停まるが，∗f (x̂∗t ) >= f (x ) − δ(h(t))∗∗>= f (x ) − ∆= θ

DOO-BAEC アルゴリズムは θ 以上の点が存在するか否かを正が成り立つ．

しく判定できるまでループを繰り返す．

DOO-BAEC アルゴリズムでは任意のノード (h, j) に対してされていることから，それに対応するノード (h∗ , j∗ ) についてbh,j を以下のように定義する．
{
defbh,j =f (x∗ ) − θ < 0 のとき h(t) の深さのセルは少なくとも一つ分解

f (x0,0 ) + δ(0)(h = 0)min{bh−1,⌊j/K⌋ , f (xh,j ) + δ(h)}(h > 0)bh,j <= bh∗ ,j∗< f (xh∗ ,j∗ ) + δ(h(t))=

ただし，⌊x⌋ は x 以下の最大の整数を表すものとする．仮定 1，∗<= f (xh∗ ,j∗ ) + ∆仮定 2 からこの bh,j は，ノード (h, j) に対応するセル Xh,j が= θ + (f (xh∗ ,j∗ ) − f (x∗ ))∗x を含む場合に，そのセル上の任意の点 x に対する f (x) の上界を示す．DOO-EABC アルゴリズムでは bh,j の最大値をとる<= θ□

ノードを選択することによって分割するセルを決定する．よっが成り立つ．て max(h,j)∈Lt bh,j は時刻 t に対し単調に減少する．

定理 2. limt→∞ δ(h(t)) < ∆∗ であるとき，DOO-BAEC アル

ここで |f (x∗ ) − θ| = ∆∗ とおく．この ∆∗ は探索の困難さを表す指標と考えられ，小さいほど探索は難しくなる．

ゴリズムは悪腕存在チェック問題の正負の正しい判定を行う．

(証明). ∆∗ >= δ(h(t)) が成り立つ時刻 t において，補題 1 の補題 1. ∆∗ >= δ(h(t)) が成り立つ時刻 t において，DOO-BAEC
アルゴリズムに対し (1) または (2) が成り立つ．

(1)x̂∗t = arg max f (xh,j ) に対し f (x̂∗t ) >= θ が成り立つ．
(h,j)∈Tt(2) すべての (h, j) ∈ Lt に対し bh,j <= θ が成り立つ．

(1) 又は (2) が成り立つ．
(1) が成り立つときアルゴリズムは性の判定を行うが，θ 以上の関数値を取得しているため，判定は正しい．

(2) が成り立つときアルゴリズムは性の判定を行うが，x∗ を含むセルに対応するノード (h∗ , j∗ ) ∈ Lt について f (xh∗ ,j∗ ) +∗δ(h∗ ) <= θ である．また仮定 1, 2 から f (x ) <= f (xh∗ ,j∗ )+δ(h∗ )なので，f (x∗ ) < θ である．よって判定は正しい．

Algorithm 2 DOO-BAEC アルゴリズム
1: f + ← f0,0
2: T0 ← {(0, 0)}□定理 3. ある c > 0 と 0 < γ < 1 が存在し，全ての非負整数 hに対し，δ(h) = cγ h を満たすと仮定する．また，X, f, l, ν に対3: t ← 1

し，最適点近傍次元を d，その d に対し条件 NOD により存在4: while true doが保証される C > 0 を考える．このとき，DOO-BAEC アル

5:(ht , jt ) ← arg max bh,j

ゴリズムの停止時刻 n(セルの分割回数) は d > 0 のとき(h,j)∈Lt−1

6:

Tt ← Tt−1

7:

for i = 0 to K − 1 do

8:

Tt ← Tt ∪ {(ht + 1, Kjt + i)}9:if f (xht +1,Kjt +i ) > f + then

10:
11:
12:
13:
14:
15:
16:

f + ← f (xht +1,Kjt +i )end ifend forif f + >= θ thenreturn 正
end ifif arg max bh,j <= θ then⌈C∆∗−d1 − γd⌉以下である．d = 0 のとき⌈( ∗ )⌉∆ γ
C logγc以下である．

(証明). d > 0 のとき
h(n) の定義から(h,j)∈Lt

17:

return 負18:

end if19:

t←t+120: end while∑h(n)n<=Cδ (l)−d = c−d Cl=0である．よって

γ −dh(n) >=(証明). f (x∗ ) − θ >= 0 のとき定理 1 より

γ −d(h(n)+1) − 1
γ −d − 1であるので仮定から

n(1 − γ d )c−d Cここで K は Ki,j = k(xi , xj ) で定義される t × t の正方行列でδ(h(n)) = cγ h(n)1d<= C n1−d(1 − γ d )ある．この共分散関数 k(xi , xj ) はカーネル関数とも呼ばれ，直1−d

感的にはその関数値 f (xi ) と f (xj ) の類似度を表す．取得した
関数値 Dt = (x1:t , f (x1:t )) に対し，新しく観測する点 xt+1 の1d∗ >1−d1d −d∗ >が成り立つ．ここで ∆ = C n (1 − γ )のとき ∆ =δ(h(n)) を満たし，補題 1 よりプログラムは必ず停止している．
よってµ(xt+1 |Dt ) = kT D−1 f (x1:t )σ 2 (xt+1 |Dt ) = k(xt+1 , xt+1 ) − kT K −1 kn(1 − γ d )C(∆∗ )−d <=目的関数値 f (xt+1 ) はの正規分布 N (µ(x1:t |Dt ), σ 2 (xt+1 |Dt )) に従う．DOO-BAEC-∗−dC∆n>= 1 − γdGP アルゴリズムでは次の仮定 4, 5, 6 を用いる [7] ．

⌈仮定 4 (X とカーネル関数 k). X ∈ RD はコンパクトセット

よって停止時刻はC∆∗−d1 − γd⌉

でカーネル関数 k(·, ·) は RD 上のカーネルで対角に沿って 2 回′微分可能である．∂x ∂x′ k(x, x )|x=x′ が存在する．

以下である．

d = 0 のとき同様に∑

仮定 5 (f の局所的な滑らかさ). f ∼ GP (0, k) は定義域 X の連

h(n)

n<=C

続的なサンプルで，少なくとも一つ x∗ ∈ X が存在し,f (x∗ ) =0

δ(l) = C(h(n) + 1)

supx∈X f (x) を満たす．ある定数 c1 , c2 , ρ > 0, α ∈ {1, 2} につ

l=0

いてなので

δ(h(n)) = cγh(n) <= cγ<f (x∗ ) − c1 ||x − x∗ ||α2 = f (x), ∀x ∈ X(n/C)−1∗∗ 2∗
f (x) >= f (x ) − c2 ||x − x ||2 , ∀x ∈ l-ball(x , ρ)(n/C)−1が成り立つ．ここで ∆∗ >のとき ∆∗ >= cγ
= δ(h(n)) を満たし，補題 1 よりプログラムは必ず停止している．よって
( ∗ )
∆ γn>
Clog
γ
=c

さらにある定数 ϵ0 > 0 について

よって停止時刻は

仮定 6. 仮定 5 で存在が保証された c(> 0) に対し，l(x, y) =f∗ −⌈( ∗ )⌉∆ γ
C logγcf (x) > ϵ0c1 ||x − y||α2 (α ∈ 1, 2) とする．これに対し，仮定 2, 3 が成り立つ．

□以下である．

maxx∈X\l-ball(x∗ ,ρ)系 1. 定理 3 と同じ仮定の下で DOO-BAEC アルゴリズムが取得する関数値の数はまだ関数値を取得していない点について以下の信頼上界を√U (x|Dt ) = µ(x|Dt ) + Bt σ(x|Dt ) と定義する時，次の定理 4が成り立つ．
定理 4 (論文 [7] の Lemma4). 仮定 4 ∼ 6 を満たすとき任d > 0 のとき，高々⌈K⌉∗−dC∆
1 − γd意 の η ∈ (0, 1) に 対 し て Bt = 2 log (π 2 t2 /6η) と す る と ，+1，d = 0 のとき，高々⌈( ∗ )⌉∆ γK C logγ+1c

少なくとも 1 − η の確率で全ての時刻 t において f (xt ) <=√µ(xt |Dt ) + Bt σ(xt |Dt ) = U (xt |Dt ) が成り立つ．

DOO-BAEC アルゴリズムでは，分割するセルを決定した後にその K 個の子ノードの関数値を無条件で全て取得していた．

である．

DOO-BAEC-GP アルゴリズムでは DOO-BAEC と同様に分

3. 2 DOO-BAEC-GP アルゴリズム
ここで DOO-BAEC アルゴリズムの関数値の取得回数をさらに減少するために，GP(Gaussian Process)[3][4] を導入する．GPでは目的関数 f が平均関数 m(·) と共分散関数 k(·, ·) によって指定される確率変数であると考える．具体的には，xi ∈ X ⊆ RDの点の集合 x1:t に対して，f (x1:t ) = (f (x1 ), f (x2 ), . . . , f (xt ))が多変量正規分布に従うことを指す．

f (x1:t ) ∼ N (m(x1:t ), K)割するセルを決定し，まず K 個の子ノードの点で U (x|Dt ) を計算する．さらにセル全体の信頼上界 U (x|Dt ) + δ(h) を計算し，関数値を取得するかどうかを判断する．

Algorithm 3 に DOO-BAEC-GP アルゴリズムを示す．

4 実験

この節では提案手法のアルゴリズムを実装し，その挙動を確認する．人工の関数を用い DOO-BAEC アルゴリズムと DOO-BAEC-GP アルゴリズムの比較を行う．また比較手法として定Algorithm 3 DOO-BAEC-GP アルゴリズム
1: f + ← f0,0
2: T0 ← {(0, 0)}
3: t ← 1, Dt ← {(x0,0 , f (x0,0 ))}4: while true do
5:(ht , jt ) ← arg max bh,j6:

Tt ← Tt−1

7:

for i = 0 to K − 1 do(h,j)∈Lt−1

8:+if UN (xht +1,Kjt +i |Dt ) + δ(ht + 1) >= f then9:

Tt ← Tt ∪ {(ht + 1, Kjt + i)}

10:

Dt ← Dt ∪ {(xh+1,Kj+i , f (xh+1,Kj+i ))}11:

if f (xht +1,Kjt +i ) > f + thenf + = f (xht +1,Kjt +i )12:

DOO-BAEC アルゴリズムは 165 回の関数値の取得によって閾

end if16:

end forif f + >= θ then17:

return 正

15:点が取得した関数値の座標，赤い線が閾値を表す．この例ではend if13:
14:

図 2 DOO-BAEC アルゴリズムの木構造値以上の関数値を発見し停止した．
また DOO-BAEC-GP アルゴリズムの結果を図 3 に示す．

18:

end if19:

if arg max bh,j <= θ then(h,j)∈Lt

20:

return 負21:

end if

22:t←t+1

23: end while

義域をグリットに分割する方法と GP-UCB を用いる．これらの手法では負 (閾値以上が存在しない) 判定は出来ないため，正(閾値以上が存在する) の場合のみ比較する．

図 3 DOO-BAEC-GP アルゴリズムの木構造

関数 f = 0.5(sin (13x) sin (27x) + 1)，δ(h) = 14(1/2)h とし，θ = 0.97, 0.97559, 0.98 以上の関数値をもつ x ∈ X

この例では DOO-BAEC-GP アルゴリズムは 88 回の関数値が存の取得によって閾値以上の関数値を発見し取得し停止した．ま在するかどうかを関数値の取得回数で比較した結果を表 1 に示た信頼上界に基づく判断によって関数値を取得しなかった回数

す．また各アルゴリズム全体の実行時間を表 2 に示す．

は 41 回となった．図 3 の木構造を図 2 と比較すると，関数値の取得回数が減少していることが確認された．

表 1 関数値の取得回数と判定結果
手法

θ = 0.97

θ = 0.97559

θ = 0.98

比較手法(129,’ 正’)(2049,’ 正’)

(-,-)

比較手法

(15,’ 正’)(31,’ 正’)(-,-)

DOO-BAEC(71,’ 正’)(165,’ 正’) (243,’ 負’)

DOO-BAEC-GP(55,’ 正’)(89,’ 正’)(99,’ 負’)5 考察

提案手法である DOO-BAEC アルゴリズムは，実験の結果から適切な δ(h) の設定のもとで正しい出力を得ることが確認された．また DOO-BAEC アルゴリズムもより少ない関数値の取得回数で同様の結果を得た．しかし特に DOO-BAEC-GP

表 2 アルゴリズムの実行時間 [sec]アルゴリズムは DOO-BAEC アルゴリズムと比較すると実際

手法

θ = 0.97 θ = 0.97559 θ = 0.98のプログラムの実行時間は増加する結果を得た．

比較手法

0.022030.30056-

本来 GP の考え方は「最適腕識別」の文脈 [3] で研究されてお比較手法

0.397510.41084-

DOO-BAEC

0.18447

0.294410.36610

DOO-BAEC-GP

0.25033

0.386050.44024

り，定義域全体において各点の信頼上限を計算するなどして利用されている．しかしそれは本来の問題を解くために別の最適化 (定義域全体のうち信頼上限が最大となる点の探索) をするという点で計算量が多く，本質的ではないと考えられていた．今さらに θ = 0.97559 の時，DOO-BAEC アルゴリズムとDOO-BAEC-GP アルゴリズムの対応した探索の木構造を示す．
DOO-BAEC アルゴリズムの結果は図 2 となった．
図 2 は生成された木構造と関数値の対応を示しており，赤い回の提案手法における GP の利用の仕方はセルの分割に対してその子ノードの点のみで信頼上界を計算するため，その意味では従来の課題に適応していると予想された [6][7] ．
しかし実験では DOO-BAEC-GP は DOO-BAEC に比べて探索回数は減少されたものの，実際のプログラムの実行時間は増加するケースも存在した．また GP-UCB と比較すると，次の[2]観測点の決定にかかる時間は減少したが関数値の取得回数は増加した．
提案手法の実用に向けて主に３つの点について考慮する必要[3]がある．

1. 入力次元数の増加
入力次元数の増加に伴ってセルの分割後に関数値を取得する子[4]ノードの数が増加し，特に DOO-BAEC-GP では GP の計算量にも大きく影響する．

2. 一回の関数値の取得にかかる時間[5]

今回の実験で利用した関数はすぐに関数値を取得できるものであるが，その取得に時間がかかる設定も想定される．アルゴリ[6]

ズム全体として早く処理を終了するために，「一回の関数値の取得にかかる時間」と「次の観測点を決定にかかる時間」のバラ[7]ンスを考慮する必要がある．

3. δ(h) の設定
δ(h) は関数 f と半距離 l，またセルの分割の方法に依存するため，事前に適切に仮定することは困難である．しかし提案手法
では実行時にユーザによって δ(h) が決定されている必要があり，これが δ(h) の仮定を満たさない場合は正しい判定を得られない可能性がある．

[8]
[9]
[10]
[11]

6 おわりに
本稿では悪腕存在チェック問題に対して DOO-BAEC アルゴ
リズムを提案した．またこのアルゴリズムについていくつかの仮定の下で関数値の取得回数の上界を示した．さらにその改良として DOO-BAEC-GP アルゴリズムを提案し，より少ない関数値の取得回数で DOO-BAEC アルゴリズムと同等の精度を得られることを実験によって示した．DOO-BAEC の欠点として，観測の雑音を考慮していない点，半距離 l や δ(h) が既知である点など，様々な仮定の下に成り立っていることが挙げられる．よってこのアルゴリズムで実データを扱うには注意が必要である．また一方でセルの中の代表点の取り方や分割の方法を工夫することで，探索回数を抑えることができることも知られており [4] ，まだ考察の余地があると考えられる．
また DOO-BAEC-GP の欠点として，上記の欠点に加えて調整する必要があるパラメータがさらに増えること，時間経過に伴って必要な信頼区間の計算量が増加し，プログラム全体の実行時間が増加することが挙げられる．
提案したアルゴリズムと問題設定自体の拡張として閾値以上の選択肢が少なくとも 1 つではなく，「ある面積以上かどうか」
または「閾値以上の点の数がある個数以上存在するかどうか」などを判定すると，病気の判定のような用途の場合に有用であることが期待される．

文献[1] R. Munos, “Optimistic optimization of deterministic functions without the knowledge of its smoothness.” In Advancesin Neural Information Processing Systems (NIPS), pp. 783–791, 2011.
J. Audibert, S. Bubeck, and R. Munos, “Best Arm Identification in Multi-Armed Bandits.” The 23rd Conference on
Learning Theory, pp. 41–53, 2010.
N. Srinivas et al. “Gaussian process optimization in the bandit setting: No Regret and Experimental Design.” In International Conference on Machine Learning (ICML), pp.
1015–1022, 2010.
N. de Freitas, A. Smola and M. Zoghi. “Exponential regret bounds for Gaussian process bandits with deterministic observations.” In International Conference on MachineLearning (ICML), 2012.
K. Kawaguchi, L. Pack Kaelbling and T. Lozano-Perez,“Baysian Optimization with Exponential Convergence.”
InAdvances in Neural Information Processing Systems,(NIPS), pp. 2809–2817, 2015.
M. Valko, A. Carpentier and R. Munos, “Stochastic simultaneous optimistic optimization.” In International Conference
on Machine Learning (ICML), 2013.
Z. Wang et al. “Bayesian Multi-Scale Optimistic Optimization.” In Proceedings of the 17th International Conference on Artificial Intelligence and Statistics, pp. 1005–1014,2014.
S. Bubeck et al. “X-armed bandits”, Journal of Machine
Learning Research, 12, pp. 1655–1695, 2014.
中村 篤祥, 「悪腕存在チェック問題のアルゴリズム」 信学技報,117-110(2017), 49-54.
田端 公次, 中村 篤祥, 工藤 峰一, 試行回数の少ない悪腕存在チェックアルゴリズム」 人工知能学会研究会, 106(2018), 94-99.
A. Locatelli et al. “An optimal algorithm for the Thresholding Bandit Problem.”In International Conference on Machine Learning (ICML), pp. 1690–1698, 2016.