IDEAS home Printed from https://ideas.repec.org/a/spr/indpam/v47y2016i2d10.1007_s13226-016-0184-5.html
   My bibliography  Save this article

Multi-armed bandits based on a variant of Simulated Annealing

Author

Listed:
  • Mohammed Shahid Abdulla

    (Indian Institute of Management)

  • Shalabh Bhatnagar

    (Indian Institute of Science)

Abstract

A variant of Simulated Annealing termed Simulated Annealing with Multiplicative Weights (SAMW) has been proposed in the literature. However, convergence was dependent on a parameter β(T), which was calculated a-priori based on the total iterations T the algorithm would run for. We first show the convergence of SAMW even when a diminishing stepsize β k → 1 is used, where k is the index of iteration. Using this SAMW as a kernel, a stochastic multi-armed bandit (SMAB) algorithm called SOFTMIX can be improved to obtain the minimum-possible log regret, as compared to log2 regret of the original. Another modification of SOFTMIX is proposed which avoids the need for a parameter that is dependent on the reward distribution of the arms. Further, a variant of SOFTMIX that uses a comparison term drawn from another popular SMAB algorithm called UCB1 is then described. It is also shown why the proposed scheme is computationally more efficient over UCB1, and an alternative to this algorithm with simpler stepsizes is also proposed. Numerical simulations for all the proposed algorithms are then presented.

Suggested Citation

  • Mohammed Shahid Abdulla & Shalabh Bhatnagar, 2016. "Multi-armed bandits based on a variant of Simulated Annealing," Indian Journal of Pure and Applied Mathematics, Springer, vol. 47(2), pages 195-212, June.
    • Handle: RePEc:spr:indpam:v:47:y:2016:i:2:d:10.1007_s13226-016-0184-5
    DOI: 10.1007/s13226-016-0184-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13226-016-0184-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13226-016-0184-5?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Freund, Yoav & Schapire, Robert E., 1999. "Adaptive Game Playing Using Multiplicative Weights," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 79-103, October.
    2. Hyeong Soo Chang & Michael C. Fu & Jiaqiao Hu & Steven I. Marcus, 2005. "An Adaptive Sampling Algorithm for Solving Markov Decision Processes," Operations Research, INFORMS, vol. 53(1), pages 126-139, February.
    3. Vivek F. Farias & Ritesh Madan, 2011. "The Irrevocable Multiarmed Bandit Problem," Operations Research, INFORMS, vol. 59(2), pages 383-399, April.
    Full references (including those not matched with items on IDEAS)

    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. Josef Hofbauer & Sylvain Sorin & Yannick Viossat, 2009. "Time Average Replicator and Best-Reply Dynamics," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 263-269, May.
    2. Shie Mannor & Gilles Stoltz, 2009. "A Geometric Proof of Calibration," Working Papers hal-00442042, HAL.
    3. Du, Ye & Lehrer, Ehud, 2020. "Constrained no-regret learning," Journal of Mathematical Economics, Elsevier, vol. 88(C), pages 16-24.
    4. Karl Schlag & Andriy Zapechelnyuk, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.
    5. Schlag, Karl & Zapechelnyuk, Andriy, 2012. "On the impossibility of achieving no regrets in repeated games," Journal of Economic Behavior & Organization, Elsevier, vol. 81(1), pages 153-158.
    6. Greg Lewis & Vasilis Syrgkanis, 2018. "Adversarial Generalized Method of Moments," Papers 1803.07164, arXiv.org, revised Apr 2018.
    7. Márton Gosztonyi & Csákné Filep Judit, 2022. "Profiling (Non-)Nascent Entrepreneurs in Hungary Based on Machine Learning Approaches," Sustainability, MDPI, vol. 14(6), pages 1-20, March.
    8. Denis Sauré & Assaf Zeevi, 2013. "Optimal Dynamic Assortment Planning with Demand Learning," Manufacturing & Service Operations Management, INFORMS, vol. 15(3), pages 387-404, July.
    9. Emerson Melo, 2021. "Learning in Random Utility Models Via Online Decision Problems," Papers 2112.10993, arXiv.org, revised Aug 2022.
    10. Michael C. Fu, 2019. "Simulation-Based Algorithms for Markov Decision Processes: Monte Carlo Tree Search from AlphaGo to AlphaZero," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(06), pages 1-25, December.
    11. Simina Br^anzei, 2019. "Tit-for-Tat Dynamics and Market Volatility," Papers 1911.03629, arXiv.org, revised Jan 2024.
    12. Sergiu Hart & Andreu Mas-Colell, 2013. "A General Class Of Adaptive Strategies," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 3, pages 47-76, World Scientific Publishing Co. Pte. Ltd..
    13. Mario Bravo, 2016. "An Adjusted Payoff-Based Procedure for Normal Form Games," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1469-1483, November.
    14. Mannor, Shie & Shimkin, Nahum, 2008. "Regret minimization in repeated matrix games with variable stage duration," Games and Economic Behavior, Elsevier, vol. 63(1), pages 227-258, May.
    15. Kris Johnson Ferreira & Joel Goh, 2021. "Assortment Rotation and the Value of Concealment," Management Science, INFORMS, vol. 67(3), pages 1489-1507, March.
    16. Hanyu Li & Wenhan Huang & Zhijian Duan & David Henry Mguni & Kun Shao & Jun Wang & Xiaotie Deng, 2023. "A survey on algorithms for Nash equilibria in finite normal-form games," Papers 2312.11063, arXiv.org.
    17. Yu, Ruyang & Zhang, Kai & Ramasubramanian, Brindha & Jiang, Shu & Ramakrishna, Seeram & Tang, Yuhang, 2024. "Ensemble learning for predicting average thermal extraction load of a hydrothermal geothermal field: A case study in Guanzhong Basin, China," Energy, Elsevier, vol. 296(C).
    18. David B. Brown & James E. Smith, 2013. "Optimal Sequential Exploration: Bandits, Clairvoyants, and Wildcats," Operations Research, INFORMS, vol. 61(3), pages 644-665, June.
    19. Nymisha Bandi & Theja Tulabandhula, 2020. "Off-Policy Optimization of Portfolio Allocation Policies under Constraints," Papers 2012.11715, arXiv.org.
    20. Arnoud V. den Boer & Bert Zwart, 2015. "Dynamic Pricing and Learning with Finite Inventories," Operations Research, INFORMS, vol. 63(4), pages 965-978, August.

    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:spr:indpam:v:47:y:2016:i:2:d:10.1007_s13226-016-0184-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.