= Solution
At a given time write $p_i=P_i^t$ and $q_i=\alpha_ip_i$, the conditional probability that the next search succeeds if box $i$ is chosen. Compare two consecutive searches $i,j$, keeping the continuation after two failures fixed. Their expected costs up to that common continuation are
$$
C_{ij}=c_i+(1-q_i)c_j,
\qquad
C_{ji}=c_j+(1-q_j)c_i.
$$
The probability of reaching the common continuation is the same in either order. Moreover,
$$
C_{ij}\leq C_{ji}
\Longleftrightarrow
q_ic_j\geq q_jc_i
\Longleftrightarrow
\frac{\alpha_ip_i}{c_i}
\geq\frac{\alpha_jp_j}{c_j}.
$$
Repeated adjacent interchanges move a box with maximal index to the front without increasing expected cost; applying the same argument after every failure proves the <optimal index for Bayesian box search> policy
$$
\boxed{\text{search a box maximizing }
\frac{\alpha_iP_i^t}{c_i}.}
$$
For completeness, after an unsuccessful search of box $i$, <Bayes' theorem> gives the posterior in the <Bayesian box search problem>:
$$
P_i^{t+1}=\frac{(1-\alpha_i)P_i^t}{1-\alpha_iP_i^t},
\qquad
P_j^{t+1}=\frac{P_j^t}{1-\alpha_iP_i^t}\quad(j\ne i).
$$
Back to article page
