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.
Original language | English (US) |
---|---|
Article number | 6774467 |
Pages (from-to) | 544-571 |
Number of pages | 28 |
Journal | Proceedings of the IEEE |
Volume | 102 |
Issue number | 4 |
DOIs | |
State | Published - Apr 2014 |
Externally published | Yes |
Keywords
- Adaptive control
- human decision making
- machine learning
- multiarmed bandit
ASJC Scopus subject areas
- General Computer Science
- Electrical and Electronic Engineering