Provably Efficient Exploration in Reward Machines with Low Regret
This work addresses efficient exploration in reinforcement learning for structured tasks, representing an incremental advance by tailoring algorithms specifically to probabilistic reward machines.
The paper tackles reinforcement learning for non-Markovian reward processes using probabilistic reward machines, proposing a model-based algorithm that exploits this structure to achieve lower regret than existing methods, with derived high-probability regret bounds and a lower bound.
We study reinforcement learning (RL) for decision processes with non-Markovian reward, in which high-level knowledge of the task in the form of reward machines is available to the learner. We consider probabilistic reward machines with initially unknown dynamics, and investigate RL under the average-reward criterion, where the learning performance is assessed through the notion of regret. Our main algorithmic contribution is a model-based RL algorithm for decision processes involving probabilistic reward machines that is capable of exploiting the structure induced by such machines. We further derive high-probability and non-asymptotic bounds on its regret and demonstrate the gain in terms of regret over existing algorithms that could be applied, but obliviously to the structure. We also present a regret lower bound for the studied setting. To the best of our knowledge, the proposed algorithm constitutes the first attempt to tailor and analyze regret specifically for RL with probabilistic reward machines.