An optimal algorithm for bandit convex optimization
We consider the problem of online convex optimization against an arbitrary adversary with bandit feedback, known as bandit convex optimization. We give the first $\tilde{O}(\sqrt{T})$-regret algorithm for this setting based on a novel application of the ellipsoid method to online learning. This bound is known to be tight up to logarithmic factors. Our analysis introduces new tools in discrete convex geometry.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Regret Analysis for Continuous Dueling Bandit
The dueling bandit is a learning framework wherein the feedback information in the learning process is restricted to a noisy comparison between a pair of actions. In this research, we address a dueling bandit problem bas…
An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per round. We provide a simple algorithm and ana…
Second Order Methods for Bandit Optimization and Control
Bandit convex optimization (BCO) is a general framework for online decision making under uncertainty. While tight regret bounds for general convex losses have been established, existing algorithms achieving these bounds …
Decision MakingDecision Making Under UncertaintySecond-order methodsRisk-Averse Stochastic Convex Bandit
Motivated by applications in clinical trials and finance, we study the problem of online convex optimization (with bandit feedback) where the decision maker is risk-averse. We provide two algorithms to solve this problem…
Position-based Multiple-play Bandit Problem with Unknown Position Bias
Motivated by online advertising, we study a multiple-play multi-armed bandit problem with position bias that involves several slots and the latter slots yield fewer rewards. We characterize the hardness of the problem by…
Position