時間変化する報酬環境で、バンディットアルゴリズムをどうオフライン評価するか
こんにちは、サイバーエージェントAI Lab強化学習チームの暮石です。CyberAgent AILabアドベントカレンダーの21日目を担当させていただきます。
普段は、非定常な環境におけるバンディット問題について研究しています。
特に、環境が時間とともに変化する状況で、探索と活用をどのようにバランスさせるべきか、という点に関心を持って取り組んでいます。
こうしたテーマに実務で取り組んでいく中で、強く感じている難しさの一つが、非定常な環境下でのバンディットアルゴリズムのオフライン評価です。
1.はじめに
オンライン広告や推薦システムにおいて、クリエイティブやサムネイルなど複数の選択肢がある状況で、探索と活用をオンラインでバランスさせる手法として、Thompson Sampling や Upper Confidence Bound などのバンディットアルゴリズムが用いられています。
では、これらのアルゴリズムをどのように評価すればよいのでしょうか。
理想的には、実際にオンラインでアルゴリズムを動かして比較評価するのが、最も素直な方法です。
しかし現実には、
- 大規模な A/B テストのコストが高い
- 安定運用中のシステムで強い探索を行いにくい
- 過去ログを用いて事前に検討したい
といった理由から、オフライン評価が求められる場面も多くあります。
一般的に、オフラインでバンディットアルゴリズムを評価する際には、Replay Method[1]と呼ばれる方法がよく用いられます。一方で、報酬分布が時間とともに変化する非定常環境では、「いつ得られたデータか」という時間情報が本質的な意味を持ちます。このため、過去ログを用いた評価は、定常環境の場合と比べて格段に難しくなります。
本記事では、こうした背景を踏まえ、時間変化する報酬環境で、バンディットアルゴリズムをどうオフライン評価するかという点に焦点を絞って整理します。本記事の目的は、万能な評価手法を提案することではありません。
むしろ、
- 非定常環境では何が本質的に難しくなるのか
- どのような前提のもとで、どこまでなら意味のある比較ができるのかを明確にし、評価結果をどのように解釈すべきかを整理することを目的としています。
気軽に読んでいただければ幸いです。
2. バンディット問題の概要
本章では、以降の議論に必要な範囲に限定して、バンディット問題について整理します。
すでにバンディット問題に馴染みのある方は、必要に応じて読み飛ばしていただいて構いません。
2.1 バンディット問題とは何か
バンディット問題は、複数の選択肢（アーム）から1つを選び、その結果として報酬を観測するという意思決定を、繰り返し行う問題として定式化されます。
例えば、オンライン広告や推薦システムでは、
- 表示する広告クリエイティブ
- 表示するサムネイル
- 推薦するアイテム
などが「アーム」に対応し、クリックや購買などが報酬として観測されます。このとき、実務では総クリック数などを最大化させる問題を考えます。もう少し分かりやすく言うと、複数の選択肢がある中で、どれが良いか分からない状態から、総クリック数を最大化することが目的です。ただし、実際にクリック率が高いアームは分からないので、バンディット問題では探索と活用をバランスよく行うことが大事になってきます。
- 探索（exploration）：まだ十分に試していない選択肢を選び、情報を集める
- 活用（exploitation）：これまでの観測から良さそうな選択肢を選ぶ
この探索と活用を、オンラインでどのようにバランスさせるかが、バンディットアルゴリズムの中心的なテーマです。
2.2 定常環境と非定常環境
バンディット問題では、報酬分布をどう定義するかで大きく問題が変わってきます。
定常環境では、各アームの報酬分布は時間によらず一定であると仮定します。
- 同じアームを選べば、いつ選んでも同じ分布から報酬が得られる
- 時刻は単なるインデックスであり、特別な意味を持たない
理論的な解析がしやすく、多くの基礎研究はこの仮定のもとで行われています。
定常環境を仮定したバンディットアルゴリズムの代表例としては以下のようなアルゴリズムがあります。
- Thompson Sampling (TS) : 各アームの報酬分布に対する事後分布からサンプリングし、その結果に基づいて行動を選択する確率的手法
- Upper Confidence Bound (UCB) : 推定した平均報酬と不確実性を組み合わせ、上界が最大となるアームを選択する手法
バンディットアルゴリズムを実際に応用することを考えると、報酬分布（クリック率など）は時間によらず一定であることは稀です。そのため、非定常環境では、報酬分布が時間とともに変化することを仮定します。
- ユーザの嗜好の変化
- トレンドや季節性
- 外部要因による環境変化
などにより、同じアームであっても、「いつ選んだか」によって得られる報酬が異なります。
本記事で扱うのは、このような 時間変化する報酬環境 です。
特に、環境の変化は アルゴリズムの行動によって引き起こされるものではなく、外生的に起こると仮定します。すなわち、報酬分布は時間とともに変化するものの、その変化はアルゴリズムの選択には依存しないとします。
非定常環境を仮定したバンディットアルゴリズムの代表例としては以下のようなアルゴリズムがあります。
- Sliding Window UCB : 非定常環境を意識し、直近のデータのみを用いて推定を行う UCB 系手法
- Discounted UCB : 非定常環境を意識し、過去のデータに重みをかけて推定を行う UCB 系手法
3. オフライン評価の選択肢と Replay Method
前章では、バンディット問題の基本と、定常環境・非定常環境の違いについて整理しました。本章では、こうしたバンディットアルゴリズムをオフラインで評価する際に、どのような選択肢があるのかを整理し、その上で本記事の立場を明確にします。
3.1 オンラインで学習するアルゴリズムを評価する難しさ
Thompson Sampling(TS)やUpper Confidence Bound(UCB)、Sliding Window UCB[2]といったバンディットアルゴリズムは、オンラインで学習しながら行動を変えていくアルゴリズムです。そのため、これらを評価しようとすると、次のような問題に直面します。
- アルゴリズムの振る舞いは過去の観測履歴に依存する
- 同じアルゴリズムでも、観測のされ方が違えば行動の系列が変わる
- 「このアルゴリズムの期待報酬はいくらか」といった固定的な量を定義しにくい
つまり、固定された方策の価値を推定することを前提とした一般的なオフライン評価の枠組みは、そのままでは適用できません。特に、非定常環境では「いつどのような観測を得たか」が重要になるため、評価はさらに難しくなります。
3.2 オフライン評価の主な選択肢
このような設定で考えられるオフライン評価の方法は、大きく分けて次の2つです。
1つ目は、モデルベース・シミュレーションです。これは、環境のモデルを推定し、そのモデル上でアルゴリズムを実行する方法です。
具体的には、
- 各アームの報酬分布（時間変化を含む）を推定し
- その推定モデルを用いて、TS や UCB をシミュレーションする
というアプローチです。
この方法には、
- 任意の行動に対する反事実を生成できる
- 時間歪みやスキップが生じない
といった利点があります。
一方で、非定常環境では、
- 報酬分布の時間変化を正しくモデル化する必要がある
- モデルの仮定や推定誤差が評価結果を大きく左右する
という問題があり、実務データに対して適用するのは容易ではありません。
もう1つの選択肢が、Replay Method です。Replay Method では、環境のモデルを明示的に仮定する代わりに、
- 過去に観測されたログデータを固定し
- 「もしこのログ環境のもとで、あるアルゴリズムを動かしていたらどうなったか」
を再現することで評価を行います。モデル仮定が不要で、実データを使った評価をできることから実務において広く用いられている方法です。
本記事では、モデルベース・シミュレーションは扱わず、Replay Method に基づく評価を考えます。
理由は次の通りです。
- 非定常な報酬分布を正確にモデル化することは難しい
- モデルの仮定に評価結果が強く依存してしまう
- 実務ログをそのまま用いた評価を考えたい
以降の議論では、Replay Method を前提として、
- 何が評価できて
- 何が評価できず
- どのような解釈が妥当か
を順に整理していきます。
3.3 Replay Methodとは
Replay Method の基本的なアイデアは、非常にシンプルです。
- 過去に観測されたログデータを、時間順に1つずつ見ていく
- 各時刻で、評価対象のアルゴリズムがどのアームを選ぶかを計算する
- ログに記録されているアームと一致した場合のみ、その報酬を観測したものとしてアルゴリズムを更新する
一致しなかった場合は、その時刻の観測は行われず、次の時刻に進みます。
この手続きを通して、
「もしこのログ環境のもとで、そのアルゴリズムを動かしていたら」
という反事実的な実行を、可能な範囲で再現します。Replay Method はシンプルである一方、いくつかの暗黙の仮定を含んでいます。特に重要なのは次の点です。
- ログに記録されていない行動の報酬は観測できない
- アルゴリズムの行動によって、環境の時間変化は影響を受けない（外生的である）
- ログデータが、評価対象のアルゴリズムにとって十分な情報を含んでいる
これらの仮定は、後の章で議論する 評価の限界 と密接に関係しています。
4. 非定常環境で何が難しくなるのか
前章では、オフライン評価の選択肢を整理し、本記事では Replay Method に基づく評価を考える立場を明確にしました。本章では、非定常な報酬環境において Replay Method を用いると、何が本質的に難しくなるのかを整理します。結論を先に述べると、難しさの本質は 「時間が単なるインデックスではなく、情報そのものになる」 点にあります。
4.1 非定常環境では「時間」が情報になる
定常環境では、同じアームを選べば、いつ選んでも同じ分布から報酬が得られると仮定します。この場合、観測された報酬は「どのアームを選んだか」だけで意味が決まり、**「いつ観測されたか」**は本質的な情報ではありません。
一方、非定常環境では状況が異なります。
- 同じアームであっても
- 時刻によって報酬分布が変化する
ため、観測された報酬は
「どのアームを、いつ選んだか」
と不可分な形で意味を持ちます。
このため非定常環境では、過去のデータをどの時点の情報として解釈するかが、アルゴリズムの振る舞いに大きく影響します。
4.2 Replay Method によるスキップと時間歪み
Replay Method では、ログと一致した行動が選ばれたときのみ報酬が観測されます。一致しなかった場合、その時刻の観測はスキップされます。
このとき、次のような現象が起きます。
- 実際の時間は 1 ステップずつ進んでいく
- 一方で、アルゴリズムが学習するタイミングは飛び飛びになる
つまり、実時間と学習時間がズレることになります。
定常環境であれば、このズレは主に、
- 観測数が減る
- 推定の分散が大きくなる
という効果に還元できます。
しかし非定常環境では、
- どの時刻で観測が得られたか
- 重要な変化点の前後で情報が得られたか
が本質的になるため、このズレは単なる分散の問題では済みません。Replay Method によるスキップは、アルゴリズムが「どの時間帯の情報を学習できたか」を大きく制約するのです。
4.3 アルゴリズムごとに異なる影響
この時間歪みの影響は、アルゴリズムの種類によって異なります。
まず、UCB 系アルゴリズムでは、
- 各アームの平均報酬推定
- 観測回数に基づく不確実性
を組み合わせて行動を選択します。
Replay Method によるスキップは、
- 観測回数の増加を遅らせる
- 推定精度の向上を遅らせる
という影響を与えます。
定常環境では、これは主に「学習が遅くなる」という影響にとどまりますが、非定常環境では、
- 古い情報が長く残る
- 環境変化への追従が遅れる
といった形で、より深刻な影響を及ぼします。
次に、Sliding Window UCBを考えます。Sliding Window UCB は、非定常環境を意識し、直近のデータのみを用いて推定を行うアルゴリズムです。
しかし Replay Method の下では、
- 「直近の (W) ステップ」
- 「直近の (W) 回の観測」
が一致しなくなります。
その結果、
本来は「時間窓」で動作するアルゴリズムが、
Replay 下では「観測イベントの窓」で動作してしまう
というズレが生じます。これは単なる性能劣化ではなく、評価しているアルゴリズムそのものが変質してしまうことを意味します。
5. それでも何が比較できるのか
前章では、非定常環境において Replay Method を用いたオフライン評価が、時間歪みやスキップといった構造的な困難を伴うことを見てきました。このような制約を踏まえると、
「それでは、Replay Method を使って何が分かるのか」
という疑問が自然に生じます。本章では、Replay Method による評価をどのように解釈すれば意味のある比較になるのかを整理します。
5.1 同一条件下での比較という考え方
非定常環境でのReplay Method による評価は、アルゴリズムの「真の性能」や「一般的な期待報酬」を推定するものではありません。Replay Method が与えるのは、
「この特定のログ環境に条件付けたとき（同一条件で比較したとき）に、各アルゴリズムがどのように振る舞ったか」
という結果です。ここで重要なのは、「同一条件で比較したとき」という点です。Replay Method は、過去に集めたログを 一つの“固定された世界” として扱い、その世界の中で「もし別のアルゴリズムを動かしていたら」を再生します。
もう少し噛み砕くと、Replay 評価では次のものが あらかじめ固定された条件になります。
- 環境の時間変化：たとえばトレンド変化や季節性など、クリック率が上がった／下がったといった時間的な変動の“起き方”は、ログに含まれる履歴として固定されます。
- ログに含まれる行動と報酬：各時刻に実際に表示されたアーム（クリエイティブ等）と、そのとき観測された報酬（クリック等）も固定です。Replay では「ログに書かれていない別の行動を取ったときの報酬」は原理的に分かりません。
-
（結果として生じる）スキップの発生：Replay では、評価対象アルゴリズムがその時刻に選んだアームがログと一致したときだけ報酬を観測できます。一致しない時刻はスキップされます。この“観測できる／できない”という制約自体が、ログという固定世界の上で評価を行う、という条件に含まれます。
このように「ログで与えられた世界」を固定した上で、Replay が比較しているのは、固定された条件のもとで、アルゴリズムだけを入れ替えたときに、
同じログ世界（同じ時間変化・同じ観測可能性）のもとで、
どのアルゴリズムが、どのタイミングでログと一致して学習できたか
その結果、行動や学習の進み方がどのように異なったか
という点を比較しています。
です。
言い換えると、Replay Method は、
- 「一般に A は B より良い（真の期待報酬が大きい）」ではなく、
- 「同一条件下でのアルゴリズムの振る舞いを比較するための評価手法
として捉えることができます。
5.2 ログ方策の探索性の重要性
同一条件下での比較として Replay 評価を解釈する場合でも、ログデータがどのように集められたかは評価結果に大きく影響します。特に重要なのが、ログ方策の探索性（どのアームも一定確率で選ばれるか、時間帯ごとに多様なアームが試されているか）です。Replay Method では、評価対象アルゴリズムがその時刻に選んだアームがログの行動と一致したときだけ、報酬を観測して更新できます。
したがって、ログ方策が探索的でないと、次の2つの理由で評価が難しくなります。
(1) そもそも「観測できる機会」が少なくなる
ログ方策が特定のアームに偏っていると、ログにはそのアームの記録ばかりが残ります。その結果、評価対象アルゴリズムが別のアームを選びたくなったとしても、ログと一致せずスキップが増え、学習がほとんど進まない状況が起こります。このとき Replay 評価で比較されるのは、「アルゴリズムが賢いか」以前に、ログが許した範囲でどれだけ更新できたかになってしまいます。
(2) 非定常では「変化点の前後の情報」が欠けやすい
非定常環境では、「いつ観測されたか」が本質的な情報です。ところがログ方策が探索的でないと、たとえば変化点付近で
- あるアームはほとんど表示されていない
- 逆に別のアームしか表示されていない
といった“時間帯ごとの欠損”が起こりやすくなります。この場合、評価対象アルゴリズムが本来やりたい「変化を検知して切り替える」という挙動を、ログがそもそも支えられません。結果として、
アルゴリズムの適応能力の差ではなく、
ログが提供した“変化点の周辺情報”の有無が勝敗を決める
という状況になりかねません。
6. まとめ
本記事では、時間変化する報酬環境において、バンディットアルゴリズムをどのようにオフライン評価すべきかという問題について整理しました。特に、Thompson Sampling や UCB、Sliding Window UCB といった オンライン学習アルゴリズムを評価対象とし、非定常環境における Replay Method の限界と、その解釈の仕方を議論しました。非定常環境では、「いつ観測されたか」という時間情報が本質的な意味を持ちます。このため、Replay Method による評価は、真の性能や期待報酬を推定するものではなく、特定のログ環境に条件付けた相対的な振る舞いの比較として解釈する必要があります。Replay Method は万能な評価手法ではありませんが、評価の前提と限界を明確にした上で用いれば、非定常な実務ログのもとでアルゴリズム同士を比較検討するための、現実的で有用な手段となります。
本記事が、非定常環境でバンディットアルゴリズムを扱う際のオフライン評価の設計や結果解釈の一助になれば幸いです。
-
Li, Lihong, et al. "Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms." Proceedings of the fourth ACM international conference on Web search and data mining. 2011. ↩︎
-
Aurélien Garivier and Eric Moulines. 2011. On upper-confidence bound policies for switching bandit problems. In International conference on algorithmic learning theory. Springer, 174–188 ↩︎
Discussion