{'fraction_non_alphanumeric': 0.05277929210329719, 'fraction_numerical': 0.015082682173359986, 'mean_word_length': 3.8868278243709917, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bandit problems with Levy payoff processes

We study two-armed Levy bandits in continuous-time, which have one safe arm that yields a constant payoff s, and one risky arm that can be either of type High or Low; both types yield stochastic payoffs generated by a Levy process. The expectation of the Levy process when the arm is High is greater than s, and lower than s if the arm is Low. The decision maker (DM) has to choose, at any given time t, the fraction of resource to be allocated to each arm over the time interval [t,t+dt). We show that under proper conditions on the Levy processes, there is a unique optimal strategy, which is a cut-off strategy, and we provide an explicit formula for the cut-off and the optimal payoff, as a function of the data of the problem. We also examine the case where the DM has incorrect prior over the type of the risky arm, and we calculate the expected payoff gained by a DM who plays the optimal strategy that corresponds to the incorrect prior. In addition, we study two applications of the results: (a) we show how to price information in two-armed Levy bandit problem, and (b) we investigate who fares better in two-armed bandit problems: an optimist who assigns to High a probability higher than the true probability, or a pessimist who assigns to High a probability lower than the true probability.


Introduction
Consider a firm that has to determine, on an ongoing basis, how much to invest in the research of new technologies for its next line of products. The firm faces a tradeoff between exploration and exploitation: on the one hand, it can adopt the technology that seems most successful according to the research conducted so far, thereby exploiting its investment in research, but on the other hand, it could continue investing in various technologies, in the hope of finding an even better technology for its products. If the firm decides to stop investing in a given technology, then no information will be obtained on that technology, so even if it is actually better than the finally adopted technology, it will never be adopted.
A similar tradeoff between exploration and exploitation arises, e.g., in the market of venture capital funds, where each fund has to decide in which start-up companies to invest, and in clinical trials, where pharmaceutical companies have to decide which new drugs or treatments to explore.
To concentrate on the trade off between exploration and exploitation, one assumes that there are no exogenous factors that affect the firm's decision (such as new technologies or drugs that are introduced by competitors). The optimization problem that the firm faces has been modeled in the literature as a multi-arm bandit problem (see, e.g., Rothschild (1974), Bergemann and Välimäki (2006), Keller, Rady and Cripps (2005), Besanko and Wu (2008), Klein and Rady (2008), Moscarini and Squintani (2004), Roberts and Weitzman (1981), Weitzman (1979)): a decision maker (DM) has finitely many actions, called arms, each one yields a payoff with an unknown distribution, that is taken from a finite set of distributions. Each time the DM chooses an arm, he obtains a payoff, and improves his information regarding the correct payoff distribution of the arm he has just chosen. Gittins and Jones (1979) proved that, in discrete-time, the optimal strategy of the DM has a particularly simple form: at every period the DM calculates a real number, an index, for each arm, based on past observations of that arm, and he chooses the arm with the highest index. It turns out that to calculate the index of an arm it is sufficient to consider an auxiliary problem with two arms: the arm for which we calculate the index, and an arm that yields a constant payoff. The literature therefore focuses on such problems, called two-armed bandit problems.
Once the optimality of the index strategy is guaranteed, one looks for the relation between that data of the game and the index. Explicit formulas for the index when the payoff is one of two distributions that have a simple form has been established in the literature. Berry and Friestedt (1985) provide the solution to the problem in discrete-time, e.g., when the payoff distribution is one of two Bernoulli distributions, and in continuous-time, e.g., when the payoff distribution is one of two Brownian motions. In continuous-time, by studying the dynamic programming equation that describes the problem, Keller, Rady and Cripps (2005) and Keller and Rady (2008) provided an explicit form for the index when the payoff's distribution is Poisson. 1 When the payoff distribution is known, Karatzas (1984) characterized the index when the payoff's distribution is a diffusion process, and Kaspi and Mandelbaum (1995) characterized the index when the payoff's distribution is a Lévy process, and they obtained an explicit form for the index for special distributions.
In practice, payoff processes have a complex form, exhibiting both small random changes, that can be modeled by a Brownian motion, and large shocks that can be modeled as arriving at a Poisson rate. A stochastic process that incorporates these two types of changes is the Lévy process. In fact, Carr and Wu (2004) argue that almost all economic phenomena can be described by time shifts of Lévy processes. Therefore, it is desirable to study the bandit problem where the payoff distribution is one of finitely many Lévy distributions.
In the present paper we provide an explicit solution to the two-armed bandit problem where the payoff distribution is one of two Lévy processes. We assume that one distribution, called High, dominates the other, called Low, in a strong sense (see Assumption 2.1 below). To eliminate trivial cases, we assume that the expected payoff that is generated by the safe arm is lower than the expected payoff generated by the High distribution, and higher than the expected payoff generated by the Low distribution.
In such a case in discrete-time, the optimal strategy is a cut-off strategy: the DM keeps on experimenting as long as the posterior belief that the distribution is High is higher than some cut-off point, and, once the posterior probability that the distribution is High falls below the cut-off point, the DM switches to the safe arm. We prove that when the two payoff distributions are Lévy processes that satisfy several requirements, the optimal strategy is a cut-off strategy, and we provide an explicit expression for the cut-off point, in terms of the data of the problem. When particularized to the models studied by Kaspi and Mandelbaum (1995), Bolton and Harris (1999), Keller, Rady and Cripps (2005) and Keller and Rady (2008), our expression reduces to the expressions that they obtained.
Apart of unifying previous results, our characterization shows that the special form of the optimal payoff derived by Bolton and Harris (1999) and Keller, Rady and Cripps (2005) is valid in a general setup: the optimal payoff is the sum of the expected payoff if no information is available, and of an option value, that measures the expected gain from the ability to experiment. It also shows that the data of the problem can be divided into information-relevant parameters and payoff-relevant parameters; the information-relevant parameters can be summarized in a single real number, and the payoff-relevant parameters are the expectations of the processes that contribute to the DM's payoff. Finally, the characterization allows one to derive comparative statics on the optimal cut-off and payoff. For example, as the discount rate increases, or the signals become less informative, the cut-off point increases but the DM's optimal payoff decreases.
It is often the case that the DM holds an incorrect prior, and plays optimally given that prior (for further discussion and literature review, see Section 2.4). We provide an explicit expression for the value function in this case. Our technique provides a new description of the optimal strategy with a time dependent cut-off.
So far we have assumed that all the information that the DM has is the payoff process. Sometimes, the DM has information that does not contribute to the payoff process, yet it helps him learn the type of risky arm. For example, scientific discoveries made by other firms in other markets may shed light on the appropriateness of a given technology to a product that a firm develops. In addition, part of the payoff of the DM may not be observed by the DM.
In Section 2.5 we study a bandit problem, in which the risky arm generates three Lévy processes -the first is observed by the DM and contributes to the payoff, the second is observed by the DM and does not contribute to the payoff, and the third is not observed by the DM but it contributes to the payoff. We provide an explicit expression for the cut-off and for the optimal payoff of the DM. That generalizes the expression we found when the risky arm generates only one process. This analysis clarifies the distinction between information-relevant data and payoff-relevant data.
We conclude the paper by applying our characterization to compare the effects of optimism and pessimism in bandit problems. A DM is called optimist if his prior probability that the payoff's distribution is High is higher than the true probability, and he is called a pessimist if his prior probability that the payoff's distribution is High is lower than the true probability. Using our characterization we find that unless the pessimist assigns high probability to the High type and the two DM's are sufficiently patient, an optimist will fare better than a pessimist.
The rest of the paper is arranged as follows. The model and the main results appear in Section 2. Directions for future research appear in Section 3. All proofs appear in Section 4.

2.1.
Reminder about Lévy Processes. Lévy processes are the continuous-time analog of discrete-time random walks with i.i.d. increments. A Lévy process X = (X(t)) t≥0 is a continuous-time stochastic process that (a) starts at the origin: X(0) = 0, (b) admits càdlàg modification, 2 and (c) has stationary independent increments. See figures 1 and 2 for a generic path of a Lévy process. A few examples of Lévy processes are a Brownian motion, a Poisson process, and a compound Poisson process. The latter is a continuous-time process in which jumps arrive according to a Poisson process and the jumps are i.i.d. 3 We now present the Lévy-Ito decomposition of Lévy processes. Let (X(t)) be a Lévy process. For every Borel measurable set A ⊆ R\{0}, define: This is the expected number of jumps with size in A that occurs up to time 1. One can verify that ν is a measure, called the Lévy measure of the process. The quantity ν(R\{0}) is the expected number of jumps that occur up to time 1. If ν(R\{0}) = ∞, then the number of jumps in the time interval [0, 1], and therefore in any compact time interval, is infinite a.s., and we say that the Lévy measure is infinite. If ν(R\{0}) < ∞, then the expected number of jumps in any compact time interval is finite a.s., and we say that the Lévy measure is finite. In this paper we study Lévy processes that have finite Lévy measures. The results can be generalized for Lévy processes with infinite Lévy measures, see Cohen and Solan (2009).
The Lévy-Ito decomposition (see Applebaum (2004)) states that every Lévy process with finite Lévy measure can be represented as follows: where µt is a linear drift, σZ(t) is a Brownian motion with standard deviation σ, and L ν (t) is a compound Poisson process with Lévy measure ν which is independent of σZ(t): jumps arrive at a Poisson rate with expectation ν(R\{0}), and the distribution of each jump is given by the distribution function ν(dh) ν(R\{0}) .

Lévy Bandits.
A DM operates a two-armed bandit machine in continuoustime, with a safe arm that yields a constant payoff s, and a risky arm that yields a stochastic payoff (X(t)). The risky arm can be of two types, High or Low. We denote the arm's type by θ: if the type is High (resp. Low) we set θ = θ 1 (resp. θ 2 ). If θ = θ i , i ∈ {1, 2}, the risky arm yields payoff (X i (t)), which is a Lévy process. We assume throughout that the Lévy measures of both (X 1 (t)) and (X 2 (t)) are finite, and therefore a.s. there are only finitely many jumps in each compact time interval. Denote the Lévy-Ito decomposition of ( 2 That is, it is continuous from the right, and has limits from the left: for every t 0 , the limit 3 Formally, let λ > 0, and let D be a distribution over R\{0}. A compound Poisson process with rate λ and jump size distribution D is a continuous-time stochastic process given by X(t) = where N (t) is a Poisson process with rate λ, and D i are i.i.d. random variables, with distribution function D, which are also independent of (N (t)) t≥0 .
Setν i := ν i (R \ {0}), and denote by H i := hν i (dh)/ν i the expected jump size of (X i (t)). 4 We assume that H i is finite. The quantity hν i (dh) =ν i H i is the contribution of the compound Poisson process to the instantaneous payoff. The expectation of the risky arm at time t Throughout we make the following assumption, which states that the High type is better than the Low type in a strong sense.
Assumptions A1 and A2 rule out trivial cases. Assumption A1 merely says that the High (resp. Low) type provides higher (resp. lower) expected payoff than the safe arm. Assumption A2 states that the Brownian motion component of both the High type and Low type have the same standard deviation. Otherwise, since the realized path reveals the standard deviation, the DM can distinguish between the arms in any infinitesimal time interval.
The third part of the assumption is less innocuous; it requires that the Lévy measure of the High type will dominate the Lévy measure of the Low type in a strong sense: roughly, jumps of any size h occur more often (or at the same rate) under the high type than under the Low type.
A consequence of this assumption is that jumps always provide good news, and (weakly) increase the posterior probability of the High type.
At each time instance t, the DM chooses the proportion of time to devote to each of the two arms. If he chooses to devote a proportion k of the current time instance to the risky arm, then the instantaneous payoff dY k is the sum of several terms: • (1 − k)sdt, which is the contribution of the safe arm; • kµ i dt, which is the contribution of the linear drift; • √ kσdZ(t), which is the contribution of the Brownian motion; 5 • kH i dt, which is the contribution of the compound Poisson process. A strategy κ is a (measurable) function, that assigns to each history a number in the interval [0, 1], that is interpreted as the amount of time in the interval [t, t + dt) devoted to the risky arm. In continuous time, it is usually assumed that a strategy is predictable, that is, to determine the behavior at time t, it is sufficient to know the history strictly before time t. Formally, κ t is F I t− -measurable, where I(t) := t 0 re −rt dY κ (t) is the stochastic discounted payoff using the strategy κ, and F I t− is the σ-algebra generated by the stochastic process (I(t)) of the discounted payoff with discount rate r, up to (excluding) time t.
As is well known , in continuous-time the play path need not be uniquely defined, and therefore one should be careful in defining the set of strategies available to the DM, and the play path that a strategy defines. We circumvent this issue by arguing that an optimal strategy must solve a certain Functional Differential Equation 4 In order to simplify notation, we denote R hν i (dh) := R R\{0} hν i (dh). 5 By devoting the proportion κ of the time interval [t, t + dt) to the risky arm, the variance of the continuous part of the payoff is κσ 2 dt. This explains the scaling parameter √ kσ. For a qualitative explanation for this form, see Bolton and Harris (1999).
(FDE), by showing that this FDE has a unique solution, and by exhibiting this solution. As for discrete-time, this solution turns out to be a cut-off strategy, which we now define.
Let p t := P (θ = θ 1 |F I t− ) be the posterior belief at time t that the risky arm is High. A strategy κ is a cut-off strategy with cut-off point p if the DM chooses the safe arm (with probability 1) whenever p t ≤ p, and the risky arm (with probability 1) whenever p t > p. We now argue that Assumption A3 guarantees that the play under a cut-off strategy is well defined. Suppose that p 0 > p. Then the DM chooses the risky arm until the first time t that satisfies p t = p. Since the Lévy payoff processes have finite measures, Assumption A3 implies that in an infinitesimal interval after time t the posterior belief will drop below the cut-off. Indeed, the first time t satisfying p t = p is a predictable stopping time, and therefore, the probability that a jump occurs atthat time is zero (see Bertoin (1996)). Therefore, If there is a Brownian motion component, its fluctuations will cause the posterior to drop below p in an infinitesimal time interval after time t. If there is no Brownian motion component, since the Lévy measure is finite, there are no jumps in an infinitesimal time interval, and by Assumption A3 the compound Poisson process will cause the posterior to drop below p. This implies that the play under a cut-off strategy is well defined.
2.3. The Optimal Strategy. The expected discounted payoff under a strategy κ when the prior is p 0 = p is Let U (p) = sup κ V κ (p) be the maximal payoff the DM can achieve. As we show below, the DM has an optimal strategy, so in fact the supremum in the definition of U (p) is achieved. The function V κ (p) is linear with respect to p, and therefore U (p), as the supremum of linear functions, is convex. By always choosing the safe arm, the DM can achieve at least s; since U (0) = s, the convexity of U (p) implies that U is non-decreasing.

Proposition 2.2. U (p) is monotone non-decreasing, convex, and continuous in p.
It follows from Proposition 2.2 that there is p * such that U (p) = s if p ≤ p * and U (p) > s otherwise, so that the strategy κ ≡ 0 that always chooses the safe arm is optimal for prior beliefs in [0, p * ].
Our first theorem states that there is a unique optimal strategy, which is a cut-off strategy. Moreover it provides the exact cut-off point and the corresponding expected payoff in terms of the data of the problem. Let α be the unique solution of The term pg 1 + (1 − p)g 2 in (2.3) is the expected payoff for a DM choosing only the risky arm. Thus, C α (1 − p)( 1−p p ) α is the option value for the ability to switch to the safe arm. The quantity α summarizes all the information-relevant parameters of the problem (see also Section 2.5). Apart from that, the parameters of the payoff processes that determine the cut-off point p * and the optimal payoff U (p) are the expected payoffs g 1 and g 2 .
The function in (2.3) has the same structure as the solution of Bolton and Harris (1999) and Keller, Rady and Cripps (2005) for the one agent problem. In Bolton and Harris (1999), the only component in the risky arm is the Brownian motion with drift. Therefore ν i ≡ 0, so that g 1 = µ 1 , g 2 = µ 2 , and α = (−1 + 1 + 8rσ 2 /(µ 1 − µ 2 ) 2 )/2. In Keller, Rady and Cripps (2005), the risky arm is either the constant zero (Low type, so that ν 2 ≡ 0), or yields a payoffh according to a Poisson process with rate λ (High type). If the risky arm is High, the only component in the Lévy-Ito decomposition is the compound Poisson component, and ν 1 (h) = λ and zero otherwise. Therefore, g 1 = λh, g 2 = 0, and α = r/λ.
The explicit form of the cut-off point p * and of the value function U allows us to derive simple comparative statics. As is well known, a DM who plays optimally switches to the safe arm later than a myopic DM, and indeed, p * is smaller than the myopic cut-off point p m := s−g2 g1−g2 . Furthermore, the cut-off point p * is an increasing function of α. As can be expected, α (and therefore also p * ) increases at the discount rate r and at ν 2 (dh), and it decreases at ν 1 (dh) and at |µ 1 − µ 2 |: the DM switches to the safe arm earlier as the discount rate increases, as jumps provide less information, or as the difference between the drifts of the two types increases. 7 Furthermore, as long as p > p * , the value function U (p) decreases in α. Thus, decreasing the discount rate, increasing the informativeness of the jumps and the difference between the drifts is beneficial to the DM. 6 To ensure the existence of the Radon-Nikodym derivative, and therefore the form of the solution, one does not need the full power of Assumption A3. Its full power will be used within the proof. 7 Moreover, α(r = 0) = 0 and α(r = ∞) = ∞.
In Section 2.4 we extend the results to the case that the prior belief of the DM is not the true prior p 0 . In Sections 2.6 and 2.5 we provide two applications to our techniques and results.
Remark 2.4. Incomplete information of p 0 . Suppose that the DM does not know the prior belief p 0 , but rather has some belief ϕ over p 0 . That is, p 0 is chosen at the outset according to ϕ, and is not told to the DM. From the DM's point of view, the situation is equivalent to an auxiliary problem in which the prior probability of the High type is the expectation of the corresponding probability in the original problem, and therefore Theorem 2.3 provides the optimal strategy in this case as well.
2.4. The Payoff with Incorrect Prior. In decision problems it is usually assumed that the DM either knows the true state of nature, or has some prior distribution over the set of states of nature. Experiments show that the prior distribution that DMs have is often different than the true prior. The phenomenon of overconfidence -assigning too high a probability to the good state of nature -has been observed in various areas (Svenson (1981), Baumhart (1968), Larwood and Whittaker (1977), Cross (1977), Weinstein (1980), Camerer and Lovallo (1999)). Babcock and Loewenstein (1997) argue that biases in bargaining may be self-serving, and Heifetz, Shannon and Spiegel (2007) show that biases of preferences may be stable.
In every decision problem, a DM who correctly perceives the prior distribution will fare better than a DM who has some bias, and believes that the prior distribution is different than the correct one. Indeed, an optimal strategy of a DM who correctly perceives the prior distribution is a strategy that yields the highest possible gains for this prior distribution, so it yields at least as much as any other strategy, in particular, optimal strategies for incorrect prior distributions.
Denote the initial belief of the DM for the High type by q 0 , and suppose that it may be different from the true probability p 0 . By Theorem 2.3, the optimal strategy of the DM is a cut-off strategy, however, since he has an incorrect prior, he does not switch to the safe arm at the optimal time. In this section we give an exact formula for the payoff, assuming the DM plays optimally given his belief. We will also describe the optimal strategy from a different point of view, not as a cut-off strategy. This point of view is arguably closer to the way people perceive the decision problem that the DM faces.
Suppose that until time t, the DM chose the risky arm, and observed the jumps h 1 , ...h n from the compound Poisson component of the payoff process. Let Y 1 B (t) be the Brownian motion with drift component of the payoff process from the risky arm at time t. Note that Y 1 B (t) ∼ N (µt, σ 2 t). The posterior belief .
is the probability of receiving the n jumps that occurred until time t, given the type θ i . The first equality in (2.4) is the Bayesian belief updating, using the independence of the components in the Lévy-Ito decomposition, given the type of the risky arm, and the second equality is obtained by eliminating common components. For a generic path of the process (q t ), see figure 3.
Suppose the DM follows a cut-off strategy κ ′ with cut-off point p ′ : If q 0 ≤ p ′ , the DM will always choose the safe arm. If q 0 > p ′ , the DM will initially choose the risky arm. The DM chooses the risky arm as long as q t > p ′ , which, by Eq. (2.4), is equivalent to: Without loss of generality assume that µ 1 − µ 2 > 0; the case µ 1 − µ 2 < 0 is handled similarly, and provides the same results. By taking the natural logarithm, and rearranging the resulting terms, we obtain that this inequality is equivalent to: The right-hand side in (2.6) is a piecewise linear function is independent of t, the intercept at t = 0 is ν2(dh) the contribution of a jump of size h to the intercept.
is the product of ν i (dh j ) over all jumps h j that occur up to time t−. Similarly, we use the notation P t− for the sum over all jumps up to time t−.
From Eq. (2.6) we obtain the following alternative description of the optimal strategy: The DM has a time-dependent cut-off which is piecewise linear. The slope of the cut-off function is always F , and whenever there is a jump of size h, the cut-off decreases by G h (see Figure 4). The DM chooses the risky arm as long as his current payoff from the continuous part of the Lévy process, Y 1 B (t), exceeds the cut-off.
Thus, at first the DM plays until the payoff from the continuous part divided by the standard deviation satisfies: if a jump of size h occurs before he switches to the safe arm, then the intercept decreases by G h , and this behavior repeats itself. If there is no Brownian motion component, then Y 1 B (t) ≡ 0 and F = 0; the DM chooses the risky arm for a fixed amount of time, and then switches to the safe arm, unless a jump occurs before the switch; if a jump occurred, the amount of time to choose the risky arm increases, as a function of ν1(dh) ν2(dh) . Theorem 2.5. Under Assumption 2.1, for every p 0 ∈ [0, 1], the payoff U (p 0 , q 0 ) of a DM who uses a cut-off strategy with cut-off point p ′ , is as follows: 9 One can verify that when the DM holds the correct prior, and plays according to the optimal strategy κ * , Eq. (2.7) coincides with (2.3): U (p 0 , p 0 ) = U (p 0 ). Note that U (p 0 , q 0 ) is continuous in all its parameters. To calculate the payoff of a DM who plays optimally but has an incorrect prior, simply substitute the expression for p * from Theorem 2.3 as p ′ in Theorem 2.5.
2.5. Information and Payoff. Theorems 2.3 and 2.5 express the optimal cut-off, the optimal expected payoff, and the expected payoff for a DM with incorrect prior who uses a cut-off strategy in terms of the expected payoff of each arm, and the quantity α, which captures all the information-relevant parameters of the payoff processes. In this section we justify why α indeed captures all the informationrelevant parameters. This justification explains why the solutions of Bolton and Harris (1995) and Keller, Rady and Cripps (2005) have the same structure as our solution. Suppose the DM faces a two-armed bandit problem with Lévy payoffs. If the risky arm's type is High (resp. Low), it yields three independent Lévy processes (X a , (X c 2 (t))). As in Section 2.2, the notation µ j i , σ j i , ν j i , and g j i , represents the drift of the process (X j i (t)), the standard deviation of the Brownian motion component of (X j i (t)), the Lévy measure of the process (X j i (t)), and the expectation of the process (X j i (t)) at time t = 1, respectively, where j ∈ {a, b, c}, and i ∈ {1, 2} is the arm's type.
Suppose that the DM's payoff is X a i + X c i , while his information is (X a i , X b i ). Thus, the component X a i represents observed information of the DM that contributes to his payoff, the component X b i represents observed information that does not contribute to the payoff, and the component X c i represents unobserved information that contributes to the payoff. The following theorem characterizes the optimal strategy of the DM in this setup, as well as his expected payoff when he holds a possibly incorrect prior. This characterization can be used to calculate the fair price of additional information.
Let β be the unique solution of Theorem 2.6. The expected payoff to a DM who holds the prior belief q 0 , uses a cut-off strategy κ ′ with cut-off point p ′ , receives and observes the payoff process (X a (t)), observes but does not receive the payoff process (X b (t)), and receives but does not observe the payoff process (X c (t)), is as follows Moreover, the optimal cut-off for a DM who holds the correct prior, i.e. q 0 = p 0 , is given by .
Observe that if there are no processes (X b i , X c i ), then Theorem 2.6 reduces to Theorem 2.5. Moreover, the parameter β in Theorem 2.6 is the equivalent of α in Theorem 2.5.
The characterization in Theorem 2.6 shows that β incorporates all the data that is relevant to the information that the DM has. It depends on the parameters of (X a i , X b i ), which the DM observes, but not on the parameters of (X c i ), which the DM does not observe. Moreover, it depends on the absolute value of the difference between the drifts, |µ 1 − µ 2 |, the standard deviation of the Brownian motion, σ, the Radon-Nikodym derivative ν2(dh) ν1(dh) , and the average ην 1 + (1 − η)ν 2 . These quantities help in distinguishing between the two types of the Risky arm. Once the information-relevant parameters are summarized in β, the only relevant parameters, which affect both the optimal cut-off and the optimal expected payoff, are the expectations of the payoff-relevant processes (g a i , g c i ).
Theorem 2.6 can be used to find the fair price of the additional information X b and of X c . That is, the price of information that does not affect the DM's payoff, as well as the price of information that affects the DM's payoff. This is done by comparing the optimal value of two bandit problems that differ in the information of the DM.
The next corollary to Theorem 2.6 states that, using cut-off strategies, additional information is more profitable. 10 Corollary 2.7. Suppose that there are two decision makers, DM1 and DM2, who hold the correct prior, i.e. q 0 = p 0 , and use cut-off strategies. DM1 receives and observes the payoff process (X a (t)), observes but does not receive the payoff process (X b (t)), and receives but does not observe the payoff process (X c (t)). DM2 receives and observes the payoff process (X a (t)), and receives but does not observe the payoff process (X c (t)). Then the optimal expected payoff of DM1 is higher than the optimal expected payoff of DM2.
2.6. Optimism vs Pessimism. As mentioned before, the phenomenon of over confidence is common in many decision problems. In this section we apply the result of Section 2.4, and investigate who will fare better in two-armed bandit problems, an optimist who assigns a probability higher than the true probability to the High type, or a pessimist who assigns a probability lower than the true probability to the High type.
Suppose that there are two decision makers, DM1 and DM2, who face independent identical copies of the decision problem. DM1 is an optimist, and believes that the probability of High is p 0 + ρ, where ρ > 0, while DM2 is a pessimist, and believes that the probability of High is p 0 − ρ, and both play optimally given their beliefs. If p 0 − ρ ≤ p * , the pessimist will always choose the safe arm, since according to his subjective belief the prior is at most the cut-off. Assume then that p 0 − ρ > p * . For every ǫ ∈ [p * − p 0 , 1 − p 0 ] denote by V p0 (ǫ) the expected payoff for a DM playing optimally according to the incorrect prior p 0 + ǫ, where ǫ may be negative. It turns out that the answer regarding who will fare better, an optimist or a pessimist, depends on α that is defined in Eq. (2.2).
Thus, an optimist will fare better than a pessimist, unless α is low and p 0 − ε is high. That is, a pessimist will fare better only if the following two conditions are satisfied: 1) The pessimist assigns high probability to the High type.
2) The two DM's are sufficiently patient, or it is easy to distinguish between the 10 It is well known that in one-player optimization problems, additional information cannot hurt the DM, since he can always ignore it. However, a Markovian cut-off strategy does not allow a player to forget additional information, and therefore the statement is not trivial. two types of the risky arm. Otherwise, an optimist will fare better.
We obtain the same result if the biases of the optimist and the pessimist are geometric rather than absolute, that is, if the initial prior of the optimist is (1 + ǫ)p 0 = p 0 + ǫp 0 and the initial prior of the pessimist is (1 − ǫ)p 0 = p 0 − ǫp 0 . This is true since the absolute bias of the optimist and the pessimist is the same: ǫp 0 .

Future directions
Our results call for further research. We here list few possible directions for future research.
• We studied the case that the distribution of the High type dominates the distribution of the Low type in a strong sense (see Assumptions 2.1). These assumptions ensure that the discontinuities of the process of posterior belief are always to one direction. It would be interesting to know whether a similar characterization holds under only assumptions A1 and A2. • We assumed that the payoff is distributed according to a Lévy process.
It would be interesting to solve the model when the payoff is distributed according to a geometric Lévy process.

The Control Equation.
In this section we express the optimal payoff U (p) using the dynamic programming principle. This representation extends that in Bolton and Harris (1999) to the more general setup of Lévy payoff processes. we start by calculating how the belief of the DM is updated given his observations. To simplify notation, it is convenient to divide various expressions by the standard deviation σ; setμ 1 = µ1 σ ,μ 2 = µ2 σ andμ = µ σ , and denote dỸ k B := 1 √ kσ dY k B = √ kμdt + dZ(t), modulo the factor √ κσ, dỸ k B is the contribution to the payoff of the linear drift and the Brownian motion. Then the probability of obtaining a specific observation (that is not a jump) given the type is: Let p = P t (θ 1 ) be the belief at time t that the risky arm is High. Then: . This is the Bayesian belief updating, using the independence of the components in the Lévy-Ito decomposition, given the risky-arm type θ. The next lemma expresses the change in the posterior belief over time. The lemma handles separately the case where there are no jumps in the time interval [t, t + dt), and the case where there is a jump in this interval.
dt is a standard Brownian motion. 2. Suppose that during the interval [t, t + dt) a jump of size h occurred. Then: The first term in the right-hand side of (4.2) is the contribution of the continuous part of the payoff process to the change in the belief, while the second term is the contribution of the fact that no jump arrived. This latter contribution is negative due to Assumption A3. If a jump of size h occurs during the interval [t, t + dt), then the contribution of the continuous part of the payoff process is (μ 1 −μ 2 )(dỸ k B − √ k(μ 1 P h +μ 2 (1 − P h ))dt), and the compound Poisson process' contribution is P h := pν1(dh) pν1(dh)+(1−p)ν2(dh) . The latter is the Bayesian update of the probability that the risky arm is High given that a jump of size h occurred. Note that p < P h .
Proof of Lemma 4.1. The proof of the lemma is standard and non-inspiring. The first statement follows from a long chain of equalities. Assume that there is no jump in the interval [t, t + dt) In the calculations we used the fact that dZ = dỸ k B − √ k(pμ 1 + (1 − p)μ 2 )dt is a standard Brownian motion (see Bolton and Harris (1999)), and the Brownian motion properties: dZ 2 = dt, and dZdt = 0. We also ignored terms of order (dt) 3/2 and above.
We now prove the second statement.
We now formulate the control equation that describes the optimal payoff.
where k is the control variable. The first term within the maximization is the expected instantaneous payoff, and the second term is the discounted expected continuation payoff. The following lemma provides a more convenient form to the control equation, in terms of the derivatives of U .
Lemma 4.2. The following equality holds: there are no jumps in the interval [t, t + dt). In this case, using the Taylor expansion of U , and ignoring terms of order (dt) 3/2 and higher, we obtain that the optimal payoff is U (p +ďp) = U (p) + U ′ (p)ďp + 1 2 U ′′ (p)(ďp) 2 a.s., 11 whereďp is given by the right-hand side of (4.1).
With probability [pkν 1 (dh)dt + (1 − p)kν 2 (dh)dt] there is a jump of size h, and the optimal payoff is U During the subsequent calculations we use the following Eqs. This is the expectation of the change in the belief, given that no jump occurred during the interval [t, t + dt).
This is the second moment of the change in the belief, given that no jump occurred during the interval [t, t + dt).
This is the expected contribution of the Brownian motion part to the posterior belief, given that a jump of size h occurred during the interval [t, t + dt).
This is the second moment of the contribution of the Brownian motion part to the posterior belief, given that a jump of size h occurred during the interval [t, t + dt). In Eqs. (4.5) and (4.6), C 1 and C 2 are constants. Using the above notation, we 11 Since we can ignore terms or order (dt) 3/2 and higher, it is sufficient to consider the Taylor expansion up to the second derivative.
obtain from (CE): The second, third and fourth lines in (4.7) represent the expected continuation payoff given a jump of size h occurred during the time interval [t, t + dt), and the fifth line represents the expected continuation payoff given no jump occurred during the time interval [t, t + dt). Using (dt) 2 = 0, several of the terms in (4.7) vanish, and we obtain: Eliminating U (p) from both sides, and dividing by dt, we obtain (CE2) after simple algebraic manipulations, as desired.
From Eq. (4.7) it follows that the contribution of the continuation payoff given that a jump of size h occurred during the time interval [t, t + dt) is The parameters of the Brownian motion affect (4.9) only through C 1 and C 2 , and since C 1 and C 2 do not appear in Eq. (4.8), it follows that if a jump occurs during the time interval [t, t + dt), the information from the compound Poisson process has more impact than the information of the Brownian motion.
According to (CE2), the payoff is the maximum over the control variable k of the expectation of the current flow payoff [(1 − k)s + k(p(ν 1 H 1 + µ 1 ) + (1 − p)(ν 2 H 2 + µ 2 ))] plus the discounted value of the continuation payoff A solution κ to this maximization problem must satisfy: The function within the maximization in (CE2) is linear in k. Therefore, it achieves its maximum at k = 1 or k = 0, p-a.s. From Proposition 2.2, U (p) is non-decreasing and continuous, and therefore there is p * such that U (p) = s for every p ≤ p * . Thus k = 0 is optimal for p < p * . For every p > p * , we have U (p) > s, so that in this case k = 1 is optimal p-a.s. 12

4.3.
Characterizing the optimal strategy and the value. When it is optimal to play safe, that is, when the optimal solution of (CE) is k * = 0, we have U (p) = s. When it is optimal to play risky, that is, when the optimal solution of (CE) is k * = 1, it follows from Lemma 4.2 that U (p) solves the following functional differential equation: A solution U (p) for this equation must be smooth (Friedman (1969), p.56). 13 Therefore, U (p) satisfies Eq. (FDE) in (p * , 1) always, and k = 1 is optimal in (p * , 1). 12 Recall that Eq. (CE2) is satisfied p-a.s., since U ′ (p) and U ′′ (p) exist p-a.s. In the next Section we show that the optimal strategy is in fact a cut-off strategy. 13 To see that the conditions of Friedman (1969) are satisfied, substitute f (p) = R (pν 1 (dh) + (1 − p)ν 2 (dh))U " − U (p)(r + (pν 1 + (1 − p)ν 2 )). Since U (p) is continuous, so is f , and we get U ∈ C 2 , as Friedman (1969) requires.
Hence, there is an optimal cut-off strategy κ * with cut-off point p * .
The next lemma suggests one solution to Eq. (FDE). To prove it, substitute the expression for U (p) defined in Eq. (4.11) below into Eq. (FDE). Recall that 2)), that α is the unique solution of the equation f (η) = 0 in (0, ∞), and that p * and C α were defined in the statement of Theorem 2.3.
In order to see that the function U (p), defined above, actually solves (FDE), we use the fact that P h = pν1(dh) pν1(dh)+(1−p)ν2(dh) ≥ p * for every p > p * , ν 1 −a.s., which is equivalent to Assumption A3. Thus, the form of our solution crucially depends on this assumption.
In fact, one can verify that  Proof.
The function f is a continuous function that satisfies f (0) < 0 and f (∞) = ∞.
is increasing in η. Now, where the first inequality holds since η > 0 and by Assumption A3. The second inequality holds since − ln(x) + x − 1 > 0 for every x = 1. Therefore, g h (η) is increasing, as desired.
As mentioned before, there is an optimal cut-off strategy with corresponding payoff U . Lemmas 4.3, 4.4 and 4.5 prove that U is the unique solution of Eq. (FDE). We now prove Theorem 2.3, which provides an explicit form to the optimal strategy and to the payoff function.

Proof of Theorem 2.3.
Recall that κ * is the optimal cut-off strategy (with cut-off point p * ). To complete the proof of the theorem, we provide an explicit expression to p * and to U . To this end, we first prove that the right-hand derivative of U at p * is 0.
be the right derivative of U at the cut-off For every q 0 ∈ [0, 1], let κ(q 0 ) be the strategy that plays as κ, assuming the prior belief is q 0 rather then p 0 . Define M κ := ∞ 0 re −rt dY κ (t), the discounted payoff under the strategy κ.

Incorrect Prior.
To find the expected discounted payoff for a DM who plays according to an incorrect prior q 0 , we present here a condition which is equivalent to (2.6). Substituting Y 1 B (t) = µt + σZ(t) andμ = µ σ in (2.6), we get: ν2(dhj) . It follows that the DM selects the risky arm until the first time t is satisfied: Proof of Theorem 2.5. If the prior belief of the DM, q 0 , satisfies q 0 ≥ p ′ then there is a bijection relation between E and q 0 , If q 0 ≤ p ′ , then the DM always chooses the safe arm, which is equivalent to E = 0. Therefore, we will use the notation U (p 0 , E) instead of U (p 0 , q 0 ) when the former is more convenient. We now prove that under Assumption 2.1, for every p 0 ∈ [0, 1] and every E ∈ [0, ∞), the payoff of the DM is U (p 0 , E) = p 0 g 1 +(1−p 0 )g 2 +(s−g 1 )p 0 e −(μ1−μ2)(α+1)E +(s−g 2 )(1−p 0 )e −(μ1−μ2)αE .
Using Eq. (4.15), we construct an integral equation, to find the utility function for a DM who has a prior belief q 0 . Let τ be the stopping time of the first jump. Let T be the first time t satisfying (4.15). The DM chooses the risky arm until the stopping time T , and then he switches to the safe arm. The calculations use dynamic programming in which the continuation payoff is determined by the time of the first jump, τ , and the value of the continuous part of the payoff at that time.
Notation and Formulas. The proof requires computations that rely on some results on Brownian motion. In this subsection we provide these results, that are derived using Borodin and Salminen (1996) p.197 -223. Recall that,μ = µ σ is determined by θ. Notice that B µ (t) is a standard Brownian motion with drift . This is the probability that the first jump occurs in the interval [t, t+dt), and B µ belongs to [x, x+dx), given a jump occurs before the DM switches to the safe arm.
This is the posterior belief that the type is θ 1 , given that (a) the first jump that occurred in the time interval [t, t + dt) has size h; (b) it occurred before the DM switched to the safe arm; and (c) the Brownian motion with drift, B µ (t), is in the interval [x, x + dx).
The probability that the DM switches to the safe arm before the first jump appeared is The expected discounted payoff from the continuous part of the risky arm, until the switching time to the safe arm, given the DM switched before the first jump, is The expected discounted payoff from the safe arm, after the switching time to the safe arm, given the DM switched before the first jump, is The expected discounted payoff from the continuous part of the risky arm, until the first jump occurs, given the first jump occurred before the switching time, is The expression on the right-hand side of (4.19), can be re-written using the following list of equalities: where P θ (τ r > t) = e −(r+ν)t , and P θ (τ r > T ) = e −E(Fµ+ √ 2(ν+r)+F 2 µ ) . Similarly, the expression on the right-hand side of (4.20) can be re-written as follows: In the proof of Theorem 2.5 we use the following two identities: .
Where the first equality follows by (4.23).
Constructing the integral equation. The DM chooses the risky arm, until the minimum between the stopping time of the first jump τ and the stopping time T . We distinguish between two cases. In case the DM stops before the time of the first jump τ , we calculate the expected discounted payoff from the risky arm until the stopping time T , and the expected discounted payoff from the safe arm after the stopping time T . In case the first jump occurs before the stopping time T , we calculate the expected discounted payoff received from the continuous part Y 1 B (t) until time τ . We add the expected discounted payoff from the first jump, and the expected discounted continuation payoff, updating both the posterior p t,h,x , and the intercept E + G h + x, according to the time of the first jump, the first jump's size, and the value of the continuous part of the payoff.
The notation used are as follows: P θ (τ > T ) is the probability that the DM switches to the safe arm before a jump occurs. If τ > T then the expected payoff from the risky arm is E θ [ T 0 re −rt dY 1 B (t)|τ > T ], and the expected payoff from the safe arm is E θ [ ∞ T re −rt sdt|τ > T ]. P θ (τ < T ) is the probability a jump occurs before the DM switches to the safe arm. If τ < T then the expected payoff until the first is the probability that the first jump occurs in the interval [t, t + dt), and B µ (τ ) belongs to [x, x + dx), given that a jump occurs before the DM switches to the safe arm. re −rt 1 ν hν(dh) is the expected discounted payoff from the first jump, and 1 ν νe −rt U (p t,h,x , E + G h + x)) is the expected discounted continuation payoff, updating both the posterior p t,h,x , and the intercept E + G h + x at time t. With this notation, the expected payoff is as follows: .
By Eqs. (4.18), (4.19) and (4.20), this expression is equal to By Eqs. (4.21), (4.22) and (4.23), this expression is equal to Simplifying the last expression, the integral equation is where A, B, C, and D are constants, and We show now that (IE) admits a unique solution U in the region [0, 1] × [0, ∞). The proof is similar to the proof of Lemma 4.4, and therefore omitted. We turn to the proof of Theorem 2.6, which is analogous to the proof of Theorems 2.3 and 2.5.

Boundary values
Proof of Theorem 2.6. Suppose that until time t, the DM chose the risky arm, and observed the jumps h a 1 , ...h a n (resp. h b 1 , ...h b m ) from the process (X a (t)) (resp. (X b (t))). Let Y a B (t) (resp. Y b B (t)) be the Brownian motion with drift component of (X a (t)) (resp. (X b (t))) at time t. Note that Y j B (t) ∼ N (µ j t, (σ j ) 2 t), j ∈ {a, b}. Let q t := P t (θ 1 |h 1 , ...h n ; h b 1 , ...h b m ; Y a B (t); Y b B (t); q 0 ) be the posterior belief of the DM. The odd ratio of the posterior belief is ) is the probability of observing Y a B (t) (resp. Y b B (t)), given the type θ i , and e −ν a i t (ν a i t) n n! t− ν a i (dh a j ) ν a i (resp. ) is the probability of receiving the n (resp. m) jumps that occurred until time t from (X a i (t)) (resp. (X b i (t))), given the type θ i . The first equality in (4.27) is the Bayesian belief updating, using the independence of the Lévy processes X a i (t) and X b i (t), and the independence of the components in the Lévy-Ito decomposition, given the type of the risky arm, and the second equality is obtained by eliminating common components.
Suppose the DM follows a cut-off strategy κ ′ with cut-off point p ′ . If q 0 ≤ p ′ , the DM will always choose the safe arm. If q 0 > p ′ the DM will initially choose the risky arm. Then the DM chooses the risky arm as long as q t > p ′ , which, by Eq. (2.4), is equivalent to By taking the natural logarithm, and rearranging the resulting terms, we obtain that this inequality is equivalent to .
Since Y j B (t) = µ a + σ a Z a (t), k ∈ {a, b}, it follows that Eq. (4.29) is equivalent to whereμ j i = µ j i σ j , for j ∈ {a, b, c}, and i ∈ {1, 2}. Notice that Bμ a ,μ b (t) is a standard Brownian motion with drift: We construct an integral equation similar to the one in the proof of Theorem 2.5.
Let τ be the stopping time of the first jump from the process (X a (t) + X b (t)). Let the stopping time T be the first time t that satisfies (4.31) Denote G a h := ln " ν a 1 (dh a j ) ν a 2 (dh a j ) « √ (μ a 1 −μ a 2 ) 2 +(μ b 1 −μ b

Figures
In Figure 1 we depict a generic path of the Lévy payoff process (Y (t)). The contribution of the compound Poisson process (the jumps) appears in Figure 2. The posterior belief given the observations appears in Figure 3. Finally, Figure 4 shows the time-dependent cut-off, as well as the continuous part of the process (the Brownian motion with drift).