mlsanityData to 7 Oct 2026

Tractable Offline Learning of Regular Decision Processes

arXiv 2409.02747 ↗First posted 4 Sep 2024cs.LG cs.AI cs.FLcited by 2

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

This work studies offline Reinforcement Learning (RL) in a class of non-Markovian environments called Regular Decision Processes (RDPs). In RDPs, the unknown dependency of future observations and rewards from the past interactions can be captured by some hidden finite-state automaton. For this reason, many RDP algorithms first reconstruct this unknown dependency using automata learning techniques. In this paper, we show that it is possible to overcome two strong limitations of previous offline RL algorithms for RDPs, notably RegORL. This can be accomplished via the introduction of two original techniques: the development of a new pseudometric based on formal languages, which removes a problematic dependency on L_∞^mathsfp-distinguishability parameters, and the adoption of Count-Min-Sketch (CMS), instead of naive counting. The former reduces the number of samples required in environments that are characterized by a low complexity in language-theoretic terms. The latter alleviates the memory requirements for long planning horizons. We derive the PAC sample complexity bounds associated to each of these techniques, and we validate the approach experimentally.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 34 of its 72 references that are in the map. First posted on arXiv 4 Sep 2024.

Builds on

34 of 72 references.

Closest ancestors · 10

Same direction, newest first

  1. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation23 Nov
  2. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  3. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  4. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  5. 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct
  6. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  7. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  8. 2021Nearly Horizon-Free Offline Reinforcement Learning25 Mar
  9. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  10. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec

Other references · 24

  1. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 285
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  3. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
  4. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  5. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
  6. 2018Omega-Regular Objectives in Model-Free Reinforcement Learningcited by 74
  7. 2019Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learningcited by 74
  8. 2018Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specificationscited by 69
  9. 2020Approximate information state for approximate planning and reinforcement learning in partially observed systemscited by 67
  10. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  11. 2019Joint Inference of Reward Machines and Policies for Reinforcement Learningcited by 56
  12. 2014Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraintscited by 53
12 more
  1. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  2. 2020Cautious Reinforcement Learning with Logical Constraintscited by 44
  3. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  4. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  5. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  6. 2021Multi-Agent Reinforcement Learning with Temporal Logic Specificationscited by 27
  7. 2013The Sample-Complexity of General Reinforcement Learningcited by 18
  8. 2020Learning and Solving Regular Decision Processescited by 11
  9. 2022Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processescited by 10
  10. 2013Selecting the State-Representation in Reinforcement Learningcited by 6
  11. 2021Efficient PAC Reinforcement Learning in Regular Decision Processescited by 6
  12. 2013Optimal Regret Bounds for Selecting the State Representation in Reinforcement Learningcited by 2

Built on by

Cited by year (2026 to 7 Oct)

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

2 papers.

  1. 2025Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processescited by 0
  2. 2026Exact Distinguishability in Non-Markovian Decision Processescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees
  2. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory
  3. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  4. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  5. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processes
  6. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  7. 2020MOReL : Model-Based Offline Reinforcement Learning
  8. 2025A Clean Slate for Offline Reinforcement Learning