Efficient PAC Reinforcement Learning in Regular Decision Processes

1 Introduction

The standard RL setting [Sutton and Barto, 2018] has long been characterised by the Markov assumption, which is arguably limiting. Regular decision processes (RDPs) have been proposed as a formalism with the promise to dispense with the Markov assumption while retaining good computational properties [Brafman and De Giacomo, 2019]. Complete knowledge of an RDP allows one to compute an equivalent Markov decision process (MDP), in a precise formal sense, and then to apply standard solution techniques for MDPs. This correspondence is not immediately applicable in the standard reinforcement learning (RL) setting, where an agent has no prior knowledge of the decision process. Instead, one needs to learn simultaneously a model of the dependencies on the past, and how observations and rewards evolve [Brafman and De Giacomo, 2019]. The possibility for an RL agent to learn such a model in the form of an automaton has been exploited in [Abadi and Brafman, 2020]. The work provides empirical evidence that algorithms based on automata learning can find near-optimal policies for certain RDPs. However, the proposed technique requires exponential time to converge unless only a small number of traces have high probability to be observed: it relies on statistics for single traces that may have exponentially-low probability, and hence require exponential time to be observed a number of times that is sufficient to compute accurate statistics.

In this paper, for the first time to the best of our knowledge, we introduce a technique for RL in RDPs which has formal guarantees analogous to those studied in literature for RL in MDPs [

Kearns and Singh, 2002; Auer et al., 2002; Kakade, 2003; Strehl and Littman, 2005; Auer and Ortner, 2006; Strehl et al., 2009; Audibert et al., 2009; Jaksch et al., 2010; Szita and Szepesv´ari, 2010; Lattimore and Hutter, 2014; Dann and Brunskill, 2015; Dann et al., 2017; Azar et al., 2017; Bai et al., 2020; Wang et al., 2020].

We show that RL in RDPs is feasible in polynomial time with respect to the probably approximately correct (PAC) learning criterion [Valiant, 1984; Kearns and Vazirani, 1994]. We present an algorithm that computes a near-optimal policy with high confidence, in a number of steps that is polynomial in the required accuracy and confidence, and in a set of parameters that describe the underlying RDP. The algorithm first learns a probabilistic deterministic finite automaton (PDFA) that represents the underlying RDP, then it maps it to an MDP, which is solved to compute an intermediate stationary policy, which is then turned into the final policy by composing it with the transition function of the learned PDFA. This process is repeated many times, yielding a better policy as more data becomes available, and converging in polynomial time.

Our results show that the Markov assumption can be largely removed while maintaining polynomial-time guarantees. This is a fundamental positive result, that should boost the confidence in finding effective RL techniques that dispense with the Markov assumption. Furthermore, our results should draw attention on RDPs, which have the potential of becoming the standard formalism for RL in the non-Markov setting, similarly to MDPs in the Markov setting.

Our work shows a strong connection between RDPs and PDFA, which allows one to take advantage of the many fundamental results and learning algorithms available for PDFA [Kearns et al., 1994; Ron et al., 1998; Clark and Thollard, 2004; Palmer and Goldberg, 2007; Balle et al., 2013; Balle et al., 2014]. On one hand, the negative results from [Kearns et al., 1994] about the impossibility of polynomialtime learning when state distinguishability is low transfer to RDPs. On the other hand, when state distinguishability is sufficiently high, PDFA techniques allow for polynomial-time learning (cf. [Ron et al., 1998; Balle et al., 2013]), and we show that such techniques can be leveraged to learn RDPs. In particular, we claim that PDFA techniques are the only known techniques so far to effectively learn states when they determine probability distributions, as it happens in RDPs.

Proofs of all results are given in an extended version of this paper [Ronca and De Giacomo, 2021]

2 Preliminaries

Transducers. We follow [Moore, 1956]. A transducer is a tuple 〈Q, q0,Σ, τ, Γ, θ〉 where: Q is a finite set of states; q0 ∈ Q is the initial state; Σ is the finite input alphabet; τ : Q×Σ → Q is the deterministic transition function; Γ is the finite output alphabet; θ : Q → Γ is the output function. We extend the use of τ to strings of length greater than one as τ(q, σ1σ2 . . . σn) = τ(τ(q, σ1), σ2 . . . σn), and to the empty string as τ(q, ε) = q. We also extend the use of θ to arbitrary strings as θ(q, σ1 . . . σn) = θ(q) θ(τ(q, σ1), σ2 . . . σn) where the base case is θ(q, ε) = θ(q). Furthermore, we write τ(σ1 . . . σn) for τ(q0, σ1 . . . σn), and we write θ(σ1 . . . σn) for θ(q0, σ1 . . . σn). Finally, we call θ(σ1 . . . σn) the output of the transducer on σ1 . . . σn.

Probabilistic Automata. We follow [Balle et al., 2013]. A Probabilistic Deterministic Finite Automaton (PDFA) is a tuple A = 〈Q,Σ, τ, λ, ζ, q0〉 where: Q is a finite set of states; Σ is an arbitrary finite alphabet; τ : Q × Σ → Q is the transition function; λ : Q × (Σ ∪ {ζ}) → [0, 1] defines the probability of emitting each symbol from each state (λ(q, σ) = 0 when σ ∈ Σ and τ(q, σ) is not defined); ζ is a special symbol not in Σ reserved to mark the end of a string; q0 ∈ Q is the initial state. It is required that: (i) λ(q, σ) = 0 when σ ∈ Σ and τ(q, σ) is not defined; (ii) for each state q ∈ Q, ∑σ∈(Σ∪{ζ}) λ(q, σ) = 1; (iii) for each state q ∈ Q that can be reached from the initial state q0 with non-zero probability, there is a state q′ ∈ Q with λ(q′ , ζ) > 0 that can be reached from q. The transition function τ is extended to strings as for transducers, and the probability function is extended as λ(q, ε) = 1 and λ(q, σ1σ2 . . . σn) = λ(q, σ1) · λ(q, σ2 . . . σn). Then, the probability that x ∈ Σ∗ is a string generated by the automaton starting from state q is λ(q, xζ), and the probability that it is a prefix is λ(q, x). For µ > 0, we say that A is µdistinguishable if maxx |λ(q1, x) - λ(q2, x)| ≥ µ for every two distinct states q1 and q2.

Non-Markov Decision Processes. A Non-Markov Decision Process (NMDP) (cf. [Brafman and De Giacomo, 2019]) is a tuple P = 〈A, S,R,T,R, γ〉 where: A is a finite set of actions; S is a finite set of states (or observation states to distinguish them from automata and transducer states); R ⊆ R≥0 is a finite set of non-negative reward values; T : S∗ × A × S → [0, 1] is the transition function which defines a probability distribution T(·|h, a) over S for every h ∈ S∗ and every a ∈ A; R : S∗ ×A×S → R is the reward function; γ ∈ (0, 1) is the discount factor. The transition and reward functions can be combined into the dynamics function D : S∗ × A × S × R → [0, 1] which defines a probability distribution D(·|h, a) over S ×R for every h ∈ S∗ and every a ∈ A. Namely, D(s, r|h, a) is T(s|h, a) if r = R(h, a, s), and zero otherwise. Every element of S∗ is called a history. A

policy is a function π : S∗ ×A → [0, 1] that, for every history h, defines a probability distribution π(·|h) over the actions A. A policy π is deterministic on a history h if π(a|h) = 1 for some action a, in which case we write π(h) = a; and it is deterministic if it is deterministic on every history. A policy π is uniform on a history h if π(a|h) = 1/|A| for every action a ∈ A. We call πu the policy that is uniform on every history. Every element of (ASR)∗ is called a trace. The dynamics of P under a policy π describe the probability of an upcoming trace, given the history so far, when actions are chosen according to a policy π; it can be recursively computed as Dπ(asrt|h) = π(a|h) · D(s, r|h) · Dπ(t|hs), with base case Dπ(ε|h) = 1 for ε the empty trace. The value of a policy π on a history h, written vπ(h), is the expected discounted sum of future rewards when actions are chosen according to π given that the history so far is h; it can be recursively computed as vπ(h) = ∑asr π(a|h) · D(s, r|h, a) · (r + γ · vπ(hs)). The optimal value on a history h is v∗(h) = maxπ vπ(h), which can be expressed without reference to any policy as v∗(h) = maxa (∑sr D(s, r|h, a) · (r + γ · v∗(hs))). The value of an action a on a history h under a policy π , written qπ(h, a), is the expected discounted sum of future rewards when the next action is a and the following actions are chosen according to π, given that the history so far is h; it is qπ(h, a) = ∑sr D(s, r|h, a)·(r+γ·vπ(hs)). The optimal value of an action a on a history h is q∗(h, a) = maxπ qπ(h, a), and it can be expressed as q∗(h, a) = ∑sr D(s, r|h, a)·(r+γ·v∗(hs)). A policy π is optimal on a history h if vπ(h) = v∗(h). For ϵ > 0, a policy π is ϵ-optimal on h if vπ(h) ≥ v∗(h) - ϵ. A policy is optimal (resp., ϵ-optimal) if it is so on every history. We also say near-optimal to say ϵ-optimal for some ϵ.

Regular Decision Processes. A Regular Decision Process (RDP) [Brafman and De Giacomo, 2019] 1 is an NMDP P = 〈A, S, R, T, R, γ〉 whose transition and reward functions can be represented by finite transducers. Specifically, there is a finite transducer that, on every history h, outputs the function Th : A × S → [0, 1] induced by T when its first argument is h; and there is a finite transducer that, on every history h, outputs the function Rh : A × S × R → [0, 1] induced by Rwhen its first argument is h. Note that the cross-product of such transducers yields a finite transducer for the dynamics function D of P.

Markov Decision Processes. A Markov Decision Process (MDP) [Bellman, 1957; Puterman, 1994] is an NMDP 〈A, S, R, T, R, γ〉 where both the transition function and the reward function (and hence the dynamics function) depend only on the last state in the history, which is never empty since every history starts with a state that is chosen arbitrarily. Specifically, for every pair of non-empty histories h1s and h2s, it holds that T(h1s, ·) = T(h2s, ·) and R(h1s, ·) = R(h2s, ·). Similarly, we say that a policy π is stationary if π(h1s, ·) = π(h2s, ·) for every pair of non-empty histories h1s and h2s. In the case of MDPs, we can see all historydependent functions-e.g., transition and reward functions, value functions, policies-as taking a single state in place of a history.

1 In [Brafman and De Giacomo, 2019] the functions T and R are represented using the temporal logics on finite traces LDLf . Here instead we use directly finite transducers to express them. Note that all T and R representable in LDLf are indeed expressible through finite transducers.

3 PAC-RL in RDPs

We consider reinforcement learning (RL) as the problem of an agent that has to learn an optimal policy for an unknown RDP P, by acting and receiving observation states and rewards according to the transition and reward functions of P. The agent performs a sequence of actions a1 . . . an, receiving an observation state si and a reward ri after each action ai. The agent has the opportunity to stop and possibly start over. This process generates strings of the form a1s1r1 . . . ansnrn which we call episodes. They form the experience of the agent, which is the basis to learn an optimal policy.

Example 1. As a running example, we consider an agent that has to cross a 2 ×m grid while avoiding enemies. Every enemy guards a two-cell column: enemy i guards cells (0, i) and (1, i), and it is found in cell (0, i) with probability p0i or p1i . Initially the probability is p0i , and the two probabilities are swapped every time the agent hits an enemy. At every step, say i, the agent has to decide whether to go through cell (0, i) or (1, i), taking action a0 or a1, respectively. Specifically, when in cell (0, i) or (1, i), action a0 leads to (0, i +1) and action a1 to (1, i+1). From the last column, the agent is brought back to the first one. The agent receives reward one every time it avoids an enemy. Each observation state s is a triple 〈i, j, e〉 where i ∈ [0, 1] and j ∈ [0, m-1] are the coordinates of the agent and e ∈ {enemy , clear } denotes whether an enemy is in the agent's current cell. To maximise rewards, the agent has to learn to predict the enemies' positions, which depend on the history of observation states in a regular manner. Such a dependency is described by a transducer with 2m states of the form 〈q1, q2〉 where q1 ∈ [0,m- 1] stores the agent's current column and q2 is a bit that keeps track of whether probabilities p0i or p1i are being used.

Our goal is to understand how fast an agent can learn a near-optimal policy. In particular, we want the agent to find near-optimal policies in the shortest possible time, and we are not interested in the agent maximising the collected rewards during learning. Thus, we require the agent to return policies π1, π2, . . . that improve over time. The idea is that these policies can be passed to an executing agent, living in such an environment, whose behaviour will improve as it receives better policies. Then, the central question is how fast an agent can reach a point after which it outputs only good policies.

Now we make our discussion more precise. To measure the learning performance of an agent, we consider the number of steps it performs.

Definition 1. An action step consists in performing an action and collecting the resulting observation-state and reward. A step is an action step or an elementary computation step.

Then, to have a reasonable notion of learning, we borrow from the Probably Approximately Correct (PAC) framework [Valiant, 1984; Kearns and Vazirani, 1994], similarly to what is done in previous work on RL in MDPs (cf. [Fiechter, 1994; Kearns and Singh, 2002; Strehl et al., 2009]). The PAC

framework is based on the observation that exact learning is infeasible. Thus, it introduces two parameters ϵ > 0 and δ ∈ (0, 1) that describe the required accuracy and the confidence of success, respectively. In the RL setting it translates into looking for policies that are ϵ-optimal with probability at least 1 - δ. Then, RL is considered feasible if these policies can be found in a number of steps that is polynomial in 1/ϵ and ln(1/δ), and in other parameters that describe the underlying RDP.

Definition 2. An RL agent (or algorithm) is said to reach accuracy ϵ and confidence δ in the moment it returns the first policy π∗ such that π∗ is ϵ-optimal with probability at least 1 - δ and the same holds for every policy returned after π∗.

Definition 3. Let dP be a list of parameters describing P, let A be its actions, and let γ be its discount factor. An RL agent (or algorithm) is PAC-RL with respect to dP if, for every ϵ > 0 and δ ∈ (0, 1), given (A, γ, ϵ, δ) as input, it reaches accuracy ϵ and confidence δ in poly(1/ϵ, ln(1/δ), dP) steps.

We propose to describe an RDP P = 〈A, S,R,T,R, γ〉 using the following parameters.

The first three parameters take into account the number of actions |A|, the discount factor γ, the maximum reward value Rmax, and the number of states n of the minimum transducer for the dynamics of P. Then, the reachability ρ of an RDP measures how easy it is to reach states of the dynamics transducer T when actions are taken uniformly at random.

Definition 4. The reachability of P is the minimum non-zero probability ρ that a given state of the dynamics transducer T is reached from the initial state within n steps (with n the number of states) when actions are chosen uniformly at random.

The distinguishability µ of an RDP measures how easy it is to distinguish states of the dynamics transducer T when actions are taken uniformly at random. It is a parameter inherited from the PDFA literature [Ron et al., 1998; Balle et al., 2013].

Definition 5. The distinguishability of P is the minimum µ ∈ (0, 1) such that one of the following conditions holds for every two histories h1, h2, where πu is the uniform policy:

• Dπu (t|h1) =Dπu (t|h2) for every trace t;
• |Dπu (t|h1) -Dπu (t|h2)| > µ for some trace t.

The degree of determinism η measures how easy it is to discover transitions. If η is small, then there is some transition that is possible, but unlikely to be observed. Note that this parameter takes value one when the RDP is deterministic.

Definition 6. The degree of determinism η of P is the minimum non-zero probability that T(·|h, a) assigns to an observation state.

Example 2. Consider the RDP of Example 1. Its reachability ρ is 1/2, since, by an inductive argument, every state reachable in i steps has probability at least 1/2 to be visited at step i and, from there, each of the two next states is visited with probability 1/2. The degree of determinism η is the minimum, for any i, among the probabilities p0i and p1i , and their complements. The distinguishability µ is given by the uniform probability of an action 1/2 times the minimum among η and the values |p0i - p1i |.

One can show that all the above parameters are necessary. For the number of actions, discount, and maximum reward parameters (and also for the accuracy and confidence parameters) the result follows from a known lower bound for the MAB problem [Mannor and Tsitsiklis, 2004]. Then, the number of transducer states, reachability, and degree of determinism can be shown to increase the number of action steps required to visit the relevant parts of the dynamics transducer a sufficient number of times. Finally, for the distinguishability parameter, it is straighforward to adapt the hardness proof for PDFA given in [Kearns et al., 1994], which assumes hardness of learning noisy parity function, a standard cryptographic assumption.

Theorem 1. There is no algorithm that is PAC-RL with respect to a strict subset of the parameters dP given in (1), if it is hard to learn noisy parity functions.

4 PAC-RL via Probabilistic Automata

We present an RL algorithm for RDPs that relies on probabilistic automata. We consider an RDP P = 〈A, S,R,T,R, γ〉, its dynamics function D, and the minimum transducer T = 〈Q, q0, S, τ, Γ, θ〉 that represents D in the sense that θ(h)(a, s, r) = D(s, r|h, a).

Representing RDPs as PDFA. When learning, the agent has the possibility to experience multiple episodes. In particular, the agent has an extra action, called stop action, that ends the current episode and starts a new one. To take advantage of that, the agent generates episodes following a stationary policy that chooses to stop with a non-zero probability p, and it chooses an action from A uniformly if it does not stop.

Definition 7. The stop action is a special action ζ that allows the agent to terminate the current episode and start a new one. The exploration policy with stop probability p > 0, written πp, is the policy that selects the stop action ζ with probability p, and each action from A with probability (1-p)/|A|.

Under an exploration policy, an RDP determines a probability distribution on traces, and hence can be seen as a PDFA. Specifically, the dynamics of P under πp are captured by the PDFA A = 〈Q, Σ, τ ′ , λ, ζ, q0〉 where:

• alphabet Σ = {asr ∈ ASR | ∃h. D(s, r|h, a) > 0},
• transitions τ ′ (q, asr) = τ(q, s),
• probability function:

The dynamics of P are captured in the sense that the following holds for every history h, trace t, and string h′ such that the projection of h′ on observation states coincides with h:

Algorithm 1 Reinforcement Learning RL(A, γ, ϵ, δ)

Input: Actions A, discount factor γ, required precision ϵ, confidence parameter δ.

Output: Policies.

• 1: for ℓ = 1, 2, . . . do 2: p ← 1/(10ℓ +1); k ← (2/p) · ℓ2 · (ℓ +5 lnℓ) 3: X ← ∅; i ← 0; hardStop ← false 4: while ¬hardStop do 5: x, hardStop ← generate an episode under policy πp with a hard stop after k - i actions 6: i ← increase i by the number of actions in x 7: if ¬hardStop then 8: X ← X ∪ {x} 9: end if 10: end while 11: ˆΣ← symbols in X; ˆRmax ←max reward in X 12: ˆ A ← learn PDFA by calling AdaCT(ℓ, | ˆΣ|, δ/2, X) 13: ˆM ←compute the MDP induced by ˆ A and γ 14: m← ⌈ 1 1-γ · ln ( 2· ˆRmax ϵ·(1-γ)2 )⌉ 15: π ← solve ˆM by calling ValueIteration( ˆM,m) 16: return transducer for the composition of π with the
• projection-on-states of the transition function of ˆ A
• 17: end for

PAC-RLAlgorithm. Algorithm1 provides the pseudocode of our RL algoritm. The algorithm repeats the following operations for increasing values of an integer variable ℓ, starting from 1. (Line 2) It computes the stop probability p, and the maximum number k of actions to perform during the current iteration. (Line 3) It initialises the set of episodes X to the empty set, a counter i for the actions to zero, and a flag hardStop to know when a hard stop has occurred. (Lines 410) It generates episodes following the exploration policy with stop probability p, and with a hard stop if the number of performed actions reaches k. Episodes are stored in variable X. (Line 11) It reads the set ˆΣ of action-state-reward symbols from X, and the maximum reward ˆRmax occurring in X. (Line 12) It learns a PDFA ˆ A = 〈 ˆQ, ˆΣ, ˆ τ ′ , ˆλ, ζ, ˆ q0〉 via the AdaCT algorithm [Balle et al., 2013] instantiated with ℓ as an upper bound on the number of automaton states, |ˆΣ| as an estimate of the size of the alphabet, confidence parameter δ/2, and set of strings X. (Line 13) Starting from ˆ A, the algorithm computes theMDP ˆM = 〈A, ˆQ, ˆR,D ˆM , γ, ˆ q0〉 where ˆR consists of each reward value occurring as the third component of an element of ˆΣ, and the dynamics function is as follows:

(Lines 14-15) The algorithm then solves ˆM via m iterations of the classic value iteration algorithm with action-value estimates initialised to zero. Specifically, value iteration computes an approximation ˆq ˆM∗ of the optimal action-value function q ˆM∗ of ˆM, and then computes the greedy policy π with respect ˆq ˆM∗ , which is a stationary policy on state space ˆQ.

(Line 16) The algorithm returns a transducer that represents the policy function π(ˆ τ(·)) obtained by composing the stationary policy π and the 'projection' transition function ˆ τ defined as ˆ τ(q, s) = ˆ τ ′ (q, asr) for an arbitrary choice of a and r such that ˆλ(q, asr) > 0; note that every choice yields the same result and a choice always exists. Specifically, the returned transducer is 〈 ˆQ, ˆ q0, ˆ S, ˆ τ,A, θ′ 〉 where θ′ (ˆ q) = π(ˆ q) and ˆ S consists of each observation-state occurring as the second component of an element of ˆΣ.

5 PACAnalysis

Algorithm 1 shows that RL in RDPs is feasible in polynomial time.

Theorem 2. Algorithm 1 is PAC-RL with respect to the parameters dP given in (1).

We analyse Algorithm 1 to show that the theorem holds. We first show that we can compute a near-optimal policy for P starting from a near-optimal policy for the MDP induced by the dynamics transducer T, that is defined as M = 〈A, Q, R, DM , γ〉 where the dynamics function is as follows:

We call it the ideal MDP, since it is the MDP that the algorithm would build if it learned the automaton ˆ A perfectly. Its key property is that an ϵ-optimal policy for P can be obtained from an ϵ-optimal policy for M by composing it with the transition function of T .

Lemma 1. If π is an ϵ-optimal policy for M, then π(τ(·)) is an ϵ-optimal policy for P.

Now that we know that it suffices to compute an ϵ-optimal policy for the ideal MDP M, we establish the accuracy required for the MDP ˆM that is actually computed by the algorithm (Line 14) in order to be the basis for computing an ϵ-optimal policy for M.

Definition 8. We say that ˆM is an α-approximation of M if the two MDPs have the same actions, rewards, and discount factor, and there is a bijection φ between their states such that ‖DM (·|q, a) - D ˆM (·|φ(q), a)‖1 ≤ α for every q and a.

The following lemma is an application of known results for MDPs. First, if ˆM approximates M, then the value functions of ˆM approximate the value functions of M [Strehl and Littman, 2005]. Then, the value functions of ˆM can be computed in polynomial time with high accuracy via the value iteration algorithm [Strehl et al., 2009]. Finally, any policy that greedily chooses the best action according to an accurate estimate of the optimal action-value function is near-optimal [Singh and Yee, 1994].

Lemma 2. If ˆM is an ϵ′ -approximation of M (with ϵ′ as in Table 1), then the greedy policy obtained via

iterations of the value iteration algorithm, with action-value estimates initialised to zero, is an ϵ-optimal policy for M.

We establish the accuracy required for the learned PDFA.

Definition 9. We say that ˆ A is an α-approximation of A if the two automata have the same alphabet, there is a transitionpreserving isomorphism φ between their states, and their probability functions satisfy |λ(q, σ) - ˆλ(φ(q), σ)| < α for every state q and symbol σ, with the additional condition that λ(q, σ) = 0 implies ˆλ(φ(q), σ) = 0.

The bound on the error for the learned automaton transfers to the MDP it induces, amplified by the number of transducer states, alphabet size, and the inverse of the minimum probability assigned to an action by the exploration policy πp.

Lemma 3. If ˆ A is an ϵ′′ -approximation of A, then ˆM is an ϵ′ -approximation of M (with ϵ′′ as in Table 1).

We next derive the number of episodes and the stop probability (which determines the length of episodes) under which the AdaCT algorithm guarantees to learn ϵ′′ -approximation of A. The accuracy of the algorithm depends on the distinguishability of the automaton to learn, on the minimum probability that a state is visited during a run, and on the minimum transition probability. Thus, we need establish lower bounds for the former three quantities. First, the distinguishability A is close to the distinguishability µ of P if p is sufficiently small, since states can be distinguished by looking at strings of length at most the number of states n. In fact, for any pair of longer strings witnessing the distinguishability, we can take their substrings of length at most n obtained by removing 'cycles', similarly to what is done in the pumping lemma for regular languages. The bound then follows by taking into account the probability (1-p)n of generating a string of length at least n. Second, the probability of visiting a state of A is at least the probability of generating a string of length at least n times the probability of visting the corresponding state in T while generating the string, which is at least the reachability ρ of P. Third, the minimum transition probability in A is at least the degree of determinism η of P times the probability of picking an action uniformly when not stopping.

Lemma 4. The distinguishability of A is at least µ· (1-p)n . The minimum non-zero probability that a state of A is visited during a run is at least ρ · (1 - p)n . The minimum non-zero probability of a non-ζ transition of A is at least η·(1-p)/|A|.

Given the bounds above, the next lemma follows from the guarantees for the AdaCT algorithm [Balle et al., 2013]. In particular, the guarantees require a number of episodes that depends on the specified upper bound on the states, on the specified alphabet size, on the required accuracy and confidence, and on the three quantities of the previous lemma, which applies considering that (1-p)n ≥ 0.9 because of the condition on p.

Lemma 5. If p ≤ 1/(10n + 1), ˆn is an upper bound on the number n of states of A, and X are strings generated by A with |X| ≥ max(N ′ ,N ′′ ), then AdaCT(ˆn, |Σ|, δ/2,X) returns an ϵ′′ -approximation of A with probability 1 - δ/2.

The required sample size and stop probability are achieved in a polynomial number ℓ of iterations of the algorithm. The sample size also guarantees ˆΣ = Σ and ˆRmax = Rmax. Furthermore, introducing a logarithmic dependency on δ ensures that a hard stop occurs with probability at most δ/2, which combined with the probability of failure of AdaCT is still less than δ. The ℓ-th iteration of the algorithm performs the number of actions k specified in Line 2, which is ˜O(ℓ4 ), and hence the algorithm performs ˜O(ℓ5 ) action steps in ℓ iterations, which is:

The bound mentions |Σ| which is not in dP, but satisfies |Σ| ≤ n · |A| · ⌈1/η⌉. Then, a polynomial number of action steps immediately implies a polynomial number of steps overall. In particular, AdaCT runs in time polynomial in the size of the input sample and in the specified values for the number of states and alphabet size, and also value iteration ValueIteration runs in time polynomial in the size of the input MDP and in the number of iterations. We conclude that Algorithm 1 reaches accuracy ϵ and confidence δ in a polynomial number of steps. Therefore, Algorithm 1 is PAC-RL.

6 Exploiting Prior Knowledge

We observe that if we know (or we can estimate) the number of states in the dynamics transducer, we can devise a simpler algorithm, Algorithm 2, with better performance bounds. Algorithm 2 is simpler than Algorithm 1, since it does need to search for the number of transducer states. The stop probability is constant throughout a run, and computed based on the upper bound on the states. Since the stop probability is uniform across iterations, all episodes can be seen as generated by the same automaton, and hence we can accumulate episodes instead of deleting previous ones. Furthermore, we can now call AdaCT directly with the given parameter ˆn. A simplified analysis, again based on Lemmas 1-5, yields the following polynomial bound on the expected number of action steps, which immediately implies a polynomial bound on the expected number of steps overall.

Theorem 3. Algorithm 2 on input (A, γ, ϵ, δ, ˆn) reaches accuracy ϵ and confidence δ within an expected number of action steps that is:

Algorithm 2 Reinforcement Learning RL(A, γ, ϵ, δ, ˆn)

Input: Actions A, discount factor γ, required precision ϵ, confidence parameter δ, upper bound ˆn on transducer states. Output: Policies.

• 1: p ← 1/(10 · ˆn+1)
• 2: X ← ∅
• 3: loop
• 4: x ←generate an episode under exploration policy πp
• 5: X ←X ∪ {x}
• 6: ˆΣ← symbols in X; ˆRmax ←max reward in X
• 7: ˆ A ← learn PDFA by calling AdaCT(ˆn, | ˆΣ|, δ, X)
• 8: ˆM ←compute the MDP induced by ˆ A and γ

• 10: π ← solve ˆM by calling ValueIteration( ˆM,m)
• 11: return transducer for the composition of π with the projection-on-states of the transition function of ˆ A
• 12: end loop

7 Discussion

We have presented RL algorithms that can learn near-optimal policies for RDPs in polynomially-many steps, in the parameters that describe the underlying RDP.

Example 3. Algorithm 1 and Algorithm 2 (with a bound on the number of states that is polynomial in the grid length) compute a near-optimal policy in each of the RDPs introduced in Example 1 in a number of steps that is polynomial in the following quantities: (i) the grid lengthm, (ii) the inverse of the minimum among p0i , p1i , 1-p0i , 1-p1i , (iii) the inverse of the minimum value |p0i - p1i |.

Adopting PDFA techniques takes us into a different direction from existing approaches based on a direct clustering of histories such as [Abadi and Brafman, 2020]. There, histories are clustered according to the probability of the following observation state. Since the algorithm compares single histories, the accuracy of the algorithm depends on the probability of single histories, which can be exponentially-low in their length. In turn, the required length of histories can growwith the number of transducer states, and hence the approach can require exponentially-many episodes in order to achieve high accuracy. For instance, in our running example, a history of length m has probability at most gm under any policy, with g the maximum probability among p0i , p1u , 1-p0i , 1-p1i . Histories of length m-1 are necessary to determine the best action at the m-th step. To address the issue, PDFA algorithms build states incrementally while relying on their distinguishability. This way, each state gathers the probability of all the histories it represents. In light of our results, we believe that these PDFA techniques will be instrumental in developing the next generation of tools for RL in RDPs.

Acknowledgments

This work has been partially supported by the ERC Advanced Grant WhiteMech (No. 834228) and by the EU ICT-48 2020 project TAILOR (No. 952215).