An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits. (September 2019)

• Record Type: Journal Article
• Authors: Zayas-Cabán, Gabriel; Jasin, Stefanus; Wang, Guihua
• Is Part Of: Advances in applied probability. Volume 51:Number 3(2019)
• Page Start: 745
• Page End: 772
• Publication Date: 2019-09
• Subjects: Restless bandit, -- asymptotic optimality, -- finite horizon, -- nonstationary, -- arm acquiring, -- nonindexable bandit; Primary 90C40, -- Secondary 68M20, -- 90B36; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1017/apr.2019.29
• Languages: English
• ISSNs: 0001-8678

Abstract

Abstract: 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.