Timezone: »
Poster
UCB-based Algorithms for Multinomial Logistic Regression Bandits
Sanae Amani · Christos Thrampoulidis
Out of the rich family of generalized linear bandits, perhaps the most well studied ones are logistic bandits that are used in problems with binary rewards: for instance, when the learner aims 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\geq 2$ possible outcomes (+1 stands for the `not click' outcome): we assume that for a learner's action $\mathbf{x}_t$, the user selects one of $K+1\geq 2$ outcomes, say outcome $i$, with a MNL probabilistic model with corresponding unknown parameter $\bar{\boldsymbol{\theta}}_{\ast i}$. Each outcome $i$ is also associated with a revenue parameter $\rho_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 $\tilde{\mathcal{O}}(dK\sqrt{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.
Author Information
Sanae Amani (University of California, Los Angeles)
Christos Thrampoulidis (University of British Columbia)
More from the Same Authors
-
2022 : On the Implicit Geometry of Cross-Entropy Parameterizations for Label-Imbalanced Data »
Tina Behnia · Ganesh Ramachandra Kini · Vala Vakilian · Christos Thrampoulidis -
2022 : Generalization of Decentralized Gradient Descent with Separable Data »
Hossein Taheri · Christos Thrampoulidis -
2022 : Fast Convergence of Random Reshuffling under Interpolation and the Polyak-Ćojasiewicz Condition »
Chen Fan · Christos Thrampoulidis · Mark Schmidt -
2022 Poster: Imbalance Trouble: Revisiting Neural-Collapse Geometry »
Christos Thrampoulidis · Ganesh Ramachandra Kini · Vala Vakilian · Tina Behnia -
2022 Poster: Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently »
Haoyuan Sun · Kwangjun Ahn · Christos Thrampoulidis · Navid Azizan -
2021 Poster: AutoBalance: Optimized Loss Functions for Imbalanced Data »
Mingchen Li · Xuechen Zhang · Christos Thrampoulidis · Jiasi Chen · Samet Oymak -
2021 Poster: Label-Imbalanced and Group-Sensitive Classification under Overparameterization »
Ganesh Ramachandra Kini · Orestis Paraskevas · Samet Oymak · Christos Thrampoulidis -
2021 Poster: Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation »
Ke Wang · Vidya Muthukumar · Christos Thrampoulidis -
2020 Poster: Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View »
Christos Thrampoulidis · Samet Oymak · Mahdi Soltanolkotabi -
2020 Poster: Stage-wise Conservative Linear Bandits »
Ahmadreza Moradipari · Christos Thrampoulidis · Mahnoosh Alizadeh