Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit
Motivated by real-world applications such as fast fashion retailing and online advertising, the Multinomial Logit Bandit (MNL-bandit) is a popular model in online learning and operations research, and has attracted much attention in the past decade. However, it is a bit surprising that pure exploration, a basic problem in bandit theory, has not been well studied in MNL-bandit so far. In this paper we give efficient algorithms for pure exploration in MNL-bandit. Our algorithms achieve instance-sensitive pull complexities. We also complement the upper bounds by an almost matching lower bound.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Near Optimal Pure Exploration in Logistic Bandits
Bandit algorithms have garnered significant attention due to their practical applications in real-world scenarios. However, beyond simple settings such as multi-arm or linear bandits, optimal algorithms remain scarce. No…
Near Instance Optimal Model Selection for Pure Exploration Linear Bandits
We introduce the model selection problem in pure exploration linear bandits, where the learner needs to adapt to the instance-dependent complexity measure of the smallest hypothesis class containing the true model. We de…
Experimental DesignModel SelectionGamification of Pure Exploration for Linear Bandits
We investigate an active pure-exploration setting, that includes best-arm identification, in the context of linear stochastic bandits. While asymptotically optimal algorithms exist for standard multi-arm bandits, the exi…
Experimental DesignFast Pure Exploration via Frank-Wolfe
We study the problem of active pure exploration with fixed confidence in generic stochastic bandit environments. The goal of the learner is to answer a query about the environment with a given level of certainty while mi…
Pure Exploration of Multi-armed Bandit Under Matroid Constraints
We study the pure exploration problem subject to a matroid constraint (Best-Basis) in a stochastic multi-armed bandit game. In a Best-Basis instance, we are given $n$ stochastic arms with unknown reward distributions, as…