2021/03/21 by Sanae Amani, Christos Thrampoulidis, Amani, Sanae +1 · 2 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Algorithm #Artificial intelligence #Computer science #Data Stream Mining Techniques #Econometrics #FOS: Computer and information sciences #Logistic regression #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine learning #Mathematics #Multinomial distribution #Multinomial logistic regression #Smart Grid Energy Management #Statistics #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2103.11489
published in arXiv (Cornell University) (Cornell University) · 27 pages, 5 figures
arxiv created 2021/03/21 · openalex publication_date 2021/03/21 · arxiv updated 2021/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Out of the rich family of generalized linear bandits, perhaps the most well studied ones are logisitc bandits that are used in problems with binary rewards: for instance, when the learner/agent tries to maximize the profit over a user that can select one of two possible outcomes (e.g., `click' vs `no-click'). Despite remarkable recent progress and improved algorithms for logistic bandits, existing works do not address practical situations where the number of outcomes that can be selected by the user is larger than two (e.g., `click', `show me later', `never show again', `no click'). In this paper, we study such an extension. We use multinomial logit (MNL) to model the probability of each one of K+1≥ 2 possible outcomes (+1 stands for the `not click' outcome): we assume that for a learner's action xt, the user selects one of K+1≥ 2 outcomes, say outcome i, with a multinomial logit (MNL) probabilistic model with corresponding unknown parameter \boldsymbolθ∗ i. Each outcome i is also associated with a revenue parameter ρi and the goal is to maximize the expected revenue. For this problem, we present MNL-UCB, an upper confidence bound (UCB)-based algorithm, that achieves regret O(dK√(T)) with small dependency on problem-dependent constants that can otherwise be arbitrarily large and lead to loose regret bounds. We present numerical simulations that corroborate our theoretical results.