技術要約：Impatient Bandits: 遅延を伴わない長期的な最適化

1. 問題設定

本論文は、大規模なレコメンダーシステムにおける極めて重要な課題、すなわち長期的なユーザー満足度（例：60日間にわたる継続的なエンゲージメント）の最適化と、それに伴う深刻な報酬の遅延の緩和の両立に取り組んでいる。標準的なマルチアームドバンディット（MAB）の設定では、アルゴリズムは即時のフィードバックを前提としている。しかし、Spotifyのような現実世界のプラットフォームでは、真の報酬（長期的なエンゲージメント）は、かなりの遅延（例：$d_{max} = 60$日）を経て初めて観測可能となる。

完全な報酬が顕在化するまで待機してポリシーを更新する方法では、新しいコンテンツを効果的に評価できない「コールドスタート」問題が発生する。また、学習率も極めて低くなってしまう。一方で、短期的なプロキシ（例：直後のクリック）を最適化することは、長期的な目標と乖離してしまうことが多い。

著者らはこれを、**進行的なフィードバックを伴うバンディット問題（Bandit problem with Progressive Feedback）**として定式化している。標準的な遅延フィードバックでは、遅延期間が終了するまで情報は得られないが、進行的なフィードバックでは、長期的結果は一連の相関のある中間的なアウトカム（例：日次のリスニング活動）を通じて、時間の経過とともに徐々に予測可能になると仮定する。核心となる課題は、中間信号が完璧な代理指標であるという仮定に頼ることなく、最終的な長期報酬が観測される前に、これらの中間信号を活用して効果的に学習することである。

2. 手法

2.1 モデル：進行的なフィードバックを伴うバンディット

著者らは以下の設定を定義する：

• アクション（Actions）： 各タイムステップ $t$ において、アイテムの有限集合 $\mathcal{A}$ がユーザーのバッチ $U_t$ に推奨される。
• アウトカム（Outcomes）： ユーザー $u$ に対してアイテム $a$ を選択すると、ベクトル形式のアウトカム $Y_u = (Y_u^{(1)}, \dots, Y_u^{(J)})$ が生成される。これは、$J$ 日間にわたって段階的に明らかになるエンゲージメント指標を表す。
• 報酬（Reward）： 真の報酬 $R(Y_u)$ は、完全な軌跡の既知の関数である（例：60日間の総エンゲージメント）。
• 仮定：
  • 交換可能性（Exchangeability）： 同じアイテムを受け取ったユーザーは、アイテムの特徴量に基づいた条件付きで、潜在的なアウトカムが交換可能である。
  • ガウス過程（Gaussian Process）： 潜在的なアウトカムは多変量ガウス分布に従う。潜在パラメータ $\theta_a$ はアイテムの真の品質を表し、観測されたアウトカムは $\theta_a$ のノイズを含む実現値である。
  • 線形報酬（Linear Reward）： 報酬関数 $R(\cdot)$ はアフィンであり、これにより期待報酬がガウス分布に従うことを保証する。

2.2 アルゴリズム：Impatient Thompson Sampling

提案手法は、Thompson Samplingと**(経験的)ベイズフィルタ**を統合したものである。

1. 事前分布の学習： 過去のデータを用いて、システムはアイテムの特徴量 $z$ に条件付けられた潜在的なアイテム品質パラメータ $\theta_a$（具体的には平均 $\mu_{1,z}$ と共分散 $\Sigma_{1,z}$）の事前分布を適合させる。これは、タイプII最尤推定（経験的ベイズ）を通じて行われる。
2. 事後分布の更新： 中間アウトカム $Y_u^{(j)}$ が明らかになるにつれ、アルゴリズムはガウスフィルタを用いて $\theta_a$ の事後分布を更新する。これにより、最終的な報酬が観測されていない時点でも、アイテムの長期的な価値に関する確率的な確信を維持することができる。
3. 意思決定： 各ステップにおいて、アルゴリズムは各アイテムの現在の事後分布から候補となる $\theta'_a$ をサンプリングし、期待報酬 $R(\theta'_a)$ を最大化するアイテムを選択する。

理論的分析のために、「低分散（Lower Variance）」版のアルゴリズムも導入されている。これは、正確なバッチサイズを確保するためにサンプリング確率を丸めるものであるが、実証実験では標準版と同等の性能を示すことが示されている。

2.3 理論的枠組み：進行的フィードバックの価値（VoPF）

本論文では、中間信号の有用性を定量化するために、情報理論的な指標である**進行的フィードバックの価値（Value of Progressive Feedback: VoPF）**を導入している。

• 定義： VoPFは、遅延したアウトカムを条件とした、真の長期報酬と進行的な（検閲された）アウトカムとの間の条件付き相互情報量である。
• 意義： これは、中間信号を観測することによって、長期的な報酬に関する不確実性がどの程度解消されるかを測定するものである。
• リグレット境界（Regret Bound）： 著者らは、$\exp(-\text{VoPF})$ に比例するアルゴリズムのリグレット境界を導出している。
  • もし VoPF がゼロである場合（中間信号が情報を与えない場合）、この境界は標準的な遅延報酬のリグレット境界へと回帰する。
  • もし VoPF が高い場合（信号が非常に予測的である場合）、リグレットは大幅に減少し、実質的に遅延が短い場合と同様の学習を可能にする。

3. 主な貢献

1. 進行的フィードバックの定式化： 本論文は、「進行的なフィードバック」（漸進的に明らかになる予測的な信号）を、標準的な「遅延フィードメント」や「完璧な代理指標」から明確に区別している。レコメンダーシステムの文脈において、この現象に対する厳密なモデルを提供している。
2. 新規アルゴリズム： 相関があり、段階的に明らかになるアウトカムを扱うために、Thompson Samplingとガウスフィルタリングを組み合わせたImpatient Banditアルゴリズムを提案している。
3. 理論的保証： VoPFメトリックによって制御される新しいリグレット境界を確立し、中間信号が情報的であれば、長期報酬が完全に観測される前の早い段階のバッチにおいても、アルゴリズムが低いリグレットを達成できることを証明した。
4. 実証的検証：
   • 合成実験： アルゴリズムの性能が、信号の情報の豊かさ（informativeness）の変化に応じて、理論的な予測と定性的に一致することを実証した。
   • 半合成実験： Spotifyのポッドキャストデータを用い、提案アルゴリズムが（遅延のみ、または短期プロキシを用いる）ベースラインと比較して、累積リグレットにおいて大幅に優れた性能を示すことを示した。特にコールドスタートのシナリオにおいて顕著であった。
   • A/Bテスト： 数億人のユーザーが利用するSpotify上での大規模な展開を実施した。

4. 結果

4.1 合成および半合成実験

• リグレットの削減： 合成環境において、Impatient Banditアルゴリズムは、中間フィードバックを無視する標準的なThompson Samplingアルゴリズムと比較して、累積リグレットを大幅に減少させた。この改善はVoPFと直接相関していた。
• コールドスタート： Spotifyのポッドキャストデータを用いた半合成実験では、提案アルゴリズムは、遅延報酬ベースラインと比較して、最初の60日間（遅延期間）における累積リグレットを大幅に低く抑えた。
• 事前分布の重要性： 過去のデータから学習された事前分布を使用することが極めて重要であることを実験で示した。情報を持たない事前分布を用いた場合、性能は遅延報酬ベースラインと同程度であった。
• 非定常性： 利用可能なアイテムセットが頻繁に変化する設定（継続的なコンテンツリリースをシミュレート）において、進行的フィードバックアルゴリズムは低いリグレットを維持したが、遅延アルゴリズムは迅速に適応できず失敗した。

4.2 A/Bテストの結果（Spotify）

本手法は、Spotifyモバイルアプリの「あなたへのおすすめ（Shows you might like）」シェルフにおけるポッドキャスト推奨のランキングに対してテストされた。

• 処置群 vs 対照群： 処置群のポリシーは、進行的フィードバックを用いて新しい番組の「粘着性（stickiness）」（長期的なエンゲージメント）を推定した。一方、対照群のポリシーは、遅延報酬（データを待つために60日間待機）に依存した。
• 新着コンテンツへの影響： 最近リリースされた番組について、処置群は対照群と比較して、発見率（discovery rate）をほぼ30%向上させ、60日間のインプレッションあたりのアクティブ日数を50%以上改善させた。
• 全体的な影響： 全ての番組を通じて、処置群は60日間のアクティブ日数を7%増加させ、インプレッションあたりの60分間の再生時間を10%以上増加させた。
• トレードオフ： これらの長期的な利点は、短期的な発見率（直後のクリック数）のわずかな、かつ統計的に有意な減少を伴っていた。これは、アルゴリズムが短期的なプロキシから長期的な価値へと、見事に焦点をシフトさせたことを裏付けている。
• デプロイメント： これらの結果に基づき、本手法は数億人のユーザーに対するパーソナライズされたポッドキャスト推奨を強化するためにロールアウトされた。

5. 重要性と主張

本論文の主な貢献は、レコメンダーシステムにおける「学習速度」と「長期的な整合性」の間のトレードオフを解決することにある。進行的フィードバックを定式化することで、中間信号が予測的である限り、長期的な報酬の全期間を待つことなく、長期的な目標を最適化できることを著者らは示している。

著者らは、以下の点において、自身のアプローチが既存の代理アウトカム（surrogate outcome）の文献とは異なることを強調している：

1. 中間アウトカムが完璧な代理指標であるという仮定を置いていない。
2. 単一のバイナリアウトカムではなく、多数の連続的かつ逐次的に明らかになる中間信号（例：50以上のデイリーメトリクス）を扱っている。
3. ベイズフィルタリングを通じて、時間の経過に伴う不確実性の減少を明示的にモデル化している。

本研究は、進行的フィードバックを活用することが、特に歴史的な長期データが存在しない新しいコンテンツのコールドスタート問題を解決する上で、大規模な産業システムにおいて実質的な改善をもたらすことを検証している。著者らは、アルゴリズムの成功は、過去のデータから正確な事前分布を学習できる能力に依存しており、これは経験的ベイズ適合によって対処している実用的な要件であると述べている。