Bayesian box search problem

A hidden object lies in box $i$ with posterior probability $p_i$. Searching box $i$ costs $c_i$ and, conditional on the object being there, detects it with probability ${\alpha }_i$. After an unsuccessful search of box $i$, Bayes theorem updates the probabilities to

When search continues until discovery, expected search cost is minimized by searching at each step a box maximizing ${\alpha }_i{p}_i/c_i$. An adjacent-interchange argument compares two searches: placing $i$ before $j$ costs less exactly when ${\alpha }_i{p}_i/c_i\ge {\alpha }_j{p}_j/c_j$.

If discovery in box $i$ earns reward $R_i$ and stopping earns zero, the Bellman equation isIf ${\sum }_i{c}_i/({\alpha }_i{R}_i)<1$, every posterior state has some $i$ with ${\alpha }_i{p}_i{R}_i>c_i$, so stopping is never optimal.