ARG WI2 No.17, 2021

仮想的な探索を用いて文脈や時間の経過による番狂わせにも迅速に追従する多腕バンディット手法
三宅 悠介 †, a

峯 恒憲 ††, b† 九州大学 大学院システム情報科学府 情報知能工学専攻/GMO ペパボ株式会社 ペパボ研究所†† 九州大学 大学院システム情報科学研究院 情報知能工学部門a) miyakey@pepabo.com b) mine@ait.kyushu-u.ac.jp
概要 多腕バンディット問題は，腕と呼ばれる複数の候補から得られる報酬を最大化する問題である．同問題のWeb サービスへの応用では，利用者の嗜好傾向が多様かつ継続的に変化する課題に対処するため，文脈や時間の経過を考慮した問題設定への拡張と方策が提案されている．しかし従来の方策は，腕の相対的な有用性が逆転する環境で，不充分な追従性や非効率な探索に起因する機会損失が増加してしまう．本研究では，このような番狂わせを含む環境であっても機会損失を低減可能な方策を提案する．提案手法では，線形カルマンフィルタを用いた継続的な状態推定によって文脈や時間の経過に応じた変化に迅速に追従する．さらに，状態推定の欠損値処理を仮想的な探索に見立て，探索効率を高める．評価では，方策の追従性と探索効率を分析するための新たな指標を導入し，これらが従来の方策と比べて提案手法により改善することを確認した．
キーワード

1

多腕バンディット問題，線形カルマンフィルタ，非定常，コンテキスト

はじめにている．この拡張された問題設定は，文脈付き，かつ，

適応的なシステムの実現には，利用者と情報システ

非定常な多腕バンディット問題と呼ばれ，いくつかの方ムが互いの状態をよく理解するためのコミュニケーショ策が提案されている．これらの方策では，文脈や時間のンと，それに応じた振る舞いの変更が必要となる．一方

経過に応じて迅速に腕の評価を更新する性能が注目されで，そのコミュニケーションから得られる情報や利益のてきた．一方で，この問題設定では番狂わせが発生する

価値を考慮しなければならない環境では，確実な情報に場合がある．ここで番狂わせとは，文脈や時間の経過に基づく振る舞いを選択しつつ，まだ得られていない情報

応じて腕の相対的な有用性が逆転する状況の中で，最善を引き出すために，価値の低いコミュニケーションを敢の腕の有用性は維持されながらも，その他の腕の有用性

行しなければならない．このような，振る舞いの候補にが向上した結果，逆転する状況を指す．探索を減らして対する利用と評価のトレードオフの最適な解を求める問

機会損失を抑える方策では，この状況を察知するのは難

題は，多腕バンディット問題として知られている．このしく，全ての腕の全ての文脈で一律に継続的に注意を払問題は，腕と呼ばれる複数の候補から得られる報酬を最うような方策では，全体的な機会損失を増加させてしま大化する問題である．プレイヤーは各試行で 1 つの腕をう．また，これらの不充分な追従性や非効率な探索に加選択し，その腕から報酬を得る．各腕はある確率分布にえ，試行ごとの評価の更新処理に時間がかかる方策も多従い報酬を生成するが，プレイヤーは試行の結果からこい．そのため，この番狂わせな環境に対応するには，評の確率分布を推測しなければならない．そのため，プレ価の更新に加え，変化の検出も迅速かつ効率的に，軽量

イヤーはある時点の腕ごとの評価に基づき，最も評価のな機構により行われる必要がある．

高い腕を用いながらも，真に評価の高い腕の探索を並行

本研究では，仮想的な探索を用いて文脈や時間の経過して行う．この問題に対する方策では，ある時点で最もによる番狂わせにも効率的かつ迅速に追従する多腕バン

評価の高い腕を用いることを活用，各腕の評価を行うこ

ディットの方策を提案する．提案手法では，文脈に応じとを探索と呼び，これらの活用と探索，報酬による評価て推定した状態に基づき腕を選定する．状態の推定に，の見直しを繰り返し行うことで，短期的には探索による軽量で多変量の特徴量を扱うことができる線形カルマン

機会損失を，長期的には腕の固定化による機会損失を低フィルタを用いることで文脈の考慮と実行時間の短縮を減する．

図る．また，線形カルマンフィルタの欠損値処理を仮想同問題の Web サービスへの応用では，利用者の嗜好的な探索と見立て，選定されなかった腕に対しても評価傾向が多様かつ継続的に変化する課題に対処するため，を更新することで，評価の低い腕に対する長期的な探索

文脈や時間の経過を考慮した問題設定への拡張がなされを促しながらも，実際の探索を最小限に抑えられる．

Copyright is held by the author(s).
The article has been published without reviewing.

変化するシミュレーションを実施し，提案手法と従来の評価では，文脈と時間の経過に応じて候補の有用性がWeb インテリジェンスとインタラクション研究会予稿集

方策を比較した．比較のため，方策の追従性と探索効率たモデルの導入や履歴の削除によって，過去に観測したを分析するための新たな指標を導入し，これらが従来の報酬に捉われずに腕の再評価を迅速に行うが，評価の低方策と比べて提案手法により改善することを確認した．

い腕に探索を促す仕組みを備えていない．また，迅速な本報告の構成を述べる．2 節で多腕バンディット問題

評価の更新のため導入される粒子フィルタやブートスト

における番狂わせの課題について述べる．3 節では，2

ラップといった機構の実行に時間がかかるという課題が節で述べた課題を解決する提案手法について述べる．4ある．Decay LinUCB [5] は報酬に対する重み付けによ節では提案手法の評価を行い，5 節でまとめる．

り腕の再評価を迅速に行う．この手法では，腕の相対的な選定回数の差に基づき始めは探索が促されるが，選定

2

多腕バンディット問題における番狂わせと，回数に対する減衰操作により徐々に探索が減ってしまう．

その課題

Dynamic Linear UCB (dLinUCB) [6] と Dynamic

多腕バンディット問題では，多様かつ継続的に変化す

Ensemble of Bandit Experts (DenBand) [7] は報酬予る利用者の嗜好傾向のような，報酬分布の変化を想定し測の誤差の変化を検出し，新たな報酬分布に適したバン

た問題設定について，文脈と非定常性という 2 種類の観

ディットのモデルを追加する．追加されたモデルでは変点から拡張が図られている．文脈付き多腕バンディット

化後の報酬を利用するため，過去に観測した報酬に捉わ問題では，複数の要因パラメータからなる文脈に応じてれないが，同時に，全ての腕に対する評価がやり直しと腕から得られる報酬分布が決定される．非定常な多腕バなる．また，これらの手法は，徐々に変化検出の閾値をンディット問題は，同じ文脈においても報酬分布が時間下げることから変化の有無によらず定期的にモデル追加

経過によって変化する問題である．利用者の嗜好傾向がと再評価を発生させる．よって間接的に評価の低い腕に多様かつ継続的に変化する環境において最適な候補を選探索を促すと見なせるものの，不要な探索が発生する．

定するには，文脈付き，かつ，非定常な多腕バンディッ

腕の報酬が確率的ではなくプレイヤーの方策を知る敵ト問題の方策を用いる必要がある．

対者によって決定される敵対的バンディットと呼ばれる

これらの方策で非定常性の解決のために採用される問題への方策である，ADA-ILTCB+ [8] は，非定常な様々な方式は，いずれも変化後の報酬分布から得られる問題設定にも用いることができる．この方策は，番狂わ

報酬のサンプルを一定数必要とする．機会損失の低減

せの発生も常に想定する必要があることから評価の低を目的とした多腕バンディット問題の設定では，各方策

い腕に対する探索を積極的に行う．しかしながら，同様

は，ある時点で評価の高い腕を最も多く活用する．そのの仮定から慢性的に探索が増加する傾向が見られる．まため，ある時点で最適腕の有用性のみが低くなるようた，文脈を扱う場合，全ての状態と腕の組み合わせからな状況では，報酬のサンプルを十分に観測することがで最適なペアを推定するため，組み合わせが爆発し実行時

き，いずれの方式も有効に働く．反対に，評価の低かっ間が指数的に増加する課題がある．

た腕が，ある時点で有効性が高くなるような番狂わせのKF-MANB [9] は，カルマンフィルタを用いて現在の状況では，新たな最適腕に対する報酬のサンプルを得る

状態を継続的に推定し，確率一致法と組み合わせることまでに時間が掛かり，以前の最適腕を選定し続ける機会

で非定常な問題を扱う手法である．この手法では，カル損失が発生してしまう．そこで，番狂わせの検出のため

マンフィルタの欠損値処理の仕組みを導入し，選定されに一定割合の探索機会を設ける方式 [1] も提案されていなかった腕に対し長期的に探索が促されるよう評価を更るが，探索を一律に増加させるため，相対的な腕の評価

新できる．このことから，変化の検出，評価の更新をそが逆転しない期間での機会損失につながってしまう．それぞれ迅速かつ効率的に行える．さらに，カルマンフィのため，方策を番狂わせに対応させるためには，評価のルタの状態推定は軽量であることから，実行時間の課題

低い腕の有効性の変化を素早く察知できるよう探索を行も生じにくいという利点がある．しかしながら，この手

いつつ，その探索に伴う機会損失を減らすことが求めら

法では一次元の状態しか扱えないため，文脈によって報れる．このような方策は，推薦手法のコールドスタート

酬分布が異なるような文脈付きの問題設定の場合に対応のように，一定の嗜好情報が蓄積されるまでその有効性できない．

が現れない選択肢を比較評価する状況で必要になると考提案手法えられる [2]．以降では，従来の方策での，番狂わせへ

3の対応の課題を個別に分析する．

3.1

Time varying Thompson sampling (TVTP) [3]，Adap-

確率一致法による線形カルマンフィルタとの統合

tive Thompson Sampling (AdTS) [4] は評価の更新のみ

線形カルマンフィルタは，観測時の誤差を含む時系列に着目した手法である．これらは，非定常性を前提としデータに対し，時系列の観測値ならびにその背後にある

Proceedings of ARG WI2た観測値から，この状態空間モデルで表現された時系列

Algorithm 1: Linear KalmanFilter Bandits
1
2

ならびにその背後にある状態を逐次的に推定する．推定

procedure MAIN(): ▷ main entry

は，与えられた t = 1 時点の初期状態 α1 の平均 µ1 とInitialize K arms with

分散共分散 P1 を起点とし，フィルタリングと一期先予µ1 , P1 , Z(xt ), H, T, R(xt ), Q.

測と呼ばれる操作を交互に行う．

3

for t ← 1, T do

4

Get xt .

5a(k) = arg max SAM P LE(a(j) , xt )フィルタリングは，t 時点での観測値 yt と予測した観測値 Zµt の誤差から，その時点での状態を推定する操作である．この操作によって得られる状態 αt の平均と

j=1,K
(k)

6

Receive rt by pulling arm a

7

for j ← 1, K do

Pt|t と表す．フィルタ化推定量の算出は以下の通り．

F ILT ER(xt , a(j) , rt , j == k).
P REDICT (xt , a(j) ).

8
9

10

分散共分散をフィルタ化推定量と呼び，それぞれ µt|t ，.

µt|t = µt + Kvt
Pt|t = Pt − KFt K T

procedure SAMPLE(a(j) , xt ): ▷ sample for

ここで，vt = yt − Zµt ，Ft = ZPt Z T + H ，K =a(j) , given xt .
(j)

(j)

Pt Z T Ft−1 とした．

(j)∼ Nm (µt , βPt ).

11

Sample st

12

return xTt st .

一期先予測は，先に求めたフィルタ化推定量を用いて

(j)

13

t + 1 時点の状態を推定する操作である．一期先予測に

procedure FILTER(xt , a(j) , rt , observed):

おける状態 αt+1 の平均 µt+1 と分散共分散 Pt+1 の算出▷ filter the state, given xt , rt .
14
15
16

は以下の通り．

if observed thenZt = Z(xt )µt+1 = T µt|t
Pt+1 = T Pt|t T T + RQRT

Get ﬁltered estimator µt|t , Pt|t for a(j)by Equation (3).

17
18
19

20

(3)

(4)

提案手法では，この推定した状態を多腕バンディット問題における腕の選定に利用する．はじめに，腕ごとに

else
(j)
(j)
µt|t = µt(j)(j)
Pt|t = Pt

線形カルマンフィルタによって推定された状態の平均と分散共分散を得る．次に，それらを平均と分散共分散とする多変量正規分布からサンプリングを行う．なお，多procedure PREDICT(xt , a(j) ): ▷ predict

腕バンディット問題としての探索のバランスを調整でき

the state, given xt .

るよう，分散共分散に対してスケール項 β を設けた．最21

Rt = R(xt )22

Get predictor µt+1 , Pt+1 for a(j) by

後に，サンプリングされた値とコンテキスト xt との内積が最も大きかった腕を選定する．これらは，線形カル

Equation (4).

マンフィルタの状態推定値を用いた確率一致法とみなすことができる．なお，この工程は Algorithm1 の 5 行目

状態の推定を行う手法の一つである．この手法では，対ならびに 10 から 12 行目に相当する．

3.2

象の時系列を以下の状態空間モデルで表現する．

欠損値処理による仮想的な探索

線形カルマンフィルタは，ある時点で観測値が得られ

yt = Zαt + ϵt ,ϵt ∼ Np (0, H)(1)ない場合も欠損値として適切に扱うことができる．提案

αt+1 = T αt + Rηt ,ηt ∼ Nr (0, Q)(2)

手法では，この欠損値処理を多腕バンディット問題において選定されなかった腕に対する評価の更新操作として

ここで yt ∈ Rp と αt ∈ Rm は t 時点の観測値と状態を，取り入れる．この仮想的な探索による評価更新は，各時

ϵt は平均 0 分散共分散 H ∈ Rp×p ，ηt は平均 0 分散共点で選定した腕の評価のみを更新する従来の多腕バン

分散 Q ∈ Rr×r の多変量正規分布 N から得られる誤差

ディットの方策に比べ，以下の 2 つの効果が期待できる．

を表す．なお，本稿では N の添字は変量の次元数を示

第一は，番狂わせの早期検出である．線形カルマン

す．また，Z ∈ Rp×m は，状態空間から観測値空間へのフィルタでは，欠損値に対するフィルタ化推定量は，式

写像，R ∈ Rm×r は，誤差空間から状態空間への写像，(3) の結果ではなく t 時点の状態として推定した平均 µt

T ∈ Rm×m は，時点の経過に伴う状態の推移を表現している．線形カルマンフィルタは，t 時点までに得られと分散共分散 Pt となる．一方，一期先予測は観測値を得た場合と同様に行う．状態の分散共分散に着目すると，

Web インテリジェンスとインタラクション研究会予稿集

フィルタリングは分散共分散を小さく，一期先予測は大表 1 方策の腕の選定に関する混同行列

きくするよう更新する．そのため，選定されない腕では

活用

探索

一期先予測のみ行われることで分散共分散が継続的に増

最適腕

1
⃝

2
⃝

加し，確率一致法の仕組みにより該当する腕の探索が促

最適腕以外

3
⃝

4
⃝

される．
第二は，評価の更新に伴う機会損失の低減である．線

3 に該当する試行のみから再評価する．一方，たことを⃝形カルマンフィルタでは，先の欠損値処理により観測値

2 に該
番狂わせの場合，新たな最適腕を再評価するため⃝を用いずとも一期先予測による状態の推定が可能であ当する試行が必要となる．そして，どちらの場合でも，る．すなわち，状態のモデルにトレンドや周期的成分が1 に該当する試行
最適腕を正しく切り替えられたならば⃝含まれ，これを正しく推定できている場合，探索を経ずが増加する．よって，最適な腕が切り替わる状況に迅速に状態の推移傾向を捉えることができる．この探索が不1 に対し，⃝
2 と⃝3 の値をかつ効率的に追従可能な方策は⃝

要な予測機能により，腕の有用性の変化を検出して評価小さく保つと期待される．

が逆転するまでの期間における途中経過の評価を把握す

この仮定に基づき，変化への追従性と探索効率の指標

るための探索を減らし，探索効率の向上が期待できる．

としての F0.5 値を表 1 の混同行列から算出する．これは

これらは Algorithm1 の 18 から 19 行目に相当する．

分類問題の評価に使われる同指標を先の混同行列に適用

時変行列による文脈に応じた腕の評価更新

11
3
したもので，Precision(P = ⃝/(⃝+⃝))と Recall(R =3.3

多次元の要素からなる状態を扱う線形カルマンフィル
タでは，この状態と観測値，誤差の次元数の整合性を取るため，式 (1) における Z や式 (2) における R のような行列を必要とする．これらの行列 Z, R は，式 (3) のフィ
ルタリングや式 (4) の一期先予測において状態の平均や分散共分散のどの要素を更新するかを決定している．多様な文脈を扱う多腕バンディットにおいて，常時同じ行列を用いて，文脈に関連しない状態の要素を更新することは，推定の精度を低下させ非効率な探索が発生してしまう．このような状況として，排他的に発生する文脈において同じ腕であっても有用性が異なる状況が挙げられる．この状況では，ある文脈での試行に対する欠損値処
理が，異なる文脈も含んだ分散共分散の継続的な増加に繋がり，本来不要な探索を引き起こす．
提案手法では，文脈に応じて行列 Z, R を切り替えることでこの問題を解消する．これらの時変の行列 Zt , Rt
は，t 時点のコンテキスト情報 xt のうち値が 0 より大きい要素と対応する成分のみ 1 を設定して得られる．例P ·R
1
1 + ⃝))
2⃝/(⃝の重み付き調和平均 (F0.5 = 1.25 0.25P+R )
2 がである．Precision を重視する F0.5 値とするのは，⃝

最適腕への探索であり，誤判定ではあるものの試行の増加に対して短期的な機会損失が生じにくいためである．
従来の評価指標に用いられる累積リグレットは各時点
で最善の腕の期待値と選択した腕の期待値の差を期間までに合計したものである．この指標では，腕の選定にお
2 ⃝
3 ⃝
4
ける方策の判断は区別されておらず，値の増加が⃝のどれに起因するものかを把握できない．結果として，方策による追従性の差異の分析が定性的な考察に留まるか，分析の観点が不統一なことが多かった．本指標により，変化に対する各方策の挙動の特性を定量的に示すことが可能になり，本分野での有意義な議論の促進につながると考える．

評価

4
4.1

評価方法

本報告では，文脈と時間の経過に応じて腕の有用性

として，状態のモデルにトレンドや周期的成分を含まが変化する状況のシミュレーションを通して提案手法のず xt ∈ {0, 1}m の場合，時変の行列 Zt , Rt はそれぞれ有効性を評価する．評価は 10 本の候補より選定した腕Zt = xT
t ，Rt = xt となる．これらは Algorithm1 の 15
行目と 21 行目に相当する．

3.4

方策の特性を分析する評価指標

本研究では，方策の追従性と探索効率を定量的に分析するための新たな指標を導入する．この指標では，各時点での方策の判断結果を，選定された腕が最適腕かどうか，その腕を方策が活用として選定したかどうかの四象限に分類し，全ての試行分を数え上げた，表 1 の混同行
2 と⃝3 の値から，最適列を準備する．この混同行列では⃝から得られる期間中のクリック数のシミュレーションによって行う．ここで，腕は多腕バンディットの方策によって各時点ごとに選定され，各腕は設定したクリック率のベルヌーイ分布に従いクリックされるものとする．各腕は 4 次元のパラメータ θ を持ち，選定時点 t のコンテキスト情報 xt との線形和によってクリック率を算出する．
各腕のパラメータを時間の経過に応じて変化させること
で，文脈と時間の経過に応じて腕の有用性が変化する状
況を再現する．本評価ではコンテキスト情報としてな腕が切り替わる状況での誤判定の数を把握できる．番

X = {(0, 0, 0, 1)T , (0, 0, 1, 0)T , (0, 0, 1, 1)T ,狂わせではない場合，各方策は最適腕の有用性が低下し(0, 1, 0, 0)T , (1, 0, 0, 0)T , (1, 1, 0, 0)T }Proceedings of ARG WI2

Transition of 2
arm0
arm1
arm2
arm3
arm4
arm5
arm6
arm7
arm8
arm9

0.8
0.6
0.4
0.2
0.0

0

500

1000

1500

2000

2500

図 1 腕ごとの線形パラメータ θ2 の推移

Cumulative regrets (overall)

200

Decay LinUCB
AdTS
dLinUCB150

DenBand
TVTP
LKF

100
50
0

Cumulative regrets (x = (0,1,0,0))

80
60
40

から時点 t ごとに無作為に選択された xt を用いる．各20

腕の線形パラメータのうち，2 次元目の値 θ2 の変動を0

図 1 に示す．約 500 時点で発生する最善な腕の有用性の

0

500

1000

1500

2000

2500

図 2 方策ごとの累積リグレットの推移

みが低下する状況と，約 1, 000 時点で発生する番狂わせの状況を変動として含めた．なお，パラメータの他の次元は期首に設定した値を維持する．これにより，コンテ

xt = (0, 1, 0, 0)T における各方策の腕ごとの累積選定数

キスト情報 xt ∈ {(0, 1, 0, 0)T , (1, 1, 0, 0)T } の場合にのの推移を示した．ただし，Decay LinUCB，dLinUCB はみ上述のクリック率の変動が発生する．

それぞれ TVTP と DenBand と同じ推移特性であったこ

本評価では，乱数を用いた確率の計算結果を平均化すとから図から省略した．なお，最上段は理想的な腕の選るために，異なる乱数シードを用いてシミュレーション定がなされた場合の推移である．また，括弧内の数値はを 50 回行い，この平均を結果として用いた．また，腕の各腕の累積選定数を示している．図より Decay LinUCB，評価が定まった後における変化への対応の性能を調査す

AdTS，TVTP は，番狂わせではない最初の変化には迅るため，各方策へ各腕の各コンテキスト xt ごとに 50 回

速に追従できた一方，二度目の番狂わせの検出が遅れ，分の試行結果をシミュレーション実施前に予め与えてい新たな最適腕への切替が遅れたことがわかる．これは，る．比較する方策には 2 節で紹介した文脈付き，かつ，非これらの方策に弱い腕に対する探索の仕組みが備わって定常な方策である Decay LinUCB，AdTS，dLinUCB，

いないことに起因する．反対に，dLinUCB，DenBand，

DenBand，TVTP，ADA-ILTCB+を用いる．また，提LKF では新たな最適腕への切替が見て取れる．

案手法の Linear KalmanFilter Bandits(LKF) では，状4.3

変化への追従性と探索効率の評価

態の次元数をコンテキスト xt と揃えた状態モデルを採図 4 に xt = (0, 1, 0, 0)T における方策ごとの F0.5 値と用する．なお，評価時とは異なる乱数シードでの予備評

Precision，Recall の値を示す．提案手法の LKF が，高価で各方策のパラメータ調整を実施した．パラメータい水準で Precision と Recall を両立したことで F0.5 値

調整には GP-UCB [10] を用い，方策ごとに設けたパラが最も大きくなり，誤判定の期間と新たな腕への探索を

メータの組み合わせから累積クリック数が最大となるも最小限に抑えたことがわかる．反対に，番狂わせへの追のを探索した．

従が遅れた Decay LinUCB と TVTP では，新たな最適4.2

機会損失の評価

腕への探索が極端に少なかったことから Recall は大き

図 2 に方策ごとの累積リグレットの推移を示す．上段

いが，以前の最適腕を使い続けたため Precision が小さは全ての文脈の合計，下段は図 1 の変化が起きるコン

くなり，結果として F0.5 値も小さくなっている．Decay

テキスト xt = (0, 1, 0, 0)T での結果である．破線は最LinUCB と TVTP より早いものの，やはり番狂わせへ

適腕の切替が発生する時点を表している．なお，ADA-の追従が遅れた AdTS では，F0.5 値はこれらと LKF のILTCB+については本設定における腕と文脈の組み合わ中間を示した．しかしながら，番狂わせの検出のため混せ数の増加により評価作業中に実行が完了しなかったた

4 の探索が多くなり，変化のない期間でのリグ
同行列の⃝め以降の結果から除いている．シミュレーション全体をレットの増加が観測されている．本報告時点では F0.5

通して，累積リグレットが最も少ない方策は DenBand

値は変化時の追従性と探索効率の評価指標であり，変で 94.3，次いで提案手法の LKF がほぼ同程度の 94.8 と化のない期間の評価は今後の課題である．dLinUCB となった．図より，これらの方策が，番狂わせに追従した

DenBand では，図 2 の下段からリグレットを LKF とことで全体的な累積リグレットの増加を抑えたことが同程度に抑えているにも関わらず F0.5 値が低く算出さわかる．各方策の切替の様子を確認するため，図 3 に2 の極端な増加に起因していれた．これは，混同行列の⃝Web インテリジェンスとインタラクション研究会予稿集

Best arm [81.1, 91.0, 228.3, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
arm0
arm1
arm2
arm3

200
100

arm4
arm5
arm6

arm7
arm8
arm9

0.8
0.6
0.4

0

DenBand [129.5, 65.2, 204.3, 0.2, 0.1, 0.1, 0.4, 0.0, 0.3, 0.3]
200

LKF

TVTP

図 4 方策ごとの F0.5 値と Precision，Recall

参考文献

100
0

TVTP [121.5, 232.2, 46.4, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.2]
200
100
0

LKF [113.1, 91.2, 188.9, 1.0, 1.1, 1.0, 1.5, 0.8, 1.0, 0.9]
200
100
0

500

1000

1500

2000

2500

図 3 腕ごとの累積選定数の推移

る．ここから，新たな最適腕への探索を積極的に行いながらも評価の更新が緩やかな特性を持つ方策であることがわかる．すなわち，番狂わせが短期間に高頻度で発生するような環境に課題がある可能性が考慮された値とみなせる．

5

DenBand100

0.0

dLinUCB

200

0.2
AdTS

AdTS [110.3, 102.1, 143.1, 6.9, 3.1, 3.1, 3.2, 2.4, 5.5, 20.7]

Decay LinUCB

00

F0.5 Score (x = (0,1,0,0)) with Precision(+) and Recall( )
1.0

おわりに
本報告では，線形カルマンフィルタを用いた継続的な状態推定と欠損値処理によって，番狂わせを含む環境であっても機会損失を低減可能な多腕バンディット手法を提案した．評価では，機会損失の低減の観点において従来の最先端の方策と遜色のない性能を示した．また，方策の追従性と探索効率の分析のために新たな指標を提案
し，この観点でも従来の方策に比べ改善を確認した．今後は，線形カルマンフィルタにおけるトレンドや周期変動モデルの仮想的な探索アプローチに対する有効性の評
価や，誤差の分散共分散の逐次的な推定による探索効率の向上，ならびに提案指標の改善を進めたい．

[1] Yang Cao, Zheng Wen, Branislav Kveton, and Yao
Xie. Nearly optimal adaptive procedure with change
detection for piecewise-stationary bandit. In The
22nd International Conference on Artiﬁcial Intelligence and Statistics, pp. 418–427. PMLR, 2019.
[2] 三宅悠介, 峯恒憲. Synapse: 文脈に応じて継続的に推薦手法の選択を最適化する推薦システム. 電子情報通信学会論文誌 D, Vol. 103, No. 11, pp. 764–775, 2020.
[3] Chunqiu Zeng, Qing Wang, Shekoofeh Mokhtari, andTao Li. Online context-aware recommendation withtime varying multi-armed bandit. In Proceedingsof the 22nd ACM SIGKDD international conferenceon Knowledge discovery and data mining, pp. 2025–
2034, 2016.
[4] Negar Hariri, Bamshad Mobasher, and Robin Burke.
Adapting to user preference changes in interactive
recommendation. In Twenty-Fourth International
Joint Conference on Artiﬁcial Intelligence, 2015.
[5] Muhammad Ammar Hassan. Non-Stationary Contextual Multi-Armed Bandit with Application in Online Recommendations. PhD thesis, University ofVirginia, 2015.
[6] Qingyun Wu, Naveen Iyer, and Hongning Wang.
Learning contextual bandits in a non-stationary environment. In The 41st International ACM SIGIR
Conference on Research & Development in Information Retrieval, pp. 495–504, 2018.
[7] Qingyun Wu, Huazheng Wang, Yanen Li, andHongning Wang. Dynamic ensemble of contextual
bandits to satisfy users’ changing interests. In The
World Wide Web Conference, pp. 2080–2090, 2019.
[8] Yifang Chen, Chung-Wei Lee, Haipeng Luo,and Chen-Yu Wei. A new algorithm for nonstationary contextual bandits: Eﬃcient, optimal andparameter-free. In Conference on Learning Theory,
pp. 696–726. PMLR, 2019.
[9] Ole-Christoﬀer Granmo and Stian Berg. Solving
non-stationary bandit problems by random samplingfrom sibling kalman ﬁlters. In International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, pp. 199–208.
Springer, 2010.
[10] Niranjan Srinivas, Andreas Krause, Sham M
Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995,
2009.