Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 2 / 30K (Optimisation and Control)

At a given time write $p_i=P_i^t$ and $q_i={\alpha }_i{p}_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 areThe probability of reaching the common continuation is the same in either order. Moreover,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 policyFor completeness, after an unsuccessful search of box $i$, Bayes theorem gives the posterior in the Bayesian box search problem:

Let $V(p)$ be the maximal expected future reward minus search costs at posterior $p=(p_1,\dots ,p_n)$, with stopping value zero. Searching $i$ costs $c_i$, succeeds with probability ${\alpha }_i{p}_i$ and earns $R_i$, and otherwise produces the posterior $p^{(i)}$ displayed in part (a). The rewarded Bayesian box search Bellman equation is

Suppose ${\sum }_i{c}_i/({\alpha }_i{R}_i)<1$. At every posterior $p$, some index must satisfyotherwise summing the reverse inequalities would give $1={\sum }_i{p}_i<1$. For this box,even if one stops immediately after a failed search. Hence $V(p)>0$ at every posterior, and stopping before discovery is never optimal.

Once search necessarily continues until the ball is found, the expected reward ${\sum }_i{p}_i{R}_i$ is independent of the order of searches. Maximizing expected net reward therefore amounts to minimizing expected search cost. Part (a) applies, so the policy maximizing ${\alpha }_i{P}_i^t/c_i$ remains optimal.