IDEAS home Printed from https://ideas.repec.org/p/cte/wsrepe/ws074109.html
   My bibliography  Save this paper

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

Author

Listed:
  • Niño-Mora, José

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.

Suggested Citation

  • Niño-Mora, José, 2007. "Two-stage index computation for bandits with switching penalties I : switching costs," DES - Working Papers. Statistics and Econometrics. WS ws074109, Universidad Carlos III de Madrid. Departamento de Estadística.
  • Handle: RePEc:cte:wsrepe:ws074109
    as

    Download full text from publisher

    File URL: https://e-archivo.uc3m.es/bitstream/handle/10016/794/ws074109.pdf?sequence=1
    Download Restriction: no

    More about this item

    Keywords

    Bandits;

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cte:wsrepe:ws074109. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ana Poveda). General contact details of provider: http://portal.uc3m.es/portal/page/portal/dpto_estadistica .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.