Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits

Abstract

We propose improved fixed-design confidence bounds for the linear logistic model. Our bounds significantly improve upon the state-of-the-art bound by Li et al. (2017) via recent developments of the self-concordant analysis of the logistic loss (Faury et al., 2020). Specifically, our confidence bound avoids a direct dependence on $1/\kappa$, where $\kappa$ is the minimal variance over all arms' reward distributions. In general, $1/\kappa$ scales exponentially with the norm of the unknown linear parameter ${\theta }^{\ast }$. Instead of relying on this worst-case quantity, our confidence bound for the reward of any given arm depends directly on the variance of that arm's reward distribution. We present two applications of our novel bounds to pure exploration and regret minimization logistic bandits improving upon state-of-the-art performance guarantees. For pure exploration, we also provide a lower bound highlighting a dependence on $1/\kappa$ for a family of instances.

References in corpus (12)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Semantic Jitter: Dense Supervision for Visual Comparisons via Synthetic Images
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Best-Arm Identification in Linear Bandits
• Adaptive, Personalized Diversity for Visual Discovery
• Gamification of Pure Exploration for Linear Bandits
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
• Improved Optimistic Algorithms for Logistic Bandits
• On the Complexity of A/B Testing
• Contextual Multi-Armed Bandits for Causal Marketing
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• On the Performance of Thompson Sampling on Logistic Bandits

Cited by in corpus (2)

• Regret Bounds for Generalized Linear Bandits under Parameter Drift
• Nearly Optimal Algorithms for Level Set Estimation