処理時間の長短を考慮した確率的多腕バンディット問題へのUCB戦略の拡張

(1)

処理時間の長短を考慮した確率的多腕バンディット問題への

UCB

戦略の拡張

An Extension of UCB to the Stochastic Multi-armed Bandits with

Action-dependent Processing Time

渡辺僚

1 ∗

_{中村篤祥}

1

_{工藤峰一}

1

Ryo Watanabe

1

_{Atsuyoshi Nakamura}

1

_{Mineichi Kudo}

1

_{北海道大学大学院情報科学研究科}

1

_{Graduate School of Information Science and Technology, Hokkaido University}

Abstract: Stochastic K-armed bandits tries to maximize his cumulative reward in limited number

of plays. In this paper, we consider the variant of stochastic K-armed bandits that has action-dependent processing time. For this problem, we propose the policy N-UCB (Normalized UCB), the extension of well-known policy UCB, and shows some fundamental results of its regret analysis.

1 はじめに

多腕バンディット問題とは，逐次的な意思決定によって利益が得られるような問題の数理的なモデルであり，機械学習や統計学の分野において古くから研究されているものである．特に確率的多腕バンディット問題は一人のプレイヤーによる繰り返しゲームとして表される．プレイヤーは可能な複数のアクションから一つを選び実行し，そのアクションに対応した確率分布に従い報酬を得る．このサイクルを繰り返しながら，プレイヤーは可能な限り多くの報酬を得ることを目指す．多腕バンディット問題を考える上で重要となるのが知識利用と獲得のトレードオフである．累積報酬の最大化という目的を達成するためにプレイヤーは最良なアクション，すなわち期待報酬がもっとも大きいアクションを選びたい一方，各アクションによる報酬が従う確率分布に関する知識は一切持たないため，最良なアクションを探し出すために様々なアクションを試して各々の期待報酬を推定しなければならない．プレイヤーが次に選ぶアクションを決める規準を戦略という．戦略の良し悪しの定量的評価としてある最適戦略と実際にその戦略に従うアクション選択をおこなったときに得られる累積期待報酬の差で定義される（累積）期待リグレットが一般的に用いられる．この期待リグレットは理論的解析によってその上界をアクション数や選択回数による不等式で示すことができる [3]．しかし，限られた時間の間のアクション選択によって累積報酬を最大化したいという目的を考えると，各 ∗_{連絡先: 北海道大学大学院情報科学研究科} 〒 060-0814 北海道札幌市北区北 14 条西 9 丁目 E-mail: [email protected] アクションを実行するためにかかる時間が異なる場合に不都合を生じる．多腕バンディット問題の代表的な応用例として知られる治験においても，それぞれの薬が効果を発揮するまでの期間が異なるという状況が考えられる．期間あたりの治療人数を最大化したい場合は，単純に薬の効果だけでなく，効果を発揮するまでにかかる服用期間を考慮しなければならない．本稿ではそのような各アクションを実行するのに必要な時間である処理時間の概念を導入した確率的多腕バンディット問題を考える．前述の治験の例では，それぞれの薬を投与がアクション，その薬が効果を発揮するまでにかかる服用期間が処理時間にあたる．この問題に対して，確率的多腕バンディット問題に対する代表的戦略 UCB [3] を元にした戦略 N-UCB (Normalized UCB) を提案する．また N-UCB に関してリグレット解析を行ったを結果を示す．

2 問題設定

プレイヤーには K 個のアクション（行動）が与えら れている．そのそれぞれを単に整数 1, . . . , K で表すこ ととし，全てのアクションの集合を A ={1, . . . , K} と する．各アクション i は処理時間 Li> 0 を持つ．この 処理時間によって，プレイヤーが時刻 t においてアク ション i を選んだとき，報酬を得て次のアクションを 選択できる時刻は t + Liとなる．この条件のもと，プ レイヤーは時刻 0 から T までの間アクション選択を繰 り返し報酬を得る．ただし，終了時刻 T はプレイヤー は未知の情報である．人工知能学会研究会資料 SIG-FPAI-B403-06

(2)

時刻 t においてアクション i を選んだときに得られ る報酬を Xi(t)∈ [0, 1] と表す．Xi(t) は選択したアク ションのみから決まる確率分布 νiに従い出力される．ただし，選択したアクションによる処理時刻が経過した段階で終了時刻を越えていた場合，報酬は 0 とし繰り返しを終了する．同一アクションによって異なる時 刻で出力される報酬 Xi(t) と Xi(s) (t̸= s) は i.i.d. で ある一方，同一時刻で異なるアクションから出力され る報酬 Xi(t) と Xj(t) (i̸= j) は相関があってもよいこ ととする．また，アクション i を選択して得られる報 酬の期待値を µiと表す． プレイヤーが実際に時刻 t において選択するアクシ ョンを I(t) と表す．これを決定する規準を戦略（pol-icy，もしくは strategy）といい，形式的には過去の選 択 I(0), I(t2), . . . , I(tn) (tn≤ t) とその選択によって得

た報酬 XI(0)(0), XI(t2)(t2), . . . , XI(tn)(tn) (tn ≤ t) か

らアクション集合への写像_{P : (A × [0, 1])}n _{→ A とし} て定義される．ここで tnは n 回目の選択を行った時刻 を表す，すなわち tn = { 0 (n = 1) LI(tn−1)+ tn₋₁ (n≥ 2) である．時刻 T 以前にアクション選択を行った時刻の タイムスタンプ集合を D(T ) ={tn| n ≥ 1, tn+1≤ T } と表すこととする．プレイヤーの目的は時刻 0 から T までの間の累積報酬 G(T ) = ∑ t∈D(T ) XI(t)(t) を最大化することである．Algorithm 1 に本稿で扱う処理時間を導入した多腕バンディット問題の流れを示 した．ここで，全てのアクションの処理時間が L1 = · · · = LK = 1（かつ T が自然数）であればこのバン ディット問題は古典的多腕バンディット問題 [3, 7] と一致する． Algorithm 1 処理時間を考慮したバンディット問題 1: t← 0.0． 2: while t < T do 3: アクション I(t)∈ A を選択する． 4: if t + LI(t)≤ T then 5: 報酬 XI(t)(t)∼ νI(t)を得る． 6: end if 7: t← t + LI(t)． 8: end while 所与の戦略が累積報酬の最大化をどれだけ達成できているかの定量的な評価指標として，（累積）期待リ グレットを導入する．期待リグレットは T 時間の間に 最適戦略によって得られる累積報酬と，プレイヤーが実際に得る報酬の差の報酬分布をわたる期待値で定義されるもので，小さいほどその戦略が大きい累積報酬を得られるものであることを示す．最適戦略としてここでは常に単位時間あたりの期待 報酬が最大となるアクション i∗，すなわち i∗= arg max i∈A µi をとる戦略を採用し，これを最適アクションと呼ぶこととする．終了時刻を超過するアクションを選んだ場合報酬を得ることができないことから，終了時刻間際では単位時間あたりの期待報酬がやや小さくとも終了時刻に間に合うような処理時間が短いアクションを選ぶことで累積期待報酬を最適戦略よりもわずかながら増加させることができる戦略が存在することがある． T 時間累積期待リグレット R(T ) を R(T ) = E   ∑ t∈D(T ) ( µi∗LI(t) Li∗ − XI(t)(t) )  で定義する，最適でないアクション i̸= i∗_{について，単} 位時間あたりの期待報酬の差 ∆i= (µi∗/Li∗)−(µi/Li) および時刻 t までにアクション i を選択した回数 Ni(t) = ∑ s∈D(t) I{I(s) = i} を導入することで， R(T ) =∑ i∈A ∆iLiE[Ni(T )] (1) という関係を示すことができる．ただし_{I{·} は指示関} 数である．すなわち，リグレットは最適でないアクションを選択する回数と密接な関係を持つ．

3

4 アクション選択戦略

N-UCB

N-UCB (Normalized UCB) は処理時間の長短に合わせて評価値を正規化し，アクション依存の調整係数 βi > 0 を導入した UCB 戦略 [3] の拡張である． 各アクション i について，期待報酬 µiを初めの s 回 で得た報酬から推定した値を ˆµi(s) とする．形式的には ˆ µi(s) = 1 s ∑ t_{∈D(T )} I(t)=i,Ni(t)≤s Xi(t) と表される．このとき，N-UCB の評価関数は式 (2) で定義される． Bi,s(t) = ˆ µi(s) Li + 1 Li √ α ln+(βit) s (2) ただし ln+(x) = max{0, ln(x)} である．このアクショ ン評価関数により時刻 t で選択するアクション I(t) を

I(t) = arg max

i∈A Bi,Ni(t)(t) によって決定する．ただし，初めに全てのアクション を一度ずつ選ぶ初期化のために，Bi,0(t) =∞ とする． N-UCB は全てのアクションの処理時間が 1 かつ βi= 1 としたとき UCB と一致する．UCB のリグレット解 析の結果によると，学習率 α について α > 1/2 のとき 期待リグレットの上界を O(K ln(T )) で抑えられること が知られている [4]．調整係数 βiはその値をを変更することで，大きい値が設定されたアクションは選ばれやすく，小さいアクションは選ばれにくくすることができる．具体的な値の設定についてはリグレット解析の章で改めて議論する．

5 リグレット解析

本章では処理時間を導入したバンディット問題のうち，全アクションの処理時間を整数で表すことができる場合に対して N-UCB を用いたときの期待リグレットの上界の証明を与える．スペースの都合上，以後_{∗ = i}∗, ci,s(t) = √ α ln+(βit)/s，Lmin= min{Li | i ∈ A} と いう略記を用いる，以降に示す定理は全アクションの処理時間を整数比で表すことができるならば，スケーリングにより一般性を失わず適用することができる．

5.1 分布依存上界

初めに報酬の確率分布によって決まる定数 ∆iを含む形の上界を示す．N-UCB は UCB の拡張として構築されているため，証明手順も Auer らによる方式 [3] に概ね従うものとなっている． N-UCB を用いたアクション選択による期待リグレットの上界を示すに先立って，必要な定理や補題を述べる． 定理 1 (正規化された Chernoﬀ-Hoeﬀding の不等式). n≥ 1 個の確率変数 X1, . . . , Xnについて，i.i.d. かつ値 域が [0, 1] であるとする．そのとき，期待値 µ = E[Xt] と任意の a≥ 0 について， Pr { 1 n n ∑ t=1 Xt≤ µ − a } ≤ exp(−2na2₎ かつ Pr { 1 n n ∑ t=1 Xt≥ µ + a } ≤ exp(−2na2₎ が成立する． 補題 1. 処理時間を考慮した多腕バンディット問題に対 し N-UCB を用いたとき，I(t) = i̸= ∗ ならば，次のい ずれかが成立する． ˆ µi(Ni(t))≥ µi+ ci,Ni(t)(t) (3) ˆ µ_∗(N_∗(t))≤ µ_∗− c_∗,N_∗(t)(t) (4) µ_∗ L_∗ < µi Li +2ci,Ni(t)(t) Li (5) Proof. I(t) = i̸= ∗ ならば ˆ µi(Ni(t)) Li +ci,Ni(t)(t) Li >µˆ∗(N∗(t)) L_∗ − c_∗,N_∗(t)(t) L_∗ (6) が成立する．一方，式 (3)，(4)，(5) のいずれも成立しないとすると， ˆ µi(Ni(t)) Li +ci,Ni(t)(t) Li ≤ µi Li +2ci,Ni(t)(t) Li < µ∗ L_∗ ≤ ˆ µ_∗ L_∗ + c_∗,N_∗(t)(t) L_∗ が導かれる．これは式 (6) と矛盾する．

(4)

次に示す定理が，N-UCB を用いたときの期待リグレットの上界に関するものである． 定理 2. 処理時間を考慮した多腕バンディット問題に対 し N-UCB を用いたとき，全ての処理時間が整数なら ば任意の α > 1 および βi> 0 (i∈ A) において期待リ グレット R(T ) は R(T )≤ ∑ i:∆i>0 4α ln+(βiT ) Li∆i + Li∆i (( β_i−2α Li +β −2α ∗ L_∗ ) ( 1 2α− 2+ 1 ) + 1 ) を満たす． Proof. 本証明では E[Ni(T )]≤ 4α ln+(βiT ) (Li∆i)2 + ( β_i−2α Li +β −2α ∗ L_∗ ) ( 1 2α− 2+ 1 ) + 1 を示すことを目指す．式 (1) によってこの証明が定理 2 の証明となることは明らかである． 任意の自然数 ℓ によって，Ni(T ) は Ni(T ) = ℓ + ∑ t_{∈D(T )} I{I(t) = i, Ni(t)≥ ℓ} と書き直すことができる．ここで補題 1 を用い Ni(T )≤ ℓ + ∑ t∈D(T ) I { µ_∗ L_∗ < µi Li +2ci,Ni(t)(t) Li , Ni(t)≥ ℓ } + ∑ t_{∈D(T )} I{ˆµi(Ni(t))≥ µi+ ci,Ni(t)(t)} + ∑ t∈D(T ) I{ˆµ∗(N∗(t))≤ µ∗− c∗,N∗(t)(t)} という分解を得る．一つ目のの指示関数の部分につい て，ℓ≥ ⌈4α ln+(βiT )/(Li∆i)2⌉ とすると µ_∗ L_∗ − µi Li − 2ci,Ni(t)(t) Li > ∆i− 2 Li √ α ln+(βit)(Li∆i)2 4α ln+(βiT ) = ∆i− ∆i= 0 が成立することから常にそのイベントが発生しないことが示される．よって， Ni(T )≤ 4α ln+(βiT ) (Li∆i)2 + 1 + ∑ t∈D(T ) I{ˆµi(Ni(t))≥ µi+ ci,Ni(t)(t)} + ∑ t_{∈D(T )} I{ˆµ∗(N_∗(t))≤ µ_∗− c_∗,N_∗(t)(t)} であることが示される．次に，全てのアクションの処理時間が整数であるこ とから，あらゆる D(T ) に関し D(T ) ⊆ {1, . . . , ⌊T ⌋} が成り立つことが分かる．また，時刻 t における Ni(t) の値域が_{{1, . . . , ⌊t/L}_i_{⌋} であることから} E   ∑ t∈D(T ) I{µˆi(Ni(t))≥ µi+ ci,Ni(t)(t) }_ ≤ ⌊T ⌋ ∑ t=1 ⌊t/L∑i⌋ s=1 Pr{Ni(t) = s, ˆµi(s)≥ µi+ ci,s(t)} ≤ ⌊T ⌋ ∑ t=1 ⌊t/L∑i⌋ s=1 Pr{ˆµi(s)≥ µi+ ci,s(t)} を得る．ここで Chernoﬀ-Hoeﬀding の不等式（定理 1） を用いることで任意の βi> 0，t≥ 0 において Pr{ˆµi(s)≥ µi+ ci,s(t)} ≤ (βit)−2α が成立することを示すことができる．このことを用いると， ⌊T ⌋ ∑ t=1 ( t Li ) (βit)−2α≤ β_i−2α Li ⌊T ⌋ ∑ t=1 t1−2α のようにして上から抑えることができる．最後に α > 1 を仮定すると初等的な積分によって ⌊T ⌋ ∑ n=1 t1−2α≤ 1 + ∫ _∞ 1 t1−2αdt≤ 1 + 1 2α− 2 が示される．よって， E   ∑ t_{∈D(T )} Pr{µˆi(Ni(t))≥ µi+ ci,Ni(t)(t) }_ ≤βi−2α Li ( 1 2α− 2 + 1 ) が成立する．また，同様の手順によって E   ∑ t∈D(T ) Pr{µˆ_∗(N_∗(t))≤ µ_∗− c_∗,N_∗(t)(t) }_ ≤β∗−2α L_∗ ( 1 2α− 2 + 1 )

(5)

を示すことができる．最後に，全ての結果を組み合わせることで E[Ni(T )]≤ 4α ln+(βiT ) (Li∆i)2 + ( β_i−2α Li +β −2α ∗ L_∗ ) ( 1 2α− 2+ 1 ) + 1 を得る． 定理 2 は一般の調整係数 βiの設定に関するものであ る．この定理の結果によると，N-UCB は Li，βiおよび ∆iを定数とみなした場合期待リグレットの上界が O(K ln(T )) で抑えられることを示している．この結果 は古典的多腕バンディット問題における UCB に関するものと一致する．次に，典型的な調整係数の設定によって得られる系を紹介する． 系 1. βi= 1 (i∈ A) としたとき，期待リグレット R(T ) に関して， R(T )≤ ∑ i:∆i>0 4α ln(T ) Li∆i + Li∆i (( 1 Li + 1 L_∗ ) ( 1 2α− 2+ 1 ) + 1 ) (7) が成立する．系 1 は調整係数を無視した場合に得られる期待リグレットの上界を示している．ここで式 (7) の第二項に着目すると，非常に短い処理時間のアクションがある場合に期待リグレットの上界が大きくなることが予想される．このようなアクションが期待リグレットに及ぼす影響を抑えるために，アクションごとに異なる調整係数を与えたひとつの例が次の系である． 系 2. βiとして βi= L− 1 2α i を用いた N-UCB の期待リ グレット R(T ) に関して，βi> 1/T であれば R(T )≤ ∑ i:∆i>0 4α ln(T )− 2 ln(Li) Li∆i + Li∆i ( 1 α− 1+ 3 ) (8) が成立する．系 2 で各アクションに与えた調整係数は処理時間が長いアクションほど小さく，短いほど大きくなる．式 (8) をみると第二項の値は処理時間が短ければ短いほど小さく抑えられるようになったことが確認できる． 注 1. 定理 2 は α > 1 の場合に期待リグレットの上界 が O(K ln(T )) で抑えられることを示している．しかし

peeling argument [1, 4] を用いることで UCB と同様に

α > 1/2 で期待リグレットの上界が O(K ln(T )) で抑え られることを証明できる．その証明はやや煩雑であり ながら期待リグレットの K および T に関するオーダ に影響しないため割愛する．

5.2 分布に依存しない上界

定理 2 が示す期待リグレットの上界は律速項の係数 に報酬の確率分布から決まる値 1/∆iを含む．∆iはア クション i と最適アクションの単位時間あたりの期待 報酬の差であり，これが極めて小さいようなアクションがあるとき，定理 2 で示した上界は数値的に発散してしまう．しかしながら，単位時間あたりのリグレッ トは高々1/Lminであることから，確率変数としての累 積リグレットは T /Lminという自明な上界を持つ．これらのことを用いると，分布依存定数 ∆iの値によらない期待リグレットの上界を示すことができる [1, 4]． N-UCB に関しても，分布に依存しない形の期待リグレットの上界を証明する． 定理 3. N-UCB を用いたときの期待リグレット R(T ) について，報酬の確率分布によらず以下の不等式が成立する． R(T )≤ 2√αKT ln+(βmaxT ) +∑ i∈A ( 2√αT ln+(βiT ) Li √ K + LiCi(α) Lmin )

ただし，βmax= max{βi| i ∈ A}，

Ci(α) = ( β_i−2α Li +β −2α ∗ L_∗ ) ( 1 2α− 2 + 1 ) + 1 である． Proof. ϵ∈ (0, 1/Lmin] を導入し，定理 2 より， R(T )≤ ∑ j:∆j<ϵ ∆jLjNj(T ) + ∑ i:∆i≥ϵ 4α ln+(βiT ) Li∆i + Li∆iCi(α) を得る．第一項は， ∑ i∈A LiNi(T )≤ T であることから， ∑ j:∆i<ϵ ∆jLjNj(T )≤ ∑ j:∆i<ϵ ϵLjNj(T )≤ ϵT

(6)

で抑えられる．一方第二項は ∆i≤ 1/Lminから ∑ i:∆i≥ϵ 4α ln+(βiT ) Li∆i + Li∆iCi(α) ≤∑ i_∈A 4α ln+(βiT ) Liϵ +LiCi(α) Lmin で抑えられる．ここで，ϵ を小さくとると第一項が小 さく，大きくとると第二項が小さくなることがわかる．両者のバランスをとる値として ϵ = 2 √ αK ln+(βmaxT ) T を与えることで，第一項は ϵT ≤ 2√αKT ln+(βmaxT )，第二項の総和の中についても 4α ln+(βiT ) Liϵ +LiCi(α) Lmin ≤ 4α √ T ln+(βiT ) √ ln+(βiT ) Li √ αK√ln+(βmaxT ) +LiCi(α) Lmin ≤ 2 √ αT ln+(βiT ) Li √ K + LiCi(α) Lmin を得る．ここで ln+(βiT )/ ln+(βmaxT )≤ 1 を用いた． アクション数が K であることに注意すると，定理 3 で 示された上界は Li, βiを定数とみなすと O (√ KT ln(T ) ) であることがわかる．同様の証明は古典的多腕バンディット問題における UCB に関しても示されており，こ ちらも O(√KT ln(T ) ) で抑えられることが示されている [1]．古典的多腕バンディット問題において，分布に依存しない期待リグレットの下界は Θ(√KT ) であ ることが知られていて，それをを達成する戦略として MOSS が考案されている [1]．ただし，MOSS は終了 時刻 T を事前に知っていなければならない anytime で ない戦略となっている1_．

6 おわりに

古典的な確率的多腕バンディット問題に対し処理時間の概念を導入し，経過時間に基づく最適戦略およびリグレットの考えに基づき，UCB の拡張である N-UCB を提案した．N-UCB に関して，処理時間が整数で表現できる場合に限り期待リグレットの上界を証明した． 1_{UCB に代表される終了時刻 T を知らなくても実行できる戦略}

を anytime であるという．N-UCB も anytime な戦略である．

今後の課題として，処理時間に対して仮定をおかない期待リグレットの上界を示すことが挙げられる．このとき問題となるのが選択を行いうるタイムスタンプが報酬の確率分布に強く影響を受けることと，そのとりうる時刻は有限ではあるものの非常に多くに存在するという点である．しかし実際に選択が行われる回数は高々_⌈T/L_min_{⌉ 回で抑えられることや，時刻の経過に} 応じて期待値の推定精度は単調に上がってゆくことなどが手がかりとなると考えられる．本稿で示したのはリグレット解析による理論的な評価の結果のみである．そのような理論的アプローチのみならず，その裏付けとなるような実験的評価を計算機シミュレーションなどにより行うことも重要である．

参考文献

[1] Jean-Yves Audibert and S´ebastien Bubeck. Re-gret bounds and minimax policies under partial monitoring. The Journal of Machine Learning

Re-search, 11:2785–2836, 2010.

[2] Jean-Yves Audibert, S´ebastien Bubeck, and R´emi Munos. Best arm identification in multi-armed bandits. In Proceedings of the 23rd Conference on

Learning Theory, pages 41–53, 2010.

[3] Peter Auer, Nicol´o Cesa-Bianchi, and Paul Fis-cher. Finite-time analysis of the multiarmed ban-dit problem. Machine learning, 47(2):235–256,

2002.

[4] S´ebastien Bubeck. Bandit Games and Clustering

Foundations. PhD thesis, Universit´e Lille 1, 2010. [5] Junpei Komiyama, Issei Sato, and Hiroshi Naka-gawa. Multi-armed bandit problem with lock-up periods. In Proceedings of the 5th Asian

Confer-ence on Machine Learning, pages 100–115, 2013.

[6] Tze L. Lai and Herbert Robbins. Asymptotically eﬃcient adaptive allocation rules. Advances in

ap-plied mathematics, 6(1):4–22, 1985.

[7] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American

処理時間の長短を考慮した確率的多腕バンディット問題へのUCB戦略の拡張