Finite Horizon Markov Decision Processes with Uncertain Terminal Payoffs

This paper deals with the problem of finding an estimate of the maximal loss of optimality which can arise when terminal payoffs are uncertain and policies are restricted in some way. The original non-convex optimization problem is converted to a sequence of sub-problems involving the maximization of a bilinear function over a convex region. The paper deals solely with the theoretical issues.