An Index-based Deterministic Asymptotically Optimal Algorithm for Constrained Multi-armed Bandit Problems
For the model of constrained multi-armed bandit, we show that by construction there exists an index-based deterministic asymptotically optimal algorithm. The optimality is achieved by the convergence of the probability of choosing an optimal feasible arm to one over infinite horizon. The algorithm is built upon Locatelli et al.'s "anytime parameter-free thresholding" algorithm under the assumption that the optimal value is known. We provide a finite-time bound to the probability of the asymptotic optimality given as 1-O(|A|Te^{-T}) where T is the horizon size and A is the set of the arms in the bandit. We then study a relaxed-version of the algorithm in a general form that estimates the optimal value and discuss the asymptotic optimality of the algorithm after a sufficiently large T with examples.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Sliding Regret in Stochastic Bandits: Discriminating Index and Randomized Policies
This paper studies the one-shot behavior of no-regret algorithms for stochastic bandits. Although many algorithms are known to be asymptotically optimal with respect to the expected regret, over a single run, their pseud…
Thompson SamplingGINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits
The restless multi-armed bandit (RMAB) framework is a popular model with applications across a wide variety of fields. However, its solution is hindered by the exponentially growing state space (with respect to the numbe…
Multi-Armed BanditsQ-LearningOptimism Stabilizes Thompson Sampling for Adaptive Inference
Thompson sampling (TS) is widely used for stochastic multi-armed bandits, yet its inferential properties under adaptive data collection are subtle. Classical asymptotic theory for sample means can fail because arm-specif…
Multi-Armed BanditsDeterministic Coreset Construction via Adaptive Sensitivity Trimming
We develop a rigorous framework for deterministic coreset construction in empirical risk minimization (ERM). Our central contribution is the Adaptive Deterministic Uniform-Weight Trimming (ADUWT) algorithm, which constru…
Fair Incentives for Repeated Engagement
We study a decision-maker's problem of finding optimal monetary incentive schemes for retention when faced with agents whose participation decisions (stochastically) depend on the incentive they receive. Our focus is on …
Decision MakingFairnessStochastic Optimization