Repositorio Digital de la UPF
Publication
Contribución de congreso (ConferenceOutput)
Provably efficient offline reinforcement learning in regular decision processes
This paper deals with offline (or batch) Reinforcement Learning (RL) in episodic Regular Decision Processes (RDPs). RDPs are the subclass of Non-Markov Decision Processes where the dependency on the history of past events can be captured by a finite-state automaton. We consider a setting where the automaton that underlies the RDP is unknown, and a learner strives to learn a near-optimal policy using pre-collected data, in the form of non-Markov sequences of observations, without further exploration. We present RegORL, an algorithm that suitably combines automata learning techniques and state-of-the-art algorithms for offline RL in MDPs. RegORL has a modular design allowing one to use any off-the-shelf offline RL algorithm in MDPs. We report a non-asymptotic high-probability sample complexity bound for RegORL to yield an ε-optimal policy, which makes appear a notion of concentrability relevant for RDPs. Furthermore, we present a sample complexity lower bound for offline RL in RDPs. To our best knowledge, this is the first work presenting a provably efficient algorithm for offline learning in RDPs., Roberto Cipollone is partially supported by the EU H2020 project AIPlan4EU (No. 101016442), the
ERC-ADG White-Mech (No. 834228), the EU ICT-48 2020 project TAILOR (No. 952215), the PRIN
project RIPER (No. 20203FFYLK), and the PNRR MUR project FAIR (No. PE0000013). Anders
Jonsson is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215), AGAUR SGR,
and the Spanish grant PID2019-108141GB-I00. Alessandro Ronca is partially supported by the
ERC project WhiteMech (No. 834228), and the ERC project ARiAT (No. 852769). Mohammad
Sadegh Talebi is partially supported by the Independent Research Fund Denmark, grant number
1026-00397B.