  We address the problem of computing reliable policies in reinforcement
learning problems with limited data. In particular, we compute policies that
achieve good returns with high confidence when deployed. This objective, known
as the \emph{percentile criterion}, can be optimized using Robust MDPs~(RMDPs).
RMDPs generalize MDPs to allow for uncertain transition probabilities chosen
adversarially from given ambiguity sets. We show that the RMDP solution's
sub-optimality depends on the spans of the ambiguity sets along the value
function. We then propose new algorithms that minimize the span of ambiguity
sets defined by weighted $L_1$ and $L_\infty$ norms. Our primary focus is on
Bayesian guarantees, but we also describe how our methods apply to frequentist
guarantees and derive new concentration inequalities for weighted $L_1$ and
$L_\infty$ norms. Experimental results indicate that our optimized ambiguity
sets improve significantly on prior construction methods.
