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

We thank the reviewer for the detailed review and valuable feedback, which we will integrate into the paper. We discuss several points meant to address weaknesses and questions in the review.

Example application domains : As mentioned in the answer to other reviewers, the complexity of the RDP directly impacts the sample efficiency of RDP learning. In turn, since the RDP states are sufficient to predict the future, the difficulty of learning the RDP is directly linked to the difficulty of translating a generic episodic decision process into an MDP. We believe that the language metric should make it possible to learn simple RDPs independently of the number of observations and actions. This is possible precisely when the amount of information to remember about the past is relatively limited.

Non-trivial environment : We strongly believe that the successful application of reinforcement learning to non-trivial environments was preceded by many important theoretical results. An important objective of the present paper is to illustrate the benefits of the proposed language metric, and we believe that the experiments supplement the theory by showing its superior performance in several domains. Of course this is only a first step towards handling larger domains.

We thank the reviewer for the detailed review and valuable feedback, which we will integrate into the paper. We discuss several points meant to address weaknesses and questions in the review. In particular, the question is addressed by points “Episode traces” and “AdaCT-H”.

Episode traces : We use the terms "episode", "trace" and "suffix" interchangeably in the paper, and all refer to sequences of action-reward-observation triplets introduced at the beginning of Section 2.3. We have clarified the use of terminology in the paper.

Outline of Theorem 1 : In the T-maze introduced in Example 3, while traversing the corridor each observation is random ($101$ or $111$). Hence in a corridor of length $H-1$, there are $2^{H-1}$ possible observation sequences, all equally likely. At the end of the corridor, the random reward depends on the first observation ($110$ or $011$). Hence the $L_\infty$ norm has to compare the difference in probability of traces of length $H$, each of which has probability $1/2^H$. The distinguishability is equal to the maximum difference in probability, which can be at most $1/2^H$ in case the distribution on final rewards is different. On the other hand, the language metric only compares whether or not a certain final reward occurs, and each reward has probability $1/2$, so the distinguishability is $1/2$ in this case.

AdaCT-H : The algorithm is first introduced in Section 3, but we have added a reference to Appendix A when AdaCT-H is again mentioned in Section 4.2.

We thank the reviewer for the detailed review and valuable feedback, which we will integrate into the paper. We discuss several points meant to address weaknesses and questions in the review. In particular, the first question is addressed mainly by the point “Novelty of the language metric”. The second question is addressed mainly by the point “Count-Min-Sketch”.

Novelty of the language metric : Contrary to the weakness perceived by the reviewer, we claim that the proposed language hierarchy does not rely on existing language hierarchies. The only connection with existing classes of languages is the operator in Definition 1, which is only loosely inspired by classes of languages in the first level of the dot-depth hierarchy. Thus, our contribution with regards to the language metric and the language hierarchies is entirely novel. Furthermore, we believe that using a language-theoretic approach to prove sample complexity guarantees in a reinforcement learning setting is extremely innovative.

Count-Min-Sketch : Though CMS is indeed used in other automaton learning algorithms (e.g. Baumgartner & Verwer[1]), other authors do not provide an extensive statistical analysis, and hence the choice of CMS parameters appears arbitrary. In contrast, our analysis sheds light on how to properly choose the CMS parameters, and as far as we know, we are the first to prove sample complexity guarantees for CMS in the automaton learning setting. As discussed in the answer to Reviewer K6iR, the difficulty of learning complex RDPs is not due to CMS, but rather due to properties of the RDP itself.

Omega-regular decision processes (ODPs) : As far as we can tell, ODPs are a generalization of RDPs, and hence ODPs should be at least as hard to learn as RDPs. The paper on ODPs present several classical complexity results (e.g. EXPTIME-hardness), while one of our major contributions is to provide a statistical analysis of the RDP learning algorithm and its sample complexity.

Limitation of benchmarks : As a primarily theoretical RL paper, the key goal is to devise provably sample-efficient algorithms that admit meaningful sample complexity bounds. The motivation behind providing numerical experiments here is: (1) to provide further insights into the presented results, thereby enriching discussion; and (2) to showcase that the presented approaches are not merely high-level theories and can indeed be implemented. We believe the domains used in our experiments, albeit rather small, render quite useful in achieving (1) and (2). Simple domains appear especially effective to spell out some key quantities (e.g., distinguishability) that arise in the context of RDP. We believe conducting experiments on larger domains fall into the scope of a follow-up work, where one may slightly depart from the theoretical framework via applying some techniques that are yet justifiable from a practical standpoint or may use some domain knowledge. Finally, we stress that releasing the code – which we plan to do – is a plus and paves the way to examining the presented approaches on larger domains.

References : We plan to incorporate the references mentioned by the reviewer in the final version of the paper.

[1] Baumgartner, Robert, and Sicco Verwer. "Learning state machines from data streams: A generic strategy and an improved heuristic." International Conference on Grammatical Inference. PMLR, 2023.

We thank the reviewer for the detailed review and valuable feedback, which we will integrate into the paper. We discuss several points meant to address weaknesses and questions in the review. In particular, the first question is addressed mainly by the point “Assumption on distinguishability” and “Complexity of RDPs”. The second question is addressed mainly by the point “Continuous observations and actions”.

Comparison to the reward machine literature : We remark that unlike Toro Icarte et al., we do not assume access to an existing label set and label function, and instead learn RDPs directly from a dataset of action-observation-reward episodes. We believe this problem to be significantly harder, and at the same time more realistic in case a label function is hard to define manually. Hence the two approaches are not directly comparable, and the RDPs we obtain are generally larger since we cannot exploit the compression afforded by the labels.

Scalability : An interesting direction for future research would be to assume that the underlying MDP state is the cross-product of the observation and the automaton state, i.e. $S = \mathcal{O} \times \mathcal{U}$ in our new notation. This is generally done in the reward machine literature, and makes the automaton part to be learned considerably more compact. A significant challenge is to achieve such an extension while still maintaining formal sample complexity guarantees.

Assumption on distinguishability : Cipollone et al. prove a lower bound on the sample complexity which is inversely proportional to the distinguishability of the $L_1$-norm. Hence the difficulty of the RDP learning problem increases as the distinguishability approaches 0, and we do not believe that we can efficiently learn the exact RDP in this case, or easily generalize Assumption 1 (but perhaps efficient approximation algorithms are possible).

Minimum occupancy : The approximation algorithm AdaCT-H-A of Cipollone et al. (which appears in Appendix A) partially alleviates the dependence on the minimum occupancy $d_m^*$. In fact, Cipollone et al. prove a sample complexity bound which excludes $d_m^*$ but in our corrected proof it appears as an additive term. In our view, the most promising direction for removing the dependence on $d_m^*$ (and on the concentrability $C^*$) is to develop sample-efficient online algorithms, which is something that we plan to investigate in future work.

Complexity of RDPs : Several problem-specific parameters that appear in the sample complexity bound, such as $C^*$, $d_m^*$ and $\mu_0$, strongly depend on the complexity of the RDP. Concretely, if the RDP is reasonably small and has no low-probability branches, then we can control the magnitude of $C^*$ and $d_m^*$. As we show in the paper, we can also often control the magnitude of $\mu_0$ using our novel language metric. Hence the novel language metric should allow us to efficiently learn such well-behaved RDPs, even if the action and observation spaces are large. Since the lower bound of Cipollone et al. includes both $C^*$ and $\mu_0$, learning exact RDPs becomes significantly harder as the complexity of the RDP increases, no matter which algorithm is used.

Continuous observations or actions : Since we do not assume access to an existing label set, the only possibility we foresee is to learn a discrete latent representation ("labels") from experience, perhaps using unsupervised learning or another optimization objective, and use such latent variables as transition labels in the learned RDP.

Count-Min-Sketch : Note that the exponential complexity in the horizon H is due to the distinguishability of the $L_\infty$-norm, which is problem-dependent. Hence the exponential complexity is not due to CMS (which always improves the memory complexity), but instead due to the problem being solved and the metric used. This is precisely the limitation addressed by the language metric, which can unfortunately not be combined with CMS while maintaining strong sample complexity guarantees.

Notation : We have changed our notation for the set of RDP states from $\mathcal{Q}$ to $\mathcal{U}$ according to the suggestions of the reviewer.