Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints

By Jie Fu, Ufuk Topcu. 2014

196 citations recorded by the source corpus.

We consider synthesis of control policies that maximize the probability of satisfying given temporal logic specifications in unknown, stochastic environments. We model the interaction between the system and its environment as a Markov decision process (MDP) with initially unknown transition probabilities. The solution we develop builds on the so-called model-based probably approximately correct Markov decision process (PAC-MDP) methodology. The algorithm attains an $\varepsilon$-approximately optimal policy with probability $1-\delta$ using samples (i.e. observations), time and space that grow polynomially with the size of the MDP, the size of the automaton expressing the temporal logic specification, $\frac{1}{\varepsilon}$, $\frac{1}{\delta}$ and a finite time horizon. In this approach, the system maintains a model of the initially unknown MDP, and constructs a product MDP based on its learned model and the specification automaton that expresses the temporal logic constraints. During execution, the policy is iteratively updated using observation of the transitions taken by the system. The iteration terminates in finitely many steps. With high probability, the resulting policy is such that, for any state, the difference between the probability of satisfying the specification under this policy and the optimal one is within a predefined bound.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Bootstrapping with Models: Confidence Intervals for Off-Policy Evaluation (2016, positive): “Model-based PAC-MDP methods can be used to synthesize policies which are approximately optimal with high probability [8].”
Safe Control under Uncertainty (2015, background): “Similarly, other approaches that model uncertainty as a variable added to the dynamics [36, 13, 37, 11, 12] lack clear connections to various sources of uncertainty present in the environment.”
A Review of Robot Learning for Manipulation: Challenges, Representations, and Algorithms (2019, background): “a finite-state automata) to guarantee (or bound the probability, in the stochastic case) that following a policy will not lead to an unsafe outcome [116, 106, 61, 57, 10].”