One-bit feedback is sufficient for upper confidence bound policies
We consider a variant of the traditional multi-armed bandit problem in which each arm is only able to provide one-bit feedback during each pull based on its past history of rewards. Our main result is the following: given an upper confidence bound policy which uses full-reward feedback, there exists a coding scheme for generating one-bit feedback, and a corresponding decoding scheme and arm selection policy, such that the ratio of the regret achieved by our policy and the regret of the full-reward feedback policy asymptotically approaches one.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Bayesian Linear Information Filtering Problem
We present a Bayesian sequential decision-making formulation of the information filtering problem, in which an algorithm presents items (news articles, scientific papers, tweets) arriving in a stream, and learns relevanc…
ArticlesDecision MakingSequential Decision MakingInformation Directed Sampling for Stochastic Bandits with Graph Feedback
We consider stochastic multi-armed bandit problems with graph feedback, where the decision maker is allowed to observe the neighboring actions of the chosen action. We allow the graph structure to vary with time and cons…
Decision MakingThompson SamplingAdaptive Sequential Experiments with Unknown Information Arrival Processes
Sequential experiments are often characterized by an exploration-exploitation tradeoff that is captured by the multi-armed bandit (MAB) framework. This framework has been studied and applied, typically when at each time …
Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem
This paper proposes a new method for the K-armed dueling bandit problem, a variation on the regular K-armed bandit problem that offers only relative feedback about pairs of arms. Our approach extends the Upper Confidence…
Information RetrievalRetrievalA Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents
This note gives a short, self-contained, proof of a sharp connection between Gittins indices and Bayesian upper confidence bound algorithms. I consider a Gaussian multi-armed bandit problem with discount factor $\gamma$.…