This paper provides a technique, based on partially observable Markov decision processes (POMDPs), for building automatic recovery controllers to guide distributed system recovery in a way that provides provable assurances on the quality of the generated recovery actions even when the diagnostic information may be imprecise. Lower bounds on the cost of recovery are introduced and proved, and it is shown how the characteristics of the recovery process can be used to ensure that the lower bounds converge even on undiscounted models. The bounds used in an appropriate online controller provide it with provable termination properties. Simulation-based experimental results on a realistic e-commerce system demonstrate that the proposed bounds can be improved iteratively, and the resulting controller convincingly outperforms a controller that uses heuristics instead of bounds.