On functional equations for KKth best policies in Markov decision processes

This paper revisits the problem of finding the values of KKth best policies for finite-horizon finite Markov decision processes. The recursive dynamic-programming (DP) equations established by Bellman and Kalaba for non-deterministic MDPs with zero-cost function in [Bellman, R., & Kalaba, R. (1960). On kth best policies. Journal of SIAM, 8, 582–588] are incomplete because expectation and selection for the KKth minimum do not interchange in general. Based on the DP equations by Dreyfus for the KKth shortest path problem, some non-DP equations generally satisfied by the values of the KKth best policies are identified, from which corrected Bellman and Kalaba’s DP equations are derived with an appropriate sufficient condition.