Offline RL in Regular Decision Processes: Sample Efficiency via Language Metrics

Authors: Ahana Deb, Roberto Cipollone, Anders Jonsson, Alessandro Ronca, Mohammad Sadegh Talebi
Primary area: reinforcement learning
Keywords: reinforcement learning, non-markov decision process, offline reinforcement learning, regular decision processes, sample complexity, automata

Abstract:
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.

Decision: accept (poster)
Reviewer scores: 6, 6, 8, 8

Reviews and discussion:
<thread>
creation date:
1729783855999

thread_type:
official_review

<thread_object>
creator: reviewer_yhdk

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730584828611

thread_type:
official_review

<thread_object>
creator: reviewer_9ta3

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721714318

thread_type:
official_review

<thread_object>
creator: reviewer_92xy

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730756959224

thread_type:
official_review

<thread_object>
creator: reviewer_k6ir

<content>
summary:
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.

strengths:
- 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.

weaknesses:
- 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.

questions:
- 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).
</content>
</thread_object>

</thread>


Metareview:
metareview:
This work studies offline RL in a special class of non-Markovian environments --- RDPs, where hidden finite-state automata capture dependencies between past interactions and future outcomes. It introduces two novel techniques: a formal language theory-based metric, which improves sample efficiency, and a Count-Min-Sketch approach that reduces memory requirements for long planning horizons. The authors also provide PAC sample complexity bounds and experimental validation to support their approach. The reviewers unanimously agree that this paper makes an interesting and valuable contribution to the field. As such, they all recommend accepting the paper.