2. Related literature

After years of research, many excellent strategies have been produced. Here we review some common strategies and illustrate how the results of this paper relate to and differ from these strategies.

In the multi-armed bandit literature, a celebrated result is the so-called Gittins index strategy introduced by Gittins and Jones [Reference Gittins and Jones17]. Unlike the model studied in this paper, the Gittins index strategy is used in a model with independent arms and an infinite number of trials, and the aim is to maximize the sum of geometrically discounted payoffs. This strategy assigns to each arm an index as a function of its current state, and then activates the arm with the largest index value (breaking the ties arbitrarily). It optimizes the infinite-horizon expected discounted payoffs. If the number of trials N is finite, then the Gittins index strategy can be used to approximate the optimal strategy when N is large. If more than one arm can change its state at every stage, the problem is called ‘restless’. Whittle [Reference Whittle37] proposed an index rule to solve the restless problem. This index is not necessarily optimal, but Whittle conjectured that it would admit a form of asymptotic optimality as both the number of arms and the number of allocated arms in each period grow to infinity at a fixed proportion, which was eventually proved in Weber and Weiss [Reference Weber and Weiss36] under some technical assumptions. The restless multi-armed bandit model can be used in many aspects such as clinical trials, sensor management, and capacity management in healthcare; see [Reference Ahmad, Liu, Javidi, Zhao and Krishnamachari3], [Reference Deo, Iravani, Jiang, Smilowitz and Samuelson13], [Reference Gittins, Glazebrook and Weber19], [Reference Lee, Lavieri and Volk27], [Reference Mahajan and Teneketzis28], and [Reference Washburn35].

A major drawback of the Gittins index and Whittle index is that they are both difficult to calculate. The current fastest algorithm can only solve the index in cubic time [Reference Gast, Gaujal and Khun16, Reference Niño-Mora29]. In contrast, the calculation of the myopic strategy is much easier. A second issue of the Gittins index is that the arms must have independent parameters, and the payoffs are geometrically discounted. If these conditions are not met, as in the model studied in this paper, the Gittins index strategy is no longer the optimal strategy [Reference Berry and Fristedt9, Reference Gittins and Wang18]. Therefore it is necessary to obtain the condition that the myopic strategy is the optimal strategy when studying the model in this paper.

Another important strategy is the UCB strategy. Lai and Robbins [Reference Lai and Robbins25] laid out the theory of asymptotically optimal allocation and were the first to actually use the term ‘upper confidence bound’ (UCB). The UCB strategy is also applied to models with independent arms. Initially the UCB strategy was used for models with an infinite number of trials, but with modifications the UCB can also be used for models with a finite number of trials. When using the UCB strategy, each arm is assigned a UCB for its mean reward, and the arm with the largest bound is to be played. The bound is not the conventional upper limit for a confidence interval. The design of the confidence bound has been successively improved [Reference Agrawal2, Reference Audibert and Bubeck4–Reference Auer, Cesa-Bianchi and Fischer6, Reference Cappé, Garivier, Maillard, Munos and Stoltz11, Reference Honda and Takemura20, Reference Lai26]. Among these, the kl-UCB strategy [Reference Cappé, Garivier, Maillard, Munos and Stoltz11] and Bayes-UCB strategy [Reference Kaufmann21] are asymptotically optimal for exponential family bandit models. The improved UCB strategy is now easy to compute but is still limited to models with independent arms.

The $\epsilon$ -greedy strategy [Reference Kuleshov and Precup24] is widely used because it is very simple. At each round $t = 1, 2,\dots$ the agent selects the arm with the highest empirical mean with probability $1-\epsilon$ , and selects a random arm with probability $\epsilon$ . It has poor asymptotic behavior, because it continues to explore long after the optimal solution becomes apparent. Another common strategy, in the case of Bernoulli arms, is play-the-winner. It is a well-known strategy in which arm a is played at time $t +1$ if it resulted in success at time t. If a failure is observed at time t, then the next arm is either chosen at random or the arms are cycled through deterministically. Play-the-winner can be nearly optimal when the best arm has a very high success rate, but does not perform well in most cases [Reference Berry and Fristedt9, Reference Scott33].

There are also many variants of the bandit problem, such as the adversarial multi-armed bandit with the EXP3 strategy [Reference Auer, Cesa-Bianchi, Freund and Schapire7] and online linear optimization with the FTL strategy [Reference Abernethy, Hazan and Rakhlin1], but these are beyond the scope of this paper.

In fact, compared with the various classical models mentioned above, the biggest feature of the model in this paper is the introduction of the utility function of the agent. All of the above strategies only consider linear utility or discounted returns, but agents may have nonlinear utility functions. For example, in Nouiehed and Ross’s conjecture, the utility of an agent will no longer grow after a certain amount of gain. In this case, the effect of strategies such as the Gittins index or UCB will be significantly reduced.

After the introduction of a generalized utility function, the bandit problem becomes very complicated. To simplify the model and clearly demonstrate the ideas in this paper, we study this two-armed bandit model. Nouiehed and Ross’s conjecture for the multi-armed bandit machine model can also be studied with the method in this paper.

The multi-armed bandit model in Ross’s conjecture can be further generalized. For example, when the arms have independent parameters and the discounting factor is geometric, Banks and Sundaram [Reference Banks and Sundaram8] proved that the myopic strategy is equivalent to the Gittins index strategy for linear utility functions. When the agent has a general utility function, does the Gittins index still exist, and can the myopic strategy still be the optimal strategy under certain conditions? Exploration of these issues will lead us to better understand the nature of the bandit problem. Chen, Epstein, and Zhang [Reference Chen, Epstein and Zhang12] studied a multi-armed bandit problem where the agent is loss-averse; in particular, the agent is risk-averse in the domain of gains and risk-loving in the domain of losses, and they established the corresponding asymptotically optimal strategy. This is an important advance in this research.

3. Preliminaries

Let us start with the description of the two-armed bandit model (1.1) and the strategies.

Consider the bandit model in equation (1.1). Let $\{X_i\}_{i\geq1}$ be a sequence of random variables, where $X_i$ describes the payoff of trial i from the X-arm, and let $\{Y_i\}_{i\geq1}$ be a sequence of random variables selected from the Y-arm; $\{(X_i,Y_i)\}_{i\ge 1}$ are independent under each hypothesis. We define $\mathcal{F}_i\;:\!=\; \sigma\{(X_1,Y_1),\ldots,(X_{i},Y_i)\}$ , which represents all the information that can be obtained until trial i.

We call this model a $(\xi_0,n,x)$ -bandit if there are n trials to be played with initial fund x and a prior probability $\xi_0$ . In the following discussion, the distributions $F_1$ and $F_2$ of arms are continuous with density $f_1$ and $f_2$ , respectively.

For each $i\geq1$ , let $\theta_i$ be an $\mathcal{F}_{i-1}$ -measurable random variable taking values in $\{0,1\}$ , where $\theta_i=1$ means the X-arm is selected for observation in trial i and $\theta_i=0$ means the Y-arm is selected for observation in trial i. The payoff that an agent receives using $\theta_i$ in trial i is

\begin{equation*}Z_{i}^{\theta}\;:\!=\; \theta_{i}X_{i}+(1-\theta_{i})Y_{i}.\end{equation*}

For a $(\xi_0,n,x)$ -bandit and $\theta=\{\theta_1,\ldots,\theta_n\}$ , if $\theta_i\in \sigma(Z_1^\theta,\ldots,Z_{i-1}^\theta)\subset \mathcal{F}_{i-1}$ , then we call $\theta$ a strategy. The set of strategies for a $(\xi_0,n,x)$ -bandit is denoted by $\Theta_n$ .

For a $(\xi_0,n,x)$ -bandit and a suitable measurable function $\varphi$ , the expected utility obtained by using strategy $\theta$ is denoted by

\begin{align*} W(\xi_0,n,x,\theta)=\mathbb{E}_\mathbb{P}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr],\end{align*}

where $\varphi$ is called a utility function.

For each strategy $\theta\in\Theta_n$ , let $\{\xi_i^\theta\}_{i\ge1}$ be the sequence of the posterior probabilities that hypothesis $H_1$ is true after i trials. The posterior probability $\xi^\theta_1$ after trial 1 with payoff s is calculated by

(3.1) $$\xi _1^\theta (s) = \left\{ {\matrix{ {{{{\xi _0}{f_1}(s)} \over {{\xi _0}{f_1}(s) + (1 - {\xi _0}){f_2}(s)}}} & {{\rm{if }}\,{\theta _{\rm{1}}}{\rm{ = 1}},{\rm{i}}.{\rm{e}}.\;{\rm{the }} \, X{\rm{- arm \, is \, selected,}}} \cr {{{{\xi _{\rm{0}}}{{\rm{f}}_{\rm{2}}}({\rm{s}})} \over {{\xi _{\rm{0}}}{{\rm{f}}_{\rm{2}}}({\rm{s}}){\rm{ + }}({\rm{1 - }}{\xi _{\rm{0}}}){{\rm{f}}_{\rm{1}}}({\rm{s}})}}} & {{\rm{if }}\,{\theta _{\rm{1}}}{\rm{ = 0}},{\rm{i}}.{\rm{e}}.\;{\rm{the }}\, Y{\rm{ - arm \,is \, selected}}{\rm{.}}} \cr } } \right.$$

We can easily obtain that for any fixed s, $\xi_1^\theta(s)$ is increasing in $\xi_0$ . When the posterior probability $\xi_i^\theta$ is known and the payoff of the $i+1$ trial is s, there is a recursive formula

(3.2) $$\xi _{i + 1}^\theta (s) = \left\{ {\matrix{ {{{\xi _i^\theta {f_1}(s)} \over {\xi _i^\theta {f_1}(s) + (1 - \xi _i^\theta ){f_2}(s)}}} & {{\rm{if }}\,{\theta _{{\rm{i + 1}}}}{\rm{ = 1}},{\rm{i}}.{\rm{e}}.\;{\rm{the }}\,X{\rm{ - arm \, is \, selected,}}} \cr {{{\xi _{\rm{i}}^\theta {{\rm{f}}_{\rm{2}}}({\rm{s}})} \over {\xi _{\rm{i}}^\theta {{\rm{f}}_{\rm{2}}}({\rm{s}}){\rm{ + }}({\rm{1 - }}\xi _{\rm{i}}^\theta ){{\rm{f}}_{\rm{1}}}({\rm{s}})}}} & {{\rm{if }}\,{\theta _{{\rm{i + 1}}}}{\rm{ = 0}},{\rm{i}}.{\rm{e}}.\;{\rm{the}}\, Y{\rm{ - arm \, is \, selected}}{\rm{.}}} \cr } } \right.$$

Now we propose the following two-armed bandit problem.

Problem (TAB). For a $(\xi_0,n,x)$ -bandit and a utility function $\varphi$ , find some strategy in $\Theta_n$ to achieve the maximal expected utility

(3.3) \begin{equation}V(\xi_0,n,x)\;:\!=\; \sup_{\theta\in \Theta_n} W(\xi_0,n,x,\theta)=\sup_{\theta\in\Theta_n} \mathbb{E}_\mathbb{P}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr].\end{equation}

Note that the expected utility $\mathbb{E}_\mathbb{P}[\!\cdot\!]$ depends on hypothesis $H_1$ , $H_2$ , and $\xi_0$ . In fact,

\begin{align*}&\mathbb{E}_\mathbb{P} \Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr] =\xi_0 \mathbb{E}_\mathbb{P}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\mid H_1\Biggr]+(1-\xi_0)\mathbb{E}_\mathbb{P}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\mid H_2\Biggr],\end{align*}

where $\mathbb{E}_\mathbb{P}[\cdot\mid H_i]$ is the expectation under hypothesis $H_i$ $(i=1,2).$

To simplify the notation, we write $\mathbb{E}_\mathbb{P}[\cdot\mid H_1]$ as $\mathbb{E}_1[\!\cdot\!]$ , $\mathbb{E}_\mathbb{P}[\cdot\mid H_2]$ as $\mathbb{E}_2[\!\cdot\!]$ , and $\mathbb{E}_\mathbb{P}[\!\cdot\!]$ as $\mathbb{E}_{\xi_0}[\!\cdot\!]$ . Then the expected utility can be written as

\begin{align*} W(\xi_0,n,x,\theta)=\mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr],\end{align*}

where

\begin{equation*} \mathbb{E}_{\xi_0} \Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr]=\xi_0 \mathbb{E}_1\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr]+(1-\xi_0)\mathbb{E}_2\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr].\end{equation*}

Immediately, equality (3.3) can be written as follows:

\begin{align*} V(\xi_0,n,x)=\sup_{\theta\in \Theta_n} W(\xi_0,n,x,\theta)=\sup_{\theta\in \Theta_n} \mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr].\end{align*}

Consider a strategy $\textsf{M}^n$ : in trial i, play the X-arm if $\xi_{i-1}\ge \frac{1}{2}$ , or the Y-arm otherwise. Our main result is to find conditions under which $\textsf{M}^n$ could solve Problem (TAB).

The following lemma shows that when calculating the expected utility, we can temporarily fix the payoff of the first trial, calculate the expected utility as a function of the first payoff, and then take expectation while seeing the first payoff as a random variable. This is an extension of equation (2) in Feldman [Reference Feldman14].

Lemma 3.1. For each integer $n\ge 2$ and strategy $\theta=\{\theta_1,\ldots,\theta_n\}\in\Theta_n $ , we have

(3.4) \begin{align}\mathbb{E}_{\xi_0} \Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr]=\mathbb{E}_{\xi_0}\bigl[h\bigl(x,Z_1^\theta\bigr)\bigr]\quad \textit{for all $x\in \mathbb R$,}\end{align}

where

\begin{align*} h(x,u)=\mathbb{E}_{\xi_1^\theta(u)}\Biggl[\varphi\Biggl(x+u+\sum_{i=2}^{n} Z_i^{\theta[u]}\Biggr)\Biggr],\end{align*}

$\xi_{1}^\theta$ is defined by (3.1), and $\theta[u]$ is the strategy obtained from $\theta$ by fixing the payoff of the first trial to be u.

Remark 3.3. $\mathbb{E}_{\xi_1^\theta(u)}[\!\cdot\!]$ is the expected utility $\mathbb{E}_{\xi_0}[\!\cdot\!]$ replacing $\xi_0$ with $\xi_1^\theta(u)$ . In integral form, equation (3.4) is

\begin{align*}&\mathbb{E}_{\xi_0} \Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^\theta\Biggr)\Biggr] =\int_{\mathbb R} \mathbb{E}_{\xi_1^\theta(u)}\Biggl[\varphi\Biggl(x+u+\sum_{i=2}^{n} Z_i^{\theta[u]}\Biggr)\Biggr](\xi_0f_{1}(u)+(1-\xi_0)f_{2}(u))\,{\mathrm{d}} u.\end{align*}

We can see that the form of h(x, u) is very similar to the expected utility of the $(\xi_1^\theta(u),$ $n-1,x+u)$ -bandit with some strategy. There is indeed such a strategy to make the value of h(x, u) equal to the expected utility of the $(\xi_1^\theta(u),n-1,x+u)$ -bandit.

Lemma 3.2. For any strategy $\theta\in \Theta_n$ , let

\begin{align*} h(x,u)=\mathbb{E}_{\xi_1^\theta(u)}\Biggl[\varphi\Biggl(x+u+\sum_{i=2}^{n} Z_i^{\theta[u]}\Biggr)\Biggr]. \end{align*}

Then, for any u, there exists a strategy $\rho\in \Theta_{n-1}$ , such that the value of h(x,u) is equal to the expected utility of the $(\xi_1^\theta(u),n-1,x+u)$ -bandit with strategy $\rho$ , that is,

\begin{align*} h(x,u)&=\mathbb{E}_{\xi_1^\theta(u)}\Biggl[\varphi\Biggl(x+u+\sum_{i=2}^{n} Z_i^{\theta[u]}\Biggr)\Biggr]\notag \\[5pt] &=\mathbb{E}_{\xi_1^\theta(u)}\Biggl[\varphi\Biggl(x+u+\sum_{i=1}^{n-1} Z_i^{\rho}\Biggr)\Biggr]\notag \\[5pt] &=W(\xi_1^\theta(u),n-1,x+u,\rho).\end{align*}

Proof. We know that $\theta[u]$ is obtained by fixing the payoff u of the first trial, so for any $\theta'_{\!\!i}\in \theta[u]$ it is $\sigma(X_2,Y_2,\ldots,X_{i-1},Y_{i-1})$ -measurable. Then there are measurable functions $\pi_i$ , $i\ge 2$ , such that

\begin{align*}\theta'_{\!\!i}=\pi_i(X_2,Y_2,\ldots,X_{i-1},Y_{i-1}),\quad i\ge 2.\end{align*}

Define a new strategy $\rho\in\Theta_{n-1}$ by

\begin{align*}\rho_i=\pi_{i+1}(X_1,Y_1,\ldots,X_{i-1},Y_{i-1}),\quad 1\le i\le n-1.\end{align*}

The fact that $\rho_{i+1}\in \sigma(Z_1^\rho,\ldots,Z_i^\rho)$ can be easily verified.

By the definition of $\rho$ , we know that $\rho_i$ has the same distribution as $\theta'_{i+1}$ in both hypotheses, so $Z_i^{\theta[u]}$ and $Z_i^{\rho}$ have the same distribution. Using this fact, we can easily verify that

\begin{align*}\mathbb{E}_{\xi_1^\theta(u)}\Biggl[\varphi\Biggl(x+u+\sum_{i=2}^{n} Z_i^{\theta[u]}\Biggr)\Biggr]=\mathbb{E}_{\xi_1^\theta(u)}\Biggl[\varphi\Biggl(x+u+\sum_{i=1}^{n-1} Z_i^{\rho}\Biggr)\Biggr].\end{align*}

Now we introduce the dynamic programming property of the expected utility, which plays an important role in the subsequent arguments. Similar results are found in many works on bandit problems, but only for the case of $\varphi(x)=x$ (e.g. [Reference Berry and Fristedt9], [Reference Feldman14]). Our result extends the classical ones.

Theorem 3.1. For each $\xi_0\in [0,1]$ , $n\geq1$ and $x\in\mathbb{R}$ , consider the $(\xi_0,n,x)$ -bandit. The optimal strategy $\theta^{[n]}\in \Theta_n$ exists. Then there are measurable functions

\begin{align*}\pi^{[n]}_i\;:\;[0,1]\times\mathbb{R}\times\mathbb{R}^{2i-2}\mapsto \{0,1\},\quad 1\le i\le n, \end{align*}

such that for any $\xi_0\in [0,1]$ and $x\in\mathbb{R}$ , the optimal strategy $\theta^{[n]}$ for the $(\xi_0,n,x)$ -bandit satisfies

\begin{equation*} \begin{aligned}\theta^{[n]}_1&=\pi^{[n]}_1(\xi_0,x),\\[5pt] \theta^{[n]}_i&=\pi^{[n]}_i(\xi_0,x,X_1,Y_1,\ldots,X_{i-1},Y_{i-1}),\quad i\geq2.\end{aligned}\end{equation*}

Further, the optimal expected utility satisfies the following dynamic programming property:

\begin{align*} V(\xi_0,n,x)&= \sup_{\theta\in \Theta_n} \mathbb{E}_{\xi_0}\bigl[V\bigl(\xi_1^\theta,n-1,x+Z^\theta_1\bigr)\bigr] \notag \\[5pt] &= \max \biggl\{ \mathbb{E}_{\xi_0}\biggl[V\biggl(\dfrac{\xi_0f_1(X_1) }{\xi_0 f_1(X_1)+(1-\xi_0)f_2(X_1)},n-1,x+X_1\biggr)\biggr],\notag \\[5pt] &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbb{E}_{\xi_0}\biggl[V\biggl(\dfrac{\xi_0f_2(Y_1) }{\xi_0 f_2(Y_1)+(1-\xi_0)f_1(Y_1)},n-1,x+Y_1\biggr)\biggr] \biggr\}.\end{align*}

Theorem 3.1 is mostly standard for a finite action and horizon dynamic programming problem, so we omit the proof.

4. Main results

Now we are going to study the specific form of the optimal strategy, for the finite two-armed bandit (1.1) with utility function $\varphi$ . It is obvious that different utility functions may lead to different optimal strategies, but we will show that when a reasonable condition is satisfied, the optimal strategy is independent of the specific form of $\varphi$ .

Recall that the myopic strategy for $(\xi_0,n,x)$ -bandits is $\textsf{M}^n=\{\textsf{m}^n_1,\ldots,\textsf{m}^n_n\}$ : in trial i, play the X-arm if the posterior probability $\xi_{i-1}^{\textsf{M}^n}\ge \frac{1}{2}$ , or the Y-arm if $\xi_{i-1}^{\textsf{M}^n}\lt\frac{1}{2}$ . Note that $\textsf{M}^n\in\Theta_n$ . In fact, $\textsf{M}^n$ can be denoted by

(4.1) \begin{align}\textsf{M}^n&=\bigl\{\textsf{m}^n_1,\ldots,\textsf{m}^n_n\bigr\}\notag \\[5pt] &=\bigl\{g\bigl(\xi_0\bigr),g\bigl(\xi_1^{\textsf{M}^n}\bigr),\ldots,g\bigl(\xi_{n-1}^{\textsf{M}^n}\bigr)\bigr\}\in\Theta_n,\end{align}

where $g(x)=1$ if $x\geq\frac{1}{2}$ , or $g(x)=0$ if $x\lt\frac{1}{2}$ . From the definition of $\xi_{i-1}^{\textsf{M}^n}$ and $\textsf{m}^n_i$ , we know that they are both independent of n and x. Hence we can write $\xi_{i-1}^{\textsf{M}^n}$ for short as $\xi_{i-1}^{\textsf{M}}$ , and write $\textsf{m}^n_i$ as $\textsf{m}_i$ . Now the myopic strategy $\textsf{M}^n$ is denoted by

\begin{align*}\textsf{M}^n&=\{\textsf{m}_1,\ldots,\textsf{m}_n\}\notag \\[5pt] &=\bigl\{g\bigl(\xi_0\bigr),g\bigl(\xi_1^{\textsf{M}}\bigr),\ldots,g\bigl(\xi_{n-1}^{\textsf{M}}\bigr)\bigr\}.\end{align*}

Next we will give a condition on $\varphi$ which is necessary and sufficient for $\textsf{M}^n$ being the optimal strategy.

Theorem 4.1. For any integer $n\ge 1$ , the myopic strategy $\textsf{M}^n$ is the optimal strategy of the $(\xi_0,n,x)$ -bandit for all $ \xi_0\in[0,1]$ , $ x\in \mathbb{R}$ , if and only if

(I) \begin{equation}\mathbb{E}_1[\varphi(u+X_1)]\ge \mathbb{E}_1[\varphi(u+Y_1)] \quad \textit{for all $ u\in \mathbb{R}$.}\end{equation}

Remark 4.1. When $\varphi(x)=x$ , condition (I) is in fact

\begin{align*} \mathbb{E}_1[X_1]\ge \mathbb{E}_1[Y_1],\end{align*}

and Theorem 4.1 in this case is exactly Theorem 2.1 of Feldman [Reference Feldman14].

Remark 4.2. When the two distributions $F_1$ , $F_2$ are Bernoulli distributions, say $\operatorname{Bernoulli}(\alpha)$ and $\operatorname{Bernoulli}(\beta)$ , $\alpha,\beta\in(0,1)$ , then condition (I) is written as

\begin{equation*}(\varphi(x+1)-\varphi(x))(\alpha-\beta)\ge 0\quad \text{for any $x\in \mathbb{R}$}.\end{equation*}

If $\varphi(x)$ is an increasing function of x, and $\alpha\ge \beta$ , then condition (I) holds.

To achieve our goal, we need to formulate some properties of the expected utility of $\textsf{M}^n$ , which can be considered as extensions of properties of $R_N$ , and Lemma 2.1 in Feldman’s paper [Reference Feldman14].

Lemma 4.2. Consider the following strategies.

For $n=2$ , let $\textsf{U}^2=\{1,0\}$ and $\textsf{V}^2=\{0,1\}$ .

For each $n\geq3$ , let

\begin{align*}\textsf{U}^n&=\bigl\{1,0,g\bigl(\xi_2^{\textsf{U}^n}\bigr),\ldots,g\bigl(\xi_{n-1}^{\textsf{U}^n}\bigr)\bigr\},\\[5pt] \textsf{V}^n&=\bigl\{0,1,g\bigl(\xi_2^{\textsf{V}^n}\bigr),\ldots,g\bigl(\xi_{n-1}^{\textsf{V}^n}\bigr)\bigr\},\end{align*}

where $g(\!\cdot\!)$ is the function defined in (4.1). Then, for each $n\ge 2$ , $\xi_0\in[0,1]$ and $x\in\mathbb{R}$ , the expected utilities obtained by using $\textsf{U}^n$ and $\textsf{V}^n$ satisfy the relation

\begin{align*} W(\xi_0,n,x,\textsf{U}^n)=W(\xi_0,n,x,\textsf{V}^n).\end{align*}

Proof. For $n=2$ the result is obvious. We only need to consider cases where $n\ge 3$ . Let $\xi_2^{\textsf{U}^n}(u,s)$ be the posterior probability given the first payoff u and second payoff s, using strategy $\textsf{U}^n$ , and let $\xi_2^{\textsf{V}^n}(s,u)$ be the posterior probability given the first payoff s and second payoff u, using strategy $\textsf{V}^n$ . According to (3.2), there is

(4.4) \begin{align}\xi_2^{\textsf{U}^n}(u,s)=\dfrac{\xi_0 f_1(u)f_2(s)}{\xi_0f_1(u)f_2(s)+(1-\xi_0)f_2(u)f_1(s)}=\xi_2^{\textsf{V}^n}(s,u).\end{align}

Let the conditional strategy $\textsf{U}^n[u,s]$ denote the strategy $\textsf{U}^n$ given the first payoff u and second payoff s, and let the conditional strategy $\textsf{V}^n[s,u]$ denote the strategy $\textsf{V}^n$ given the first payoff s and second payoff u. Then, by (4.4) and the definitions of $\textsf{U}^n[u,s]$ and $\textsf{V}^n[s,u]$ , we can easily get that these two conditional strategies are the same for $i\ge 3$ trials.

Using the same techniques as in Lemma 3.1, we obtain

\begin{align*}&W(\xi_0,n,x,\textsf{U}^n)\notag \\[5pt] &\quad =\mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^{\textsf{U}^n}\Biggr)\Biggr]\notag\\[5pt] &\quad =\int_{\mathbb R}\int_{\mathbb R} \mathbb{E}_{\xi_2^{\textsf{U}^n}\!(u,s)\!}\Biggl[\varphi\Biggl(x+u+s+\sum_{j=3}^{n} Z_j^{\textsf{U}^n[u,s]}\Biggr)\Biggr] (\xi_0f_{1}(u)f_{2}(s)+(1-\xi_0)f_{2}(u)f_{1}(s))\,{\mathrm{d}} s\,{\mathrm{d}} u \end{align*}

and

\begin{align*} &W(\xi_0,n,x,\textsf{V}^n)\notag \\[5pt] &\quad =\mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^{\textsf{V}^n}\Biggr)\Biggr]\notag\\[5pt] &\quad =\int_{\mathbb R}\int_{\mathbb R} \mathbb{E}_{\xi_2^{\textsf{V}^n}\!(s,u)\!}\Biggl[\varphi\Biggl(\!x+s+u+\sum_{j=3}^{n} Z_j^{\textsf{V}^n[s,u]}\Biggr)\Biggr](\xi_0f_{2}(s)f_{1}(u)+(1-\xi_0)f_{1}(s)f_{2}(u))\,{\mathrm{d}} u\,{\mathrm{d}} s.\end{align*}

Then the desired result is obtained by using (4.4) and the fact that $\textsf{U}^n[u,s]=\textsf{V}^n[s,u]$ for $i\ge 3$ trials.

For each $n\in\mathbb{Z}^+$ , let $\textsf{L}^n$ and $\textsf{R}^n$ be the strategies defined in Lemma 4.1. For $x\in\mathbb{R}$ , $\xi_0\in[0,1]$ , define the difference of expected utilities by

\begin{align*}\Delta_n(x,\xi_0)&\;:\!=\; W(\xi_0,n,x,\textsf{L}^n)-W(\xi_0,n,x,\textsf{R}^n)\\[5pt] &=\mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^{\textsf{L}^n}\Biggr)\Biggr] - \mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^{\textsf{R}^n}\Biggr)\Biggr].\end{align*}

By Lemma 4.1 we can obtain $\Delta_n(x,\xi_0)=-\Delta_n(x,1-\xi_0)$ and $\Delta_n(x,0.5)=0$ .

In the case $\varphi(x)=x$ , there is an important recurrence formula for $\Delta_n(x,\xi_0)$ ; see equations (12), (13), and (14) in [Reference Feldman14] and equation (7.1.1) in [Reference Berry and Fristedt9]. The following lemma shows that this recurrence formula still holds for a general utility function.

Lemma 4.3. For $n\ge 2$ , and any $x\in\mathbb{R}$ , $\xi_0\in[0,1]$ , there is

\begin{align*}\Delta_n(x,\xi_0)& =\int_{\mathbb R} I_{\bigl\{\xi_1^X(u)\ge 0.5\bigr\}}\Delta_{n-1}\bigl(x+u,\xi_1^X(u)\bigr)\bigl(\xi_0f_1(u)+(1-\xi_0)f_2(u)\bigr)\,{\mathrm{d}} u \notag \\[5pt] &\quad +\int_{\mathbb R} I_{\bigl\{\xi_1^Y(u)<0.5\bigr\}}\Delta_{n-1}\bigl(x +u,\xi_1^Y(u)\bigr)\bigl(\xi_0f_2(u) +(1-\xi_0)f_1(u) \bigr)\,{\mathrm{d}} u,\end{align*}

where

\begin{align*} \xi_1^X(u)=\frac{\xi_0 f_1(u) }{\xi_0 f_1(u) +(1-\xi_0)f_2(u)}\quad\textit{and}\quad\xi_1^Y(u)=\frac{\xi_0 f_2(u) }{\xi_0 f_2(u) +(1-\xi_0)f_1(u)}.\end{align*}

Proof. Consider strategies $\textsf{U}^n,\textsf{V}^n$ defined in Lemma 4.2. Using Lemmas 3.1 and 3.2, we can make the following two differences:

\begin{align*}&W(\xi_0,n,x,\textsf{L}^n)-W(\xi_0,n,x,\textsf{U}^n) \notag \\[5pt] &\quad =\mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^{\textsf{L}^n}\Biggr)\Biggr] - \mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^{\textsf{U}^n}\Biggr)\Biggr] \notag\\[5pt] &\quad =\int_{\mathbb R} I_{\bigl\{\xi_1^X(u)\ge 0.5\bigr\}}\Delta_{n-1}\bigl(x+u,\xi_1^X(u)\bigr)\bigl(\xi_0f_1(u)+(1-\xi_0)f_2(u)\bigr)\,{\mathrm{d}} u,\\[5pt] &W(\xi_0,n,x,\textsf{V}^n)-W(\xi_0,n,x,\textsf{R}^n) \notag\\[5pt] &\quad =\mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^{\textsf{V}^n}\Biggr)\Biggr] - \mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{n} Z_i^{\textsf{R}^n}\Biggr)\Biggr] \notag\\[5pt] &\quad =\int_{\mathbb R} I_{\bigl\{\xi_1^Y(u)<0.5\bigr\}}\Delta_{n-1}\bigl(x +u,\xi_1^Y(u)\bigr)\bigl(\xi_0f_2(u) +(1-\xi_0)f_1(u) \bigr)\,{\mathrm{d}} u.\end{align*}

The computational details are similar to the proofs of Lemmas 4.1 and 4.2, so we omit them. The desired formula is obtained by adding the above two equations and using Lemma 4.2.

The key to achieving our main theorem is to prove that for any fixed $x\in\mathbb{R}$ and $n\in\mathbb{Z}^+$ , the above difference $\Delta_n(x,\xi_0)$ is an increasing function of $\xi_0$ . To prove this assertion, we use a method similar to that used by Rodman [Reference Rodman31].

Define functions $D_n(x,t_X,t_Y)$ , $n=1,2,\dots$ , for every tuple $(x,t_X,t_Y)$ of numbers, such that $x\in\mathbb{R}$ and $t_X,t_Y\ge 0$ :

\begin{equation*}D_n(x,t_X,t_Y)= \left\{\begin{aligned}&(t_X+t_Y)\Delta_n\biggl(x,\frac{t_X}{t_X+t_Y}\biggr)& &\text{if $t_X+t_Y>0$,}\\[5pt] &0&&\text{otherwise.}\end{aligned}\right.\end{equation*}

From this definition we obtain immediately that

\begin{align*} D_n(x,t_X,t_Y)=-D_n(x,t_Y,t_X)\quad\text{and}\quad D_n(x,t_X,t_Y)=0\quad\text{if $t_X=t_Y$.}\end{align*}

Proof. The proof is by induction. When $n=1$ ,

\begin{equation*}D_1(x,t_X,t_Y)=(t_X-t_Y)\int_{\mathbb R} \varphi(x+u)(f_1(u)-f_2(u))\,{\mathrm{d}} u\end{equation*}

is clearly an increasing function of $t_X$ when $x,t_Y$ are kept fixed.

Now suppose Lemma 4.4 is proved for $n=k$ . From Lemma 4.3 we know that

\begin{align*}D_{k+1}(x,t_X,t_Y)& =\int_{\mathbb R} I_{\{t_X f_1(u)\ge t_Y f_2(u)\}}D_k(x+u,t_X f_1(u), t_Y f_2(u))\,{\mathrm{d}} u \notag \\[5pt] &\quad +\int_{\mathbb R} I_{\{t_X f_2(u)< t_Y f_1(u)\}}D_k(x+u,t_X f_2(u), t_Y f_1(u))\,{\mathrm{d}} u.\end{align*}

When $u,x,t_Y$ are fixed,

\begin{align*} D_k(x+u,t_X f_1(u), t_Y f_2(u))\quad\text{and}\quad D_k(x+u,t_X f_2(u), t_Y f_1(u))\end{align*}

are increasing functions of $t_X$ . Moreover,

\begin{align*}& D_k(x+u,t_X f_1(u), t_Y f_2(u))\ge 0\quad \text{when $t_X f_1(u)\ge t_Y f_2(u)$,}\\[5pt] & D_k(x+u,t_X f_2(u), t_Y f_1(u))\le 0\quad \text{when $t_X f_2(u)< t_Y f_1(u)$.}\end{align*}

So the two integrands in the above two integrals are both increasing functions of $t_X$ .

Hence we obtain that $D_{k+1}(x,t_X,t_Y)$ is an increasing function of $t_X$ when $x,t_Y$ are fixed, and complete the proof.

Now let $t_X=\xi_0$ , $t_Y=1-\xi_0$ . Then

\begin{align*} D_n(x,t_X,t_Y)=\Delta_n(x,\xi_0).\end{align*}

By Lemma 4.4 and $D_n(x,t_X,t_Y)=-D_n(x,t_Y,t_X)$ , we get the desired fact.

Now we are ready to prove Theorem 4.1.

Proof of Theorem 4.1. Firstly, we assume that condition (I) holds and prove the optimality of $\textsf{M}^n$ . This can be easily obtained by Theorem 3.1 and Corollary 4.1. We now use mathematical induction.

When $n=1$ , by Corollary 4.1,

\begin{align*}\Delta_{1}(x,\xi_0)=\mathbb{E}_{\xi_0} [\varphi(x+X_{1})]-\mathbb{E}_{\xi_{0}}[\varphi(x+Y_{1})]\end{align*}

is an increasing function of $\xi_0$ for any fixed x. Since $\Delta_{1}(x,\frac{1}{2})=0$ , then the optimal strategy should choose X first if $\xi_0\ge \frac{1}{2}$ and choose Y first if $\xi<\frac{1}{2}$ . This means that $\textsf{M}^1$ is the optimal strategy of the $(\xi_0,1,x)$ -bandit, for any $x\in\mathbb{R}$ and $\xi_0\in[0,1]$ .

Assume that for fixed $k\ge 1$ , the myopic strategy $\textsf{M}^k$ is optimal for $(\xi_0,k,x)$ -bandits, for any $x\in\mathbb{R}$ and $\xi_0\in[0,1]$ .

Now consider a bandit problem with $k+1$ trials. Note that by definition of $\textsf{M}^{k+1}$ , $\textsf{L}^{k+1}$ , and $\textsf{R}^{k+1}$ , there is

\begin{align*} W(\xi_0,k+1,x,\textsf{M}^{k+1})=\begin{cases}W(\xi_0,k+1,x,\textsf{L}^{k+1}) & \text{if $\xi_{0}\geq\frac{1}{2}$,}\\[5pt] W(\xi_0,k+1,x,\textsf{R}^{k+1}) & \text{otherwise.}\end{cases}\end{align*}

By Lemmas 3.1 and 3.2 we know that

\begin{align*}W(\xi_0,k+1,x,\textsf{L}^{k+1})& =\mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{k+1} Z_i^{\textsf{L}^{k+1}}\Biggr)\Biggr]\notag\\[5pt] & = \mathbb{E}_{\xi_{0}}\biggl[W\biggl(\dfrac{\xi_0f_1(X_1)}{\xi_0f_1(X_1)+(1-\xi_0)f_2(X_1)},k,x+X_1,\textsf{M}^{k}\biggr)\biggr],\\[5pt] W(\xi_0,k+1,x,\textsf{R}^{k+1})& =\mathbb{E}_{\xi_0}\Biggl[\varphi\Biggl(x+\sum_{i=1}^{k+1} Z_i^{\textsf{R}^{k+1}}\Biggr)\Biggr]\notag\\[5pt] & = \mathbb{E}_{\xi_{0}}\biggl[W\biggl(\dfrac{\xi_0f_2(Y_1)}{\xi_0f_2(Y_1)+(1-\xi_0)f_1(Y_1)},k,x+Y_1,\textsf{M}^{k}\biggr)\biggr].\end{align*}

By Corollary 4.1, $\Delta_{k+1}(x,\xi_0)$ is an increasing function of $\xi_0$ , $\Delta_{k+1}(x,\frac{1}{2})=0$ . By the induction hypothesis, $\textsf{M}^k$ is the optimal strategy of $\bigl(\frac{\xi_0 f_1(u) }{\xi_0 f_1(u) +(1-\xi_0)f_2(u)},k,x+u\bigr)$ -bandits and $\bigl(\frac{\xi_0 f_2(u) }{\xi_0 f_2(u) +(1-\xi_0)f_1(u)},k,x+u\bigr)$ -bandits, for $ u\in\mathbb{R}$ . Then we have

\begin{align*}&W\bigl(\xi_0,k+1,x,\textsf{M}^{k+1}\bigr) \notag \\[5pt] &\quad =\max\bigl\{W\bigl(\xi_0,k+1,x,\textsf{L}^{k+1}\bigr),W\bigl(\xi_0,k+1,x,\textsf{R}^{k+1}\bigr)\bigr\} \notag\\[5pt] &\quad =\max\biggl\{\mathbb{E}_{\xi_{0}}\biggl[V\biggl(\dfrac{\xi_0f_1(X_1)}{\xi_0f_1(X_1)+(1-\xi_0)f_2(X_1)},k,x+X_1\biggr)\biggr], \notag\\[5pt] &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbb{E}_{\xi_{0}}\biggl[V\biggl(\dfrac{\xi_0f_2(Y_1)}{\xi_0f_2(Y_1)+(1-\xi_0)f_1(Y_1)},k,x+Y_1\biggr)\biggr]\biggr\}.\end{align*}

Therefore, by Theorem 3.1,

\begin{align*}W(\xi_0,k+1,x,\textsf{M}^{k+1})=V(\xi_0,k+1,x).\end{align*}

Hence $\textsf{M}^{k+1}$ is the optimal strategy of $(\xi_0,k+1,x)$ -bandits, for any $x\in\mathbb{R}$ and $\xi_0\in[0,1]$ . The first part of the main theorem is proved.

Now we prove that if the strategy $\textsf{M}^n$ is optimal for $(\xi_0,n,x)$ -bandits, for any integer $n\ge 1$ , for all $ \xi_0\in[0,1]$ , $ x\in \mathbb{R}$ , then condition (I) holds.

Indeed, we only need to consider the case when $n=1$ . For any fixed $x\in\mathbb{R}$ , we have

\begin{align*}\mathbb{E}_{\xi_0}[\varphi(x+X_1)]&=\xi_0\int_{\mathbb R}\varphi(x+u)f_1(u)\,{\mathrm{d}} u+(1-\xi_0)\int_{\mathbb R} \varphi(x+u)f_2(u)\,{\mathrm{d}} u,\\[5pt] \mathbb{E}_{\xi_0}[\varphi(x+Y_1)]&=\xi_0\int_{\mathbb R}\varphi(x+u)f_2(u)\,{\mathrm{d}} u+(1-\xi_0)\int_{\mathbb R} \varphi(x+u)f_1(u)\,{\mathrm{d}} u.\end{align*}

Since the strategy $\textsf{M}^1$ which chooses X if and only if $\xi_0\ge \frac{1}{2}$ is the optimal strategy, we know that

\begin{align*}\mathbb{E}_{\xi_0}[\varphi(x+X_1)]-\mathbb{E}_{\xi_0}[\varphi(x+Y_1)]\ge 0\quad \text{if $\xi_0\ge \frac{1}{2}$.}\end{align*}

Then, for any fixed $x\in\mathbb{R}$ , we have

\begin{align*}(2\xi_0-1)\biggl[ \int_{\mathbb R}\varphi(x+u)f_1(u)\,{\mathrm{d}} u-\int_{\mathbb R}\varphi(x+u)f_2(u)\,{\mathrm{d}} u\biggr]\ge 0\quad \text{if $\xi_0\ge \frac{1}{2}$,}\end{align*}

which leads to

\begin{align*}\int_{\mathbb R}\varphi(x+u)f_1(u)\,{\mathrm{d}} u-\int_{\mathbb R}\varphi(x+u)f_2(u)\,{\mathrm{d}} u\ge 0.\end{align*}

This is clearly condition (I).

Theorem 4.1 gives a reasonable condition on $\varphi$ that is necessary and sufficient for the myopic strategy $\textsf{M}^n$ being the optimal strategy. With Theorem 4.1 in hand, we can immediately obtain the following two corollaries. The first corollary is the same as the result of Feldman [Reference Feldman14], obtained by applying Theorem 4.1 on the $\varphi(x)=x$ case. The second corollary answers Nouiehed and Ross’s conjecture for the two-armed case.

Corollary 4.2. (Feldman.) The myopic strategy $\textsf{M}^n$ is optimal for $(\xi_0,n,x)$ -bandits with utility function $\varphi(x)=x$ , for any integer $n\ge 1$ , for all $ \xi_0\in[0,1]$ , $ x\in \mathbb{R}$ , if and only if

\begin{align*}\mathbb{E}_\mathbb{P}[X_1\mid H_1]\ge \mathbb{E}_\mathbb{P}[Y_1\mid H_1].\end{align*}