Bernoulli Bandits

Methods are presented for using arrays to solve a class of statistical decision problems.

by Leida M. Bonilla M. and Martin L. Jones

A bandit problem is a statistical decision problem in which an observer must choose one of finitely many random processes to be observed at each of a possible infinite number of stages. The parameters governing the randomness in each process are not completely known to the observer in advance, therefore selections may be made for the purpose of gaining information as well as for reward. In this article we present a method of solving two-point Bernoulli bandits using arrays. The ideas are extendible to distributions with more than two points. 
Suppose that two medicines of unknown effectiveness are to be used to treat patients with a particular disease. As patients arrive requesting treatment, the practitioner must select one of the two medicines to be administered based on the available information at that time. The results of each treatment will increase the available information thereby aiding the practitioner in treating future patients. His objective is to maximize the number of successful treatments. Based on the preliminary information on the two medicines, does there exist a decision strategy for the selection process at each stage that would be optimal in the sense that on average this strategy would maximize the number of successful treatments? The answer, although not an unqualified one, is yes, and pertains to most situations of interest such as the one considered here in this article. Problems of this type are called a bandit problems, the name coming from the many-armed slot machines in which a player must choose an arm at each stage. Bandit problems are statistical decision problems in sequential experimental design. The practitioner not only performs an experiment (observes a process) at each stage in a sequential manner, but also must choose the experiment to be run at that stage. Moreover, because of the sequential nature of the design, he may use information from earlier experiments to aid in the selection of future ones. Throughout the article we will refer to the experiments or processes as arms and a bandit problem with two possible experiments at each stage as a two-armed bandit, etc. An excellent treatise on the subject is given by [Berry and Fristedt 1985]. 
For simplicity, in this article we will concentrate on the special case of two-armed Bernoulli bandits although the ideas are easily extendible to more complicated bandits. The name Bernoulli refers to the fact that each experiment or selection results in either a success or a failure. For the medical trial example we would regard the patients' recovery as a success and continued illness or death as a failure. Each success will be counted as a reward of 1 unit and each failure as a reward of 0 units. The parameters (Subscript[θ, 1]) and (Subscript[θ, 2]) will be used to represent the probability of a success on (Subscript[((a  r  m)), 1]) and (Subscript[((a  r  m)), 2]) respectively. At least one of these two parameters will be unknown to the observer at the beginning of the selection process although he will have some prior information regarding the likelihoods of different values for the parameters. This prior information will be represented by a distribution G on the parameter space [0, 1]×[0, 1]. In this article we will assume that G is supported by two points, that is the observer believes the parameters to be either ((Subscript[θ, 11]), (Subscript[θ, 21])) or ((Subscript[θ, 12]), (Subscript[θ, 22])). Letting p ∈ [0, 1] represent the observer's belief that the parameters are equal to ((Subscript[θ, 11]), (Subscript[θ, 21])), we may represent G by \(TraditionalForm
      \`G = p \((·δ)\)\_\((θ\_11, θ\_21)\) + 
        \((1 - p)\) 
        \((·δ)\)\_\((θ\_12, θ\_22)\)\). We will further assume that the observer has only finitely many selections. This so-called finite horizon uniform case is often represented by A = {1, 1,  ... , 1, 0,  ... } which indicates that for the first n selections the rewards are multiplied by a factor of 1 and thereafter by a factor of 0. The observer may continue making selections after stage n but receives no further rewards. Once the prior distribution G and the discount sequence A have been specified, the problem is referred to as the (G, A) bandit. A strategy τ is a function of the partial histories of the observations which indicates the arm to be selected at the next stage. For example, τ (∅) = 2 means that (Subscript[((a  r  m)), 2]) should be selected initially while τ (0) = 1 indicates that (Subscript[((a  r  m)), 1]) should be selected after a failure is observed on the first selection. Similarly, τ (0, 0, 1) = 2 indicates that (Subscript[((a  r  m)), 2]) should be selected at stage 4 after a pattern of two failures and one success in the first three observations on the arms indicated at these stages by τ. The expected gain from using strategy τ for the (G, A) bandit is denoted W (G, A, τ) (called the worth) and the supremum of W (G, A, τ) over all possible strategies is called the value of the (G, A) bandit and is denoted V (G, A). 
For Bernoulli bandits with a finite horizon discount sequence there always exists an optimal strategy \(TraditionalForm\`\(τ\^*\)\) for which \(TraditionalForm\`V \((G, A)\) = W \((G, A, \(τ\^*\))\)\). Moreover, both the value and an optimal strategy can be constructed using a procedure known as dynamic programming. The purpose of this article is to show how this can be accomplished efficiently using Mathematica. To begin we will give a short example taken from [Berry and Fristedt 1985] in which we construct by hand the value and an optimal strategy using the dynamic programming algorithm. Afterwards we will show how to implement the algorithm in Mathematica.

A Two-point Finite Horizon Bernoulli Bandit

In this example, \(TraditionalForm
      \`G = \((4/5)\) δ\_\((1/10, 0)\) + \((1/5)\) 
        δ\_\((9/10, 1)\)\) and A = {1, 1, 0,  ... }. That is, initially with probability 4/5 the observer believes that the parameters are both small and with probability 1/5 that both are large, and he has only two selections. Notice that a selection on (Subscript[((a  r  m)), 2]) gives complete information about the distributions since (Subscript[((a  r  m)), 2]) either always yields a success or always yields a failure. However, despite this information advantage on (Subscript[((a  r  m)), 2]), a selection of (Subscript[((a  r  m)), 1]) offers a positive probability of a success regardless of which of the two parameter sets represents the actual parameters. For a problem of this type with only two selections we could write down all of the possible strategies one by one and check the worth of each until we found an optimal one, however for illustrative purposes we will use our dynamic programming algorithm. We solve the problem by working backwards from the penultimate stage. That is, faced with the last (in this case the second) selection, the observer will have already witnessed one of four possible histories which we will denote (Subscript[σ, 1]), (Subscript[ϕ, 1]), (Subscript[σ, 2]), and (Subscript[ϕ, 2]) representing a success or failure (σ or ϕ) and the arm which was selected. Using Baye's Theorem we can calculate the updated distributions for each of the four histories. For example, after witnessing a success on (Subscript[((a  r  m)), 1]), the new probability that the parameters are (1/10, 0) is

({{(Subscript[p, (Subscript[σ, 1])]),  = P (
                    ((Subscript[θ, 1]), (Subscript[θ, 2])) = (1/10, 0) 
                       |   (Subscript[σ, 1]))}, {,  = ((P 
                      ((Subscript[σ, 1])  |   
                          (Subscript[θ, 1]) = 1/10)·(4/5))/(P 
                      ((Subscript[σ, 1])  |   
                          (Subscript[θ, 1]) = 1/10)·(4/5) + P 
                      ((Subscript[σ, 1])  |   
                          (Subscript[θ, 1]) = 9/10)·(1/5)))}, {,  = (((1/10)·(4/5))/((1/10)
                        ·(4/5) + 
                      (9/10)·(1/5)))}, {, \( = \(4\/13\) . 
                    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \((1)\)\)}})

Using similar calculations we can obtain the four updated distributions

({{(Subscript[σ, 1]) G,  = (4/13) (Subscript[δ, (1/10, 0)]) + (9/13) 
                (Subscript[δ, (9/10, 1)])}, {(Subscript[ϕ, 1]) G,  = (36/37) (Subscript[δ, (1/10, 0)]) + (1/37) 
                (Subscript[δ, (9/10, 1)])}, {(Subscript[σ, 2]) G,  = 0 (Subscript[((·δ)), (1/10, 0)]) + 1 
                (Subscript[((·δ)), (9/10, 1)])}, {(Subscript[ϕ, 2]) G,  = 1 (Subscript[((·δ)), (1/10, 0)]) + 0 
                (Subscript[((·δ)), (9/10, 1)]) . }})

We will represent the observer's one remaining selection at this stage by (A^((1))) = {1, 0, 0,  ... }, the original discount sequence with the first term deleted. For each each history we calculate the expected gain on the last observation which is the maximum (denoted below by `⋁') expected gain between the two arms. Using V (·, (A^((1)))) to represent this partial history value we have

({{V ((Subscript[σ, 1]) G, (A^((1)))),  = ((4/13)·(1/10) + (9/13)·(9/10))
                  ⋁((4/13)·0 + (9/13)·1)}, {, =(17/26)⋁(("9")/("13"))=(9/13)}, {V ((Subscript[ϕ, 1]) G, (A^((1)))),  = ((36/37)·(1/10) + (1/37)·(9/10))
                  ⋁((36/37)·0 + (1/37)·1)}, {, =(("9")/("74"))⋁(1/37)=(9/74)}, {V ((Subscript[σ, 2]) G, (A^((1)))), =(1·(9/10))⋁(1·1)=(9/10)⋁"1"}, {,  = 1}, {V ((Subscript[ϕ, 2]) G, (A^((1)))), =(1·(1/10))⋁(1·0)=(("1")/("10"))⋁0=(1/10) . 
                                                  
                        (2)}})

We can see from the above calculations that after observing a success on (Subscript[((a  r  m)), 1]) it is wise to switch to (Subscript[((a  r  m)), 2]) for the last selection, whereas after observing a failure on (Subscript[((a  r  m)), 1]) it is wise to continue with (Subscript[((a  r  m)), 1]). Similar interpretations hold for initial selections on (Subscript[((a  r  m)), 2]). Now that we know how to select at the penultimate stage we may continue to work backwards and now average these stage two possibilities over the distribution G to obtain an optimal initial selection. The value obtained is

({{V (G, A),  = (4/5) 
                ((1/10) (1 + (9/13)) + (9/10) (0 + (9/74)))
                  }, {, +(1/5) 
                ((9/10) (1 + (9/13)) + (1/10) (0 + (9/74)))
                  }, {, ⋁(4/5) (0 (1 + 1) + 1 (0 + (1/10)))}, {, +(1/5) (1 (1 + 1) + 0 (0 + (1/10)))}, {, =(("53")/("100"))⋁(12/25)=(53/100),                                                                      (3)}})

and we can see that the optimal initial selection is (Subscript[((a  r  m)), 1]). To explain the calculations in (3), consider the term

\(TraditionalForm
    \`\(4\/5\) \((\(1\/10\) \((1 + 9\/13)\) + \(9\/10\) \((0 + 9\/74)\))\) . 
      \)

With probability 4/5 the parameters will be (1/10, 0), so that a selection of (Subscript[((a  r  m)), 1]) yields a success with probability 1/10 and a failure with probability 9/10. Therefore, if a success is observed, a reward of 1 will be earned plus the expected gain on the second selection which from (2) is seen to be on the average 9/13. Similarly a failure on (Subscript[((a  r  m)), 1]) will earn a reward of 0 plus, from (2), an expected gain on the second selection of 9/74. An optimal strategy may be pieced together starting from the optimal initial selection forward to yield \(TraditionalForm
      \`τ \((∅)\) = 1, τ \((0)\) = 1, τ \((1)\) = 2
        \). In the next section we will demonstrate how the dynamic programming method can be implemented in an efficient manner using arrays.

An Algorithm for Solving Two-point Bernoulli Bandits

The equations (2) and (3) of the previous example are known as the fundamental equations of dynamic programming, adjusted here to the two-point Bernoulli bandit setting. Let * represent a partial history of observations (e.g. (Subscript[σ, 1]) (Subscript[ϕ, 1]) (Subscript[σ, 2])) and (Subscript[σ, 2])*, for example, represent the same partial history followed by a success on (Subscript[((a  r  m)), 2]). Then using (A^((k))) to denote the original discount sequence with the first k terms deleted and \(TraditionalForm\`\(q\_*\) = 1 - \(p\_*\)\) we can represent the general form of the fundamental equation of dynamic programming as