.png){kind=icon}
.png){kind=icon}
Return
Large Deviation Algorithms for Thresholding Bandit Problem
.png){kind=icon}
PRE
AI
DOI：10.26599/BDMA.2025.9020028.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Thresholding Bandit (TB) problem is a popular sequential decision-making problem, which aims at identifying the systems whose means are greater than a threshold. Instead of working on the upper bound of a loss function, our approach stands out from conventional practices by directly minimizing the loss itself. Leveraging the large deviation theory, we firstly provide an asymptotically optimal allocation rule for the TB problem, and then propose a parameter-free Large Deviation (LD) algorithm to make the allocation rule implementable. Central limit theorem-based Large Deviation (CLD) algorithm is further proposed as a supplement to improve the computation efficiency using normal approximation. Extensive experiments are conducted to validate the superiority of our algorithms compared to existing methods, and demonstrate their broader applications to more general distributions and various kinds of loss functions.
Keywords:
Upper bound
Decision making
Big Data
Approximation algorithms
Computational efficiency
Resource management
Data mining
Thresholding Bandit (TB) problem
Large Deviation (LD) theory
optimal allocation rule
parameter-free policy
asymptotical optimality
Journal
IF:
6.2
Papers:
274
Citations:
1.0K
Organization
View more organizations