これは何??

推薦タスクを解くアプローチとしてbandit系の手法を軽く調べてた中で、「こういうユースケースではこういうbandit手法を使うとよさそう！」みたいなメンタルマップ的なものを示した論文 A Map of Bandits for E-commerce を読んでみたメモです!
本記事はn週連続推薦システム系論文読んだシリーズ 43 週目の記事です。
- ちなみに42週目はこちら: The Feature Store Advanced Guide 2025年ver.を読んだメモ

ざっくりどんな内容?

E-commerceサービスにおけるbanditアルゴリズムの活用のための、「こういうユースケースではこういうbandit手法を使うとよさそう！」みたいなメンタルマップ的なものを示した論文。
提案されたマップは、実務者が適切なアルゴリズムを見つけるためのいくつかの重要な意思決定ポイントで構成されてる。
- 意思決定ポイント1: そもそもbanditは適切な定式化か??
  - bandit設定なのか? full-information設定なのか? あるいは長期的な影響を考慮するRL設定なのか?
- 意思決定ポイント2: 報酬の設定はどんな感じか??
  - 報酬の次元数は? 報酬分布の仮定は? 報酬は絶対的か相対的か? 報酬の粒度は? 報酬の観察は遅延する? 報酬はbinary値か連続値か?
- 意思決定ポイント3: アクションの設定はどんな感じか??
  - アクションのタイプは? アクション空間の大きさは?

導入: 本論文のモチベーション

そもそもbanditアルゴリズムって??
- sequential decision making (逐次的意思決定) のためのフレームワーク。
  - 意思決定者(="agent")が逐次的にアクション(="arm")を選択し、報酬シグナルを観察する。(手法によっては、現在のcontextに基づきアクションを選択する)
  - agentの典型的な目標は、観察された報酬シグナルについての何らかの関数(ex. 累積報酬の期待値, etc.)を最大化できるような、最適なアクション選択方策(action-selection policy)を学習すること。
  - この問題は強化学習(RL)の特別なケースと言える。
なぜbanditアルゴリズムがたくさん研究されて文献がたくさんあるのか??
- 応用範囲が広いから! (wide applications!)
  - オンライン推薦、dynamic pricing、サプライチェーン最適化など。
  - ex. Amazon, Google, Netflix, Yahoo!などの推薦タスクにbanditアルゴリズムが使われてる。
本論文のモチベーション
- 文献が多いのは、多様なアルゴリズムがあるという点では嬉しいことだが、実務者が直面してる問題を解決するための適切なアプローチを見つけるのを難しくしてしまう...!
- 実務者がアプリケーションの特定のユースケースに対して、実用的なbandit手法を選択するための指針が必要だ!
  - マップは、実務者がバンディットの複雑な世界をナビゲートし、適切なアルゴリズムを見つけるためのいくつかの重要な意思決定ポイントで構成されてる。
- 本論文ではEコマースを実例としてるが、このマップは他のアプリケーションにも役立つ。

意思決定ポイント1: そもそもbanditは適切な定式化か??

"bandit"という用語は、選択されたアクションの報酬のみが観察されるという事実を指す。
一方で、全てのアクションの報酬が観察される場合、その設定は"full-information"と呼ばれる。アプリケーションで解決したい問題がfull-information設定の場合、banditアルゴリズムは適切ではない。
- ex. 典型的な他クラス分類。
  - インスタンスのラベルを予測することは、アクションを選択することとみなせる。
  - これはbanditではなくfull-informationの設定。なぜなら、インスタンスの正しいラベルが分かれば、全てのアクションの報酬が分かるから(=正しいアクションは1, 他は0)。
また一方で、より一般的な強化学習(RL)の設定では、次のcontext(="state")が以前のcontextや選ばれたアクションに依存して変化し得るため、agentはより複雑なアルゴリズムを使用して長期的な報酬を考慮する必要がある。
- 長期的な影響が重要な場合、banditアルゴリズムは最適な定式化ではないかもしれないが、ベースラインまたは出発点としては有用になり得る。

意思決定ポイント2: 報酬の設定はどんな感じか??

アプリケーションにおける報酬シグナルの性質は、適切なバンディットアルゴリズムを決定する上で重要な役割を果たす。
以下の図は、実際の10個の典型的な使用例に至る報酬の6つの重要な特性。

(図は論文より引用)

Dimension: 報酬の数(次元数)はスカラー?それともベクトル?
- 報酬は1次元（スカラー）または多次元（ベクトル）である可能性がある。
- 後者の場合、タスクはベクトル報酬（ノード3）を最適化するか、残りの次元に対する制約の下で1つの報酬次元を最大化するアプローチを取ることができる（ノード4）。
Distributional assumption: 報酬が従う確率分布の仮定について
- 確率的バンディットの場合は、報酬は確率分布に従うと仮定される。
  - 報酬分布が時間と共にゆっくりと変化する場合でも、新しいデータで方策を継続的に学習すれば、同様に確率的ばんディットとして扱うことができる。
- 敵対的バンディット(adversarial bandit)の場合は報酬に関する確率的な仮定をしない（ノード7）。
  - ちなみに敵対的バンディットって何それ?? = 報酬が確率的に決まるのではなく、何らかの意図やパターン、あるいは「敵対者」の行動によって決定される可能性がある状況をモデル化する手法、らしい...?
Relativity: 報酬は絶対的か相対的か?
- 報酬は通常、特定のアクションの良さを測定する。
- 一方でランキングのような一部の問題では、デュエリングバンディットのようにアクションを比較する相対的な報酬を扱うこともできる（ノード8）。
Granularity: 報酬の粒度
- アクションが組み合わせ的である場合、報酬は全体のアクションに対してであるか（ノード9）、アクションを構成するサブアクションに対するシグナルを使って構成することができます（ノード10）。
  - 後者の設定はsemi-banditsとも呼ばれる。
- (例えば推薦アイテムリストを作るタスクの場合は、まさにアクションが組み合わせ的であるケースだよな...)
Delay: 報酬がすぐに観測される? それとも遅延する?
- アプリケーションの実用的な制限により、次のアクションを選択する前に報酬を観察できない場合がある。
  - 報酬の遅延には2種類あり、制約されたもの（ノード5）と無期限のもの（ノード6）がある。これは、遅延に対して合理的に小さな上限があるかどうかによる。
Value type: 報酬はbinary値? それとも連続値?
- 報酬はバイナリ（ノード1）または数値（ノード2）になる。

また論文では、図の各リーフノード(1~10)に対して、bandit手法の例を示してた。

意思決定ポイント3: アクションの設定はどんな感じか??

アクション集合 $A$ の設定は、適切なバンディットアルゴリズムを決定する上で重要な役割を果たす。

アクションの特性1: Action type

(図は論文より引用)

3つの一般的なaction typeがある: single, slate, combinatorial
- single:
  - アクション集合はアイテムの集合。
  - このaction typeの場合は基本的に、アクション集合は小さく有限。
- slate:
  - アクション集合は、アイテムのランク付きリストからなるslate(=日本語で訳すと組みあわせ?)
  - このaction typeの場合は、アクション集合は組み合わせ爆発的に大きくなり得る。なので、より効率的なアルゴリズムが必要かも。
  - 更に、異なるスロットで表示されるアイテムのポジションバイアスや、スレート全体におけるアイテムの多様性などの効果も考慮する必要がある。
- combinatorial:
  - アクション集合は、異なる集合からのsub-actionsで構成される組み合わせオブジェクト。
    - (なるほど、slateタイプは同じアイテム集合からの組み合わせだけど、combinatorialは異なるアイテム集合からの組み合わせってことか...!)
  - このaction typeの場合も、アクション集合は組み合わせ爆発的に大きくなり得る。
  - また、sub-actionの間の相互作用効果なども考慮する必要がある。
- でも文献によっては、slate banditも時々combinatorial banditと呼ばれることがあるみたい。

アクションの特性2: Action set size

多くのbanditアルゴリズムのユースケースでは、離散的なアクションがある。
- (ほぼほぼ離散的なのかな? あ〜でもdynamic pricingとかは連続的なアクションなのか...!)
- アクション空間(action space)が小さい場合:
  - アクションIDをカテゴリ値とみなして、報酬の定式化においてbinary変数の集合としてencodeすることができる。
  - (アクション空間が小さい場合は、他クラス分類モデル的なものを使ってbanditアルゴリズムを組めそうだよね、みたいな話かな?)
- アクション空間が大きい場合:
  - アクション空間が大きい場合は、アクションを表現するための特徴量を使用することになる。
    - (i.e. アイテム特徴量を入力として使ったcontextual banditってことだよね...!こうやってアイテム間でモデルパラメータをshareしないと計算・運用コストが上がってしまうので...!)
  - ↑のアプローチ (action featurizationって論文では書いてあった) は、変数の次元を削減するだけでなく、アクション間の一般化を可能にし、アクションのコールドスタート問題を軽減するのにも役立つ
    - (うんうん、アクション間でモデルパラメータをshareしてるから、新しいアクションが追加された時もゼロから学習し直す必要がない、みたいな話だよね...!)
連続的なアクションを持つようなユースケースも一般的らしい。
- (dynamic pricingとか!)
- このあたりはそこまで詳しく書いてなかった。

(図は論文より引用)

意思決定に影響を与え得るその他のトピック

特徴量エンジニアリング

多くのアプリケーションでは、大きなcontextやアクション集合をより効率的に扱うために、特徴量を使用する。
- (逆に言えば、小さいcontextやアクション集合の場合は、context-freeなbanditアルゴリズムで対応できる、ということ...!)
  - ex. contextとして5個のユーザセグメント、アクション集合の数が10個の場合、5*10=50通りの報酬期待値をcontext-freeで学習することもあり得る...! (別の論文でセミパーソナライズ戦略として紹介されてた)
contextual banditアルゴリズムにおいて、期待報酬 $r$ (の推定値...!)は、アクション特徴量 $\phi_{a}$ とコンテキスト特徴量 $\phi_{c}$ の関数として書ける: $E[r] = f(\phi_{a}, \phi_{c})$
banditアルゴリズムにおける特徴量エンジニアリングは、$\phi_{a}$ と $\phi_{c}$ の選択/前処理/相互作用項の追加などを含む。
線形banditでは、$E[r]$ は特徴量に対して線形であると仮定される。
特に特徴量のサイズが大きい場合に非線形性をモデル化するために、生の特徴量（$\phi_a$ または/および $\phi_x$）から低次元の埋め込みを学習し、埋め込みを報酬関数に代わりに入れる事もあり得る。
- 教師あり学習のための埋め込み生成技術は一般的にバンディットにも適用できる。
線形報酬の仮定を緩和する別の方法は、報酬関数が特徴量ベクトルに対して非線形になる非線形バンディットを使用すること。

オフラインでの方策評価

オンラインテストの前にオフライン評価:
- bandit方策をいきなり実際のユーザトラフィックでテストすることはしばしばコストが高く、またユーザ体験を損なうリスクもある。なので、オフライン評価は一般的。
オフラインでの方策評価の重要な課題:
- ログデータにあるアクションとは異なるアクションに対して、ユーザがどのように反応したかを知ることができないこと。なぜなら、データには選択された行動に対する報酬しか含まれていないから。
  - (これがfull-information設定ではないbandit設定特有の課題...!)
- この反実仮想的な性質により、バンディットのオフライン評価は因果推論に似ており、オフライン評価手法では、方策 $\pi$ が行動を選択する場合の平均報酬 $E_{\pi}[r]$（因果効果）を推定しようとする。
一般的に、オフライン評価はアクションセットが大きくなるほど難しくなる。(うんうん、分散が爆発するから...!)
(「オフライン評価しやすいログデータを集められるような、bandit手法を採用しよう」という意思決定をしたりするから、この観点も重要だよなぁ...)

best-arm identification

いくつかのバンディットアプリケーションでは、実験中の累積報酬を最大化することではなく、実験の終了時に最良のアクション（例：最良のマーケティングキャンペーン戦略）を特定することを目的とするケースがある。
- この問題は、**best-arm identification (最良アームの特定)**として知られる。
- 従来のA/B/Nテストと同じ目標を持つが、実験中にアクションを適応的に選択することで統計的により効率的である可能性がある。