Two-stage index computation for bandits with switching penalties I: switching costs

José Niño Mora

DES - Working Papers. Statistics and Econometrics. WS from Universidad Carlos III de Madrid. Departamento de Estadística

Abstract: This paper addresses the multi-armed bandit problem with switching costs. Asawa and Teneketzis (1996) introduced an index that partly characterizes optimal policies, attaching to each bandit state a "continuation index" (its Gittins index) and a "switching index". They proposed to jointly compute both as the Gittins index of a bandit having 2n states — when the original bandit has n states — which results in an eight-fold increase in O(n^3) arithmetic operations relative to those to compute the continuation index alone. This paper presents a more efficient, 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. The paper exploits the fact that the Asawa and Teneketzis index is the Whittle, or marginal productivity, index of a classic bandit with switching costs in its restless reformulation, by deploying work-reward analysis and PCL-indexability methods introduced by the author. A computational study demonstrates the dramatic runtime savings achieved by the new algorithm, the near-optimality of the index policy, and its substantial gains against the benchmark Gittins index policy across a wide range of instances.

Keywords: Bandits; Switching; costs; Finite; state; Work-reward; analysis; PCL-indexability; Analysis; of; algorithms; Dynamic; programming; Markov; Index; policy; Whittle; index; Hysteresis (search for similar items in EconPapers)
Date: 2007-05
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://e-archivo.uc3m.es/rest/api/core/bitstreams ... 7dbffb7e16b0/content (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cte:wsrepe:ws074109

Access Statistics for this paper

More papers in DES - Working Papers. Statistics and Econometrics. WS from Universidad Carlos III de Madrid. Departamento de Estadística
Bibliographic data for series maintained by Ana Poveda ().