Tractable Offline Learning of Regular Decision Processes
Ahana Deb Roberto Cipollone Anders Jonsson Alessandro Ronca Mohammad Sadegh Talebi



Power-grid modelling via gradual
      improvement of parameters
    I. Papp
    September 4, 2024
================================================================




§ 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 show that it is possible to overcome two strong limitations of previous offline RL algorithms for RDPs, notably RegORL <cit.>.
This can be accomplished via the introduction of two original techniques:
the development of a new pseudometric based on formal languages, which removes a problematic dependency on -distinguishability parameters, and the adoption of Count-Min-Sketch (CMS), instead of naive counting.
The former reduces the number of samples required in environments that are characterized by a low complexity in language-theoretic terms.
The latter alleviates the memory requirements for long planning horizons.
We derive the PAC sample complexity bounds associated to each of these techniques, and we validate the approach experimentally.





§ 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, the computation of (near-)optimal 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-Markovian Decision Processes (NMDPs).
In these very expressive models, the probability of future observations and rewards may depend on the entire history, which is the past interaction sequence composed of observations and actions.


The unrestricted dynamics of the NMDP formulation is not tractable for optimization.
Therefore, previous work in non-Markovian RL focus on tractable subclasses of decision processes.
In this work, we focus on Regular Decision Processes (RDPs) <cit.>.
In RDPs, the distribution of the next observation and reward is allowed to vary according to regular properties evaluated on the history.
Thus, these dependencies can be captured by a Deterministic Finite-state Automaton (DFA).
RDPs are expressive models that can represent complex dependencies, which may be based on events that occurred arbitrarily back in time.
For example, we could model that an agent may only enter a restricted area if it has previously asked for permission and the access was granted.


Due to the properties above, RL algorithms for RDPs are very general and applicable.
However, provably correct and sample efficient algorithms for RDPs are still missing.
On one hand, local optimization approaches are generally more efficient, but lack correctness guarantees.
In this group, we recall <cit.> and all RL algorithms with policy networks that can operate on sequences.
On the other hand, algorithms with formal guarantees do not provide a practical implementation <cit.> or can only be applied effectively in small environments <cit.>.


In this work, we propose a new offline RL algorithm for RDPs with a Probably Approximately Correct (PAC) sample complexity guarantee. 
Our algorithm improves over previous work in three ways.
First, we overcome a limitation of previous sample complexity bounds,
which is the dependence on a parameter called -distinguishability.
This is desirable because there exist simple non-Markovian domains in which this parameter decays exponentially with respect to the number of RDP states; an example is the T-maze by <cit.>, discussed below.
Second, a careful treatment of the individual features that compose the trace and each observation allows us to further improve the efficiency.
Third, inspired by the automaton-learning algorithm FlexFringe <cit.>, we use a data structure called Count-Min-Sketch (CMS) <cit.> to compactly represent probability distributions on large sets.



[T-maze] 
  As a running example, we consider the T-Maze domain <cit.>, a deterministic non-Markovian grid-world environment.
  An agent has to reach a goal G from an initial position S in a corridor of length N that terminates with a T-junction as shown in Figure <ref>.
  The agent can move one cell at a time, taking actions 𝑁𝑜𝑟𝑡ℎ, 𝑆𝑜𝑢𝑡ℎ, 𝐸𝑎𝑠𝑡, or 𝑊𝑒𝑠𝑡.
  In each episode, the rewarding goal G can be in the cell above or below the T-junction.
  Depending on the position of the goal, the observation in state S is 011 or 110.
  In the corridor the observation is 101, and at the T-junction the observation is 010.
  This means that, when crossing the corridor, the agent cannot observe the current location or the goal position.
  This yields a history-dependent dynamics that cannot be modeled with an MDP or any k-order MDP.
  As we show later, this domain can be expressed as an RDP.
  
  
  




  
Contributions
We study offline RL for Regular Decision Processes (RDPs) and address limitations of previous algorithms.
To do so, we develop a novel language metric L_, based on the theory of formal languages, and define a hierarchy of language families that allows for a fine-grained characterization of the RDP complexity.
Unlike previous algorithms, the RL algorithm we develop based on this language hierarchy does not depend on -distinguishability and is exponentially more sample efficient in domains having low complexity in language-theoretic terms.
In addition, we reduce the space complexity of the algorithm and modify RegORL with the use of Count-Min-Sketch.
To validate our claims, we provide a theoretical analysis for both variants, when the L_-distinguishability or CMS is used.
Finally, we provide an experimental analysis of both approaches.




 §.§ Related work




  
RL in RDPs
The first online RL algorithm for RDPs is provided in <cit.>.

Later, <cit.> and <cit.> developed the first online RL algorithms with sample complexity guarantees.
The algorithm and the sample complexity bound provided in <cit.> adapts analogous results from automata learning literature <cit.>.
RegORL from <cit.> is an RL algorithm for RDPs with sample complexity guarantees for the offline setting.
In this work, we study the same setting and improve on two significant weaknesses of RegORL, regarding the sample compexity and the space requirements.
The details of these improvements are discussed in the following sections.
Lastly, the online RL algorithm in <cit.> can also be applied to RDPs,
but it is not proven to be sample efficient.



  
Non-Markovian RL
Apart from RDP algorithms, one can apply RL methods to more general decision processes.
Indeed, the automaton state of an RDP can be seen as an information state, as defined in <cit.>.
As shown in <cit.>,
any RDP can also be expressed as a POMDP whose hidden dynamics evolves according to its finite-state automaton.
Therefore, any RL algorithm for generic POMDPs can also be applied to RDPs.
Unfortunately, planning and learning in POMDPs is intractable <cit.>.
More efficient learning algorithms, with more favorable complexity bounds, have been obtained for subclasses of POMDPs, such as undercomplete POMDPs <cit.>,
few-step reachability <cit.>,
ergodicity <cit.>,
few-step decodability <cit.>,
or weakly-revealing <cit.>.
However, none of these assumptions exhaustively capture the entire RDP class, and they cannot be applied in general RDPs.

Regarding more general non-Markovian dynamics,
Predictive State Representations (PSRs) <cit.> are general descriptions of dynamical systems that capture POMDPs and therefore RDPs.
There exist polynomial PAC bounds for online RL in PSRs <cit.>.
However, these bounds involve parameters that are specific to PSRs and do not immediately apply to RDPs.

Feature MDPs and state representations both share the idea of having a map from histories to a state space.
This is analogous to the map determined by the transition function of the automaton underlying an RDP.
Algorithmic solutions for feature MDPs are based on suffix trees, and they cannot yield optimal performance in our setting <cit.>.
The automaton of an RDP can be seen as providing one kind of state representation <cit.>.
The existing bounds for state representations show a linear dependency on the number of candidate representations, which is exponential in the number of states in our case.
A similar dependency is also observed in <cit.>.
With respect to temporal dependencies for rewards, Reward Machines consider RL with non-Markovian rewards
<cit.>.
However, this dependency is usually assumed to be known, which makes the Markovian state computable.
Lastly, non-Markovianity is also introduced by the logical specifications that the agent is
required to satisfy
<cit.>;
however, it is resolved a priori from the known specification.



  
Offline RL in MDPs.
There is a rich and growing literature on offline RL, and provably sample efficient algorithms have been proposed for various settings of MDPs <cit.>. For example, in the case of episodic MDPs, it is established that the optimal sample size in offline RL 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. 
A closely related problem is off-policy learning <cit.>. 





§ PRELIMINARIES




  
Notation
Given a set Y, Y denotes the set of probability distributions over Y. 
For a function f: X→Y,
f(y  x) is the probability of y∈Y given x∈X. 
Further, we write y ∼ f(x) to abbreviate y ∼ f(· x). 

Given an event E,  (E) denotes the indicator function of E, which equals 1 if E is true, and 0 otherwise. 
For any pair of integers m and n such that 0≤ m≤ n, we let [m,n]:={m,…,n} and [n]:={1, …, n}.

The notation 𝒪(·) hides poly-logarithmic terms. 



  
Count-Min-Sketch
Count-Min-Sketch, or CMS <cit.>, is a data structure that compactly represents a large non-negative vector v=[v_1,…,v_m].
CMS takes two parameters δ_c and ε as input, and constructs a matrix C with d=⌈log1/δ_c⌉ rows and w=⌈e/ε⌉ columns.
For each row j∈[d], CMS picks a hash function h_j:[m]→[w] uniformly at random from a pairwise independent family <cit.>.
Initially, all elements of v and C equal 0.
An update (i,c) consists in incrementing the element v_i by c>0.
CMS approximates an update (i,c) by incrementing C(j,h_j(i)) by c for each j∈[d].
At any moment, a point query v_i returns an estimate of v_i by taking the minimum of the row estimates, i.e. v_i = min_j C(j,h_j(i)).
It is easy to see that v_i≥ v_i, i.e. CMS never underestimates v_i.



 §.§ Languages and operators
 
An alphabet  is a finite non-empty set of elements called letters.
A string over  is a concatenation a_1 ⋯ a_ℓ of letters from , and we call ℓ its length.
In particular, the string containing no letters, having length zero, is a valid string called the empty string, and is denoted by .
Given two strings x_1 = a_1 ⋯ a_ℓ and x_2 = b_1 ⋯ b_m, their concatenation x_1x_2 is the string a_1 ⋯ a_ℓ b_1 ⋯ b_m. In particular,
for any given string x, we have x  =  x = x.
The set of all strings over alphabet  is written as ^*, and the set of all strings of length ℓ is written as ^ℓ. 
Thus, ^* = ∪_ℓ∈^ℓ.
A language is a subset of ^*.
Given two languages _1 and _2, their concatenation is the language defined by 
_1 _2 = { x_1 x_2 | x_1 ∈_1 ,  x_2 ∈_2 }. 
When concatenating with a language { a } containing a single string consisting of a letter a ∈, we simply write a instead of { a }.
Concatenation is associative and hence we can write the concatenation _1 _2 ⋯_k of an arbitrary number of languages.










Given the fundamental definitions above, we introduce two operators to construct sets of languages.
The first operator C_k^ℓ is defined for any two non-negative integers ℓ and k ∈{1,…,ℓ}, it takes  a set of languages 𝒢, and constructs a new set of languages as follows:

    C_k^ℓ(𝒢) = 
    {^ℓ∩ S_1 G_1 S_2 G_2 ⋯ S_k G_k S_k+1| G_1, …, G_k ∈𝒢,   S_1, …, S_k+1∈𝒮},

where the set 𝒮 = {^*, {}} consists of the language ^* of all strings over the considered alphabet and the singleton language {} consisting of the empty string only.
In the definition, each S_i can be Γ^* or .
Choosing S_i = Γ^* allows arbitrary letters between a string from G_i and the next string from G_i+1, whereas choosing S_i = {} enforces that a string from G_i is immediately followed by a string from G_i+1.

Also, the intersection with Γ^ℓ amounts to restricting to strings of length ℓ in the languages given by the concatenation.

The second operator we define, , takes a set of languages , and it constructs a new set of languages () = ^⊔∪^⊓ by taking combinations as follows:

    ^⊔  = {_1 ∪_2 |_1,_2 ∈},
              ^⊓  = {_1 ∩_2 |_1, _2 ∈}.

The set ^⊔ consists of the pair-wise unions of the languages in .
For example, when = {{ ac, ad }, {ac,bc}}, we have ^⊔ = ∪{{ ac, ad, bc }}. 
Similarly, the set ^⊓ consists of the pair-wise intersections of the languages in .
For example, when = {{ ac, ad }, {ac,bc}}, we have ^⊓ = ∪{{ ac }}. 
From the previous example we can observe that ⊆^⊔, ^⊓, which holds in general since 
= {∩| X ∈}⊆^⊓ and similarly = {∪| X ∈}⊆^⊔
Therefore ⊆().

The operators will later be used to define relevant patterns on episode traces.
They are inspired by classes of languages in the first level of the dot-depth hierarchy, a well-known hierarchy of star-free regular languages <cit.>.










 §.§ Episodic regular decision processes

We first introduce generic episodic decision processes. 
An episodic decision process is a tuple =,,,T,R,H, where  is a finite set of observations,  is a finite set of actions, ⊂[0,1] is a finite set of rewards, and H≥ 1 is a finite horizon.
We frequently consider the concatenation  of the sets  and .

Let _t=()^t+1 be the set of histories of length t+1, and let e_m:n∈_n-m denote a history from time m to time n, both included.
Each action-observation pair ao∈ in a history has an associated reward label r∈, which we write ao/r∈/.
A trajectory e_0:T is the full history generated until (and including) time T.


We assume that a trajectory e_0:T can be partitioned into episodes e_ℓ:ℓ+H∈_H of length H+1,



In each episode e_0:H, a_0=a_ is a dummy action used to initialize the distribution on _0.
The transition function T:×→ and the reward function R:×→ depend on the current history in =∪_t=0^H_t.
Given , a generic policy is a function :()^*→ that maps trajectories to distributions over actions.
The value function V^:[0,H]×→ of a policy  is a mapping that assigns real values to histories.
For h∈, it is defined as V^(H, h) 0 and

    V^(t, h) [ ∑_i=t+1^H r_i  |  h, ],   ∀ t<H, ∀ h∈_t.

For brevity, we write V^π_t(h):=V^π(t,h).
The optimal value function V^* is defined as V^*_t(h) sup_π V^π_t(h), ∀ t∈ [H], ∀ h∈_t,  
where sup is taken over all policies :()^*→. Any policy achieving  V^* is called optimal, which we denote by π^*; namely V^π^*=V^*. 
Solving  amounts to finding ^*.
In what follows, we consider simpler policies of the form :→ mapping finite histories to distributions over actions.
Let Π_ denote the set of such policies.
It can be shown that Π_ always contains an optimal policy, i.e. V^*_t(h) max_π∈Π_ V^π_t(h), ∀ t∈ [H], ∀ h∈_t. An episodic MDP is an episodic decision process whose dynamics at each timestep t only depends on the last observation and action <cit.>.



  
Episodic RDPs
An episodic Regular Decision Process (RDP) <cit.> is an episodic decision process =,,,T,R,H described by a finite transducer (Moore machine)  , , , , , q_0, where  is a finite set of states, = is a finite input alphabet composed of actions and observations,  is a finite output alphabet, : ×→ is a transition function, : → is an output function, and q_0∈ is a fixed initial state <cit.>. 
The output space = _𝗈×_𝗋 consists of a finite set of functions that compute the conditional probabilities of observations and rewards, on the form _𝗈⊂→ and _𝗋⊂→.
For simplicity, we use two output functions, : ×→ and : ×→, to denote the individual conditional probabilities.
Let ^-1 denote the inverse of , i.e. ^-1(q)⊆× is the subset of state-symbol pairs that map to q∈.

An RDP  implicitly represents a function : → from histories in  to states in , recursively defined as
(h_0) (q_0, a_0 o_0), where a_0 is some fixed starting action, and (h_t) ((h_t-1), a_t o_t).
The dynamics and of  are defined as T(o  h,a)=(o (h),a) and R(r  h,a)=(r (h),a), ∀ h∈, ∀ ao/r∈/.
As in previous work <cit.>, we assume that any episodic RDP generates a designated termination observation ∈ after exactly H transitions.
This ensures that any episodic RDP is acyclic, i.e. the states can be partitioned as =_0∪⋯∪_H+1, where each _t+1 is the set of states generated by the histories in _t for each t∈[0,H].
An RDP is minimal if its Moore machine is minimal.
We use A, R, O, Q to denote the cardinality of , , ,, respectively, and assume A≥ 2 and O≥ 2.

Since the conditional probabilities of observations and rewards are fully determined by the current state-action pair (q,a), an RDP  adheres to the Markov property over its states, but not over the observations.
Given a state q_t ∈ and an action a_t ∈,
the probability of the next transition is

    (r_t, o_t, q_t+1 q_t, a_t, ) =
    		(r_t  q_t, a_t) (o_t  q_t, a_t) (q_t+1=(q_t,a_t o_t)).

Since RDPs are Markovian in the unobservable states , there is an important class of policies that is called regular.
Given an RDP , a policy :→ is called regular if (h_1)=(h_2) whenever (h_1)=(h_2), for all h_1,h_2∈.
Hence, we can compactly define a regular policy as a function of the RDP state, i.e. π:→.
Let Π_ denote the set of regular policies for .
Regular policies exhibit powerful properties. First, under a 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.

[RDP for T-maze]
  Consider the T-maze described in Example <ref>.
  This can be modeled as an episodic RDP 
  , , , , , q_0
  with states q_0 ∪ ({ q_⊤ 1, …, q_⊤ 13}∪{ q_ 1, …, q_ 13}) ×{1, …, H}, which include the initial state q_0 and two parallel components, ⊤ and , for the 13 cells of the grid world.
  In addition, each state also includes a counter for the time step.
  Within each component {(q_⊤ i, t)}_i and {(q_ i, t)}, the transition function  mimics the grid world dynamics of the maze and increments the counter t.
  From the initial state and the start action a_0, (q_0, a_0 o_0) equals q_1,⊤ if o_0 = 110, and q_1, if o_0 = 011.
  Observations are deterministic as described in Example <ref>,
  except for (q_0, a_0) = {110,011}.
  The rewards are null, except for a 1 in the top right or bottom right cell, depending if the current state is in the component ⊤ or , respectively.





  
Occupancy and distinguishability
Given a regular policy :→ and a time step t∈[0,H], let _t^∈_t× be the induced occupancy, i.e. a probability distribution over the states in _t and the input symbols in , recursively defined as _0^(q_0,a_0o_0) = (o_0  q_0, a_0) and 

    _t^(q_t,a_to_t)    = ∑_(q,ao)∈^-1(q_t)_t-1^(q,ao) ·(a_t  q_t) ·(o_t  q_t, a_t),    t>0.

Of particular interest is the occupancy distribution _t^* _t^^* associated with an optimal policy ^*. Let us assume that ^* is unique, which further implies that d^*_t is uniquely defined[This assumption is imposed to ease the definition of the concentrability coefficient that follows, and is also considered in the offline  reinforcement learning literature (e.g., <cit.>). In the general case, one may consider the set D^* of occupancy distributions, collecting occupancy distributions of all optimal policies.].

Consider a minimal RDP  with states = ∪_t ∈ [0,H+1]_t.
Given a regular policy ∈Π_ and a time step t∈[0,H], each RDP state q ∈_t defines a unique probability distribution (· q_t = q, ) on episode suffixes in _H-t=( /  )^H-t+1.
The states in _t can be compared in terms of the probability distributions they induce over _H-t.
Consider any L = {L_ℓ}_ℓ = 0^H, where each L_ℓ is a metric over _ℓ.
We define the L-distinguishability of  and  as the maximum ≥ 0 such that,
for any t ∈ [0,H] and any two distinct q, q' ∈_t, the probability distributions over suffix traces e_t:H∈_ℓ from the two states satisfy

    L_H-t((e_t:H q_t = q, ), (e_t:H q_t = q', )) ≥  .

We will often omit the remaining episode length ℓ = H-t from L_ℓ and simply write L. 

We consider the -distinguishability, instantiating the definition above with  
the metric (p_1, p_2) = max_u ∈ [0,ℓ], e ∈_up_1(e  *) - p_2(e  *),
where p_i(e *) represents the probability of the trace prefix e∈_u, followed by any trace e' ∈_ℓ-u-1. The -distinguishability is defined analogously using (p_1, p_2) = ∑_u ∈ [0,ℓ], e ∈_up_1(e  *) - p_2(e  *).



§ LEARNING RDPS WITH STATE-MERGING ALGORITHMS FROM OFFLINE DATA


Here we describe an algorithm called AdaCT-H <cit.> for learning episodic RDPs from a dataset of episodes.
The algorithm starts with a set  of episodes generated using a regular behavior policy , where the k-th episode is of the form 
e_0:H^k=a_0^ko_0^k/r_0^k⋯ a_H^ko_H^k/r_H^k and where, for each t∈[0,H],

    q_0^k = q_0,    a_t^k∼(q_t^k),    o_t^k∼(q_t^k,a_t^k),    r_t^k∼(q_t^k,a_t^k),    q_t+1^k = (q_t^k,a_t^ko_t^k).

Note that the behavior policy  and underlying RDP states q_t^k are unknown to the learner.
The algorithm is an instance of the PAC learning framework and takes as input an accuracy ε∈ (0,H] and a failure probability δ∈(0,1).
The aim is to find an ε-optimal policy  satisfying V_0^*(h) - V_0^(h)≤ε for each h∈_0 with probability at least 1-δ, using the smallest dataset  possible.

Since AdaCT-H performs offline learning, it is necessary to control the mismatch in occupancy between the behavior policy  and the optimal policy ^*. 
Concretely, the single-policy RDP concentrability coefficient associated with RDP  and behavior policy  is defined as <cit.>:
	
    C_^* = max_t ∈ [H], q ∈_t, ao ∈_t^*(q, ao)/_t(q, ao)  .

As <cit.>, we also assume that the concentrability is bounded away from infinity, i.e. that C_^*<∞.

AdaCT-H is a state-merging algorithm that iteratively constructs the set of RDP states _1,…,_H and the associated transition function .
For each t∈[0,H], AdaCT-H maintains a set of candidate states qao∈_t-1×.
Each candidate state qao has an associated multiset of suffixes (qao)={e_t:H^k : e^k∈, (e_0:t-1^k)=q, a_t-1^ko_t-1^k=ao}, i.e. episode suffixes whose history is consistent with qao.
To determine whether or not the candidate qao should be promoted to _t or merged with an existing RDP state q_t, 
AdaCT-H compares the empirical probability distributions on suffixes using the prefix distance  defined earlier.
For reference, we include the pseudocode of AdaCT-H(,δ) in Appendix <ref>.
<cit.> prove that AdaCT-H(,δ) constructs a minimal RDP  with probability at least 1-4AOQδ.

In practice, the main bottleneck of AdaCT-H is the statistical test on the last line,

    (_1,_2)≥√(2log(8(ARO)^H-t/δ)/min(|_1|,|_2|)),

since the number of episode suffixes in _ℓ is exponential in the current horizon ℓ.
The purpose of the present paper is to 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 <cit.>.



§ TRACTABLE OFFLINE LEARNING OF RDPS



The lower bound derived in <cit.> shows that sample complexity of learning RDPs is inversely proportional to the -distinguishability.
When testing candidate states of the unknown RDP,  is the metric that allows maximum separation between distinct distributions over traces.
Unfortunately, accurate estimates of  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  are much more practical to obtain.
However, there are instances for which states can be well separated in the -norm, but have an -distance that is exponentially small.
To address these issues, in this section we develop two improvements over the previous learning algorithms for RDPs.



 §.§ Testing in structured languages




  
The language of traces
Under a regular policy, any RDP state _t uniquely determines a distribution over the remaining trace a_t o_t / r_t … a_H o_H / r_H ∈ ( / )^H-t+1.
Existing work <cit.> treats each element a_i o_i / r_i as an independent atomic symbol.
This approach neglects the internal structure of each tuple and of the observations, which are often composed of features.
As a result, common conditions such as the presence of a reward become unpractical to express.

In this work, we allow observations to be composed of internal features.
Let = 1×…×m be an observation space.
We choose to see it as the language 
= 1⋯m given by the concatenation of the features.
Then, instead of representing an observation (o1, …, om) as an atomic symbol, we consider it as the word 
o1 o2⋯ om.
This results into traces _i = (1⋯m/)^i+1,

and each regular policy and RDP state uniquely determine a distribution over strings from _H-t+1.
This fine-grained representation greatly simplifies the representation of most common conditions,
such as the presence of specific rewards or features in the observation vector.




  
Testing in the language metric

The metrics induced by the L_1 and L_∞ norms are completely generic and can be applied to any distribution.
Although this is generally an advantage, this means that they do not exploit the internal structure of the sample space.
In our application, a sample is a trace that, as discussed above, can be regarded as a string of a specific language.
An important improvement, proposed by <cit.>, is to consider  and , 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 norms are strongly different and lead to dramatically different sample and space complexities.

In this section, we define a new formalism that unifies both metrics and will allow the development 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.

    Let ℓ∈ℕ, let  be an alphabet, and let  be a set of languages consisting of strings in ^ℓ.
    The language metric in 
    is the function L_: ^ℓ×^ℓ→, on 
    pairs of probability distributions p,p' over Γ^ℓ, defined as 
    
    L_(p, p') max_∈p() - p'(),

    where the probability of a language is p() ∑_x ∈ p(x).


This original notion unifies all the most common metrics. Considering distributions over Γ^ℓ, 
when = {{x}| x ∈^ℓ},
the language metric L_ reduces to L_∞.
When = 2^^ℓ, which is the set of all languages in ^ℓ,
the language metric becomes the total variation distance, which is half the value of L_1.
A similar reduction can be made for the prefix distances.
The language metric captures  when = {x ^ℓ-t| t ∈ [0,ℓ], x ∈^t }, and it
captures  when = ∪_t ∈ [0,ℓ] 2^^t.





  
Testing in language classes

The language metric can be applied directly to the language of traces and used for testing in RDP learning algorithms.
In particular, it suffices to consider any set of languages  that satisfy ⊆_H-h = (1⋯m/)^H-t+1⊆^H-t+1, for each ∈.
However, as we have seen above, the selection of a specific set of languages  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 .
Intuitively, we seek to evaluate the distance between candidate states based on increasingly complex sets of languages. We present a way to construct a hierarchy of sets of languages of increasing complexity. As a first step, we define sets  of basic patterns 𝒢_i of increasing complexity. 

    𝒢_1 =     { a / | a ∈}∪{ / r | r ∈}∪{1⋯ oi⋯m / | i ∈ [m] ,  oi∈i},
        
    𝒢_i =     𝒢_i-1∪(𝒢_i-1),   ∀ i ∈ [2,m+2].

In particular, 𝒢_1 focuses on single components, by matching an action a, a reward r, or a single observation feature oi. At the opposite side of the spectrum, the set 𝒢_m+2 considers every possible combination of actions, observation, reward; namely, it includes the set of singleton languages
{{ ao1⋯ om/r }| ao1⋯ om/r ∈1⋯m/},
which is the most fine-grained choice of patterns, but it grows exponentially with m. On the contrary, the cardinality of 𝒢_1 is linear in m. 
Starting from the above hiearchy, we identify two more dimensions along which complexity can grow. One dimension results from concatenating the basic patterns from 𝒢_i, and it is obtained by applying the operator C_k^ℓ. The other dimension results from Boolean combinations of languages, and it is obtained by applying the operator . 

Thus, letting ℓ = H-t+1, 
we define the following three-dimensional hierarchy of sets _i,j,k of languages:

    _i,j,1    = _i,j-1,1∪C_j^ℓ(𝒢_i),       ∀ i ∈ [1,m+2], ∀ j ∈ [ℓ],
        
    _i,j,k    = _i,j,k-1∪(_i,j,k-1),       ∀ i ∈ [1,m+2], ∀ j ∈ [ℓ],  ∀ k ∈ [2,ℓ].

The family _i,j,k induces a family of language metrics L__i,j,k, which are non-decreasing along the dimensions of the hiearchy:

    L__i,j,k≤ L__i+1,j,k, L__i,j+1,k, L__i,j,k+1,   ∀ i ∈ [1,m+2], ∀ j ∈ [ℓ],  ∀ k ∈ [ℓ],

and it may actually be increasing since we include more and more languages as we move towards higher levels of the hierarchy.
Moreover, the last levels _m+2,ℓ,k satisfy 
L__m+2,ℓ,k≥ for every k ∈ [ℓ]
since {x ^ℓ-t| t ∈ [0,ℓ],  x ∈^t }⊆_m+2,ℓ,k. Therefore, the metric L__m+2,ℓ,k is at least as effective as  in distinguishing candidate states. It can be much more effective as shown next.













[Language metric in T-maze]
  We now discuss the importance of our language metric for distinguishability,
  with respect to the T-maze described in Example <ref> and the associated RDP in Example <ref>.
  Consider the two states (q_⊤ 6, 6) and (q_ 6, 6) in the middle of the corridor and assume that the behavior policy is uniform.
  In these two states, the probability of each future sequence of actions, observations, and rewards is identical, except for the sequences that reach S or the top/bottom cells.
  These differ in the starting observation or the reward, respectively.
  Thus, the maximizer in the definition of -distinguishability is the length u=6 and any string x that contains the initial observation.
  Since the behavior policy is a random walk, the probability of x is 0.5^6 from one state, and 0 from the other, depending on the observation.
  Therefore, -distinguishability decreases exponentially with the length of the corridor.
  Consider instead the language _1,1,1 and its associated L__1,1,1.
  This set of languages includes ^* “110" ^* ∩^ℓ, which represents the language of any episode suffix containing the observation 110.
  Since it does not depend on specific paths, its probability is 0 for (q_ 6, 6) and it equals the probability of visiting the leftmost cell for (q_⊤ 6, 6).
  For sufficiently long episodes, this probability approaches 1.
  Thus, in some domains, the language metric improves exponentially over .



    The behavior policy  has an L__i,j,k-distinguishability of at least > 0,
    where _i,j,k is constructed as above and is an input to the algorithm.


Given i∈[0,H], let p, p' ∈_i be two distributions over traces.
To have accurate estimates for the language metric over some _i,j,k,
we instantiate two estimators, p and p', respectively built using datasets of episodes C and C', defined as the fraction of samples that belong to the language; 
that is, p∑_e ∈C(e ∈_i,j,k) / |C|
and p' ∑_e ∈C'(e ∈_i,j,k) / |C'|.



 §.§ Analysis


In this section, we show how to derive high-probability sample complexity bounds for AdaCT-H when Count-Min-Sketch (CMS) or the language metric L_ is used.
Intuitively, it is sufficient to show that the statistical test is correct with high probability; the remaining proof is identical to that of <cit.>.



AdaCT-H(,δ) returns a minimal RDP  with probability at least 1-4AOQδ when CMS is used to store the empirical probability distributions of episode suffixes, the statistical test is

    (_1,_2)≥√(8log(16(ARO)^H-t/δ)/min(|_1|,|_2|)),

and the size of the dataset is at least ||≥𝒪(√(H)/ d_minμ_0), where d_min = min_t,q,ao d_t(q,ao).

The proof of Theorem <ref> appears in Appendix <ref>.



AdaCT-H(,δ) returns a minimal RDP  with probability at least 1-4AOQδ when the statistical test is implemented using the language metric L_ and equals

    L_(_1,_2)≥√(2log(4||/δ)/min(|_1|,|_2|)),

and the size of the dataset is at least ||≥𝒪(1/ d_minμ_0).

The proof of Theorem <ref> also appears in Appendix <ref>.
Note that by definition, μ_0 is the L-distinguishability of  for the chosen language set , which has to satisfy μ_0>0 for AdaCT-H to successfully learn a minimal RDP.
Even though our sample complexity results are similar to those of previous work up to a factor √(H), as discussed earlier, μ_0 may be exponentially smaller for L_ than for .
We remark that the analysis does not hold if CMS is used to store the empirical probability distribution of the language metric L_, since the languages in a set  may overlap, causing the probabilities to sum to a value significantly greater than 1.



§ EXPERIMENTAL RESULTS


In this section we present the results of experiments with two versions of AdaCT-H: one that uses CMS to compactly store probability distributions on suffixes, and one that uses the restricted language family _1,1,1.
We compare against FlexFringe <cit.>, a state-of-the-art algorithm for learning probabilistic deterministic finite automata, which includes RDPs as a special case.
To approximate episodic traces, we add a termination symbol to the end of each trace, but FlexFringe sometimes learns RDPs with cycles.
Moreover, FlexFringe uses a number of different heuristics that optimize performance, but these heuristics no longer preserve the high-probability guarantees.
Hence the automata output by FlexFringe are not always directly comparable to the RDPs output by AdaCT-H.

We perform experiments in five domains from the literature on POMDPs and RDPs: Corridor <cit.>, T-maze <cit.>, Cookie <cit.>, Cheese <cit.> and Mini-hall <cit.>.
Appendix <ref> contains a detailed description of each domain, as well as example automata learned by the different algorithms.
Table <ref> summarizes the results of the three algorithms in the five domains.
We see that AdaCT-H with CMS is significantly slower than FlexFringe, which makes sense since FlexFringe has been optimized for performance.
CMS compactly represents the probability distributions over suffixes, but AdaCT-H still has to iterate over all suffixes, which is exponential in H for the  distance.
As a result, CMS suffers from slow running times, and exceeds the alloted time budget of 1800 seconds in the Mini-hall domain.

On the other hand, AdaCT-H with the restricted language family _1,1,1 is faster than FlexFringe in all domains except T-maze, and outputs smaller automata than both FlexFringe and CMS in all domains except Mini-hall.
The number of languages of _1,1,1 is linear in the number of actions, observation symbols, and reward values, so the algorithm does not have to iterate over all suffixes, and the resulting RDPs better exploit the underlying structure of the domains.
In Corridor and Cookie, all algorithms learn automata that admit an optimal policy.
However, in T-maze, Cheese and Mini-hall, the RDPs learned by AdaCT-H with the restricted language family  _1,1,1 admit a policy that outperforms those of FlexFringe and CMS.
As mentioned, the heuristics used by FlexFringe are not optimized to preserve reward, which is likely the reason why the derived policies perform worse.





§ CONCLUSION

In this paper, we propose two new approaches to offline RL for Regular Decision Processes and provide their respective theoretical analysis. We also improve upon existing algorithms for RDP learning, and propose a modified algorithm using Count-Min-Sketch with reduced memory complexity. We define a hierarchy of language families and introduce a language-restricted approach, removing the dependency on -distinguishability parameters and compare the performance of our algorithms to FlexFringe, a state-of-the-art algorithm for learning probabilistic deterministic finite automata. Although CMS suffers from a large running time, the language-restricted approach offers smaller automata and optimal (or near optimal) policies, even on domains requiring long-term dependencies. Finally, as a future work, we plan to expand our approach to the online RDP learning setting. 

abbrvnat








§ PSEUDOCODE OF ADACT-H




functionfunction
	myalg
  	AdaCT–H
	
	
	Dataset  containing N traces in _H, failure probability 0<δ<1
	Set  of RDP states, transition function :× →
	
	_0 {q_0}, (q_0) *initial state
	t = 0, …, H
		_𝖼,t+1{qao  q∈_t, ao∈ } *get candidate states
		qao∈_𝖼,t+1(qao) {e_t+1:H aroe_t+1:H∈(q)}  *[h]compute suffixes
		q_𝗆a_𝗆o_𝗆max_qao∈_𝖼,t+1 |(qao)| *most common candidate
		_t+1{q_𝗆a_𝗆o_𝗆}, (q_𝗆,a_𝗆o_𝗆)=q_𝗆a_𝗆o_𝗆 *promote candidate
		_𝖼,t+1_𝖼,t+1∖{q_𝗆a_𝗆o_𝗆} *remove from candidate states
		qao∈_𝖼,t+1
			{q'∈_t+1 not TestDistinct(t, (qao), (q'), δ)}  *[h]confidence test
			
			= ∅
				_t+1_t+1∪{qao},
				(q,ao)=qao  *[h]promote candidate
			
   
			
				q' element in ,
				(q,ao)=q',
				(q') (q') ∪(qao)  *[h]merge states
			
		
	
	_0∪⋯∪_H+1, 
	
	
	TestDistinct 
	
	Time t, two multisets _1 and _2 of traces in (×)^H-t+1, failure probability 0<δ<1
	True if _1 and _2 are regarded as distinct, False otherwise
	
	(_1,_2)≥√(2log(8(ARO)^H-t/δ)/min(|_1|,|_2|))
	





§ PSEUDOMETRICS



We provide the definition of pseudometric spaces.


    Given a set 𝒦 and a non-negative function d: ×→, we call (, d) a pseudometric space with pseudometric d, if for all x, y, z ∈:
    
        
  (i) d(x, x) = 0,
        
  (ii) d(x, y) = d(y, x),
        
  (iii) d(x, y) + d(y, z) ≥ d(x, z).
    


If it also holds that d(x, y) = 0 iff x = y, then d is a metric. 



§ PROOF OF THEOREMS



In this appendix we prove Theorems <ref> and <ref> using a series of lemmas. We first describe how to implement AdaCT-H using CMS.

Given a finite set  and a probability distribution q∈Δ(), let q∈Δ() be an empirical estimate of q computed using n samples.
CMS can store an estimate q of the empirical distribution q.
In this setting, the vector v contains the empirical counts of each element of , which implies v_1=n and q(z_i)=v_i/n for each z_i∈.
The following lemma shows how to bound the error between q and q.



Given a finite set , a probability distribution q∈Δ(), and an empirical estimate q∈Δ() of q obtained using n samples, let q be the estimate of q output by CMS with parameters δ_c and ε. With probability at least 1-||δ_c it holds that q-q_∞≤ϵ. 



<cit.> show that for a point query that returns an approximation v_i of v_i, with probability at least 1-δ_c it holds that

    v_i ≤ v_i + εv_1.

In our case, the estimated probability of an element z_i∈ equals q(z_i)=v_i/n, where v_i is the point query for z_i.
Using the result above, with probability at least 1-δ_c we have

    q(z_i) = v_i/n≤v_i/n + εv_1/n = q(z_i) + ε.

Since CMS never underestimates a value, q(z_i)≤q(z_i) trivially holds. Taking a union bound shows that the inequality above holds simultaneously for all z_i∈ with probability 1-||δ_c.


The following two lemmas are analogous to Lemmas 13 and 14 of <cit.>.


For t∈[0,H], let _1 and _2 be multisets sampled from distributions p_1 and p_2 on Δ(_H-t).
Assume that we use CMS with parameters δ_c=δ/8(AOR)^H-t and ε=√(log(2/δ_c) / 2|_i| ) to store an approximation p_i of the empirical estimate p_i of p_i due to _i, i∈[2].
If p_1=p_2, with probability at least 1-δ the statistical test satisfies

    (p_1, p_2) ≤√(8log(16(AOR)^H-t/δ)/min(|_1|,|_2|)).




Hoeffding's inequality states that for each i∈[2], with probability at least 1-δ_c it holds for each e∈_u, u≤ H-t, that

    p_i(e) - p_i(e) ≤√(log(2/δ_c)/2|_i|).

We can now use Lemma <ref> to upper bound the  metric as

    L_(p_1, p_2)    = max_u∈[0,H-t],e∈_up_1(e) - p_2(e)
       ≤max_u∈[0,H-t],e∈_u ( p_1(e) - p_1(e) + p_1(e) - p_1(e) + p_1(e) - p_2(e)
        + p_2(e) - p_2(e) + p_2(e) - p_2(e) )
       ≤√(log(2/δ_c)/2|_1|) + √(log(2/δ_c)/2|_1|) + √(log(2/δ_c)/2|_2|) + √(log(2/δ_c)/2|_2|)≤√(8log(2/δ_c)/min(|_1|,|_2|)).

Taking a union bound implies that this holds with probability at least 1-8(AOR)^H-tδ_c=1-δ.




For t∈[0,H], let _1 and _2 be multisets sampled from distributions p_1 and p_2 on Δ(_H-t).
Assume that we use CMS with parameters δ_c=δ/8(AOR)^H-t and ε=√(log(2/δ_c) / 2|_i| ) to store an approximation p_i of the empirical estimate p_i of p_i due to _i, i∈[2].
If p_1≠ p_2 and min(|_1|,|_2|)≥ 32 log (2/δ_c)/μ_0^2, with probability at least 1-δ the statistical test satisfies

    (p_1, p_2) ≥√(8log(16(AOR)^H-t/δ)/min(|_1|,|_2|)).




We can use Lemma <ref> to lower bound the  metric as

    L_(p_1, p_2)    = max_u∈[0,H-t],e∈_up_1(e) - p_2(e)
       ≥max_u∈[0,H-t],e∈_u ( p_1(e) - p_2(e) - p_1(e) - p_1(e) - p_1(e) - p_1(e)
        - p_2(e) - p_2(e) - p_2(e) - p_2(e) )
       ≥μ_0 - √(log(2/δ_c)/2|_1|) - √(log(2/δ_c)/2|_1|) - √(log(2/δ_c)/2|_2|) - √(log(2/δ_c)/2|_2|)
       ≥μ_0 - √(8log(2/δ_c)/min(|_1|,|_2|))≥μ_0 - μ_0/2≥μ_0/2≥√(8log(2/δ_c)/min(|_1|,|_2|)).

Taking a union bound implies that this holds with probability at least 1-8(AOR)^H-tδ_c=1-δ.


The remainder of the proof of Theorem <ref> follows exactly the same steps as in the proof of <cit.>.
For completeness, we repeat the steps here.
The proof consists in choosing N=|| and δ such that the condition on min(|_1|,|_2|) in Lemma <ref> is true with high probability for each application of TestDistinct. Consider an iteration t∈[0,H] of AdaCT-H.
For a candidate state qao∈_𝖼,t+1, its associated probability is _t(q,ao) with empirical estimate p_t(qao)=|(qao)| / N, i.e. the proportion of episodes in  that are consistent with qao. We can apply an empirical Bernstein inequality to show that

    |p_t(qao) - _t(q,ao) |≥√(2p_t(qao)ℓ/N) + 14ℓ/3N = √( 2Mℓ) + 14ℓ/3 /N≤δ,

where M=|(qao)|, ℓ=log(4/δ), and δ is the failure probability of AdaCT-H. To obtain a bound on M and N, assume that we can estimate _t(q,ao) with  accuracy _t(q,ao) / 2, which yields

    _t(q,ao)/2   ≥√( 2Mℓ) + 14ℓ/3 /N
    p_t(qao)    ≥_t(q,ao) - √( 2Mℓ) + 14ℓ/3 /N≥_t(q,ao) - _t(q,ao)/2 = _t(q,ao)/2.

Combining these two results, we obtain

    M    = Np_t(qao) ≥ N_t(q,ao)/2 ≥N/2N√( 2Mℓ) + 14ℓ/3  = 1/2√( 2Mℓ) + 14ℓ/3 .

Solving for M yields M≥ 4ℓ, which is subsumed by the bound on M in Lemma <ref> since <1.
Hence the bound on M in Lemma <ref> is sufficient to ensure that we estimate _t(q,ao) with accuracy _t(q,ao) / 2.
We can now insert the bound on M from Lemma <ref> into (<ref>) to obtain a bound on N:

    N    ≥2 ( √( 2Mℓ) + 14ℓ/3) /_t(q,ao)≥2ℓ/_t(q,ao)8/√((H-t)log(4ARO)/ℓ+ 1 ) + 14/3≡ N_1.

To simplify the bound, we can choose any value larger than N_1:

    N_1    ≤2ℓ/_t(q,ao)8/√(Hlog(4ARO) + Hlog(4ARO) ) + 14/3√(Hlog(4ARO))
       < 32ℓ/_min √(Hlog(4ARO))≡ N_0,

where we have used _t(q,ao)≥_min, <1, ℓ=log 4 + log(1/δ)≥ 1, Hlog(4ARO)≥log 4≥ 1 and 8√(2) + 14/3 < 32/2. Choosing δ=δ_0/2QAO, a union bound implies that accurately estimating _t(q,ao) for each candidate state qao and accurately estimating p(e_0:u*) for each prefix in the multiset (qao) associated with qao occurs with probability 1-2QAOδ=1-δ_0, since there are at most QAO candidate states. Ignoring logarithmic terms, this equals the bound in the theorem.

It remains to show that the resulting RDP is minimal. We show the result by induction. The base case is given by the set _0, which is clearly minimal since it only contains the initial state q_0. For t∈[0,H], assume that the algorithm has learned a minimal RDP for sets _0,…,_t. Let _t+1 be the set of states at layer t+1 of a minimal RDP. Each pair of histories that map to a state q_t+1∈_t+1 generate the same probability distribution over suffixes. Hence by Lemma <ref>, with high probability TestDistinct(t,(qao),(q'a'o'),δ) returns false for each pair of candidate states qao and q'a'o' that map to q_t+1. Consequently, the algorithm merges qao and q'a'o'. On the other hand, by assumption, each pair of histories that map to different states of _t+1 have -distinguishability . Hence by Lemma <ref>, with high probability TestDistinct(t,(qao),(q'a'o'),δ) returns true for each pair of candidate states qao and q'a'o' that map to different states in _t+1. Consequently, the algorithm does not merge qao and q'a'o'. It follows that with high probability, will generate exactly the set _t+1, which is that of a minimal RDP.

The proof of Theorem <ref> is achieved by proving two very similar lemmas.


For t∈[0,H], let _1 and _2 be multisets sampled from distributions p_1 and p_2 on Δ(_H-t), and let p_1 and p_2 be empirical estimates of p_1 and p_2 due to _1 and _2, respectively.
If p_1=p_2, with probability at least 1-δ the statistical test satisfies

    L_(p_1, p_2) ≤√(2log(4||/δ)/min(|_1|,|_2|)).




Let δ_ℓ=δ/2||.
Hoeffding's inequality states that for each ∈ and each i∈{1,2}, with probability at least 1-δ_ℓ it holds that

    p_i() - p_i() ≤√(log(2/δ_ℓ)/2|_i|).

We can now upper bound the language metric as

    L_(p_1, p_2)    = max_∈p_1() - p_2()
       ≤max_∈ ( p_1() - p_1() + p_1() - p_2() + p_2() - p_2() )
       ≤√(log(2/δ_ℓ)/2|_1|) + 0 + √(log(2/δ_ℓ)/2|_2|)≤√(2log(2/δ_ℓ)/min(|_1|,|_2|)).

Taking a union bound implies that this bound holds with probability at least 1-2||δ_ℓ=1-δ.



For t∈[0,H], let _1 and _2 be multisets sampled from distributions p_1 and p_2 on Δ(_H-t), and let p_1 and p_2 be empirical estimates of p_1 and p_2 due to _1 and _2, respectively.
If p_1≠ p_2 and min(|_1|,|_2|)≥ 8log(4||/δ)/μ_0^2, with probability at least 1-δ the statistical test satisfies

    L_(p_1, p_2) ≥√(2log(4||/δ)/min(|_1|,|_2|)).




We can lower bound the language metric as

    L_(p_1, p_2)    = max_∈p_1() - p_2()
       ≥max_∈ ( p_1() - p_2() - p_1() - p_1() - p_2() - p_2() )
       ≥μ_0 - √(log(2/δ_ℓ)/2|_1|) - √(log(2/δ_ℓ)/2|_2|)≥μ_0 - √(2log(4||/δ)/min(|_1|,|_2|))
       ≥μ_0 - μ_2/2≥μ_0/2≥√(2log(4||/δ)/min(|_1|,|_2|)).

Taking a union bound implies that this bound holds with probability at least 1-2||δ_ℓ=1-δ.

The remainder of the proof of Theorem <ref> is analogous to that of Theorem <ref>.
However, we no longer get a term √(H) from √(log((AOR)^H)) unless the number of languages in  is exponential in H.



§ DETAILS OF THE EXPERIMENTS



In this appendix we describe each domain in detail and include examples of RDPs learned by AdaCT-H.



 §.§ Corridor

This RDP example was introduced in  <cit.>. The environment consists of a 2× m grid, with only two actions a_0 and a_1 which moves the agent to states (0,i+1) and (1,i+1) respectively from state (·, i). The goal of the agent is to avoid an enemy which is present in position (0,i) with probability p_i^0, and at (1,i) with probability p_i^1. The agent receives a reward of +1 for avoiding the enemy at a particular column, and the probabilities p_i^0 and p_i^i are switched every time it encounters the enemy. When the agent reaches the last column, its position is reset to the first column. The observation space is given by (i,j,e), where i,j is the cell position of the agent and e ∈{enemy, clear} denotes the presence of the guard in the current cell. Fig <ref> shows the minimal automaton obtained by all three algorithms for H=5.





 §.§ T-maze

The T-maze environment was introduced by Bakker <cit.> to capture long term dependencies with RL-LSTMs. As shown in Figure <ref>, 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 a reward of +4 on taking the correct action at the T-junction, and -1 otherwise, terminating the episode. The agent also recieves a -1 reward for standing still. At the initial state the agent receives observation 011 or 110, 101 throughout the corridor and 010 at the T-junction. Fig <ref> shows the optimal automaton obtained when the available actions in the corridor are restricted to only East (the automaton obtained without this restriction is shown in Fig. <ref>). Table <ref> shows our results with the unrestricted action space. Both our approaches find the optimal policy in this case, unlike Flex-Fringe which fails to capture this long term dependency. 












 §.§ Cookie domain


We modify the original cookie domain as described in Icarte et al. <cit.>, to a simpler domain consisting of 4 rooms, blue, white, green and red as shown in Fig. <ref>. If the agent presses the button in room red, a cookie appears in room blue or 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 a 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 _1,1,1  for distinguishability in the restricted language case. Our restricted language approach here finds the optimal policy and the smallest state space.





 §.§ Cheese maze

Cheese maze <cit.> consists of 10 states, and 6 observations, and 4 actions. After reaching the goal state, the agent receives a reward of +1, and the position of the agent is reintialised to one of the non-goal states with equal probability. Our restricted language approach uses the set _1,1,1. For a horizon of 6, the results for the restricted language and Flex-Fringe are comparable, however upon further increasing the horizon, Flex-Fringe outperforms AdaCT-H by learning cyclic RDPs which is not possible in our approach. 



 §.§ Mini-hall

The mini-hall environment <cit.> shown in Fig <ref> has 12 states, 4 orientations in 3 rooms, a goal state given by a star associated with a reward of +1, 6 observation and 3 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 6 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 B or C. We use the set _1,1,1 in our restricted language approach for distinguishability. Although we get a much larger state space, our algorithm gets closer to the optimal policy. However our CMS approach is not efficient in this case and exceeds the alloted time budget of 1800 seconds, as it requires to iterate over the entire length of trajectories.





































































 




























































































































    

























    


































































