AAAI 2024technical6 citations
A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs
Mateo Perez, Fabio Somenzi, Ashutosh Trivedi
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 in the limit. We prove that our algorithm only requires a polynomial number of samples in the relevant parameters, and perform experiments which confirm our theory.
BibTeX
@article{Perez_Somenzi_Trivedi_2024, title={A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/30148}, DOI={10.1609/aaai.v38i19.30148}, abstractNote={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 in the limit. We prove that our algorithm only requires a polynomial number of samples in the relevant parameters, and perform experiments which confirm our theory.}, number={19}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Perez, Mateo and Somenzi, Fabio and Trivedi, Ashutosh}, year={2024}, month={Mar.}, pages={21510-21517} }