Improved Optimistic Algorithms for Logistic Bandits

Abstract

The generalized linear bandit framework has attracted a lot of attention in recent years by extending the well-understood linear setting and allowing to model richer reward structures. It notably covers the logistic model, widely used when rewards are binary. For logistic bandits, the frequentist regret guarantees of existing algorithms are $\tilde{\mathcal{O}}(\kappa \sqrt{T})$, where $\kappa$ is a problem-dependent constant. Unfortunately, $\kappa$ can be arbitrarily large as it scales exponentially with the size of the decision set. This may lead to significantly loose regret bounds and poor empirical performance. In this work, we study the logistic bandit with a focus on the prohibitive dependencies introduced by $\kappa$. We propose a new optimistic algorithm based on a finer examination of the non-linearities of the reward function. We show that it enjoys a $\tilde{\mathcal{O}}(\sqrt{T})$ regret with no dependency in $\kappa$, but for a second order term. Our analysis is based on a new tail-inequality for self-normalized martingales, of independent interest.

arXiv commentAccepted at ICML2020

References in corpus (5)

• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Finite-Time Analysis of Kernelised Contextual Bandits
• Scalable Generalized Linear Bandits: Online Computation and Hashing
• An Information-Theoretic Analysis for Thompson Sampling with Many Actions
• On the Performance of Thompson Sampling on Logistic Bandits

Cited by in corpus (10)

• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Advances in Preference-based Reinforcement Learning: A Review
• On the Theory of Reinforcement Learning with Once-per-Episode Feedback
• Dueling RL: Reinforcement Learning with Trajectory Preferences
• Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits
• UCB-based Algorithms for Multinomial Logistic Regression Bandits
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification