일시: 3월 19일 (수) 10시 - 11시 30분

장소: 58동 119호 

발표자: 오민환 교수 (서울대학교 데이터사이언스대학원) 

 

In this talk, we address the contextual multinomial logistic (MNL) bandit problem, where a decision-making agent sequentially selects assortments of items based on contextual information, with user choices modeled by the MNL framework. Although widely applicable in various domains such as online retail and online advertising, a significant theoretical gap has persisted between known upper and lower regret bounds for this problem.
We first focus on the case of uniform revenues, establishing a minimax regret lower bound. We then introduce OFU-MNL+, a novel, computationally efficient algorithm achieving matching minimax-optimal upper bounds (up to logarithmic factors). Additionally, we extend our theoretical results by providing instance-dependent regret guarantees. Subsequently, we examine the case of non-uniform revenues, again proving matching lower and upper regret bounds. We demonstrate that OFU-MNL+ remains minimax-optimal (up to logarithmic factors) in this broader setting as well. Hence, our proposed algorithm is the first to achieve minimax optimality in either case. Empirical evaluations further validate our theoretical findings, confirming the effectiveness and practical performance of OFU-MNL+ based on cumulative regret and computational efficiency. Overall, this work provides the first minimax-optimal solution in the contextual MNL bandit literature, bridging theoretical efficiency with practical applicability.

This work is a joint work with my PhD student, Joongkyu Lee.