Provably Efficient Offline Reinforcement Learning in Regular Decision Processes
Authors: Roberto Cipollone
Anders Jonsson
Alessandro Ronca
Mohammad Sadegh Talebi
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Offline Reinforcement Learning
Regular Decision Processes
Sample complexity
Automata
TL;DR: We present a provably efficient algorithm for offline Reinforcement Learning in episodic Regular Decision Processes

Abstract: This paper deals with offline (or batch) Reinforcement Learning (RL) in episodic Regular Decision Processes (RDPs). RDPs are the subclass of Non-Markov Decision Processes where the dependency on the history of past events can be captured by a finite-state automaton. We consider a setting where the automaton that underlies the RDP is unknown, and a learner strives to learn a near-optimal policy using pre-collected data, in the form of non-Markov sequences of observations, without further exploration. We present RegORL, an algorithm that suitably combines automata learning techniques and state-of-the-art algorithms for offline RL in MDPs. RegORL has a modular design allowing one to use any off-the-shelf offline RL algorithm in MDPs. We report a non-asymptotic high-probability sample complexity bound for RegORL to yield an $\varepsilon$-optimal policy, which makes appear a notion of concentrability relevant for RDPs. Furthermore, we present a sample complexity lower bound for offline RL in RDPs. To our best knowledge, this is the first work presenting a provably efficient algorithm for offline learning in RDPs.

Provably Efficient Offline Reinforcement Learning in Regular Decision Processes
Roberto Cipollone Sapienza University of Rome cipollone@diag. uniromal.
Anders Jonsson Universitat Pompeu Fabra ceders.jonssonoee edu
Alessandro Ronca University of Oxford www.aaadddooooocaccccaaaaa. roncaccs. ox ac. uk
Mohammad Sadegh Talebi University of Copenhagen m. shahi @dii ku. dk
alessandro
Abstract
This paper deals with offline (or batch) Reinforcement Learning (RL) in episodic Regular Decision Processes (RDPs). RDPs are the subclass of Non-Markov Deci- sion Processes where the dependency on the history of past events can be captured by finite-state automaton. We consider a setting where the automaton that under- lies the RDP is unknown, and learner strives to learn near-optimal policy using pre-collected data, in the form of non-Markov sequences of observations, without further exploration. We present RegORL, an algorithm that suitably combines au- tomata learning techniques and state-of-the-art algorithms for offline RL in MDPs. RegORL has a modular design allowing one to use any off-the-shelf offline RL gorithm in MDPs. We report non-asymptotic high-probability sample complexity bound for RegORL to yield an e-optimal policy, which makes appear a notion concentrability relevant for RDPs. Furthermore, present sample complexity lower bound for offline RL in RDPs. To our best knowledge, this is the first work presenting provably efficient algorithm for offline learning in RDPs.
Introduction
Most reinforcement learning (RL) algorithms hinge the Markovian assumption, i.e. that the underlying system transitions and rewards are Markovian in some natural notion of (observable) state, and hence, the distribution of future observations depends only the current state-action of the system. This fundamental assumption allows one to model decision making using the powerful framework of Markov Decision Processes (MDPs) [1]. However, there many application scenarios where rewards are issued according to temporal conditions over histories (or trajectories), and others where the environment itself evolves in eestory-dependen manner. As result, Markovian approaches may prove unsuitable for modeling such situations. These scenarios can be appropriately modeled Mar-Markovian Decision Processes (NMDPs) [2, 3].
NMDPs describe environments where the distribution on next observation and reward is function of the history. In these environments, behaving optimally may also require to take histories into account, For example, a robot may receive a reward for delivering an item only the item was previously requested, and self-driving rained. Also, consider mobile robot that has to track an object which may disappear from its field of view. The object is likely be found again in the same place where it seen last time. This requires the agent to remember, hence to act according to information in its interaction history. In general, NMDP show arbitrary dependency the history trace, preventing efficient learning. Consequently, recent research has focused on tractable sub-classes NMDPs. In Regular
is more likely to skid and lose control if it previously
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Decision Processes (RDPs) [3], the next observation and reward distributions depend on regular properties of the history, which can be captured by a deterministic finite-state automaton. This determines the existence of finite state space where states are determined by histories, and where the Markov property is regained.
In this paper, we investigate offline RL in episodic RDPs, where the goal is to find a near-optimal policy using a pre-collected dataset, with minimal possible size, generated by a fixed behavior policy (and without further exploration). Offline RL in MDPs has received extensive attention recently, and provably sample efficient algorithms have been proposed for various settings, Despite the extensive and rich literature on MDPs, comparatively little work exists on offline RL in NMDPs. The scarcity of results may likely be attributed to the difficult nature of the problem rather than the lack of interest.
Partially-Ohservalel Markov Decision Processes (POMDPs) [4] are also NMDPs, and RDPs can be seen the subclass of POMDPs that enjoy the property of having hidden states determined by the history of observations. This is a key property that allows one to take advantage of a set of planning and learning techniques that do not apply to arbitrary POMDPs. Planning POMDPs is computationally intractable [5], and two common approaches to solve (and learn) them rely on maintaining either belief state finite history of observations. Maintaining and updating belief state is worst-case exponential in the size of the original observation space, while the latter approach yields a space whose size is exponential in the history length. Sfate-of-thh-ar work on offline RL in POMDPs considers restricted classes of POMDPs such as undercomplete POMDPs (e.g., [6, 7)). which cannot be used model all RDP instances. General POMDPs are only considered under assumptions such as the possibility of reaching every belief state in few steps [8] or ergodicity [9]. While existing offline RL. algorithms for solving POMDPs cannot guarantee provable learning in a generic RDP, the structural properties of RDPs indicate that they can be solved more efficiently using techniques that are carefully tailored to their structure. Exploiting the structure in RDPs is thus key in designing provably sample-efficient learning algorithms.
1.1 Summary of Contributions
We formalize offline RL in RDPs (Section 2), and establish a first, to the best of our knowledge, sample complexity lower bound thereof (Section 5). We introduce algorithm, called RegORL, that learns e-optimal policies for any RDP, the episodic setting. At the core of RegORL, there is component called ADACT-H. which is variant of ADACT [10], carefully tailored to episodic RDPs ADACT-H learns a minimal automaton that underlies the unknown RDP without prior knowledge. The output automaton is further used to derive a Markov abstraction of data to be used by any off-the-shelf algorithm for offline RL in episodic MDPs. We present a comple-comlexxtt bound for ADACT-H H to return minimal underlying automaton with high probability. This bound substantially improves the existing bound for the original ADACT, and can be of independent interest. In view of the modular design of RegORL, the total sample complexity is controlled by twice that of ADACT-H (Theorem 6) and that for the incorporated off-the-shelf algorithm. We also present another variant of ADACT-H, called ADACT-HIA. In contrast ADACT-H that learns complete RDP, ADACT-H-A only reconstructs subset of states that are likely under the behavior policy, in relation to an input accuracy parameter. As such, ADACT-H-A renders more aligned with the practice of RL than ADACT-H. Furthermore, we provide a first lower-bound for offline RL in RDPs that involves relevant parameters for the problem, such as the RDP single-policy concentrability, which extends an analogous notion for MDPs from the literature. Finally, if contrasted to both online learning RDPs and automata learning, our results suggest possible improvements in sample complexity results for both areas.
1.2 Related Work
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; see, e.g., [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]. For example, in the case of episodic MDPs, it is established that the optimal sample size in offline RI. depends on the size of state-space, episode length, well as some notion of concentrability, reflecting the distribution mismatch between the behavior and optimal policies. closely related problem is off- off-policy learning, see, c.g., [21, 22, 23] and the recent survey [24].
2

---

Online RL in RDPs. Several algorithms for online RL in RDPs exist [25, 26, 27] but complexity bounds are only given in [26] for the horizon discounted setting. The sample complexity bounds in [26] are not immediately comparable to ours, due to the different setting. Importantly, the algorithm in [26] uses the uniform policy for learning. and therefore might be adapted to our setting only under the assumption that the behaviour policy is uniform. Even in this case, our bounds show an improved dependency on several key quantities. Furthermore, we provide a sample complexity lower bound, whereas their results are limited to showing that a dependency on the quantities occurring in their upper bounds is necessary.
The online RL algorithms in [28, 29, 30, 31] have been developed for formalisms that are closely related RDPs, and such algorithms can be applied RDPs. However, these algorithms are not proven to be sample efficient.
POMDPs. Every RDP can be seen as POMDP whose hidden dynamics evolves according to its finite-state automaton. However, RL in POMDPs is largely open problem. Even for a known POMDP, computing a near-optimal policy is complee [5]. For unknown dynamics, which is the setting considered here, favourable bounds have been obtained for the class of undercomplete POMDPs [6, 7], which does not include all RDPs, or alternatively, under other assumptions such as few-step reachability [8] or ergodicity 19]. This relationship between RDPs and POMDPs can be also seen from the notion of state. In fact, the automaton state of an RDP is an instance of information state, as defined in [32], and of belief, as in classic POMDP literature [33].
PSRs. Predictive State Representations (PSRs) [34, 35, 36, 37] are general descriptions of dynami- cal systems that capture POMDPs and hence RDPs. There exist polynomial PAC bounds for online RL in PSRs [38]. Nonetheless, these bounds are looser than the one we show here, since they must necessarily consider wider class of models. Moreover, although minimum core set for PSRs is similar to a minimal RDP, the bounds feature a number of quantities that are specific to PSRs (c.g.. regularity parameter) and do not immediately apply to RDPs.
Other Mon-Markov Settings. Feature MDPs and state representations both share the idea of having map from histories to state space. This is analogous to the map determined by the transition function of the automaton underlying an RDP. Algorithmic solutions for feature MDPs based suffix trees, and they cannot yield optimal performance in our setting [29, 30]. The automaton of an RDP can be seen as providing one kind of state representation [39, 40, 41, 42]. The existing bounds for state representations show linear dependency representations, which is exponential in the number of states in our case. A similar dependency is also observed in [43]. RL with Markovann rewards is considered in [44, 45, 46, 47, 48, 49]. The idea of a map from histories to states is also found in [32]. Non-Markovianity is also introduced by logical specifications that the agent required to satisfy [50, 51, 52, 53, 54]; however, it is resolved a priori from the known specification. The convergence properties of Q-learning over a (known) underlying state space such as the one of an RDP are studied in [55].
the number of candidate
Learning PDFA. Our algorithms for learning an RDP borrow and improve over techniques for learning maabbilistic-Deteeminnttt Finite Automata (PDFA) [56, 57, 57, 10, 59, 60). Our algorithm builds upon the state-of-the-art algorithm ADACT [10], and we derive bounds that are a substantial improvement over the ones that would be obtained from a straightforward application of any existing PDFA-learning algorithm to the offline RL setting.
We provide additional literature review in Appendix A.
2 Preliminaries and Problem Formulation
Notations. Given a set V, A()) denotes the set of probability distributions over V. For a function
f: X A()), f (zr, y) is the probability of y given æ. Further, write y y~ [(x) abbreviate
y ~ [(x, .). For y E y, we use 1, E (()) to denote the Kronecker delta defined as 1, 1y) = 1 and (y') = 0 for each y' )' such that y' * y. Given an event F,, TI (E) denotes the indicator function of E, which equals 1 if E' is true, and 0 otherwise, c.g. 1,'))) 1(y = y'). For any integer 2 2 0, we let [Z] = {O...., Z}. Given a set X, for & E N. x represents the set of sequences of length & whose elements from X. Also, X U The notation (-)) hides logarttgaii terms.
3

---

2.1 Episodic Regular Decision Processes
We first introduce generic episodic decision processes. An episodic decision process is a tuple P = (O, A. R. T, R. H), where O is a finite set of observations, AA is a finite set of actions, R C [o, 1] is a finite set of rewards and H 2 1 is a finite horizon. As is common in automata theory, we use sequences am Om ... Onnnnn on to denote traces of actions, rewards and observations, and concatenation ARO = {aro : a E A.r E R. E O to denote sets of sequences. Let & = (ARO))+ be the set of traces of length i. + 1, and let Cncn E En-m denote a trace from time m to time n, included. A trajectory C0.T the full trace generated until time T. We assume that a trajectory 60.7 can be partitioned into episodes E1.++ EH of length H + 1, and that the dynamics at time T = k(H + + t E [H]. are conditionally independent of the previous episodes and all rewards, i.e. the dynamics only depend on (c(H+))0k(++)) ". .00 For t E [H], let H₂ (AO)(+1 denote the relevant part of the trajectory for decision making, and let H H. We refer to elements in H as histories, even though they are not complete trajectories. In each episode CD:H. ao T is a dummy action used to initialize the distribution on Ho. The transition function T: H x A - (OO) and the reward function R: H x A + A(R) only depend on the history of the current episode. Given P. generic policy a function π (AO)) + (A4) that maps trajectories to distributions over actions. The value function V [H] x H + R of policy и is a mapping that assigns real values to histories. For h E H. it is defined as V (H, h) = and
H
(t(th))== = E
Σ
T4 h
Vt < H, Ah E He.
(1)
1-1+1
For brevity, we write (h) (= V" h). The optimal value function V defined as (h) = sup, V (h), VI E [H] Vh E Hr, where sup is taken over all policies π (AO))* - (AA). Any policy achieving V is called optimal, which we denote by x"; namely V = V Solving P amounts to finding π. In what follows we consider simpler policies of the form π : H - A(A) mapping histories to distributions over actions. Let Hy denote the set of such policies. can be shown that 17 always contains an optimal policy, i.e. (h) == max (1((h), VI E [H], Vh- E He, An episodic MDP is episodic decision process whose dynamics each timestep only depends on the last observation and action [1].
Episodic RDPs. An episodic Regular Decision Process (RDP) [3, 25) is an episodic decision process R R R, T, R. H) described by a finite transducer (Moore machine) (Q, Σ, 92, T, 8, qo), where is a finite set of states, Σ = AO is finite input alphabet composed of actions and observations, Q a finite output alphabet, T : Q x Σ- + Q is a transition function, : Q + Ω is an output function, and go E Q is fixed initial state [61, 62, 63]. The output space Ω Ω. x Ω consists of a finite set of functions that compute the conditional probabilities of observations and rewards, two output functions, 8. : @ A + ((O) and 0, Q x A A(R). to denote the individual conditional probabilitics. L denote the inverse of 1.,,ie ie. T (g) C Q x AO is the subset of state-symbol pairs that map to q E Q. In this context, an input symbol is an element of AO. We use A, R, O, Q to denote the cardinality of A, R, O, Q, respectively, and assume A 2 2.
meaning So C A + A(O) and Ω A + ARR). For simplicity,
An RDP R implicitly represents a function ;: H + 2 from histories in H to states in Q, recursively defined as 7 (ho) == Tgoo, anon) and F(hx) == -(F(,,, 1), a.o:). The dynamics and of R are defined as T(h, a, o) = (F) a, o) and R(h, r) = (7hh), a, r). Vh E H. Varo E ARO. Episodic RDPs are acyelic, i.e. the states can be partitioned as Q Qn U ... U QH+1, where each Q is the set of states generated by historics in H, for each t E [H]. An RDP is minimal if its Moore machine is minimal. Since there is nothing to predict at time H - 1, a minimal RDP contains single state 1 in QH+1- To ensure that an acyclic RDP R is minimal, we introduce a designated termination observation T_ in O and define T(g ao1)= = qu++1 and (0 a) 1,, for each a E A. Hence, +1 is absorbing and the states in Q implicitly count how many steps are left until we observe -T. Without To, a Moore machine could potentially represent all episodes using fewer than H + 2 states.
Since the conditional probabilities of observations and rewards are fully determined by the current state-action pair (g. a), an RDP R adheres to the Markov property over its states, but not over the observations. Given a state q: Q and an action a, E A, the probability of the next transition is
(rr,, on: g0+1
gt, oz, R) (g a, T.) oo a, 0:) llq(41 =[(gt, 0(0)).

---

(a) Cookie domain.
(b) Agent's view.
Figure 1: The cookie domain: The agent can only what is in the current room [28].
Evidently, in the special case where an RDP is Markovian in both observations and rewards, it reduces to an episodic MDP. More precisely, any episodic MDP with actions A, states O and horizon can be represented by some episodic RDP with states Q S O x [H + 1] and inputs AO.
An important class of policies for RDPs are the regular policies. Given an RDP R, policy H -> (AA) is called regular if π (h1) = π (hh2) whenever F(h1) (h2), for all h1, h2 E H. Let R 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.
Proposition 1. Consider an RDP R. a regular policy л E IR and two histories hy and h in Hr t E H such that T(h2) = 7(h2). For each suffix e+41: E EH-t-1, the probability of generating 6:41:1 1:H is the same for h1 and h2, i.e. P(e141:H h1, n. R) = P(et+1:H h2, n, R).
Proposition 2. Each RDP R has at least one optimal policy πt E 1lR.
Due to Proposition 2, when solving an RDP R. we can restrict our search to the set of regular policies I A regular policy can be compactly defined as Q - A(A), where π (40) 1a1 always selects the dummy action dj, and its value function as V [ x 2 R.
Next, we define occupancy measures for RDPs. Given regular policy π Q + ((A) and t E [H] let di E A(Q, AO) be the induced probability distribution over states Qe and input symbols A O, recursively defined as dī (40, agoo) == 0o 0o, 00) and
di (It, (+o:) =
Σ
d. 14 ao) x x(11, 0o (1,
t> 0.
(q.a0)ET ((g))
We also overload the notation by writing dī (gt, az) = EoEo d' (gt, azo). Of particular interest is the occupancy distribution di == dd associated with an optimal policy n².
Example (The cookie domain [28]). The cookie domain (Figure la) has three rooms connected by a hallway. The agent (purple triangle) can move in the four cardinal directions. When pressing button in the orange room, cookie randomly appears in either the green the blue room. The agent receives reward of +1 for eating the cookie and it may then press the button again. This domain partially observable since the agent can only see what is in the room that currently occupies (Figure lb). The cookie domain can be modelled as an episodic RDP with states Q = [H [H+1] 1-11]xx xu. with 4 = {u,, U2, U3, u4). The value of 24 μj when the button has not been pressed yet (or not pressed since the last cookie was eaten). The value is U2 when the button has been pressed, but the agent has not visited the blue or green room yet. In this state, the environment has a 50% probability of generating the observation of cookie when the agent enters either room for the first time. If the agent visits the green room and finds no cookie, the value becomes uz, meaning that the cookie is in the blue room. The meaning of un is dual to that of uz.
2.2 Offline RL in RDPs
We are now ready to formally present the offline RL problem in episodic RDPs. Assume that we have access batch dataset collected through interacting with an unknown (but fixed) episodic RDP R using regular behavior policy nb. We assume that D comprises N episodes, where the k-th episode is of the form e/t afrg ... ...a & where dă qo and where, for each E (H).
de (g))), ot a.), of 0olo, af), dia = o.
5

---

The goal is to compute a opar-optimal policy गे using the dataset 'D (and without further exploration). More precisely, for pre-specified accuracy E (0, H], we aim to find an s-optimal policy म. using the smallest dataset D possible. A policy क is s-optimal iff ENo Vo (ho) VØ² (ho)] S E, where ho = a_ Oo, for some random On E O.
By virtue of Proposition 2, one may expect that it is sufficient to search for regular e-optimal policies, which is indeed the case. In order to learn an e-optimal policy from D, some assumption is necessary regarding the policy xb that was used to collect the episodes. Let de == d; be the occupancy distribution of T². The following assumption requires that the behavior policy assigns positive probability all actions, which ensures that TD explores the entire RDP.
Assumption 1. minig di (g. a) 0.
Assumption is only needed by Theorem 6, which reconstructs the full unknown RDP. Theorem 8, instead, relies weaker assumption that can be expressed with the coefficient introduced in Definition 1.
The second assumption we require concerns the richness of n² and its capability to allow us to distinguish the various RDP states. This is perfectly captured by notions of distiguishubility arising in automata theory, such as in Balle et al. [10]. We apply these concepts in our context, where such discrete distributions are generated from an RDP and a policy. Consider a minimal RDP R with states Q Ut ②t Given some policy x, at each timestep & [H] every RDP state q Qr defines unique probability distribution over the episode suffixes Eн (ARO) Then, the states in each O2 can be compared through the probability distributions they induce over E Consider any L [Le]r- where each Lg is a metric over (EE)). We define the L-distinguishaabiity of R and π as the maximum d4o such that, for any E [H] and any two distinct q, o' E Qt, the probability distributions over suffix traces Et.H E & from the two states satisfy
LH LP q: q, x), P(e.H 4: g', T)) 2 No.
We will often omit the remaining length of the episode & = H - 1 from L,f and simply write L. We consider the T. -distinguisaabiiity, instantiating the definition above with the metrie T. (p1,72) p2) max [Pi (e x) p2 +),, where pi(e *) represents the probability of the trace prefix e E E,,, followed by any trace e' E Ez- The L iigiisiinuushaabiity is defined analogously using LP p2) Ene(",,ee,, (e*) p2(e+)], We can now require positive distinguishability with our second assumption.
Assumption 2. The behavior policy xb has Li distinguishabiiity of at least μu 0.
Finally, in order to capture the mismatch in occupancy measure between the optimal policy and the behavior policy, introduce key quantity called single-policy RDP concentrability coefficient, which extends the single-policy concentrability coefficient in MDPs to RDPs:
Definition 1. The single-policy RDP concentrability coefficient of an RDP R with episode horizon H and with respect to a policy nh is defined as:
max di (q. ao) (E[H], a0 db ao)
CR.
The concentrability coefficient in Definition resembles the notions of concentrability in MDPs (e.g.. [14, 15)). It should be stressed, however, that those in MDPs are defined in terms of observation- action pairs (o, a), whereas CR is defined in terms of hidden RDP states and actions-observationn,, (g, ao). It is worth remarking that C could be equivalently defined in terms of state-action pairs (9. a). Finally, in the special case where the RDP is Markovian in which case coincides with an episodic MDP- - we have Q C O x H + 1] and CR coincides with the standard single-policy concentrability coefficient for MDPs in [15]. This fact is shown in the proof of Corollary 17.
3 RegORL: Learning an Episodic RDP
In this section we present an algorithm for learning the transition function of an RDP R. from dataset D of episodes generated by a regular behavior policy xb. To simplify the presentation, we treat D multiset of traces in En. The learning agent only has access to the non- Mar-Maaoviann traces

---

Function ADACT-H(D, 8)
Input: Dataset D containing N traces in Ex,, failure probability << 8 <
Output: Set Q of RDP states, transition function 7 Q AO - Q
Qo t {g.) (go) 4 D
// initial state
for - H do
// get candidate states foreach gao E 20,4+1 do X(q00) t fe++1:11 ar0er+1:11 E EX(4)) // most common candidate
Qe,141 - {9a0 gE 20, AO}
// compute suffixes
@mammm f- arg maX [g(o)]
Q4+1 ammammm) T(4m: am0m) gm4mOm
// pronote candidate // remove from candidate states
Qc,t11 t 2c,441 {m for quo E Qc,1+1 do
Similar + {g' E Q441 not TIgT x(')), if Similar 0 then 2++1 + Cc+1 U (quo), 2o) qao
// confidence test // promote candidate // merge states
11
else q' + element in Similar, 7 ao) d(') + x(4') U (qao)
end
13 end
14 return Co U... QH+L.
is Function TESTDISTINCT(,, Xi, X2, 6)
return Lh (2,, X2) 2 (2log(((ARO) min (11,,, (22
in D, and needs prior knowledge of A, and O, but no prior knowledge of nD and R. Our algorithm is an adaptation of ADACT [10] to episodic RDPs, and we thus refer to the algorithm as ADACT-H.
The intuition behind ADACT-H is that due Proposition 1, two histories h1 and h2 should map to the same RDP state if they induce the same probability distribution on suffixes. ADACT-H starts by adding an initial RDP state qu to Qu whose suffixes are the full traces in D (line 1). The algorithm then iteratively constructs the state sets Q1.... QH In each iteration t E [H] ADACT-H creates set of candidate states Qc,t+1 by extending all states in Q, with symbols in AO (line 3). We use qao to simultancously refer to a candidate state and its state-symbol prefix (q, ao). We associate each candidate state qao with multiset of suffixes Xgao), i.e. traces in E obtained by selecting all suffixes in X²) that start with action a and observation o (line 4).
Next, ADACT-H finds the candidate state whose suffix multiset has maximum cardinality, and promotes this candidate to 2++1 by defining the transition function 7 accordingly (lines 5-7). The algorithm then iterates over each remaining candidate state quo Qc,44.1. comparing the distribution on suffixes in (gao) to those of states in 24+1 (line 9). If the suffix distribution is different from that of each state in Q++1. gao is promoted to Qc+1 (line 10), else qao merged with a state d' E Q that has a similar suffix distribution (line 11). Finally, ADACT-H H returns the set of RDP states Q and the associated transition function т. The function TESTDISTINCT compares two multisets Xi and Xr of traces in εn -t11 using the metric T.P- For i E {1,2) and each trace e E E let
(e) ExEx, [([r= = e) be the empirical estimate of Pt, as the proportion of elements in X;
equal to e. TESTDISTINCT compares L (Xi, X2) == L& (P), P2) to confidence threshold.
Markoy transformation. We are now ready to connect the RDP learning phase with the MDP learning phase. RDPs do not respect the Markov property over their observations and rewards, automaton states remain hidden. However, we can use the reconstructed transition function 7 returned by ADACT-H, extended over histories as : H - Q, to recover the Markov property. In what follows we formalize the notion of Markov transformation and the properties that its outputs satisfy.
Let CD:H E Eh be episode collected from RDP R and policy xb that is regular in R. The Markov transformation of eи with respect to R is the episode constructed as agroq1 ... OHT where It+ F(he) and he 0g00 -....-.-.,0. transformation of dataset 'D is the Markov transformation of all the episodes it contains.
Definition 2.
[H]] The Markoy
A Markov transformation discards all observations from D and replaces them with RDP states output by 7. The dataset so constructed can be seen as generated from an MDP, which we define next.
Definition The episodic MDP associated to an episodic RDP MR. = (,, H), where T(g, a, d') Eoeo l(d' = T(q, ao)) (o (, a, o) for each (g. a, df) Q x Ax Q.
7

---

The associated MDP in Definition 3 is the decision process that corresponds to the Markov transfor- mation of Definition 2, i... any episode produced with the Markov transformation can be equivalently seen as being generated from the associated MDP, in the sense of the following proposition.
Proposition 3. Let E0.H be an episode sampled from an episodic RDP under a regular policy E I with (h, a) = (7(h),)), Ife is the Markov transformation of en with respect to R, then Pe(e R, = P( MR, T.), where MR. is the MDP associated to R.
Rewards are not affected by the Markov transformation, only observations, implying the following. IlR be a regular policy in R such that x x(h,a) (t(F(h), a). Then E[VØR = E V.V, u.Mn where VOR and V.Ma, are the values in the respective decision process, and R = R. V o. where expectations are with respect to randomness in on-
Proposition 4. Let
Corollary 5. Given E (0, H). if n. Q + A(A)) is e-optimal policy of MR. the MDP associated to some RDP R. then, ah, (T(())), a) is E-optimal in R.
In summary, from Proposition 3, if Dm is the Markov transformation of a dataset D with respect to an RDP R. then, Dm can be seen as being generated from the associated MDP MR. Hence, any offline RL algorithm for MDPs can be used for learning in Dm. Moreover, according to Corollary 5, any solution for MR. can be translated via into policy for the original RDP, with the same guarantees.
Complete algorithm. The complete procedure is illustrated in Algorithm 1. Initially, the input dataset D is separated in two halves. The first portion is used for learning the transition function of the unknown RDP with ADACT-EE (Section 3). If an upper bound Q on Q is available, it can optionally be provided to compute a more appropriate failure parameter for ADACT-H. If not available, we adopt the upper bound of 2(AO) # states, which is valid for any instance, due histories having finite length. As we will see in Theorem 6, this would only contribute linearly in H to the required dataset size. The output function computed by ADACT-H is then used to compute Markov transformation of the second phase, as specified in Definition 2. The resulting dataset, now Markovian, can be passed generic offline RL algorithm, which we represent with the function OFTLINEL((DDe, 8). In Appendix D, we instantiate it for a specific statc-of- -ftth-rf- offline RL algorithm.
Algorithm 1: Full procedure (RegORL)
Input: Dataset 2), accuracy E (0, H). failure probability 0 5 < 1, (optionally) upper bound Q on |Q] Output: Policy H. + ((A)
D1, D2 + separate D into two datascts of the same size
Q, r < ADACT-H(D), 5/ (1AOQ)), where Q = (AO)# not provided
D22 Markov transfrmmttion D2 with respect as in Definition 2 Am <- OFFLINERL 6/2)
return से h + (f)))
4 Theoretical Guarantees
We now turn to theoretical performance guarantees of RegORL. Our main performance result is a sample complexity bound in Theorem ensuring that, for any accuracy s E (0, H). RegORL finds e-optimal policy. We also report a sample complexity bound for ADACT-H in Theorem 6, and an alternative bound in Theorem In comparison, the sample complexity bound for ADACT [10] is
δ ( ("'AP02H*'oog log(111
max {
A2
})-
E2
(M3 E+
We achieve a tighter bound by using Bernstein's inequalities and exploiting the finiteness of histories.
Theorem 6. Consider dataset of episodes sampled from an RDP R and regular policy b E UR With probability 1- 8, the output of ADACT-H(D, (DA is the transition runsition,function
of the minimal RDP equivalent R, provided that [D] 2 Ng. where
21 (ooog(QQA/ / H log (AAO)) E
H
N₂
db Quin Pg
jbb dein 140
8

---

diain: == min (g. ao) i E [H],q E Qa.ao E AO, d2 (0. ao) > 0f is the minimal occupaney distribution, and Po is the L distinguishaaiiiiyy.
The proof appears in Appendix C.2. Theorem 6 tells us that the sample complexity of ADACT-H, to return a minimal RDP, is inversely proportional to μo. the T. dd--siinguuisabblliy of R. and nb, and the minimal occupancy de dinin. Note that di S 1/(QOA), The bound also depends on Q, the number of RDP states, implicitly through da dmin and explicitly via a logarithmic term. In the absence of prior knowledge of Q, one may use in the argument of Algorithm I the worst-case upper bound Q = 2( ((A0)". The sample complexity would then have an additional linear term in H, since Q is only used in the logarithmic term to set the appropriate value of 6. However, this will not impact the value of the de term.
Theorem is a sample complexity guarantee for the first phase of the algorithm, which learns т, the structure of the minimal RDP that is equivalent to the underlying RDP. If ó is the desired failure probability of the complete algorithm, RegORL executes ADACT-H at least 1 - 5/2. This means that with the same probability, D/2 is an MDP dataset with the properties listed in Section 3. As a consequence, provided that OFFLINERL is some generic (a. 8/2)-PAC offline RL algorithm for MDPs, the output of RegüRL is an e-optimal policy with probability 1 - 8.
that its success probability is
Theorem 7. Consider dataset D of episodes sampled from an RDP R and regular policy T E RR For any E (0, H and 0 < 8 < 1, if OFFLINERI. an (e. 8/C)-PCC offline algorithm for MDPs with sample complexity Nm. then, the output of RegORL e, e, is an e-optimal policy in R. with probability at least 6, provided that [D] z max(Na/2) N.
As we can see, the sample complexity requirement separates for the two phases. While Na/2 is due to the RDP learning component, defined in Theorem 6, the quantity Nm completely depends on the offline RL algorithm for MDPs that is adopted. Among other terms, the performance guarantees of offline algorithms can often be characterized through the single-policy concentrability for MDPs C* However. since states become observations in the associated MDP, due the properties of Proposition 3, C' coincides with CR. the RDP single-policy concentrability of Definition 1.
In Appendix D, demonstrate a specific instantiation of RegORL with off-the-shelf offline RL algorithm from the literature by et al. [16]. This yields the following requirement for Nm:
c c1f log N
Nm
e²
for constant 0.
To eliminate the dependence that Theorem has on diiin- we develop a variant of ADACT-H which does not learn a complete RDP. Rather, it only reconstructs a subset of states that are likely under the behavior policy. The algorithm, which we call ADACT-H-A (with 'A' standing for "approximation" "), is defined in Appendix C.3. Theorem 8 is an upper bound on the sample complexity of ADACT- H-A that takes the accuracy E as input and returns the transition function of an E/ e/2-approximat RDP R', whose optimal policy is s/ /2-ooptm for the original RDP R. By performing a Markov transformation for R' and using an (e/2, 8/2 PPC offline algorithm for MDPs, we can compute an eopptiall policy for R. The total sample complexity can be combined in the same way as in Theorem 7.
Theorem 8. Consider a dataset 'D of episodes sampled on RDP R. and regular policy nb UR- With probability 1 - 8, the output of ADACT-H-A. called with D, 8/(QQAO) and E E (0, Hj in input, is the transition function of an e/2-approximate RDP R', provided that [D] 2 N23. where
No = 50AHQAOC log (66QAA/0))
(0//QAOOR
Hogg(2ARO) Ō
8
8/0
This theorem does not rely on Assumption 1, because a finite CR suffices.
Sample Complexity Lower Bound
The main result of this section is Theorem 9, sample complexity lower bound for offline RI. in RDPs. It shows that the dataset size required by any RL algorithm scales with the relevant parameters.

---

901
O
711
F.B
Bo
V.
Y,
og. V-- sing
+
9b1
9ba
ag-26
Figure 2: One episodic RDP instance R101,1 E (R, H, associated to the parity function f101. with code 101, and the optimal arm dj. The length is L [101] 3, the horizon H = 5, the noise parameter & and the bandit bonus parameter is 1/. The transition function only depends on the observations, not the actions. The output distributions are:
unif(0, 1). u unif -}. va(+) (1 + a2/2, (a(-)= (1- (1-a)/2. The star denotes any symbol. If the label of state is a.d, then the observation function is (g a) = d. Refer to Appendix E for details.
Theorem 9. For any (CR: Po) satisfying CR 2 2, 2 and & S 1oo/64 there exists an RDP with horizon H, L. di-isiinguishabiityy po and a regular behavior policy Th with RDP single-policy concentrability CR. such that if has been generated using n. and R, and
H
CR 62
D $
Ω
(3)
140
then, for any algorithm A DD + To returning non-Markov deterministic policies, the probability that ß is not e-optimal least
The proof relies on worst-case RDP instances that carefully combine two-armed bandits with noisy parity functions. This last component allows to capture the difficulty of learning in presence of temporal dependencies. Figure shows an RDP in this class. the beginning of each episode, the observation causes transition towards either the bandit component (bottom branch) or the noisy parity function (top branches). Acting optimally in the two parity branches requires to predict the output of a parity function, which depends on some unknown binary code (of length 3, in the example). The first term in Theorem 9 due to this component, because the code scales linearly with H, Q, while the amount of information revealed about the code is controlled by μoo The second term is caused by the required optimality in the bandit.
Differently from this lower bound, the parameter μoo appearing in the upper bounds of Theorems and 8, is L -idiiinnuuisaablitt.. However, the two are related, since L g') (g.99)) 2o Intuitively, the T. ii-distinguishabiiity accounts for all the information that is available as differences in episode probabilities. The L.P. distinguishabbiltty on the other hand, quantifies the maximum difference in probability associated to specific suffixes. This is the information used by the algorithm and the one appearing in the two upper bounds.
Conclusion
In this paper we propose an algorithm for Offline RI episodic Regular Decision Processes. Our algorithm exploits automata learning techniques reduce the problem RL in RDPs, in which observations and rewards are non-Markovian, into standard offline RL for MDPs. We provide the first high-probabilityy sample complexity guarantees for this setting, well lower bound that shows how its complexity relates to the parameters that characterize the decision process and the behavior policy. We identify the RDP single-policy concentrability as an analogous quantity the one used for MDPs in the literature. Our sample complexity upper bound depends on the LP, -iisinguishability of behavior policy. As a future work, we plan to investigate any milder notion distinguishability also suffices. This is motivated by our lower bound which only involves the I.-ddistinuuihaabiliy over the same policy. Finally, our results have strong implications for online learning in RDPs, which is relevant setting to be explored.
10

---

Acknowledgments
Roberto Cipollone is partially supported by the EU H2020 project AIP (No. 101016442), the
ERC-ADG White-Mech (No, 834228), the EU ICT-48 2020 project TAILOR (No. 952215), the PRIN project RIPER (No. 20203FFYLK), and the PNRR MUR project FAIR (No. PE0000013). Anders Jonsson is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215), AGAUR SGR, and the Spanish grant 10811199-0111B-----
Alessandro Ronca is partially supported by the ERC project WhiteMech (No. 834228), and the ERC project ARiAT (No. 852769). Mohammad Sadegh Talebi partially supported by the Independent Research Fund Denmark, grant number
1026-00397B.
References
[1] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 1994.
[2] Fahiem Bacchus, Craig Boutilier, and Adam J. Grove. Rewarding behaviors. AAAA, pages 1160-1167, 1996.
[3] Ronen I. Brafman and Giuseppe De Giacomo. Regular decision processes: model for non manakvaoov domains. In IJCAI, pages
2019.
[4] Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artif. Intell,, 101(1-2):99-134, 1998.
[5] Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of Markov dccision processes. Mathe- matics of Operations Research, 12(3):411-450, 1987.
[6] Chi Jin, Sham M. Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete POMDPs. In NeurlPS, 2020.
[7] Hongyi Guo, Qi Cai. Yufeng Zhang, Zhuoran Yang. and Zhaoran Wang. Provably efficient offline reinforcement learning for partially observable Markov decision processes. In ICML, pages 8016-8038, 2022.
[8] Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A PAC RL algorithm for episodic POMDPs. In AISTATS, pages 510-518, 2016.
[9] Kamyar Azizzadeneshell, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of POMDPs using spectral methods. In COLT, pages 193-256, 2016.
[10] Borja Balle, Jorge Castro, and Ricard Gavaldà. Learning probabilistic automata: study in state distin- guishability. Theor. Comput. Sei., 473:46-60 60, 2013.
[11] Masatoshi Uehara and Wen Sun. Pessimistic model-hased offline reinforcement learning under partial coverage. In ICIRR, 2022.
[12] Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. In NeurlPS, pages 4065-4078, 2021.
[13] Jinglin Chen and Nan Jiang. Information-theerriiic considerations batch reinforcement learning. In ICML, pages 1042-10 1051, 2019.
[14] Tengyang Xie, Nan Jiang. Huan Wang. Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample- efficient offline and online reinforcement lcarning. In NeurlPS, pages 27395-27407, 2021.
[15] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. In NeurlPS, pages 1 11702-11716, 2021.
[16] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settlng the sample complexity of model-based offline reinforcement learning. CoRR, 0bb//2044.0225,.20 2022.
[17] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In COLT, pages 2730-2775, 2022.
[18] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In ICML, pages 5084-5096, 2021.
[19] Tongzheng Ren, Jialian Li, Bo Dai, Simon Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. In NewrIPS, pages 15621-15634 2021.
[20] Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. ICLR, 2022.
[21] Philip Thomas and Emma Brunskill. Dfta-efficient off-policy policy evaluation for reinforcement learning.
In International Conference Machine Learning, pages 1139-1148. PMLR, 2016.
11

---

[22] Hamid Reza Maei, Csaba Szepesvári. Shalabh Bhatnagar, and Richard S Sutton. Toward off oof-policy learning control with function upproximation. In ICML. pages 719-726, 2010.
[23] Nathan Kallus and Masatoshi Uchara. Double reinforeement leamingg for efficient off oool- evaluation in Markov decision processes. The Journal of Machine Learning Research, 21(1):67426604 2020.
[24] Masatoshi Uehara, Chengchun Shi, and Nathan Kallus. A review of off- off-policy evaluation in reinforcement learning. arXiv preprint arXiv:2212.06335, 2022.
[25] Eden Abadi and Ronen I. Brafman, Learning and solving regular decision processes. In IJCAI, pages 1948-1954, 2020.
[26] Alessandro Ronca and Giuseppe Giacomo. Efficient PAC reinforcement learning in regular decision processes, In ICCAI, pages 2026-2000 2032, 2021.
[27] Alessandro Ronca, Gabriel Paludo Licks, and Giuseppe De Giacomo. Markov abstractions for PAC reinforcement learning in non-Markov decision processes. IJCAI, pages 3408-3415, 2022.
[28] Rodrigo Toro Iearte, Ethan Waldie, Toryn Q Klassen, Richard Anthony Valenzano, Margarita P. Castro, and Sheila A. Mcllraith. Learning reward machines for partially observable reinforcement learning. In NewrIPS, pages 15497-15508, 2019.
[29] Marcus Hutter. Feature reinforcement learning: Part I. Unstructured MDPs. J. Artif. Gen. Intell., 1(1): 3-24, 2009.
[30] Joel Veness, Kee Siong Ng, Marcus Hutter, William T. B. Uther, and David Silver. A Monte-Carlo AIXT approximation. Artif. Intell. Res., 40:95-142, 2011.
[31] M. M. Hassan Mahmud. Constructing states for reinforcement learning. In ICML, pages 727-734, 2010.
[32] Jayakumar Subramanian, Amit Sinha, Raihan Seraj, and Aditya Mahajan. Approximate information state for approximate planning and reinforcement lcarning in partially observed systems. The Journal of Machine Learning Research, 23(1))483-56)
2022.
[33] Karl Johan Aström. Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications, 10(1):174 205, 1965.
[34] Satinder Singh, Michael I.. Littman, Nicholas K. Jong, David Pardoe, and Peter Stone. learning predictive state representations. In JCML. pages 712-719, 2003.
[35] Michacl R. James and Satinder Singh. Learning and discovery of predictive state representations in dynamical systems with reset. In ICML, 2004.
[36] Michael H. Bowling. Peter McCracken, Michael James, James Neufeld, and Dana E. Wilkinson. Learning predictive state representations using non-blind policies. ICML, pages 129-136, 2006.
[37] Alex Kulesza, Nan Jiang, and Satinder Singh. Spectral learning of predictive state representations with insufficient statistics. In AAAI, pages 2715-2721, 2015.
[38] Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D. Lee. PAC reinforcement learning for predictive state representations. In ICLR, 2023.
[39] Aitaric-AAbbyer Maillard, Rémi Munos, and Daniil Ryabko. Selecting the state-representation in rein- forcement learning. In NeurIPS, pages 2627-2635, 2011.
[40] Phuong Nguyen, Odalric-Ambrym Maillard, Daniil Ryabko, and Ronald Ortner. Competing with an infinite set of models in reinforcement learning. In AISTATS, pages 463 471, 2013.
[41] Odmlric-Ambrym Maillard, Phuong Nguyen, Ronald Ortner, and Daniil Ryabko. Optimal regret bounds for selecting the state representation in reinforcement learning. In JCML, pages 543-551, 2013.
[42] Ronald Ortner, Mattco Pirotta, Alessandro Lazaric, Ronan Fruit, and Odalric-Ambrym Maillard. Regret bounds for lcarning state representations in reinforcement learning. In NeurlPS, pages 12717-12727, 2019.
[43] Tor Lattimore, Marcus Hutter, and Peter Sunehag. The sample-complexity of general reinforcement learning. In ICML, pages 28-36, 2013.
[44] 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 ICMI., pages 21 2112-112 2018.
[45] Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topcu, and Bo Wu. Joint inference of reward machines and policies for reinforcement leaming. In ICAPS, pages 590-598, 2020.
[46] Giuseppe De Giacomo, Luca locchi, Marco Favorito, and Fabio Patrizi. Foundations for restraining bolts: Reinforcement learning with LTLI/LDLf restraining specifications. In ICAPS, pages 128-136, 2019.
[47] Giuseppe De Giacomo, Marco Favorito, Luca locchi, Fabio Patrizi, and Alessandro Ronca. Temporal logic monitoring rewards via transducers. In KR, pages 860-870, 2020.
12

---

[48] 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. pages 7647-7656, 2021.
[49] Hippolyte Bourel, Anders Jonsson, Odalric-Ambrym Maillard, and Mohammad Sadegh Talebi. Exploration in reward machines with low regret. In International Conference Artificial Intelligence and Statistics, pages 14-4146. PMLR, 2023.
[50] Jie Fu and Ufuk Topeu. Probably approximately correct MDP learning and control with temporal logic constraints. In RSS, 2014.
[SI] Mohammadhosein Hasanbeig. Alessandro Abate, and Daniel Kroening. Cautious reinforcement learning with logical constraints. In AAMAS, pages 483-491, 2020.
[52] Lewis Hammond, Alessandro Abate, Julian Gutierrez, and Michael J. Wooldridge. Multi Multi-agent reinforce- ment learning with temporal logic specifications. In AAMAS, pages 583-592, 2021.
[53] Alper Kamil Bozkurt, Yu Wang, Michael M. Zavlanos, and Miroslav Pajic. Control synthesis from linear temporal logic specifications using model- free reinforcement learning. In ICRA, pages 10349-10355 2020.
[54] Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtezak. Omega-regular objectives in model-free reinforcement learning. In TACAS, pages 395-412, 2019.
[55] Sultan Javed Majeed and Marcus Hutter. On Q-lcarning convergence for non- Markov decision processes. In IJCAI, pages 2546 2252, 2018
[56] Dana Ron, Yoram Singer, and Naftali Tishby, On the learnability and usage acyclic prohabilistic finite automata. J. Comput. Syst. Sci., 56(2):133-152, 1998.
[57] Alexander Clark and Franck Thollard. PAC-Icamabilityy of probabilistic deterministic finite state automata. Mach. Learn, Res., 5:473-497, 2004.
[58] Nick Palmer and Paul W. Goldberg. PAC-learnability of probabilistic deterministic finite state automata in terms variation distance. Theor. Comput. Sei., 387(1):18-11, 2007.
[59] Borja Balle. Learning Finite-State Machines: Statistical and Algorithmic Aspects. PhD thesis, Universitat Politècnica de Catalunya, 2013.
[60] Borja Balle, Jorge Castro, and Ricard Gavaldà. Adaptively learning probabilistic deterministic automata from data streams. Machine Learning, 96(1):99-127, 2014.
[61] Edward Forrest Moore. Gedanken-exxprimentts on sequential machines. Automata studies, 34:129-153, 1956.
[62] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley Longman Publishing Co., Inc., 2006.
[63] Jeffrey Shallit. A second course in formal languages and automata theory. Cambridge University Press, 2008.
[64] Ronen I. Brafman, Giuseppe De Giacomo, and Fabio Patrizi. LTLf/LDff non-markovian rewards, In AAAI, pages 1771-1778, 2018.
[65] Maor Gaon and Ronen I. Brafman. Reinforcement learning with non-markovian rewards. In AAAI, pages 3980-3987, 2020.
[66] Andrew Kachites McCallum. Reinforcement Learning with Selective Perception and Hidden State PhD) thesis, University of Rochester, 1996.
[67] Jorma Rissanen. A universal data compression system. IEEE Transuctions on information theory, 29(5): 356-664, 1983.
[68] Dana Ron, Yoram Singer, and Nañtali Tishby, The power of amnesia: Learning probabilistic automata with variable memory length. Mach. Learn., 25(2-3):117-149, 1996.
[69] Marcus Hutter. Extreme state aggregation beyond Markov decision processes. Theor. Comp. Sci., pages
73 91, 2016.
[77]] Andreas Maurer and Massimiliano Pontil, Empirical Bernstein bounds and sample-variance penalization. In COLT, 2009.
[71] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement lcarning. In NeurlPS, pages 7713-5723, 2017.
[72] Thomas M. Cover and Joy A. Thomas. Elements Information Theory (2. Ed.) Wiley, 2006.
[73] Balázs Szörényi. Characterizing statistical query learning: Simplified notions and proofs. In ALT, pages 186 200. 2009.
13

---

[74] Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. STOC, pages 253-262, 1994.
[75] Sumegha Garg. Ran Raz, and Avishay Tal. Extractor eetractor-based time-space lower bounds for learning. In STOC, pages 1900,102, 2018.
[76] Sumegha Garg, Pravesh K. Kothari, Pengda Liu, and Ran Raz. Memory-sampll lower bounds for learning parity with noise. CoRR, his/2107.02320 2021.
14

---

Appendices
Extended Discussion of Related Work
16
A.1 Offline RL in MDPs
16
A.2 Online RL in RDPs
16
A.3 Non-Markov Rewards Reward Machines
16
A.4 State Representations
17
A.5 Feature MDPs and General RL
17
A.6 Learning PDFA
18
RDP properties
18
B.1 RDPs and Regular Policies
18
B.2 Markov Transformation
19
C Sample Complexity of ADACT-H
20
C.I Preliminaries
20
C.2 Proof of Theorem
C,3 Proof of Theorem 8
23
C.4 Distinguishability Parameters
26
RegORL with Subsampled VI-LCB
26
E Sample Complexity Lower Bound: Proof of Theorem 9
28
E.1 Learning parity with noise
28
E.2 Class of hard RDP instances
29
E.3 Proof of Theorem 9
30
15

---

A Extended Discussion of Related Work
Some of the related work mentioned in the introduction requires a more extensive discussion, which we provide below.
A.1 Offline RL in MDPs
There is a rich and growing literature on offline RL in MDPs; see, e.g., [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]. A closely related line of work is off-policy learning in MDPs [21, 22, 23]; we refer to the recent survey [24] for a discussion on how the various settings are related. For offline RL in MDPs, the papers cited above report learning algorithms with theoretical guarantees on their sample efficiency. The majority of these algorithms are designed based on the pessimism principle. While most literature focuses on tabular MDPs, the case of linear function approximation is discussed in some papers, e.g. [20]. In several settings, the presented algorithmss are shown to be minimax optimal. For instance, in the case of tabular episodic MDPs, it is established in [16] that the optimal sample complexity 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 policy.
A.2
Online RL in RDPs
RDPs have been introduced in [3] as a formalism based on temporal logic. They admit an equivalent formulation in terms of automata, which is favoured in the context of RL. Several algorithms for online RI. in RDPs exist [25, 26, 27] but complexity bounds are only given in [26] for the infinite- horizon discounted setting. This work [26] shows the correspondence between RDPs and Probabilistic Deterministic Finite Automata (PDFA), and it introduces the idea of using PDFA- PDFA-Icarning techniques learn RDPs. Their sample complexity bounds are not immediately comparable ours, due the different setting. Importantly, this algorithm uses the uniform policy for learning. So, the algorithm might be adapted to our setting only under the assumption that the behaviour policy is uniform. Even in this case, our bounds show an improved dependency on several key quantities. Furthermore, we provide a sample complexity lower bound, whereas their results are limited to showing that a dependency on the quantities occurring in their upper bounds is necessary.
The first RI. algorithm for RDPs appears in [25] for the online discounted setting. It is automaton- based, and in particular, it learns the RDP in the form of Mealy machine. The algorithm is shown in [26] incur an exponential dependency on the length of the relevant histories. An algorithm that achieves performance guarantees building on the techniques from [26] but also integrating an effective exploration strategy is given in [27]. This work also introduces the idea of seeing the transition function of a PDFA as Markov abstraction of the histories to be passed to an RL algorithm for MDPs, so as to employ in modular manner.
The algorithms in [28, 29, 30, 31] apply to RDPs even though they have not been developed specifi- cally for RDPs. Toro Icarte et al. [28] present an RI algorithm for the subclass of POMDPs that have a finite set of reachable belief states. Such POMDPs can be captured by finite-state automata, and are in fact RDPs. Their algorithm is based automata learning, but it does not come with analysis of its performance guarantees. The RL techniques presented in [29, 30) for feature MDPs are in fact applicable to episodic RDPs. The techniques are based on suffix trees, rather than automata. There are cases when the size of the smallest suffix tree is exponential in the horizon, while an automaton of linear size exists-see section below on feature MDPs. Thus their techniques cannot yield optimal bounds for RDPs. Mahmud [31] introduces an RL algorithm for Deterministic Markov Decision Models (MDDs). Such MDDs are also automaton based, and they are more general than RDPs since the automaton is only required to predict rewards. Thus their RL algorithm applies to RDPs. However, is an algorithm without guarantees.
A.3 Non-Markov Rewards and Reward Machines
MDPs with non-Markov rewards are special case of NMDPs, where only rewards are ManrMvaovian. Namely, observed states satisfy the Markov property, while rewards may depend on the history of past states. The specific kind of non-Markov rewards considered in the literature amount to the subclass of RDPs where the automaton's 's state is only needed to predict the next while the next observation (i.e., state) can be predicted from the last observation.
16

---

MonnMarkovv rewards can already be found in [2], where the reward function is specified in a temporal logic of the past. More recently, the setting has been revisited with so-called reward machines [44] as well as with temporal logics of the future on finite traces [64, 47]. A reward machine is a finite automaton (or transducer) used to specify a Markovian reward function. Reward machines have been introduced in [44] along with an RL algorithm that assumes the reward machine to be known. RL algorithms with unknown reward machine, or equivalently unknown temporal specification, are presented in [65, 45J, with no performance guarantees. Reward machines have been generalised so as to predict observations as well [28], which makes them equivalent to RDPs as mentioned above.
The first performance bounds for RL with reward machines have been recently established in [49]. The work shows regret bounds that take into account the structure provided by a reward machine, and hence improve over the bounds that one would obtain by naively adapting regret bounds for MDPs.
An automaton-bases method for dealing with non-Markov sparse rewards is proposed in [48].
A.4 State Representations
State representations are maps from histories to a finite state space. The map defined by the transition function of an RDP a state representation. The studies on state representations [39, 40, 41, 42] focus on regret bounds for RI. given candidate set of state representations. While in our case the state representations are concretely defined by the class of finite-state automata, in their case they are arbitrary maps. This is challenging setting, which does not allow for taking ad advantage of the properties of specific classes of state representations. The regret bounds in [39, 1, 42] are for finite sets of state representations, and they all show linear dependency the cardinality of the given set of state representations. In our case, the candidate state representations correspond to the set of automata with at most Q ((AO) " states and AO input letters. Such set contains at least QQA0 automata-the number of distinct transition functions. Thus, if we could instantiate their bounds in our setting, they would have exponential dependency the number Q of RDP states, and hence dependency on the horizon H. We avoid this dependency, obtaining polynomial bounds in the mentioned quantities.
Nguyen et al. [40] consider the case of a countably infinite set of state representations, and present an algorithm whose regret bound does not show a dependency such the one discussed above. Instead, they show a dependency on a quantity Kg, which admits several interpretations, including one based on the descriptional complexity of the candidate state representations. Thus, there may be way to relate Ku to the quantities we use in our bounds. However, the formal relationship between the two, if any, renders highly non-trivial, which prevents one use their ideas in the case of RDPs. We believe establishing a fomal relationship between their model and RDPs is an interesting, yet challenging. topic for future work. Furthermore, it should be stressed that even if the relationship was clear and one could borrow ideas from [40], the resulting sample complexity bound would have to grow as 1/E3 in view of their regret bound scaling as T2/3, In contrast, our bounds achieve an optimal dependency of 1/2² on E.
A.5 Feature MDPs and General RL
Hutter [29] introduces feature MDPs, where histories are mapped to states by a feature map. It relates to our work since the map provided by the transition function of an RDP a feature map. The concrete feature maps considered in [29] are based on U-Trees [66]. The idea is also revisited in [30] with Prediction Suffix Trees (PST') [67, 68). Both U-Trees and PSTs are suffix trees. There are cases when their size is exponential in the horizon, while an automaton of linear size exists. For instance, in the case of a parity condition over the history. To see this, note that a suffix x of a bit string bæ does not suffice to establish parity of bz. In fact, the parity of Oz is different from the parity of Ir. Thus a suffix tree for parity must encode all suffixes, and hence it will have a number of leaves that is exponential in the maximum length of relevant string- the horizon H in the case of episodic RL.
Hutter [69] provides several formal characterisations of feature maps. All the characterisations are less restrictive than the one defined by an RDP. In particular, their most restrictive characterisation is given their Equation (6). It only requires to preserve the ability to predict rewards, not observations- -thii is also adopted by Mahmud [31]. The states of our automata suffice to predict observations as well. It unclear whether automata techniques can be used to learn directly abstractions that not preserve the dynamics entirely.
17

---

Majeed and Hutter [55] study convergence of Q-learning when executed over the state space of an MDP that underlies a non-Markov decision processes. Such a state space corresponds the state space of the RDP, but they do not consider the problem of learning the state space.
Lattimore et al. [43] consider General RL the problem of RL when are given a set of candidate NMDPs, rather than assuming the decision process to belong to a fixed class. Similarly to the works on state representations, it does not commit to specific classes of NMDPs, and their bounds have a linear dependency on the number of candidate models. As remarked above, in our setting, it amounts an exponential dependency on the number of states of the candidate RDPs, and hence a dependency on the horizon; we avoid such exponential dependencies.
A.6 Learning PDFA
Our algorithms for learning RDP borrow and improve over techniques for learning Probabilistic- Deterministic Finite Automata (PDFA). The first PAC learning algorithm for acyclic PDFA has been presented in [56], then followed by extensions and variants that can handle PDFA with cycles [57, 58, 10, 59, 60]. All bounds feature some variant of a distinguishability parameter. which we adopt in our bounds, properly adapting state-of-the-art algorithm ADACT [10], and we derive bounds that are substantial improvement over the ones that can be obtained from straightforward application of any existing PDFA-learning algorithm to the offline RL setting.
the offline RL setting. Our algorithm builds upon the
B RDP properties
In this section we prove several properties of RDPs that are stated in Sections 2 and 3.
B.1 RDPs and Regular Policies
In this section, we prove Propositions and 2.
Proposition 1. Consider an RDP R. regular policy π E Il and two histories hı and h2 in Hu t E [H], such that F(h1) = F(h2). For each suffix 6141:H E EH-t-1, the probability of generating 6441: is the same for hı and h2, i.e. P(e++1:H h1, n. R) P(e++1: h2, n, R)).
H, all histories in H. generate the empty suffix in (ARO)O with probability 1 (the stop symbol is omitted). For t < H, the probability of generating suffix aroe++2:1 is
Proof. By induction on t. For t =
P(aroe+42:H h1, R) = π (h1,a) a) P((, F(h1), R) P(ee+2:H h100, x, R) =x(h,,a) a) PP(, F(h2), a, R) P(er42:H h2ao, n. R) P(aroe(42.H 122, n. R),
where we have used the fact that æ is regular, F(hı) = F(h2). F(hqao) = r(F(h1), T(F(h2), ao) F(h2a0), and the induction hypothesis.
The following statement appears in the literature [3, Theorem 2], but the authors do not provide a complete proof, so for completeness we prove the statement here.
Proposition 2. Each RDP R has at least one optimal policy πt E 1lR-
Proof. Given R, consider any optimal policy x² H + (AA), not necessarily regular. We prove the statement by constructing a policy ग and showing by induction on / E [H] that π is both optimal and regular. The base case given by f H. In this case, for an arbitrary each history h E H. Since V (h) = O by definition, is optimal for each history h E H.. and regular since always selects the same action.
A, define T(h) == 1, for
For t < H, we first construct a new policy मe which is the composition of policies T" and и. Concretely, for each history h H. such that u < t, Te( x² (h) acts according to x², while for each history h E H. such that u > t, (h) = T (h) acts according to т. Clearly, Te is an optimal policy for R since =² is optimal and since by induction, x is optimal for histories in H., u >
Consider a pair of histories iy and hy He such that F(hn) = F(h2) but ne(hi) * me(h2). Define (hi) = x(h2) = Te(h)). Since the value function can be written expectation
18

---

over suffixes, due to Proposition 1 and the fact that is regular for histories in Hus u > t, we have V. (h1) (h2)) Since Te is the same as π for histories H..
t, this implies (h1) = (, < (h2) since Te is optimal for h2- If we were to instead define π T(h1) (h2)) == Th (h2), we would obtain (Tr((h2) S V?>((h)
The only possibility is (h1) = (h2), which is the same value achieved by the policy л. Hence ı is optimal for h1 and hg-
We now repeat the same procedure for each pair of histories h and fig in Hi such that F(h1) F F(h2) but (ha) A Te(h2). If necessary, we complete the definition of π by copying the action choices of TT. The resulting policy и is optimal for each history h E Hr, and regular since makes the same action choices for each pair of histories h1 and h2 in h E Hi such that f(h1) = F(h2).
B.2 Markoy Transformation
In this section, we verify the properties of the Markov transformation, which is the intermediate step that RegORL uses to recover the Markov property in the original dataset. This transformation has been formalized in Definition 2. We use D and D' to denote the original and the transformed datasets, respectively.
Proposition 3. Let eo:H be an episode sampled from an episodic RDP R under a regular policy E IRR, with Th, a) = m,(F(h), a). If e is the Markov transformation of eg with respect to R, then P( R,,)) P(C MR. T,), where MR. is the MDP associated to R.
Proof. For t E [H], let e, E E = (ARO)--1 be an episode prefix in R. d(ez) E E (ARQ)(+ be its Markov transformation and e₁ E & be an episode of the associated MDP. The function Ø E E" transforms the observations according to F, and preserves actions and rewards. The statement says that P(ó(e)) R. = P(e;, MR. π,) (note that ((e) and ef are distinct random variables). We prove this by induction. For t O, we recall that the irrelevant quantities ap, Tn constant and,
P(á(aarooo) aorog R, π.)
Σ
T(T(go, ago) = 4) (o(10 4o, o)
oEO
= T(qo ao q)
= -Pcc = agrol MR. T.)
where T: Q A - ((Q) is the transition function of MR. from Definition 3. Due to the role of the dummy action, (gqu, dn) is the initial distribution of the MDP.
For the inductive step, assume that PP(((e,1)) R, x) = P(L- MR. m.). Then, for any e' E E/
arq E ARQ, if o' is the last element of e', we have
P(ó(ez) = e'arg R R) ((((e--1) = = R, T) P(arr:4411 arg ((()-)) =E, R,
(5)
= =P(E'-1 = MR, T.) P(are:t+ arg ae of R, T)
(6)
= =P(e--1 = e' MR, n.) (1', a) 0r(g', a)
Σ 0old'' a, o) I(g = -((',a0)
(7)
OEO
-P(C = e' MR, m. (d , a) 0,(g', a, a,))
(8)
= =P(e, e' arq MR.
(9)
where, in (6), we have used the induction hypothesis and the fact that 0c7:4441 are Markov in q' by regularity of the policy.
Thanks to this relation, the values of corresponding policies are also related in the following way.
Proposition 4. Let E IR be a regular policy in R such that π 7(, a) (T(F()) Then E[ViT = E. V.V. Mg where Von and Vo,Mg are the values in the respective decision process, and E[VRR = E E Mg. where expectations are with respect to randonness in
OR = E which is Proof. The statement is composed of two parts. First, show that E[
direct consequence of Proposition 3. Following the same convention in the proof of Proposition 3.
19

---

we use E = (ARQ)(+ and Φ for the Markov transformation. Then,
11
EIVVRl
Σ
P( -1 ...HH
R
Σ
(10)
i=1
H
Σ P(o(eH)= = R, |
Σ
(11)
e'EEg
im
H
Σ e'ECH
P(c' e' MR. TT)
Σ
(12)
i=1
E 0.MR
(13)
For the second part of the statement, let I. and IM be the regular and the Markov policies in R and MR. respectively. Then, using Proposition 2 and the first part of this statement,
max E O,M. Vo,Ma VO.R max V.V.Rl max [V O.MR x.llll
(14)
sellR
rEllR
Corollary 5 is a consequence of the two parts of Proposition 4. Since VO U, and the value achieved by the optimal policy in the respective model is the same, e-optimality of a in R implies e-optimality n, MM. and vice versa.
C
Sample Complexity of ADACT-H
In this section we prove high-probability upper bounds on the sample complexity of ADACT-H.
C.1 Preliminaries
We first state Hoeffding's inequality for Bernoulli variables. In what follows we take log to be the natural logarithm.
Lemma 10 (Hoeffding's inequality). Let XI...., Xx be N independent random Bernoulli variables with the same expected value [[[x]] and let PN = E X./N be an empirical estimate of Then, for any d E (0, 1).
log(2/0)
IP pN
< 6.
(15)
2N
An alternative to Hoeffding's inequality is the empirical Bernstein inequality, which can be expressed as follows for Bernoulli variables [70, 71].
Lemma 11 (Empirical Bernstein inequality). Let XI,...,NN be N independent random Bernoulli variables with the same expected value [[[1]] p. and let PN En X./N be an empirical
estimate of p. Then, for any 10,
26 2plog(4/0) 14log(4/8)
P
pNN pl
88.
(16)
N
3N
If X px is discrete random variable, the entropy of X is H - - Px
log
Further. for x E (0, 1), we define the binary entropy function Hz(x) -I log(r)
Pxy are two discrete variables, the conditional entropy H(Y X) EmEX (x) H(Y X = r). The mutual information is T(X;Y) = X))
x:) log(1 r). If (X.Y)
(RI(PXY || Px PY), where DKL is the Kullback-Leibler divergence. If X, Y, Z are three random variables, we write X Y + Z if the conditional distribution of Z does not depend on X, given Y. With these definition, we state Fano's 's inequality, as one can find in Cover and Thomas [72]. (40).
Theorem 12 (Fano's inequality). Let X + Y + X, for X, X E X and Pa = P(X + X). Then, Hz(P.) + P. log(l - 1) 2 H ((X Y).
(17)
20

---

C.2 Proof of Theorem 6
In this section we prove Theorem which states a high- sish--robbbblityy upper bound on the sample complexity of ADACT-H. The first two lemmas are adaptations of Lemmas 19 and 20 in Balle et al. [10] to the episodic setting.
Lemma 13. For [H], let X1 and X2 be multisets sampled from distributions pt and p2 in A(EH-111). P1 P2, then TESTDISTINCT(t, N1, N2. 6) returns False with probability 1 - ô.
Proof. For each E [1,2] and each trace - we can view each episode as random Bemoulli variable with expected value pi(e) that takes value if we observe e, and 0 otherwise. Let Pa(e) = ExEx, [[ = e)/|&g be the empirical estimate of pt. i.e. the proportion of elements in Xr equal to e. For each {1,2), 2}. each a E [H -t 1] and each prefix co.u En, Hoeffding's inequality yields
log(2/5g)
P
ps (e *) Pa (e +)1
85.
2|X,|
The total number of non-emply prefixes of EH-1-1 equals a geometric sum:
(ARO)' + .... (ARO)"-1= ARO - 1
1 ((ARO)"-,
Choosing dş = 8//(AAR))"-+ and taking a union bound implies that the above incquality holds for each i E {1,2} and each ep:,. simultancously with probability 1 4(ARO) -t = - 6, implying
(2gg)
(2g()/
L.. (2) max (conu*) ) S LP (p1.Pe) +
u.e0.u
2/
2/
log(2/6g) 5 2/ 2 minn[XXl, [22))
2 (OAg()
min( [1 (211
which is precisely the condition under which TESTDISTINCT((, Xi, X2, 0) returns False.
Lemma 14. For [H]. let X1 and X2 be multisets sampled from distributions pi and Pa in A(En-t-1) the & di-dditiinguihaabiltt of xD is pu, then TESTDISTINCT(t, X1, X2, 8) returns True with probability 8 provided that
8 pg
min(|23], (22))
(bo{(((AR))**) log(4//))
Proof. Using the same argument as in the proof of Lemma 13, Hoeffding's inequality yields
log (2g(2/))) 2|
P 1.. *) Pe(Curu +)1 >
S 8g.
with the inequality holding simultaneously for E (1, 2} and each prefix ep.u with probability 1
by choosing & = 5/4(ARO)) H- Choosing Ho 2 4 /11o((2/8))/2 for each E (1, 2} yields
x > min 1,11) 2 log(2/6)) = (1og(((ARO)* + log(4/6)).
8
8
In this case have
log(2/5.)
log(2/8))
L8 L% (2,,,,
max (e) Pz(e)) > LB P2),
a,ean
2//4
2//6z|
log(2/5))
2 llog(8 ((AR)) min([X]) (22))
140
440
140
2
140
min
1,121
which is precisely the condition under which TESTDISTINCT(t. X2,
8) returns True.
21

---

We are now ready to prove Theorem 6, which we restate below:
Theorem Consider a dataset DD of episodes sampled from an RDP R. and a regular policy Th HR- With probability 1- 6, the output of ADACT- HDD,-H(D,,))) H(D,8/((QAO) is the transition function of the minimal RDP equivalent to R. provided that [D] N N6, where
N8 (1QA08))
H
V H (2ggO2 Eō
d P4
donin Po
db dinin == min(fd) q. ao) t E [H], E Q1,ao E AO, di (g. ao) > 0f is the minimal occupancy distribution, and po is the L -distinguishabiityy
The proof consists in choosing N and such that the condition in Lemma 14 is true with high probability for each application of TESTDISTINCT. Consider an iteration & E [H] of ADACT-H For candidate state goo E Qc,r+ its associated probability is di (g, uo) with empirical estimate Pe (g(a)) = [ggo))] //N, i.e. the proportion of episodes in D that are consistent with qao. We can apply the empirical Bernstein inequality in (16) to show that
Proof.
2pr 2pi(qao)e
14f 3N
V2ME+ + 148/3
P [i((q0)) (g 2
S
N
N
where M = |x(gaO)), e = log(4/8), and 5 is the failure probability of ADACT-H. To obtain a bound on M and N, assume that we can estimate dl (q, ao) with accuracy di (g, /2) which yields
(g. ao)
V2Me+ + 148/3
(18)
2
N
V2ME 148/3 2 di ao)
(gq.ao)
di (q,
Do (guo) 2 (g ao)
(19)
Combining these results, obtain
N M = (goo)) 2 (d)(q.
(V2ME- (2ME+140/3) = (V2ME + 148/3) 2N
(20)
Solving for M yields M 2 46, which is subsumed by the bound on M in Lemma 14 since po < 1. Hence the bound M in Lemma 14 is sufficient ensure that we estimate dg ao) with accuracy di /2. We can now insert the bound on M from Lemma 14 into (18) to obtain bound on N:
2MM + 148/3)
28
H t) log 2ARO
14
N 2
+ 1 1
= NN.
(21)
di (g)
di (g. ao)
140
3
To simplify the bound, we can choose any value larger than Ni:
2
4 VH log(2ARO) + H log((AR + 3po
14
N1 v
VH (og(2
(g ao)
21
Hog(2ARRO) = No,
(22)
db 110
where have used (g,, a0) > db uuin 1o 1, log 4 log(1/5) 2 1, H log(2ARO) log 1 and 4/2 +4/3 < 21 Choosing 8 = 60/ 6Q/2QA a union bound implies that accurately estimating db (q, ao) for each candidate state qao and accurately estimating p(E).=)) for each prefix in the multiset {(qao) associated with qao occurs with probability 2QA08 = 1 - dg. since there at most QAO candidate states. Substituting the expression for in No yields 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 Qu, which is clearly minimal since it only contains the initial state qu- For t E [H] assume that the algorithm has learned a minimal RDP for sets Qo...., C.. Let Q++1 be the set of states at layer + 1 of a minimal RDP. Due to Proposition 1, each pair of histories that map to a state ge+1 E Q++1 generate the same probability distribution over suffixes. Hence by Lemma 13, with high probability TESTDISTINCT( X' (quo), X('' o') 5) returns false for each pair of candidate states gao and d'a'o that map q++1. Consequently, the algorithm
22

---

merges gao and da'o'. On the other hand, by assumption, each pair of histories that map to different states of 24+1 have L -istinguishability μo- Hence by Lemma 14, with high probability TESTDISTINCT(( (((o)) (qao), ('''a''),, returns true for each pair of candidate states qao and q' d' that map to different states in 2(+1- Consequently, the algorithm does not merge qao and g' d'o'o. follows that with high probability, ADACT-H will generate exactly the set 1++1, which is that of minimal RDP.
C.3 Proof of Theorem 8
In this section we prove Theorem 8, which states an alternative upper bound on the sample complexity of ADACT-H. The proof requires an alternative definition of the algorithm, which we call ADACT- H-A (for "approximation").
Theorem 8. Consider a dataset D episodes sampled an RDP R. and regular policy Th RR With probability 1 - 6, the output of ADACT- H-A, called with DD 3/(QAO) and & E (0, H. in input, is the transition function of an e e/2-approximate RDP R', provided that [D] 2 No., where
N₂ 50AHQAOCK log(16QA0//))
/ logg(RA) e
E Ho
E 140
Function ADACT-H-A(D, 8, s, 0.)
Input: Dataset D, failure probability 0 < 5 < 1, accuracy e, upper bounds Q on 22'l and C on Ci:'
Output: Set Q' of RDP stales, transition function r': Q' x *AO- - Q' of an approximate RDP R'
L + {qo). (go) t
// initial state 1/ initiaa side state
% Q U [g6]. x(6) +
for t
0,.... H do
2++1 + {
// side state // get candidate states // compute suffixes // most common candidate // promote candidate 1/ remove from candidate states Similar + ld E C.+1 not , if Similar 0 then U'+1 +- Ce+1 U (qao). (q. ao) quo 8)}
foreach ao AO do (' ao) = gf+1, X(((+1) (e441. arre141.M x()))
Ce.411 < [qaa] | E L2 ao E AO)
foreach gao 2e,4 do X(g0o) t (e++1:H/ arre141. E x()))
@mlmmmm f- arg maxpaoe 0 1111 [ggo))
2++1 + -1+1 mm. T (Zm, ammm) = 4m0m Om
10
Cd t 22,441 \ [m
11
for qoo E 21 such that (X(gO))|/N 2/CQAAHHC) do
12
// confidence test // promote candidate // merge states
14
else o' <- element in Similar, r'(q, ao) = (44)) < (44)) (gaoo
15
if 16 +.. + > Q then return Failure end
16
17
for
qoo E Ce,,+1 such that [X(gO))\/N <e/(AQAOHC) do T' r'(q, ao) g. (((++) X(g++) U (ggoo)
18
// merge with side state
19
end
end
21
return 0 U...UU Cutu
Proof. ADACT-H-A returns the set of RDP states Q' and transition function r' of an approximate RDP R', taking as input the accuracy 8, an upper bound Q on [Q'), and an upper bound C on the concentrability Cit of R'. If, at any moment, the number of RDP states Q'l exceeds Q, the algorithm returns Failure (line 15). ADACT-H-A defines sequence of side states 46.... ... fir+1 (lines 2 and 4), and defines r'(gf, ao) L. for each t E [H] and ao E AO (line 5). For each candidate state quo E Qe,44 such that (Xga))//N =/AQAAHHC) the definition of ADACT-H-A is the same as that of ADACT-H, including the call to TESTDISTINCT (lines 11-14). For each candidate state qao E L. such that (quo))/N < <OHC)CAOHC), instead of mapping (g, ao) to the correct RDP state, ADACT-H-A maps (g, ao) to the side state 4 (lines 17-18). Once z.41. R' remains in side state for the rest of the episode. The side states do not satisfy Proposition 1, since the
23

---

histories that map to side states may assign different probabilities to suffixes (and TESTDISTINCT is never called).
We define an alternative occupancy measure d' ao) associated with the approximate RDP R' and the behavior policy T². The new definition is given by dg (g0. aooo) = 0000 ao, oo) and
a(o;)== a())=)))))
Σ (9,00)Er'~(a)))
d ao) x (qe, a1) ) (o az, oz). t > 0.
The only difference between d' and de is that d' is defined with respect to the transition function r' of the approximate RDP R', instead of the transition function associated with the original RDP R. Note that apart from the side states, states satisfy the condition on line 11, and r' will be the same on those states. Since the states and behavior policy are the same, the L distingishaaiiity Ao of R' will be the same as that of R.
will contain the same states as R, as long as the candidate
First consider each candidate state qoo E Ce,t1 such that |X (ggo)) I/N 2 E E/(QQAOHC). In this case, ADACT-H-A calls TESTDISTINCT, so Lemmas 13 and 14 apply to these candidate states. Hence the
The associated occupancy (g, ao) with empirical estimate (e = [gaa))) empirical Bernstein inequality applies to (g, 0o) and (e(ga)). Just as in the proof of Theorem 6, we choose (qao) large enough accurately estimate d' (g, ao) within factor dg a0) with probability 1 - 5. We thus obtain an alternative upper bound on d2 ao) as follows:
[[(qa)) N
d'(g, ao)
3d ao)
[((qa))
(g ao) 2
N
AQAOHC
From here, we can use the proof of Theorem 6 by substituting d' for di up until the definition of the bound N1 on [D] in (21). Inserting the bound on d' ao) into the expression for N1 yields
28
14
N1
V log(2ARO) + H log(2ARO)
v H log(2ARO)
dg 0o)
3400
126QAOHCE
H Mlog(2ARO)) = N2-
(23)
E/0
Next, consider each candidate state gao E Le,41 such that |/(g0)) < <e/(AQAOHC), this case, we instead choose X (guo) large enough to estimate d'íq, ao) with accuracy 3 with probability
1 - 8. From the empirical Bernstein inequality, estimating dy ao) with accuracy 3 implies
148 N
28
14
Pc(ga))
= =N3.
N
3N
3
B
Choosing 3 = =/ implies Pe(aa)) 3, and can thus simplify N₃ as
N3 8 Fe(gao)
2 14
12f
48QAOHCL N4-
(24)
B
In addition, this choice of (3 yields the following bound on dz(4, ao):
d/ ao) (gao) +
4QAOHC 4QAOHC 2QAOHC
We prove that R' is an /ppapoixxin of the original RDP R. We briefly overload notation by letting di (q, ao) refer to the occupancy of optimal policy x" with respect to the transition function r' of R'. Consider candidate state qao E Q' 241 such that (A(gu)) < 8/ e/(4QAOHC) The contribution to the expected optimal reward of R of histories that map to quo is bounded as
/
di (g. (H < CR (g Ho)
2QAO'
since (H -t- 1) the maximum reward obtained during the remaining time steps. Since qao mapped to side state of R', an optimal policy for R' may not accurately estimate the expected optimal value for qoo, but the contribution of all such candidate states to the expected optimal value most
ΣΣX Σ -E]H-I a0EAo
(0) -) 1)
Σ 1E 1] Q aoEAO
Σ Σ
S
E
2QA0
2
24

---

since there can be at most QAO such candidate states. Hence any optimal policy for R' is an e/2-optimal policy for R. which implies that we can approximate an e-optimal regular policy for the exact RDP R by finding an e/ e/2-optimal policy for the approximate RDP R'.
It is easy verify that the bound N4 in (24) is less than the bound N₂ in (23). Hence worst-case bound is obtained by assuming that | (ggo))//N 2 =/(QQOHC) for each t [H] and each candidate state quo E 22,++1 which yields an upper bound N2. Note that ADACT-H-A takes as input upper bound Q on the number of RDP states |Q'| of R', well upper bound C' of the concentrability coefficient CR. If the learning agent has no prior knowledge of Q and C, it could start with small estimates of Q and C. and in the case that ADACT-H-A returns Failure the resulting policy has larger concentrability than for R', iteratively double the estimates Q and/or C and call the algorithm again. This only increases the computational complexity of ADACT-H-A by a factor Ollog ) and the resulting upper bounds Q and C' do not exceed 2Q and 20 Since we already have an estimate Q. in each iteration we can call ADACT-H-A with 8 (2) to ensure that the bound N2 holds for each candidate state simultancously with probability 1 d1. Substituting this value of 8 in the bound N2 (23) and using Q 2Q and C 2C's yields the sample complexity bound stated in the theorem.
Lemma 15. The concentrability CR of the approximate RDP R' satisfies
CR S CR CR(+1
Proof. For each t > 0, let (2)) be the occupancy of the side state of in the approximate RDP R'. prove by induction on / that d' (gf) satisfies
=1 Qul
d(qf)) <
8 2HC
2QHC
The base case is given by --1.=11 1. In this case, candidate state (go, ao) is mapped to of if di (go, ao) (1o, ao) < <e((2QAOHC). Since there can be at most AO = 1Qol AO such candidate states, we have
AQ ElQ
d( < 2QAOHC 2QHC
For 1, a candidate state (q--1a00 ao) is mapped to of if d4(ge-1, uo) < <E/1QAAOCC Again, there can be at most IQ--1/A0 such candidate states. Since all occupancy of gf is also mapped to Le have
c eiQ-1AA0
-1-2 Qu w=
eQQ--1
E1- Qa
d((1 < <.
2QAOHT
2QHC
2QHC
2QHC
where we have used the induction hypothesis.
Consider a candidate state (g, ao) of R. at time Due to approximation, some histories in 7 (4) are mapped to side states in R' instead of q, and can therefore write de (q, ao) = dz ao) { <
dg ao) - (g))), where is the total occupancy of histories in F-)(g) mapped to side states. In turn, this implies
(0) & (e(g,,0) S (d'(g, + d(()))R < (d/gg,
2HC CR )C.
The concentrability of candidate state (q,a0) ao) in the approximate RDP R' that is not mapped to side state (i.e. d'(g, ao) e/ (/(QAOHCC) can now be bounded
di (g,,a0) ao) (' ao)
d' ao) + (2(1II
CR (1+ 2HCd, 00) )
S 3QAO).
a0)
This concludes the proof of the lemma.
25

---

C.4
Distinguishability Parameters
As defined in the main text, for 1 E [H], we consider a metric over distributions on the remaining part of the episode ((Ex), for l = H -L. Then, the L-distinguishabiiity of an RDP R and policy the maximum Me such that, for any 1. E [H] and any two distinct q, q' E 22, the probability distributions over suffix traces Ct:H Eg from the two states satisfy
L(P(CEH q: 9. P(e. 1/ q x)) 2 pu
(25)
So, (og is a feature of the RDP and the policy combined and it quantifies the distance between any two distinct states of the RDP with respect to the distributions they induce over the observable quantities. Distinguishability parameters have been first introduced in Ron al. [56] and later generalized for other metrics. They can be also found in Balle [59] for PDFA learning and in Ronca and De Giacomo [26), Ronca al. [27] for RDP learning.
According to the definition we adopt, there exists an L-distinguishabblity for any RDP and policy. However, as stated in Assumption 2, we require (40 to be strictly positive. This does not constitute restriction for the RDP, since it can be always minimized while preserving all conditional probabilities. Though it implies that, in any state, the behavior policy takes with positive probability all actions that are needed to observe episode suffixes that have different probability under the two states. Clearly this was not the case for two distinct q, q' E Q some E [H]. P( 9: q. TT) P(et. 9 q', T and no information would be available for the algorithm to distinguish and g'. Assumption 2 implied by Assumption 1. However, it becomes necessary for Theorem 8, since this does not rely on Assumption 1.
The metric selected also influences the actual value of the distinguishability parameter. In this paper, we adopt LPc, as can be seen from the TESTDISTINCT function in the two algorithms. A more standard distance would be L. According to Eq. (25), an Lox -iistinuuisaability of po implies that for any & E [H] and two distinct q, q E Qt.
[P( = e qt =4) - P(e.n =e a: = =0') no- εεÊH
max
(26)
This means that some sequence until the end of the episode has a different probability of being generated from the two states. Although similar, the LP distance, maximizes for the full trace as well as any of its prefixes as
max EE
1 [P(C. = = q -) - -((C = c*
q: |
d')l po
(27)
As it has been discussed in Balle [59], Appendix A.5, the prefix LP metric always upper bounds the Lizo metric, up to a multiplicative factor, while there are pairs of distributions in which L is exponentially smaller than L% with respect the expected suffix length. This motivates our choice. Moreover, in the specific case of our fixed horizon setting. we have that the LG distinguishabblity is never lower than Loe -distinuiihaabiitty Note that in the hard instance of Appendix E.2, the two coincide.
The lower bound is stated in terms of the I,P fi-diiiinuuisaabiiityy of the RDP. While T.P. is achieved for one specific trace prefix maximizing the difference probability. I. takes all traces into account as _ne(H_ [PP(e.. IPPe,, e* &t q) P(e.. e* q: = Due to this relation, the T.g. distinnuuishabiltty always lower bounds the T. distinguishability in the fixed horizon setting.
D RegORL with Subsampled VI-LCB
In this section we demonstrate the composition of our proposed algorithm with a specific Offline Reinforcement Learning algorithm for MDPs. Specifically, we adopt Subsampled VI-LCB, from Algorithm 3 of Li et al. [16] and report the combined sample complexity of this choice, through a simple application of Theorem 7.
First, we introduce the occupancy distribution and the single-policy conentrability coefficient for MDPs. Let M- = (Q, A. R, T, R, H) be an MDP with states Q, horizon H, transition function T: Q x A + Q and reward function R: Q x A + A(R). The state-action occupancy distribution of a policy π: Q + A(A) in M at step t [H] is e a) P(g: g. a = a M, T). For our
26

---

purposes, it suffices to consider fixed initial state qo. Finally, the MDP single-poligg concentrability of policy n² is [15]:
m a)
C
(28)
oE d (g: a)
We can now express the sample complexity Subsampled VI-LCB.
Theorem 16 (Li et al. [16]). Let 'D be a dataset of Nm episodes, sampled an MDP M with 1/12, with probability exceeding 6, the policy ßt returned by Subsampled VI- LCB obeys Vg (go) VØ (go) S E, as long as:
a Markov policy x². For any & E (0, H] and
Nm 2 cH log N.H
(29)
for a positive constant c.
The analysis in et al. [16] of Subsampled VI-LCB assumes that the reward function is deterministic and known. Thus, restricting our attention to this setting, we consider any episodic RDP with history-dependee deterministic rewards. The reward function can regarded as known, since may be easily extracted from the dataset resulting from the Markov transformation of Definition 2.
Corollary 17. Let 'D be dataset of N episodes, sampled with regular policy n Tn from an RDP R with deterministic rewards. If Subsampled VI-LCB is the OFFliNERL algorithm in Algorithm 1, then, for any (0, H) and 0 <, 8 < 1/12, with probability exceeding 1 5, the output of RegORL(D, E, 8) is an e-optimal policy of R, as long as
21 log(8QQA//) V log(2R
cH*QCR log g2
2NH 5
N > 2 max { db Ho
(30)
Proof. This corollary follows as a direct application of Theorem 16 Theorem 6. It only remains to verify that the single-policy concentrability of the MDP underlying the dataset 'D' that Subsampled VI-LCB receives CR. The dataset D' generated according the Markov transformation from Definition 2. We only consider the cases in which ADACT-H succeeds. Let E IR be any regular policy and (t, %f the states reached at step by R and MR. respectively. Then for 0,
di (q, a) P(ur 4 R. T) (1, (F(((h,1)) = g R, R) mr(g, a) P(4 = g MR. m,) mr(g.a) a) (4,
(31)
(32)
(33)
(34)
This is valid for any regular policy, and for the optimal and behavior policies in particular. Then,
dj (g. 0o)
CR
(35)
a00 di (g. ao)
d (q.a) 0o 0, LE[H].gEE...o. a0 de (g 0o (1, 0.
max
(36)
(g)
(37)
rE(H1), 0i.49,0
C
(38)
Similarly to the previous corollary, it is also possible to combine Theorem 16 with Theorem 8. In this case, the sample complexity Subsampled VI-LCB for learning an e/ e/2-accurate policy with probability 1 - 6/2 would be combined with 8/2 of Theorem 8.
27

---

E Sample Complexity Lower Bound: Proof of Theorem
In this section, we prove the sample complexity lower bound in Theorem 9. The proof is based on suitable composition of a two-armed bandit and an instance of the learning problem associated to noisy parity functions. We first describe this latter problem and its sample-complexity lower bound in Appendix E.I. Then, we compose hard class of RDP instances in Appendix E.2, and prove the final statement in Appendix E.3.
E.1 Learning parity with noise
Let IB {0, 1) and L N. For any string x E IB,, the parity function fz BL - B (n
Bie 1j where @ is addition modulo 2. For noise parameter & E (0,0.5), a noisy parity function ʃz,ş returns (u) with probability 0.5 + & and 1 fa(y) otherwise. Consider the class of (ea) and the class of noisy parity functions [T,,,
( Assume that F, V1, 12. ... uni are uniformly sampled. The success probability of streaming algorithm 2 for F(L, E) is the probability that 21 recovers I, given in input sequence of observations (yis (1:)))
parity functions F(I.)
Lemma 18. Any streaming algorithm for F(L,E) E) with a success probability higher than 0(2-1) requires at least ((L/E) or 20(1) input samples (a.ff.(())))
Proof. Learning in (F(LE) is the problem of recovering x E 2 from noisy data (yi, b,), where b; = fz(M)) with probability 0.5 + E, and 6; = - (mx) otherwise. This is the problem of learning in IL) with corruption rate 0.5 - E. Hence, we focus on the problem learning noiseless parity first.
The Statistical Query dimension SQDIM(C, d), characterizes the complexity of learning in the class C with respect to the prior distribution d E AC)). As defined in [73]. SQDIM(C, d) is the maximum n N such that there exist distinct f1, .i..... fn E C, such that their pairwise correlations with respect to d are between -1 -1/n and 1 1/n. For the class of parity functions, under the uniform distribution over x, (FL), unif) 2 This was already observed in [74], for slightly different notion of SQ dimension. However, to verify this, we can consider a natural ordering over binary strings in
matrix M (min (1, (1,-1)2 x2" defined as m,j = (-1)(a,(ou) = (-1) where scalar product is modulo 2. We have that M is a Hadamard matrix. Then, since every row is orthogonal to the others, and the same is true for columns, every couple of parity functions are uncorrelated under the uniform distribution over sr
X, and represent the problem of learning (T.)
Regarding the noisy parity problem, since SQDIM [.), unif) 24, we can apply Corollary 8 of [75] with m = 2 to have that the matrix M corresponding to the parity problem is a (k: ()-L2- extractor with error 2 for k, G, E Q(L). Since M is suitable extractor, we can apply Theorem I of [76], which considers the problem of learning M with the additional noise parameter ç. We obtain that, in the streaming setting, any branching program for F(L, whose depth is at most (k...r and width is at most 20kl/E has success probability of at most 0(2 (22-11())))) where e is a suitable constant and fi is equation (1) of [76].
Then, the success probability is not in O(2- ((2-51(A4))) meaning it is higher, we have that the depth of 21 exceeds 2 (k...r) or the width of 21 exceeds 20k//E Since k. L, E Q(L), then, if the success probability is not in O(2-=), the depth of 2 is 20(E) or the width of 2 is 20(LP)/E Width and depth refer the computational model that represents 2 as a branching program. A branching program is a directed acyclic graph in which internal nodes have one outgoing edge for each possible input sample, that [B² x B = 24+11 in our problem, and leaves correspond to algorithm decisions. From the required width and depth we know that Q has a leaf in layer 20(L) or in a layer that contains 20(L2)/E nodes. The former case implies a worst case sample complexity requirement that is exponential in L. For the latter, we observe that in order to reach that width, at least loggz-1 28(L2/E) transitions and input samples, are required. This is (LLE).
D
28

---

d1 1i-
14
24
+.5
1
111
1o
M-11
ag V-t ai Rig
1h1
giva
yba
+
dp.00 2g 41 41-
Figure 3: One episodic RDP instance R101.1 E R,3,5, 7),, associated to the parity function f1o and optimal arm of. The transition function represented by the ares, labelled by observations (transitions do not depend on actions). The star denotes any symbol. If the label of a state is a.d, then the observation function is (.(g. a) d, where d A(O) (some irrelevant outputs are omitted).
E.2 Class of hard RDP instances
For main lower bound, define class of hard RDP instances. Figure shows possible instance in this class. We will soon define it formally, but we can observe that its structure is organized in two main paths. The hidden code x E IB,, so that behaving optimally in that region requires to solve a parity problem (the one of Lemma 18). The bottom part reaches two-armed bandit whose optimal action is c. The right-most states are winning or losing states that provide a positive and null reward accordingly.
branches in the top part encode a parity computation according some
Formally, define class of hard RDP instances R(L, H,E, (Rz,) cE((..) where Rr,c (Q, AO, Ω, r, 0, qs H), for Q {ya: 9o1 (uus 4is (=i).=...... A = { /. O = {0, 1, +. }}. Assume 2 and > Rewards are zero everywhere, except in the winning states
0. a, = 1, q q+o with > I., 1o, otherwise
(39)
where we recall that 1, represents the deterministic distribution on For observation probabilities, denote the distributions u(o)= == unif {0, 1} and
if
1/4 if 0
Cx (o)
if otherwise
s(0)
1/4 ifo
(40)
1/2 of +
Now define observations
8(0) u(o)
if q = qs if q E {Tos, Qii ) i=1....,.1
(e(
if q = for A a or q Qır A a = d'
v-e(o)
if fol A al or g qol
8o a.
(+)
if q qui with < L
(41)
(o)
if = dbl A a = d'
(0) if q&L A dí A Ac=1
(0) if IbL A df Ac=0
(0) if q 9o..
Finally, the transition function is defined such that 7(gs, 11 ( 9r with i f= 1), and
T(y,L, a+) = 4+.
T(UeL, a-) = 9-1b+1
for k = 1,2
(42)
T(bb, = 4+.
T(bb,, = 99-6+1
(43)
29

---

T(9+s, ao) = 4+,541
T(q-;, 00) = 9-,5-1
(44)
T (4s, a+) = qb1
((hi a0) 96,i+1
for i
(45)
T[ ao) = fo1
{q- 00) = fou
7( a, 0) = qau
(46)
In addition, the trnasitions (gos, ao) and ((9i;, ao), for i < L, are defined according to {0, 1] and the parity code I. Namely, (qui, ao) equals 41,++1 iff o @ x(i) = 1, and g0,5-1, otherwise. T(11;,0) a0) is defined analogously.
E.3 Proof of Theorem 9
Theorem 9. For any (Ci, E, po) satisfying CR 2 an RDP with horizon H, Li-distinguishaabiit po and a regular behavior policy Hb with RDP single-policy concentrabilityy Cn such that if has been generated using n. and R, and
H and S HHpo64, there exists
(M
H
CR
D $ Q
E2
then, for any algorithu 2 D D āे returning non-Markov deterministic policies, the probability that f is not e-optimal is at least 1/4.
Proof. Denote with nb a regular policy in R and D E DD a dataset of episodes of length H, collected from R and the behavior policy 75. For RDP R. let IIa = A be the set of deterministic non- Markov policies and 2 = D - IIa an offline RL algorithm. For < 0.5, we say that an algorithm 2 is (e, PA- for the class of RDPs R under y, if, for every R. E IR and D E D. if the condition (p(D, R) is verified, then the output policy (D) is e-optimal in R, with probability 1 - 8. One notable case is that of & requiring a minimum dataset size.
Since the output of generic algorithm might be any generic nar-Markov deterministic policy, we cannot restrict our attention to regular policies. We expand the value a policy क H + in RDP Rize E (L, H, as follows:
H
E (ho)] = E
Σ
(47)
1=1
= (H L) P(qr+1 = 1+1 T)
(48)
(H L)) Σ P(gr = a TT) P(uc+1 = 2+,4+1 qr. = q, T)
(49)
(ERL
= (H - L) (F(qL = 901 т) P()+(1 4+. 9L = 90L T)
P(gr = -/r.. P))((1+ 9+,1+1 Qr. = QII,, T))
+ (H - L) (P((1. = qbr σ)) [ = 94.4+1 Qr = 96L, x))
(50)
1 (P(q) = goz 00 E {0, 1}. T) P(gr+1 = 2+,++1 1r = -00, m)
2
+ P(gz qu. 1o E (0. 1}, x) P( = 7+. Qr. = ()L,
H- - L
+
PP(qL+1 1+.4+1 qu QbL: T)
(51)
2
H 1- L
(P(q1+) 1+.1+1 -=== -or. T) + P(gr++ = 04,041 qr. -iz,,
4
H
+
P(gL+1 9+.111 q1 = 9bL: x)
(52)
2
H -
(P(as = do qr = 9OL. Pfoz = + QL = 9OL, ag = =6)
4
+ (1 - P(Ll = dg q9 = 9OL, T)) P(ol = + 19 qUL. ap = a1)
+ (1 - P(ar. = d' qr. qıt,, T)) P(orr = + qr. qur a1. = d6)
+ P(rr = di (r. = qut. T) Poorr = + | qr. qu, az = =ai))
+ H (Pa(r, = ag qr. 9b.. T) Pooor gr. = 9b. Rr. = =d))
2
30

---

+ P(al= = I 9L - quL. T) P(ol = + 11 QLL. = d1))
(53)
where in Eq. (52) we have used the uniform probability over æ. Now, for any history-dependent deterministic policy in episodie RDPs, it is possible to identify associated regular stochastic
policy n, O + A(A), where Q = 2 \ {qo,) } and:
a) = (()
F(h) =q)
(54)
Σ T(T(K)) =a) IP(h = 1// (T) WEF-1(O)
(55)
P I
In other words, Tr encodes the probability that π takes action o, given that some history has led to state q. With this convention, we resume from Eq. (53)
EVV (ho)] = H
(क (90z, de) (e(+)) + कe (gor, d6)) (=())
4
+ (1 - n (9LL a ()) 0e + क. (911 a1) (x(+))
H
+
(T,(90L, db) ul (+) + म. (00. a1) (I(c= = I[c a6) vn(()))))
2
(56)
H L
(कx (9OL, ab) (1 E) + (1 (00l an)) (1 (1)
8
+ (1 - n ( a1)) (1 {) + ( ()) (1+
H (n.(9bL, db) + ग Tr(9,L, a (I(c d)) + + I[(c db) (1 - n)))
+
4
(57)
H (1 -
db) + ( (1)
4
+ M (r(gbL, d6) + ne (1bL d1) (1 + 17 TT[ di) - 17 ryI(cc db)))
(58)
For the optimal policy in particular, this becomes:
4 H L (1+ d') + (1 1) I(c -())
(59)
4
From the e-optimality of x= 2(()), then,
E 2 E(V (hu) - V0- (ho)]
(60)
H L
4 (2g - E n, (4OL: d6)) - [T,((LL,
+ n [(c = d') (1 - T (1bL, a()) + n [[ = ab) n. (4bL, d())
(61)
H L (5 - TT(QUL, db) T (r(L d()) + 17 (1 ग. Tr(bb,, c)))
(62)
4
H - L
max(g (1 Tr(902, (r a()),, (1 Tr c))}
(63)
4
Now, assume that
16s
min(E, 2 H-I L
(64)
Then, all of the following is true: (9(LL d6) 2 3/4, TT TT(91L df) 2 3/4, 44, T. (r(66, c) 2 3/4. This means that, for small any s-optimal policy must frequently select the optimal action for both the parity problem and the bandit. Let us represent the first two events with Bp and the third with Bg Since 21 is (c, PPC for R[L, H, under yo, the probability of Bp B, is at least 6, for any D and n satisfying (DD, x²)
We proceed to compute the necessary data to satisfy both events with high probability. The dataset D can be partitioned in two subsets D, and Dp. containing any episode from D whose initial observation {0, 1} and +, respectively. The two datasets share no information and Dp and D, are mutually independent. To see this, we observe that the sequence a1+1"1+10141 ... og is independent of
31

---

a0rg0g... ag given OL, since - or determines at step L determines the rest of the episode. Also, for any two episodes en,, Cg. the sequence a1 ...or. independent of a dfrío of given on. Since, On ~ 8, that is the starting distribution, the two datasets are independent. Let 2p (Is: HU (for f=......... U
and 2. = (9s. fo, JU (Wi (2+,0- i= H be the reachable states in the two datasets. Then, we consider two separate classes IR [L, E) and RLL, H, 1) as the sets of RDPs in IR L, H, n), restricted to 2p and Qo. respectively. To do we construct R, E CL, E) and R. E RR(, H,) such that the initial observation follows unif([0, 11) in R, and 1+ in Re. Now, from the independence of the two datasets and the fact that 21 is (E, 8) -PC in D, there must exists is (2e, 5) 6)- in R L, H, E) under some (pp, and 2I, Do + To that is (2e, 8)-PAC in R(L, H) under some Pb. If this
U
algorithm M, Dp + Tp that
not the case, Bp A B, could not be verified in one of the two terms.
We analyze 2lp first and we show that its requirement up is (Dol E Q(LLE) U 20(4), For a contra- diction, assume this is not the case and that [Dpl {(L,E) & (((L/) 2 is allowed. Then, we can use 2p to solve the noisy parity problem under the streaming setting with g(L,E) samples (this setting has been introduced in Appendix 1. We proceed follows. Consider any noisy parity function fa.g with unknown x. Sample a sequence of strings {y: Ji E 2 from the uniform distribution and collect g (T,, {) pairs (yi,Pe),, sampling p; ~ (1s). Then, for H > I., compose dataset of episodes {e:hi- All actions of e; are selected uniformly in {ab. d1)- The observations 00:L-1 are y/ and or, equals p. if ar dgg Pt. otherwise (0 and I take roles of + and symbols here). Rewards 1: Rr are equal to one if or, 1, null otherwise. We obtain that dataset so constructed is equally likely under this procedure than under the uniform policy and the RDP R2 E RRL, H). Since 21p is (2s, 8)- PAC for RLL, E), with probability 1 - 5, the output policy Tp satisfies:
min(xTpp(0o. ob), p d1) ) 2 3/4
(65)
where Trr is the stochastic regular policy for Tp. This can be seen by our assumption in Eq. (64) and doubling both e and the sub-optimality gap of Eq. (63), due to the updated probability for the initial observation. Then, for any sequence y E 2 and associated history hr. with on. y,
(y) = arg max Tp (h(h-11.a))
(66)
1=0,1
which is the noiseless parity function based on x. This means that it is possible to reconstruct x solely by interacting with Tp, without collecting further samples. The solution we have described is a streaming algorithm with sample complexity E(L, Since this contradicts Lemma 18, we have proven DDpl E (((LE) U 20(L).
We now consider the bandit problem, which is solved by 24g Similarly to the previous case, from the e-optimality of 2g (Dp), we obtain the necessary condition: The (9bz. c) 2 3/4 from Eq. (63). This condition is expressed for the stochastic policy Tar, However, we notice that for qur. in particular, the only possible history is h = an ........ where all actions must also be deterministie. Then,
Tor (QbL, c) (h) c [(h) 9bL) = I(TT =c)
(67)
implying that Toe can only be deterministic for PoL- This means that 24 must solve best-arm identification in the two arm bandit at QbL- We can compose simplified dataset that is relevant for the bandit as:
D = (ar.or : En DD)
(68)
Since Dp can be deterministically reconstructed from D/,- we have the following conditional indepen- dence: ma J. c D', where e E {ah, } is the optimal arm, and म. (2,)) is the output of the algorithm. Denoting with é = Tb mb(h the selected arm, the error probability is P. == P(è & c).
Applying Fano's 's inequality from Theorem 12 to the variables e + Dj -> gives:
H2((P) > ((c D() = (c))) - D(, = log 2 T(c; D()
(69)
(70)
where we have used the fact that is a Bernoulli variable and the uniform prior over c. Now, assuming
C 2 2, we construct the following behavior policy: x² < ao) = 1 1/C and T" ("(L,, 1/C. In the following, we write No-- == [Dp] and omit the implicit dependency on nb.
[(c; D() = HD()) - H (T(,
(71)
(oL(L) (aroL c))
(72)
32

---

NDDKL(((OOOL c) P(OLOL) P(c))
(73)
Nb
P(a,ole) e') log o(a,olc)
(74)
2 a,c'EA,,E0
P(a,o)
Nb
P(a (alcd)P( c)) d.
Σ
P(a,0 log
(75)
2
Ene P(a d") P(o c0/0)/2
a,cEEA,EE0
No
2P | d'
P(a,ol log
(76)
2
Ee, P(o c"
a,C'EA,DEO
No
Σ
P(a, d)) log(2((o d))))
(77)
2
No
Σ
P(a'. c') log(2P(o d.
(78)
d'EA,0EO
Nb
Σ
(P(d), o c= dn) 1og(2I((o c= dg. (])) + P(d o c= di) log(2P(o c= dj d)))
2
(79)
= Nb(P(d)) + e= 1og(2P(+ c dg. af)) + P(di, + c= di) log(2I(( c== a')))
(80)
1-
1+ 20
No6
log(1 -1) +
log(1 (1 + n)
(81)
20
No
(EI |l vo)
(82)
C
17
(83)
C
Then from Eq. (70), and the fact that 21 is (2e, 8)-PAC,
12 C
H(6) Z H2(P.) 2 log
(84)
C
= No > 7/2 (log2 H()))
(85)
Which means that this must be Pb. the requirement for Ap.
Finally, to compose the results from both branches, we observe that [D] = |D, + |D,]. Also, for any 8 E (0, 0.5). say 1/4, (log 2 (8) becomes positive constant, and we can add both sizes asymptotically:
H |D] e (
C E 172
(86)
To relate the parameters to features of the RDP, we observe that the number of states of any RDP in R(L, H. n) Q < 3H. Also, the behavior policy is uniform everywhere except in qbt. Assuming C' 2 2, the computation of the single-policy concentrability coefficient yields C = C, for any c E d1). Next, we compute the L -distinguishabiiity of any RDP in this class. The L distinguishability of a set of states Q is the minimum L₁ distance in distribution between episodes prefixes that are generated starting from any two states in Q. Let us consider the L, norm for the pair Yu1 and 911.
[IP(e.: yo,, x²)- PP 90.. >
(87)
EE cEEH-1
[P(eL: e (01) - P(ei- = |1))l
(88)
Σ ((eu--1e))P(o a, r. r.ol e) P(as a, rl = =,00
911 e)
caroεÊ,
(89)
33

---

Σ aoEAO
Plas 0, =0 (oL) P(as a.oz = =0]
(90)
(1/2)
Poor =0 az doy 90L) Po = o as dg. qı6)
(91)
AEO
+(1/2)
Σ
[P(0 = 901) 90L) p(ol =0 o az 9121
(92)
oE
Σ [P aL d/i 9OL) Pooo o ar dg. 91
(93)
oEO
=o u1 d/ 9OL) P( + ag o/. 41
(94)
2
(95)
The L1 distance of suffixes from go1. 911 that are shorter than have also a distance 2 On the other hand, any shorter prefix has distance of O. Since. Li sums all these distances, the minimum across the qoi Qı pairs, is attained for Yo- and QıL, which determines μo 2 25. Also, the distance between any other pair of states in the same layer is strietly higher, since they differ deterministically in some reward or observation. Hence, the LP di-iitiinuuisaabiitty
the entire RDP is μuu 25.
Now, we choose L H/2. 17 32 e H and assume I HHuo/62 64, H 2. We can verify that these choices are consistent with the previous assumption min(S,n) 2 H-I- Substituting, the final requirement yp for the complete algorithm A is an exponential number of episodes in or:
16c
H Na
C E²
DD] E Ω
+
(96)
Now, for any H, no; C satisfying the previous assumptions, any algorithm cannot be (s, 1/4)- optimal for the instances in (H/2, H, po, 32 H) if Eq. (96) is not satisfied.
Note that in our RDP instance, the number of states and the horizon length scale linearly. So, might equivalently write HO instead of H²
34


Reviews:
[{"review_id": "HdFItYtpAj", "reviewer": "Reviewer_TAnR", "summary": "This paper studies the sample complexity of offline reinforcement learning (RL) in environments with non-Markov observation, i.e., partially observable Markov decision processes (POMDPs). In specific, the paper considers the episodic regular decision process (RDP) where the spaces of state, action, and observation are all finite. Given a batch of offline data, the proposed (offline RL) algorithm learns the ''states'' from the history data and converts the problem as offline RL for MDPs. The paper provides sample complexity bound for learning the states, as well as the optimal policy under certain assumptions. The paper also provides lower bound to prove the optimality of the upper bounds.\n\nOverall, the reviewer feels that the proposed algorithm for POMDPs brings new insight to the RL community and the theoretical results are strong enough to be accepted, even though they are built on strong assumptions, for example the distinguishability condition. As claimed by the authors, this is the first RL complexity bound of the setting and approach. Please see more details in the strengths and weakness parts.", "questions": "-", "limitations": "-", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The episodic regular decision process is conceptually a very large set of models that can be used to model many realistic environments. The 'state' the proposed algorithm trying to learn is essentially a sufficient statistics of the history for inference of future observations (folloiwing the behavior policy), which is very similar to the predictive stats representation (PSR) but slightly different in key assumptions (and leading to different learning approach). If my understanding is correct, every episodic finite-state POMDP is also an episodic RDP since we can always define the concatenation of the entire history or the belief, i.e., conditional distribution, of the 'hidden state' as the 'state' of the RDP.", "weaknesses": "1. The methodology that we first learn the state and then apply RL algorithm to the transformed data is quite a quite a straightforward approach. And it seems that Assumption 2 is the critical reason that we can eventually obtain the polynomial sample upper bound $\\sqrt{H}log(QAO)/(d\\mu)$ following such a straightforward approach. My biggest concern will be the scale of $\\mu_0$ which is related to the distinguishability. In particular, $\\mu_0$ represents the $L_\\infty$ distance between distributions over $e_{t:H}$, which will be $(OA)^{H-t}$-dimensional vectors with bounded $L_1$ norm. Roughly speaking, it feels that the average $L_\\infty$ distribution will be $(OA)^{-(H-t)}$. Then, unless the maximal distance $\\mu_0$ has a jump in the orders due to some special structure of the RDP, we seem to have exponential dependency on $H$ in the sample complexity. Perhaps more discussion of the scale of $\\mu_0$ with examples would be necessary.\n2. Assumption 1 is also a very strong assumption and greatly reduces the difficulty of learning the states and optimal policy. I am wondering if we can still obtain the current strong results by adding pessimism (e.g., as in [18]) into the current algorithm and removing Assumption 1.\n3. More technical discussion about the (reason for) improvement compared with the previous results [10, 27] in the main paper would be helpful for readers to understand the contribution of the current paper better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and constructive suggestions. Please find our response to your questions and concerns below:\n\n1. In the worst case scenario, the reviewer's intuition is correct. The distinguishability parameter in $L_\\infty$ distance may be exponentially small in the remaining horizon. This is indeed the case in the hard instance used for proving the lower bound. In the RDP of Figure 3 of the appendix, the two paths $q_{01} \\dots q_{0L}$ and $q_{11} \\dots q_{1L}$ are indistinguishable for $L-1$ steps, when they generate strings with uniform probabilities, and differ only after $L$ steps. Each string of length $L$ has a probability of $2^{-L}$ of being generated.\nHowever, this does not imply that distinguishability is necessarily small. In fact, two factors contribute to a larger parameter $\\mu_0$, as desired: \n    - First, we recall that we compute distinguishability with respect to the *prefix* $L_\\infty$ distance, which we denote by $L_\\infty^\\mathsf{p}$. The prefix distance computes the maximum distance between distributions over strings of all lengths. This means that if two states can be separated just by looking at suffixes of length $K$, where $K$ could be as small as 1, for effects that are immediately observable, the distinguishability parameter for those two states will scale as $2^{-K}$, in the worst case, not $2^{-H}$.\n    - A second factor that allows $\\mu_0$ to be large is the existence of one or few witnesses for distinguishability: these are traces of any length in $[1,H]$ that have high probability of being generated from one state but not from the other. Looking at the extreme side of the spectrum, we can consider RDPs with deterministic outputs, which are still non-Markovian environments. In this case, the prefix $L_\\infty$-distinguishability coincides with $\\max_{u \\in [t]} \\sum_{e_{0:u}} \\left| p_1(e_{0:u} *) - p_2(e_{0:u} *) \\right|$.\nMore generally, all the intermediate cases are possible. \n\n\n2. Assumption 1 is only needed if the full algorithm is combined with ADACT-H, which learns the complete RDP. The approximate version, that is ADACT-H-A, the algorithm referred to in Theorem 8, does not require Assumption 1. We will clarify this fact in the camera-ready version.\nHowever, integrating the two phases into a single learning algorithm is one of the main future directions we had also identified, which we will include in the final version. This will allow us to propagate low-value estimates from the RL side into the automata learning algorithm.\n3. We will clarify the differences with respect to the mentioned references in the final version. To briefly highlight the main observations here, we can comment for [10] and [27] separately.\n    - The paper [27] addresses online RL of RDPs in a discounted, infinite-horizon setting. Importantly, this algorithm uses the uniform policy for learning. So, the algorithm might be adapted to our setting, only under the assumption that the behaviour policy is uniform. Even in this case, such adaptation would imply sample efficiency bounds that are much looser than the ones we show here. In particular, the bound would roughly scale according to $O^{15}$ and $\\epsilon^{-10}$.\n    - The paper [10] is an important reference for the automata learning algorithm that we adapted to the episodic setting. Specifically for this part, we compare the upper bound at the bottom of page 7, and our upper bound in equation (4). Improving over known bounds for automata learning is necessary in order to obtain tight bounds for RL  so as to identify the true sources of complexity and hence obtain a better understanding of the problem overall."}, {"review_id": "e3IQRhwh2q", "reviewer": "Reviewer_jsz4", "summary": "This work studies the problem of offline reinforcement learning (ORL) of episodic regular decision processes (ERDP) where we wish to find an near-optimal policy for an unknown ERDP with a small dataset of trajectories (collected with a behavioral policy). The authors took a reductive approach to first find the states and transitions of the minimal automata (by a proposed algorithm ADACT-H) underlying the ERDP and then to transform the original dataset into an MDP (using the estimated automata states as MDP states) and lastly to apply any existing ORL algorithm to the resulting MDP. The theoretical results are substantiated with theorems, necessary definitions and assumptions.", "questions": "1. The trajectory length is fixed ($H$) the episodic setting, which implies a fixed length language (unlike general automata which can accept variable length sentences). Furthermore, the automata state space is stratified over tilmestep--making the DFAs acyclic--, I wonder if this makes the full generalization of DFAs a good fit for the episodic setting. \n1. Related to above, could you comment on the relevance of your approach to non-episodic setting? The DFA modeling of non-episodic environments seems more natural.\n1. Is there some interesting interaction between the learned DFA and subsequent ORL? For example, does it matter if the learned DFA is slightly larger than minimal? Is there some kind of tradeoff worth sharing or further study? What are some looseness in the reduction approach you took? \n1. Assumption 1, which asks for all observation to be present in the dataset, seems very restrictive (perhaps impossible for many ERDP). Since the ORL step is over $\\mathcal{Q}\\times\\mathcal{A}$, is it possible to relax the assumption?", "limitations": "NA", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The exposition is easy to follow and the overall logic is coherent and sound.\n1. The presented results support claims of contributions and seem novel.\n1. The problem studied is interesting and I think that the reductive approach in this work involving recent results from automata theory (ADACT which learns a minimal Moore machine) may inspire other RL studies.", "weaknesses": "1. Perhaps the result of a conscious choice of tradeoff in the presentation, it seldomly highlights the key theoretical challenges and the authors' insights in the main text of the paper. Maybe the authors could reclaim some space for this purpose from example 1? (It is not referenced in the main text.)\n1. In a similar vein, I wish that there is more technical discussion on (promising) un/under-explored alternative approaches and implications for related problem settings in closing. This should help contextualize the contributions of the work for a broader audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading, constructive suggestions, and recognition of our novelty. Please find our response to your questions and concerns below:\n\n### Response to Weaknesses:\nAs suggested, we will give further context and background about the main challenges in the introduction and closing. The discussion will include the following observations:\n\nOne of the main challenges of working with non-Markovian decision processes is to develop learning algorithms that avoid exponential dependencies in the horizon in both sample- and computational-complexity. In our algorithm, we were able to achieve this result by incrementally learning each state of the RDP (all the states in ADACT-H or a subset of states in ADACT-H-A) and carefully accounting for the contribution of learning each state to the sample complexity. This role is mainly played by the distinguishability factor, which modulates the complexity of identifying each state for a specific RDP instance. In many instances, this is what allows our sample complexity analysis to remain polynomial in the relevant factors. Finally, our algorithm has low computational complexity by design.\nAs future work, we believe that valuable directions can concentrate on alternative parameterizations or improvements on the definition of distinguishability. In particular, the development of a state-merging test that accounts for the (unknown) RDP structure of the distributions being tested.\n\n### Response to Questions:\n\n1. The automata that define Episodic RDPs are acyclic. More precisely, the class we consider is the one composed of all and only the RDP automata that generate a stop symbol after $H$ transitions. As a consequence, any automaton in this class is acyclic. This means that our work considers the most general class of automata that is consistent with a fixed horizon. This RDP definition also remains close to the ones that are present in the literature, because a non-Episodic RDP would simply be an automaton that is not forced to output $o_\\bot$ after $H$ transitions.\nThe explicit layered structure mainly serves to allow for some optimizations when testing RDP states. In fact, our automata learning algorithms ADACT-H and ADACT-H-A are specialised for the episodic setting, so as to have better performance than generic algorithms, which must account for the presence of cycles. \n2. Our work is the first one addressing offline RL in RDPs. Fixed-horizon MDPs are very well-studied and popular in the theoretical RL literature (see, for example, [12, 18]), in both online and offline settings, and they appear to have relatively gained more attention than their infinite-horizon counterparts, perhaps mostly because many practical tasks of interest are episodic in nature. Our paper contributes to this line of research, extending it to RDPs. In our work, we exploit the finiteness of the horizon in two ways: both to allow some algorithmic optimizations, as discussed above, and to take advantage of the horizon in our analysis. We do agree, however, that other interactions and optimality criteria are also interesting, such as the discounted, infinite horizon setting. This would require some independent treatment that we also identified as a possible future direction of our work.\n3. For computing an $\\epsilon$-optimal policy, it is sufficient that the Offline RL algorithm receives a dataset that respects the Markov assumptions in the new states and the original rewards. To guarantee this, it is sufficient that the function \"TestDistinct\" never returns a false negative. Minimality of the automaton, instead, is guaranteed by the absence of false positives. This second condition, however, is of much more minor importance than the former, as it only causes an increase in the sample complexity of the offline RL part, without any impact on correctness.\n4. Assumption 1 is only needed for the variant that learns the complete model (i.e., the one of Theorem 6), not for the approximate version of the algorithm, the one appearing in Theorem 8.\nFurthermore, Assumption 1 effectively means that the behaviour policy must select every action with positive probability, but we can modify the statement to omit the probability of observations. This is consistent with equation (2), with the convention that 0/0 = 0.\nWe will improve the assumption and the surrounding text to clarify both points."}, {"review_id": "Wl2SjgLLga", "reviewer": "Reviewer_9NCg", "summary": "The paper presents RegORL, an algorithm for offline RL in episodic RDPs. The algorithm combines automata learning techniques with state-of-the-art offline RL algorithms for MDPs. The authors provide a non-asymptotic high-probability sample complexity bound for RegORL, which guarantees the learning of an $\\epsilon$-optimal policy. They also establish a sample complexity lower bound for offline RL in RDPs. ", "questions": "1. Does the claim made by the authors in line 98, stating that computing a near-optimal policy is challenging even for a known POMDP, imply that this difficulty does not exist in the case of RDPs?\n\n2. Can the techniques proposed in this paper be applied to settings where the state or observation space is infinite, such as RDPs with a linear structure?\n\n\n\n\n\n", "limitations": "The suggestions have been claimed in \"Weaknesses\" and \"Questions\".\n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper comprehensively and rigorously explores algorithms for offline RDPs while leveraging automata learning techniques. This contribution carries great significance within the realm of offline RL theory.\n\n2. The structure of this paper is well-organized, resulting in a smooth and coherent reading experience. The comprehensive summary of relevant literature further enhances its overall completeness.", "weaknesses": "1. It would be beneficial to present a comparative analysis of RDP algorithms in tabular form, facilitating a clearer understanding of the different studies in this area.\n\n2.  In what ways does the offline setting present additional difficulties beyond the combination of commonly used techniques from offline RL and the technique used in online RDP research [1]?\n\n\n\n\n\n[1] Alessandro Ronca and Giuseppe De Giacomo. Efficient PAC reinforcement learning in regular decision\n418 processes. In IJCAI, pages 2026–2032, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and constructive suggestions. Please find our response to your questions and concerns below:\n\n### Response to Weaknesses:\n1. As suggested by the reviewer, we will include a more explicit comparison with the other papers that address RL in RDPs. We had identified three works [25, 27, 28]. These have been discussed more extensively in the appendix. However, we will make the comparison more explicit and also include the important differences in the main body in the final version.\n2. Offline RL in RDPs has some specific features with respect to the two, taken in isolation. One important difference is the need for a new single-policy RDP concentrability coefficient, which we defined. Its main difference with respect to the single-policy MDP concentrability is that each occupancy measure is computed on features that are not present in the dataset. Also, with regards to [1] (Ronca and De Giacomo, 2021), we mention that it addresses online RL in RDPs in a discounted, infinite-horizon setting. Importantly, this algorithm uses the uniform policy for learning. Hence, using the machinery in [1] could be adapted to our setting, only under the very strong assumption that the behaviour policy is uniform. Even in this case, such adaptation would imply sample efficiency bounds that are much looser than the ones we show here. In particular, the bound would roughly scale according to $O^{15}$ and $\\epsilon^{-10}$, which is far larger than our sample complexity bounds. We will clarify this in the final version.\n\n\n### Response to Questions:\n1. In line 98, we mention the computational complexity of finding the optimal policy of a known POMDP. This is PSPACE-complete. For RDPs, instead, thanks to their internal structure, optimal policies can be computed very efficiently, in polynomial time. When the RDP is known, the solution is to compute the MDP of Definition 3 and find its optimal policy.\n2. The answer differs depending on whether we consider infinite states, observations or rewards. Regarding states, the finite number of hidden states is tightly related to the finite automaton representation on which the RDP is built. This is part of what distinguishes them from more general formalisms such as POMDPs and yields the computational advantages discussed for Question 1. Such modification would strongly alter the specificity of RDPs. An infinite number of observations, on the other hand, leads to an interesting generalisation, which would allow RDPs to capture new interesting environments. The main challenge is that observations are part of the input alphabet of the transducer. In fact, an infinite number of input symbols would immediately impact the number of potential transitions from each state. This additional power modifies the class of automata under study, which would require an independent study. These are so-called symbolic automata. See, e.g., “The Power of Symbolic Automata and Transducers” by D'Antoni and Veanes, in CAV 2017. Extending RDPs to symbolic automata is an interesting direction for future work.\nOn the other hand, we believe that an infinite set of rewards is a very natural extension that is worth considering. Continuous reward functions do not conflict with the finite transducer structure or its transition function. Mainly, the \"TestDistinct\" function would need to be updated accordingly, as well as its analysis. This is an interesting direction for future work. We include and discuss both as future directions in the revised version. "}, {"review_id": "bb9Z9QXe31", "reviewer": "Reviewer_xyrg", "summary": "The authors presents a novel algorithm for offline RL in episodic Regular Decision Processes (RDP), a computationally feasible subclass of Non-Markovian Decision Processes. The presented algorithm have two phases: 1) learning the underlying automata by a novel algorithm, and 2) Markov transformation of the rest of the dataset and use any state-of-the-art algorithm for offline RL in usual MDPs. To obtain a theoretical guarantees, authors presents a notion of concentrability coefficient in the RDP setup. Finally, the lower bounds on sample complexity were presented.", "questions": "- What are the limitation to generalize the presented techniques beyond the tabular setting?\n- Is it possible to propose direct algorithm that will not depend on reduction to usual MDPs?", "limitations": "This is a theoretical paper that does not need to address the potential societal impact.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The first algorithm for offline RL in a challenging setup of Regular Decision Processes with provable guarantees.\n- A novel algorithm for automata learning that have a much tighter sample complexity than in the previous work.\n- The lower bounds shows that the introduced concentrability coefficient is indeed makes sense from the point of view of learning in RDB.", "weaknesses": "- Lack of empirical validation. The empirical experiments even on toy examples should much increase the value of the presented paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and constructive suggestions. Please find our response to your questions and concerns below:\n\n### Response to Questions:\n- We believe extension to discrete structured RDPs (with a known structure) could pose some mild challenges, in terms of algorithm design and analysis thereof, and may require some assumptions to be imposed. However, the task is certainly far from straightforward and the said challenges depend on the type of structure. In contrast, in the case of RDPs with infinite state and observation spaces, one must resort to using substantially different ideas, and we believe the problem becomes an interesting open question for future research. In the latter case, the first and most natural generalisation is considering reward distributions with continuous support. To do so, depending on the reward distribution class that is assumed, the \"TestDistinct\" function would need to be updated accordingly, as well as its analysis. The statistical test would be specific to continuous distribution and not be based on counting schemes.\nAlthough a similar modification might be done for observations, these pose an additional challenge with respect to rewards. In fact, observations are both outputs and inputs for our model. An infinite observation space would immediately imply an infinite number of input symbols and infinite potential transitions from each RDP state. This is a much more meaningful change that possibly alters the class and the expressiveness of the underlying transducer. This case would require an independent study to understand its impact.\n\n- We believe deriving a direct algorithm is a very interesting future direction that renders very challenging and calls for novel algorithmic ideas. Intuitively, such a direct algorithm avoids a sharp two-phase separation and would allow for interleaving automata learning steps with value estimations steps. This is desirable in order to direct RDP learning steps toward regions with high value estimates, thus resulting in a more sample-efficient algorithm for RDPs. However, deriving theoretical sample complexity bounds for such an algorithm could be very challenging. On the other hand, the approach taken appears natural in view of the fact that each RDP has an associated MDP, which is very easy to construct or simulate. Our current understanding is that the reduction is not a source of complexity in itself; it  was powerful enough to yield a sample complexity bound that matches some factors in the lower bound. Overall, we believe this is a very promising future direction, despite its involved challenges. Thus, we will include this discussion in the conclusion. "}, {"review_id": "kAxJT7gERS", "reviewer": "Reviewer_9RiT", "summary": "The paper presents an offline RL algorithm to learn near-optimal policies in a (episodic) Regular Decision Process (RDP). The problem is to learn a policy given a data set. The algorithm is split into two parts. First, is to learn the transition function of the RDP. Then, the problem of off-line learning on RDP is reduced to offline learning in MDP (intuitively, the underlying automata in the RDP is extracted) to generate a near-optimal policy in the RDP. The upper bound provided in this setting improves upon an upper bound of a similar algorithm in the non-episodic variant and a lower bound is also provided.   ", "questions": "What may be some challenges in adopting these algorithms in practice? ", "limitations": "NA.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Good problem. Well-written paper. Contributions and algorithms are well-stated and well-contextualized w.r.t. related work.  ", "weaknesses": "NA. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and recognition of our novelty. Please find our response to your questions and concerns below.\n\n### Response to Questions: \nInput prior knowledge and assumptions are, generally, the main limiting factors to the practicality of learning algorithms. Our algorithm works under a few assumptions, as listed in the paper, and only a few inputs. Besides the input dataset, we can see that ADACT-H only requires a confidence parameter $\\delta$ and an accuracy parameter $\\varepsilon$, both of which are user-specified. This is a minimal set of input knowledge. The second variant, ADACT-H-A, has a different trade-off between input knowledge and assumptions. Depending on the specific application, either solution might be more appropriate than the other. \n\nWe currently work under the assumption that rewards distributions are supported on a finite set. More general reward distributions are an important extension that would allow RDP to generalise to new classes of environments. We leave such a modification for future work.\n\nWe will include part of this discussion in the final revision of the manuscript."}]

Author rebuttal:

Meta-review: This work considers offline RL in a subclass of finite POMDPs. In this class called regular decision processes the observations can be captured by a finite state automaton. The paper provides sample complexity bound for learning the process and the optimal policy under certain assumptions. This bound is complemented with a tight lower bound.

All reviewers are in consensus that this paper tackles an interesting setting and although the approach perhaps follows expected techniques, the results are significant and well executed. The paper is also clear and well written. The AC agrees with this assessment and hence recommends acceptance.
Decision: Accept (poster)