mlsanityData to 14 Oct 2026

Online Stochastic Linear Optimization under One-bit Feedback

arXiv 1509.07728 ↗First posted 25 Sep 2015cs.LGcited by 26

Not on the map. Why?

Abstract (arXiv)

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√T), which matches the optimal result of stochastic linear bandits.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). First posted on arXiv 25 Sep 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 3; 2023: 4; 2024: 3; 2025: 4; 2026: 4.

26 papers.

Sort:

By area:

  1. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  2. 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
  3. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  4. 2021Multinomial Logit Contextual Bandits: Provable Optimality and Practicalitycited by 21
  5. 2021Dynamic pricing and assortment under a contextual MNL demandcited by 20
  6. 2024Nearly Minimax Optimal Regret for Multinomial Logistic Banditcited by 20
  7. 2021Distributed Learning Systems with First-order Methodscited by 17
  8. 2021Maillard Sampling: Boltzmann Exploration Done Optimallycited by 13
  9. 2022Communication Efficient Federated Learning for Generalized Linear Banditscited by 13
  10. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
  11. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  12. 2021Stochastic Multi-Armed Bandits with Control Variatescited by 7
14 more
  1. 2024Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimizationcited by 6
  2. 2025Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functionscited by 6
  3. 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
  4. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  5. 2022Reinforcement Learning with a Terminatorcited by 4
  6. 2025A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimizationcited by 3
  7. 2021CORe: Capitalizing On Rewards in Bandit Explorationcited by 1
  8. 2023Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Banditscited by 1
  9. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  10. 2021On Learning to Rank Long Sequences with Contextual Banditscited by 0
  11. 2023Revisiting Weighted Strategy for Non-stationary Parametric Banditscited by 0
  12. 2025Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoidscited by 0
  13. 2026Stochastic Multi-Armed Bandits with Limited Control Variatescited by 0
  14. 2026Efficient Multinomial Logistic Bandit via Frequent Directionscited by 0