An Index-based Deterministic Asymptotically Optimal Algorithm for Constrained Multi-armed Bandit Problems
From MaRDI portal
Publication:6346060
DOI10.1016/J.AUTOMATICA.2021.109673arXiv2007.14550MaRDI QIDQ6346060
Publication date: 28 July 2020
Abstract: 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.
This page was built for publication: An Index-based Deterministic Asymptotically Optimal Algorithm for Constrained Multi-armed Bandit Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6346060)
