Robust Anytime Learning of Markov Decision Processes
Markov decision processes (MDPs) are formal models commonly used in
sequential decision-making. MDPs capture the stochasticity that may arise, for
instance, from imprecise actuators via probabilities in the transition
function. However, in data-driven applications, deriving precise probabilities
from (limited) data introduces statistical errors that may lead to unexpected
or undesirable outcomes. Uncertain MDPs (uMDPs) do not require precise
probabilities but instead use so-called uncertainty sets in the transitions,
accounting for such limited data. Tools from the formal verification community
efficiently compute robust policies that provably adhere to formal
specifications, like safety constraints, under the worst-case instance in the
uncertainty set. We continuously learn the transition probabilities of an MDP
in a robust anytime-learning approach that combines a dedicated Bayesian
inference scheme with the computation of robust policies. In particular, our
method (1) approximates probabilities as intervals, (2) adapts to new data that
may be inconsistent with an intermediate model, and (3) may be stopped at any
time to compute a robust policy on the uMDP that faithfully captures the data
so far. We show the effectiveness of our approach and compare it to robust
policies computed on uMDPs learned by the UCRL2 reinforcement learning
algorithm in an experimental evaluation on several benchmarks.