Online Stochastic Linear Optimization under One-bit Feedback

Abstract

In this paper, we study a special bandit setting of online stochastic linear optimization, where only one-bit of information is revealed to the learner at each round. This problem has found many applications including online advertisement and online recommendation. We assume the binary feedback is a random variable generated from the logit model, and aim to minimize the regret defined by the unknown linear function. Although the existing method for generalized linear bandit can be applied to our problem, the high computational cost makes it impractical for real-world problems. To address this challenge, we develop an efficient online learning algorithm by exploiting particular structures of the observation model. Specifically, we adopt online Newton step to estimate the unknown parameter and derive a tight confidence region based on the exponential concavity of the logistic loss. Our analysis shows that the proposed algorithm achieves a regret bound of $O(d\sqrt{T})$, which matches the optimal result of stochastic linear bandits.

References in corpus (2)

• Reducing Dueling Bandits to Cardinal Bandits
• Logistic Regression: Tight Bounds for Stochastic and Online Optimization

Cited by in corpus (17)

• Online Learning: A Comprehensive Survey
• Online Product Quantization
• Scalable Generalized Linear Bandits: Online Computation and Hashing
• A Simple Approach for Non-stationary Linear Bandits
• Bilinear Bandits with Low-rank Structure
• Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
• New Insights into Bootstrapping for Bandits
• Learning Adaptive Embedding Considering Incremental Class
• No-regret Exploration in Contextual Reinforcement Learning
• Hacking the Waveform: Generalized Wireless Adversarial Deep Learning
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs
• Reward-Biased Maximum Likelihood Estimation for Linear Stochastic Bandits
• Online Algorithm for Unsupervised Sequential Selection with Contextual Information
• Online optimal task offloading with one-bit feedback
• Stochastic Multi-Armed Bandits with Control Variates