Proceedings

Efficient PAC Reinforcement Learning in Regular Decision Processes

Alessandro Ronca, Giuseppe De Giacomo

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 2026-2032.

https://doi.org/10.24963/ijcai.2021/279

Keywords

  • Knowledge Representation and Reasoning: Action, Change and Causality
  • Planning and Scheduling: Markov Decisions Processes
  • Machine Learning: Reinforcement Learning

Abstract

Recently regular decision processes have been proposed as a well-behaved form of non-Markov decision process. Regular decision processes are characterised by a transition function and a reward function that depend on the whole history, though regularly (as in regular languages). In practice both the transition and the reward functions can be seen as finite transducers. We study reinforcement learning in regular decision processes. Our main contribution is to show that a near-optimal policy can be PAC-learned in polynomial time in a set of parameters that describe the underlying decision process. We argue that the identified set of parameters is minimal and it reasonably captures the difficulty of a regular decision process.

Alessandro Ronca, and Giuseppe De Giacomo. 2021. Efficient PAC Reinforcement Learning in Regular Decision Processes. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 2026–2032. https://doi.org/10.24963/ijcai.2021/279
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards