EUVIMEDEUVIMED entdecken
Crossref

An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits

Gabriel Zayas-Cabán, Stefanus Jasin, Guihua Wang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →