  We present a formal model of human decision-making in explore-exploit tasks
using the context of multi-armed bandit problems, where the decision-maker must
choose among multiple options with uncertain rewards. We address 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 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 multi-armed 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 multi-armed bandit problem with transition
costs and the multi-armed 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 sub-logarithmic expected number of transitions
among arms. We further illustrate the performance of these algorithms with
numerical examples. NB: Appendix G included in this version details minor
modifications that correct for an oversight in the previously-published proofs.
The remainder of the text reflects the published work.
