Modeling Human Decision-making in Generalized Gaussian Multi-armed Bandits

I Introduction

Imagine the following scenario: you are reading the menu in a new restaurant, deciding which dish to order. Some of the dishes are familiar to you, while others are completely new. Which dish do you ultimately order: a familiar one that you are fairly certain to enjoy, or an unfamiliar one that looks interesting but you may dislike?

Your answer will depend on a multitude of factors, including your mood that day (Do you feel adventurous or conservative?), your knowledge of the restaurant and its cuisine (Do you know little about African cuisine, and everything looks new to you?), and the number of future decisions the outcome is likely to influence (Is this a restaurant in a foreign city you are unlikely to visit again, or is it one that has newly opened close to home, where you may return many times?). This scenario encapsulates many of the difficulties faced by a decision-making agent interacting with his/her environment, e.g. the role of prior knowledge and the number of future choices (time horizon).

The problem of learning the optimal way to interact with an uncertain environment is common to a variety of areas of study in engineering such as adaptive control and reinforcement learning . Fundamental to these problems is the tradeoff between exploration (collecting more information to reduce uncertainty) and exploitation (using the current information to maximize the immediate reward). Formally, such problems are often formulated as Markov Decision Processes (MDPs). MDPs are decision problems in which the decision-making agent is required to make a sequence of choices along a process evolving in time . The theory of dynamic programming , provides methods to find optimal solutions to generic MDPs, but is subject to the so-called curse of dimensionality , where the size of the problem often grows exponentially in the number of states.

The curse of dimensionality makes finding the optimal solution difficult, and in general intractable for finite-horizon problems of any significant size. Many engineering solutions of MDPs consider the infinite-horizon case, i.e., the limit where the agent will be required to make an infinite sequence of decisions. In this case, the problem simplifies significantly and a variety of reinforcement learning methods can be used to converge to the optimal solution, for example . However, these methods only converge to the optimal solution asymptotically at a rate that is difficult to analyze. The UCRL algorithm addressed this issue by deriving a heuristic-based reinforcement learning algorithm with a provable learning rate.

However, the infinite-horizon limit may be inappropriate for finite-horizon tasks. In particular, optimal solutions to the finite-horizon problem may be strongly dependent on the task horizon. Consider again our restaurant scenario. If the decision is a one-off, we are likely to be conservative, since selecting an unfamiliar option is risky and even if we choose an unfamiliar dish and like it, we will have no further opportunity to use the information in the same context. However, if we are likely to return to the restaurant many times in the future, discovering new dishes we enjoy is valuable.

Although the finite-horizon problem may be intractable to computational analysis, humans are confronted with it all the time, as evidenced by our restaurant example. The fact that they are able to find efficient solutions quickly with inherently limited computational power suggests that humans employ relatively sophisticated heuristics for solving these problems. Elucidating these heuristics is of interest both from a psychological point of view where they may help us understand human cognitive control and from an engineering point of view where they may lead to development of improved algorithms to solve MDPs . In this paper, we seek to elucidate the behavioral heuristics at play with a model that is both mathematically rigorous and computationally tractable.

Multi-armed bandit problems constitute a class of MDPs that is well suited to our goal of connecting biologically plausible heuristics with mathematically rigorous algorithms. In the mathematical context, multi-armed bandit problems have been studied in both the infinite-horizon and finite-horizon cases. There is a well-known optimal solution to the infinite-horizon problem . For the finite-horizon problem, the policies are designed to match the best possible performance established in . In the biological context, the decision-making behavior and performance of both animals and humans have been studied using the multi-armed bandit framework.

In a multi-armed bandit problem, a decision-maker allocates a single resource by sequentially choosing one among a set of competing alternative options called arms. In the so-called stationary multi-armed bandit problem, a decision-maker at each discrete time instant chooses an arm and collects a reward drawn from an unknown stationary probability distribution associated with the selected arm. The objective of the decision-maker is to maximize the total reward aggregated over the sequential allocation process. We will refer to this as the standard multi-armed bandit problem, and we will consider variations that add transition costs or spatial unavailability of arms. A classical example of a standard multi-armed bandit problem is the evaluation of clinical trials with medical patients described in . The decision-maker is a doctor and the options are different treatments with unknown effectiveness for a given disease. Given patients that arrive and get treated sequentially, the objective for the doctor is to maximize the number of cured patients, using information gained from successive outcomes.

Multi-armed bandit problems capture the fundamental exploration-exploitation tradeoff. Indeed, they model a wide variety of real-world decision-making scenarios including those associated with foraging and search in an uncertain environment. The rigorous examination in the present paper of the heuristics that humans use in multi-armed bandit tasks can help in understanding and enhancing both natural and engineered strategies and performance in these kinds of tasks. For example, a trained human operator can quickly learn the relevant features of a new environment, and an efficient model for human decision-making in a multi-armed bandit task may facilitate a means to learn a trained operator’s task-specific knowledge for use in an autonomous decision-making algorithm. Likewise, such a model may help in detecting weaknesses in a human operator’s strategy and deriving computational means to augment human performance.

Multi-armed bandit problems became popular following the seminal paper by Robbins and found application in diverse areas including controls, robotics, machine learning, economics, ecology, and operational research . For example, in ecology the multi-armed bandit problem was used to study the foraging behavior of birds in an unknown environment . The authors showed that the optimal policy for the two-armed bandit problem captures well the observed foraging behavior of birds. Given the limited computational capacity of birds, it is likely they use simple heuristics to achieve near-optimal performance. The development of simple heuristics in this and other contexts has spawned a wide literature.

Gittins studied the infinite-horizon multi-armed bandit problem and developed a dynamic allocation index (Gittins’ index) for each arm. He showed that selecting an arm with the highest index at the given time results in the optimal policy. The dynamic allocation index, while a powerful idea, suffers from two drawbacks: (i) it is hard to compute, and (ii) it does not provide insight into the nature of the optimal policies.

Much recent work on multi-armed bandit problems focuses on a quantity termed cumulative expected regret. The cumulative expected regret of a sequence of decisions is simply the cumulative difference between the expected reward of the options chosen and the maximum reward possible. In this sense, expected regret plays the same role as expected value in standard reinforcement learning schemes: maximizing expected value is equivalent to minimizing cumulative expected regret. Note that this definition of regret is in the sense of an omniscient being who is aware of the expected values of all options, rather than in the sense of an agent playing the game. As such, it is not a quantity of direct psychological relevance but rather an analytical tool that allows one to characterize performance.

In a ground-breaking work, Lai and Robbins established a logarithmic lower bound on the expected number of times a sub-optimal arm needs to be sampled by an optimal policy, thereby showing that cumulative expected regret is bounded below by a logarithmic function of time. Their work established the best possible performance of any solution to the standard multi-armed bandit problem. They also developed an algorithm based on an upper confidence bound on estimated reward and showed that this algorithm achieves the performance bound asymptotically. In the following, we use the phrase logarithmic regret to refer to cumulative expected regret being bounded above by a logarithmic function of time, i.e., having the same order of growth rate as the optimal solution. The calculation of the upper confidence bounds in involves tedious computations. Agarwal simplified these computations to develop sample mean-based upper confidence bounds, and showed that the policies in with these upper confidence bounds achieve logarithmic regret asymptotically.

In the context of bounded multi-armed bandits, i.e., multi-armed bandits in which the reward is sampled from a distribution with a bounded support, Auer et al. developed upper confidence bound-based algorithms that achieve logarithmic regret uniformly in time; see for an extensive survey of upper confidence bound-based algorithms. Audibert et al. considered upper confidence bound-based algorithms that take into account the empirical variance of the various arms. In a related work, Cesa-Bianchi et al. analyzed a Boltzman allocation rule for bounded multi-armed bandit problems. Garivier et al. studied the KL-UCB algorithm, which uses upper confidence bounds based on the Kullback-Leibler divergence, and advocated its use in multi-armed bandit problems where the rewards are distributed according to a known exponential family.

The works cited above adopt a frequentist perspective, but a number of researchers have also considered MDPs and multi-armed bandit problems from a Bayesian perspective. Dearden et al. studied general MDPs and showed that a Bayesian approach can substantially improve performance in some cases. Recently, Srinivas et al. developed asymptotically optimal upper confidence bound-based algorithms for Gaussian process optimization. Agrawal et al. proved that a Bayesian algorithm known as Thompson Sampling is near-optimal for binary bandits with a uniform prior. Kauffman et al. developed a generic Bayesian upper confidence bound-based algorithm and established its optimality for binary bandits with a uniform prior. In the present paper we develop a similar Bayesian upper confidence bound-based algorithm for Gaussian multi-armed bandit problems and show that it achieves logarithmic regret for uninformative priors uniformly in time.

Some variations of these multi-armed bandit problems have been studied as well. Agarwal et al. studied multi-armed bandit problems with transition costs, i.e., the multi-armed bandit problems in which a certain penalty is imposed each time the decision-maker switches from the currently selected arm. To address this problem, they developed an asymptotically optimal block allocation algorithm. Banks and Sundaram show that, in general, it is not possible to define dynamic allocation indices (Gittins’ indices) which lead to an optimal solution of the multi-armed bandit problem with switching costs. However, if the cost to switch to an arm from any other arm is a stationary random variable, then such indices exist. Asawa and Teneketzis characterize qualitative properties of the optimal solution to the multi-armed bandit problem with switching costs, and establish sufficient conditions for the optimality of limited lookahead based techniques. A survey of multi-armed bandit problems with switching costs is presented in . In the present paper, we consider Gaussian multi-armed bandit problems with transition costs and develop a block allocation algorithm that achieves logarithmic regret for uninformative priors uniformly in time. Our block allocation scheme is similar to the scheme in ; however, our scheme incurs a smaller expected cumulative transition cost than the scheme in . Moreover, an asymptotic analysis is considered in , while our results hold uniformly in time.

Kleinberg et al. considered multi-armed bandit problems in which arms are not all available for selection at each time (sleeping experts) and analyzed the performance of upper confidence bound-based algorithms. In contrast to the temporal unavailability of arms in , we consider a spatial unavailability of arms. In particular, we propose a novel multi-armed bandit problem, namely, the graphical multi-armed bandit problem in which only a subset of the arms can be selected at the next allocation instance given the currently selected arm. We develop a block allocation algorithm for such problems that achieves logarithmic regret for uninformative priors uniformly in time.

Human decision-making in multi-armed bandit problems has also been studied in the cognitive psychology literature. Cohen et al. surveyed the exploration-exploitation tradeoff in humans and animals and discussed the mechanisms in the brain that mediate this tradeoff. Acuña et al. studied human decision-making in multi-armed bandits from a Bayesian perspective. They modeled the human subject’s prior knowledge about the reward structure using conjugate priors to the reward distribution. They concluded that a policy using Gittins’ index, computed from approximate Bayesian inference based on limited memory and finite step look-ahead, captures the empirical behavior in certain multi-armed bandit tasks. In a subsequent work , they showed that a critical feature of human decision-making in multi-armed bandit problems is structural learning, i.e., humans learn the correlation structure among different arms.

Steyvers et al. considered Bayesian models for multi-armed bandits parametrized by human subjects’ assumptions about reward distributions and observed that there are individual differences that determine the extent to which people use optimal models rather than simple heuristics. In a subsequent work, Lee et al. considered latent models in which there is a latent mental state that determines if the human subject should explore or exploit. Zhang et al. considered multi-armed bandits with Bernoulli rewards and concluded that, among the models considered, the knowledge gradient algorithm best captures the trial-by-trial performance of human subjects.

Wilson et al. studied human performance in two-armed bandit problems and showed that at each arm selection instance the decision is based on a linear combination of the estimate of the mean reward of each arm and an ambiguity bonus that depends on the value of the information from that arm. Tomlin et al. studied human performance on multi-armed bandits that are located on a spatial grid; at each arm selection instance, the decision-maker can only select the current arm or one of the neighboring arms.

In this paper, we study multi-armed bandits with Gaussian rewards in a Bayesian setting, and we develop upper credible limit (UCL)-based algorithms that achieve efficient performance. We propose a deterministic UCL algorithm and a stochastic UCL algorithm for the standard multi-armed bandit problem. We propose a block UCL algorithm and a graphical block UCL algorithm for the multi-armed bandit problem with transitions costs and the multi-armed problem on graphs, respectively. We analyze the proposed algorithms in terms of the cumulative expected regret, i.e., the cumulative difference between the expected received reward and the maximum expected reward that could have been received. We compare human performance in multi-armed bandit tasks with the performance of the proposed stochastic UCL algorithm and show that the algorithm with the right choice of parameters efficiently models human decision-making performance. The major contributions of this work are fourfold.

First, we develop and analyze the deterministic UCL algorithm for multi-armed bandits with Gaussian rewards. We derive a novel upper bound on the inverse cumulative distribution function for the standard Gaussian distribution, and we use it to show that for an uninformative prior on the rewards, the proposed algorithm achieves logarithmic regret. To the best of our knowledge, this is the first confidence bound-based algorithm that provably achieves logarithmic cumulative expected regret uniformly in time for multi-armed bandits with Gaussian rewards.

We further define a quality of priors on rewards and show that for small values of this quality, i.e., good priors, the proposed algorithm achieves logarithmic regret uniformly in time. Furthermore, for good priors with small variance, a slight modification of the algorithm yields sub-logarithmic regret uniformly in time. Sub-logarithmic refers to a rate of expected regret that is even slower than logarithmic, and thus performance is better than with uninformative priors. For large values of the quality, i.e., bad priors, the proposed algorithm can yield performance significantly worse than with uninformative priors. Our analysis also highlights the impact of the correlation structure among the rewards from different arms on the performance of the algorithm as well as the performance advantage when the prior includes a good model of the correlation structure.

Second, to capture the inherent noise in human decision-making, we develop the stochastic UCL algorithm, a stochastic arm selection version of the deterministic UCL algorithm. We model the stochastic arm selection using softmax arm selection , and show that there exists a feedback law for the cooling rate in the softmax function such that for an uninformative prior the stochastic arm selection policy achieves logarithmic regret uniformly in time.

Third, we compare the stochastic UCL algorithm with the data obtained from our human behavioral experiments. We show that the observed empirical behaviors can be reconstructed by varying only a few parameters in the algorithm.

Fourth, we study the multi-armed bandit problem with transition costs in which a stationary random cost is incurred each time an arm other than the current arm is selected. We also study the graphical multi-armed bandit problem in which the arms are located at the vertices of a graph and only the current arm and its neighbors can be selected at each time. For these multi-armed bandit problems, we extend the deterministic UCL algorithm to block allocation algorithms that for uninformative priors achieve logarithmic regret uniformly in time.

In summary, the main contribution of this work is to provide a formal algorithmic model (the UCL algorithms) of choice behavior in the exploration-exploitation tradeoff using the context of the multi-arm bandit problem. In relation to cognitive dynamics, we expect that this model could be used to explain observed choice behavior and thereby quantify the underlying computational anatomy in terms of key model parameters. The fitting of such models of choice behavior to empirical performance is now standard in cognitive neuroscience. We illustrate the potential of our model to categorize individuals in terms of a small number of model parameters by showing that the stochastic UCL algorithm can reproduce canonical classes of performance observed in large numbers of subjects.

The remainder of the paper is organized as follows. The standard multi-armed bandit problem is described in Section II. The salient features of human decision-making in bandit tasks are discussed in Section III. In Section IV we propose and analyze the regret of the deterministic UCL and stochastic UCL algorithms. In Section V we describe an experiment with human participants and a spatially-embedded multi-armed bandit task. We show that human performance in that task tends to fall into one of several categories, and we demonstrate that the stochastic UCL algorithm can capture these categories with a small number of parameters. We consider an extension of the multi-armed bandit problem to include transition costs and describe and analyze the block UCL algorithm in Section VI. In Section VII we consider an extension to the graphical multi-armed bandit problem, and we propose and analyze the graphical block UCL algorithm. Finally, in Section VIII we conclude and present avenues for future work.

II A review of multi-armed bandit problems

Consider a set of $N$ options, termed arms in analogy with the lever of a slot machine. A single-levered slot machine is termed a one-armed bandit, so the case of $N$ options is often called an $N$-armed bandit. The $N$-armed bandit problem refers to the choice among the $N$ options that a decision-making agent should make to maximize the cumulative reward.

where $n_{i}^{T}$ is the total number of times option $i$ has been chosen until time $T$ and $\Delta_{i}=m_{i^{*}}-m_{i}$ is the expected regret due to picking arm $i$ instead of arm $i^{*}$. Note that in order to minimize the cumulative expected regret, it suffices to minimize the expected number of times any suboptimal option $i\in\{1,\dots,N\}\setminus\{i^{*}\}$ is selected.

The multi-armed bandit problem is a canonical example of the exploration-exploitation tradeoff common to many problems in controls and machine learning. In this context, at time $t$, exploitation refers to picking arm $i_{t}$ that is estimated to have the highest mean at time $t$, and exploration refers to picking any other arm. A successful policy balances the exploration-exploitation tradeoff by exploring enough to learn which arm is most rewarding and exploiting that information by picking the best arm often.

Lai and Robbins showed that, for any algorithm solving the multi-armed bandit problem, the expected number of times a suboptimal arm is selected is at least logarithmic in time, i.e.,

II-B The Gaussian multi-armed bandit task

For the Gaussian multi-armed bandit problem considered in this paper, the reward density $p_{i}$ is Gaussian with mean $m_{i}$ and variance $\sigma_{s}^{2}$. The variance $\sigma_{s}^{2}$ is assumed known, e.g., from previous observations or known characteristics of the reward generation process. Therefore

The insight from (3) is that for a fixed value of $\sigma_{s}$, a suboptimal arm $i$ with higher $\Delta_{i}$ is easier to identify, and thus chosen less often, since it yields a lower average reward. Conversely, for a fixed value of $\Delta_{i}$, higher values of $\sigma_{s}$ make the observed rewards more variable, and thus it is more difficult to distinguish the optimal arm $i^{*}$ from the suboptimal ones.

II-C The Upper Confidence Bound algorithms

For multi-armed bandit problems with bounded rewards, Auer et al. developed upper confidence bound-based algorithms, known as the UCB1 algorithm and its variants, that achieve logarithmic regret uniformly in time. UCB1 is a heuristic-based algorithm that at each time $t$ computes a heuristic value $Q_{i}^{t}$ for each option $i$. This value provides an upper bound for the expected reward to be gained by selecting that option:

where $\bar{m}_{i}^{t}$ is the empirical mean reward and $C_{i}^{t}$ is a measure of uncertainty in the reward of arm $i$ at time $t$. The UCB1 algorithm picks the option $i_{t}$ that maximizes $Q_{i}^{t}$. Figure 1 depicts this logic: the confidence intervals represent uncertainty in the algorithm’s estimate of the true value of $m_{i}$ for each option, and the algorithm optimistically chooses the option with the highest upper confidence bound. This is an example of a general heuristic known in the bandit literature as optimism in the face of uncertainty . The idea is that one should formulate the set of possible environments that are consistent with the observed data, then act as if the true environment were the most favorable one in that set.

Auer et al. showed that for an appropriate choice of the uncertainty term $C_{i}^{t}$, the UCB1 algorithm achieves logarithmic regret uniformly in time, albeit with a larger leading constant than the optimal one (1). They also provided a slightly more complicated policy, termed UCB2, that brings the factor multiplying the logarithmic term arbitrarily close to that of (1). Their analysis relies on Chernoff-Hoeffding bounds which apply to probability distributions with bounded support.

They also considered the case of multi-armed bandits with Gaussian rewards, where both the mean ($m_{i}$ in our notation) and sample variance ($\sigma_{s}^{2}$) are unknown. In this case they constructed an algorithm, termed UCB1-Normal, that achieves logarithmic regret. Their analysis of the regret in this case cannot appeal to Chernoff-Hoeffding bounds because the reward distribution has unbounded support. Instead their analysis relies on certain bounds on the tails of the $\chi^{2}$ and the Student t-distribution that they could only verify numerically. Our work improves on their result in the case $\sigma_{s}^{2}$ is known by constructing a UCB-like algorithm that provably achieves logarithmic regret. The proof relies on new tight bounds on the tails of the Gaussian distribution that will be stated in Theorem 1.

II-D The Bayes-UCB algorithm

UCB algorithms rely on a frequentist estimator $\bar{m}_{i}^{t}$ of $m_{i}$ and therefore must sample each arm at least once in an initialization step, which requires a sufficiently long horizon, i.e., $N<T$. Bayesian estimators allow the integration of prior beliefs into the decision process. This enables a Bayesian UCB algorithm to treat the case $N>T$ as well as to capture the initial beliefs of an agent, informed perhaps through prior experience. Kauffman et al. considered the $N$-armed bandit problem from a Bayesian perspective and proposed the quantile function of the posterior reward distribution as the heuristic function (4).

i.e., $F^{-1}(p)$ inverts the cdf to provide an upper bound for the value of the random variable $X\sim f(x)$:

In order to be increasingly sure of choosing the optimal arm as time goes on, sets $p=1-\alpha_{t}$ as a function of time with $\alpha_{t}=1/(t(\log T)^{c})$, so that $1-p$ is of order $1/t$. The authors termed the resulting algorithm Bayes-UCB. In the case that the rewards are Bernoulli distributed, they proved that with $c\geq 5$ Bayes-UCB achieves the bound (1) for uniform (uninformative) priors.

The choice of $1/t$ as the functional form for $\alpha_{t}$ can be motivated as follows. Roughly speaking, $\alpha_{t}$ is the probability of making an error (i.e., choosing a suboptimal arm) at time $t$. If a suboptimal arm is chosen with probability $1/t$, then the expected number of times it is chosen until time $T$ will follow the integral of this rate, which is $\sum_{1}^{T}1/t\approx\log T$, yielding a logarithmic functional form.

III Features of human decision-making in multi-armed bandit tasks

As discussed in the introduction, human decision-making in the multi-armed bandit task has been the subject of numerous studies in the cognitive psychology literature. We list the five salient features of human decision-making in this literature that we wish to capture with our model.

(i) Familiarity with the environment: Familiarity with the environment and its structure plays a critical role in human decision-making . In the context of multi-armed bandit tasks, familiarity with the environment translates to prior knowledge about the mean rewards from each arm.

(ii) Ambiguity bonus: Wilson et al. showed that the decision at time $t$ is based on a linear combination of the estimate of the mean reward of each arm and an ambiguity bonus that captures the value of information from that arm. In the context of UCB and related algorithms, the ambiguity bonus can be interpreted similarly to the $C_{i}^{t}$ term of (4) that defines the size of the upper bound on the estimated reward.

(iii) Stochasticity: Human decision-making is inherently noisy . This is possibly due to inherent limitations in human computational capacity, or it could be the signature of noise being used as a cheap, general-purpose problem-solving algorithm. In the context of algorithms for solving the multi-armed bandit problem, this can be interpreted as picking arm $i_{t}$ at time $t$ using a stochastic arm selection strategy rather than a deterministic one.

(iv) Finite-horizon effects: Both the level of decision noise and the exploration-exploitation tradeoff are sensitive to the time horizon $T$ of the bandit task . This is a sensible feature to have, as shorter time horizons mean less time to take advantage of information gained by exploration, therefore biasing the optimal policy towards exploitation. The fact that both decision noise and the exploration-exploitation tradeoff (as represented by the ambiguity bonus) are affected by the time horizon suggests that they are both working as mechanisms for exploration, as investigated in . In the context of algorithms, this means that the uncertainty term $C_{i}^{t}$ and the stochastic arm selection scheme should be functions of the horizon $T$.

(v) Environmental structure effects: Acuña et al. showed that an important aspect of human learning in multi-armed bandit tasks is structural learning, i.e., humans learn the correlation structure among different arms, and utilize it to improve their decision.

In the following, we develop a plausible model for human decision-making that captures these features. Feature (i) of human decision-making is captured through priors on the mean rewards from the arms. The introduction of priors in the decision-making process suggests that non-Bayesian upper confidence bound algorithms cannot be used, and therefore, we focus on Bayesian upper confidence bound (upper credible limit) algorithms . Feature (ii) of human decision-making is captured by making decisions based on a metric that comprises two components, namely, the estimate of the mean reward from each arm, and the width of a credible set. It is well known that the width of a credible set is a good measure of the uncertainty in the estimate of the reward. Feature (iii) of human decision-making is captured by introducing a stochastic arm selection strategy in place of the standard deterministic arm selection strategy . In the spirit of Kauffman et al. , we choose the credibility parameter $\alpha_{t}$ as a function of the horizon length to capture feature (iv) of human decision-making. Feature (v) is captured through the correlation structure of the prior used for the Bayesian estimation. For example, if the arms of the bandit are spatially embedded, it is natural to think of a covariance structure defined by $\Sigma_{ij}=\sigma_{0}^{2}\exp(-|x_{i}-x_{j}|/\lambda)$, where $x_{i}$ is the location of arm $i$ and $\lambda\geq 0$ is the correlation length scale parameter that encodes the spatial smoothness of the rewards.

IV The Upper Credible Limit (UCL) Algorithms for Gaussian Multi-armed Bandits

In this section, we construct a Bayesian UCB algorithm that captures the features of human decision-making described above. We begin with the case of deterministic decision-making and show that for an uninformative prior the resulting algorithm achieves logarithmic regret. We then extend the algorithm to the case of stochastic decision-making using a Boltzmann (or softmax) decision rule, and show that there exists a feedback rule for the temperature of the Boltzmann distribution such that the stochastic algorithm achieves logarithmic regret. In both cases we first consider uncorrelated priors and then extend to correlated priors.

Let the prior on the mean reward at arm $i$ be a Gaussian random variable with mean $\mu_{i}^{0}$ and variance $\sigma_{0}^{2}$. We are particularly interested in the case of an uninformative prior, i.e., $\sigma_{0}^{2}\to+\infty$. Let the number of times arm $i$ has been selected until time $t$ be denoted by $n_{i}^{t}$. Let the empirical mean of the rewards from arm $i$ until time $t$ be $\bar{m}_{i}^{t}$. Conditioned on the number of visits $n_{i}^{t}$ to arm $i$ and the empirical mean $\bar{m}_{i}^{t}$, the mean reward at arm $i$ at time $t$ is a Gaussian random variable ($M_{i}$) with mean and variance

respectively, where $\delta^{2}=\sigma_{s}^{2}/\sigma_{0}^{2}$. Moreover,

We now propose the UCL algorithm for the Gaussian multi-armed bandit problem. At each decision instance $t\in\{1,\dots,T\}$, the UCL algorithm selects an arm with the maximum value of the upper limit of the smallest $(1-1/Kt)$-credible interval, i.e., it selects an arm $i_{t}=\text{argmax}\{Q_{i}^{t}\;|\;i\in\{1,\dots,N\}\}$, where

It is known that an efficient policy to maximize the total information gained over sequential sampling of options is to pick the option with highest variance at each time. Thus, $Q_{i}^{t}$ is the weighted sum of the expected gain in the total reward (exploitation), and the gain in the total information about arms (exploration), if arm $i$ is picked at time $t$.

IV-B Regret analysis of the deterministic UCL Algorithm

In this section, we analyze the performance of the UCL algorithm. We first derive bounds on the inverse cumulative distribution function for the standard Gaussian random variable and then utilize it to derive upper bounds on the cumulative expected regret for the UCL algorithm. We state the following theorem about bounds on the inverse Gaussian cdf.

The following bounds hold for the inverse cumulative distribution function of the standard Gaussian random variable for each $\alpha\in(0,1/\sqrt{2\pi})$, and any $\beta\geq 1.02$:

The bounds in equations (6) and (7) were conjectured by Fan without the factor $\beta$. In fact, it can be numerically verified that without the factor $\beta$, the conjectured upper bound is incorrect. We present a visual depiction of the tightness of the derived bounds in Figure 4.

We now analyze the performance of the UCL algorithm. We define $\{R^{\textup{UCL}}_{t}\}_{t\in\{1,\dots,T\}}$ as the sequence of expected regret for the UCL algorithm. The UCL algorithm achieves logarithmic regret uniformly in time as formalized in the following theorem.

The following statements hold for the Gaussian multi-armed bandit problem and the deterministic UCL algorithm with uncorrelated uninformative prior and $K=\sqrt{2\pi e}$:

the expected number of times a suboptimal arm $i$ is chosen until time $T$ satisfies

the cumulative expected regret until time $T$ satisfies

When the deterministic UCL algorithm is used with an uncorrelated uninformative prior, Theorem 2 guarantees that the algorithm incurs logarithmic regret uniformly in horizon length $T$. However, for small horizon lengths, the upper bound on the regret can be lower bounded by a super-logarithmic curve. Accordingly, in practice, the cumulative expected regret curve may appear super-logarithmic for short time horizons. For example, for horizon $T$ less than the number of arms $N$, the cumulative expected regret of the deterministic UCL algorithm grows at most linearly with the horizon length. $\square$

In view of the bounds in Theorem 1, for an uninformative prior, the $(1-1/Kt)$-upper credible limit obeys

This upper bound is similar to the one in UCB1, which sets

For an uninformative prior, i.e., very large variance $\sigma_{0}^{2}$, we established in Theorem 2 that the deterministic UCL algorithm achieves logarithmic regret uniformly in time. For informative priors, the cumulative expected regret depends on the quality of the prior. The quality of a prior on the rewards can be captured by the metric $\zeta:=\max\{|m_{i}-\mu_{i}^{0}|/\sigma_{0}\;|\;i\in\{1,\dots,N\}\}$. A good prior corresponds to small values of $\zeta$, while a bad prior corresponds to large values of $\zeta$. In other words, a good prior is one that has (i) mean close to the true mean reward, or (ii) a large variance. Intuitively, a good prior either has a fairly accurate estimate of the mean reward, or has low confidence about its estimate of the mean reward. For a good prior, the parameter $K$ can be tuned such that

For a good prior with a small variance, even uniform sub-logarithmic regret can be achieved. Specifically, if the variable $Q_{i}^{t}$ in Algorithm 1 is set to $Q_{i}^{t}=m_{i}^{t}+\sigma_{i}^{t}\Phi^{-1}(1-1/Kt^{2})$, then an analysis similar to Theorem 2 yields an upper bound on the cumulative expected regret that is dominated by (i) a sub-logarithmic term for good priors with small variance, and (ii) a logarithmic term for uninformative priors with a higher constant in front than the constant in Theorem 2. Notice that such good priors may correspond to human operators who have previous training in the task. $\square$

IV-C The stochastic UCL algorithm with uncorrelated priors

To capture the inherent stochastic nature of human decision-making, we consider the UCL algorithm with stochastic arm selection. Stochasticity has been used as a generic optimization mechanism that does not require information about the objective function. For example, simulated annealing is a global optimization method that attempts to break out of local optima by sampling locations near the currently selected optimum and accepting locations with worse objective values with a probability that decreases in time. By analogy with physical annealing processes, the probabilities are chosen from a Boltzmann distribution with a dynamic temperature parameter that decreases in time, gradually making the optimization more deterministic. An important problem in the design of simulated annealing algorithms is the choice of the temperature parameter, also known as a cooling schedule.

Choosing a good cooling schedule is equivalent to solving the explore-exploit problem in the context of simulated annealing, since the temperature parameter balances exploration and exploitation by tuning the amount of stochasticity (exploration) in the algorithm. In their classic work, Mitra et al. found cooling schedules that maximize the rate of convergence of simulated annealing to the global optimum. In a similar way, the stochastic UCL algorithm (see Algorithm 2 in Appendix F for an explicit pseudocode implementation) extends the deterministic UCL algorithm (Algorithm 1) to the stochastic case. The stochastic UCL algorithm chooses an arm at time $t$ using a Boltzmann distribution with temperature $\upsilon_{t}$, so the probability $P_{it}$ of picking arm $i$ at time $t$ is given by

In the case $\upsilon_{t}\to 0^{+}$ this scheme chooses $i_{t}=\operatorname{argmax}\{Q_{i}^{t}\;|\;i\in\{1,\dots,N\}\}$ and as $\upsilon_{t}$ increases the probability of selecting any other arm increases. Thus Boltzmann selection generalizes the maximum operation and is sometimes known as the soft maximum (or softmax) rule.

The temperature parameter might be chosen constant, i.e., $\upsilon_{t}=\upsilon$. In this case the performance of the stochastic UCL algorithm can be made arbitrarily close to that of the deterministic UCL algorithm by taking the limit $\upsilon\to 0^{+}$. However, showed that good cooling schedules for simulated annealing take the form

so we investigate cooling schedules of this form. We choose $\nu$ using a feedback rule on the values of the heuristic function $Q_{i}^{t},i\in\{1,\dots,N\}$ and define the cooling schedule as

where $\Delta Q_{\min}^{t}=\min\{|Q_{i}^{t}-Q_{j}^{t}|\;|\;i,j\in\{1,\dots,N\},i\neq j\}$ is the minimum gap between the heuristic function value for any two pairs of arms. We define $\infty-\infty=0$, so that $\Delta Q_{\min}^{t}=0$ if two arms have infinite heuristic values, and define $0/0=1$.

IV-D Regret analysis of the stochastic UCL algorithm

In this section we show that for an uninformative prior, the stochastic UCL algorithm achieves efficient performance. We define $\{R^{\textup{SUCL}}_{t}\}_{t\in\{1,\dots,T\}}$ as the sequence of expected regret for the stochastic UCL algorithm. The stochastic UCL algorithm achieves logarithmic regret uniformly in time as formalized in the following theorem.

The following statements hold for the Gaussian multi-armed bandit problem and the stochastic UCL algorithm with uncorrelated uninformative prior and $K=\sqrt{2\pi e}$:

the expected number of times a suboptimal arm $i$ is chosen until time $T$ satisfies

the cumulative expected regret until time $T$ satisfies

IV-E The UCL algorithms with correlated priors

In the preceding sections, we consider the case of uncorrelated priors, i.e., the case with diagonal covariance matrix of the prior distribution for mean rewards $\Sigma_{0}=\sigma_{0}^{2}I_{N}$. However, in many cases there may be dependence among the arms that we wish to encode in the form of a non-diagonal covariance matrix. In fact, one of the main advantages a human may have in performing a bandit task is their prior experience with the dependency structure across the arms resulting in a good prior correlation structure. We show that including covariance information can improve performance and may, in some cases, lead to sub-logarithmic regret.

where $\Lambda_{t}=\Sigma_{t}^{-1}$ is the precision matrix.

The upper credible limit for each arm $i$ can be computed based on the univariate Gaussian marginal distribution of the posterior with mean $\mu_{i}^{t}$ and variance $\left(\sigma_{i}^{t}\right)^{2}=(\Sigma_{t})_{ii}$. Consider the evolution of the belief state with the diagonal (uncorrelated) prior $\Sigma_{0d}$ and compare it with the belief state based on the non-diagonal $\Sigma_{0}$ which encodes information about the correlation structure of the rewards in the off-diagonal terms. The additional information means that the inference procedure will converge more quickly than in the uncorrelated case, as seen in Theorem 8. If the assumed correlation structure correctly models the environment, then the inference will converge towards the correct values, and the performance of the UCL and stochastic UCL algorithms will be at least as good as that guaranteed by the preceding analyses in Theorems 2 and 7.

Denoting ${\sigma_{i}^{t}}^{2}=(\Sigma_{t})_{ii}$ as the posterior at time $t$ based on $\Sigma_{0}$ and ${\sigma_{id}^{t}}^{2}=(\Sigma_{td})_{ii}$ as the posterior based on $\Sigma_{0d}$, for a given sequence of chosen arms $\{i_{\tau}\}_{\tau\in\{1,\dots,T\}}$, we have that the variance of the non-diagonal estimator will be no larger than that of the diagonal one, as summarized in the following theorem:

For the inference procedure in (8), and any given sequence of selected arms $\{i_{\tau}\}_{\tau\in\{1,\dots,T\}}$, ${\sigma_{i}^{t}}^{2}\leq{\sigma_{id}^{t}}^{2}$, for any $t\in\{0,\ldots,T\}$, and for each $i\in\{1,\dots,N\}$.

We use induction. By construction, ${\sigma_{i}^{0}}^{2}={\sigma_{id}^{0}}^{2}$, so the statement is true for $t=0$. Suppose the statement holds for some $t\geq 0$ and consider the update rule for $\Sigma_{t}$. From the Sherman-Morrison formula for a rank-$1$ update , we have

We now examine the update term in detail, starting with its denominator:

so $\sigma_{s}^{2}+\boldsymbol{\phi}_{t}^{\prime}\Sigma_{t}\boldsymbol{\phi}_{t}=\sigma_{s}^{2}+(\Sigma_{t})_{i_{t}i_{t}}>0$. The numerator is the outer product of the $i_{t}$-th column of $\Sigma_{t}$ with itself, and can be expressed in index form as

Note that if $\Sigma_{t}$ is diagonal, then so is $\Sigma_{t+1}$ since the only non-zero update element will be $(\Sigma_{t})_{i_{t}i_{t}}^{2}$. Therefore, $\Sigma_{td}$ is diagonal for all $t\geq 0$.

The update of the diagonal terms of $\Sigma$ only uses the diagonal elements of the update term, so

In the case of $\Sigma_{td}$, the sum over $j$ only includes the $j=i_{t}$ element whereas with the non-diagonal prior $\Sigma_{t}$ the sum may include many additional terms. So we have

Note that the above result merely shows that the belief state converges more quickly in the case of a correlated prior, without making any claim about the correctness of this convergence. For example, consider a case where the prior belief is that two arms are perfectly correlated, i.e., the relevant block of the prior is a multiple of $\displaystyle\left(\begin{smallmatrix}1&1\\ 1&1\end{smallmatrix}\right)$, but in actuality the two arms have very different mean rewards. If the algorithm first samples the arm with lower reward, it will tend to underestimate the reward to the second arm. However, in the case of a well-chosen prior the faster convergence will allow the algorithm to more quickly disregard related sets of arms with low rewards.

V Classification of human performance in multi-armed bandit tasks

In this section, we study human data from a multi-armed bandit task and show how human performance can be classified as falling into one of several categories, which we term phenotypes. We then show that the stochastic UCL algorithm can produce performance that is analogous to the observed human performance.

In order to study human performance in multi-armed bandit tasks, we ran a spatially-embedded multi-armed bandit task through web servers at Princeton University. Human participants were recruited using Amazon’s Mechanical Turk (AMT) web-based task platform . Upon selecting the task on the AMT website, participants were directed to follow a link to a Princeton University website, where informed consent was obtained according to protocols approved by the Princeton University Institutional Review Board.

After informed consent was obtained, participants were shown instructions that told them they would be playing a simple game during which they could collect points, and that their goal was to collect the maximum number of total points in each part of the game.

Each participant was presented with a set of $N=100$ options in a $10\times 10$ grid. At each decision time $t\in\{1,\dots,T\}$, the participant made a choice by moving the cursor to one element of the grid and clicking. After each choice was made a numerical reward associated to that choice was reported on the screen. The time allowed for each choice was manipulated and allowed to take one of two values, denoted fast and slow. If the participant did not make a choice within 1.5 (fast) or 6 (slow) seconds after the prompt, then the last choice was automatically selected again. The reward was visible until the next decision was made and the new reward reported. The time allotted for the next decision began immediately upon the reporting of the new reward. Figure 5 shows the screen used in the experiment.

The dynamics of the game were also experimentally manipulated, although we focus exclusively here on the first dynamic condition. The first dynamic condition was a standard bandit task, where the participant could choose any option at each decision time, and the game would immediately sample that option. In the second and third dynamic conditions, the participant was restricted in choices and the game responded in different ways. These two conditions are beyond the scope of this paper.

Participants were first trained with three training blocks of $T=10$ choices each, one for each form of the game dynamics. Subsequently, the participants performed two task blocks of $T=90$ choices each in a balanced experimental design. For each participant, the first task had parameters randomly chosen from one of the 12 possible combinations (2 timing, 3 dynamics, 2 landscapes), and the second task was conditioned on the first so that the alternative timing was used with the alternative landscape and the dynamics chosen randomly from the two remaining alternatives. In particular, only approximately 2/3 of the participants were assigned a standard bandit task, while other subjects were assigned other dynamic conditions. The horizon $T<N$ was chosen so that prior beliefs would be important to performing the task. Each training block took 15 seconds and each task block took 135 (fast) or 540 (slow) seconds. The time between blocks was negligible, due only to network latency.

Mean rewards in the task blocks corresponded to one of two landscapes: Landscape A (Figure 6(a)) and Landscape B (Figure 6(b)). Each landscape was flat along one dimension and followed a profile along the other dimension. In the two task blocks, each participant saw each landscape once, presented in random order. Both landscapes had a mean value of 30 points and a maximum of approximately 60 points, and the rewards $r_{t}$ for choosing an option $i_{t}$ were computed as the sum of the mean reward $m_{i_{t}}$ and an integer chosen uniformly from the range $$. In the training blocks, the landscape had a mean value of zero everywhere except for a single peak of 100 points in the center. The participants were given no specific information about the value or the structure of the reward landscapes.

To incentivize the participants to make choices to maximize their cumulative reward, the participants were told that they were being paid based on the total reward they collected during the tasks. As noted above, due to the multiple manipulations, not every participant performed a standard bandit task block. Data were collected from a total of 417 participants: 326 of these participants performed one standard bandit task block each, and the remaining 91 participants performed no standard bandit task blocks.

V-B Phenotypes of observed performance

For each 90 choice standard bandit task block, we computed observed regret by subtracting the maximum mean cumulative reward from the participant’s cumulative reward, i.e.,

The definition of $\mathcal{R}(t)$ uses received rather than expected reward, so it is not identical to cumulative expected regret. However, due to the large number of individual rewards received and the small variance in rewards, the difference between the two quantities is small.

We study human performance by considering the functional form of $\mathcal{R}(t)$. Optimal performance in terms of regret corresponds to $\mathcal{R}(t)=\mathcal{C}\log t$, where $\mathcal{C}$ is the sum over $i$ of the factors in (1). The worst-case performance, corresponding to repeatedly choosing the lowest-value option, corresponds to the form $\mathcal{R}(t)=\mathcal{K}t$, where $\mathcal{K}>0$ is a constant. Other bounds in the bandit literature (e.g. ) are known to have the form $\mathcal{R}(t)=\mathcal{K}\sqrt{t}$.

To classify types of observed human performance in bandit tasks, we fit models representing these three forms to the observed regret from each task. Specifically, we fit the three models

to the data from each task and classified the behavior according to which of the models (9)–(11) best fit the data in terms of squared residuals. Model selection using this procedure is tenable given that the complexity or number of degrees of freedom of the three models is the same.

Of the 326 participants who performed a standard bandit task block, 59.2% were classified as exhibiting linear regret (model (9)), 19.3% power regret (10), and 21.5% logarithmic regret (11). This suggests that 40.8% of the participants performed well overall and 21.5% performed very well. We observed no significant correlation between performance and timing, landscape, or order (first or second) of playing the standard bandit task block.

Averaging across all tasks, mean performance was best fit by a power model with exponent $b\approx 0.9$, so participants on average achieved sub-linear regret, i.e., better than linear regret. The nontrivial number of positive performances are noteworthy given that $T<N$, i.e., a relatively short time horizon which makes the task challenging.

Averaging, conditional on the best-fit model, separates the performance of the participants into the three categories of regret performance as can be observed in Figure 7. The difference between linear and power-law performance is not statistically significant until near the task horizon at $t=90$, but log-law performance is statistically different from the other two, as seen using the confidence intervals in the figure. We therefore interpret the linear and power-law performance phenotypes as representing participants with low performance and the log-law phenotype as representing participants with high performance. Interestingly, the three models are indistinguishable for time less than sufficiently small $t\lesssim 30$. This may represent a fundamental limit to performance that depends on the complexity of the reward surface: if the surface is smooth, skilled participants can quickly find good options, corresponding to a small value of the constant $\mathcal{K}$, and thus their performance will quickly be distinguished from less skilled participants. However, if the surface is rough, identifying good options is harder and will therefore require more samples, i.e., a large value of $\mathcal{K}$, even for skilled participants.

V-C Comparison with UCL

Having identified the three phenotypes of observed human performance in the above section, we show that the stochastic UCL algorithm (Algorithm 2) can produce behavior corresponding to the linear-law and log-law phenotypes by varying a minimal number of parameters. Parameters are used to encode the prior beliefs and the decision noise of the participant. A minimal set of parameters is given by the four scalars $\mu_{0},\sigma_{0},\lambda$ and $\upsilon$, defined as follows.

(ii,iii) Prior covariance For a spatially-embedded task, it is reasonable to assume that arms that are spatially close will have similar mean rewards. Following we choose the elements of $\Sigma_{0}$ to have the form

where $x_{i}$ is the location of arm $i$ and $\lambda\geq 0$ is the correlation length scale parameter that encodes the spatial smoothness of the reward surface. The case $\lambda=0$ represents complete independence of rewards, i.e., a very rough surface, while as $\lambda$ increases the agent believes the surface to be smoother. The parameter $\sigma_{0}\geq 0$ can be interpreted as a confidence parameter, with $\sigma_{0}=0$ representing absolute confidence in the beliefs about the mean $\boldsymbol{\mu}_{0}$, and $\sigma_{0}=+\infty$ representing complete lack of confidence.

(iv) Decision noise In Theorem 7 we show that for an appropriately chosen cooling schedule, the stochastic UCL algorithm with softmax action selection achieves logarithmic regret. However, the assumption that human participants employ this particular cooling schedule is unreasonably strong. It is of great interest in future experimental work to investigate what kind of cooling schedule best models human behavior. The Bayes-optimal cooling schedule can be computed using variational Bayes methods ; however, for simplicity, we model the participants’ decision noise by using softmax action selection with a constant temperature $\upsilon\geq 0$. This yields a single parameter representing the stochasticity of the decision-making: in the limit $\upsilon\to 0^{+}$, the model reduces to the deterministic UCL algorithm, while with increasing $\upsilon$ the decision-making is increasingly stochastic.

With this set of parameters, the prior quality $\zeta$ from Remark 5 reduces to $\zeta=(\max_{i}|m_{i}-\mu_{0}|)/\sigma_{0}$. Uninformative priors correspond to very large values of $\sigma_{0}$. Good priors, corresponding to small values of $\zeta$, have $\mu_{0}$ close to $m_{i^{*}}=\max_{i}m_{i}$ or little confidence in the value of $\mu_{0}$, represented by large values of $\sigma_{0}$.

By adjusting these parameters, we can replicate both linear and logarithmic observed regret behaviors as seen in the human data. Figure 8 shows examples of simulated observed regret $\mathcal{R}(t)$ that capture linear and logarithmic regret, respectively. In both examples, Landscape B was used for the mean rewards. The example with linear regret shows a case where the agent has fairly uninformative and fully uncorrelated prior beliefs (i.e., $\lambda=0$). The prior mean $\mu_{0}=30$ is set equal to the true surface mean, but with $\sigma_{0}^{2}=1000$, so that the agent is not very certain of this value. Moderate decision noise is incorporated by setting $\upsilon=4$. The values of the prior encourage the agent to explore most of the $N=100$ options in the $T=90$ choices, yielding regret that is linear in time. As emphasized in Remark 3, the deterministic UCL algorithm (and any agent employing the algorithm) with an uninformative prior cannot in general achieve sub-linear cumulative expected regret in a task with such a short horizon. The addition of decision noise to this algorithm will tend to increase regret, making it harder for the agent to achieve sub-linear regret.

In contrast, the example with logarithmic regret shows how an informative prior with an appropriate correlation structure can significantly improve the agent’s performance. The prior mean $\mu_{0}=200$ encourages more exploration than the previous value of 30, but the smaller value of $\sigma_{0}^{2}=10$ means the agent is more confident in its belief and will explore less. The correlation structure induced by setting the length scale $\lambda=4$ is a good model for the reward surface, allowing the agent to more quickly reject areas of low rewards. A lower softmax temperature $\upsilon=1$ means that the agent’s decisions are made more deterministically. Together, these differences lead to the agent’s logarithmic regret curve; this agent suffers less than a third of the total regret during the task as compared to the agent with the poorer prior and linear regret.

VI Gaussian multi-armed bandit problems with transition costs

To address this variation of the multi-armed bandit problem, we extend the UCL algorithm to a strategy that makes use of block allocations. Block allocations refer to sequences in which the same choice is made repeatedly; thus, during a block no transition cost is incurred. The UCL algorithm is used to make the choice of arm at the beginning of each block. The design of the (increasing) length of the blocks makes the block algorithm provably efficient. This model can be used in future experimental work to investigate human behavior in multi-armed bandit tasks with transition costs.

For Gaussian multi-armed bandits with transition costs, we develop a block allocation strategy described graphically in Figure 9 and in pseudocode in Algorithm 3 in Appendix F. The intuition behind the strategy is as follows. The decision-maker’s objective is to maximize the total expected reward while minimizing the number of transitions. As we have shown, maximizing total expected reward is equivalent to minimizing expected regret, which we know grows at least logarithmically with time. If we can bound the number of expected cumulative transitions to grow less than logarithmically in time, then the regret term will dominate and the overall objective will be close to its optimum value. Our block allocation strategy is designed to make transitions less than logarithmically in time, thereby ensuring that the expected cumulative regret term dominates.

We subdivide frame $f_{k}$ into blocks each of which will correspond to a sequence of choices of the same option. Let the first $\lfloor 2^{k-1}/k\rfloor$ blocks in frame $f_{k}$ have length $k$ and the remaining choices in frame $f_{k}$ constitute a single block of length $2^{k-1}-\lfloor 2^{k-1}/k\rfloor k$. The time associated with the choices made within frame $f_{k}$ is $\mathcal{O}(2^{k})$. Thus, following the intuition in the last paragraph, the length of each block in frame $f_{k}$ is chosen equal to $k$, which is $\mathcal{O}(\log(2^{k}))$.

Next, we analyze the regret of the block UCL algorithm. We first introduce some notation. Let $Q_{i}^{kr}$ be the $(1-1/K\tau_{kr})$-upper credible limit for the mean reward of arm $i$ at allocation round $(k,r)$, where $K=\sqrt{2\pi e}$ is the credible limit parameter. Let $n_{i}^{kr}$ be the number of times arm $i$ has been chosen until time $\tau_{kr}$ (the start of block $(k,r)$). Let $s_{i}^{t}$ be the number of times the decision-maker transitions to arm $i$ from another arm $j\in\{1,\dots,N\}\setminus\{i\}$ until time $t$. Let the empirical mean of the rewards from arm $i$ until time $\tau_{kr}$ be $\bar{m}_{i}^{kr}$. Conditioned on the number of visits $n_{i}^{kr}$ to arm $i$ and the empirical mean $\bar{m}_{i}^{kr}$, the mean reward at arm $i$ at time $\tau_{kr}$ is a Gaussian random variable ($M_{i}$) with mean and variance

Accordingly, the $\left(1-1/K\tau_{k,r}\right)$-upper credible upper limit $Q_{i}^{kr}$ is

Also, for each $i\in\{1,\dots,N\}$, we define constants

Let $\{R^{\textup{BUCL}}_{t}\}_{t\in\{1,\dots,T\}}$ be the sequence of the expected regret of the block UCL algorithm, and $\{S^{\textup{BUCL}}_{t}\}_{t\in\{1,\dots,T\}}$ be the sequence of expected transition costs. The block UCL algorithm achieves logarithmic regret uniformly in time as formalized in the following theorem.

The following statements hold for the Gaussian multi-armed bandit problem with transition costs and the block UCL algorithm with an uncorrelated uninformative prior:

the expected number of times a suboptimal arm $i$ is chosen until time $T$ satisfies

the expected number of transitions to a suboptimal arm $i$ from another arm until time $T$ satisfies

the cumulative expected regret and the cumulative transition cost until time $T$ satisfy

Figures 10 and 11 show, respectively, the cumulative expected regret and the cumulative transition cost of the block UCL algorithm on a bandit task with transition costs. For comparison, the figures also show the associated bounds from statement (iii) of Theorem 9. Cumulative expected regret was computed using 250 runs of the block UCL algorithm. Variance of the regret was minimal. The task used the reward surface of Landscape B from Figure 6(b) with sampling noise variance $\sigma_{s}^{2}=1$. The algorithm used an uncorrelated prior with $\mu_{0}=200$ and $\sigma_{0}^{2}=10^{6}$. Transition costs between options were equal to the distance between them on the surface.

The variance of the cumulative regret is relatively small, i.e., the cumulative regret experienced in a given task is close to the expected value. Also the bound on transition costs is quite loose. This is due to the loose bound on the expected number of transitions to the optimal arm. More detailed analysis of the total number of transitions would allow the bound to be tightened.

VII Graphical Gaussian multi-armed bandit problems

For graphical Gaussian multi-armed bandits, we develop an algorithm similar to the block allocation Algorithm 3, namely, the graphical block UCL algorithm, described in pseudocode in Algorithm 4 in Appendix F. Similar to the block allocation algorithm, at each block, the arm with maximum upper credible limit is determined. Since the arm with the maximum upper credible limit may not be immediately reached from the current arm, the graphical block UCL algorithm traverses a shortest path from the current arm to the arm with maximum upper credible limit. Traversing a shortest path will mean making as many as $N-2$ visits to undesirable arms ($N-2$ is the worst case in a line graph where the current location is at one end of the line and the desired arm is at the other end of the line). Thus, we apply a block allocation algorithm to limit the number of transitions as in the case of Algorithm 3 for the bandit problem with transition costs.

We classify the selection of arms in two categories, namely, goal selection and transient selection. The goal selection of an arm corresponds to the situation in which the arm is selected because it has the maximum upper credible limit, while the transient selection corresponds to the situation in which the arm is selected because it belongs to the shortest path to the arm with the maximum credible limit. Accordingly, we define the block associated with the goal selection of an arm as the goal block, and the block associated with arms on the shortest path between two arms associated with consecutive goal blocks as the transient block. The design of the blocks is pictorially depicted in Figure 12.

The key idea behind the algorithm is that the block allocation strategy results in an expected number of transitions that is sub-logarithmic in the horizon length. In the context of the graphical bandit, sub-logarithmic transitions result in sub-logarithmic undesired visits to the arms on the chosen shortest path to the desired arm with maximum upper credible limit. Consequently, the cumulative expected regret of the algorithm is dominated by a logarithmic term.

VII-B Regret analysis of the graphical block UCL algorithm

We now analyze the performance of the graphical block UCL algorithm. Let $\{R^{\textup{GUCL}}_{t}\}_{t\in\{1,\dots,T\}}$ be the sequence of expected regret of the graphical block UCL algorithm. The graphical block UCL algorithm achieves logarithmic regret uniformly in time as formalized in the following theorem.

The following statements hold for the graphical Gaussian multi-armed bandit problem with the graphical block UCL algorithm and an uncorrelated uninformative prior:

the expected number of times a suboptimal arm $i$ is chosen until time $T$ satisfies

the cumulative expected regret until time $T$ satisfies

Figure 13 shows cumulative expected regret and the associated bound from Theorem 10 for the graphical block UCB algorithm. The underlying graph topology was chosen to be a line graph, so the algorithm could only choose to move one step forwards or backwards at each time. Expected regret was computed using 250 runs of the graphical block UCL algorithm. Each task consisted of $N=10$ bandits with mean rewards set equal to the reward profile along the $x$-axis of Figure 6(b). Reward variance was $\sigma_{s}^{2}=6.25$, while the agent used the uncorrelated prior with $\mu_{0}=40$ and $\sigma_{0}^{2}=10^{6}$. Note that the regret bound is quite loose, as in the case of transition costs for the block UCL algorithm. This is because the regret bound uses the same bound on switching costs as in Theorem 9 to bound the regret incurred by traversing the graph.

VIII Conclusions

In this paper, we considered multi-armed bandit problems with Gaussian rewards and studied them from a Bayesian perspective. We considered three particular multi-armed bandit problems: the standard multi-armed bandit problem, the multi-armed bandit problem with transition costs, and the graphical multi-armed bandit problem. We developed two UCL algorithms, namely, the deterministic UCL algorithm and the stochastic UCL algorithm, for the standard multi-armed bandit problem. We extended the deterministic UCL algorithm to the block UCL algorithm and the graphical block UCL algorithm for the multi-armed bandit problem with transition costs, and the graphical multi-armed bandit problem, respectively. We established that for uninformative priors, each of the proposed algorithms achieves logarithmic regret uniformly in time, and moreover, the block UCL algorithm achieves a sub-logarithmic expected number of transitions among arms. We elucidated the role of general priors and the correlation structure among arms, showing how good priors and good assumptions on the correlation structure among arms can greatly enhance decision-making performance of the proposed deterministic UCL algorithm, even over short time horizons.

We drew connections between the features of the stochastic UCL and human decision-making in multi-armed bandit tasks. In particular, we showed how the stochastic UCL algorithm captures five key features of human decision-making in multi-armed bandit tasks, namely, (i) familiarity with the environment, (ii) ambiguity bonus, (iii) stochasticity, (iv) finite-horizon effects, and (v) environmental structure effects. We then presented empirical data from human decision-making experiments on a spatially-embedded multi-armed bandit task and demonstrated that the observed performance is efficiently captured by the proposed stochastic UCL algorithm with appropriate parameters.

This work presents several interesting avenues for future work in the design of human-automata systems. The model phenotypes discussed in Section V provide a method for assessing human performance in real time, and the experimental results presented in that section suggest that some humans use informative priors for spatial search tasks which allow them to achieve better performance than a similar algorithm using uninformative priors. Therefore, a useful goal for human-automata systems would be to develop a means to learn the humans’ informative priors and use them to improve the performance of the overall system.

This work also presents several interesting avenues for future psychological research. First, in this work, we relied on certain functional forms for the parameters in the algorithms, e.g., we considered credibility parameter $\alpha_{t}=1/Kt$ and cooling schedule $\upsilon_{t}=\nu/\log t$. It is of interest to perform thorough experiments with human subjects to ascertain the correctness of these functional forms. Second, efficient methods for estimation of parameters in the proposed algorithms need to be developed.

Overall, the proposed algorithms provide ample insights into plausible decision mechanisms involved with human decision-making in tasks with an explore-exploit tension. We envision a rich interplay between these algorithms and psychological research.

Acknowledgements

The authors wish to thank John Myles White, Robert C. Wilson, Philip Holmes and Jonathan D. Cohen for their input, which helped make possible the strong connection of this work to the psychology literature. We also thank the editor and two anonymous referees, whose comments greatly strengthened and clarified the paper. The first author is grateful to John Myles White and Daniel T. Swain for their help with implementing the online experiment.

References

Appendix

We start by establishing inequality (6). It suffices to establish this inequality for $\beta=1.02$. Since the cumulative distribution function for the standard normal random variable is a continuous and monotonically increasing function, it suffices to show that

for each $\alpha\in(0,1)$. Equation (13) can be equivalently written as $h(x)\geq 0$, where $x=2\pi\alpha^{2}$ and $h:(0,1)\rightarrow(0,1/\sqrt{2\pi})$ is defined by

Note that $\lim_{x\to 0^{+}}h(x)=0$ and $\lim_{x\to 1^{-}}h(x)=1/\sqrt{2\pi}$. Therefore, to establish the theorem, it suffices to establish that $h$ is a monotonically increasing function. It follows that

Note that $\lim_{x\to 0^{+}}g(x)=+\infty$ and $\lim_{x\to 1^{-}}g(x)=1$. Therefore, to establish that $h$ is monotonically increasing, it suffices to show that $g$ is non-negative for $x\in(0,1)$. This is the case if the following inequality holds:

The inequality holds if the right hand side is negative. If it is positive, one can take the square of both sides and the inequality holds if

Letting $t=-\log x$, the above inequality transforms to

These extrema can be calculated analytically, so we have

for the right hand side of (14). Therefore, (14) holds. In consequence, $g(x)$ is non-negative for $x\in(0,1)$, $h(x)$ is a monotonically increasing function. This establishes inequality (6). Inequality (7) follows analogously. ∎

VIII-B Proof of regret of the deterministic UCL algorithm

We start by establishing the first statement. In the spirit of , we bound $n_{i}^{T}$ as follows:

where $\eta$ is some positive integer and $\mathbf{1}\!\left(x\right)$ is the indicator function, with $\mathbf{1}\!\left(x\right)=1$ if $x$ is a true statement and otherwise.

At time $t$, the agent picks option $i$ over $i^{*}$ only if

This is true when at least one of the following equations holds:

where $C_{i}^{t}=\frac{\sigma_{s}}{\sqrt{\delta^{2}+n_{it}}}\Phi^{-1}(1-\alpha_{t})$ and $\alpha_{t}=1/Kt$. Otherwise, if none of the equations (15)-(17) holds,

and option $i^{*}$ is picked over option $i$ at time t.

We proceed by analyzing the probability that Equations (15) and (16) hold. Note that the empirical mean $\bar{m}_{i}^{t}$ is a normal random variable with mean $m_{i}$ and variance $\sigma_{s}^{2}/n_{i}^{t}$, so, conditional on $n_{i}^{t}$, $\mu_{i}^{t}$ is a normal random variable distributed as

where $z\sim\mathcal{N}(0,1)$ is a standard normal random variable and $\Delta m_{i^{*}}=m_{i^{*}}-\mu_{i^{*}}^{0}$. For an uninformative prior $\delta^{2}\to 0^{+}$, and consequently, equation (15) holds if and only if $z\leq-\Phi(1-\alpha_{t})$. Therefore, for a uninformative prior,

where $z\sim\mathcal{N}(0,1)$ is a standard normal random variable and $\Delta m_{i}=m_{i}-\mu_{i}^{0}$. The analogous argument to that for the above case shows that, for an uninformative prior,

where $\Delta_{i}=m_{i^{*}}-m_{i}$, the inequality (18) follows from the bound (6), and the inequality (19) follows from the monotonicity of the function $\log x-\log\log x$ in the interval $[e,+\infty)$. Therefore, for an uninformative prior, inequality (17) never holds if

Setting $\eta=\lceil\frac{4\beta^{2}\sigma_{s}^{2}}{\Delta_{i}^{2}}(1+2\log T-\log 2-\log\log T)\rceil$, we get

yielding the bound in the first statement

The second statement follows from the definition of the cumulative expected regret. ∎

VIII-C Proof of regret of the stochastic UCL algorithm

The probability $P_{it}$ can itself be bounded as

Substituting the expression for the cooling schedule in inequality (22), we obtain

For the purposes of the following analysis, define $\frac{0}{0}=1$.

Since $\Delta Q_{\min}^{t}\geq 0$, with equality only if two arms have identical heuristic values, conditioned on $Q_{i^{*}}^{t}\geq Q_{i}^{t}$ the exponent on $t$ can take the following magnitudes:

where $x\in[1,+\infty)$. The sign of the exponent is determined by the sign of $Q_{i^{*}}^{t}-Q_{i}^{t}$.

Consequently, it follows from inequality (23) that

where the last inequality follows from Theorem 2. This establishes the first statement.

The second statement follows from the definition of the cumulative expected regret. ∎

VIII-D Proof of regret of the block UCL algorithm

We start by establishing the first statement. For a given $t$, let $({k}_{t},{r}_{t})$ be the lexicographically maximum tuple such that $\tau_{{k}_{t}{r}_{t}}\leq t$. We note that

We note that $\boldsymbol{1}(i_{\tau_{kr}}=i)\leq\boldsymbol{1}(Q_{i}^{kr}>Q_{i^{*}}^{kr})$, where $i^{*}$ is the optimal arm. We now analyze the event $\boldsymbol{1}(Q_{i}^{kr}>Q_{i^{*}}^{kr})$. It follows that $\boldsymbol{1}(Q_{i}^{kr}>Q_{i^{*}}^{kr})=1$ if the following inequalities hold:

where C_{i}^{kr}=\frac{\sigma_{s}}{\sqrt{\delta^{2}+n_{i}^{kr}}}\Phi^{-1}\big{(}1-\frac{1}{K\tau_{kr}}\big{)}. Otherwise if none of the inequalities (25)-(27) hold, then

We now evaluate the probabilities of events (25)-(27). We note that

where $z\sim\mathcal{N}(0,1)$ is a standard normal random variable. Since $\delta^{2}\to 0^{+}$ as $\sigma_{0}^{2}\to+\infty$, it follows that

Since $\log x-\log\log x$ achieves its minimum at $x=e$, it follows that $\log(e\tau_{kr}^{2})-\log\log(e\tau_{kr}^{2})\leq\log(eT^{2})-\log\log(eT^{2})$. Consequently, inequality (27) holds if

Since $\delta^{2}\to 0^{+}$, it follows that inequality (27) does not hold if

Therefore, if we choose $\eta=\lceil\frac{8\beta^{2}\sigma_{s}^{2}}{\Delta_{i}^{2}}(\log T-\frac{1}{2}\log\log T)+\frac{4\beta^{2}\sigma_{s}^{2}}{\Delta_{i}^{2}}(1-\log 2)\rceil$, it follows from equation (24) that

We now establish the second statement. In the spirit of , we note that the number of times the decision-maker transitions to arm $i$ from another arm in frame $f_{k}$ is equal to the number of times arm $i$ is selected in frame $k$ divided by the length of each block in frame $f_{k}$. Consequently,

For the second sub-logarithmic term, the right hand side of inequality (30) is equal to

Similarly, for the constant term $\gamma_{2}$, the right hand side of inequality (30) is equal to

Collecting the terms from inequalities (31)-(33), it follows from inequality (30) that

We now establish the last statement. The bound on the cumulative expected regret follows from its definition and the first statement. To establish the bound on the cumulative switching cost, we note that

where the second inequality follows from the observation that $s_{i^{*}}^{T}\leq\sum_{i=1,i\neq i^{*}}^{T}s_{i}^{T}+1$. The final expression follows from inequality (34) and the second statement. ∎

VIII-E Proof of regret of the graphical block UCL algorithm

We start by establishing the first statement. Due to transient selections, the number of frames until time $T$ are at most equal to the number of frames if there are no transient selections. Consequently, the expected number of goal selections of a suboptimal arm $i$ are upper bounded by the expected number of selections of arm $i$ in the block UCL Algorithm 3, i.e.,

Moreover, the number of transient selections of arm $i$ are upper bounded by the total number of transitions from an arm to another arm in the block UCL Algorithm 3, i.e.,

The expected number of selections of arm $i$ is the sum of the expected number of transient selections and the expected number of goal selections, and thus the first statement follows.

The second statement follows immediately from the definition of the cumulative regret. ∎

VIII-F Pseudocode implementations of the UCL algorithms

VIII-G Correction to published proofs

The UCL algorithms described in the main body of this text and published in are heuristic-based algorithms which compute a heuristic value $Q_{i}^{t}$ for each option $i$ at each time $t$. The heuristic takes the functional form

which defines $C_{i}^{t}$, and where $\mu_{i}^{t}$ and $\sigma_{i}^{t}$ are the algorithm’s belief about the mean and standard deviation, respectively, of the reward associated with option $i$ at time $t$. The error in the proof arises from the fact that to apply concentration inequalities, we condition on the number $n_{i}^{t}$ of times that the algorithm has selected option $i$ up to time $t$. Since the arm selection policy depends on the rewards accrued, $n_{i}^{t}$ and the rewards are dependent random variables. Here, we build upon an alternative concentration inequality that accounts for this dependence and show that proofs of all the performance bounds follow a similar pattern with slight modification in the choice of $\alpha_{t}$ in the deterministic UCL algorithm and then show how to extend the correction to the other UCL algorithms published in .

Let $(X_{t})_{t\geq 1}$ be a sequence of sub-GaussianThe result in [1, Theorem 22] is stated for bounded rewards, but it extends immediately to sub-Gaussian rewards by noting that the upper bound on the moment generating function for a bounded random variable obtained using a Hoeffding inequality has the same functional form as the sub-Gaussian random variable. independent random variables with common variance parameter $\sigma$ and let $(\epsilon_{t})_{t\geq 1}$ be a previsible sequence of Bernoulli variables. Then, for all integers $t$ and all $\delta,\epsilon>0$,

We will also use the following bounds for $\Phi^{-1}(1-\alpha)$, the quantile function of the normal distribution.

We first prove (37). We begin with the inequality $\Phi^{-1}(1-\alpha)>\sqrt{-\log(2\pi\alpha^{2}(1-\log(2\pi\alpha^{2})))}$ established in . It suffices to show that

for $0<\nu\leq 1.59$. The left hand side of the above inequality is

It can be verified that $g$ admits a unique minimum at $t=e^{(\nu-1)/(2-\nu)}$ and the minimum value is $\nu-\log 2+\log(2-\nu)$, which is positive for $0<\nu\leq 1.59$.

Equation (38) is a straightforward application of Lemma 9 of , which itself follows from . ∎

VIII-G2 Correction for the deterministic UCL algorithm

We now show that a minor change of the functional form for $\alpha_{t}$ corrects the oversight in the proof of [2, Theorem 2]. Let $a>1$ and set $\alpha_{t}=1/\sqrt{2\pi e}t^{a}$. Note that the originally-published version of the deterministic UCL algorithm used $\alpha_{t}=1/\sqrt{2\pi e}t$, which is equivalent to taking $a=1$ in the modified functional form of $\alpha_{t}$. Then the following slightly-modified version of [2, Theorem 2] holds.

Let $\epsilon>0$. The following statements hold for the Gaussian multi-armed bandit problem and the deterministic UCL algorithm with uncorrelated uninformative prior and $\alpha_{t}=1/Kt^{a}$, with $K=\sqrt{2\pi e}$ and $a>4/(3(1-\epsilon^{2}/16))$:

the expected number of times a suboptimal arm $i$ is chosen until time $T$ satisfies

the cumulative expected regret until time $T$ satisfies

where $\eta$ is some positive integer. The condition $Q_{i^{*}}^{t}\leq Q_{i}^{t}$ is true when at least one of the three equations labeled (15–17) in hold. For an uninformative prior and applying Proposition 12, inequality (17) in never holds if

Setting $\eta=\left\lceil\frac{8a\sigma_{s}^{2}}{\Delta_{i}^{2}}\log T+o(\log T)\right\rceil$, we again get

Consider the probability that (15) holds. For an uncorrelated uninformative prior, $\mu_{i}^{t}=\bar{m}_{i}^{t}$ and $\sigma_{i}^{t}=\sigma_{s}/\sqrt{n_{i}^{t}}$. Then,

Suppose that $\alpha_{t}=1/\sqrt{2\pi e}t^{a}$ for some $a>1$. Then, (37) implies that at each time $t$,

The same bound holds for (16). Thus, for all $\epsilon>0$, we have

Furthermore, note that for $\varepsilon>0$, the following bounds hold:

This implies that the integral (39) is of class $o(\log T)$ as long as the exponent $3a(1-\epsilon^{2}/16)/4>1$. Let $\epsilon>0$. Then it suffices to take $a>4/(3(1-\epsilon^{2}/16))$, and $1+\varepsilon=(3a(1-\epsilon^{2}/16))/4$, so that $\varepsilon=(3a(1-\epsilon^{2}/16)/4-1>0$. Putting everything together, we have

The second statement follows from the definition of the cumulative expected regret. ∎

The same correction holds for the other UCL algorithms developed in , namely, the stochastic, block, and graphical block UCL algorithms. Let $\epsilon>0,K=\sqrt{2\pi e},$ and set $\alpha_{t}=1/(Kt^{a})$, where $a>4/(3(1-\epsilon^{2}/16))$. The resulting revised performance bounds are given in Table I.

References