On the Complexity of Bandit Linear Optimization
We study the attainable regret for online linear optimization problems with bandit feedback, where unlike the full-information setting, the player can only observe its own loss rather than the full loss vector. We show that the price of bandit information in this setting can be as large as $d$, disproving the well-known conjecture that the regret for bandit linear optimization is at most $\sqrt{d}$ times the full-information regret. Surprisingly, this is shown using "trivial" modifications of standard domains, which have no effect in the full-information setting. This and other results we present highlight some interesting differences between full-information and bandit learning, which were not considered in previous literature.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Online Bandit Linear Optimization: A Study
This article introduces the concepts around Online Bandit Linear Optimization and explores an efficient setup called SCRiBLe (Self-Concordant Regularization in Bandit Learning) created by Abernethy et. al.\cite{abernethy…
Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
Bandit problems with linear or concave reward have been extensively studied, but relatively few works have studied bandits with non-concave reward. This work considers a large family of bandit problems where the unknown …
Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding
Bayesian optimization is a framework for global search via maximum a posteriori updates rather than simulated annealing, and has gained prominence for decision-making under uncertainty. In this work, we cast Bayesian opt…
Bayesian OptimizationDecision MakingDecision Making Under Uncertaintyglobal-optimizationOracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback
We propose computationally efficient algorithms for \textit{online linear optimization with bandit feedback}, in which a player chooses an \textit{action vector} from a given (possibly infinite) set $\mathcal{A} \subsete…
Computational EfficiencyApproximation Theory Based Methods for RKHS Bandits
The RKHS bandit problem (also called kernelized multi-armed bandit problem) is an online optimization problem of non-linear functions with noisy feedback. Although the problem has been extensively studied, there are unsa…