An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits
Advances in Applied Probability · 2019-09 · 51 (03) · 745-772
DOI: 10.1017/apr.2019.29 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances in Applied Probability, online erschienen am 03.09.2019. Verfasst von Gabriel Zayas-Cabán und 2 weiteren Autor:innen. Die Arbeit wurde bisher 37-mal zitiert (Crossref) und nennt 18 Literaturangaben.
Abstract (Originalsprache)
We propose an asymptotically optimal heuristic, which we term randomized assignment control (RAC) for a restless multi-armed bandit problem with discrete-time and finite states. It is constructed using a linear programming relaxation of the original stochastic control formulation. In contrast to most of the existing literature, we consider a finite-horizon problem with multiple actions and time-dependent (i.e. nonstationary) upper bound on the number of bandits that can be activated at each time period; indeed, our analysis can also be applied in the setting with nonstationary transition matrix and nonstationary cost function. The asymptotic setting is obtained by letting the number of bandits and other related parameters grow to infinity. Our main contribution is that the asymptotic optimality of RAC in this general setting does not require indexability properties or the usual stability conditions of the underlying Markov chain (e.g. unichain) or fluid approximation (e.g. global stable attractor). Moreover, our multi-action setting is not restricted to the usual dominant action concept. Finally, we show that RAC is also asymptotically optimal for a dynamic population, where bandits can randomly arrive and depart the system.
Zitieren
APA
Zayas-Cabán, G., Jasin, S., & Wang, G. (2019). An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits. Advances in Applied Probability, 51(03), 745-772. https://doi.org/10.1017/apr.2019.29
Vancouver
Zayas-Cabán G, Jasin S, Wang G. An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits. Advances in Applied Probability. 2019;51(03):745-772. doi:10.1017/apr.2019.29
BibTeX
@article{ZayasCabn2019,
author = {Zayas-Cabán, Gabriel and Jasin, Stefanus and Wang, Guihua},
title = {An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits},
journal = {Advances in Applied Probability},
year = {2019},
volume = {51},
number = {03},
pages = {745--772},
doi = {10.1017/apr.2019.29}
}
EUVIMED