Optimal Thresholding Linear Bandit
We study a novel pure exploration problem: the $\epsilon$-Thresholding Bandit Problem (TBP) with fixed confidence in stochastic linear bandits. We prove a lower bound for the sample complexity and extend an algorithm designed for Best Arm Identification in the linear case to TBP that is asymptotically optimal.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding Linear Bandit Problem
In this study, we delve into the Thresholding Linear Bandit (TLB) problem, a nuanced domain within stochastic Multi-Armed Bandit (MAB) problems, focusing on maximizing decision accuracy against a linearly defined thresho…
Computational EfficiencyDecision MakingSequential Decision MakingMinimax Rate-Optimal Algorithms for High-Dimensional Stochastic Linear Bandits
We study the stochastic linear bandit problem with multiple arms over $T$ rounds, where the covariate dimension $d$ may exceed $T$, but each arm-specific parameter vector is $s$-sparse. We begin by analyzing the sequenti…
Thresholding Bandit with Optimal Aggregate Regret
We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold $\theta$, with a fixed budget of $T$ trials. We introduce LSA, a new, simple and anytime algorithm that aims…
FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits
High dimensional sparse linear bandits serve as an efficient model for sequential decision-making problems (e.g. personalized medicine), where high dimensional features (e.g. genomic data) on the users are available, but…
Decision MakingSequential Decision MakingDifferentially Private High Dimensional Bandits
We consider a high-dimensional stochastic contextual linear bandit problem when the parameter vector is $s_{0}$-sparse and the decision maker is subject to privacy constraints under both central and local models of diffe…