A faster index algorithm and a computational study for bandits with switching costs

DOI10.1287/IJOC.1070.0238arXiv2304.01871MaRDI QIDQ6432060FDOQ6432060

Publication date: 4 April 2023

Abstract: We address the intractable multi-armed bandit problem with switching costs, for which Asawa and Teneketzis introduced in [M. Asawa and D. Teneketzis. 1996. Multi-armed bandits with switching penalties. IEEE Trans. Automat. Control, 41 328-348] an index that partially characterizes optimal policies, attaching to each project state a ``continuation index (its Gittins index) and a ``switching index. They proposed to jointly compute both as the Gittins index of a project with

2 n

states -- when the original project has

n

states -- resulting in an eight-fold increase in

O (n^{3})

arithmetic operations relative to those to compute the continuation index. We present a faster decoupled computation method, which in a first stage computes the continuation index and then, in a second stage, computes the switching index an order of magnitude faster in at most

n^{2} + O (n)

arithmetic operations, achieving overall a four-fold reduction in arithmetic operations and substantially reduced memory operations. The analysis exploits the fact that the Asawa and Teneketzis index is the marginal productivity index of the project in its restless reformulation, using methods introduced by the author. Extensive computational experiments are reported, which demonstrate the dramatic runtime speedups achieved by the new algorithm, as well as the near-optimality of the resultant index policy and its substantial gains against the benchmark Gittins index policy across a wide range of randomly generated two- and three-project instances.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Stochastic programming (90C15) Markov and semi-Markov decision processes (90C40)

This page was built for publication: A faster index algorithm and a computational study for bandits with switching costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432060)