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. 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.
    2. 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.
    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. Karl Schlag & Andriy Zapechelnyuk, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.
    2. Greg Lewis & Vasilis Syrgkanis, 2018. "Adversarial Generalized Method of Moments," Papers 1803.07164, arXiv.org, revised Apr 2018.
    3. 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.
    4. Emerson Melo, 2021. "Learning in Random Utility Models Via Online Decision Problems," Papers 2112.10993, arXiv.org, revised Aug 2022.
    5. Simina Br^anzei, 2019. "Tit-for-Tat Dynamics and Market Volatility," Papers 1911.03629, arXiv.org, revised Jan 2024.
    6. 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.
    7. 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.
    8. Josef Hofbauer & Sylvain Sorin & Yannick Viossat, 2009. "Time Average Replicator and Best Reply Dynamics," Post-Print hal-00360767, HAL.
    9. David B. Brown & James E. Smith, 2013. "Optimal Sequential Exploration: Bandits, Clairvoyants, and Wildcats," Operations Research, INFORMS, vol. 61(3), pages 644-665, June.
    10. Nymisha Bandi & Theja Tulabandhula, 2020. "Off-Policy Optimization of Portfolio Allocation Policies under Constraints," Papers 2012.11715, arXiv.org.
    11. Schlag, Karl H. & Zapechelnyuk, Andriy, 2017. "Dynamic benchmark targeting," Journal of Economic Theory, Elsevier, vol. 169(C), pages 145-169.
    12. Ewerhart, Christian & Valkanova, Kremena, 2020. "Fictitious play in networks," Games and Economic Behavior, Elsevier, vol. 123(C), pages 182-206.
    13. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    14. 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.
    15. Shie Mannor & Nahum Shimkin, 2003. "The Empirical Bayes Envelope and Regret Minimization in Competitive Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 28(2), pages 327-345, May.
    16. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2006. "Stochastic Approximations and Differential Inclusions, Part II: Applications," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 673-695, November.
    17. Gao, Kun & Sun, Lijun & Yang, Ying & Meng, Fanyu & Qu, Xiaobo, 2021. "Cumulative prospect theory coupled with multi-attribute decision making for modeling travel behavior," Transportation Research Part A: Policy and Practice, Elsevier, vol. 148(C), pages 1-21.
    18. Andriy Zapechelnyuk, 2009. "Limit Behavior of No-regret Dynamics," Discussion Papers 21, Kyiv School of Economics.
    19. Daskalakis, Constantinos & Deckelbaum, Alan & Kim, Anthony, 2015. "Near-optimal no-regret algorithms for zero-sum games," Games and Economic Behavior, Elsevier, vol. 92(C), pages 327-348.
    20. Sandroni, Alvaro & Smorodinsky, Rann, 2004. "Belief-based equilibrium," Games and Economic Behavior, Elsevier, vol. 47(1), pages 157-171, April.

    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.