In this paper we consider the following situation: An experimenter has to perform a total of N trials on two Bernoulli-type experiments E₁ and E₂ with success probabilities α and β respectively, where both α and β are unknown to him. The trials are to be carried out sequentially and independently, except that for each trial the experimenter may choose between E₁ and E₂, using the information obtained in all previous trials. The decisions on the part of the experimenter to use E₁ or E₂ in the successive trials may be randomized, i.e. for any trial he may use a chance mechanism in order to choose E₁ or E₂ with probabilities δ and 1 - δ respectively, where δ may depend on the decisions taken and the results obtained in the previous trials. A strategy Δ will be a set of such δ's, completely describing the experimenters behavior in every conceivable situation. We assume the experimenter wants to maximize the number of successes. More precisely, we assume that he incurs a loss {equation*}{1.1} L(α, β, s) = N max(α, β)- s{equation*} if he scores a total of s successes. If he uses a strategy Δ, his expected loss is then given by the risk function {equation*}{1.2} R(α, β, Δ) = N max(α, β) - E(Sα, β, Δ),{equation*} where S denotes the random number of successes obtained. Thus the risk of a strategy Δ equals the expected amount by which the number of successes the experimenter will obtain using Δ falls short of the number of successes he would score if he were clairvoyant and would use the more favorable experiment throughout the N trials. It is easy to see that R(α, β, Δ) also equals |α - β| times the expected number of trials in which the less favorable experiment is performed under Δ. We say that state $(m, k; n, l)$ is reached during the series of trials if in the first $m + n$ trials E₁ is performed m times, yielding k successes, and E₂ is performed n times, yielding l successes. Clearly, under a strategy Δ, the probability that this will happen is of the form {equation*}{1.3} πα,β,Δ(m, k; n, l) = p_Δ(m, k; n, l)α^k(1 - α)ᵐ⁻ᵏ β^iota(1 - β)ⁿ⁻ⁱᵒᵗᵃ,{equation*} where p_Δ(m, k; n, l) depends on the state $(m, k; n, l)$ and the strategy Δ, but not on α and β. It is easy to show (e.g. by induction on N) that the class of all strategies is convex in the sense that there exists, for every pair of strategies Δ₁ and Δ₂ and for every λ ∈ 0, 1, a strategy Δ such that {equation*}{1.4} p_Δ(m, k; n, l) = λ pΔ_1(m, k; n, l) + (1 - λ)pΔ_2(m, k; n, l){equation*} for every state $(m, k; n, l)$. Moreover, this strategy Δ can always be taken to be such, that according to it the experimenter should base all his decisions exclusively on the numbers of successes and failures observed with E₁ and E₂, irrespective of the order in which these data became available. Denoting the class of all such strategies by D and remarking that R(α, β, Δ) can be expressed in terms of the πα,β,Δ(m, k; n, l), we may conclude that D is an essentially complete class of strategies. We denote the probabilities δ constituting any strategy in D by δ(m, k; n, l): the probability with which the experimenter, having completed the first $m + n$ trials and thereby having reached state $(m, k; n, l)$, chooses E₁ for the next trial. We note that if p_Δ(m, k; n, l) = 0 for a state $(m, k; n, l)$, then δ(m, k; n, l) does not play any role in the description of Δ and may be assigned an arbitrary value without affecting the strategy. We shall say that any strategy Δ' such that p_Δ'(m, k; n, l) = p_Δ(m, k; n, l) for all states $(m, k; n, l)$ constitutes a version of Δ. Since we are considering a symmetric problem in the sense that it remains invariant when α and β are interchanged, it seems reasonable to consider strategies with a similar symmetry. Thus we are led to define the class L of all symmetric strategies: Δ iff Δ and δ(m, k; n, l) = 1 - δ(n, l; m, k) for all states $(m, k; n, l)$ with p_Δ(m, k; n, l) ≠ 0. Clearly, for Δ, {equation*}{1.5} δ(m, k; m, k) = 1/2 if p_Δ(m, k; m, k) 0, and{equation*} {equation*}{1.6} P_δ(m, k; n, l) = p_δ(n, l; m, k) for all states (m, k; n, l).{equation*} It follows that, for Δ ∈ L and all (α, β), {equation*}{1.7} R(α, β, Δ) = R(β, α, Δ){equation*}. Among the contributions to the two-armed bandit problem the work of W. Vogel deserves special mention. Considering the same set-up we do, he discussed a certain subclass of the class L in [4], and obtained asymptotic bounds for the minimax risk for N → ∞ in [5]. Since we shall not be concerned with asymptotics in this paper, we state the following result without a formal proof: The lower bound for the asymptotic minimax risk for N → ∞ obtained by Vogel in [5] may be raised by a factor 2¹/2. This is proved by applying the same method that was used in [5] to the optimal symmetric strategy for α + β = 1 that was discussed in [4]. Combining this lower bound with the upper bound given in [5] we find that the asymptotic minimax risk must be between 0.265 N1/2 and 0.376 N1/2. In Section 2 we study the Bayes strategies in D. By means of a certain recurrence relation we arrive at a complete characterization of these strategies, thus generalizing D. Feldman's well-known result in [3] for the case where the experimenter knows the values of α and β except for their order. In addition we obtain expressions for the Bayes risk of any prior distribution. Using these results we proceed to derive in Section 3 certain monotonicity properties of δ(m, k; n, l) for any admissible strategy Δ in D. Though these relations may seem intuitively evident, one does well to remember that the two-armed bandit problem has been shown to defy intuition in many aspects (cf. [2]). In Section 4 we prove the existence of an admissible symmetric minimax-risk strategy having the monotonicity properties just mentioned. This fact to some degree facilitates the search for minimax-risk strategies, but even so, the algebra involved becomes progressively more complicated with increasing N and seems to remain prohibitive already for N as small as 5.
No takes yet. Share an insight, caveat, or question.
Fabius et al. (1970) studied this question.