A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914687380094976 |
|---|---|
| author | Perez, Mateo Somenzi, Fabio Trivedi, Ashutosh |
| author_facet | Perez, Mateo Somenzi, Fabio Trivedi, Ashutosh |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_12248 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs Perez, Mateo Somenzi, Fabio Trivedi, Ashutosh Machine Learning Logic in Computer Science 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. |
| title | A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs |
| topic | Machine Learning Logic in Computer Science |
| url | https://arxiv.org/abs/2310.12248 |