Modeling Human Decision-making in Generalized Gaussian Multi-armed Bandits
Authors:
Preprint
Abstract
We develop plausible human decision-making models in three multi-armed bandit problems, namely, the standard multi-armed bandit problem, the multi-armed bandit problem with transition costs, and the multi-armed bandit problem on graphs. We focus on the case of Gaussian rewards and study these problems in a Bayesian setting. We develop the upper credible limit (UCL) algorithm for the standard multi-armed bandit problem, show that it achieves a logarithmic cumulative expected regret, and draw several connections between the proposed algorithm and human decision-making behavior. We model the prior knowledge of the human through the prior reward distribution in Bayesian inference, and elucidate the role of priors and the correlation structure among arms in the decision-making performance. We present empirical data from human experiments and show that human performance is efficiently captured by the proposed UCL algorithm with appropriate parameters. In the context of the multi-armed bandit problem with transition costs, and the multi-armed bandit problem on graphs, we extend the UCL algorithm to the block UCL algorithm and the graphical block UCL algorithm, respectively. We show that these algorithms also achieve a logarithmic cumulative expected regret and require a sub-logarithmic expected number of transitions among arms. We further illustrate the performance of these algorithms with numerical examples. Finally, we propose a formal framework for incorporating proposed human decision-making models in the design of mixed human-automata teams.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Psychological models of human and optimal performance in bandit problemsCognitive Systems Research, 2011
- Multi‐Armed Bandit Allocation Indices2011
- Amazon's Mechanical Turk: A new source of inexpensive, yet high-quality, data?2011
- A Human-Robot Collaborative Reinforcement Learning AlgorithmJournal of Intelligent & Robotic Systems, 2010
- Human–robot communication for collaborative decision making — A probabilistic approachRobotics and Autonomous Systems, 2010
- Regret bounds for sleeping experts and banditsMachine Learning, 2010
- A Bayesian analysis of human decision-making on bandit problemsJournal of Mathematical Psychology, 2009
- Finite-time Analysis of the Multiarmed Bandit ProblemMachine Learning, 2002
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Test of optimal sampling by foraging great titsNature, 1978