Two-stage index computation for bandits with switching penalties II : switching delays

e-Archivo Repository

Show simple item record

dc.contributor.author Niño Mora, José
dc.contributor.editor Universidad Carlos III de Madrid. Departamento de Estadística
dc.date.accessioned 2007-05-14T08:10:07Z
dc.date.available 2007-05-14T08:10:07Z
dc.date.issued 2007-05
dc.identifier.uri http://hdl.handle.net/10016/795
dc.description.abstract This paper addresses the multi-armed bandit problem with switching penalties including both costs and delays, extending results of the companion paper [J. Niño-Mora. "Two-Stage Index Computation for Bandits with Switching Penalties I: Switching Costs". Conditionally accepted at INFORMS J. Comp.], which addressed the no switching delays case. Asawa and Teneketzis (1996) introduced an index for bandits with delays that partly characterizes optimal policies, attaching to each bandit state a "continuation index" (its Gittins index) and a "switching index", yet gave no algorithm for it. This paper presents an 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 (5/2)n^3+O(n) arithmetic operations for an n -state bandit. The paper exploits the fact that the Asawa and Teneketzis index is the Whittle, or marginal productivity, index of a classic bandit with switching penalties in its semi- Markov restless reformulation, by deploying work-reward analysis and LP-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 a benchmark index policy across a wide instance range.
dc.format.extent 410925 bytes
dc.format.mimetype application/pdf
dc.language.iso eng
dc.relation.ispartofseries UC3M Working papers. Statistics and Econometrics
dc.relation.ispartofseries 07-10
dc.rights Atribución-NoComercial-SinDerivadas 3.0 España
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.subject.other Dynamic programming
dc.subject.other Semi-Markov
dc.subject.other Finite state
dc.subject.other Bandits
dc.subject.other Switching delays
dc.subject.other Index policy
dc.subject.other Whittle index
dc.subject.other Hysteresis
dc.subject.other Work-reward analysis
dc.subject.other LP-indexability
dc.subject.other Analysis of algorithms
dc.title Two-stage index computation for bandits with switching penalties II : switching delays
dc.type workingPaper
dc.subject.eciencia Estadística
dc.rights.accessRights openAccess
dc.identifier.repec ws074210
 Find Full text

Files in this item

*Click on file's image for preview. (Embargoed files's preview is not supported)


The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record