mlsanityData to 14 Oct 2026

Efficient Reinforcement Learning in Probabilistic Reward Machines

arXiv 2408.10381 ↗First posted 19 Aug 2024stat.ML cs.AI cs.LGcited by 4

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

Abstract (arXiv)

In this paper, we study reinforcement learning in Markov Decision Processes with Probabilistic Reward Machines (PRMs), a form of non-Markovian reward commonly found in robotics tasks. We design an algorithm for PRMs that achieves a regret bound of widetildeO(√HOAT + H2O2A3/2 + H√T), where H is the time horizon, O is the number of observations, A is the number of actions, and T is the number of time-steps. This result improves over the best-known bound, widetildeO(H√OAT) of citetpmlr-v206-bourel23a for MDPs with Deterministic Reward Machines (DRMs), a special case of PRMs. When T ≥ H3O3A2 and OA ≥ H, our regret bound leads to a regret of widetildeO(√HOAT), which matches the established lower bound of Omega(√HOAT) for MDPs with DRMs up to a logarithmic factor. To the best of our knowledge, this is the first efficient algorithm for PRMs. Additionally, we present a new simulation lemma for non-Markovian rewards, which enables reward-free exploration for any non-Markovian reward given access to an approximate planner. Complementing our theoretical findings, we show through extensive experiment evaluations that our algorithm indeed outperforms prior methods in various PRM environments.

Key facts. Cited by 4 papers 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 24 of its 35 references that are in the map. First posted on arXiv 19 Aug 2024.

Builds on

24 of 35 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods13 Jul

Other references · 23

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  3. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 191
  4. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  5. 2016Reinforcement Learning With Temporal Logic Rewardscited by 117
  6. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  7. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  8. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  9. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  10. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  11. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  12. 2014A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specificationscited by 49
11 more
  1. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  2. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  3. 2020Reward Machines for Cooperative Multi-Agent Reinforcement Learningcited by 35
  4. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  5. 2023Submodular Reinforcement Learningcited by 23
  6. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  7. 2021Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learningcited by 13
  8. 2015Correct-by-synthesis reinforcement learning with temporal logic constraintscited by 11
  9. 2021Decentralized Graph-Based Multi-Agent Reinforcement Learning Using Reward Machinescited by 7
  10. 2021Learning Quadruped Locomotion Policies using Logical Rulescited by 6
  11. 2024Multi-Agent Reinforcement Learning with a Hierarchy of Reward Machinescited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2024Provably Efficient Exploration in Reward Machines with Low Regretcited by 1
  2. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processescited by 1
  3. 2026SatQNet: Satellite-assisted Quantum Network Entanglement Routing Using Directed Line Graph Neural Networkscited by 1
  4. 2025Physics-Informed Reward Machinescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Reinforcement Learning with Stochastic Reward Machines
  2. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs
  3. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  4. 2026Learning Markov Decision Processes under Fully Bandit Feedback
  5. 2024No-Regret Reinforcement Learning in Smooth MDPs
  6. 2024Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality
  7. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  8. 2026Learning in Markov Decision Processes with Exogenous Dynamics