非定常な多腕バンディット問題において効率的に変化を察知する方式の検討
このエントリは、第8回 Web System Architecture 研究会 (WSA研)の予稿です。
非定常な多腕バンディット問題において効率的に変化を察知する方式の検討
はじめに
適応的なシステムの実現には、利用者と情報システムが互いの状態をよく理解するためのコミュニケーションと、それに応じた振る舞いの変更が必要となる。 一方で、そのコミュニケーションから得られる情報や利益の価値を考慮しなければならない環境では、確実な情報に基づく振る舞いを選択しつつ、まだ得られていない情報を引き出すために、価値の低いコミュニケーションを敢行しなければならない。
これは、多腕バンディット問題として定式化できる。 多腕バンディット問題では、振る舞いの選択肢のことを腕と呼び、ある時点までの情報をもとに有効な腕を選択することを「活用」、腕の可能性を探るために有効ではない腕を選択することを「探索」と呼ぶ。 それぞれの腕はある確率分布に従い報酬を生成する。 中でも、選択肢の相対的な有効性が時間経過とともに変化する問題設定は非定常な多腕バンディット問題と呼ばれ、いくつかの解法が提案されている。
非定常な多腕バンディット問題に対する解法には、腕の有効性の変化に応じた評価の更新が重要とされてきた。 しかしながら、選択による機会損失の低減を目的とした多腕バンディット問題の設定では、ある時点で有効性の低い選択肢が利用される機会は少なく、腕の有効性の変化を察知する、それ自体がまず難しい。
本研究では、このような非定常な多腕バンディット問題における変化を素早く察知するにあたり、探索による機会損失を抑制した、効率的な方式を検討する。 なお、多腕バンディット問題の設定は、同時に文脈付きの問題設定に拡張することができるが、課題の本質は同じであること、方式検討の容易性から、本方向では文脈の考慮は行わない。
非定常な多腕バンディット問題の解法における、変化察知の課題
非定常な多腕バンディット問題への解法では、腕の報酬分布が変化した際に、過去に観測した報酬に捉われずに腕の評価を迅速に更新しなくてはならない。 この問題の解法には大きく4つのアプローチがある。 一つ目は、腕の報酬分布が変化することを前提にして、観測時点からの経過に応じて腕の評価に重み付けをするアプローチである（減衰型）。 二つ目も、同様の前提において、新しく観測した報酬から一定の期間のみの情報で報酬分布を評価する（ウィンドウ型）。 三つ目は、腕の報酬分布の変化を契機として、腕を再評価するものである（変化検出型）。 このアプローチでは、変化検出の手法を用いて腕の報酬の変化を検出し、変化前の観測を取り除くことで、新しく観測された報酬を重視する。 これは変化検出による可変のウィンドウ型とみなすこともできる。 四つ目は、現時点の腕の評価を継続的に推定するものである。 このアプローチでは、腕の状態として状態空間モデルを仮定し、カルマンフィルタや粒子フィルタを推定に用いる。
これらの全てのアプローチは、変化後の報酬分布から得られる報酬のサンプルを一定数必要とする。 選択による機会損失の低減を目的とした多腕バンディット問題の設定では、ある時点で評価の高い腕を最も多く活用する。 そのため、評価の高い腕が、ある時点で有効性が低くなるようなケースでは、十分な報酬のサンプルを観測することができ、各アプローチは有効に働く。 反対に、評価の低かった腕が、ある時点で有効性が高くなるケースでは、その腕に対する報酬のサンプルを得るまでに時間が掛かり、機会損失の発生に繋がると考えられる。 例えば、ECサイトの推薦アルゴリズムのコールドスタートのような、一定の嗜好情報が蓄積されることでその有効性を増すような選択肢がある場合に、この問題が発生する。
この問題に直接挑んだ先行研究[1][2]では、いずれもなんらかの非定常な多腕バンディットの解法に従い腕の選択を行うが、一定の割合で、ランダムに腕を選択することで、腕の選択の偏りの解消を試みている。 また、上述のアプローチのうち、報酬の観測数の上限を変化させるような、減衰型、ウィンドウ型、変化検出型でも、間接的に腕の選択の偏りが緩和される。 なぜなら、多くの多腕バンディットの解法では、観測数の少なさを評価の不確かさと捉え、探索を促すからである。
これらの探索を増やすアプローチは、トレードオフが発生する。 すなわち、相対的な腕の評価が逆転しない期間では、その期間中の探索が機会損失につながってしまう。 そのため、評価の低い腕の有効性の変化を素早く察知できるよう探索を行いつつ、その探索に伴う機会損失を減らすことが求められる。
非定常な多腕バンディット問題の解法における、効率的な変化察知の方式の検討
本研究では、評価の低い腕に対する変化の察知について、素早さと機会損失低減の観点を両立させるため、この探索行為を多腕バンディット内の多腕バンディットとみなす。 そして、この多腕バンディット内の多腕バンディットの評価基準に、腕の不安定性と、将来性を採用することで、探索時の機会損失低減を目指す。
本報告では、先行研究の一定の割合で実施される探索行為を対象として機会損失の改善を目指す。 すなわち、腕の選定の比率が同一となるようなランダム選定ではなく、腕の不安定性と将来性を基準に、腕の選定の比率を変化させる。 提案手法では、腕の不安定性と将来性を扱うために、獲得報酬の時系列予測を行う。 時系列予測には、将来性の変化を扱えるよう少なくともトレンド成分を扱うことができ、不安定性を扱えるよう予測の幅も扱えるようなモデルが望ましい。 そこで、これらを満たすベイズ型統計モデルを採用する。 扱う報酬の形式により、カルマンフィルタや粒子フィルタを選択可能である。 探索には、各腕でn時点先の評価を予測値と信用区間に基づき腕の不安定性と将来性が高い腕を選定する。 予測値が将来性、信用区間の広さが不安定性に該当する。 なお、これらのモデルでは時系列予測の時点が進むにつれ、その信用区間が広がっていくことから、無限の将来を想定した腕の選定では、先行研究と同じ振る舞いになると考えられる。
評価
カルマンフィルタベースの提案方式のコンセプト実装し、トイ・シミュレーションで機会損失を抑えられることを評価した。
シミュレーション設定
評価環境として、腕の数が3、1000回の試行において、期間中に有効性の最も低かった腕が最も高くなるよう設定した。 なお、このシミュレーションでは、先行研究における一定数の割合の探索の試行のみを取り出したことを想定している。
評価方法
そして、以下のそれぞれの方式に対して、機会損失を抑える性能と変化を素早く察知する性能を評価した。
- random: ランダムな探索（予測できない未来を想定）ε-Greedy(ε=1.0)
- epsilon: 現在の情報に基づく探索（予測できない未来を想定）ε-Greedy(ε=0.1)
- state model: 予測に基づく探索（予測できる未来を想定）ε-Greedy(ε=0.1)だが活用時はカルマンフィルタによる100期先予測の値で選定する
なお、本報告の提案手法のコンセプト実装では、将来性のみを扱い、不安定性の考慮はできていない。
本評価では、機会損失を抑える性能を、累積リグレットの低さによって評価する。 本報告で、累積リグレットとは、各時点での最適な腕から得られる期待報酬額と方策が選定した腕から得られた報酬額の差の合計のことを指す。 また、変化を素早く察知する性能を、腕の真の有効性が切り替わった時点以降で新しい最適な腕を選択した回数が一定数を超えるまでの期間の短さによって評価する。
なお、準備期間の関係上、シミュレーションは複数回行っていないため、変動する可能性がある。
機会損失を抑える性能の評価
各方式の累積リグレットの推移を下図に示す。
均等に腕を選択するrandomではおおよそ線形にリグレットが増加する。 epsilonでは、変化前のリグレットの増加は抑えられるが、変化後には追従が遅れ、リグレットが大きく増加した。 これは、腕の選定の偏りによって探索が十分に行えないことと、過去データにひきづられて腕の評価の更新が遅れていることから発生していると考えられる。
提案のstate modelでは、シミュレーション初期にrandomと同じ程度のリグレットの増加が確認された。 これは、予測に基づく活用が精度が低かったことに起因する。 50時点以降は予測が安定することで、リグレットの増加がepsilonと同等になった。 そして、変化後であっても、リグレットの増加が抑えられていることが確認できる。 これは、予測によって、将来性がある探索すべき腕を決定し、評価の更新をいち早く行えたためである。
変化を素早く察知する性能の評価
切り替わり後の最適な腕を選択した累積回数の推移を下図に示す。
均等に腕を選定するrandomではおおよそ線形に腕が選定される。 本研究の課題設定では、この増加より大きいことが望まれる。 epsilonでは、腕の有効性の変化に追従できず、ε-Greedyの探索割合に応じた増加にとどまった。 これは、腕の選択肢が増加するほど、探索が行われない可能性が増すことも示している。 提案のstate modelでは、予測によって、将来性がある探索すべき腕を決定し、該当の腕に対する探索がrandomと比べて多く行われた。 これにより、変化の察知が素早く進むことが期待できる。
腕の有効性の変更に対する、提案方式の100時点先の予測を下図に示す。
本評価のシミュレーション設定は非常に単純なものであったため、予測がおおよそ正しかったことがわかる。
まとめ
本報告では、非定常な多腕バンディットにおける変化の察知の課題を整理し、腕の不安定性と将来性に着目した予測型の多腕バンディット方策を提案した。 将来性を考慮可能なコンセプト実装では、シミュレーションにおいて、累積リグレットを抑えた素早い変化察知の可能性が示唆された。 今後はコンセプト実装に、不安定性の考慮を組み込むこと、そのためにε-Greedyではなくトンプソンサンプリングをベースにした手法との統合を進めたい。 また、文脈を考慮した場合での実装とシミュレーションの拡張を行う。 加えて、探索割合自体を環境の変化の度合いに応じて変動させる方式も検討する。
参考文献
- [1] Fang Liu, Joohyun Lee, and Ness Shroff. 2018. A change-detection based framework for piecewise-stationary multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 32.
- [2] Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. 2019. Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 418–427.
