情報処理学会研究報告
IPSJ SIG Technical Report

非定常な多腕バンディット問題における変化検出アプローチの線形モデルへの拡張
三宅 悠介1,a)

栗林 健太郎1,b)

概要：多腕バンディット問題は，腕と呼ばれる複数の候補から得られる報酬を最大化する問題である．同問題の Web サービスにおける広告配信や推薦システムへの応用では，腕となる利用者の嗜好傾向が多様か
つ継続的に変化する課題に対処するため，利用者の文脈を考慮した問題設定への拡張と解法が提案されている．時間の経過に従い報酬分布が変化する非定常な問題設定の解法では，変化検出の手法を組み合わせ，報酬の変化を観察することで変化に追従する．しかしながら，腕の文脈を複数の要因のパラメータの組み合わせで表現し，文脈に応じて報酬分布が決定する線形な問題設定にこの解法を適用する場合，要因の数に対して指数的に増加する全ての報酬の変化を観察しなければならない．本報告では，要因の組み合わせ数によらない単一の値の推移のみから報酬分布の変化を検出・追従することで，従来の線形な解法を利用可能でありながら，汎用的でメモリ効率に優れた非定常かつ線形な多腕バンディット問題の解法を提案する．提案手法では，各腕に対する試行回数と報酬から要因のパラメータに対する試行時点での係数を推定し，この値の和の推移から報酬分布の変化を検出する．また，報酬分布の変化に合わせた動的なハイパー
パラメータ調整により迅速に変化に追従する．評価では，非定常かつ線形な多腕バンディット問題を設定し，変化検出を行わない場合と比較して性能が上回ることを確認した．

Extension of Change Detection Method for
Non-Stationary Linear Multi Armed Bandit
Abstract: A multi-armed bandit problem is a problem that maximizes reward from making choices between
candidates called arms. For the application of advertisement or recommendation system of this problem,the contextual extension of problem setting and policy is proposed to deal with variously and continuously
changing user preferences. For non-stationary problems, policies of making choices follow changes by observing reward change using change detection methods. On the other hand, for a linear problem that changes
reward distribution according to factors, the decision-maker of the policies must observe all reward changes
that increase exponentially. In this report, we propose a non-stationary linear multi-armed bandit policy
to detect a change of reward distribution from a single value transition that is independent of the numberof reward changes. The proposed policy estimates coeﬃcients of the factors from the number of trials andrewards and detects a change of reward distribution from the sum of the estimated values. Also, the policy
can follow change rapidly using dynamic hyper-parameter turning. We set up a non-stationary and linear
multi-armed bandit problem for the evaluation and conﬁrmed our policy makes the performance increase.

1. はじめにるため，多くの EC サイトには推薦システムが導入されている．推薦システムは，EC サイトが取り扱う多くの商品

消費者向け電子商取引（以下 EC）の市場規模拡大 [1] にの中から，何らかの方策に基づき利用者が興味を持つ商品伴い，取り扱う商品種類は増大している．EC サイト利用を提案することで，閲覧や購入行為を支援するシステムで者の通常の行動では全ての商品を見て回ることは困難であある．多様な利用者が訪問する EC サイトにおいては，全ての利用者に対する画一的な提案は必ずしも有用ではない

1

a)
b)

GMO ペパボ株式会社 ペパボ研究所
Pepabo R&D Institute, GMO Pepabo, Inc., Tenjin, Chuo
ku, Fukuoka 810-0001 Japan
miyakey@pepabo.com
antipop@pepabo.com

c 2020 Information Processing Society of Japan⃝

ことから，多くの推薦システムでは提案の個別化を図っている．
このような個別化した提案では，利用者ごとに有用な提1

情報処理学会研究報告
IPSJ SIG Technical Report

案を予め知ることは難しい．そこで，推薦システムは利用分布の系列数に比例して推薦システムのメモリ使用量が増者の嗜好を蓄積し，その時点で有用と考えられる情報を活加してしまう．また，利用者の文脈に応じて推薦システム

用した提案を行う一方で，より有用な提案につながる情報が適応的に振る舞うためには，報酬分布の変化を迅速に検の探索が求められる．この活用と探索のトレードオフの最出し，文脈と報酬分布の新しい関係性を速やかに学習する

適な解を求める問題は，多腕バンディット問題として知ら必要がある．加えて，多腕バンディット問題には理論保証れている [2]．この問題は，ある確率分布に従い報酬を生成があり実績のある既存の解法が多数存在するため，これらする腕と呼ばれる複数の候補から得られる報酬を最大化すの解法を非定常かつ線形な多腕バンディット問題に適用でる問題であり，同問題に対する解法が推薦システムやインきることが望ましい．

ターネット広告の分野で利用されている [3][4]．一方で，基

本報告では，要因の組み合わせ数によらない単一の値の本的な多腕バンディット問題では，報酬の確率分布が常に推移のみから報酬分布の変化を検出・追従することで，従同じであるという仮定が置かれている．推薦システムにお来の線形な解法を利用可能でありながら，汎用的でメモリ

いて腕となる，利用者の商品に対する嗜好傾向は様々な要効率に優れた非定常かつ線形な多腕バンディット問題の解因によって変化することから，問題設定について 2 種類の法を提案する．提案手法では，各腕に対する試行回数と報拡張が図られている．線形な多腕バンディット問題では，

酬から，それぞれの要因のパラメータに対する試行時点で事前に定めた要因の組み合わせによって腕から得られる報の係数を推定する．次に，この求めた値の和の推移のみか

酬の確率分布が決定される [5]．この問題の解法では，要因

ら報酬分布の変化検出を行う．最後に，線形な解法に対しごとの報酬に対する重みを活用と探索によって求める．非て変化以前の観測値を取り除くことで，新しい報酬分布に定常な多腕バンディット問題では，腕から得られる報酬の追従させる．また，記録された観測値の数の減少に合わせ確率分布が時間経過によって変化する [6]．この問題の解て探索が重視されるよう動的にハイパーパラメータを調整

法では，確率分布の変化を踏まえ，変化後の報酬を重視しする．評価では，非定常かつ線形な多腕バンディット問題て変化に追従する．

を設定し，変化検出を行わない場合と比較して性能が上回

この拡張された 2 つの問題設定は，多腕バンディット問ることを確認した．

題における文脈の考慮と捉えることができる．ここで，文本論文の構成を述べる．2 章で多腕バンディット問題の脈とは，複数の要因のパラメータによって定まる状態のこ関連研究を紹介し，推薦システムでの応用における課題にとを指す．基本的な多腕バンディット問題では，要因のパついて述べる．3 章では，非定常かつ線形な多腕バンディッ

ラメータを用いず，結果として常に一つの文脈に決定されト問題を解決する提案手法について述べる．4 章では提案

る．すなわち腕の報酬分布は一定である．線形な多腕バン手法の評価を行い，5 章でまとめる．

ディット問題では，いくつかの要因のパラメータから文脈が定まる．そして，文脈に対応して腕の報酬分布が決定す
る．要因のパラメータの組み合わせにより，表現できる文

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

脈は指数的に増加する．非定常な多腕バンディット問題で多腕バンディット問題は，腕と呼ばれる複数の候補からは，なんらかの理由により，時間の経過によって文脈に対得られる報酬を最大化する問題である．プレイヤーは 1 回応する報酬分布が変化していく．この意味で，線形な多腕の試行で 1 つの腕を選択し，選択した腕から報酬を得る．

バンディット問題は，文脈に対応する腕の報酬分布が時間それぞれの腕はある確率分布に従い報酬を生成するが，プの経過により変化しない問題設定と言い換えることができレイヤーはこの確率分布を試行の結果から推測しなければる．従来の解法ではいずれかの問題設定を扱うが，利用者ならない．そのため，プレイヤーはある時点の腕ごとの評の嗜好が多様かつ継続的に変化する環境において，推薦シ価に基づき，最も評価の高い腕を用いながらも，真に評価

ステムが利用者の要求に応えるためには，できるだけ多くの高い腕の探索を並行して行う．この問題に対する解法での文脈と報酬分布の変化を考慮できることが望ましい．

は，ある時点で最も評価の高い腕を用いることを活用，各文脈が複数の要因のパラメータによって決定され，時間腕の評価を行うことを探索と呼び，これらの活用と探索，

経過によっても報酬分布が変化する環境に対して，多腕バ

報酬による評価の見直しを繰り返し行うことで，短期的にンディット問題を適用するためには，従来の線形な解法とは探索による機会損失を，長期的には腕の固定化による機非定常な解法を組み合わせる必要がある．しかしながら，会損失を低減する．

線形な多腕バンディット問題においては，要因のパラメー同問題の最も単純な解法として ϵ-Greedy アルゴリズ

タの組み合わせごとに文脈が異なるため，要因の数に対し

ム [7] が挙げられる．この解法では，腕の評価に報酬の標て報酬分布のパターンが指数的に増加する．非定常な多腕

本平均を用いる．探索を行う割合は 0 ≤ ϵ ≤ 1 で指定され，バンディット問題では，報酬分布の変化を観測するため，

活用時はその時点で最も評価の高い腕を，探索時にはその線形な多腕バンディット問題を扱う場合に，観測する報酬

他の評価の低い腕を均等に選択する．この解法では，候補c 2020 Information Processing Society of Japan⃝2

情報処理学会研究報告
IPSJ SIG Technical Reportの評価の差が明らかな場合に探索による機会損失が発生す

タ α(α ≥ 0) が小さいほど腕の探索よりも活用が重視される．また，腕の評価において探索された回数を考慮しない

る．また，Thompson Sampling を同様に拡張した Linear

ことから特に探索初期において誤った腕の活用が起こる可Thompson Sampling[10] も提案されている．腕の報酬分布能性がある．UCB1 アルゴリズム [8] は，選択回数の少なが正規分布に従う場合，この解法では µ̂ を平均，v 2 B −1

い腕を積極的に選択することでこの問題に対応する．このを分散とする多変量正規分布から µ̃ を求め，コンテキスト

解法では腕の選択に，報酬の標本平均の値に，選択回数が情報である bi (t) との内積が最も大きくなる腕を選定する．

少ないほど値が大きくなる項を加えたスコアを用いる．こµ̂ = B −1 f であり，各要因のパラメータの累積の試行回

れにより，初期は積極的に探索し，充分な試行を経た後は，数を記録する B と各要因のパラメータの累積の報酬 f か

評価が高い腕が活用され，誤った判断や探索による機会損

ら推定される．なお，LinUCB と同様にハイパーパラメー

失を抑えることができる．UCB1 アルゴリズムでは，あるタ v 2 (v 2 ≥ 0) が小さいほど腕の探索よりも活用が重視さ時点までの報酬から選択する腕が一意に定まる．しかしなれる．

がら，報酬が遅れて反映される環境においては選定する腕が固定され，報酬がそれに対して反映されない期間に不利

2.3 非定常な多腕バンディット問題

な腕を使い続ける可能性がある．Thompson Sampling[9]ここまでの問題設定は，腕ごとの報酬分布が文脈によっは，各腕が期待値最大である確率に従い腕を選定する．こて定まり，同じ文脈であれば変わらないという仮定を置の解法では，各腕の期待値をベイズ推定によって求め，こいていた．非定常な多腕バンディット問題は，同じ文脈にの分布からの乱数が最も大きかった腕を選定する．腕の選

おいても報酬分布が時間経過によって変化する多腕バン

定が確率的に行われることから，報酬が遅れて反映される

ディット問題である．報酬分布の変化が周期的な場合，こ環境に起因する機会損失を低減することができる．

の周期を線形パラメータに含めコンテキスト情報で指定することで適切に扱うことができる．一方で，変化が不規則

2.2 線形な多腕バンディット問題である場合にはこの限りではない．同問題の解法では，腕上述の問題設定では，文脈は常に一つであり，報酬の確の報酬分布が変化した際に，不利な腕を使い続ける機会損

率分布が変わらないという仮定を置いていた．線形な多腕失を抑えるため，過去に観測した報酬に捉われずに腕の評

バンディット問題は，複数の文脈があり，文脈に応じて報価を迅速に更新する必要がある．

酬分布が決定される多腕バンディット問題である．この問

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

題では，各腕はそれぞれの要因のパラメータに対する係数

る．一つ目は，腕の報酬分布の変化を前提に，継続的に腕をベクトルとして持つ．文脈に応じた腕の報酬は，要因のの評価を更新するものである．Discounted UCB と Sliding

パラメータの値ベクトルとの内積の結果に誤差を加えた値

Window UCB は，UCB1 アルゴリズムをこの問題に適用として求める．本稿では，腕が持つ各要因に対する係数ベした提案である [11]．Discounted UCB では，各腕の評価

クトルを線形パラメータ，腕の選択時の要因のパラメータに用いる試行回数と報酬に割引の概念が導入され，過去の値ベクトルをコンテキスト情報と呼ぶ．

の観測された値は継続的に更新され，新しく観測された

文脈の種類が少ない場合には，基本的な多腕バンディッ

報酬が重視される．Sliding Window UCB では，これにト問題の解法を文脈ごとに適用することでも対応できるが，加え，評価に利用する報酬系列に対してウィンドウを設

要因のパラメータが増えるに従い，その組み合わせ結果でけ，ある時点以降の報酬のみを評価に利用する．Dynamic

ある文脈の種類が指数的に増えてしまう．この場合，各文

Thompson Sampling は，Thompson Sampling をこの問題

脈での試行回数は急激に低下し，腕の評価が充分に行えなに適用した提案である [12]．指数平滑法を用いて，直近 C

い．同問題の解法では，腕ごとの線形パラメータを推定し回までの結果を指数的に減衰しながら腕の評価に利用すながら，活用と探索のトレードオフを解決する必要がある．

る．Discounted TS[13] は，Discounted UCB と同様に試同問題の解法には，UCB1 アルゴリズムを拡張した Lin-

UCB[5] が提案されている．この解法では，t 回目の試行における各腕 a のスコア，

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

行回数と報酬に割引の概念を導入した．
二つ目は，腕の報酬分布の変化を契機に，腕を再評価するものである．このアプローチでは，多腕バンディッ√

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

ト問題の解法とは別に，変化検出の手法を利用することため，既存の解法を非定常な環境に適用することができが最も大きくなる腕を選択する．ここで b はコンテキス

る．このアプローチでは，UCB1 アルゴリズムの一種であト情報，θ̂a は腕 a に対して推定した線形パラメータである UCB1-Tuned[8] に変化検出の手法である Page-Hinkley

る．θ̂ = Ba−1 fa であり，腕 a における各要因のパラメー

test 法を組み合わせた手法が提案されている [14]．この手

タの累積の試行回数を記録する Ba と各要因のパラメータ法では，変化検出後に，腕の評価を初期状態に戻したものの累積の報酬 fa から推定する．なお，ハイパーパラメーと戻さないものを一定期間比較し，変化検出の誤りに備え

c 2020 Information Processing Society of Japan⃝3

情報処理学会研究報告
IPSJ SIG Technical Report

るメタ・バンディットを採用した．S-TS-ADWIN[15] は，メータを動的に調整するアニーリング手法を導入する．こThompson Sampling に変化検出の手法である ADWIN[16]れによって，変化時の探索と，変化がない時の活用を積極を組み合わせた手法である．ADWIN はウィンドウ W に的に行い変化への迅速な追従を実現する．

t 時点の値 xt を記録する．記録時には，ウィンドウを過去

ここで，提案手法の位置付けを整理するため，多腕バンのサブウィンドウ W0 と現在のサブウィンドウ W1 に分割

ディット問題設定と解法の適用領域の関係を表 1 に示す．

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

1 列目は多腕バンディット問題設定が仮定する報酬の確率あったとみなし，サブウィンドウ W0 を取り除く．ここで，
√
2
2
2
2
ϵcut =· σ 2 · ln ′ +
ln ,
(2)
m W
δ
3m δ ′

分布である．2 列目の解法では基本的な多腕バンディット′問題である報酬分布が変化しない環境を扱う．3 列目の線形な解法ではこれに加え，要因のパラメータによって文脈

δ= |W| ，m は | W0 | と | W1 | にが定まり，文脈に対応する報酬分布が決定する環境を扱う

対する調和平均である．なお，δ ∈ (0, 1) はこの統計的仮説

が時間の経過による報酬分布の変化は扱わない．これと対検定の信頼度である．S-TS-ADWIN では，各腕の報酬の照的に，4 列目の非定常な解法では時間の経過による報酬推移を ADWIN を用いて記録する．いずれかの腕の報酬に分布の変化のみを扱っている．提案手法となる 5 列目の解

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

法では，複数の要因のパラメータによる文脈の決定と文脈

点以降に観測された試行回数と報酬を ADWIN より求め，に対応する報酬分布の変化が同時に起こる，非定常かつ線

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

形な多腕バンディット問題への適用を実現する．

と定義される．また，δただし，これらの非定常な多腕バンディット問題に対する解法は，単一の文脈を前提としている．これらの解法を
複数の文脈を持つ環境に適用するには，基本的な多腕バン

3.1 推定した線形パラメータによる変化検出と探索ハイ
パーパラメータの動的な調整

ディット問題を線形に拡張するのと同様に，指数的に増加提案手法のアルゴリズムを Algorithm1 に示す．d 次元する文脈への対策を講じなければならない．また，これらのコンテキスト情報を持つ腕 i それぞれに，Bi ，fi ，Ai がの解法は活用と探索のトレードオフの解消を従来の解法の設定される．ここで Bi は次元数をコンテキスト情報の次

枠組みに従っている．すなわち，報酬分布の変化に伴い腕元数 d と同じにする単位行列，fi は d 次元のベクトルであの試行回数が変更され，Thompson Sampling では腕の選る．Bi はその腕 i におけるコンテキスト情報の各次元が定時の分散が，UCB1 では補正項が増加することで探索が試行された累積回数を，fi はコンテキスト情報の各次元で重視される．しかしながら，腕の報酬分布の変化が頻繁に得た累積報酬が記録される．また，Ai は腕 i に対して推定発生する環境では，変化時の積極的な探索と，変化がない

した線形パラメータの和の推移を ADWIN をデータ構造に時の試行結果の蓄積が重要であり，変化への迅速な追従に用いて記録する．なお，B ，f ，A は，全ての腕の対応す

改善の余地が残ると考えられる．

る行列，ベクトルを保持する配列である．

3. 提案手法

提案手法は，既存の線形な多腕バンディット問題の解法
によって選定された腕 i とその報酬 r を得た後に呼ばれる

本報告では，推薦システムの利用者の嗜好傾向のよう一連の処理として定義される．はじめに，腕の報酬分布のな，複数の文脈があり，文脈に対応する報酬分布が時間経変化検出のため，線形パラメータの推定を行う．このため過によっても変化する環境に対して適用可能な，非定常かに，選定した腕についてコンテキスト情報 b と報酬 r から，つ線形な多腕バンディット問題の解法を提案する．そのた

試行回数 Bi と累積報酬 fi を更新する．そして，Bi−1 fi

めに，非定常な多腕バンディット問題において，腕の評価によって得られた d 次元のベクトルを線形パラメータの推を継続的に更新するアプローチに対しても最高水準の評価定値として扱う [5][12]．提案手法では，この推定値の各次を得た [15]，変化検出アプローチである S-TS-ADWIN の元の和 M の推移を用いて腕の報酬分布の変化を検出する．

線形な問題設定への拡張を図る．提案手法では，腕の報酬

これは Algorithm1 の 4 行目に該当する．推定した線形パ分布の変化を文脈ごとの報酬からではなく，推定した線形

ラメータの和を用いることで，文脈の種類によらない単一パラメータの値の和から検出する．これにより，要因のパの時系列による省メモリな変化検出を実現する．次に，こラメータの数やその組み合わせである文脈の数によらず単の値の推移に対して ADWIN の統計的仮説検定による変化

一の値の推移から変化の検出が可能となる．また，多腕バ検出を行う．変化を検出した場合，ADWIN は変化前の系

ンディット問題の解法とは別に，変化検出の手法を利用す列データを削除する．提案手法では，変化後の系列データ

ることで，既存の線形な多腕バンディット問題の解法を非長 | Ai | を腕 i の新しい試行回数とみなし，その期間に記

定常な環境へ適用することができる．加えて，腕の報酬分録されたコンテキスト情報と報酬から試行回数 Bi と累積布の変化に従い，既存の線形な多腕バンディット問題の解

報酬 fi を更新する．

法における探索と活用のバランスを調整するハイパーパラ

c 2020 Information Processing Society of Japan
⃝提案手法では，腕の報酬分布の変化を検出した際，腕の4情報処理学会研究報告
IPSJ SIG Technical Report
表 1 多腕バンディット問題の問題設定と解法

Table 1 Problem settings and policies of multi-armed bandit problem.
Discounted UCB[11]Sliding Window UCB[11]報酬の確率分布ϵ-Greedy[7]LinUCB[5]Dynamic-

UCB1[8]Linear-Thompson Sampling[12]Thompson Sampling[9]Thompson Sampling[10]Discounted TS[13]Adapt-EvE[14]LTSADWIN-Anneal
LinUCBADWIN-Anneal

S-TS-ADWIN[15]
✓

一定

✓

✓

✓

文脈により決定✓✓✓

時間経過で変化✓

試行回数が一旦減少する点に着目し，腕の試行回数に従っ

Algorithm 2 LTS-ADWIN-Anneal

た，探索と活用のバランスを調整するハイパーパラメータ

Require: Set of arms [K], d-dimentional context
1: ADWIN conﬁdence value δ
2: Anneal parameter β
3: Set Bi = Id ∀i ∈ [K]4: Set fi = 0d ∀i ∈ [K]5: Ai ← instance of ADWIN with δ, ∀i ∈ [K]
6: for all t = 1, 2, ..., do
7:
for all i = 1, 2, ..., K do
8:
Sample µ̃i (t) from distribution N (Bi−1 fi , τ Bi−1 ).
9:end for
10:
Play arm a(t) := argmaxi b(t)T µ̃i (t), and observe reward rt .
11:
UpdateA, B, f , τ=
Linear-ADWINAnneal(a(t), A, B, f , b(t), rt , β)12: end forの動的な調整を行う．これは Algorithm1 の 10 行目に該当する．この式では，腕ごとの試行回数と反する形で値 τ が増減する．既存の多腕バンディット問題の解法における，探索と活用のバランスを調整するハイパーパラメータにこの値を用いることで，腕の試行回数の増加に伴い活用を，
試行回数の減少が起きた場合に，探索が重視することが可能となる．なお，本手法におけるハイパーパラメータである β(> 0) により最終的に求まる値の大きさを調整する．

Algorithm 1 Linear ADWIN Anneal
1: function Linear-ADWIN-Anneal(i, A, B, f , b, r, β)2:Update Bi = Bi + bbT
3:
Update fi = fi + br∑
4:
M = d (Bi−1 fi )d5:
Add M into Ai
6:
if Ai detects change then7:
Ai shrinks window∑
8:
Update Bi = tt−|Ai | bbT∑t
9:Update fi = t−|Ai | br10:
end if∑|A|11:
τ = i=0 ln |Aβ |+1i12:return A, B, f , τ
13: end function

規分布から µ̃ を求め，t 回目の試行における腕 i への d 次
元のコンテキスト情報である bi (t) との線形和が最も大きくなる腕を選定する．LiUCB では腕ごとに式 1 から求めた値が最も大きくなる腕を選定する．報酬 r を得た後に，提案手法を用いて腕の線形なパラメータの推定と報酬分布の変化検出を行う．提案手法では，これらの解法で用いられていた線形なパラメータの推定方法を用いているため，推定に用いた B ，f の結果をそのまま用いることができ，提案手法との親和性が高い．また，腕の選定には提案手法により得られた動的なハイパーパラメータ値 τ を用いるこ

3.2 既存の線形な多腕バンディット問題の解法の拡張
3.1 節で提案した手法は，変化検出と動的なハイパーパ
ラメータの算出を，利用する多腕バンディット問題の解法に依存しない．そのため，既存の線形な多腕バンディッ
ト問題の解法を拡張することができる．本節では，線形とで，試行回数の増加に伴い活用，試行回数の減少が起きた場合に探索を重視することが可能となる．

4. 評価
4.1 評価環境な多腕バンディット問題の解法である，Linear Thompson

提案手法による，非定常で線形な多腕バンディット問題

Sampling，LinUCB に対して，提案手法を適用し，非定常に対する性能を評価するため，シミュレーションを行っ

かつ線形な多腕バンディット問題の解法へと拡張する．

た．シミュレーションでは，次元数 d = 8 の線形パラ拡張した解法のアルゴリズムを Algorithm2 と Algo-

メータを持つ腕 ai ∈ {a0 , a1 } に対し提案手法を含む複rithm3 に示す．d 次元のコンテキスト情報を持つ K 本の腕数の解法を用いて 2,000 時点までの累積報酬と累積リグそれぞれに，Bi ，fi ，Ai が設定される．Linear Thompson

レットを計測した．ここで累積リグレットは試行時の文脈

Sampling では B

−1

f を平均，B−1を分散とする多変量正c 2020 Information Processing Society of Japan⃝において候補の腕のうち最大の期待値と選択した腕の期

5

情報処理学会研究報告
IPSJ SIG Technical Report
表 2

Algorithm 3 LinUCB ADWIN Anneal
Require: Set of arms [K], d-dimentional context
1: ADWIN conﬁdence value δ
2: Anneal parameter β
3: Set Bi = Id ∀i ∈ [K]4: Set fi = 0d ∀i ∈ [K]5: Ai ← instance of ADWIN with δ, ∀i ∈ [K]
6: for all t = 1, 2, ..., do
7:
for all i = 1, 2, ..., K do
8:θ̂i (t) = Bi−1 fi√
9:LinU CBi (t) = b(t)T θ̂i (t) + τ b(t)T Bi−1 b(t)10:
end for
11:
Play arm a(t) := argmaxi LinU CBi (t), and observe reward rt .
12:
UpdateA, B, f , τ=
Linear-ADWINAnneal(a(t), A, B, f , b(t), rt , β)13: end for

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

Table 2 Cumulative reward and regret.
解法

累積報酬

累積リグレット

LTS

108248.94

4003.44

TS ADWIN

107526.03

4725.26

LTS ADWIN Anneal

111431.18

821.68LinUCB

108731.40

3522.99

UCB1 ADWIN

108092.71

4157.86

LinUCB ADWIN Anneal

111699.39

552.76

メータ δ には誤検知が少なくなるような値として δ = 0.001を用いた．ただし，UCB1 ADWIN と TS ADWIN について，文脈ごとに試行が分散することから同じ設定で変化検出が行われなかったため，δ = 0.5 とした．なお，予備実験のシミュレーション回数は 100 回である．

待値の差を期間までに合計したものである．腕の線形パラメータはそれぞれ，θ0 = [14, 15, 16, 17, 18, 19, 20, −10]，

4.2 評価結果

θ1 = [12, 13, 14, 15, 16, 17, 18, 10] とするが，非定常な環境

シミュレーション結果を表 2 に示す．提案手法が共に，とするため，500 時点目に θ1 の 8 次元目のみ-11 に変更す

累積報酬が増加，累積リグレットが低下していることが見る．すなわち θ1 = [12, 13, 14, 15, 16, 17, 18, −11] となる．

て取れる．シミュレーションの累積リグレットの推移を

コンテキスト情報 b は，各次元が 0 と 1 の離散値から成り，

図 1 に示す．また，ハイパーパラメータの推移を図 2 に示

各次元の値は 1 となる確率 p = 0.5 のベルヌーイ分布に従す．図 1 より，変化検出を用いない LTS や LinUCB の場い得られることとする．t 時点の試行で選択した腕 i から得合には，500 時点での線形パラメータの変化に対して 2,000られる報酬は θiT bt + ϵt となる．ここで誤差項 ϵt は平均 0，

時点においても累積リグレットが増加していることから，

2

分散 σ = 2 の正規分布に従う乱数を用いた．なお，乱数非定常な環境においては過去の観測結果が悪影響を及ぼすを用いた確率の計算結果を平均化するために上述のシミュことがわかる．一方で，変化検出を用いたとしても文脈ご

レーションを 500 回行い，この平均を結果として用いた．

とに異なる腕を用いた TS ADWIN と UCB1 ADWIN で

本評価では，この非定常で線形な多腕バンディット問題

は，文脈ごとに試行が分散することから評価の蓄積が遅に対し，3.2 節で提案した提案手法 (以下，LinUCB ADWIN

れ，リグレットの収束に時間がかかっている．これらと比Anneal，LTS ADWIN Anneal) を解法として利用する．ま較して，提案手法では，推定した線形パラメータの値の和た，比較のため，線形な多腕バンディット問題の解法であでの変化検出が有効に働き，おおよそ 575 時点において累る LinUCB ならびに，Linear Thompson Sampling(以下，積リグレットの増加が収束傾向になっている．また，図 2

LTS) を評価する．合わせて，非定常な多腕バンディット

より，提案手法によるハイパーパラメータの動的な調整に問題の解法である S-TS-ADWIN を評価するが，本評価のよって線形パラメータに変化がない期間中は探索を抑え，設定に合わせ，報酬分布に正規分布を仮定し，試行時の腕変化時に探索を重視することで不要な探索を省き，期間全の選択本数の判定処理を除いた解法（以下，TS ADWIN)

体で累積リグレットを低く抑えたことが見て取れる．なを用いる．また，同様の拡張を UCB1 に施した解法（以お，LinUCB と比較して LTS の累積リグレットが全体とし下，UCB1 ADWIN）も評価する．なお，文脈を扱えないて高いのは，LinUCB では推定した線形パラメータと試行

TS ADWIN と UCB1 ADWIN については，文脈ごとに別回数から決定的に腕が選定されるが，LTS では推定した線の腕として計測することで擬似的に文脈を考慮した．

形パラメータから確率的に腕が選定されることで常に探索

各解法のハイパーパラメータは予備実験によって求めた．

が行われる可能性があるためである．

予備実験では，5，10，20，30，40，50，75，100，150，200のうち，累積報酬が最も高く，累積リグレットが最も低く

4.3 考察なった値を利用した．各解法におけるハイパーパラメータ

それぞれの腕における各解法の振る舞いを図 3 と図 4 には LinUCB で α = 20，LTS で v 2 = 50，LinUCB ADWIN

示す．図の上段は推定した線形パラメータの和の推移であAnneal では β = 30，LTS ADWIN Anneal では β = 100る．黒色の点線が真の線形パラメータの和を示している．

となった．UCB1 ADWIN と TS ADWIN ではハイパーパ

図の下段はウィンドウサイズの推移であり，線形パラメー

ラメータが存在しない．また，ADWIN のハイパーパラ

タの推定にどの程度直近までの試行結果を利用したかを表

c 2020 Information Processing Society of Japan⃝6

情報処理学会研究報告
IPSJ SIG Technical Report

図 1

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

Fig. 1 Comparation of cumulative regrets.
図 3 腕 a0 における推定した線形パラメータとウィンドウサイズのシミュレーション間比較

Fig. 3 Comparation of estimated linear parameters, window
size of arm a0 .

推定した．これは，腕 a1 において線形パラメータの推定に必要な十分な試行が行われなかったことに起因している．
今回のシミュレーション設定では，線形パラメータの変化
後に腕 a1 はどのようなコンテキスト情報であっても腕 a0より少ない報酬となるため，各解法において選択される
回数は少なくなる．実際に，500 時点以降の試行期間を通した腕 a1 の累積選択数は LTS ADWIN Anneal で 70 回，

LinUCB ADWIN Anneal で 80 回程度であった．また，十分なウィンドウサイズを確保できなかったことも影響した
図 2

ハイパーパラメータの推移のシミュレーション間比較

Fig. 2 Comparation of hyper parameter.

と考えられる．図 4 の下段より，500 時点以降のウィンド
ウサイズが LTS ADWIN Anneal で 40，LinUCB ADWIN

Anneal で 30 程度を推移しており，腕の選択回数の約半分
す．なお，ADWIN を用いない LTS と LinUCB では過去の試行が全て反映されるためウィンドウサイズは腕の試行回数に等しい．

程度の試行結果から推定を行っていることがわかる．

5. まとめ図 3 の腕 a0 の線形パラメータの推定について，期間中

本報告では，利用者の嗜好が多様かつ継続的に変化するに線形パラメータに変化がなかった腕 a0 では各解法で真環境において，推薦システムが利用者の要求に応えるため，の値に収束した．また，提案手法でのウィンドウサイズに

多腕バンディット問題を非定常かつ線形な問題設定に拡張

ついて，腕の試行回数に対して少ないことから継続的に小し，その解法を提案した．提案手法では，変化を観測する

幅な縮小が行われていることがわかる．報酬誤差を変化と報酬の系列数が指数的に増加する課題を解決するため，推して検出していると考えられるため，報酬誤差がより大き定した線形パラメータの和を用いることで要因の組み合わ

くなる環境では，より小さい δ の値を検討する必要がある．

せ数によらない変化検出を行った．また，変化時の積極的

図 4 の腕 a1 では，500 時点の線形パラメータの変化後に，な探索と変化がない時の活用を効果的に切り替えるため，

LTS と LinUCB は緩やかな低下を示し，提案手法では急探索に関するハイパーパラメータの動的な調整手法を提案

激な低下を示した．これは，提案手法が，ADWIN によるした．

ウィンドウサイズの縮小によって直近の観測結果を利用で非定常かつ線形な多腕バンディット問題の評価において，きた効果である．しかしながら，今回のシミュレーション

この環境を想定しない従来手法と比較して，提案手法が累では提案手法は線形パラメータの真の値に対して低い値を積報酬を増やし，累積リグレットを減少させることが確認

c 2020 Information Processing Society of Japan⃝7

情報処理学会研究報告
IPSJ SIG Technical Report

[6]

[7]
[8]

[9]

[10]

[11]

[12]
図 4 腕 a1 における推定した線形パラメータとウィンドウサイズのシミュレーション間比較

Fig. 4 Comparation of estimated linear parameters, window
size of arm a1 .

[13]された．考察の結果，精度の高い線形パラメータの推定にはウィンドウサイズの調整に課題が残ることが示された．

[14]

研究報告時点では，線形パラメータの値の和が多次元の時系列データの変化検出に有効である理論的な裏付けは行えていない．多変量時系列に対する変化検出の更なる調査が必要である．また，ADWIN に記録する値を ADWIN の[15]

ウィンドウサイズに依存した値から求めていることで，変化検出に関する安定性の低下を招いている可能性もあることから，この点についても方式の改善を図っていきたい．
今後は，上述の課題の解決に加え，実システムでの有効性の評価を進めていく．

[16]

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.

参考文献
[1]

[2]

[3]

[4]

[5]

経済産業省 商務情報政策局情報経済課. 平成 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.
三宅悠介, 松本亮介. 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.

c 2020 Information Processing Society of Japan⃝

8