A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs

arXiv:2310.12248v3 Announce Type: replace
Abstract: Linear temporal logic (LTL) and omega-regular objectives -- a superset of LTL -- have seen recent use as a way to express non-Markovian objectives in reinforcement learning. We introduce a model-based probably approximately correct (PAC) learning algorithm for omega-regular objectives in Markov decision processes (MDPs). As part of the development of our algorithm, we introduce the epsilon-recurrence time: a measure of the speed at which a policy converges to the satisfaction of the omega-regular objective …

abstract algorithm arxiv cs.lg cs.lo decision express linear logic markov processes reinforcement reinforcement learning superset temporal type