Online Stochastic Linear Optimization under One-bit Feedback
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Federated Online and Bandit Convex Optimization
We study the problems of distributed online and bandit convex optimization against an adaptive adversary. We aim to minimize the average regret on $M$ machines working in parallel over $T$ rounds with $R$ intermittent co…
Feedback Motion Planning for Stochastic Nonlinear Systems with Signal Temporal Logic Specifications
We study feedback motion planning for continuous-time stochastic nonlinear systems under signal temporal logic (STL) specifications. We propose a framework that synthesizes control policies for chance-constrained STL tra…
Motion PlanningA Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization
In this paper, we analyze the problem of online convex optimization in different settings, including different feedback types (full-information/semi-bandit/bandit/etc) in either stochastic or non-stochastic setting and d…
Stochastic MPC with Online-optimized Policies and Closed-loop Guarantees
This paper proposes a stochastic model predictive control method for linear systems affected by additive Gaussian disturbances. Closed-loop satisfaction of probabilistic constraints and recursive feasibility of the under…
Model Predictive ControlBayesian Optimization under Stochastic Delayed Feedback
Bayesian optimization (BO) is a widely-used sequential method for zeroth-order optimization of complex and expensive-to-compute black-box functions. The existing BO methods assume that the function evaluation (feedback) …
Bayesian Optimization