mlsanityData to 14 Oct 2026

Provably Efficient Exploration in Reward Machines with Low Regret

arXiv 2412.19194 ↗First posted 26 Dec 2024cs.LG cs.AIcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 7 of its 54 references that are in the map. First posted on arXiv 26 Dec 2024.

Builds on

7 of 54 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Efficient Reinforcement Learning in Probabilistic Reward Machines19 Aug

Other references · 6

  1. 2017Environment-Independent Task Specifications via GLTLcited by 67
  2. 2020Improved Analysis of UCRL2 with Empirical Bernstein Inequalitycited by 18
  3. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 15
  4. 2022Joint Learning of Reward Machines and Policies in Environments with Partially Known Semanticscited by 12
  5. 2022Learning Task Automata for Reinforcement Learning using Hidden Markov Modelscited by 7
  6. 2019Model-Based Reinforcement Learning Exploiting State-Action Equivalencecited by 6

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processescited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  2. 2025Reinforcement Learning with Stochastic Reward Machines
  3. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  4. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds
  5. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning
  6. 2024Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observation
  7. 2025Asymptotically optimal reinforcement learning in Block Markov Decision Processes
  8. 2024On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks