Improved Online Confidence Bounds for Multinomial Logistic Bandits
arXiv:2502.10020v1 Announce Type: new
Abstract: In this paper, we propose an improved online confidence bound for multinomial logistic (MNL) models and apply this result to MNL bandits, achieving variance-dependent optimal regret. Recently, Lee & Oh (2024) established an online confidence bound for MNL models and achieved nearly minimax-optimal regret in MNL bandits. However, their results still depend on the norm-boundedness of the unknown parameter $B$ and the maximum size of possible outcomes $K$. To address this, we first derive an online confidence bound of $Oleft(sqrt{d log t} + B right)$, which is a significant improvement over the previous bound of $O (B sqrt{d} log t log K )$ (Lee & Oh, 2024). This is mainly achieved by establishing tighter self-concordant properties of the MNL loss and introducing a novel intermediary term to bound the estimation error. Using this new online confidence bound, we propose a constant-time algorithm, OFU-MNL++, which achieves a variance-dependent regret bound of $O Big( d log T sqrt{ smash[b]{sum_{t=1}^T} sigma_t^2 } Big) $ for sufficiently large $T$, where $sigma_t^2$ denotes the variance of the rewards at round $t$, $d$ is the dimension of the contexts, and $T$ is the total number of rounds. Furthermore, we introduce an Maximum Likelihood Estimation (MLE)-based algorithm that achieves an anytime, OFU-MN$^2$L, poly($(B)$)-free regret of $O Big( d log (BT) sqrt{ smash[b]{sum_{t=1}^T} sigma_t^2 } Big) $.
Abstract: In this paper, we propose an improved online confidence bound for multinomial logistic (MNL) models and apply this result to MNL bandits, achieving variance-dependent optimal regret. Recently, Lee & Oh (2024) established an online confidence bound for MNL models and achieved nearly minimax-optimal regret in MNL bandits. However, their results still depend on the norm-boundedness of the unknown parameter $B$ and the maximum size of possible outcomes $K$. To address this, we first derive an online confidence bound of $Oleft(sqrt{d log t} + B right)$, which is a significant improvement over the previous bound of $O (B sqrt{d} log t log K )$ (Lee & Oh, 2024). This is mainly achieved by establishing tighter self-concordant properties of the MNL loss and introducing a novel intermediary term to bound the estimation error. Using this new online confidence bound, we propose a constant-time algorithm, OFU-MNL++, which achieves a variance-dependent regret bound of $O Big( d log T sqrt{ smash[b]{sum_{t=1}^T} sigma_t^2 } Big) $ for sufficiently large $T$, where $sigma_t^2$ denotes the variance of the rewards at round $t$, $d$ is the dimension of the contexts, and $T$ is the total number of rounds. Furthermore, we introduce an Maximum Likelihood Estimation (MLE)-based algorithm that achieves an anytime, OFU-MN$^2$L, poly($(B)$)-free regret of $O Big( d log (BT) sqrt{ smash[b]{sum_{t=1}^T} sigma_t^2 } Big) $.
Joongkyu Lee, Min-hwan Oh
Go to original source