Header menu link for other important links
X
Thompson sampling based mechanisms for stochastic multi-Armed bandit problems
, S. Gujar, S. Jain, Y. Narahari
Published in International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
2017
Volume: 1
   
Pages: 87 - 95
Abstract
This paper explores Thompson sampling in the context of mechanism design for stochastic multi-Armed bandit (MAB) problems. The setting is that of an MAB problem where the reward distribution of each arm consists of a stochastic component as well as a strategic component. Many existing MAB mechanisms use upper confidence bound (UCB) based algorithms for learning the parameters of the reward distribution. The randomized nature of Thompson sampling introduces certain unique, non-Trivial challenges for mechanism design, which we address in this paper through a rigorous regret analysis. We first propose a MAB mechanism with deterministic payment rule, namely, TSM-D. We show that in TSM- D, the variance of agent utilities asymptotically approaches zero. However, the game theoretic properties satisfied by TSM-D (incentive compatibility and individual rationality with high probability) are rather weak. As our main contribution, we then propose the mechanism TSM-R, with randomized payment rule, and prove that TSM-R satisfies appropriate, adequate notions of incentive compatibility and individual rationality. For TSM-R, we also establish a theoretical upper bound on the variance in utilities of the agents. We further show, using simulations, that the variance in social welfare incurred by TSM-D or TSM-R is much lower when compared to that of existing UCB based mechanisms. We believe this paper establishes Thompson sampling as an attractive approach to be used in MAB mechanism design. © Copyright 2017, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All Rights Reserved.
About the journal
JournalProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
ISSN15488403