2025-11-15T02:07:10.757818

Nearly Minimax Optimal Regret for Multinomial Logistic Bandit

Lee, Oh

In this paper, we study the contextual multinomial logit (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information, and user feedback follows an MNL choice model. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size $K$. Additionally, the variation in reward structures between these bounds complicates the quest for optimality. Under uniform rewards, where all items have the same expected reward, we establish a regret lower bound of $Î©(d\sqrt{T/K})$ and propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound of $\tilde{O}(d\sqrt{T/K})$. We also provide instance-dependent minimax regret bounds under uniform rewards. Under non-uniform rewards, we prove a lower bound of $Î©(d\sqrt{T})$ and an upper bound of $\tilde{O}(d\sqrt{T})$, also achievable by OFU-MNL+. Our empirical studies support these theoretical findings. To the best of our knowledge, this is the first work in the contextual MNL bandit literature to prove minimax optimality -- for either uniform or non-uniform reward setting -- and to propose a computationally efficient algorithm that achieves this optimality up to logarithmic factors.

academic

多項ロジスティックバンディットにおけるほぼミニマックス最適遺憾

基本情報

論文ID: 2405.09831
タイトル: Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
著者: Joongkyu Lee (ソウル国立大学), Min-hwan Oh (ソウル国立大学)
分類: stat.ML cs.LG
発表時期/会議: NeurIPS 2024 (第38回ニューラル情報処理システム会議)
論文リンク: https://arxiv.org/abs/2405.09831

要約

本論文は、文脈付き多項ロジスティック(MNL)バンディット問題を研究している。学習エージェントは文脈情報に基づいて順序的に商品の組み合わせを選択し、ユーザーのフィードバックはMNL選択モデルに従う。既存の研究では下界と上界の間に大きな隔たりが存在し、特に最大商品組合サイズKに関して顕著である。統一報酬設定では、本論文はΩ(d√T/K)の遺憾下界を確立し、定数時間アルゴリズムOFU-MNL+を提案して、一致する上界Õ(d√T/K)を実現している。非統一報酬設定では、Ω(d√T)の下界とÕ(d√T)の上界を証明している。これは文脈付きMNLバンディット文献において、ミニマックス最適性を証明した初めての研究である。

研究背景と動機

問題背景

MNLバンディット問題: 推奨システムとオンライン小売などのアプリケーションでは、エージェントはユーザーに商品セットを提供する必要があり、ユーザーの選択行動は多項ロジスティック(MNL)モデルに従う
文脈情報: 各ラウンドでエージェントは商品特性と可能なユーザー文脈情報を観察できる
理論的空白: 既存の研究では遺憾界の上界と下界の間に大きな隔たりが存在し、特に商品組合サイズKへの依存性に関して顕著である

研究動機

理論的完全性: MNLバンディット理論分析の空白を埋め、厳密な遺憾界を確立する
アルゴリズム効率: 既存方法の指数時間複雑性を回避する計算効率の高いアルゴリズムを設計する
実用的応用: 推奨システムなどの実用的アプリケーションに理論的保証と効率的なアルゴリズムを提供する

既存方法の限界

理論的隔たり: 下界Ω(d√T/K)と上界Õ(d√T)の間に√Kの隔たりが存在する
計算複雑性: 既存のアルゴリズムはすべての可能な商品組み合わせを列挙する必要があり、指数時間複雑性につながる
パラメータ依存: 問題関連定数κへの悪い依存性があり、1/κ = O(K²)である

核心的貢献

厳密な遺憾界の確立:
- 統一報酬下: 下界Ω(√(v₀K/(v₀+K))d√T)、上界Õ(√(v₀K/(v₀+K))d√T)
- 非統一報酬下: 下界Ω(d√T)、上界Õ(d√T)
効率的なアルゴリズムOFU-MNL+の提案:
- 定数時間複雑性O(1)、ラウンド数tに無関
- MNLバンディットでKの増加に伴い遺憾が減少することを証明した初めてのアルゴリズム
理論的革新:
- 外部選択肢の吸引パラメータv₀が遺憾に与える影響を初めて明確に示す
- インスタンス依存のミニマックス遺憾界を提供する
技術的改善:
- 改善された楕円ポテンシャル補題、Kへの依存性を排除
- 定数自己協調性を持つ損失関数の分析

方法の詳細説明

タスク定義

入力:

各ラウンドtで、N個の商品の特徴ベクトルx_ ∈ ℝᵈを観察
最大商品組合サイズK
外部選択肢の吸引パラメータv₀

出力:

商品組合S_t ⊆ {1,...,N}を選択、|S_t| ≤ K
ユーザー選択c_t ∈ S_t ∪ {0}を観察、MNLモデルに従う

目標: 累積遺憾Reg_T(w*) = Σ_^T R_t(S_t, w) - R_t(S_t, w*)を最小化

モデルアーキテクチャ

MNL選択モデル

ユーザーが商品i ∈ S_tを選択する確率:

p_t(i|S_t, w*) = exp(x_{ti}^T w*) / (v₀ + Σ_{j∈S_t} exp(x_{tj}^T w*))

外部選択肢(商品を選択しない)の確率:

p_t(0|S_t, w*) = v₀ / (v₀ + Σ_{j∈S_t} exp(x_{tj}^T w*))

OFU-MNL+アルゴリズムの核心成分

オンラインパラメータ推定:
```
w_{t+1} = argmin_{w∈W} ⟨∇ℓ_t(w_t), w⟩ + (1/2η)||w - w_t||²_{H̃_t}
```
ここでH̃_t = H_t + ηG_t(w_t)、G_t(w)はMNL損失のヘッシアン行列
信頼集合の構成:
```
C_t(δ) = {w ∈ W : ||w_t - w||_{H_t} ≤ β_t(δ)}
```
ここでβ_t(δ) = O(√(d log t log K))

楽観的効用計算:

α_{ti} = x_{ti}^T w_t + β_t(δ)||x_{ti}||_{H_t^{-1}}

商品組合選択:
- 統一報酬: 最も高いα_を持つK個の商品を選択
- 非統一報酬: 多項式時間の組合最適化問題を解く

技術的革新点

改善された自己協調分析: MNL損失関数が3√2-自己協調性を持つことを証明、従来の√(6K)から√K因子改善

K無関の楕円ポテンシャル補題:

Σ_{t=1}^T Σ_{i∈S_t} p_t(i|S_t,w_{t+1})p_t(0|S_t,w_{t+1})||x_{ti}||²_{H_t^{-1}} ≤ 2d log(1 + T/(dλ))

厳密なKL発散界: より厳密なKL発散上界を確立、Chenらの結果を改善

実験設定

データセット

合成データセット、パラメータw* ∈ ℝᵈは-1/√d, 1/√dᵈから均一にサンプリング
文脈特徴x_は多変量ガウス分布N(0_d, I_d)からサンプリングし-1/√d, 1/√dᵈに切り詰め
設定: N=100, K∈{5,10,15}, d=5, T=3000

評価指標

累積遺憾: Σ_^T R_t(S_t, w) - R_t(S_t, w*)
ラウンドごとの計算時間

比較方法

UCB-MNL: 信頼上界ベースの方法
TS-MNL: Thompson標本化ベースの方法

実装詳細

正則化パラメータλ = 84√(2d)η
ステップサイズη = (1/2)log(K+1) + 2
信頼半径β_t(δ) = O(√(d log t log K))

実験結果

主要結果

遺憾性能:
- 統一報酬下では、Kの増加に伴いすべてのアルゴリズムの累積遺憾が減少
- 非統一報酬下では、Kの増加は遺憾改善を保証しない
- OFU-MNL+はすべての設定でベースライン方法を大幅に上回る
計算効率:
- OFU-MNL+は定数計算コストを維持、ラウンド数tに無関
- ベースライン方法の計算時間はtに対して線形に増加
- 統一報酬設定下の実行時間は非統一設定の約1/10