effSAMWMIX: An efficient Stochastic Multi-Armed Bandit Algorithm based on a Simulated Annealing with Multiplicative Weights

Boby Chaitanya Villari () and Mohammed Shahid Abdulla ()
Additional contact information
Boby Chaitanya Villari: Indian Institute of Management Kozhikode
Mohammed Shahid Abdulla: Indian Institute of Management Kozhikode

No 218, Working papers from Indian Institute of Management Kozhikode

Abstract: —SAMWMIX, a Stochastic Multi-Armed Bandit(SMAB) which obtains a ????(???????????? T) where T being the number of steps in the time horizon, is proposed in the literature . A blind-SAMWMIX which incorporates an input parameter ,which has better empirical performance but obtains a regret of the order ????(????????????????+???????? ????).Current work proposes an efficient version of SAMWMIX which not only obtains a regret of ????(???????????? K) but also exults a better performance. A proof for the same is given in this work. The proposed effSAMWMIX algorithm is compared with KL-UCB and Thompson Sampling(TS) algorithms over rewards which follow distributions like Exponential, Poisson, Bernoulli, Triangular, Truncated Normal distribution and a synthetic distribution designed to stress test SMAB algorithms with closely spaced reward means. It is shown that effSAMWMIX performs better than both KL-UCB & TS in both regret performance and execution time.

Keywords: stochastic multi-armed bandit; stochastic processes; reward distributions; optimization (search for similar items in EconPapers)
Pages: 9 pages
Date: 2017-01
New Economics Papers: this item is included in nep-ore
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://iimk.ac.in/websiteadmin/FacultyPublication ... rs/218fullp.pdf?t=19 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iik:wpaper:218

Access Statistics for this paper

More papers in Working papers from Indian Institute of Management Kozhikode IIMK Campus PO, Kunnamanagalam, Kozhikode, Kerala, India -673570. Contact information at EDIRC.
Bibliographic data for series maintained by Sudheesh Kumar ().