Offline RL in Regular Decision Processes: Sample Efficiency via Language Metrics
Authors: Ahana Deb
Roberto Cipollone
Anders Jonsson
Alessandro Ronca
Mohammad Sadegh Talebi
Venue: ICLR 2025 Poster (2025)
Keywords: Reinforcement Learning
Non-Markov Decision Process
Offline Reinforcement Learning
Regular Decision Processes
Sample Complexity
Automata
Primary area: reinforcement learning
TL;DR: We propose two novel techniques to overcome the limitations of existing Offline Reinforcement Learning algorithms for Regular Decision Processes.

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.

Published as a conference paper at ICLR 2025
OFFLINE RL IN REGULAR DECISION PROCESSES: SAMPLE EFFICIENCY VIA LANGUAGE METRICS
Ahana Deb 1x Roberto Cipollone Anders Jonsson'
Alessandro Ronca
Mohammad Sadegh Talebi*
Universitat Pompeu Fabra- Leonardo S.p.A.
Uniivesstyy of Oxford
Univeersity of Copenhagen
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, consider episodic RDPs and show that it is possi- ble to overcome the limitations of existing offline RL algorithms for RDPs via the introduction of two original techniques: novel metric grounded in formal language theory and an approach based on Count-Min-Skeet the novel language metric, our algorithm proven to be more sample efficient than existing results, and in some problem instances admitting low complexity languages, the gain is showcased CMS-base based approach removes the need for naïve counting and alleviates the mem- ory 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
(CMS). Owing to
be exponential in the episode length. The
INTRODUCTION
The Markov assumption is fundamental for most Reinforcement Learning (RL) algorithms, requiring that the immediate reward and transition only depend on the last observation and action. Thanks to this property, computing qnear-Joptimen policies involves only functions over observations and actions. However, in complex environments, observations may not be complete representations of the internal environment state. In this work, we consider RL in Non-Markov Decision Processes (NMDPs) (Whitehead & Lin, 1995; Bacchus et al., 1997), expressive models where the probability of future observations and rewards may depend on the entire history, i.c. the past interaction sequence composed of observations and actions. However, the unrestricted dynamics of NMDPs make them intractable from both statistical and computational standpoints. This has steered much research effort towards tractable subclasses of NMDPs. In this work, we focus on Regular Decision Processes (RDPs) (Brafman & De Giacomo, 2019; 2024). In RDPs, the distribution of the next observation and reward determined by conditions over the history that, in terms of formal language theory, fall within the class of the regular languages. This is a rich class containing many fundamental temporal patterns, including all patterns that can be specified in Linear Temporal Logic (Manna & Pnueli, 1989; De Giacomo & Vardi, 2013) and those captured by Reward Machines (Toro Icarte et al., 2018; 2019; Toro Icarte et al., 2022). Thus, RDPs can model complex temporal dependencies that may be based on events that occur arbitrarily far in the past, e.g. that an agent may only enter a restricted area it has previously asked for permission and the access was granted. At the same time, RDPs enjoy many favouralle properties, which can be leveraged to develop effective RL algorithms. Prominently, the fact that the dynamics of an RDP can be represented by a probabilistic-detemminni automaton. This key fact is the basis of all existing RL algorithms for RDPs: learning the automaton underlying an RDP amounts to learning a representation of the histories that is instrumental to tackle non-Markovianity, it allows one to work with associated Markov Decision Process (MDP).
finite
Cooresponneecee to: ahana. deb@upž.edu
The work was conducted while the author was Sapienza University of Rome.

---

Published as a conference paper at ICLR 2025
Figure 1: T-maze (Bakker, 2001) with corridor length N = 10. The observation produced at the initial position S indicates the position of the goal G at the end of the corridor for the current episode.
S
It is worth noting that RDPs are related to decision processes operating under partial observability. More precisely, the automaton state of an RDP can be seen as a hidden information state (Subramanian et al., 2022), and as shown by Brafman & De Giacomo (2019), any RDP is also a POMDP (Kaelbling et al., 1998), whose hidden dynamics evolve according to its finite-state automaton. Thus RDPs constitute the class of POMDPs where hidden states are determined by the history of observations, namely, those in which the agent can have sharp beliefs. They also fall into the framework of Predictive State Representations (PSRs) (Bowling et al., 2006). Therefore, in the hierarchy of decision processes, RDPs greatly generalise MDPs, without introducing strong forms of partial observability present in more general processes, such as POMDPs, which quickly lead to intractability (Papadimitriou & Tsitsiklis, 1987). Despite such applicability. provably correct and sample efficient algorithms for RDPs are still missing. On one hand, local optimisation approaches are computationally efficient, but lack correctness guarantees, c.g. Abadi & Brafman (2020). Toro Iearte et al. (2019) and all RL algorithms with policy networks that can operate on sequences. On the other hand, algorithms with formal guarantees do not provide practical implementation (Cipollone et al., 2023; Ronca & De Giacomo, 2021) or can only be applied effectively in small environments (Ronca et al., 2022).
We study offline RL in episodic RDPs, where the goal is to find a near-optimal policy from a dataset pre-collected using a behavior policy. A recent algorithm called RegORL (Cipollone et al., 2023) achieves a sample complexity with polynomial dependency on the episode length and the number of actions, observations, and automaton states. Besides, the sample complexity inversely depends on a complexity notion called L distinguishabiitty, which is grounded in automata theory and captures the ability to distinguish between relevant histories generated by the behavior policy. This sample complexity bound exhibits two major drawbacks. First, the LP_ -istinguishaabiltty could be very small for
relative to problem parameters, and there exist RDPs in which L._- distinguishability = episode length H, as formalized in Theorem 1, which asserts that the sample complexity of RegORL can be exponential in H. Indeed, such an exponential blow-up is observed in many domains that seem simple from an intuitive point of view, such as T-maze by Bakker (2001), introduced below and discussed throughout the paper. Second, the only existing sample complexity lower bound presented in Cipollone al. (2023) depends on ffddstinguushabilit another complexity notion that is larger than IPp -iittinuushaabilityy and does not suffer from the exponential decay above. Thus, the following question naturally arises: Is possible to provably learn a near-optimal policy RDPs offline without requiring exponential (in H) sample complexity, while admitting computationally tractable implementation? We answer this question in the affirmative by developing novel algorithmic ideas that build on the theory of formal languages as well as using suitable data structure.
Example 1 (T-maze). As running example, we consider variant of T-Maze(c) (Bakker, 2001) that we call T-maze. An agent has to reach goal G from an initial position S a corridor length N that terminates with a T-junction as shown in Figure 1, using actions North, South, East, and West. In each episode, the rewarding goal G is placed above or below the T-junction uniformly at random. The initial observation of the agent is 011 if the goal is above the T-junction, and 110 otherwise. At every step in the corridor the observation is 101 or 111 with equal probability, and at the T-junction and beyond the observation is 010. In particular, when crossing the corridor, the agent cannot observe its precise location or the goal position. This yields history- -eeteeet dynamics that cannot be modeled by an MDP or any k-order MDP. As we show later, this domain can be expressed an RDP.
Contributions Our main contribution is provably sample efficient algorithm for offline RL in episodic RDPs. At the core is a statistical test defined via a novel language metrie Lx, whose design borrows ideas from the theory of formal languages. Its construction involves sophisticated way of expressively capturing relevant patterns on episode traces in the collected data, which allows for defining a suitable hierarchy of language families that proves effective for learning in RDPs. Specifically, as formalized in Theorem 3, this yields a PAC sample complexity bound that depends on new notion of complexity called bx--distingisshablii LB_ diiiiinuuihhabblityy and, importantly, does not suffer from an exponential blow-up in domains with low language- theoretic complexity. Second, we develop way compactly represent probability -hhooaie-
which offers more refined notion than
2

---

Published as a conference paper at ICLR 2025
distributions large sets in order to mitigate the memory requirements of RL algorithms that operate on large sets of histories. We develop a solution that uses the data structure Count-Min Minnk-Min-S (CMS) (Cormode & Muthukrishnan, 2005), taking inspiration from the automaton-learnins algorithm FlexFringe (Baumgartner & Verwer, 2023). To validate our claims, we provide theoretical analysis for both variants, when the lx--distiguussaabiitty CMS is used. Finally, report numerical experiments to demonstrate the empirical performance of the proposed approaches.
1.1 RELATED WORK
There is rich and growing literature on offline (Markovian) RL that covers a broad range of MDP settings; e.g., (Chen & Jiang, 2019; Jin et al., 2021; Li et al., 2024; Rashidinejad et al., 2021; Ren et at. 2021; Uehara & Sun, 2022; Uehara al., 2022; Xie et al., 2021; Yin & Wang. 2021; Zhan et al., 2022; Sun et al., 2023). In particular, it is by now well established that the optimal sample complexity in the episodic setting depends on the size of state-space, episode length, as well as some notion of concentrability, reflecting the distribution mismatch between the behavior and optimal policies, and optimal algorithms are reported (Li et al., 2024).
Non-Markovian RL The first online RL algorithm for RDPs is provided in Abadi & Brafman (2020). Ronca& & De Giacomo (2021) and Ronca et al. (2022) developed the first online RL algorithms with sample complexity guarantees, adapting analogous results from automata learning literature (Balle, 2013; Balle et al., 2013; 2014; Clark & Thollard, 2004; Palmer & Goldberg, 2007: Ron et al., 1998). Cipollone al. (2023) introduced RegORL, provably efficient algorithm for offline RL in RDPs. We study the same setting and improve on two weaknesses of RegORL regarding the sample complexity and the space requirements. RL with Markovvvn rewards have been studied via Reward Machines (Bourel et al., 2023; 2024; Giacomo et al., 2020; Hasanbeig et al., 2021; Toro Icarte et al., 2018; Xu et al., 2020). Existing literature, however, provide theoretical sample efficiency when the automaton of such processes is known, which makes the Markovian state computable; e.g.. the online RL algorithm in Toro Icarte et al. (2019) could be applied to RDPs, but it is not proven to be sample efficient. Lastly, non-Markovianity is also introduced by the logical specifications that the agent is required to satisfy (Bozkurt et al., 2020; Fu & Topcu, 2014; Hahn et al., 2019; Hammond et al., 2021; Hasanbeig et al., 2020); however, it is resolved priori from the known specifications.
POMDPs, PSRs, and State Representation As discussed, RDPs are also POMDPs, and any RL algorithm for POMDPs can be applied to RDPs. Tractable learning in POMDPs, our best knowledge, has been studied for special cases, such as undercomplete POMDPs (Guo et al., 2022: Jin et al., 2020), few-step reachability (Guo et al., 2016), ergodicity (Azizzadenesheli al., 2016), few-step decodability (Efroni et al.. 2022; Krishnamurthy et al., 2016), or weakly-revealing (Liu al., 2022). Hahn et al. (2024) further explore Omega-Regule Decision Processes (ODPs) which generalizes RDPs with an w-regular lookahead, and present classical complexity results. However, none of these fully capture the entire RDP class. Non-Markovian dynamics, and thus RDPs, fall into the framework of PSRs (Bowling et al., 2006; James & Singh, 2004; Kulesza et al., 2015; Singh et al., 2003). However, existing sample complexity bounds for online RL in PSRs (Zhan et al., 2023) involve PSR-specific parameters that do not immediately apply to RDPs. RDPs bear resemblance to state representation methods (Mahmud, 2010; Maillard et al., 2013; Ortner et al., 2019; Lattimore state space via their
et al., 2013), since they provide a compact way of mapping from histories underlying automata. However, existing bounds for state representations grow linearly in the number of representations, which is exponential in the number of states in our case.
2 PRELIMINARIES
Notation Given set y, A())) denotes the set of probability distributions over V. For a function
f: A()', (yy 5:) is the probability of y E y given x E X. Further, we write y ~ f(x) to abbreviate y f(- r). Given event E, I(E) denotes the indicator function of E, which equals 1 if E' is true, and otherwise. For any pair of integers m and n such that < m S n, we let [I,, m| : (m,... im.....nu n) and [n]] := [l]. The notation ((-) hides poly-logarithmic terms.
Count-Min-Sketech Count-Min- Monnt-Min-Sketch, or CMS (Cormode & Muthukrishnan, 2005), is a data structure that compactly represents large non-negative vector (V1...., Um). CMS takes two
3

---

Published as a conference paper at ICLR 2025
parameters de and input, and constructs matrix C' with d [log rows and w [ columns. For each row j E [c]]. CMS picks a hash function hy [mm] - [w] uniformly at random from a pairwise independent family (Motwani & Raghavan, 1995). Initially, all elements of and C equal O. An update (i, c) consists in incrementing the element v; by c >> 0. CMS approximates an update (i, c) by incrementing C(j. hi)) by for each j E [d]. At any moment, point query U; returns an estimate of t; by taking the minimum of the row estimates, i.c. U; min, C(j. h (i)). For each row j E [d]. since the updates for e; are always stored in the element CGi, (i)),, it follows that CÚJ, hg (i)) 2 Us. Hence each point query satisfies Ü; 2 Ui i.e. CMS never underestimates v,.
2.1 LANGUAGES AND OPERATORS
An alphaber a finite non-emply set of elements called letters. A string a over I' is concatenation a1 ... ag of letters from I"; we call É its length, and we write |x] L. In particular, the string containing no letters, having length zero, is a valid string called the empty string, and it is denoted by A. Given two strings
a1 dg and y b1 ........ .m. their concatenation zy is the string d1 .agbi ... bmn- In particular, xd = Ax = x. Note that [zy| = |x| + lyl. Concatenation is associative and hence we can write the concatenation 22 2g of an arbitrary number of strings. The of all strings over alphabet I is written as r and the set of all strings of length & is written as l Thus, n = T language is a subset of I Given two languages X₁ and X2. their concatenation is the language defined by X = {œ1σ² I1 E X1, E X2). When concatenating with a singleton language {zz, we often write Xx instead of X {z), and x instead of { X Concatenation of languages associative, allowing us to write the concatenation X1 ... X of an arbitrary number of languages.
Given the fundamental definitions above, we introduce a novel operator to construct sets of languages, which will play a key role in the algorithm design through defining relevant patterns on episode traces. inspired by classes of languages the first level of the dot-depth hierarchy, a well-known hierarchy of star-free regular languages (Simon, 1972; Thérien, 2005; Pin, 2017).
Definition 1. For E N and E [[] the operator C maps any set of languages G to a new set of languages follows:
( = (f ... III I Io...., Db. E I 100 zal (E (b) GI...., Gx E 9).
In the definition, each r; can be any string over the chosen alphabet I, including the empty string X. Thus, I; are arbitrary strings between string from G; and the next string from G,- Each resulting string consists of occurrences of letter from I or string from GI...., G3 E G. Different choices of GI...., G1 E 9 yield different languages in the resulting set.
Example 2. Let [ {a. b, c} and let G = {{a), {b)}. Then
C2 (g) = (ray 2, E r", |zy| = 9}, {aby |,,err, |ayl = =9}}
is the set consisting of (i) the language of all 10-letter strings that include an occurrence of and (ii) the language of all 10-letter strings that include an occurrence of b. Similarly.
(G) = { (wayaz x, E 1", |æya| 8), {abybz xx y, 2 E 1"", |æyz|| = 8),
{raybz y. r", zzyz| 8), (abyaz 2. y, 2 I"" |zyz| 8}}
is the set consisting of (i) the language of all 10-letter strings that include two occurrences of a, (ii) the language of all 10-letter strings that include two occurrences of b, (iii) the language of all 10-letter strings that include an occurrence of a followed by an occurrence of 6, (iv) the language of all 10-letter strings that include an occurrence of followed by an occurrence of
2.2 EPISODIC REGULAR DECISION PROCESSES
H), A generic episodic decision process is tuple P (O.A.R, H.,, where O is a finite set of
observations, A is a finite set of actions, R c [0, 1] is a finite set of rewards, and H > 1 is a finite horizon. We frequently consider the concatenation AO of the sets A and O. Let H, (AO)+t1 be the set of histories of length t + 1, and let Cm:n E Hn-m denote a history from time m to time n, both included. Each obstonnobservatiin pair ao AA in history has associated reward label r E R, which we write ooir E AO/R R with the understanding that the slash corresponds to string concatenation. A trajectory earr is the full history generated until (and including) time T.
4

---

Published as a conference paper at ICLR 2025
We assume that trajectory Cu:T' can be partitioned into episodes CEE+H E HH of length H + 1. In each episode 60:H, dg = T1 is a dummy action used to initialize the distribution on Ho. The transition function T'; H. x A - A(O) and the reward function R: H. x A - A(R) depend on the current history in H = H- Given P, a generic policy is a function π : (AQ)* - A ((A) that maps trajectories to distributions over actions. The value function V [0, H] x H. IR of a policy π is a mapping that assigns real values to histories. For & E H, is defined as V (H, H h) = 0 and
H1 Σ
(=(4h)= = E
V
< H, E He.
(I)
For brevity, we write (.*(h) == (* h). The optimal value function V is defined as V, (h) (h) = sup, V/5 (h), Vt E [0. H]. Yh E H4, where sup is taken over all policies π. (AO)- + AAA). Any policy achieving V is called optimal, which we denote by T"; namely V = V". In what follows, we consider simpler policies of the form x H + ((A) mapping finite histories to distributions over actions. Let 11x denote the set of such policies. It can be shown that 11 always contains an optimal policy, i.e. (h) = max V (h), VI E [H], Vh E He. A policy is 8-optimal iff Eno (Vo (ho) VO² (ho)] S E, where hg an for some random Og E O.
Episodic RDPs An episodic Regular Decision Process (RDP) (Abadi & Brafman, 2020; Brafman & De Giacomo, 2019; 2024) is an episodic decision process R (O, A, R. T, R, H) described by a finite transducer (Moore machine) (2, Σ, S2, T, 0, uo), where 2/ is a finite set of states, Σ = AO finite input alphabet composed of actions and observations, Ω is finite output alphabet, T u X Σ + 24 is a transition function, 0 2 + Ω is an output function, and tog E U is a fixed initial state (Moore, 1956; Shallit, 2008). The output space
22 22 consists of finite set of functions that compute the conditional probabilities of observations and rewards, on the form Q. C A + A(O) and S2 C A- + (RR). For simplicity, we use two output functions, f.. : U x A + A(O) and u x A - (RR). to denote the individual conditional probabilities. Let r- denote the inverse of - (w) S u x AO is the subset of state-symbol pairs that map to u E U. An RDP R implicitly represents a function F : H + U from histories in H to states in U1 recursively defined as (ho) == T(ug, anoo), where ag is some fixed starting action, and F(h,) == T(F((( q.o)). The transition function and reward function of R are defined as T( h, a) (o F(h), a) and R(r h, (,a)= = (r F(h), a), vh E H. vao/r E AO RR. As in previous work (Cipollone et al., 2023), we assume that any episodic RDP generates designated termination observation 01 E O after exactly H transitions. This ensures that any episodic RDP is acyclic, i.e. the states can be partitioned U1 14g U J....Z I + where each M++1 is the set of states generated by the histories in H4 for each t E [0. H1. An RDP is minimal if its Moore machine is minimal. We use A, O, R, U to denote the cardinality of A, O, R, U, respectively, and assume H 2 2, A 2 and O 2 2.
Since the conditional probabilities of observations and rewards are fully determined by the current state-action pair (u, a). an RDP R adheres to the Markov property over its states, but not over the observations. Given a state Ue E L and an action a; E A, the probability of the next transition is
PP(re Ot, Ue+1 Uy at, R.) = (,(re Ut, at) (o: at) (e. I(we+1 = ((e,aao0))
Since RDPs are Markovian in the unobservable states 21 there is an important class of policies that called regular. Given an RDP R. a policy π : H + A(A) is called regular T(h1) = ग (h2) whenever F(h,) = F(h2), for all h1, h2 E H. Hence, we can compactly define a regular policy as a function of the RDP state, i.c. π : 1 - ((A)) Let IRR denote the set of regular policies for R. Regular policies exhibit powerful properties. First, under regular policy, suffixes have the same probability of being generated for histories that map to the same RDP state. Second, there exists at least one optimal policy that is regular. Finally, in the special case where an RDP is Markovian in both observations and rewards, it reduces to a nonstationary episodic MDP.
Example 3 (RDP for T-maze). Consider the T-maze described in Example 1, for a generic corridor length N and horizon H = N + 2. This can be modeled as an episodic RDP (41 Σ, Ω. r, f. uo) with states U := uo U (fWI.T..... uN-3,T) U {_,...... UN+3, }) x {l...., H.. which include the initial state uo and two parallel components, T and J. for the N + 3 cells of the grid world. In addition, each state also includes a counter for the time step. Within each component {(u,T,,) t) and {u,,,, })}. the transition function 7 mimics the grid world dynamics of the maze and increments the counter t. From the initial state and the start action ag T(un, anan) equals u1,T T if on = 011, and $1 1. if oo = 110. In the initial state, observations are 0g (ug, aq) = unif 011}; in the
5

---

Published as a conference paper at ICLR 2025
corridor 0o (u a) unif ( 111) for every E [N]] and g {T, J]; and in the T-junction the observation is 010. The rewards are null, except for in the top right or bottom right cell, depending on if the current state is in the component T or -, respectively.
Distinguishability Consider a minimal RDP R with states U = Jo Given a regular policy UR and [0, HJ. each RDP state U4+1 defines unique probability distri- bution P(- M6+1 = u, X on episode suffixes in I where I = AO/ 'R is the alphabet of triplets. The states in U4+1 can be compared in terms of the probability distributions they induce over - Consider any I, = { where each Le is metric over A A(T)). We define the T-ddisinguishaabilty of R under as the maximum lig 2 0 such that, for any [0, H] and any two distinct u' U4+1, the probability distributions over suffix traces E:41: E p from the two states satisfy
netion-observation-rewzzz
Lu- (P(e Ue+1 = u, P(e2+) Uc41
x)) 2 P40
We will often omit the remaining episode length / = H t from I, and simply write L. We consider the I. distinguishabiiity, instantiating the definition above with the metric L (2), = maxje[q].e2] [pi (e*) p2(e=)), where x), i E {1, 2). represents the probability of the trace prefix E E 17, followed by any trace E p The LP diiistiiiguiss is defined analogously using (P1, P2) = maxjelq Eeero [p((e)) p)(
2.3 OFFLINE RL IN EPISODIC RDPs
Consider batch dataset DD comprising episodes sampled using a regular behavior policy Tb. Specifi- cally, the k-th episode (or episode trace) in D is of the form e/. a r ..aaf oft///// where, for each t E [[O, H],
-p = uo of ~ (ub), of 00 af), - ~ (ut wêt1 = r at of)
The learner seeks s-optimal policy स for given accuracy E (0, H. using the smallest dataset D possible, without further exploration. More precisely, we aim at finding i satisfying Vi V/) S e for each h E Ho with probability at least 1 5, using the smallest dataset D possible. We stress that in so doing xh and underlying RDP states u² are unknown to the learner. It suffices to restrict attention regular e-optimal policies (cf. Proposition 5 in Appendix B). However, some assumptions must be imposed on T² to provably guarantee that an 6-optimal regular policy can be learnt from D. We first recall the notion of occupancy. Given a regular policy л : + ((AA) and a time step t [0, H1. let dā e AlU x AO) be the induced occupancy, i.c. probability distribution over the states in Ue and the input symbols in AO, recursively defined as dī (uo, agoo) = 0s(op uo, ao) and
di (ut; ((o1)
Σ
di ao) T(ae u4) (o( Uee at), t 0.
(u,00)Er 1(1))
Of particular interest is the occupancy di = d associated with an optimal policy T", which is unique if we assume that x² is unique. Likewise, let dā = di be the occupancy associated with b..
As in offline RL in MDPs, is necessary to control the mismatch in occupancy between the behavior policy Thb and the optimal policy x². Concretely, the iigle-policy RDP concentrability coefficient associated with RDP and behavior policy T³ is defined as in Cipollone et al. (2023):
d; (u, 00)
CR
max WEIH AO db ao)
We assume that the concentrability is bounded away from infinity, i.e. that CR < co, which further implies that for any t E [H] E Ur db(u, a) > O whenever a E AA is chosen by an optimal policy.
3 LEARNING RDPs WITH STATE-MERGING ALGORITHMS FROM OFFLINE DATA
To learn episodic RDPs from a dataset of episodes, we adapt the algorithm ADACT-H (Cipollone et al., 2023). ADACT-H is state-merging algorithm that iteratively constructs the set of RDP states Ug...., ,,, and associated transition function 7 of a minimal RDP R. For each t E [o, H]. ADACT-H maintains set of candidate states Uc,t1 (uao E U1, AO} and set of

---

Published as a conference paper at ICLR 2025
promoted states U441. Each candidate state uao has associated multiset of suffixes ((ua)) = {cL-1, e" E "D 1) = u, a of = ao). i.c episode suffixes whose history is consistent with uao. Initially, U4+1 contains the candidate with largest multiset. To decide if candidate uao should be promoted to 14+1 or merged with promoted state v' E U4+1, ADACT-- compares the empirical probability distributions on suffixes using the prefix distance L.g For reference, we include the pseudocode of ADACT-H(D) (D, 8) in Appendix A. Cipollone et al. (2023) prove that ADACT-H(D, 6) constructs a minimal RDP R with probability at least 1 4AOU if D is large enough.
In practice, the main bottleneck of ADACT-H is the statistical test on the last line,
(2,, (2) /
(2log(((ARO)==110) min((Zz]) |22))
where 2, and Z2 are two multisets of traces in H associated with candidate state uno and promoted state u', respectively. This is because the number of episode suffixes in m is exponential in the current horizon H The purpose of the present paper is develop tractable methods for implementing the statistical test. These tractable methods can be directly applied to any algorithm that performs such statistical tests, e.g. the approximation algorithm ADACT-H-A (Cipollone et al., 2023) whose pseudocode we also include in Appendix A. Either algorithm can be incorporated into an offline RI. algorithm for learning an e-optimal policy, ef. Algorithm RegoRL in Appendix A.
A TRACTABLE ALGORITHM FOR OFFLINE LEARNING OF RDPS
The lower bound derived in Cipollone et al. (2023) shows that sample complexity of learning RDPs is inversely proportional to the L, diistinguissaabiitt.. When testing candidate states of the unknown RDP, IP is the metric that allows maximum separation between distinct distributions Unfortunately, accurate estimates of L2 are impractical to obtain for distributions over large supports- in our case the number of episode suffixes which is exponential in the horizon. Accurate estimates of L are much more practical to obtain. However, there are instances for which states can be well separated by L. but have an L -distance that is exponentially small. To address these issues, in this section we develop two improvements over the previous learning algorithms for RDPs.
traces.
4.1 THE LANGUAGE METRIC
Testing in the language metric The metries L1 and Les are generic and can be applied to any distribution. Although this is generally an advantage, they do not exploit the internal structure of the sample space. In our application, a sample is trace that, as discussed above, can be regarded as a string of specific language. An important improvement, proposed by Balle (2013), is to consider L and LP which take into account the variable length and conditional probabilities of longer suffixes. This was the approach followed by the previous RDP learning algorithms. However, these two metrics are substantially different and lead to dramatically different sample and space complexities.
In this section, we define of new techniques for distinguishing distributions over traces. Specifically, instead of expressing the probability of single strings, we generalize the concepts above by considering the probability of sets of strings. A careful selection of the sets to consider, which are languages, will allow an accurate trade-off between generality and complexity.
formalism that unifies both metrics and will allow the development
Definition 2 (Language metric). Let E E N, let I be an alphabet, and let X' be a set of languages consisting of strings in I" The language metric" in X' a function Lx : A(T*) x A(T") + E, on pairs of probability distributions p.p' over 1 defined as
Lx(p. p') = max | x'
XEX
where the probability of a language is p(X)= == Erex p(x).
This original notion unifies all the most common metrics. Considering distributions over I", when X {{x} I E ]r ). the language metric Lx reduces Loe. When X' 2 which is the set of all languages in _ the language metric becomes the total variation distance, which is half the value of LT A similar reduction can made for the prefix distances. The language metric captures Lg. when X = { E [0, []] x E r*), and it captures I, when X' = Use
Lxx only guaranteed to he pseudometric, but we call it metric for simplicity.
7

---

Published as a conference paper at ICLR 2025
Testing in language classes The language metric can be applied directly to the language of traces and used for testing in RDP learning algorithms. The language of traces is over the alphabet I 40/R. Thus, it suffices to consider any set of languages X' that satisfy X C r for each X E X. However, as we have seen above, the selection of a specific set of languages X' has a dramatic impact on the metric that is being captured. In this section, we study an appropriate trade-off between generality and sample efficiency, obtained through a suitable selection of A.. Intuitively, we seek to evaluate the distance between candidate states based on increasingly complex sets of languages. We present a way to construct hierarchy of sets of languages of increasing complexity. As first step, we define sets of basic patterns G. of increasing complexity.
(AORR) "-r
G = A (A
(0E0). G2 = 91 u (ao/R I A 0) J (aO/rlaa A R)
u a
G3 - 92 U {ao/r a A, o O, E...
The patterns 91 focus on single components, by matching single action a, reward r, observation o. Then, the patterns G2 focus on pairs, and the patterns 93 on triplets. Note that the number of basic patterns increases as we consider more interaction among actions, observations and rewards. For the first set we have | = A + 0 + R. for the second |92] |9 + AO + ARt + OR, and for the third G3l = G2l + AOR. Starting from the above hierarchy, we identify one more dimension along which complexity can grow. It results from concatenating the basic patterns from G. and is obtained by applying the operator C (Definition 1). Thus, letting = H L, we define the following two-dimensional hierarchy of sets Xi, of languages. It is parameterised by i for the granularity of the atomic symbols, and by j for the sequential composition with operator Cj. Formally,
X1 = UKEDI (G,)),
Vi [3], Vj E [[]
The family Xy induces a family of language metries Lx.,,> which are non-decreasing along the dimensions of the hierarchy:
Lxt, min (Ix Ix.s)): Vi e Vj E [4]
The number of languages in each set grows as | E ((()))) (((OR))), since the operator C introduces one language for each combination of languages from G. Hence the family Lx,,, has increasing complexity as we increase the values of the parameters i and j. Moreover, the last level X3,e satisfies Lxz,, 2 LP since {x-8-( | E [[, 4], x E9 X3,e. Therefore, the metric Lxs. is at least as effective as Le in distinguishing states. It can be much more effective as shown next.
Example 4 (Exponential gain in the T-maze). In the T-maze of Examples 1 and 3, when the behaviour policy x²b always chooses East in the corridor and North or South with equal probability at the T-junction, we observe the following exponential gap between the LE -distinguishabiiity and the L -distinguishaiiitt. The LP -distinguishability decreases exponentially with the corridor length N, since the distance between states is determined by the probability of single episode suffixes, which decreases exponentially with N due to the random observations in the corridor. At the same time, the Lx3,, -distinguishabiitty is constant. In this case, the distance between states is determined by the probability of observing a positive reward upon performing action North. This probability is 0.5 in states of kind T, and it 0 in states of kind 1. More formally, the distance between states in 24, is determined by the probability of the language (x North Ofr y x., y I |ryl = H --t+1} E X2.1-
The argument of the example can be developed into a proof of the following theorem, showing that the language metric can yield an exponential improvement in distinguishabiliy--pooo in Appendix C.
Theorem There exist a family of RDPs (R,))EE NeN and a corresponding of regular behaviour policies ( NeN satisfying the two following properties: (i) the digiiiiinguushaablii of Rxx under x is ( )) and (ii) the Lx2, -disinnuishability RN under N is 2(1).
Assumption The behavior policy nh ensures an Lx., -distiguishaaiiity of at least μg > 0, where X. is constructed as above and is an input to the algorithm.
Given & E [0, H]. let P1, P2 E A(T)) be two distributions over traces. To have accurate estimates for the language metric over some X.J. we instantiate two estimators, Pi and P2. respectively built using multisets of traces 2, and Z2, defined as the fraction of samples that belong to the language; that is,
Pi := Eeez, T(e &,2) |, and f22 = Ecez, e [e(e E /z
8

---

Published as a conference paper at ICLR 2025
4.2 ANALYSIS
In this section we derive high-probability sample complexity bounds for ADACT-H (presented in Appendix A) when Count-Min-Sketch (CMS) or the language metric Lx used.
Theorem 2. ADACT-H(D,, 6) returns the minimal RDP R. with probability at least 1 - 3AOU8
when CMS is used to store empirical probability estimates, the statistical test
IP (2) v (8log(((ARO)5-111)) min([ [2]);
and the size of the dataset D is at least (D] 2 Ô is the minimum occupancy of the optimal policy n..
HC 1o where d'm mi dj (ue, ao)
The proof of Theorem 2 appears in Appendix C. Our new analysis uncovered mistake in the proof of Cipollone et al. (2023), and as result, both their and our sample complexity has an additional multiplicative term /H/pu, /ug- The theorem shows that we can achieve the same asymptotic sample complexity when using CMS, but at much lower memory cost.
Theorem 3. ADACT-H(D,, (D))) returns the minimal RDP R with probability at least 2AOU8 when using the language metric Lx to define statistical test
Lx, 2 v (2 min( 211. 22)),
and the size of the dataset D is at least [D] Ō
CR 116) log X
The proof of Theorem 3 also appears in Appendix C. By definition, nn is the Lx-disstinuishaablityy of R. for the chosen language set X' which has to satisfy (40 > 0 for ADACT-H to successfully learn minimal RDP. In the worst case, log [2'| = (H), which matches the original bound. However, in the case of our language hierarchy X. if j is a small constant we have log | = (log((AOR))
OÚi log( (AOR)) = (1). The constant 1/dim depends exponentially on / if there exists an RDP state that very hard to reach, but can be much smaller for structured RDPs. In addition, as discussed earlier, 1/H0 may be exponentially smaller for Lx than for LP.. For completeness, Appendix C also proves sample complexity bounds for CMS and Lx for the approximation algorithm ADACT-H-A.
EXPERIMENTAL RESULTS
In this section we present experimental results illustrate the properties of our two versions of ADACT-H. We perform experiments in five domains from the literature on POMDPs and RDPs: Corridor (Ronca& De Giacomo, 2021). T-maze(e) (Bakker, 2001), Cookie (Toro Iearte et al., 2019). Cheese (MeCallum, 1992) and Mini-hall (Littman et al., 1995), and summarize the results in Table 1. Appendix D contains detailed description of each domain, as well as example automata learned. We compare against FlexFringe (Baumgartner& & Verwer, 2023), a state-of-the-ar algorithm for learning probabilistic-ddtemmiint
finite automata, which include RDPs as special case, The RDPs output by FlexFringe are not always directly comparable to the RDPs output by ADACT-H, since FlexFringe sometimes learns RDPs with cycles, and uses a number of heuristics that optimize performance, but which no longer preserve the high-probability sample complexity guarantees.
FlexFringe
CMS
Language metric
Name
H
U
time
U
time
time
Corridor
5
11
1.0
0.03
11
1.0
0.3
11
1.0
0.01
T-maze(c)
5
0.0
0.11
104
4.0
10.1
18
4.0
0.26
Cookie
9
220
1.0
0.36
116
1.0
6.05
91
1.0
0.08
Cheese
6
669
0.69 + .04
19.28
1158
0.4 + .05
207.4
1178
0.87 + .03
12.11
Mini-hall
15
897
0.33
.04
25.79
6098
0.86 + .03
29.90
Table Summary of the experiments. For each domain, the horizon, and for each algorithm, U the number of states of the learned automaton, is the reward of the derived policy, averaged over 100 episodes, and time is the running time in seconds of automaton learning. The maximum reward for all the domains is 1, except for T-maze(c) where the reward upon reaching the goal is 4.

---

Published as a conference paper at ICLR 2025
10
Language metric
10a
Language metric
10
CMS
CMS
Time (secs)
States
102
10
10
10-3
Corridor length
Corridor length
(a) Time (seconds) length of corridor
(b) Number of RDP states length of corridor
Figure 2: Impact of increasing the length of the corridor for the T-maze domain of Example 1.
In Table 1, we see that ADACT-H with the language family X3,1 is faster than FlexFringe in all domains except here FlexFringe fails find the optimal policy, since the heuristics used are not optimized to preserve reward-aa and outputs smaller automata than both FlexFringe and CMS in all domains except Mini-hall. Since the number of languages in X3.1 1 is independent H, the statistical test does not have to iterate over all suffixes, and the resulting RDPs better exploit the underlying structure of the domains. the CMS-based approach, despite having a more compact representation of the probability distributions, the statistical test still has iterate over all suffixes, which is exponential H for the L distance, and exceeds the allotted time budget of 1800 seconds in the Mini-hall domain. In Corridor and Cookie, all algorithms learn automata that admit optimal policy. However, in T-maze, Cheese and Mini-hall, the RDPs learned by ADACT-H with the language family Xn,1 admit policy that outperforms those of FlexFringe and CMS.
To better illustrate the improvement in performance for our language-bars based algorithm, in Figure function of the corridor length in T-maze
compare the time and number of RDP states (Example 1) for our two methods based on CMS and the language metric, respectively. With the increasing corridor length V (and horizon H N), we plot the time taken and RDP size over 20 runs, with K = 100 episodes. Figure 2a shows the time taken for the CMS-based algorithm increases exponentially whereas there is only linear increase for the language- expected since the number of RDP states generated also increases linearly with H. In Figure 2b, the plot indicates the size of the RDP states produced by the language based approach optimal (~2H), and grows exponentially with H for the CMS approach. We also extend this experiment by increasing N up to 100, observing the same trend for our language-bas approach. However, CMS suffers from slow running times, and exceeds 1800 seconds of rumning time over 20 runs after H 15.
approach, which is
CONCLUSION
In this paper, we propose two new approaches offline RL for Regular Decision Processes and provide their respective theoretical analysis. We also improve upon existing algorithms for RDP learning, and propose modified algorithm using Count-Min-Sketee with reduced memory complex- ity. We define a hierarchy of language families and introduce language-based approach, removing the dependency on L -distinguishabiiity parameters and compare the performance of our algorithms to FlexFringe. state-of-the-an algorithm for learning probabilistic deterministic finite automata. Although CMS suffers from a large rumning time, the automata and optimal (or near optimal) policies, even in domains requiring long-term dependencies. Finally, as future work, we plan to expand our approach to the online RDP learning setting, and investigate how leam R RDPs with cycles.
restricted approach offers smaller
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work has been co-funded by MCIN/AEE/11. 13039/50111010110110110 10001 1033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-00) 195-M). Anders Jonsson is partially supported by AGAUR 2021 SGR 00933 and Spanish grants PID2019- 1122019-181-11 14-11001440 11111-II00 and SL-PID2023-14714555 100. Alessandro Ronca is supported by the European Research Council (ERC) under the European Union's s Horizon 2020 research and innovation programme (Grant agreement No. 852769, ARiAT). Mohammad Sadegh Talebi acknowledges partial support by the Independent Research Fund Denmark, grant number 1026-00397B.
REFERENCES
Eden Abadi and Ronen I. Brafman. Learning and solving Regular Decision Processes, In International Joint Conference on Artificial Intelligence (ICAA), pp. 1948-1954, 2020.
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of POMDPs using spectral methods. In Conference on Learning Theory (COLT), pp. 193-256, 2016.
Fahiem Bacchus, Craig Boutilier, and Adam Grove. Structured solution methods for non-Markovian decision processes. In AAAI/IAAI, pp. 112-117, 1997.
Bram Bakker. Reinforcement learning with long short-term memory. In Neural Information Process- ing Systems (NeurIPS), pp. 1475-1482, 2001.
Borja Balle. Learning Finite-State Machines: Statistical and Algorithmic Aspects. PhD) thesis, Universitat Politècnica de Catalunya, 2013.
Borja Balle, Jorge Castro, and Ricard Gavaldà. Learning probabilistic automata: A study in state distinguishability. Theor. Comput. Sci., 473:46 60, 2013.
Borja Balle, Jorge Castro, and Ricard Gavaldà. Adaptively learning probabilistic deterministic automata from data streams. Machine Learning, 96(1):99-12) 127, 2014.
Robert Baumgartner and Sieco Verwer. Learning state machines from data streams: generic strategy and an improved heuristic. In International Conference on Grammatical Inference (ICGI), pp. 117-141, 2023.
Hippolyte Bourel, Anders Jonsson, Odalric- Ambrryc Maillard, and Mohammad Sadegh Talebi. Ex- ploration in reward machines with low regret. In International Conference Artificial Intelligence and Statistics (AISTATS), pp. 4114-4146, 2023.
Hippolyte Bourel, Anders Jonsson, Odalric-Ambrym Maillard, Chenxiao Ma, and Mohammad Sadegh Talebi. Provably efficient exploration in reward machines with low regret. arXiv preprint 2412 2024.
Michael H. Bowling, Peter McCracken, Michael James, James Neufeld, and Dana F. Wilkinson. Learning predictive state representations using non-blind policies. In International Conference on Machine Learning (ICML). pp. 129-136, 2006.
Alper Kamil Bozkurt, Yu Wang. Michael M. Zavlanos, and Miroslav Pajic. Control synthesis from linear temporal logic specifications using model-free reinforcement learning. In International Conference on Robotics and Automation (ICRA), pp. 10349-10355, 2020.
Ronen I. Brafman and Giuseppe De Giacomo. Regular Decision Processes: A Model for Non-
Markovian Domains. In International Joint Conference on Artificial Intelligence (IJCAI), pp. 5516-5522, 2019.
Ronen Brafman and Giuseppe De Giacomo. Regular decision processes. Artificial Intelligence. 331:104113: 13,113,770 2024.
Jinglin Chen and Nan Jiang. Information-theoree considerations in batch reinforcement learning. In International Conference Machine Learning (ICMI.), pp. 1042-1051, 2019.
11

---

Published as a conference paper at ICLR 2025
Roberto Cipollone, Anders Jonsson, Alessandro Ronca, and Mohammad Sadegh Talebi. Provably efficient offline reinforcement learning in regular decision processes. In Neural Information Processing Systems (NeurIPS), 2023.
Alexander Clark and Franck Thollard. PAC-learnability of probabilistic deterministic finite state automata. J. Mach. Learn. Res., 5:473-497, 2004.
Graham Cormode and S. Muthukrishnan. An improved data stream summary: the Count-Min Sketch and its applications. Journal of Algorithms, 55(1):58-775 2005.
Giuseppe De Giacomo and Moshe Vardi. Linear temporal logic and linear dynamic logic on finite traces. In International Joint Conference Artificial Intelligence (IJCAI), pp. 854-860, 2013.
Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforcement learning with a short-term memory. In International Conference on Machine Learning (ICML), pp- 5832-5850, 2022.
Jie Fu and Ufuk Topcu. Probably approximately correct MDP learning and control with temporal logic constraints. In Robotics: Science and Systems (RSS), 2014.
Giuseppe De Giacomo, Marco Favorito, Luca locchi, Fabio Patrizi, and Alessandro Ronca. Tem- poral logie monitoring rewards via transducers. In Principles of Knowledge Representation and Reasoning (KR), pp. 860-870, 2020.
Hongyi Guo, Qi Cai, Yufeng Zhang, Zhuoran Yang, and Zhaoran Wang. Provably efficient offline reinforcement learning for partially observable Markov decision processes. International Conference Machine Learning (ICML), pp. 8016-8038 2022.
Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A PAC RL algorithm for episodic POMDPs. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 510-518, 2016.
Ersst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtezak. Omega-regular objectives in model-free reinforcement learning. In Tools and Algorithuss for the Construction and Analysis of Systems (TACAS), pp. 395-412, 2019.
Ernst Moritz Hahn, Matco Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtezak. Omega-regular decision processes. Proceedings of the AAAI Conference Artificial Intelligence, 38(19)21125522111 Mar. 2024, doi: 10. htt.:////aa...8.....3111.. URL https: //ojs aaai wwwp/orwr.../i.o//..e/eeeeee.eee
Lewis Hammond, Alessandro Abate, Julian Gutierrez, and Michael Wooldridge. Multi-agent reinforcement learning with temporal logic specifications. In Autonomous Agents and Multiagent Systems (AAMAS), pp. 583-592, 2021.
Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening. Cautious reinforcement learning with logical constraints. In Autonomous Agents and Multiagent Systems (AAMAS), pp. 483-491, 2020.
Mohammadhosein Hasanbeig, Natasha Yogananda Jeppu, Alessandro Abate, Tom Melham, and Daniel Kroening. DeepSynth: automata synthesis for automatic task segmentation in deep reinforcement learning. In AAAI Conference on Artificial Intelligence, pp. 7647-7656, 2021.
Michael R. James and Satinder Singh. Learning and discovery of predictive state representations in dynamical systems with reset. In International Conference on Machine Learning (ICML), 2004.
Chi Jin, Sham M. Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete POMDPs. In Neural Information Processing Systems (NeurIPS), 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In
International Conference on Machine Learning (ICML), pp. 5084-5096, 2021.
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artif. Intell. (01(19))99-133, 1998.
12

---

Published as a conference paper at ICLR 2025
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In Neural Information Processing Systems (NewrIPS), pp. 1840-1848, 2016.
Alex Kulesza, Nan Jiang, and Satinder Singh. Spectral learning of predictive state representations with insufficient statistics. In AAAI Conference Artificial Intelligence, pp. 2715-2721, 2015.
Tor Lattimore, Marcus Hutter, and Peter Sunehag. The sample-complxxity of general reinforcement learning. International Conference on Machine Learning (ICML), 2013.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offiin reinforcement learning. The Annals of Statistics, 52(1):233-260, 2024.
Michael L. Littman, Anthony Cassandra, and Leslie Pack Kaelbling, Learning policies for partially observable environments: Scaling up. In International Conference on Machine Learning (ICML), pp. 362-370, 1995.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When partially observable reinforcement learning not scary? In Conference on Learning Theory (COLT), pp. $175-5220, 2022.
M. M. Hassan Mahmud. Constructing states for reinforcement learning. In International Conference on Machine Learning (ICML), pp. 727-734, 2010.
Odalric-Ambryee Maillard, Phuong Nguyen, Ronald Ortner, and Daniil Ryabko. Optimal regret bounds for selecting the state representation in reinforcement learning. In International Conference on Machine Learning (ICMI.), pp. 543-551, 2013.
Zohar Manna and Amir Pnueli. Completing the temporal picture. International Colloquium on Automala, Languages and Programming (ICALP), pp. 534-558, 1989.
R. Andrew McCallum. First results with utile distinction memory for reinforcement learning. Technical report, University of Rochester, USA, 1992.
Edward F Moore. Godanken--xperiments on sequential machines. Automata studies, 34:129-153, 1956.
Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995.
Ronald Ortner, Matteo Pirotta, Alessandro Lazaric, Ronan Fruit, and Odalric-Ambrym Maillard. Regret bounds for learning state representations in reinforcement learning. In Neural Information Processing Systems (NeurIPS), pp. 12717-12727, 2019.
Nick Palmer and Paul W. Goldberg. PAC-Icamability of probabilistic deterministic finite state automata terms of variation distance. Theor. Comput. Sci., 387(1):18-31, 2007.
Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of Markov decision processes. Mathematics of Operations Research, 12(3):441-450, 1987.
Jean-Éric Pin. The dot-depth hierarchy, 45 years later. The Role of Theory in Computer Science: Essays Dedicated Janusz Brzozowski, pp. 177-201- 2017.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. In Neural Information Processing Systems (NeuriPS), pp. 11702-11716, 2021.
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free off reinforcement learning. In Neural Information Processing Systems (NeurIPS), pp. 15621-15634, 2021.
Dana Ron, Yoram Singer, and Naftali Tishby. On the Icarnability and usage of acyclic probabilistic finite automata. J. Comput. Syst. Sci., 13(2):133-111) 1998.
Alessandro Ronea and Giuseppe De Giacomo. Efficient PAC reinforcement learning in regular decision processes. International Joint Conference on Artificial Intelligence (IJCAI), pp. 2026- 2032, 2021.
13

---

Published as a conference paper at ICLR 2025
Alessandro Ronca, Gabriel Paludo Licks, and Giuseppe De Giacomo. Markov abstractions for PAC reinforcement learning in non markov decision processes. In International Joint Conference on Artificcal Intelligence (IJCAI), pp. 3408-3415 2022.
Jeffrey Shallit. second course in formal languages and automata theory. Cambridge University Press, 2008.
Imre Simon. Hierarchies of events with dot-depth one. PhD thesis, University of Waterloo, 1972.
Satinder Singh, Michael L. Littman, Nicholas K. Jong, David Pardoe, and Peter Stone. Learning predictive state representations. In International Conference on Machine Learning (ICML), pp. 712-719, 2003.
Jayakumar Subramanian, Amit Sinha, Raihan Seraj, and Aditya Mahajan. Approximate information state for upproximate planning and reinforcement learning in partially observed systems. Journal of Machine Learning Research, 23(1):883-565, 2022.
Yihao Sun, Jiaji Zhang, Chengxing Jia, Haoxin Lin, Junyin Ye, and Yang Yu. Model-bellman inconsistency for model-based offline reinforcement learning. In International Conference on Machine Learning, pp. 33177-33194. PMLR, 2023.
Denis Thérien. Imre simon: an exceptional graduate student. RAIRO Theor. Informatics Appl., 39(1): 297-304, 2005.
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Anthony Valenzano, and Sheila A. Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning (ICML), pp. 2112 2121, 2018
Rodrigo Toro Icarte, Ethan Waldie, Toryn Q. Klassen, Richard Anthony Valenzano, Margarita P. Castro, and Sheila A. Mcllraith. Learning reward machines for partially observable reinforcement learning. Neural Information Processing Systems (NeurIPS), pp. 15497-15508, 2019.
Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Anthony Valenzano, and Sheila A. Mellraith. Reward machines: Exploiting reward function structure in reinforcement learning. J. Artif. Intell. Res., 73: 173-208, 2022.
Masatoshi Uchara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. International Conference on Learning Representations (ICLR), 2022.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RI. in low-rank MDPs. In International Conference on Learning Representations (ICLR), 2022.
Steven D Whitehead and Long-Ji Ji Lin. Reinforcement learning of non-Markov decision processes. Artificial intelligence, 73(1-2) 73(1-2):271-306 1995.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforeement learning. In Neural Information Processing Systems (NeurIPS), pp. 77395-27440 2021.
Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topcu, and Bo Wu. Joint inference of reward machines and policies for reinforcement learning. International Conference Automated Planning and Scheduling (ICAPS), pp. 590-598, 2020.
Ming Yin and Yu-Xiang Wang- Towards instance-optimal offline reinforcement learning with pessimism. In Neural Information Processing Systems (NeurIPS), pp. 4065-4078, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory (COLT), pp. 2730-2775. 2022.
Wenhao Zhan, Masatoshi Uchara, Wen Sun, and Jason D. Lee. PAC reinforcement learning for predictive state representations. In International Conference on Learning Representations (ICLR), 2023.
14

---

Published as a conference paper at ICLR 2025
A PSEUDOCODE OF ADACT-H, ADACT-H-A AND REGORL
In this section we present the pseudocode of ADACT-H, the approximation algorithm ADACT-H-A and the full reinforcement learning algorithm RegORI.
Function ADACT-H(D), ò)
Input: Dataset D of traces in r++1, failure probability 0 <
Output: Set of RDP states, transition function 7 :UxAAO-
Uo - {uo) (uu)) +
// initial state
for == o..... H do
Mc.t+1 {uao
// get candidate states foreach uno E Uc,4+1 do Z(uao) +- fEL+I:1 aroe E 2(u) // compute suffixes Um t- arg maxumoEl4 [2(ua0)
Uc ao E AO]
// most common candidate
Uc+1 [um@mmm) (1mm; am0m) mm0mmm Mct+1 Uc.e+1 {Ummmmm) for uao E Uc. do
// promote candidate
11 remove from candidate states
Similar +- {u' le+1 not TESTDISTINCT(t, Z(uao), Z(n'),8) // confidence test if Similar 0 then U441 U4+1 U {uao). (uao).T(u,a0
// promote candidate else u' < element in Similar, (u, ao) = v' 2(n') + 2 U ((ao)) // merge states end
11
12
13 end
return Uo U... U...UUK Ul
15
Function TESTDISTINCT(L, 2,, Zz, 8) return 1% (Z1, 22) 2 (R)) min 21, 22))
Function ADACT 8, U.
Input: Dataset D of traces in +1+ failure probability 0 < 8 accuracy (0, H.. bounds U and C
Output: St' of RDP states, transition function r' :'' AO +
ug < [ua]. 2 (ua) +- D
// initial state 1/ initiall side state
U/ 4 U (mā), ((u))= +
for tort=00 0,..., H do
U(41 + {
// side state get candidate states foreach uao E U6 1 do 2 (wao) t- fe++1: aroc++1: E 2(u) // compute suffixes [(uao)
foreach ao E AO do ('f ao) = ui+1, B(ui+1) + (6411: arre E (uf))
Ve {uao
Uú, E AAO}
Um0mmm +- arg maX 2e11 11
most common candidate
Ul41 Ul41 (umAmOm) ). (Um: Om0m) Um0 Om
promote candidate
10
U6.+1 + Uceet {mm
remove from candidate states
for uao E Uc such that [(uao)) 2 3e/(10 do
11
Similar < {u' 24b+1 not TESTDISTINCT(S Z(uao), 2(n'),)) // confidence test if Similar 0 then Ui + U6.1 U [ua)}, r'(u, 00) = uao // promote candidate clse u' +- element in Similar, 7' (u, n', 2(u') Z(u') // merge states if 161 + 116+111 > U then return Failure end
13
16
17
for
uno E U6,+1 such that [3(ua)) < 3e/(10 do T' (u, ao) = ui Z(u & 2 (( 1 U Z(uao) // merge with side state
18
19
end
20
end
return 26 U... U...U U4 r'
15

---

Published as a conference paper at ICLR 2025
Algorithm I: RegoRL
Input:
Dataset D, accuracy E E (0, H), failure prohability 0 < < 1, (optionally) upper bound on [u4]
Output:
Policy $ H ((A)
D1, D2 + separate DD into two datasets of the same size
14, < ADACT-H(P:, 6/(0 (4)) where U 2(AO)* # if not provided
DD2 Markov transformation of D2 with respect to
Am + (P2,
return # Am (T(h))
B PROPERTIES OF REGULAR POLICIES
In this appendix we restate two propositions from Cipollone et al. (2023). We refer the reader to the proof's in that paper.
Proposition 4. Consider an RDP R., a regular policy E IR and histories hu and h2 in Hi t E [H) such that 7(h1)= = =h2).. For each suffix 6+41:1 E H-t the probability of generating 6.41:H is the same for h1 and h2, i.e. F(e+41:H h1, n. R) P(e++1.H h2, n, R).
Proposition 5. Each RDP R has at least one optimal policy n' E IlR.
C PROOF OF THEOREMS
In this appendix we first prove Theorem 1. Then we prove Theorems 2 and using series of technical lemmas, and deseribing first how implement ADACT-H using CMS.
C.I PROOF OF THEOREM 1: EXPONENTIAL IMPROVEMENT VIA THE LANGUAGE METRIC
Theorem 1. There exist a family of RDPs (R,) New and corresponding family of regular behaviour policies (x NeW satisfying the two following properties: (i) the L distiiiguuuss of RN under T& is O -22;; and (ïi) the Lx,, -ditinguiihhbbiiiyy of RN under y is 2(1).
Proof. Let R.y be the RDP described in Example where N is the corridor length and the horizon is H N 1. Let T be the policy for R that always chooses East in the corridor, and chooses North South with equal probability at the T-junction.
We show the first point by showing that the L& -distinnuuisaabiityy is at most 0.5 It suffices to show
L (P #
(, | u', m²)m))) I 0.5.
for any states u, u' E U1 Then inequality proven immediately since the L -distane is upper- bouuddd by the probability of any single episode suffix é1:H, which is 0.5. In particular, factor 0.5 due to the uniform choice of an action at the T-junction, and N- uniform probability over the two possible observations when we take step in the corridor, for a total of times.
i is due to the
We show the second point by showing that the Lx2,, -distinguishabiliyy is at least 0.5. Let E [N+1]] and us consider two distinct states u, E Ur. It suffices to show
Lxz (P(en: We u, R) P(en. ur = u', +))) 2 0.5.
Since 24 {wo} is singleton, have t > 1. and hence set of languages X2,1 includes X = fa North O/r y x, y.y E rr, Jry] = H - + 1}. which the language consisting of all episode suffixes where the positive reward is obtained upon performing action North. The probability of language X is 0.5 given u, = u, and it is given u, u'. This proves the claimed inequality and hence the theorem.
( and u' (u.,1, t). The
16

---

Published as a conference paper at ICLR 2025
C.2 ANALYSIS CMS
Given a finite set y = {yn...... Mm and a probability distribution E A let p E (Y) be an empirical estimate of p computed using n samples. CMS can store estimate p of the empirical distribution p. In this setting, the vector = (V1,..., Um) contains the empirical counts of each element of V, i.c. for each i E [m]] is is the number of times that we have observed element yi- Given n samples, we have || = n and p(y)) = w//n for each ys E V. The following lemma shows how to bound the error between p and p.
Lemma 6. Given finite set Y, probability distribution p E (Y), and an empirical estimate P E ( of obtained using n samples, let p be the estimate of P output by CMS with parameters de and E. With probability at least 1 VV1oe it holds that || pl S
Proof. Cormode & Muthukrishnan (2005) show that for a point query that returns an approximation 0 of vi, with probability at least - 5, it holds that
S 0 + E|
In our case, the estimated probability of an element y/ Y equals p(y)) u, where ūn is the point query for yı. Using the result above, with probability at least - de we have
p(y) 03
Us
e||u|| f(y: +
Since CMS never underestimates a value, (()) S p(v) trivially holds. Taking a union bound shows that the inequality above holds simultaneously for all y; E y with probability 1 (3/66e.
In our setting, y = r for a fixed f E [H]] Given a failure probability and a multiset 2 of elements in r we set the parameters of CMS to ò, = ó/ (AOR)) and = (1og(2(AOR)) / This implies that the size of the matrix of CMS is proportional to
(AOR)*
2|
(((AOR)
log
e log
log (2(AOR)1/5) < < log
5e
E
8
V2 + log(1/5))
Hence the memory complexity is much smaller than [1', the number of elements in v. Since (AOR)* = 11,, Lemma implies that | ~l holds with probability at least d.
Given language X c the estimation error jp(X) x(X) due to CMS is proportional to |X E. which is large X contains many elements. Alternatively, for a language set X (X1..... Xmm we could use the vector element e; of CMS to count the number of elements of Z that are also members of X,. However, if the languages overlap (which is the case for many of our language families), then ||w||| n no longer holds, and neither does Lemma 6. Hence it is only practical to use CMS to estimate the error the language metric Lx when the languages in X are small and disjoint.
To bound the prefix distance LP, (Puao. PuLo) between the empirical and estimated distributions suffixes of length - 6, for each candidate state (u, ao) E U4 x AO we need H t copies of CMS to store the counts for suffixes of different lengths & [ tl. We define an associated event Ecms to correctly bound LP (Puao- Puzo) for all candidate states:
- {
log 1og(2(AOR)H-110)
EcMs
E [0, H], (u, ao) E Ue x AO L (Pueor Puaoo) S==
2|
Since the number of instances of CMS is less than HU AO, event EcMs occurs with probability at least 1 HU A08.
C.3 TECHNICAL LEMMAS
The following technical lemmas largely follow the analysis of Cipollone et al. (2023). However, we reformulate the lemmas in terms of the language metric Lx and make them more modular in order to adapt them to our different settings. We first prove a high- probbbrbbabylityy upper bound on the language metric Ix between the true suffix distribution and its empirical estimate for any candidate state.
17

---

Published as a conference paper at ICLR 2025
Lemma 7. Given timestep [0. H|,, candidate state (u, 00) E U4 x AO, multiset 2 (uuo) of suffixes I and a set X of languages defined on p with probability at least - the language metric Lx satisfies
1og(2){8160)
Lx (Pusor (PusorPuao)
2 (wao)
where Puno E A(T is the true distribution on suffixes in r that start from (u, ao), and Puno is the empirical estimate of Puao induced by (uua)..
Proof. For each language X E X, let Puno (X) E Leex Paso (z) be the true probability of X, and let ( En Z(pp)) I(x E x)))2 be the empirical estimate of Paso ( ie. the proportion of elements in Z (uao) that also in X. Hoeffding's 's inequality implies that
12g(2/55) 2 2
|Puao - Puao(X))
I 6g.
Choosing & = 6/ and taking a union bound implies that Lx satisfies
1og(21X1/0))
Lx Lxx(Faao Puao) max (Xaa(() Puno (X)o V 2 ()2()))))
Xex
with probability - 1 = - which completes the proof.
We define an associated event Ex to correctly bound the language metric Lx for all (u, 2o):
1og
Ex
Vt E [0o H], (u, ao) E Eu x AO: Lx (Puaor Puao) S V 2 2uao)
We prove high-probability sample complexity bound for accurately estimating the empirical occupancy p(uao) of each candidate state uno E l x AO. Given a number of episodes N, an empirical Bernstein inequality yields
2p( umo) log(4/0)
14gg((4
P pp(ao) (1,
8.
N
3N
Given failure probability 8, let Gs be the function for the bound in the empirical Bernstein inequality, defined as
Go = 2plog(4/8)
14 14go((4/8)
N
3.V
It is easy to see that G3 is monotonically increasing in e and monotonically decreasing in N. We define an associated event εg to correctly bound ((uao) de (u, ao) for all ao):
EB (vt [o, H], (u, ao) Us AO:
(u, ao) S Gs(P(uao), N)) [p(ua)) du,
We show that control the number of episodes N to obtain upper bound the function Gs- Lemma 8. For fixed probabilities 8 and p. N 2 16log(4/6)/5 it holds that (G, N) 2p.
Proof. We first show that the inequality holds for N = 16 (olog(/8)) In this case we have
27 log (og(4/))
log
14
3Gs N) =3/ 16 logg (4/5)
+
パ< 2p.
16 1olog(4/1)
/8
16
The case N 16log(4/6)/7 follows from the fact that G3 is monotonically decreasing in N,
Since (umo) [uaa))/NN implies N (/Hoo))(((uo))) we obtain the following corollary.
18

---

Published as a conference paper at ICLR 2025
Corollary 9. Under event Eg, if (u(oo) 16log(4/8) it holds that (p(uao) du ao)l Σ 2p(uao)/3.
We show that under event εg, we can choose the sample complexity N to ensure that we obtain at least certain number of elements in (uuo)).
Lemma 10. Given candidate state uao Ur AO and any b 1, under event &n it holds that [nao)] 2 blog(4/6) if the sample complexity satisfies
log( (4/(4/)) di (u, ao)
N
(2b 31/6).
Proof.
Letting M = (uao),, due to event &n and the given bound on N it holds that
M
db (u, (u) 00)
N I Gs(M/N,N)
< M + NG,(M/N,
(d,
< M + 22M log (4/8) + 14 log(//0)) - log(4/8) (2b + 31/6)
M + /2 log 4/5) M log (400) (2b 1/2).
Solving the quadratic inequality for positive v M yields
log(4/0)
log(4 (4/)
VM 2
+ log(4/6) (2b 1/2)
2
2
log(4/0)
1og(4/0)
2b log(4/8)
2
log(4/0)
1og(4/8) + 26 log (4g(/))
Vblog(4/0),
2
V2
where we have used the inequality v + (Vi + vT)/
Hence the bound on N in the lemma
VM² > blog(4/6).
implies that M
C.4 PROOF OF THEOREM? 2
Let DESTITISSS the version of TESTDISTINCT that uses the statistical test in the theorem. To prove Theorem 2, show that TESTDISTINCTeME answers correctly if the multisets Z and Z2 have a given minimum size McMs, both when the suffix distributions are the same and when they different. These lemmas analogous to Lemmas 13 and 14 of Cipollone et al. (2023).
Lemma 11. For t [0, H]] let 21 and Z2 be multisets sampled from distributions P1 and P2 on At) If we use CMS with parameters & /log(2i (ong(((AO))) AOR))-t/0)/2
and ö = 8/ (/(OR)H-- H-t to store an approximation ps of the empirical estimate Pr of p: induced by Z, E [2]] if events &CMS and Ex hold, and i = P2, then TESSDDISINCCTMMs 2,, 22, 0) returns false.
Proof. For i E [2], LE ( p.) Lx pi) if X contains one language for each prefix from I Events EaMS and Ex and the triangle inequality now imply that
implying | 5 ((AOR)
L. (1i, F2) < T.P. (1) + Txxe (Pi, p1) + (p1 p2) + Txx (p2. + L.P. (f2, P2)
log(2( (2AR
1og(2){(1/0)
log(2)X')
log (2(AOO)))-H///)
0
2|21
2
2|
2|
blog(4 (0((AAOO))--100)
min([2]] /22))
This is precisely the condition for which TESTDISTINCTENSS returns false.
19

---

Published as a conference paper at ICLR 2025
Lemma 12. For t E [0, H]], let 21 and Zअ be multisets sampled from distributions P1 and P2 on A(TH--): If we use CMS with parameters & = (AOR) to store approximation p. of the empirical estimate Ps of P. induced by Zz i E [2]. if events &CMs and Ex hold, and if p1 # p2, then "ESTDISTINCTCMM((( 21, 22, returns true if 21 and Z2 satisfy min([21], |2)) 2 32 (ogg /5)/n/
and 6c =
Proof.
Using the same argument as in the proof of Lemma 11 yields
L. (PI.P2)
2 Lx(P2, P2)
LP P1)
Lx (P1.
(P2, P2)
L. (P2.P2) P2)
(e(((AOR)))11))
log (2//21///0)
log (2) 1og(2)
22121/06)
(o)(2(AOR)) (18))
2 140
2/2,1
2/ 2
2 221
2|
8 log(4 (10)))
2
8 (log(((AOR)#E)
140
2 40
140
min( 22l)
2
min( (22))
where we have used the condition min ( for which TESTDISTINCTOMS returns true.
12]) in the lemma. This is precisely the condition
We next show that ADACT-H returns a minimal RDP if the multiset ((uo)) associated with each candidate state uno satisfies [((oo] 2 (eeloo((AAR))
= McMs-
Lemma 13. Under events ECMS and Ex, ADACT-H outputs a minimal RDP R. if the multiset Z(woo) associated with each candidate state uao satisfies [2(woo)| McMs-
Proof. We show the result by induction. The base case is given by the set Ug. which is clearly minimal since it only contains the initial state ug. For E [0. H]] assume that the algorithm has learned minimal RDP for sets .o.... Let 11++1 be the set of states at layer t + 1 of minimal RDP. Due to the regular property, each pair of histories that map to a state Me+1 E Ue+1 generate the same probability distribution over suffixes. Under events ÊCMS and Ex, Lemma 11 implies that DISTIIITTTTMMS Z(uao), (v' aa'a'''' o'')), ()),)) returns false for each pair of candidate states wao and a'a'o' that map 14+1- Consequently, ADACT-H merges uao and u'a'o'.
On the other hand, by assumption, each pair of histories that map to different states of U(+1 have Loe -distinuuisaabiiity μo- Under events ECMS and Ex, if minn)Z((uo)), 2 (x'''o')) 2 McMs then Lemma 12 implies that T'ESTDiSTINCTCaTT s(t 2 (uuo), 2( Z(u'a'o'), of candidate states uno and w'a'o' that map to different states in Me+11 Consequently, ADACT-H does not merge uno and u' n'a'o'. o'_ It follows that ADACT-H will generate exactly the set U6+1, which that of minimal RDP.
returns true for each pair
To prove Theorem 2 we need to ensure that M 2 McMs s for each candidate state uao. Choosing b 64 ())(A /ng and applying Lemma yields the following bound on the sample complexity:
1og(4/8) (128 log( (AOR)H + +3116)}
dd,,,, ao) (128 2
N
max Ma0
The three events &CMs, Ex and E hold simultaneously with probability least 1- 2H++)UUAAS >
1 2H AOS, so defining dn = 5/2HU AO ensures that the sample complexity holds with probabil- ity least 1 do. Since di (u, ao) 2 di (u, ao) 2 dín d we can bound the sample complexity as
N2 O+ log(SHU
128 log(
log(AR)) (AOR) + 3336 +31/)== = -0(HCn log(1/0) di 1/
(HHC)log(1/0)
di
1
This concludes the proof of the theorem.
We also prove a bound on the sample complexity of the approximation algorithm ADACT-H-A. In this algorithm, the subroutine TESTDISTINCTEWS is only called for a candidate state uao when p( uno) satisfies
38
p(uao) 10U AOC 1/,
20

---

Published as a conference paper at ICLR 2025
where E, U and C are inputs to the algorithm and v is predefined threshold. We prove the following theorem:
Theorem 14. ADACT-H-A(D. 6,
returns 5aapproximate RDP R' with probability at least 1 AHAOU6 when CMS is used to store empirical probability estimates, the statistical test is
S,U.C) C,,,U,C
L (21, 22) 2 /8log(4(ARO)*==100) 1ta0://mmmmn((((1) 21) (2)))
and the size of the dataset D is at least
HU HTUAOCloge log
D Ō
We first prove that the resulting RDP is 5-approximate.
Lemma 15. Under events EcMs, Ex and EB, U and C are upper bounds on the number of RDP states U [U') and concentrability Ciu, then ADACT-H-A returns an 5-approximate RDP R'.
Proof. Consider candidate state with M [Z(uo)]|. If ((uo)) 2 + then impose the condition M 2 McMs as before. For each such candidate state, ADACT-H-A calls TESTDIS- TINCTeMS and correctly promotes the candidate state RDP state merges it with an existing RDP state.
On the other hand, if ((p((uu) (ua))) and N 2 16log(4/8)/4) event &g and Lemma 8 yield
di (u,ao) f(uao) Gs(P(qao),
5
di (u, f(ua)) + Gs(P(uao), N) < 1 Gs(d, S
3
2T AOC
In this case, ADACT-H-A does call TESTDISTINCTEHR and hence the resulting RDP state may be incorrect. We can bound the contribution of uao to the value under the optimal policy x' as
d (u, 00)
x (T(T(, ao),
Σ
(T( r)
a'EA
PER
s (u,
Σ (T(,u_,,))
a')
(T(T(,, a'r)) dj (u, ao) I dR.d
<
6
AÚ
Y'EAA
PER
where have used the fact that the reward is bounded by 1. Summing up the contribution of all such candidate states to the expected optimal value of histories in Ho yields
Σ
Σ
de (ue, ao)
Σ T' (T(T(u, a') Σ (,(T(U, a', a'EA
Σ AE[o, Medo
Σ
AU
2
[E] 0000
PER
This proves that the resulting RDP is approximate.
To prove Theorem 14, for each candidate state uao such that p(uao) t. number of episodes
which satisfies N > 16 log(4/8)/vL is sufficient to ensure that R' is 5-approximate. If p(uo)) 2 v, we instead require M 2 McMs as before. Since McMs 2 16log(4/6). event &g together with Corollary yield
E AOC Applying Lemma 10 directly yields the following bound the sample complexity:
p(uao) - (u, ao) <
2p( uao)
di 2 p(uao)
3
3
log(4/8) du, ao)
128 (AOR))
16 16
max uno
+31 +31/6)
+
We can now use the lower bound db ao) in the case p(uao) eb achieve the following bound:
10 AOC log log(SHU A0/5o)
(128og(AARR)
1607 AOC Mog(8HUADD AO/5.)
+31/6)
E
4
35
HU log (1/8)
=
Eng
21

---

Published as a conference paper at ICLR 2025
C.5 PROOF OF THEOREM 3
Let TESTDISTINCT> be the version of TESTDISTINCT that uses the statistical test in the theorem. The proof of Theorem is achieved by proving lemmas analogous Lemmas 11 and 12.
Lemma 16. For t [0. H let 21 and Z2 be multisets sampled from distributions pı and p2 A(D#-'), and let id and p2 be empirical estimates of and due to 21 and 22, respectively. Under event Ex, if p p2 then TESTDISTINCT x 21, 22, answers false.
Proof. Due event Ex and the triangle inequality we have
Lx(Pi, (2)
Lx (P), + (x P2) (x2,2,
log 12)
(2(22
2 log (2 min 21), (2))
+ 0 +
2 Σ
2
This is precisely the condition for which TESTDISTINCT returns false.
Lemma 17. For t E [0. H1, let 21 and Z2 be multisets sampled from distributions p1 and pz on A(T"-*), and let pi and P2 be empirical estimates of and P2 due to Z1 and Zz, respectively. Under event Ex, if pı * P2 then TESTDISTINCTT Z1, 22,6) answers true if Z1 and 22 satisfy min( 21), 22l) 2 8 log(( 1
Proof. Due event Ex and the triangle inequality have
(x(p1,f2)) 2 Lx(p1, P2) - Txx (PI.P)))
(x2 P2)
log( ( x1/5)
IV
40
2
Z2l
log (2)
P4
2 log 2lo((2(X'/0))
IV
14
14
min
211.
4
min Z11. 22ll
where we have used the condition min( 12)) in the lemma. This is precisely the condition for which TESTDISTINCT. returns true.
The remainder of the proof of Theorem 3 is analogous to that of Theorem 2. To satisfy the conditions on | (wao) Lemma 17 and Corollary 9, we impose bound Mxx 16 (4/()4)) log / We can now choose = 16 log ////// in Lemma 10 to obtain a bound
log (4/)) de (u, ao)
32 log X
+ 31/6)
N max
Since TESTDISTINCT answers correctly under event Ex, Lemma 13 directly applies, with the only difference that we do not need event EcMs to hold, and hence is sufficient to choose 5y = 6/20 AO to ensure that events Ex and Eg hold. Using the lower bound on db,u, ao) yields
CR log( AO//6)))))
(32 log | + +31/6) = (CR log (lo((18))m) log [2]
N
d
d H
We also prove analogous theorem for the approximation algorithm ADACT-H-A:: Theorem 18. ADACT-H-A(D) 8, U,U, C, returns an --approximate RDP R' with probubility at least 1 2AOUS when using the language metric Lx to define a statistical test
Lx Zz) Z (2log(2,X1/6)/ min( Z1), Z2l),
and the size of the dataset D is at least
UAOC log(1/6) log {
[D] 2
Eng
22

---

Published as a conference paper at ICLR 2025
The proof is also analogous to that of Theorem 14. Concretely, Lemma 15 still holds long ensure M 2 Mx for candidate states such that P(uao) 2 v, and N 2 16 16 (log(4/0)) (4/6) / otherwise. Applying Lemma 10 directly yields the following bound the sample complexity:
log(4/6)
32 log |
16 16log(4/0)
N max wao
31/6)
dg (u, ao)
Mg
Using the lower bound on di (u, ao) in the case ((ua)) 2 v yields
N 10U AOC log((U (UU 60) 32 log X1
+ 1607 AOC AOClog(SU log(SUAA00))
+ 31 ///6//
8
Mü
3e
- U UAOC log (1 (166) log |X|
ENg
D DETAILS OF THE EXPERIMENTS
In this appendix we describe each domain in detail and include examples of RDPs learned by ADACT-H.
D.1 CORRIDOR
This RDP example was introduced by Ronca & De Giacomo (2021). The environment consists of a 2 x m grid, with only two actions ag and aj which moves the agent states (0, i + 1) and (1, + 1) respectively from state (-, The goal of the agent is to avoid an enemy which is present in position (0, i) with probability p.. and (1, with probability p The agent receives reward of +1 for avoiding the enemy at particular column, and the probabilities p and P are switched every time encounters the enemy. When the agent reaches the last column, its position reset to the first column. The observation space is given by (i.j,e) e). where i, is the cell position of the agent and e E (enemy, clear) denotes the presence of the guard in the current cell. Fig 3 shows the minimal automaton obtained by all three algorithms for H = 5.
1,5.1
al. 12.
0.3.1
a0, 0,4.0
1,4.1
0,5,
0,0,0.
11. 1.1.0
sC
al, 1,50
410
1,0.0.
J0, 0.1.1
0,3.0
97
ab, 0,4.1
a0, 0.5.1
all 32.0
1.3.1
Figure 3: Automaton obtained from the corridor environment. The edges are labelled as [action, observation, enemy).
D.2 T-MAZE(C)
The T-maze(c) environment was introduced by Bakker (2001) to capture long term dependencies with RL-LSTMs. As shown in Figure 1, at the initial position S, the agent receives an observation X, depending on the position of the goal state G in the last column. The agent can take four actions, North, South, East and West. The agent receives reward of +4 on taking the correct action the T-junction, and -1 otherwise, terminating the episode. The agent also receives a - reward for standing still. At the initial state the agent receives observation 011 or 110, 101 throughout the corridor and 010 the T-junction. Figure shows the optimal automaton obtained when the available actions the corridor are restricted to only East (the automaton obtained without this restriction shown in Figure 6). Table shows our results with the unrestricted action space using the language set Xa,1- Both our approaches find the optimal policy in this case, unlike FlexFringe which fails to capture this long term dependency.
Note that T-maze(c) differs from the T-maze Example in a small but relevant detail: in T-maze(c) the agent deterministically receives the observation 101 when it is in the corridor, but in the T-Maze
23

---

Published as a conference paper at ICLR 2025
E, 101
E, 101
E. 101
E. 101
110.
S, .10
011,
N. 010
E, 101
101
101
E, 101
q/o
S.
Figure 4: Automaton obtained from T-maze(c) environment with restricted actions. The edges labelled as [action, observation].
A
(a) Mini-hall environment (Littman et al., 1995).
(b) Simplified cookie domain.
Figure 5: Environments.
of Example the agent receive 101 or 111 uniformly random. The additional observation 111 is distraction for the agent, rather than a help, since it does not convey any additional useful information.
S. $,010
N. DED
W. JOI
W. 161
E, 101
415
E, 101
E, 101
WV 101
E. 101
IL 101
q10
W. 10J
W. 101
q12
E. 101
W,
@0
E. 101
W; 101
418
42
E, 101
q4
W. 101
W. 101
E. 101
E. 101
E. 101
N. D10
C, 101
ql1
q16
S.
W.
W;
q17
101
Figure 6: Automaton obtained from T-maze(c) (partially restricted action space), restricted language.
D.3 COOKIE DOMAIN
We modify the original cookie domain described in (Toro Icarte et al., 2019), to simpler domain consisting rooms, blue, white, green and red as shown Fig. 5b. the agent presses the button in room red, cookie appears in room blue green with equal probability. The agent can move left, right, up or down, can press the button in room red, and eat the cookie to receive reward 1, and then it may press the button again. There are 6 possible observations (4 for each room. and 2 for observing the cookie in the two rooms). We use the set X2,1 for distinguishability in the restricted language case. Our restricted language approach here finds the optimal policy and the smallest state space.
24

---

Published as a conference paper at ICLR 2025
D.4 CHEESE MAZE
Cheese maze (McCallum, 1992) consists of 10 states, and observations, and 4 actions. After reaching the goal state, the agent receives reward of +1, and the position of the agent reintialised the non-goal states with equal probability. For horizon of 6, the results for the restricted language (using the language set 1) and FlexFringe are comparable, however upon further increasing the horizon, FlexFringe outperforms ADACT-H by learning cyclic RDPs which is not possible in our approach.
of
D.5 MINI-HALL
The mini-hall environment (Littman et al., 1995) shown in Fig 5a has 12 states, 4 orientations in rooms, a goal state given by a star associated with reward of +1, observation and actions, and the position of the agent is reset after the goal is reached. This setting is much more complex than the others because 12 states are mapped into observations; for example, starting from observation 3, 3 actions are required under the optimal policy to solve the problem if the starting underlying state was in Room or C. We use the language set X and although we get a much larger state space, our algorithm gets closer to the optimal policy. However our CMS approach is not efficient this case and exceeds the alloted time budget of 1800 seconds, as it requires to iterate over all possible trajectories.
25


Reviews:
[{"review_id": "VJusLWSBpR", "reviewer": "Reviewer_K6iR", "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.", "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?\n- Can the proposed approach be applied to settings where the RDP structure is much larger, high dimensional, and even continuous? E.g. [1].\n\n[1] Allen, Cameron, et al. \"Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy.\" arXiv preprint arXiv:2407.07333 (2024).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n- 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.\n- 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. \n- 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.\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tHZwKUpxCH", "reviewer": "Reviewer_92xy", "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.", "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?\n2. Can the authors expand on any potential limitations of CMS in larger, more complex RDPs, especially concerning long planning horizons?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "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.\n2. 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).\n\n---\nHahn, 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).\n\nLenaers, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3DHQj9aj3L", "reviewer": "Reviewer_9Ta3", "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.", "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.\nThe 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.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0LjLcEizR4", "reviewer": "Reviewer_YHdK", "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.", "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.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "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. \nThe 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.\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)