Knowledge Gradient for Two Bernoulli Arms

Worked Solution

How to Think About It: This is a Bayesian decision problem where you get one free "look" before committing. Without any sample, you would just play the arm with the higher prior mean. The value of sampling comes from the chance that the sample changes your mind -- you might discover the arm you thought was worse is actually better. The knowledge gradient (KG) quantifies exactly this: the expected improvement in your final decision quality from taking one sample.

Quick Estimate: Suppose arm 1 has prior mean $\mu_1 = \alpha_1 / (\alpha_1 + \beta_1) = 0.6$ and arm 2 has $\mu_2 = 0.5$. Without sampling, you play arm 1 and expect payoff 0.6. If you sample arm 1 and see a success (which updates $\mu_1$ upward), you still play arm 1 -- no change. If you see a failure (updating $\mu_1$ downward), you might switch to arm 2 if the updated $\mu_1$ drops below 0.5. The EVOI of sampling arm 1 is the probability of this switch times the improvement when it happens. For arm 2, a success might push $\mu_2$ above $\mu_1$, causing a switch. The EVOI is larger when the two arms have similar prior means (more chance of a switch) and when priors are weak (each observation shifts the mean more).

Formal Derivation:

Let $\mu_i = \alpha_i / (\alpha_i + \beta_i)$ denote the prior mean of arm $i$, and let $n_i = \alpha_i + \beta_i$.

Baseline value (no sampling):

$$V_0 = \max(\mu_1, \mu_2)$$

Value of sampling arm $i$:

If we sample arm $i$ and observe success ($S$) or failure ($F$):

• $P(S) = \mu_i$ (prior predictive)
• $P(F) = 1 - \mu_i$

After observing success on arm $i$, the posterior mean updates to:

$$\mu_i^{+} = \frac{\alpha_i + 1}{n_i + 1}$$

After failure:

$$\mu_i^{-} = \frac{\alpha_i}{n_i + 1} = \frac{\mu_i n_i}{n_i + 1}$$

The arm $j \neq i$ is not sampled, so $\mu_j$ stays the same.

After sampling arm $i$, you play whichever arm has the higher posterior mean. The expected payoff is:

$$V_i = \mu_i \cdot \max(\mu_i^{+}, \mu_j) + (1 - \mu_i) \cdot \max(\mu_i^{-}, \mu_j)$$

The EVOI of sampling arm $i$ is:

$$\text{EVOI}_i = V_i - V_0$$

Expanding the formula:

Without loss of generality, suppose $\mu_1 \geq \mu_2$ (arm 1 is currently favored).

*Case: Sample arm 1 (the leading arm):*

• After success: $\mu_1^{+} = (\alpha_1 + 1)/(n_1 + 1)$. Since $\mu_1 \geq \mu_2$ and success only increases $\mu_1$, we still play arm 1. $\max(\mu_1^{+}, \mu_2) = \mu_1^{+}$.
• After failure: $\mu_1^{-} = \alpha_1/(n_1 + 1)$. If $\mu_1^{-} < \mu_2$, we switch to arm 2.

$$V_1 = \mu_1 \cdot \mu_1^{+} + (1 - \mu_1) \cdot \max(\mu_1^{-}, \mu_2)$$

The EVOI is positive only if failure can cause a switch, i.e., $\mu_1^{-} < \mu_2$.

When $\mu_1^{-} < \mu_2$:

$$\text{EVOI}_1 = \mu_1 \cdot \mu_1^{+} + (1 - \mu_1) \cdot \mu_2 - \mu_1$$

$$= \mu_1(\mu_1^{+} - \mu_1) + (1 - \mu_1)(\mu_2 - \mu_1)$$

Note $\mu_1^{+} - \mu_1 = \frac{\alpha_1 + 1}{n_1 + 1} - \frac{\alpha_1}{n_1} = \frac{(\alpha_1+1)n_1 - \alpha_1(n_1+1)}{n_1(n_1+1)} = \frac{n_1 - \alpha_1}{n_1(n_1+1)} = \frac{\beta_1}{n_1(n_1+1)} = \frac{1 - \mu_1}{n_1 + 1}$.

So:

$$\text{EVOI}_1 = \mu_1 \cdot \frac{1 - \mu_1}{n_1 + 1} + (1 - \mu_1)(\mu_2 - \mu_1) = (1 - \mu_1)\left[\frac{\mu_1}{n_1 + 1} + \mu_2 - \mu_1\right]$$

$$= (1 - \mu_1)\left[\mu_2 - \mu_1 + \frac{\mu_1}{n_1 + 1}\right]$$

$$= (1 - \mu_1)\left[\mu_2 - \frac{\mu_1 n_1}{n_1 + 1}\right]$$

$$= (1 - \mu_1)(\mu_2 - \mu_1^{-})$$

This is valid when $\mu_1^{-} < \mu_2$ (the failure observation causes a switch). When $\mu_1^{-} \geq \mu_2$, no switch ever occurs and $V_1 = \mu_1 = V_0$, so $ ext{EVOI}_1 = 0$. Sampling the leading arm is useless because you learn nothing decision-relevant.

*Case: Sample arm 2 (the trailing arm):*

• After success: $\mu_2^{+} = (\alpha_2 + 1)/(n_2 + 1)$. If $\mu_2^{+} > \mu_1$, switch to arm 2.
• After failure: $\mu_2^{-} = \alpha_2/(n_2 + 1) < \mu_2 \leq \mu_1$. Still play arm 1.

$$V_2 = \mu_2 \cdot \max(\mu_2^{+}, \mu_1) + (1 - \mu_2) \cdot \mu_1$$

When $\mu_2^{+} > \mu_1$:

$$\text{EVOI}_2 = \mu_2 \cdot \mu_2^{+} + (1 - \mu_2) \cdot \mu_1 - \mu_1 = \mu_2(\mu_2^{+} - \mu_1)$$

Similarly, $\mu_2^{+} - \mu_2 = \frac{1 - \mu_2}{n_2+1}$, so $\mu_2^{+} = \mu_2 + \frac{1 - \mu_2}{n_2+1}$.

$$\text{EVOI}_2 = \mu_2\left(\mu_2 + \frac{1 - \mu_2}{n_2+1} - \mu_1\right) = \mu_2(\mu_2^{+} - \mu_1)$$

Valid when $\mu_2^{+} > \mu_1$. Otherwise $\text{EVOI}_2 = 0$.

Closed-form summary (assuming $\mu_1 \geq \mu_2$):

$$\text{EVOI}_1 = (1 - \mu_1) \cdot \max(\mu_2 - \mu_1^{-}, 0)$$

$$\text{EVOI}_2 = \mu_2 \cdot \max(\mu_2^{+} - \mu_1, 0)$$

where $\mu_i^{+} = (\alpha_i + 1)/(n_i + 1)$ and $\mu_i^{-} = \alpha_i/(n_i + 1)$.

Decision Rule:

Sample the arm with the higher EVOI:

• If $\text{EVOI}_1 > \text{EVOI}_2$, sample arm 1.
• If $\text{EVOI}_2 > \text{EVOI}_1$, sample arm 2.
• If $\text{EVOI}_1 = \text{EVOI}_2 = 0$, sampling is worthless; just play the current best arm.

Symmetric priors ($\alpha_1 = \beta_1 = \alpha_2 = \beta_2 = a$):

Both arms have $\mu_1 = \mu_2 = 1/2$ and $n_1 = n_2 = 2a$. Since the arms are tied:

$$\mu_i^{+} = \frac{a + 1}{2a + 1}, \quad \mu_i^{-} = \frac{a}{2a + 1}$$

By symmetry, sampling either arm has the same EVOI. After sampling arm $i$:

• Success (prob $1/2$): posterior mean $(a+1)/(2a+1) > 1/2$, so play arm $i$. Expected payoff $(a+1)/(2a+1)$.
• Failure (prob $1/2$): posterior mean $a/(2a+1) < 1/2$, so play the other arm. Expected payoff $1/2$.

$$V_{\text{sample}} = \frac{1}{2} \cdot \frac{a+1}{2a+1} + \frac{1}{2} \cdot \frac{1}{2} = \frac{a+1}{2(2a+1)} + \frac{1}{4}$$

$$= \frac{2(a+1) + 2a+1}{4(2a+1)} = \frac{4a + 3}{4(2a+1)}$$

Baseline: $V_0 = 1/2$.

$$\text{EVOI} = \frac{4a+3}{4(2a+1)} - \frac{1}{2} = \frac{4a+3 - 2(2a+1)}{4(2a+1)} = \frac{1}{4(2a+1)}$$

As $a \to \infty$ (strong prior), $\text{EVOI} \to 0$ -- you already know the arms are fair, sampling teaches nothing. As $a \to 0$ (weak prior), $\text{EVOI} \to 1/4$ -- maximum value of information.

Answer:

For $\mu_1 \geq \mu_2$:

$$\text{EVOI}_i = P(\text{switch} \mid \text{sample } i) \times (\text{improvement from switch})$$

$$\text{EVOI}_1 = (1 - \mu_1)\max\!\left(\mu_2 - \frac{\alpha_1}{n_1+1},\, 0\right)$$

$$\text{EVOI}_2 = \mu_2 \cdot \max\!\left(\frac{\alpha_2+1}{n_2+1} - \mu_1,\, 0\right)$$

Sample the arm with higher EVOI. For symmetric priors $\text{Beta}(a, a)$, $\text{EVOI} = 1/[4(2a+1)]$, and you are indifferent between arms.