Modeling Human Decision Making in Generalized Gaussian Multiarmed Bandits
- 17 March 2014
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE
- Vol. 102 (4) , 544-571
Abstract
In this paper, we present a formal model of human decision making in explore-exploit tasks using the context of multiarmed bandit problems, where the decision maker must choose among multiple options with uncertain rewards. We address the standard multiarmed bandit problem, the multiarmed bandit problem with transition costs, and the multiarmed bandit problem on graphs. We focus on the case of Gaussian rewards in a setting where the decision maker uses Bayesian inference to estimate the reward values. We model the decision maker's prior knowledge with the Bayesian prior on the mean reward. We develop the upper-credible-limit (UCL) algorithm for the standard multiarmed bandit problem and show that this deterministic algorithm achieves logarithmic cumulative expected regret, which is optimal performance for uninformative priors. We show how good priors and good assumptions on the correlation structure among arms can greatly enhance decision-making performance, even over short time horizons. We extend to the stochastic UCL algorithm and draw several connections to human decision-making behavior. We present empirical data from human experiments and show that human performance is efficiently captured by the stochastic UCL algorithm with appropriate parameters. For the multiarmed bandit problem with transition costs and the multiarmed bandit problem on graphs, we generalize the UCL algorithm to the block UCL algorithm and the graphical block UCL algorithm, respectively. We show that these algorithms also achieve logarithmic cumulative expected regret and require a sublogarithmic expected number of transitions among arms. We further illustrate the performance of these algorithms with numerical examples.Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- The anatomy of choice: active inference and agencyFrontiers in Human Neuroscience, 2013
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends in Machine Learning, 2012
- Amazon's Mechanical TurkPerspectives on Psychological Science, 2011
- A Bayesian analysis of human decision-making on bandit problemsJournal of Mathematical Psychology, 2009
- Should I stay or should I go? How the human brain manages the trade-off between exploitation and explorationPhilosophical Transactions of the Royal Society B: Biological Sciences, 2007
- A survey on the bandit problem with switching costsDe Economist, 2004
- A Sequential Study of Migration and Job SearchJournal of Labor Economics, 1987
- Optimization by Simulated AnnealingScience, 1983
- Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given MatrixThe Annals of Mathematical Statistics, 1950
- On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two SamplesBiometrika, 1933