The following problem is example 5.1 from http://www.statslab.cam.ac.uk/~rrw1/oc/oc2013.pdf
A hidden object moves between two locations according to a Markov China with probability transition matrix $P=(p_{ij})$ A search in location $i$ costs $c_i$ and if the object is there it is found with probability $\alpha_i$. The aim is to minimise the expected cost of finding the object.
For special cases, we know the optimal policy 'search location 1 iff the probability that the object in location 1 exceeds a threshold $x_1^*$, then it goes on to say
'the value of $x_1^*$ depends on the parameters $\alpha_i$ and $p_{ij}$. t is believed the answer is of this form for all values of parameters, but this is still an unproved conjecture'
I would like to know what this particular problem is called or if there is any existing literature on this. It surprises me how a seemingly simple problem is still unresolved. I guess it tells us how little we know...