IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v43y2018i3p789-812.html
   My bibliography  Save this article

Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms

Author

Listed:
  • Will Ma

    (Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

We study the multi-armed bandit problem with arms which are Markov chains with rewards. In the finite-horizon setting, the celebrated Gittins indices do not apply, and the exact solution is intractable. We provide approximation algorithms for the general model of Markov decision processes with nonunit transition times. When preemption is allowed, we provide a (1/2 − ε )-approximation, along with an example showing this is tight. When preemption isn’t allowed, we provide a 1/12-approximation, which improves to a 4/27-approximation when transition times are unity. Our model captures the Markovian Bandits model of Gupta et al., the Stochastic Knapsack model of Dean et al., and the Budgeted Learning model of Guha and Munagala. Our algorithms improve existing results in all three areas. In our analysis, we encounter and overcome to our knowledge a new obstacle: an algorithm that provably exists via analytical arguments, but cannot be found in polynomial time

Suggested Citation

  • Will Ma, 2018. "Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 789-812, August.
    • Handle: RePEc:inm:ormoor:v:43:y:2018:i:3:p:789-812
    DOI: 10.1287/moor.2017.0884
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2017.0884
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2017.0884?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Taylan İlhan & Seyed M. R. Iravani & Mark S. Daskin, 2011. "TECHNICAL NOTE---The Adaptive Knapsack Problem with Stochastic Rewards," Operations Research, INFORMS, vol. 59(1), pages 242-248, February.
    2. Dimitris Bertsimas & Adam J. Mersereau, 2007. "A Learning Approach for Interactive Marketing to a Customer Segment," Operations Research, INFORMS, vol. 55(6), pages 1120-1135, December.
    3. Robert L. Carraway & Robert L. Schmidt & Lawrence R. Weatherford, 1993. "An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(2), pages 161-173, March.
    4. Vivek F. Farias & Ritesh Madan, 2011. "The Irrevocable Multiarmed Bandit Problem," Operations Research, INFORMS, vol. 59(2), pages 383-399, April.
    5. Brian C. Dean & Michel X. Goemans & Jan Vondrák, 2008. "Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 945-964, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Vahideh Manshadi & Scott Rodilitz, 2022. "Online Policies for Efficient Volunteer Crowdsourcing," Management Science, INFORMS, vol. 68(9), pages 6572-6590, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yasemin Merzifonluoglu & Joseph Geunes, 2021. "The Risk-Averse Static Stochastic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 931-948, July.
    2. Vivek F. Farias & Ritesh Madan, 2011. "The Irrevocable Multiarmed Bandit Problem," Operations Research, INFORMS, vol. 59(2), pages 383-399, April.
    3. Jian Li & Amol Deshpande, 2019. "Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 354-375, February.
    4. Range, Troels Martin & Kozlowski, Dawid & Petersen, Niels Chr., 2017. "A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs," Discussion Papers on Economics 9/2017, University of Southern Denmark, Department of Economics.
    5. Santiago R. Balseiro & David B. Brown & Chen Chen, 2021. "Dynamic Pricing of Relocating Resources in Large Networks," Management Science, INFORMS, vol. 67(7), pages 4075-4094, July.
    6. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    7. Deligiannis, Michalis & Liberopoulos, George, 2023. "Dynamic ordering and buyer selection policies when service affects future demand," Omega, Elsevier, vol. 118(C).
    8. Martin Skutella & Maxim Sviridenko & Marc Uetz, 2016. "Unrelated Machine Scheduling with Stochastic Processing Times," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 851-864, August.
    9. Brian C. Dean & Michel X. Goemans & Jan Vondrák, 2008. "Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 945-964, November.
    10. He, Qiao-Chu & Chen, Ying-Ju, 2018. "Dynamic pricing of electronic products with consumer reviews," Omega, Elsevier, vol. 80(C), pages 123-134.
    11. Marco Cello & Giorgio Gnecco & Mario Marchese & Marcello Sanguineti, 2015. "Narrowing the Search for Optimal Call-Admission Policies Via a Nonlinear Stochastic Knapsack Model," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 819-841, March.
    12. Springborn, Michael R., 2014. "Risk aversion and adaptive management: Insights from a multi-armed bandit model of invasive species risk," Journal of Environmental Economics and Management, Elsevier, vol. 68(2), pages 226-242.
    13. Taylan İlhan & Seyed M. R. Iravani & Mark S. Daskin, 2011. "TECHNICAL NOTE---The Adaptive Knapsack Problem with Stochastic Rewards," Operations Research, INFORMS, vol. 59(1), pages 242-248, February.
    14. David B. Brown & James E. Smith, 2013. "Optimal Sequential Exploration: Bandits, Clairvoyants, and Wildcats," Operations Research, INFORMS, vol. 61(3), pages 644-665, June.
    15. Roberto Cominetti & José R. Correa & Thomas Rothvoß & Jaime San Martín, 2010. "Optimal Selection of Customers for a Last-Minute Offer," Operations Research, INFORMS, vol. 58(4-part-1), pages 878-888, August.
    16. Jacko, Peter & Niño Mora, José, 2009. "An index for dynamic product promotion and the knapsack problem for perishable items," DES - Working Papers. Statistics and Econometrics. WS ws093111, Universidad Carlos III de Madrid. Departamento de Estadística.
    17. Stephen Chick & Martin Forster & Paolo Pertile, 2017. "A Bayesian decision theoretic model of sequential experimentation with delayed response," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(5), pages 1439-1462, November.
    18. Nicole Megow & Tjark Vredeveld, 2014. "A Tight 2-Approximation for Preemptive Stochastic Scheduling," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1297-1310, November.
    19. Daniel Adelman & Adam J. Mersereau, 2008. "Relaxations of Weakly Coupled Stochastic Dynamic Programs," Operations Research, INFORMS, vol. 56(3), pages 712-727, June.
    20. Santiago R. Balseiro & David B. Brown, 2019. "Approximations to Stochastic Dynamic Programs via Information Relaxation Duality," Operations Research, INFORMS, vol. 67(2), pages 577-597, March.

    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:inm:ormoor:v:43:y:2018:i:3:p:789-812. See general information about how to correct material in RePEc.

    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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.