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 발산 경계: Chen 등의 결과를 개선한 더욱 긴밀한 KL 발산 상한 수립

실험 설정

데이터셋

합성 데이터셋, 매개변수 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