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 to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algorithm is instance-wise asymptotically optimal. We also provide comprehensive empirical results to demonstrate the algorithm's superior performance over existing algorithms under a variety of different scenarios.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Regret Minimization and Statistical Inference in Online Decision Making with High-dimensional Covariates
This paper investigates regret minimization, statistical inference, and their interplay in high-dimensional online decision-making based on the sparse linear context bandit model. We integrate the $\varepsilon$-greedy ba…
Decision MakingvalidMinimax 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…
From Restless to Contextual: A Thresholding Bandit Approach to Improve Finite-horizon Performance
Online restless bandits extend classic contextual bandits by incorporating state transitions and budget constraints, representing each agent as a Markov Decision Process (MDP). This framework is crucial for finite-horizo…
Multi-Armed BanditsFLIPHAT: 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 MakingAdapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model, where the learner observes only the cumulative loss incurred in each episode, ra…