Offline RL in Regular Decision Processes: Sample Efficiency via Language Metrics
Reinforcement Learning;Non-Markov Decision Process;Offline Reinforcement Learning;Regular Decision Processes;Sample Complexity;Automata
Yes
No ethics review needed.
- Could the authors discuss possible modifications to their approach if $\mu_0$ is close to zero in some states? What would the practical implications be in such cases?
- Can the proposed approach be applied to settings where the RDP structure is much larger, high dimensional, and even continuous? E.g. [1].

[1] Allen, Cameron, et al. "Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy." arXiv preprint arXiv:2407.07333 (2024).
- The proposed language metric is novel and offers a unique approach to state distinguishability, unifying and extending traditional distance metrics (like $L_1$ and $L_{\infty}$). This potentially sets a new standard for offline RDP learning.
- This is primarily a theoretical paper. The proposed approach has clearly stated assumptions and is supported by rigorous sample complexity analysis with proofs. Interestingly, through their theoretical analysis, the authors also uncover a mistake in one of theoretical results from the ADACT-H (Cipollone et al., 2023) paper. Such results are very much appreciated. Although the experiments are in fairly simple small environments with a single baseline, their inclusion is also appreciated as it helps better understand the applicability of the proposed approach.
- The paper is generally well-written, with somewhat clear explanations of the RDP framework and experimental setup. Although some sections (e.g., language metric details) could benefit from further simplification for broader accessibility. They also provide pseudocodes in the appendix for better clarity. 
- This work contributes meaningfully to offline RL in non-Markov environments, where observations and rewards depend on past transitions.
This paper considers the offline reinforcement learning (RL) problem when the offline trajectories data are non-Markov---precisely when they are generated by an underlying Regular Decision Process (RDP). To address this problem, they propose two novel algorithmic adaptations of ADACT-H (Cipollone et al., 2023) from prior work to learn the underlying RDP: one using the Count-Min Sketch (CMS) and another using a novel language metric ($L_X$) for efficient learning of episodic RDPs from offline data. The language metric is shown to be a generalization of previous ones like $L_1$ and $L_{\infty}$, capturing desired properties of both to improve state distinguishability. They show that the proposed approaches significantly reduce sample and space complexity compared to prior methods. Finally, they conduct experiments across five domains from prior works to demonstrate the proposed methods' advantages in terms of runtime, number of states, and reward maximization.
- The method seems to only be applicable to very small environments in practice, given that it attempts to learn the underlying RDP for both obsservation and reward transitions. This doesn't look like it can be applied to larger environments (such as high-dimensional observations and continuous crontrol ones), unlike prior works in the online setting like Toro Icarte et al., 2019.

- The approach assumes $\pi^b$ maintains a non-zero minimum distinguishability, which may limit the algorithm's application in environments with varying policy behaviors or unobservable state spaces. Further discussion on generalizing this assumption would enhance the paper's robustness.

- The CMS-based approach suffers exponential complexity with the horizon \(H\), which could impact performance in long-horizon tasks, as evidenced in the Mini-hall domain experiment. Addressing this limitation or providing recommendations on CMS applicability range would be beneficial.

- The sample complexity bound relies on a parameter inversely related to the minimum occupancy of the optimal policy $d_m^*$, which could become infeasible in scenarios with low-reachability states. Including strategies or adjustments for low-occupancy environments could further strengthen the results.

- In general, the paper is very hard to follow for an RL researcher (at least it was for me). This is partially because of too many notations, and a mismatch of notations from different fields. For example, some come from the RL literature (like the value function $V(.)$) and others like $Q(.)$ which usually represents the action-value function in RL now represents the set of RDP states (instead of $S$ or even $U$). I think a lot of work needs to be done to simplify the notations in the background and improve the clarity of Section 4.
Yes
No ethics review needed.
1. Given the reliance on existing language hierarchy theories, how does the proposed language metric meaningfully differ in terms of its theoretical impact on distinguishing states within RDPs?
2. Can the authors expand on any potential limitations of CMS in larger, more complex RDPs, especially concerning long planning horizons?
The paper offers a theoretical framework for a new language metric and CMS integration in offline RL for RDPs. The analysis of PAC sample complexity for RDPs provides valuable insight into distinguishing state representations in non-Markovian settings.
This paper explores offline reinforcement learning (RL) within Regular Decision Processes (RDPs), a subclass of non-Markovian environments. The authors propose improvements on existing methods through a novel language metric and the use of Count-Min Sketch (CMS) to enhance sample efficiency and reduce memory costs. They provide theoretical guarantees and some empirical results in specific domains, comparing their approach to the state-of-the-art methods.
1. The primary contribution, a novel language metric, builds heavily on established language hierarchy concepts and does not provide a groundbreaking shift in methodology. CMS is also a well-established technique, and its application here does not significantly differentiate the approach from prior state-merging algorithms.  I think the author should highlight the difference and the technical contribution.
2. Experimental results are limited to a small set of benchmark domains that are relatively simple, and the benchmark algorithms used for comparison are limited. More famous RDP algorithms might be involved like Omega-RDP (Hahn et al., 2023) and Grid-world (Lenaers and Otterlo, 2021).

---
Hahn, E. M., Perez, M., Schewe, S., Somenzi, F., Trivedi, A., & Wojtczak, D. (2024, March). Omega-Regular Decision Processes. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 19, pp. 21125-21133).

Lenaers, N., & van Otterlo, M. (2022). Regular decision processes for grid worlds. In Artificial Intelligence and Machine Learning: 33rd Benelux Conference on Artificial Intelligence, BNAIC/Benelearn 2021, Esch-sur-Alzette, Luxembourg, November 10–12, 2021, Revised Selected Papers 33 (pp. 218-238). Springer International Publishing.
Yes
No ethics review needed.
I would like to see a definition of "episode trace". I think I understand the meaning from the context but it would be best to clearly write it down somewhere.
The ADACT algorithm is first mentioned on line 434 but no definition is given before that. I later found the definition in the appendix but it would be good to have a link to that definition when it is first mentioned.
Well written. The example of the T shaped world help fix the cause of the deficiency of the $L_q^p$ metric and how the $L_\chi$ fixes the problem.
The authors present a new metric $L_\chi$ regular decision processes (RDP) based on formal languages. In theorem 1, this metric is shown to be an improvement on previous metrics $L_q^p$ by outlining a family of RDPs for which the  $L_q^p$-distinguishability decays as time horizon increases while the $L_\chi$-distinguishability is constant. Example 4 is particularly useful in illustrating this phenomenon where a T shaped grid world with an increasing corridor length is causing a decay of distinguishability while it is constant in the second case.  They then compare the distinguishability of these metrics for the policies produced by the algorithm A DACT-H.
The proof of theorem 1 looks correct but I did not have time to check all details. A quick outline of how it works would be welcome.
Yes
No ethics review needed.
I understand it is always easy to ask for more, but your paper would substantially benefit from a non-toy environment, both mentioned as a fit for the learning setting you are tackling, but of course also used as an illustrative experiment to show what your contributions make possible that wasn't before.  RL research's biggest boost came from showing solutions of non-trivial environments.  I'm afraid that your good work might be lost without such a demonstrator.
The contributions are well placed in the context of directly related work.  Although some more distant related work might have been missed, such as the graph kernel work mentioned in the summary, this represents only a minor point.  To the best of my knowledge, the paper contains sufficient novelty to represent a good contribution, and it is nice to see the domain of tractable RL algorithms extended to settings beyond MDPs. 
The work and analysis presented are substantial.  I will honestly admit I did not rigorously go through all the mathematics of the paper and the appendices.  However, the parts I did go through illustrated the care for detail required.
The paper is very well written too.  There is a lot of material to get through and the organisation of the paper is well done and the focus is good.  This may also explain the limited experimental support supplied in the paper.  The authors clearly decided to focus on the theoretical guarantees they could provide and supplied a (in their own words) numerical experimental evaluation.
The paper offers approaches for offline RL in Regular Decision Processes.  It focusses on improving sample efficiency for the state merging part of existing algorithms.  One contribution is a technique that employs a language metric for state comparisons.  The metric is somewhat akin to the principles behind e.g. graph kernels based on walks (see Gaertner, Flach, Wrobel, 2003) as it compares the probability distributions of the set of traces that can be generated by starting in two given states (nodes) and walking around in the RDP (on the graph).  The paper presents an efficient way to find relevant (i.e. state distinguishing) patterns in historic traces and a memory saving approach for storing probability distributions over large histories.  The paper includes a theoretical analysis and a (brief) experimental study.
Being unfamiliar with the term Regular Decision Process, I had to dig up the 2024 paper (there is also a 2019 one, which I missed) in the hope of finding more about the type of domains they represent.  The authors do define the RDP setting, but the paper does not succeed in relating the usefulness of the setting, i.e. it remains unclear how widely applicable the presented techniques are.  It would have been nice to see some less theoretical application domains that fit the setting, are non-trivial to translate/transform into MDPs, yet present an interesting RL challenge.  It is very hard for the reader to come up with one of these themselves, or at least it is in my experience while reading the paper.
We propose two novel techniques to overcome the limitations of existing Offline Reinforcement Learning algorithms for Regular Decision Processes.
@inproceedings{
anonymous2024offline,
title={Offline {RL} in Regular Decision Processes: Sample Efficiency via Language Metrics},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=EW6bNEqalF},
note={under review}
}
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 consider episodic RDPs and show that it is possible to overcome the limitations of existing offline RL algorithms for RDPs via
the introduction of two original techniques: a novel metric grounded in formal language theory and an approach based on Count-Min-Sketch (CMS). Owing to the novel language metric, our algorithm is proven to be more sample efficient than existing results, and in some problem instances admitting low complexity languages, the gain is showcased to be exponential in the episode length. The CMS-based approach removes the need for naïve counting and alleviates the memory requirements for long planning horizons. We derive Probably Approximately Correct (PAC) sample complexity bounds associated to each of these techniques, and validate the approach experimentally.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Reinforcement Learning Non-Markov Decision Process Offline Reinforcement Learning Regular Decision Processes Sample Complexity Automata
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/ec7046fe6da959a513c1cbd7d4cccca032ef27e8.pdf
reinforcement learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Offline RL in Regular Decision Processes: Sample Efficiency via Language Metrics
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission