Conference proceeding
Online Stochastic Linear Optimization under One-bit Feedback
Proceedings of Machine Learning Research, Vol.48, pp.392-401
International Conference on Machine Learning, 33rd (New York, New York, USA, 06/20/2016 - 06/22/2016)
06/2016
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 applications. 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\sqrtT), which matches the optimal result of stochastic linear bandits.
Details
- Title: Subtitle
- Online Stochastic Linear Optimization under One-bit Feedback
- Creators
- Lijun ZhangTianbao YangRong JinZhi-Hua Zhou
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of Machine Learning Research, Vol.48, pp.392-401
- Conference
- International Conference on Machine Learning, 33rd (New York, New York, USA, 06/20/2016 - 06/22/2016)
- Language
- English
- Date published
- 06/2016
- Academic Unit
- Computer Science
- Record Identifier
- 9984259466002771
Metrics
8 Record Views