# Bayes' Model of the Best-Choice Problem with Disorder

Authors: Vladimir Mazalov; Evgeny Ivashko
Journal: International Journal of Stochastic Analysis
 (2012)

---

## Abstract

We consider the best-choice problem with disorder
and imperfect observation. The decision-maker observes sequentially
a known number of i.i.d random variables from a known distribution
with the object of choosing the largest. At the random time the distribution
law of observations is changed. The random variables cannot
be perfectly observed. Each time a random variable is sampled the
decision-maker is informed only whether it is greater than or less than
some level specified by him. The decision-maker can choose at most
one of the observation. The optimal rule is derived in the class of
Bayes' strategies.


---

## Body

## 1. Introduction

In the papers we consider the following best-choice problem with disorder and imperfect observations. A decision-maker observes sequentiallyn iid random variables ξ1,…,ξθ-1,ξθ,…,ξn. The observations ξ1,…,ξθ-1 are from a continuous distribution law F1(x) (state S1). At the random time θ, the distribution law of observations is changed to continuous distribution function F2(x) (i.e., the disorder happen—state S2). The moment of the disorder has a geometric distribution with parameter 1-α. The observer knows parameters α, F1(x), and F2(x), but the exact moment θ is unknown.At each time in which a random variable is sampled, the observer has to make a decision toaccept (and stop the observation process) or reject the observation (and continue the observation process). If the decision-maker decided to accept at step k (1≤k≤n), she receives as the payoff the value of the random variable discounted by the factor λk-1, where 0<λ<1. The random variables cannot be perfectly observed. The decision-maker is only informed whether the observation is greater than or less than some level specified by her.The aim of the decision-maker is to maximize the expected value of the accepted discounted observation.We find the solution in the class of the following strategies. At each momentk (1≤k≤n), the observer estimates the a posterior probability of the current state and specifies the threshold s=sn-k. The decision-maker accepts the observation xk if and only if it is greater than the corresponding threshold s.This problem is the generalization of the best-choice problem [1, 2] and the quickest determination of the change-point (disorder) problem [3–5]. The best-choice problems with imperfect information were treated in [6–8]. Only few papers related to the combined best-choice and disorder problem are published [9–11]. Yoshida [9] considered the full-information case and found the optimal stopping rule which maximizes the probability that accepted value is the largest of all θ+m-1 random variables for a given integer m. Closely related work to this study is Sakaguchi [10] where the optimality equation for the optimal expected reward is derived for the full-information model. In [11], we constructed the solution of the combined best-choice and disorder problem in the class of single-level strategies, and, in this paper, we search the Bayes' strategy which maximizes the expected reward in the model with imperfect observation.


## 2. Optimal Strategy

According to the problem the observer does not know the current state (S1 or S2). But she can estimate the state using the Bayes' formula:
(2.1)πs=π(s)=P{S1∣x≤s}=P(S1)P(x≤s∣S1)P(x≤s)=απF1(s)Fπ(s).Here,s=si is the threshold specified by the decision-maker within i steps until the end (i.e., at the step n-i), π is the a prior probability of the state S1 (i.e., before getting the information that x≤s), Fπ(s)=πF1(s)+π¯F2(s), and π¯=1-π.We use the dynamic programming approach to derive the optimal strategy. Letvi(π) be the payoff that the observer expects to receive using the optimal strategy within  steps until the end. The optimality equation is as follows:
(2.2)vi(π)=max⁡sE[λvi-1(πs)I{x≤s}+xI{x>s}],i≥1,v0(π)=0∀π.Simplifying (2.2), we get
(2.3)vi(π)=max⁡s[λvi-1(πs)Fπ(s)+πE1(s)+π¯E2(s)],i≥1,v0(π)=0∀π.
Here, Ek(s)=∫s∞xdFk(x), k=1,2.The following theorem gives the presentation of the expected payoff in linear form onπ.Theorem 2.1.
For anyi the function  vi(π) can be written in the form
(2.4)vi(π)=πAi(s1,…,si)+Bi(s1,…,si),
where
(2.5)si=si(π)=argmax⁡s[λvi-1(πs)Fπ(s)+πE1(s)+π¯E2(s)],i≥1,0≤π≤1.Proof.
Using the formula (2.3), one can show that
(2.6)v1(π)=max⁡s[π(E1(s)-E2(s))+E2(s)]=πA1(s1)+B1(s1),
where A1(s1)=E1(s1)-E2(s1), B1=E2(s1) and
(2.7)s1=s1(π)=argmax⁡s[π(E1(s)-E2(s))+E2(s)],0≤π≤1.
Threshold s1=s1(π) is the solution of (2.3) for 0≤π≤1 for i=1.
Assume the theorem is correct for certaini=k. Then, for i=k+1
(2.8)vk+1(π)=max⁡s[λ(πsAk(s1,…,sk)+Bk(s1,…,sk))Fπ(s)+πE1(s)+π¯E2(s)]=max⁡s[π(λαF1(s)Ak(s1,…,sk)+λBk(s1,…,sk)(F1(s)-F2(s))+E1(s)-E2(s))+λBk(s1,…,sk)F2(s)+E2(s)]=πAk+1(s1,…,sk+1)+Bk+1(s1,…,sk+1),
where
(2.9)Ak+1(s1,…,sk+1)=λαF1(s)Ak(s1,…,sk)+λBk(s1,…,sk)(F1(s)-F2(s))+E1(s)-E2(s),Bk+1(s1,…,sk+1)=λBk(s1,…,sk)F2(s)+E2(s),si=si(π)=argmax⁡s[λvi-1(πs)Fπ(s)+πE1(s)+π¯E2(s)],i≥1,0≤π≤1.
The theorem is proved.The following lemma takes place.Lemma 2.2.
AssumingEk<∞,  k=1,2 as  i→∞, there is a limit of the expected payoff  vi(π)→v(π).Proof.
It is obvious that the sequencevi(π) is increasing by i.
Now, we prove that the sequence of the expected payoffs has an upper bound.(2.10)v1(π)≤πE1+π¯E2,Ek=∫0∞xdFk(x),k=1,2v2(π)=max⁡s[λv1(πs)Fπ(s)+πE1(s)+π¯E2(s)]≤λ(πE1+π¯E2)+πE1+π¯E2.
Further one can show using the induction that for any i≥1 and any 0≤π≤1 the expected payoff at the step i has the upper bound
(2.11)vi(π)≤πE1+π¯E21-λ.
The lemma is proved.Corollary 2.3.
Theorem2.1 and the lemma yield that there are such  A and  B that
(2.12)lim⁡i→∞vi(π)=lim⁡i→∞(πAi(s1,…,si)+Bi(s1,…,si))=πA+B=v(π).Asi→∞ the expected payoff satisfies the following equation:
(2.13)v(π)=lim⁡ivi(π)=max⁡s[λv(πs)Fπ(s)+πE1(s)+π¯E2(s)].To find the components of the expected payoff for a case of huge number of observation we should solve the following equation:(2.14)πA+B=max⁡s[π(λαF1(s)A+λB(F1(s)-F2(s))+E1(s)-E2(s))+λBF2(s)+E2(s)],
therefore,
(2.15)A=λαF1(s)A+λB(F1(s)-F2(s))+E1(s)-E2(s),B=λBF2(s)+E2(s).The solution of the system is as follows(2.16)A=E1(s)(1-λF2(s))-E2(s)(1-λF1(s))(1-λF2(s))(1-λαF1(s)),B=E2(s)1-λF2(s).The expected payoff is(2.17)v(π)=max⁡s(πA+B)
and the optimal threshold is
(2.18)s=s(π)=argmax⁡s(πA+B).The above results are summarized in the following theorem.Theorem 2.4.
Fori→∞, the solution of  (2.3) is defined as
(2.19)v(π)=max⁡s(πA+B),
where
(2.20)s=s(π)=argmax⁡s(πA+B),A=E1(s)(1-λF2(s))-E2(s)(1-λF1(s))(1-λF2(s))(1-λαF1(s)),B=E2(s)1-λF2(s).


## 3. Examples

Consider the examples of using the Bayes' strategyB defined by the formula (2.18) comparing with two strategies with constant thresholds that do not depend on π.


### 3.1. Normal Distribution

Consider the example of the normal distribution of the random variables where functionsF1(x) and F2(x) have the variance σ2=1 and the expectation μ1=10 and μ2=9, respectively.StrategiesA1 and A2 with constant thresholds defined by the following formula:
(3.1)s=E(s)1-λF(s),
where F(s)≡F1(s) and E(s)≡E1(s) for the strategy A1; F(s)≡F2(s) and E(s)≡E2(s) for the strategy A2.The values of the thresholds of strategiesA1 and A2 depending on discount rate are tabulated in Table 1.Table 1
The values of the thresholds of strategiesA1 and A2.
λStrategyA1StrategyA20.9910.8519.9020.99.0888.2100.77.0006.300Table1 shows how much the discount rate is affect on the thresholds.Figure1 shows the graphics of the optimal thresholds for strategies A1 and A2 (s1 and s2, resp.) and strategy B(sopt) depending on π. As the figure shows, the strategy B depends on the a posterior probability of the state S1(π). As π tends to zero, the optimal threshold of the strategy B tends to threshold s2.Figure 1
Graphics of the optimal thresholds for strategiesA1, A2, and B for α=0.9, λ=0.99.We compare the payoffs that the observer expects to receive using different strategies. DefineVα as the expected payoff for π=1 and depending on probability of disorder α.Figure2 shows the numerical results of the expected payoffs of the observer who uses the strategies A1, A2, and B (thresholds s1, s2, and sopt, resp.).Figure 2
Expected payoffs of the observer who uses the strategiesA1, A2 and B for α=0.9, λ=0.99.The expected payoff of the observer who uses the Bayes' strategyB is greater if she uses one of the strategies A1 or A2. The difference is significant for α∈[0.75,0.98], because of uncertainty of the current state of the system.Table2 shows the numerical results of the main characteristics of the best-choice process.Table 2
Main characteristics of the best-choice process forα=0.9, λ=0.99.
CharacteristicStrategyA1StrategyA2StrategyBExpected payoff10.03510.42910.500Average time of accepting the observation14.5262.4723.072Average number of steps after the disorder30.4064.5035.031Number of the values accepted before the disorder, %64.10083.06679.738For the small probability of the disorder (1-α=0.1), the expected payoff according to the strategy A2 is greater (10.429) than according to the strategy A1 (10.035). But the Bayes' strategy B that depends on π gives the largest expected payoff (10.500).Table2 shows that the average time of accepting the observation is increasing with respect to the value of the threshold. Note that the strategy A1 does not depend on the disorder and this leads to a high value of the average time of accepting the observation. Both strategies A2 and B have a small average time of accepting the observation.


### 3.2. Exponential Distribution

Consider the example of the exponential distribution of the observations. LetF1(x) and F2(x) have the exponential distribution with parameters λ1=0.5 and λ2=1, respectively. As in the previous example, consider the strategies A1 and A2 comparing with the Bayes' strategy B,
(3.2)s=E(s)1-λF(s),
where F(s)≡F1(s) and E(s)≡E1(s) for the strategy A1; F(s)≡F2(s) and E(s)≡E2(s) for the strategy A2.Table3 shows the values of the thresholds for the strategies A1 and A2 depending on the discount rate.Table 3
The values of the thresholds of strategiesA1 and A2.
λStrategyA1StrategyA20.996.7563.3780.93.3581.679The value of the optimal threshold of the strategyB as in the case of the normal distribution of the observations is increasing by π and equal to the threshold of the strategy A2 at π=0. The graphics of the expected payoffs have the same view as in Figure 2. Table 4 shows the main characteristics of the best-choice process for different strategies.Table 4
Main characteristics of the best-choice process forα=0.9, λ=0.99.
CharacteristicStrategyA1StrategyA2StrategyBExpected payoff2.3554.4384.499Average time of accepting the observation678.93015.39716.923Average number of steps after the disorder856.53529.11029.610Number of the values accepted before the disorder, %21.5770.8956.01As in the previous example, the Bayes' strategy gives better payoff than the strategyA2, but it has bigger average time of accepting the observation. The strategy A1 is the worst for all the parameters.


## 3.1. Normal Distribution

Consider the example of the normal distribution of the random variables where functionsF1(x) and F2(x) have the variance σ2=1 and the expectation μ1=10 and μ2=9, respectively.StrategiesA1 and A2 with constant thresholds defined by the following formula:
(3.1)s=E(s)1-λF(s),
where F(s)≡F1(s) and E(s)≡E1(s) for the strategy A1; F(s)≡F2(s) and E(s)≡E2(s) for the strategy A2.The values of the thresholds of strategiesA1 and A2 depending on discount rate are tabulated in Table 1.Table 1
The values of the thresholds of strategiesA1 and A2.
λStrategyA1StrategyA20.9910.8519.9020.99.0888.2100.77.0006.300Table1 shows how much the discount rate is affect on the thresholds.Figure1 shows the graphics of the optimal thresholds for strategies A1 and A2 (s1 and s2, resp.) and strategy B(sopt) depending on π. As the figure shows, the strategy B depends on the a posterior probability of the state S1(π). As π tends to zero, the optimal threshold of the strategy B tends to threshold s2.Figure 1
Graphics of the optimal thresholds for strategiesA1, A2, and B for α=0.9, λ=0.99.We compare the payoffs that the observer expects to receive using different strategies. DefineVα as the expected payoff for π=1 and depending on probability of disorder α.Figure2 shows the numerical results of the expected payoffs of the observer who uses the strategies A1, A2, and B (thresholds s1, s2, and sopt, resp.).Figure 2
Expected payoffs of the observer who uses the strategiesA1, A2 and B for α=0.9, λ=0.99.The expected payoff of the observer who uses the Bayes' strategyB is greater if she uses one of the strategies A1 or A2. The difference is significant for α∈[0.75,0.98], because of uncertainty of the current state of the system.Table2 shows the numerical results of the main characteristics of the best-choice process.Table 2
Main characteristics of the best-choice process forα=0.9, λ=0.99.
CharacteristicStrategyA1StrategyA2StrategyBExpected payoff10.03510.42910.500Average time of accepting the observation14.5262.4723.072Average number of steps after the disorder30.4064.5035.031Number of the values accepted before the disorder, %64.10083.06679.738For the small probability of the disorder (1-α=0.1), the expected payoff according to the strategy A2 is greater (10.429) than according to the strategy A1 (10.035). But the Bayes' strategy B that depends on π gives the largest expected payoff (10.500).Table2 shows that the average time of accepting the observation is increasing with respect to the value of the threshold. Note that the strategy A1 does not depend on the disorder and this leads to a high value of the average time of accepting the observation. Both strategies A2 and B have a small average time of accepting the observation.


## 3.2. Exponential Distribution

Consider the example of the exponential distribution of the observations. LetF1(x) and F2(x) have the exponential distribution with parameters λ1=0.5 and λ2=1, respectively. As in the previous example, consider the strategies A1 and A2 comparing with the Bayes' strategy B,
(3.2)s=E(s)1-λF(s),
where F(s)≡F1(s) and E(s)≡E1(s) for the strategy A1; F(s)≡F2(s) and E(s)≡E2(s) for the strategy A2.Table3 shows the values of the thresholds for the strategies A1 and A2 depending on the discount rate.Table 3
The values of the thresholds of strategiesA1 and A2.
λStrategyA1StrategyA20.996.7563.3780.93.3581.679The value of the optimal threshold of the strategyB as in the case of the normal distribution of the observations is increasing by π and equal to the threshold of the strategy A2 at π=0. The graphics of the expected payoffs have the same view as in Figure 2. Table 4 shows the main characteristics of the best-choice process for different strategies.Table 4
Main characteristics of the best-choice process forα=0.9, λ=0.99.
CharacteristicStrategyA1StrategyA2StrategyBExpected payoff2.3554.4384.499Average time of accepting the observation678.93015.39716.923Average number of steps after the disorder856.53529.11029.610Number of the values accepted before the disorder, %21.5770.8956.01As in the previous example, the Bayes' strategy gives better payoff than the strategyA2, but it has bigger average time of accepting the observation. The strategy A1 is the worst for all the parameters.


## 4. Results

In the article, we consider the best-choice problem with disorder and imperfect observations. We propose the Bayes' strategy where the threshold depends on thea posterior probability of the disorder. The numerical results show that this strategy gives better expected payoff than the constant strategies.



---

*Source: 697458-2011-08-03.xml*