インターネットと運用技術シンポジウム 2020

IOTS2020
2020/12/3

Internet and Operation Technology Symposium 2020

変化検出と要約データ構造を用いた利用者の嗜好の変化に迅速に追従する多腕バンディット手法
三宅 悠介1,2,a)

栗林 健太郎1,b)

概要：多腕バンディット問題は，腕と呼ばれる複数の候補から得られる報酬を最大化する問題である．同問題の Web サービスにおける広告配信や推薦システムへの応用では，腕となる利用者の嗜好傾向が多様である課題に対処するため，利用者の文脈を考慮した線形な問題設定への拡張と解法が提案されている．一方で，時間の経過に従い報酬分布が変化する非定常な課題に対処するため，変化検出の手法を組み合わせ
報酬の変化を観察することで変化に追従する解法が提案されている．しかしながら，線形な問題設定にこの解法を適用する場合，文脈の増加に伴い各文脈での報酬の観測回数が低下するため，文脈ごとに報酬の変化を観測する方式では，変化の検出と追従が遅れてしまう．加えて，変化の検出と追従に必要な文脈ごとの報酬の履歴データのサイズも文脈の増加に伴い肥大化する．本研究では，多様な文脈であっても腕の報酬分布の変化に迅速に追従可能な，線形かつ非定常な多腕バンディット問題の解法を提案する．提案手法では，文脈ごとの報酬からではなく，文脈の数によらない固定数の値の推移のみから報酬分布の変化を検出することで，腕の報酬分布の変化に迅速に追従する．さらに，過去期間の値を要約するデータ構造を導入することで，報酬分布の変化検出と追従に必要な履歴データのサイズの肥大化を抑制する．評価では，
線形かつ非定常な多腕バンディット問題を設定し，提案手法を用いない場合と比較して変化への追従性が高いこと，履歴データのサイズの肥大化が抑えられることを確認した．

Multi Armed Bandit Method for Following Preference Changes
using Change Detection and Summary Data Structures
Abstract: A multi-armed bandit problem is a problem that maximizes reward from making choices between
candidates called arms. In the application of advertisement or recommendation system of this problem, thelinear extension of problem setting and policy is proposed to deal with users’ various preferences. On theother hand, the policy that follows changes by observing reward change using change detection methods is
proposed to deal with non-stationary problems that change reward distribution according to time. However,this policy delays the following changes because the number of reward observations for each context decreases
if the policy applies to a linear problem setting. In addition, the data size of reward history required forchange detection and follow changes increases as the number of contexts increases. In this paper, we propose
a non-stationary linear multi-armed bandit policy that can quickly follow changes in the reward distribution
in various contexts. The proposed policy follows changes by detecting a change of reward distribution fromtwo value transition that is independent of the number of contexts. Also, the policy suppresses the size ofthe historical data by introducing a data structure that summarizes the value of the past period. We set up
a non-stationary and linear multi-armed bandit problem for the evaluation and conﬁrmed our policy makes
the performance increase and suppress the size of historical data.

1

2

a)
b)

GMO ペパボ株式会社 ペパボ研究所
Pepabo R&D Institute, GMO Pepabo, Inc., Tenjin, Chuo
ku, Fukuoka 810-0001 Japan
九州大学 大学院システム情報科学府 情報知能工学専攻
Department of Advanced Information Technology, Graduate
School of ISEE, Kyushu University
miyakey@pepabo.com
antipop@pepabo.comⓒ 2020 Information Processing Society of Japan

1. はじめに
消費者向け電子商取引（以下 EC）の市場規模拡大 [1] に伴い，取り扱う商品種類は増大している．EC サイト利用者の通常の行動では全ての商品を見て回ることは困難であるため，多くの EC サイトには推薦システムが導入されて1

インターネットと運用技術シンポジウム 2020

IOTS2020
2020/12/3

Internet and Operation Technology Symposium 2020

いる．多様な利用者が訪問する EC サイトでは，全ての利

ラメータに対する係数を推定する．次に，この求めた値を用者に対する画一的な提案は必ずしも有用ではないことかベクトルとみなしその方向データの異常度と大きさの推移

ら，多くの推薦システムでは提案の個別化を図っている．

のみから報酬分布の変化検出を行う．最後に，変化以前の

このような個別化した提案では，利用者ごとに有用な提試行結果を取り除くことで，新しい報酬分布に追従させる．

案を予め知ることは難しい．そこで，推薦システムは利用

また，これらの変化検出と追従に必要な複数の履歴データ

者の嗜好を蓄積し，その時点で有用と考えられる情報を活の保存に，過去期間の値を要約するデータ構造を導入し，用した提案を行う一方で，より有用な提案につながる情報

データサイズの肥大化を抑制する．なお，提案手法は既存の探索が求められる．この活用と探索のトレードオフの最の解法に対し，変化検出と要約データ構造による拡張を施

適な解を求める問題は，多腕バンディット問題として知らすため，理論保証があり実績のある既存の線形な解法を利れている [2]．この問題は，ある確率分布に従い報酬を生用できる．評価では，線形かつ非定常な多腕バンディット

成する腕と呼ばれる複数の候補から得られる報酬を最大化

問題を設定し，既存の線形な解法に対し提案手法を適用すする問題であり，同問題に対する解法が推薦システムやイることで変化への追従性が向上すること，履歴データのサ

ンターネット広告の分野で利用されている [3][4]．一方で，イズの肥大化が抑えられることを確認した．

基本的な多腕バンディット問題では，報酬の確率分布が常本論文の構成を述べる．2 章で多腕バンディット問題のに同じであるという仮定が置かれている．推薦システムに関連研究を紹介し，推薦システムでの応用における課題において腕となる，利用者の商品に対する嗜好傾向は様々なついて述べる．3 章では，線形かつ非定常な多腕バンディッ

要因によって変化することから，問題設定について 2 種ト問題を解決する提案手法について述べる．4 章では提案

類の拡張が図られている．線形な多腕バンディット問題で手法の評価を行い，5 章でまとめる．

は，文脈によって腕から得られる報酬の確率分布が決定される [5]．ここで文脈とは，例えば利用者の性別，年代，行動カテゴリといった複数の要因のパラメータの組み合わせ

2. 関連研究2.1 多腕バンディット問題

によって表現される状態のことを指す．非定常な多腕バン

多腕バンディット問題は，腕と呼ばれる複数の候補からディット問題では，例えば記事の目新しさと利用者の反応得られる報酬を最大化する問題である．プレイヤーは各試の大きさの関係のように，腕から得られる報酬の確率分布

行で 1 つの腕を選択し，その腕から報酬を得る．各腕はあが時間経過によって変化する [6]．

る確率分布に従い報酬を生成するが，プレイヤーはこの確

利用者の嗜好が多様かつ継続的に変化する環境におい率分布を試行の結果から推測しなければならない．そのたて，推薦システムが利用者の要求に応えるためには，できめ，プレイヤーはある時点の腕ごとの評価に基づき，最もるだけ多くの文脈と報酬分布の変化を考慮できることが望評価の高い腕を用いながらも，真に評価の高い腕の探索をましい．そのため，線形かつ非定常な問題設定とその解法

並行して行う．この問題に対する解法では，ある時点で最が求められる．非定常な解法では，変化検出の手法を組みも評価の高い腕を用いることを活用，各腕の評価を行うこ合わせ，報酬の変化を観察することで報酬分布の変化に追とを探索と呼び，これらの活用と探索，報酬による評価の従する．一方で，線形な問題設定では，要因の数に対する見直しを繰り返し行うことで，短期的には探索による機会

文脈の指数的な増加に伴い試行回数が文脈ごとに分散する損失を，長期的には腕の固定化による機会損失を低減する．

ことから，各文脈で報酬を観測できる回数が急激に低下す

同問題の最も単純な解法に ϵ-Greedy アルゴリズム [7] がる．そのため，従来の方式では，報酬分布の変化を検出すある．この解法では，腕の評価に報酬の標本平均を用いる．

るために一定期間の報酬の履歴の蓄積が求められることか探索の割合を ϵ ∈ [0, 1] で指定し，活用時はその時点で最ら，変化の検出と追従が遅れてしまう. よって，線形かつも評価の高い腕を，探索時にはその他の評価の低い腕を均非定常な解法には，文脈や要因の数によらずに報酬分布の等に選択する．UCB1 アルゴリズム [8] は，腕の選択に報変化を検出可能な指標が必要となる．加えて，変化の検出

酬の標本平均の値に，選択回数が少ないほど値が大きくなと追従のために文脈ごとの報酬に関する履歴を利用するこる項を加えたスコアを用いる．Thompson Sampling[9] は，とから，履歴データのサイズの肥大化も課題となる．

各腕の期待値が最大である確率に従い腕を選定する．この

本研究では，変化検出と要約データ構造を用いた，多くの文脈と報酬分布の変化を考慮可能な，線形かつ非定常な解法では，各腕の期待値をベイズ推定によって求め，この分布からの乱数の値が最も大きかった腕を選定する．

多腕バンディット問題の解法を提案する．提案手法では，多様な文脈における報酬分布の変化を迅速にとらえるため，

2.2 線形な多腕バンディット問題

文脈ごとの報酬からではなく，要因の組み合わせ数によら上述の問題設定では，文脈は常に一つであり，報酬の確ない固定数の値の推移から報酬分布の変化を検出する．こ率分布が変わらないという仮定を置いていた．線形な多腕のために，まず各腕に対する試行回数と報酬から要因のパバンディット問題は，複数の要因パラメータからなる文脈ⓒ 2020 Information Processing Society of Japan2

インターネットと運用技術シンポジウム 2020

IOTS2020
2020/12/3

Internet and Operation Technology Symposium 2020に応じて報酬分布が決定される問題である．この問題でと報酬に割引の概念が導入され，過去の観測された値は継は，各腕は線形パラメータと呼ばれる要因のパラメータに続的に更新され，新しく観測された報酬が重視される．

対する係数をベクトルとして持つ．文脈に応じた腕の報酬

二つ目は，腕の報酬分布の変化を契機に，腕を再評価す

は，この線形パラメータと要因パラメータとの内積の結果るものである．このアプローチでは，多腕バンディット問に誤差を加えた値として求める．

題の解法とは別に，変化検出の手法を利用するため，既存

文脈の種類が少ない場合には，単一の文脈を仮定した解の解法を非定常な環境に適用できる．このアプローチでは，

法を文脈ごとに適用することでも対応できるが，要因のパ

UCB1 アルゴリズムの一種である UCB1-Tuned[8] に変化

ラメータが増えるに従い，その組み合わせ結果である文脈検出の手法である Page-Hinkley test 法を組み合わせた手法の種類が指数的に増えてしまう．この場合，各文脈での試が提案されている [14]．S-TS-ADWIN[15] は，Thompson

行回数は急激に低下し，腕の評価が充分に行えない．同問

Sampling に変化検出の手法である ADWIN[16] を組み合題の解法では，腕ごとの線形パラメータを推定しながら，わせた手法である．ADWIN は直近からウィンドウと呼ば活用と探索のトレードオフを解決する必要がある．

れる期間の値を記録する．記録時にウィンドウを過去のサ同問題の解法には，UCB1 アルゴリズムを拡張した Lin-

ブウィンドウ W0 と現在のサブウィンドウ W1 に分割し，UCB[5] が提案されている．この解法では，t 回目の試行に

この平均の差が ϵcut 以上であれば，その時点で変化があっ

おける各腕 a のスコア，

たとみなし，サブウィンドウ W0 を取り除く．ここで，
√
2
2
2
2
ϵcut =· σ 2 · ln ′ +
ln ,
(2)
m W
δ
3m δ ′

LinU CBa (t) = b(t)T θ̂a (t) + α√

b(t)T Ba−1 b(t)(1)

が最も大きくなる腕を選択する．ここで b は d 次元の要δと定義される．また，δ ′ = |W
| ，m は | W0 | と | W1 | に因パラメータ，θ̂a は腕 a に対して推定した線形パラメータ

対する調和平均である．なお，δ ∈ (0, 1) はこの統計的仮説である．θ̂a = Ba−1 fa であり，腕 a における各要因のパラ

検定の信頼度である．S-TS-ADWIN では，各腕の報酬のメータの累積の試行回数を記録する Ba ∈ Rと各要因

推移を ADWIN を用いて記録する．いずれかの腕の報酬にのパラメータの累積の報酬 fa ∈ R から推定する．なお，

対する変化を検出した場合，全ての腕を通して最も近い時

ハイパーパラメータ α(α ≥ 0) が小さいほど腕の探索より

点以降に観測された試行回数と報酬を ADWIN より求め，も活用が重視される．また，Thompson Sampling を同様

これを用いて各腕の評価を更新する．

d×ddに拡張した Linear Thompson Sampling[10] も提案されている．腕の報酬分布が正規分布に従う場合，この解法では

2.4 線形かつ非定常な多腕バンディット問題µ̂ を平均，v 2 Ba−1 を分散とする多変量正規分布から µ̃ を

上述の基本的または非定常な問題に対する解法は，単一求め，要因パラメータである b(t) との内積が最も大きくなの文脈を前提としている．これらの解法を複数の文脈を持る腕を選定する．なお，µ̂ = Ba−1 fa であり LinUCB と同
2 2

つ環境に適用するには，2.2 節で述べたように指数的に増様に推定される．ハイパーパラメータも同様に v (v ≥ 0)が小さいほど腕の探索よりも活用が重視される．

加する文脈への対策を講じなければならない．
そのため，複数の文脈を前提とする線形な解法を非定常な問題に対応させる方式が提案されている．Decay Lin-2.3 非定常な多腕バンディット問題

UCB[17] は線形かつ非定常な問題に対する解法である．

ここまでの問題設定は，腕ごとの報酬分布が文脈によっ

LinUCB に割引の概念を導入し，式 1 における Ba と fa にて定まり，同じ文脈であれば変わらないという仮定を置い

減衰パラメータ γ ∈ (0, 1) を乗じた結果を腕の評価に利用ていた．非定常な多腕バンディット問題は，同じ文脈におする．このアプローチでは，試行結果を常に定数倍する操いても報酬分布が時間経過によって変化する問題である．

作のみで線形な解法に追従性を付与できるため，導入が容報酬分布の変化が周期的な場合，この周期を線形パラメー

易である．しかしながら，この減衰操作により試行回数はタに含め要因パラメータで指定することで適切に扱える．

γ i の数列に対する無限級数として 1/(1 − γ) に収束する．

一方で，変化が不規則である場合にはこの限りではない．

線形な解法ではこれを総数として，要因パラメータの次元同問題の解法では，腕の報酬分布が変化した際に，不利なごとに試行回数を分配する．結果として，要因パラメータ

腕を使い続ける機会損失を抑えるため，過去に観測した報ごとの試行回数は小さく，かつ一定数から増加せず，探索

酬に捉われずに腕の評価を迅速に更新する必要がある．

が継続してしまう．そのため，安定した運用のためには γ

同問題の解法には，大きく二つのアプローチが見られる．

を大きくする必要があり，追従性を高めることができない．

一つ目は，腕の報酬分布の変化を前提に，継続的に腕の評価

我々は，非定常な問題設定へのもう一つのアプローチでを更新するものである．UCB1 アルゴリズムや Thompson

ある変化検出と線形な解法との組み合わせを検討した．こSampling をこの問題に適用した提案 [11][12][13] がなされのアプローチでは，問題の解法とは別に，変化検出の手法ている．これらの手法では，各腕の評価に用いる試行回数を利用するため，既存の線形な解法を非定常な環境に適用ⓒ 2020 Information Processing Society of Japan3

インターネットと運用技術シンポジウム 2020

IOTS2020
2020/12/3

Internet and Operation Technology Symposium 2020

できる．しかしながら，線形な問題設定では，要因の数にのとなる．よって，異常度 a(x′ ) は L2 正規化前の任意の対する文脈の指数的な増加に伴い，各文脈で報酬を観測でベクトル x′ の平均ベクトル µ̂ とのコサイン類似度を 1 か

きる回数が急激に低下する．そのため，文脈ごとに報酬のら除したものに等しい．ただし，方向データの異常度のみ変化を観測する従来の方式では，報酬の履歴の蓄積が遅では，方向が同じで大きさのみが変化する場合に変化を検れ，変化への追従性に課題が残る．また，変化検出のため出できない．多腕バンディット問題の解法では，ある腕のには，観測対象となる値を一定期間保持する必要がある．

線形パラメータの値が増減し，他の腕に対する有効性が変

加えて，変化検出後に腕の評価を更新するため，試行回数化した際に，腕の選定基準を改める必要がある．そこで，と報酬についても同様に保持しなければならない．特に，提案手法では，線形パラメータをベクトルと見なしたとき線形な解法では，腕の評価に各要因パラメータの試行回数の大きさである L2 ノルムの値の変化も考慮することで該と報酬が必要となる．すなわち，複数の要因パラメータか当する状況での検出漏れを防ぐ．

らなる線形な問題では，要因のパラメータ数が増えるに従提案手法では，この方向データの異常度と大きさの推移

い，変化検出と追従に必要な履歴データの次元数も増え，に対して，ADWIN の統計的仮説検定による変化検出を行

データサイズが肥大化してしまう課題がある．

う．ADWIN では，変化検出の閾値の根拠として，確率の分布によらない確率の近似的な評価である確率不等式を用

3. 提案手法

いており，提案手法の入力値である方向データの異常度と本研究では，推薦システムの利用者の嗜好傾向のよう

大きさの変化を同一の方式で検出が可能かつ，異なる値でな，多様な文脈があり，文脈に対応する報酬分布が時間経の評価も容易である．また，サブウィンドウ間での比較を過によって変化する環境に対して有効な，線形かつ非定常行うため，学習の工程が不要である．これらの実用性の観な多腕バンディット問題の解法を提案する．そのために，

点から多腕バンディットのシステム実装を想定した提案手

非定常な問題設定において，腕の評価を継続的に更新する法との親和性が高いと考え採用した．

アプローチに対しても最高水準の評価を得た [15]，変化検提案手法における，推定した線形パラメータに対する出アプローチである S-TS-ADWIN の線形な解法への適用

変化検出のアルゴリズムを Algorithm1 に示す．我々は本を図る．提案手法では，文脈ごとの報酬からではなく，文方式を ADWIN-V と名付けた．また，実装は OSS として脈を横断して推定する，腕の線形パラメータの値から腕の公開済みである*1 ．ADWIN-V では，入力となるベクトル

報酬分布の変化を検出する．これにより，文脈の増加に伴データから，方向データの異常度と大きさを求め，これら

う文脈ごとの報酬の観測回数の低下の影響を避け，多様なにスケーリング定数 s を乗じた値を個々の ADWIN へ記

文脈における報酬分布の変化を迅速にとらえることができ録する．なお，スケーリング定数 s は ADWIN が入力値のる．また，変化検出に，線形パラメータの値をベクトルと大きさに応じて変化検出の精度が異なる挙動に対する調整

みなしその方向データの異常度と大きさのみを用いること

パラメータである．個々の ADWIN で変化が検出された場

で，線形パラメータごとに変化を検出する場合と比べて変合，ADWIN は変化前の系列データを削除する．これらは化検出に必要な履歴データの数を減らすことができる．加Algorithm1 の 4 行目から 10 行目に相当する．なお，方向

えて，過去期間の値を要約するデータ構造を導入すること

データの異常度の算出に必要な，平均ベクトルはこれまで

で，報酬分布の変化検出と追従に必要な複数の履歴データの入力ベクトルの平均から求める．ただし，変化前の系列のサイズの肥大化を抑制する．なお，提案手法は既存の解データの削除に伴う平均ベクトルの再計算は行わず，直近法に対し，変化検出と要約データ構造による拡張を施すたの入力値を平均ベクトルとして利用する．これは，変化検め，既存の線形な解法を利用できる．

出に必要な複数の履歴データの数を減らすよう，平均ベク
トルは履歴を持たず逐次計算で求めるためである．これら

3.1 文脈数によらない指標を用いた変化検出

は Algorithm1 の 11，13 行目に相当する．

提案手法では，文脈ごとの報酬ではなく，その報酬から推定される d 次元の線形パラメータの値を用いて腕の報酬

3.2 データ構造による履歴データサイズの低減

分布の変化を検出する．検出の指標には，方向データの異提案手法では，3.1 節の方式によって腕の報酬分布の変常検知に用いられる異常度 [18] を採用する．ここで方向化を検出した後，該当する腕における変化前の試行の結果

データとは，L2 正規化されたベクトルデータを指す．こを取り除くことで環境の変化に追従させる．ここで試行のの方向データの分布にフォンミーゼス・フィッシャー分布

結果とは，任意の時点での要因パラメータと報酬額を指を仮定したとき，任意の方向ベクトル x′ の平均ベクトル

す．2.2 節で述べたように線形な解法では，t 時点までの試′′µ̂ に対する異常度 a(x ) は 1 − µ̂ x で表される．ここで，T行の結果の累積値から線形パラメータを推定できる．しかµ̂ はフォンミーゼス・フィッシャー分布の平均方向の最尤推定値であり，方向データの標本平均を L2 正規化したもⓒ 2020 Information Processing Society of Japan*1

https://github.com/monochromegane/adwin-v

4

インターネットと運用技術シンポジウム 2020

IOTS2020
2020/12/3

Internet and Operation Technology Symposium 2020

Algorithm 1 ADWIN-V

らない．この場合，各バケットで期間の長さを扱う値が重Require: ADWIN conﬁdence value δm , δa . And scaling value
parameter sm ,sa .
1: Am ← instance of ADWIN for vector magnitude with δm
2: Aa ← instance of ADWIN for vector angle with with δa
3: for all t = 1, 2, ..., do
4:
Add sm · ||xt ||2 to Am
5:
if Am detects change then6:
Am shrinks window.
7:
end if8:
Add sa · 1 − (mTt−1 xt /(||mt−1 ||2 · ||xt ||2 )) to Aa
9:
if Aa detects change then10:
Aa shrinks window.
11:
mt = xt
12:
else
13:
mt = (t · mt−1 + xt )/(t + 1)
14:
end if
15: end for

複し，結果としてデータサイズが増加してしまう．そこで，多次元の値を保持するための指数ヒストグラムとして，各バケットで単一の値ではなくベクトルを用いるデータ構造

ExpHist-V を考案，OSS として公開した*2 ．提案するデータ構造では，各バケットは期間の長さと，ベクトルデータに対する期間中の合算値からなる．なお，期間中の値の合算
はバケットごとのベクトル同士の和によって行われる．このデータ構造により，d′ 次元のデータ保持に必要なバケッ
トあたりのデータサイズが 2d′ から d′ + 1 へと縮小する．

3.3 既存の線形な多腕バンディット問題の解法の拡張
上述した ADWIN2-V と ExpHist-V を用いて，従来の線形な解法の環境変化への追従性を高める提案手法を説明する．提案手法である Adaptive-Linear-MAB のアルゴリ

し，この累積値から変化前の試行の結果を取り除くためにズムを Algorithm2 に示す．はじめに，累積試行回数，累は，各時点での試行結果の値を履歴として保持する必要が積報酬を記録する B ，f ，腕の報酬分布の変化を検出するある．また，変化検出のために，各時点における方向デーため推定した線形パラメータを記録する ADWIN2-V であタの異常度と大きさも同様に保持する必要がある．

る A，変化前の試行の結果を記録する ExpHist-V である

これらの変化検出と追従に必要な複数の履歴データのサ

E (B) ，E (f ) を腕ごとに用意する．次に t 時点の試行におイズを小さく抑えるためには，履歴の期間の長さに対していて，任意の従来の線形な解法 P を用いて，腕 a(t) を選定

小さいデータサイズで保存できることが望ましい．そこでし，報酬 rt を得る．提案手法では，この解法 P として，従提案手法では，過去期間の値を要約するデータ構造である

来の線形な解法に加え，これらに減衰操作を加える Decay

指数ヒストグラム [19] を利用する．このデータ構造は，時LinUCB も利用できる．これは Algorithm2 の 7 行目に当点ごとの入力値を保存するが，古い値についてはある期間たる．次にこの試行の結果を受け，選定した腕に関する累で合算した値で保持する．この合算する期間を指数的に大積試行回数 Bi ，累積報酬 fi を更新する．合わせて，推定きくすることで，データ構造のサイズを小さく保つ．このした線形パラメータ Bi−1 fi を ADWIN2-V の Ai へ，試行

データ構造では，この合算された期間のデータをバケットの結果を ExpHist-V である E (B) ，E (f ) へ記録する．これと呼び，各バケットは期間の長さと期間中の合算値との 2は Algorithm2 の 11 から 14 行目にあたる．ADWIN2-V につの値で表現される．

よって腕の報酬分布の変化が検出された場合，変化前の期提案手法で利用する ADWIN では変化検出の履歴データ

間データとして指数ヒストグラムの最も古いバケットが取に，この指数ヒストグラムを用いる ADWIN2[16] も提案

り除かれる．このとき E (B) ，E (f ) の最も古いバケットかされており，S-TS-ADWIN でも利用されている [15]．そら，この削除された期間と同期間の試行の結果を求め，選定

こで，3.1 節で提案した ADWIN-V における，方向デーした腕に関する累積試行回数 Bi ，累積報酬 fi から除する

タの異常度と大きさを記録する ADWIN インスタンスをことで変化前の試行の結果を取り除く．これは Algorithm2

ADWIN2 に差し替えることで変化検出に必要な履歴デーの 15 から 19 行目にあたる．なお，ADWIN2-V と同期さ

タのサイズを抑えることができる．以降，ADWIN2 を用せるため E (B) ，E (f ) の最も古いバケットも取り除く．

Decay LinUCB のような試行の結果の減衰を伴う解法

いる報酬分布の変化検出を ADWIN2-V と呼ぶ．
提案手法では，追従に必要な試行結果の値に関する複の場合，累積試行回数，累積報酬を減衰する．減衰操作は数の履歴データも指数ヒストグラムを用いて記録する．

Algorithm2 の 9 行目にあるように，累積試行回数 B ，累線形な解法では，任意の時点での d 次元の要因パラメー

積報酬 f に γ を乗じる．変化前の試行の結果である E (B) ，

タ b の直積 B = bb ，ならびに要因パラメータに報酬 r

E (f ) では各バケットの合算値に対して γ を乗じる．なお，を乗じた f = rb が試行結果にあたる．ここで，B は d

減衰を伴わない解法では γ = 1 を用いる．

T

個の元を持つ集合から 2 個の重複あり組み合わせとして(d + 1)!/2!/(d − 1)! 次元，f は d 次元のベクトルデータと4. 評価
本章では，提案する，推定した線形パラメータに対する

みなせる．ただし，従来の指数ヒストグラムは単一の値を記録することを想定しており，ベクトルデータの記録のためには各次元に対してこのデータ構造を用意しなければなⓒ 2020 Information Processing Society of Japan*2https://github.com/monochromegane/exponentialhistograms

5

インターネットと運用技術シンポジウム 2020

IOTS2020
2020/12/3

Internet and Operation Technology Symposium 2020

Algorithm 2 Adaptive-Linear-MAB

よう，500 時点目に θ1 = [20, 24, 28, 32, 2, 4, 6, 8] に変更す

Require: Set of arms [K], Linear MAB Policy P .
1: Set Bi = Id ,∀i ∈ [K]2: Set fi = 0d ,∀i ∈ [K]3: Ai ← instance of ADWIN2-V with δm , δa , sm , sa , ∀i ∈ [K](B)
4: Ei ← instance of ExpHist-V for Bi , ∀i ∈ [K](f )5: Ei ← instance of ExpHist-V for fi , ∀i ∈ [K]
6: for all t = 1, 2, ..., do
7:Play arm a(t) = P (B, f , b(t)), and observe reward rt .
8:
for all i = 1, 2, ..., K do
(B)
(f )
(B)
(f )
9:
Decay Bi , fi , Ei , Ei = γBi , γfi , γEi , γEi
10:if i = a(t) then11:
Update Bi = Bi + b(t)b(t)T
12:
Update fi = fi + rt b
13:
Add Bi−1 fi to Ai
(B)
(f )
14:
Add b(t)b(t)T , rb(t) to Ei , Ei
15:
if Ai detects change then16:
Ai drops oldest bucket.
(old)
(old)
(B)
(f )
17:
Get Bi, fifrom Ei , Ei .
(old)
(old)
18:
Update Bi = Bi − Bi,fi − fi19:
end if20:
end if21:
end for
22: end forる．また，これらの値は解法によって腕の選定回数が偏ることで，腕ごとの線形パラメータを正しく推定するまでの期間に差が出ることを防ぐため，線形パラメータの変更前
後で腕 a0 と a1 の選定割合がほぼ同等となるよう設定した．
要因パラメータ b は，各次元が 0 と 1 の離散値から成り，各次元の値は 1 となる確率 p = 0.5 のベルヌーイ分布に従い得られることとする．t 時点の試行で選択した腕 i から得られる報酬は θiT bt + ϵt となる．ここで誤差項 ϵt は平均 0，
分散 σ 2 = 2 の正規分布に従う乱数を用いた．なお，乱数を用いた確率の計算結果を平均化するために上述のシミュ
レーションを 500 回行い，この平均を結果として用いた．
本評価では，この線形かつ非定常な問題に対し 3.3 節で提案した提案手法を従来の線形な解法に適用したものを利用する．また，比較のため，提案手法を適用しない従来の解法も評価する．従来の解法には，線形な解法である LinUCB
ならびに，Linear Thompson Sampling(以下，LTS) を用いる．また，線形かつ非定常な解法である Decay LinUCB，ならびに同様の減衰操作を LTS に施した Decay LTS も評価する．以降，これらの 4 つの解法に対して提案手法を適

方向データの異常度と大きさを用いた変化検出によって，用した解法には Adaptive の接頭辞を付けて区別する．

線形かつ非定常な問題設定での追従性が高まることを確認

各解法のハイパーパラメータには，探索の重視，減衰の度する．確認は，従来の線形な解法と，これに提案手法を適合い，変化検出の感度に関するものがある．これらの効果が用し追従性を高めた解法を比較して行う．また，提案手法

大きいとき，線形パラメータに変化がなくとも累積リグレッ

で採用したデータ構造により，これを採用しない場合と比トが継続的に増加し，評価期間の長さで結果が異なる場合がべ，報酬分布の変化検出・追従に必要な履歴データのサイ見られた．これを加味し，各解法のハイパーパラメータはズの肥大化が抑えられることを確認する．

線形パラメータの変化を伴わない予備実験によって求めた．
予備実験では，線形パラメータの推定に対して，不要な探索4.1 評価環境を避けつつ一定の追従性を持つものを選定した．この基準

提案手法による，線形かつ非定常な問題に対する性能をとして 500 時点と 2000 時点の累積リグレットの増加率を採評価するため，シミュレーションを行った．シミュレー

用し，複数の候補値のうち，この値が最も小さいものを選定

ションでは時間あたりの購入数が多い商品を選定する推する．なお，試行履歴の減衰や変化検出の効果を明確にす

薦システムを想定した．ここで，文脈によって購入数がるため，基礎となる解法と共通するハイパーパラメータの値異なる状況を表現するため，購入数を性別，年代，行動には同じものを設定した．探索に関するハイパーパラメー

カテゴリのような要因に対する線形パラメータから算出

タの予備実験では 5, 10, 20, 30, 40, 50, 75, 100, 150, 200, 250

する．また，線形パラメータをある時点で変化させるこのうち，LTS で v 2 = 150，LinUCB で α = 20 を選定した．

とで非定常な環境を再現する．このような状況には，例

減衰に関するハイパーパラメータは，上記の探索に関する

えば，特定の年代に向けたメディアへの露出による突発値のもとで 0.95, 0.99, 0.999 から選定した．Decay LTS と的な購買傾向の変化などが考えられる．シミュレーショ

Decay LinUCB でともに γ = 0.999 であった．変化検出に

ンでは，数百程度の文脈を想定し，次元数 d = 8 の線形

関するハイパーパラメータは，上記の探索に関する値のもパラメータを持つ腕 ai ∈ {a0 , a1 } に対し提案手法を含むとで 0.1, 0.01, 0.001, 0.0001 から選定した．Adaptive LTS，

複数の解法を用いて 2,000 時点までの累積報酬と累積リグ

Adaptive LinUCB でともに δm = 0.0001，δa = 0.0001 でレットを計測した．ここで累積リグレットは試行時の文あった．スケーリング定数 s は異常度 a と大きさ m が同脈において候補の腕のうち最大の期待値と選択した腕の程度の範囲となるよう sm = 0.1，sa = 1.0 を用いた．減衰

期待値の差を期間までに合計したものである．腕の線形と変化検出をともに行う Adaptive Decay LTS，Adaptive

パラメータはそれぞれ，θ0 = [14, 15, 16, 17, 18, 19, 20, 4]，

Decay LinUCB では，これまでに選定した減衰と変化検出

θ1 = [12, 13, 14, 15, 16, 17, 18, 20] とするが，非定常な環境の値を利用する．なお，予備実験のシミュレーション回数とするため，腕同士の要因ごとの係数の多寡を入れ替えるは 100 回である．

ⓒ 2020 Information Processing Society of Japan6

インターネットと運用技術シンポジウム 2020

IOTS2020
2020/12/3

Internet and Operation Technology Symposium 2020
表 1

累積報酬と累積リグレット

Table 1 Cumulative reward and regret.
解法

累積報酬

累積リグレット

LTS

133624.88

2420.73

Adaptive LTS

134014.42

2030.73

Decay LTS

134001.87

2043.92

Adaptive Decay LTS

134253.28

1792.76

LinUCB

134256.95

1788.08

Adaptive LinUCB

134644.75

1401.28

Decay LinUCB

134639.68

1406.06

Adaptive Decay LinUCB

134847.37

1198.89

4.2 評価結果
シミュレーション結果を表 1 に示す．提案手法の適用によって，全ての解法において，適用前と比較して累積報酬

図 1

試行回数と累積リグレットのシミュレーション間比較

Fig. 1 Comparation of cumulative regrets.

が増加，累積リグレットが低下していることが見て取れる．
ここで，非定常な変化への追従性を比較するため図 1 に示

メータの推定にどの程度直近までの試行結果を利用したかす累積リグレットの推移を確認する．点線が従来の解法，を表す．図の 1 段目と 2 段目で確認できた値の収束後に同色の実線が提案手法を適用したものである．減衰や変化

再度ウィンドウサイズが増加し，非定常な変化後の値が線検出を用いない LTS や LinUCB の場合には，500 時点での形パラメータの推定に利用されていることがわかる．図の線形パラメータの変化に対して 2000 時点においても累積リ

4 段目は提案手法における報酬分布の変化検出と追従に必グレットが増加していることから，非定常な環境において要な履歴データの要素数の推移を示している．点線が指数

は過去の観測結果が悪影響を及ぼすことがわかる．Decay

ヒストグラムを用いない場合の要素数，同色の実線は，用LTS と Decay LinUCB では，過去の観測結果の減衰によりいた場合の要素数である．指数ヒストグラムを用いること

累積リグレットの増加は抑えられたが，十分に減衰されるで，履歴の期間数に対して必要なデータ数を大幅に削減でまでは累積リグレットの増加が見られた．これらの 4 つのきるため，履歴データの全体の要素数を抑え，データサイ解法と比較して，提案手法では，推定した線形パラメータズの肥大化を抑制できた．一方で，変化検出時に履歴の期に対する変化検出が有効に働き，累積リグレットの収束ま間が短くなった時に要素数の差が見られなくなった．全腕での期間が短縮している．なお，LinUCB と比較して LTS

を通して変化検出の頻度が多いような環境においては平均の累積リグレットが全体として高いのは，LinUCB では推ウィンドウ数を事前に計測した上で ExpHist-V の導入を定した線形パラメータと試行回数から決定的に腕が選定さ検討する必要があると考えられる．

れるが，LTS では推定した線形パラメータから確率的に腕が選定され，常に探索される可能性があるためである．

5. まとめ本研究では，利用者の嗜好が多様かつ継続的に変化する

4.3 考察環境において，推薦システムが利用者の要求に応えるた

非定常な変化があった腕 a1 における各解法の振る舞い

め，多腕バンディット問題を線形かつ非定常な問題設定にを図 2 に示す．なお，図 2 では各解法の挙動の特性を明確拡張し，その解法を提案した．提案手法では，従来の線形にするため，500 回のシミュレーションの平均ではなく，基な解法に変化検出の手法を組み合わせ変化への追従性を高準となる LTS と LinUCB で最も累積リグレットの低かっめた．また，変化を観測する報酬の系列数が指数的に増加たシミュレーションの回の結果を示している．図の 1 段目

する課題を解決するため，推定した線形パラメータの値かと 2 段目はそれぞれ推定した線形パラメータの大きさと異ら方向データの異常度と大きさを求めることで，要因の組

常度の推移である．黒色の点線が真の線形パラメータから

み合わせ数によらない変化検出を行った．加えて，過去期算出した値の推移を示している．500 時点の線形パラメー間の値を要約するデータ構造を導入し，報酬分布の変化検タの変化後に，従来の解法では推定値が緩やかに真の値に出と追従に必要な履歴データのサイズを低減した．

近づき，提案手法では急激に収束した．これは，提案手法

評価では，提案手法の適用により従来の解法と比較して，が，ADWIN-V によるウィンドウサイズの縮小によって直線形パラメータの変化に素早く追従し，累積報酬の増加と近の観測結果のみを利用できた効果である．図の 3 段目

累積リグレットの減少が確認された．一方で，履歴の期間

は提案手法における履歴の期間数の推移であり，線形パラが短い場合，提案するデータ構造がデータサイズの低減にⓒ 2020 Information Processing Society of Japan7

インターネットと運用技術シンポジウム 2020

IOTS2020
2020/12/3

Internet and Operation Technology Symposium 2020

[4]

[5]

[6]

[7]
[8]

[9]

[10]

[11]

[12]

[13]

[14]

図 2 腕 a1 における推定した線形パラメータとデータサイズのシ[15]

ミュレーション間比較

Fig. 2 Comparation of estimated linear parameters, data sizeof arm a1 .

[16]

寄与できない課題も示された．今後は，更なるデータ表現の改善の検討と実システムでの有効性の評価を進めていく．
[17]

参考文献
[1]

[2]

[3]

経済産業省 商務情報政策局情報経済課. 平成 30 年度我が国におけるデータ駆動型社会に係る基盤整備（電子商取引に関する市場調査）, 2019.
Michael N Katehakis and Arthur F Veinott Jr. The
multi-armed bandit problem: decomposition and computation. Mathematics of Operations Research, Vol. 12,
No. 2, pp. 262–268, 1987.
Deepak Agarwal, Bee-Chung Chen, and Pradheep
Elango. Spatio-temporal models for estimating clickthrough rate. In Proceedings of the 18th international
conference on World wide web, pp. 21–30, 2009.

ⓒ 2020 Information Processing Society of Japan

[18]

[19]

三宅悠介, 松本亮介. Synapse: 利用者の文脈に応じて継続的に推薦手法の選択を最適化する推薦システム. 研究報
告インターネットと運用技術 (IOT), Vol. 2019-IOT-45,
pp. 1–7, 2019.
Lihong Li, Wei Chu, John Langford, and Robert E
Schapire. A contextual-bandit approach to personalized
news article recommendation. In Proceedings of the 19th
international conference on World wide web, pp. 661–
670, 2010.
Deepak Agarwal, Bee-Chung Chen, and Pradheep
Elango. Explore/exploit schemes for web content optimization. In 2009 Ninth IEEE International Conferenceon Data Mining, pp. 1–10. IEEE, 2009.
Richard S Sutton and Andrew G Barto. Reinforcement
learning: An introduction. MIT press, 2018.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.
Finite-time analysis of the multiarmed bandit problem.
Machine Learning, Vol. 47, No. 2-3, pp. 235–256, 2002.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, Vol. 25, No. 3/4, pp.
285–294, 1933.
Shipra Agrawal and Navin Goyal. Thompson samplingfor contextual bandits with linear payoﬀs. In International Conference on Machine Learning, pp. 127–135,
2013.
Aurélien Garivier and Eric Moulines.
On upperconﬁdence bound policies for switching bandit problems.
In International Conference on Algorithmic Learning
Theory, pp. 174–188. Springer, 2011.
Neha Gupta, Ole-Christoﬀer Granmo, and Ashok
Agrawala. Thompson sampling for dynamic multi-armed
bandits. In 2011 10th International Conference on Machine Learning and Applications and Workshops, Vol. 1,
pp. 484–489. IEEE, 2011.
Vishnu Raj and Sheetal Kalyani.
Taming nonstationary bandits: A bayesian approach. arXiv preprint
arXiv:1707.09727, 2017.
Cédric Hartland, Sylvain Gelly, Nicolas Baskiotis,
Olivier Teytaud, and Michele Sebag. Multi-armed bandit, dynamic environments and meta-bandits, 2006. In
NIPS-2006 workshop, Online trading between exploration and exploitation, Whistler, Canada, 2006.
Edouard Fouché, Junpei Komiyama, and KlemensBöhm. Scaling multi-armed bandit algorithms. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp.
1449–1459, 2019.
Albert Bifet and Ricard Gavalda. Learning from timechanging data with adaptive windowing. In Proceedings of the 2007 SIAM international conference on data
mining, pp. 443–448. SIAM, 2007.
Muhammad Ammar Hassan. Non-Stationary Contextual Multi-Armed Bandit with Application in Online
Recommendations. PhD thesis, University of Virginia,
2015.
Tsuyoshi Idé and Hisashi Kashima. Eigenspace-based
anomaly detection in computer systems. In Proceedingsof the tenth ACM SIGKDD international conferenceon Knowledge discovery and data mining, pp. 440–449,
2004.
Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev
Motwani. Maintaining stream statistics over sliding windows. SIAM journal on computing, Vol. 31, No. 6, pp.
1794–1813, 2002.

8