Bootstrapping Upper Confidence Bound
Upper Confidence Bound (UCB) method is arguably the most celebrated one used in online decision making with partial information feedback. Existing techniques for constructing confidence bounds are typically built upon various concentration inequalities, which thus lead to over-exploration. In this paper, we propose a non-parametric and data-dependent UCB algorithm based on the multiplier bootstrap. To improve its finite sample performance, we further incorporate second-order correction into the above construction. In theory, we derive both problem-dependent and problem-independent regret bounds for multi-armed bandits under a much weaker tail assumption than the standard sub-Gaussianity. Numerical results demonstrate significant regret reductions by our method, in comparison with several baselines in a range of multi-armed and linear bandit problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingMulti-Armed BanditsSimilar Papers 제목 키워드 기반
Bootstrapping with Models: Confidence Intervals for Off-Policy Evaluation
For an autonomous agent, executing a poor policy may be costly or even dangerous. For such agents, it is desirable to determine confidence interval lower bounds on the performance of any given policy without executing sa…
Off-policy evaluationAdapting multi-armed bandits policies to contextual bandits scenarios
This work explores adaptations of successful multi-armed bandits policies to the online contextual bandits scenario with binary rewards using binary classification algorithms such as logistic regression as black-box orac…
Binary ClassificationClassificationGeneral ClassificationMulti-Armed Bandits+2Principled Exploration via Optimistic Bootstrapping and Backward Induction
One principled approach for provably efficient exploration is incorporating the upper confidence bound (UCB) into the value function as a bonus. However, UCB is specified to deal with linear and tabular settings and is i…
Deep Reinforcement LearningEfficient ExplorationReinforcement Learning (RL)To bootstrap or to rollout? An optimal and adaptive interpolation
Bootstrapping and rollout are two fundamental principles for value function estimation in reinforcement learning (RL). We introduce a novel class of Bellman operators, called subgraph Bellman operators, that interpolate …
Reinforcement Learning (RL)Thompson Sampling for (Combinatorial) Pure Exploration
Existing methods of combinatorial pure exploration mainly focus on the UCB approach. To make the algorithm efficient, they usually use the sum of upper confidence bounds within arm set $S$ to represent the upper confiden…
Thompson Sampling