Regular Decision Processes: A Model for Non-Markovian Domains

1 Introduction

The Markov assumption (MA) plays a key-role in the definition of MDPs. It states that the next-state distribution following an action is independent of the history, given the current state. Yet, MA does not hold in many domains: one is likelier to be able to enter a restricted area if permission was obtained in the past; a car is likelier to skid if it rained in the past with no sunshine since; and even more so, if the rain was followed by below zero temperature; a person is likelier to contract mumps flying, if she has not contracted it in the past; or, a robot should be rewarded for delivering coffee only if its owner previously requested it. The first examples describe non-Markovian dynamics, and the last one, a non-Markovian reward, first studied in [Bacchus et al., 1996], and recently advocated as useful for reinforcement learning in robotics [Littman et al., 2017; Camacho et al., 2017].

Often, MA is treated as a simple technical restriction because one can always modify the state description to make a non-Markovian model Markovian. For example, we can add indicator variables that record whether access was granted, coffee was requested, etc. More generally, the belief-space MDP can be viewed as maintaining information about the entire history of a POMDP using an infinitely larger state space.

This approach suffers from two problems: First, the agent's state space may be hard-coded. For example, a robot learning its environment may have a built-in state representation, related to its sensing abilities, set by a designer who was possibly unfamiliar with this environment. Second, even when the designer has the freedom to modify the state space, it may be much simpler to specify non-Markovian dynamics or reward explicitly than to design the correct equivalent Markovian model which (as we show) can be exponentially larger.

One well-known non-Markovian model is k-order MDPs, in which the next state distribution induced by an action depends on the last k states. However, k-order MDPs are impractical for large k, as their equivalent MDP is exponential in k. Moreover, they cannot express simple properties that depend on the arbitrary past, such as the examples above.

To address these issues, we introduce and study Regular Decision Process (RDP), a non-Markovian decision model and language that can succinctly represent dependence on the arbitrary past. In RDPs, the next state distribution and the reward function are conditioned on logical formulas, like in factored MDPs [Boutilier et al., 1999]. But while formulas in factored MDPs are propositional (or first-order) and refer to the current state only, formulas in RDPs are in LDLf- linear dynamic logic over finite traces, and refer to the entire history.

The main contributions of this paper are to introduce RDPs, study their properties and complexity, describe how to optimize them, and postulate a potential method for learning them from observations. We also briefly explore the potential role of RDPs in approximating POMDPs. It is well known that POMDPs are difficult to solve [Papadimitriou and Tsitsiklis, 1987; Littman et al., 1998; Madani et al., 2003] - and difficult to learn: only a few algorithms exist that provide some guarantees (e.g., [Zhang et al., 2012]) but they are not too useful w.r.t. sample complexity. RDPs offer three potential benefits: First, they are easier to solve than POMDPs. Second, they are more expressive than MDPs, and hence may be able to provide a better approximation. Indeed, we show that for every POMDP, there exists a RDP that can ϵ-approximate it. Third, they do not require hypothesizing the existence of hidden variables - they are based on observable variables only. This latter property is promising from the learning perspective.

2 Background

We assume familiarity with MDPs and POMDPs, and only recall basic notation and ideas.

A Markov Decision Process (MDP) M = 〈S, A, T r, R, s0〉 contains a set S of states, a set A of actions, a transition function Tr : S × A → Π(S) that returns for every state s and action a a distribution over the next state; a reward function R : S × A → R that specifies the real-valued reward received by the agent when applying action a in state s; and an initial state s0 ∈ S. In this paper, states in S are truth assignments to a set P of primitive propositions. This allows for using a more compact factored description of the reward and transition function. To emphasize this, we write M = 〈P, S, A, Tr, R, s0〉. The horizon of the MDP is the number of actions/steps that the agent executes.

A solution to an MDP is a policy that maps histories of states and actions to actions. The value of policy ρ at s, vρ (s), is the expected discounted sum of rewards when starting at s and selecting actions based on ρ. Every MDP has an optimal policy, ρ∗ , that maximizes the expected discounted sum of rewards for every starting state s ∈ S. When the horizon is infinite, a deterministic stationary policy ρ∗ : S → A that is optimal, exists [Puterman, 2005]. Many methods for solving MDPs rely on the Markov assumption, and their theoretical and practical complexity is strongly impacted by |S||A|.

A partially observable MDP (POMDP) is a tuple M = 〈S,A, Tr,R,O,Ω, b0〉. S,A, Tr,R are as in MDPs, but instead of observing the entire state, the agent observes an element of Ω. O : A × S → Π(Ω) specifies the probability of observing o ∈ Ω if a ∈ A was executed and led to state s ∈ S, denoted o(a, s, o). Observations can be noisy, and the same observation may be possible in different state-action pairs. b0 is the initial distribution over states. In a factored POMDP [Boutilier et al., 1999], M = 〈P, S, A, T r, R, O, PO, b0〉, P is a set of propositions, S contains assignments to P, and PO ⊂ P are the observable propositions. Transition, reward, and observation functions are specified more succinctly by alluding to changes in the values of propositions as a function of the current state's properties.

POMDPs can be solved by compiling them to belief-space MDPs - MDPs in which the states (called belief states) are distributions over S. The initial belief state is b0, and given the current belief state, action and observation, the next belief state can be computed using standard probabilistic inference. While this state space is uncountable, it enjoys special properties that are exploited by various solution algorithms.

LDLf (linear dynamic logic on finite traces)[De Giacomo and Vardi, 2013] combines linear-time temporal logic LTL [Pnueli, 1977] with the syntax of PDL, propositional dynamic logic [Fischer and Ladner, 1979; Harel et al., 2000; Vardi, 2011], but interpreted over finite traces. LDLf is as expressive as regular expressions (RE) and both have the expressive power of monadic second order logic over finite traces. Thus, much of this paper can be understood without familiarity with LDLf , by substituting "regular expressions" wherever "LDLf formula" appears. However, RE themselves are not convenient for expressing temporal specifications: To negate a RE, one must generate the corresponding deterministic finite automaton (DFA), which can be exponential in the size of the RE, negate it, and generate its corresponding RE. One can conjoin two RE in polynomial time by constructing their NFAs, generating their product NFA, and then moving to RE. Polynomial, but quite inconvenient. LDLf was explicitly introduced in [De Giacomo and Vardi, 2013] to provide a more convenient specification language.

Here, we consider a variant of LDLf that works also on empty traces [Brafman et al., 2018]. Formally, LDLf formulas ϕ are built as follows:

tt stands for logical true; φ is a propositional formula over P (including true, not to be confused with tt); ϱ denotes path expressions, which are RE over propositional formulas φ with the addition of the test construct ϕ? typical of PDL. We use abbreviations [ϱ]ϕ .= ¬〈ϱ〉¬ϕ, ff .= ¬tt for false, and φ .= 〈φ〉tt to denote occurrence of propositional formula φ.

Intuitively, 〈ϱ〉ϕ states that from the current step in the trace, there exists an execution satisfying the RE ϱ, such that its last step satisfies ϕ, while [ϱ]ϕ states that from the current step, all executions satisfying the RE ϱ are such that their last step satisfies ϕ. Tests are used to insert into the execution path checks for satisfaction of additional LDLf formulas.

The semantics of LDLf is given in terms of finite traces, i.e., finite sequences τ = τ0, . . . , τn of elements from the alphabet 2P . In decision processes, traces are sequences of states and actions: 〈s0, a1, s1, . . . , an, sn〉. We represent them as a trace by extending the set P to include one proposition pa per action a, assigned true if a was the last action, and setting τi .= si ∪ {pa | a = ai}. In this way, τi denotes the pair (ai, si) (with a dummy action a0 for the initial state s0). Henceforth, we assume this form, even if verbally referring to state-action sequences and sometimes representing the actions explicitly. We define τ(i) .= τi, length(τ) .= n + 1, and τ(i, j) .= τi, τi+1, . . . , τj-1. When j > length(τ), τ(i, j) .= τ(i, length(τ)). Given a finite trace τ, an LDLf formula ϕ, and a position i, we define when ϕ is true at step i, written τ, i |= ϕ, by (mutual) induction, as follows:

• τ, i |= tt;
• τ, i |= ¬ϕ iff τ, i ̸|= ϕ;
• τ, i |= ϕ1 ∧ϕ2 iff τ, i |= ϕ1 and τ, i |= ϕ2;
• τ, i |= 〈ϱ〉ϕ iff there exists i ≤ j such that τ(i, j) ∈ L(ϱ) and τ, j |= ϕ, where the relation τ(i, j) ∈ L(ϱ) is as follows:
• τ(i, j) ∈ L(φ) if j=i+1, i < length(τ), and τ(i) |= φ (φ propositional);
• τ(i, j) ∈ L(ϕ?) if j = i and τ, i |= ϕ;
• τ(i, j) ∈ L(ϱ1+ϱ2) if τ(i, j) ∈ L(ϱ1) or τ(i, j) ∈ L(ϱ2);
• τ(i, j) ∈ L(ϱ1; ϱ2) if there exists k ∈ [i, j] such that τ(i, k) ∈ L(ϱ1) and τ(k, j) ∈ L(ϱ2);
• τ(i, j) ∈ L(ϱ∗ ) if j = i or there exists k such that τ (i, k) ∈ L(ϱ) and τ (k, j) ∈ L(ϱ∗ ).

Note that if i ≥ length(τ), the above definitions still apply; though, 〈φ〉ϕ (φ prop.) and 〈ϱ〉ϕ become trivially false.

We say that a trace τ satisfies an LDLf formula ϕ, written τ |= ϕ, if τ, 0 |= ϕ.

In LDLf we can easily express temporal operators such as next (◦) and until (U) using abbreviations ◦ϕ .= 〈true〉(ϕ∧ ¬end) and ϕ1Uϕ2 .= 〈(ϕ1?; true)∗ 〉(ϕ2 ∧ ¬end), and any RE r, with the formula 〈r〉end, where end .= [true]ff expresses that the trace has ended. We also use the abbreviation atlast(ϱ) .= 〈true∗ ; ϱ〉end to say that the sequence ϱ happened just before the end. For example, atlast(Rain) means that at the very end of the trace it rained.

Example 1. Here are some LDLf formulas and their intuitive semantics: ϕ1 = 〈true∗ ;Rain; true∗ 〉end - it rained in the past. ϕ2 = atlast(Rain;Rain;Rain)end - it rained in the last 3 time steps (e.g., days). ϕ′2 = atlast(Rain)∨atlast(Rain; true)∨atlast(Rain; true; true) - it rained in one of the last 3 time steps. ϕ3 = 〈true∗ ;Rain; (¬(Tmp>5))∗ 〉end - it rained in the past, and the temperature was not above 5oC since. ϕ4 = 〈true∗ ; Rain; Tmp<0; (¬(Tmp>2))∗ 〉end - it rained in the past, then the temperature was below 0, and since, it was not above 2oC.

3 Non-Markovian Decision Processes

We define the basic semantic model of a Non-Markovian Decision Process (NMDP) and the more restricted case of a RDP.

3.1 NMDPs

A NMDP is identical to an MDP, except that the transition and reward functions depend on the entire history (trace). Formally, a Non-Markovian Decision Process (NMDP) is a tuple M = 〈P,A, S, tr, r, s0〉, where P,A, S, s0 are as in an MDP, and we assume there are propositions A ⊆ P that denote the action that just occurred; tr : S+ ×A×S →Π(S) is the transition function, i.e., tr((s0, . . . , sk), a, s′ ) is the probability of reaching state s′ when executing action a given history s0, ..., sk; and r : S+ → [rmin, rmax]. Here S+ is the set of all finite, non-empty, state sequences.

A policy for a NMDP is a partial function ρ : S+ → A such that ρ is defined on every sequence w ∈ S+ reachable from s0 under ρ, where reachability under ρ is defined inductively as follows: s0 is reachable; if w ∈ S+ is reachable and tr(w, a, s′ ) > 0 then w · s′ is reachable.

The value of a trace s0, s1, . . . , sn is its discounted sum of rewards: v(s0, . . . , sn) = ∑ni=0 γ n r(s0, . . . si), where 0 < γ < 1 is the discount factor. Because we assume the reward value is lower and upper bounded, this discounted sum is always finite and bounded from above and below. For every finite horizon n, ρ and M define a distribution over possible traces, and vn(ρ) denotes the expected value of length n traces with respect to this distribution. We denote the value of a policy ρ by v(ρ) = lim infn→∞ vn(ρ). Finally, ρ is an optimal policy for M if for every policy ρ′ , we have that v(ρ) ≥ v(ρ′ ).

For MDPs with infinite horizon, we know that there exists an optimal stationary policy, i.e., a policy ρ : S →A. Thus, in MDPs we can restrict attention to this finite set of policies. For NMDPs, it is clear that we cannot restrict our attention to stationary policies. In fact, it is not a-priori clear that there exists an optimal policy. However, since the value of a policy is bounded, there exists some value v∗ = suppolicy ρ v(ρ).

3.2 RDPs

NMDPs can refer to infinite objects and may not be finitely representable, so one cannot specify or learn them, in general. Hence, we restrict attention to a class of NMDPs in which a finite, logic-based description is used to capture properties of traces. Specifically, we use dynamic logic over finite trace, LDLf , whose formulas are interpreted as sets of traces. We note that there is much past work in the area of probabilistic model-checking and control on computing the probability that a trace will satisfy a given temporal formula [Kwiatkowska et al., 2011], and on generating policies that ensure (or maximizing the probability) that it will be satisfied [Ding et al., 2014]. Unlike them, we use LDLf formula to describe the inherent dynamics of the system.

We define a Regular Decision Processes (RDP) to be a NMDP ML = 〈P, A, S, trL, rL, s0〉 whose transition and reward functions are specified as follows: trL is represented by a finite set T of quadruples of the form: (ϕ, a, P ′ , π(P ′ )), where ϕ is an LDLf formula over P, a ∈ A, P ′ ⊆ P is the set of propositions affected by a when ϕ holds, and π(P ′ ) is a joint-distribution over P ′ describing its post-action distribution. The basic assumption is that the value of variables not in P ′ is not impacted by a.

If {(ϕi, a, P ′ i , πi(P ′ )|i ∈ Ia} are all quadruples for a, then the ϕi's must be mutually exclusive, i.e., ϕi∧ϕj is inconsistent, for i ̸= j. But they need not be exhaustive, so that no a transition may be possible given some traces.

trL((s0, ..., sk), a, s′ ) is now defined as follows:

1. trL((s0, ..., sk), a, s′ ) = π(s′ |P ′) if exists a quadruple (ϕ, a, P ′ , π(P ′ )) such that s0, ..., sk |= ϕ, and sk and s′ agree on all variables in P \ P ′ . Here, s′ |P ′ denotes the restriction of s′ to the propositions in P ′ .
2. trL((s0, ..., sk), a, s′ ) = 0 otherwise.

That is, given current trace s0, ..., sk and action a, if no quadruple has a condition ϕ satisfied by s0, ..., sk, then no transition is possible on a. Otherwise, let (ϕ, a, P ′ , π(P ′ )) be such a quadruple. By our assumptions, it is the only one. The next state s′ must assign exactly the same value to propositions not in P ′ as in sk - i.e., they are not impacted by the action. Its probability is equal to the probability that π assigns to the value of the P ′ propositions in s′ .

The reward function rL is specified using a finite set R of pairs of the form (ϕ, r), where ϕ is an LDLf formula over P, and r ∈ R is a real-valued reward. Given a trace s0, . . . , sk, the agent receives the reward: rL(s0, . . . , sk) = ∑(ϕ,r)∈R∧s0,...,sk|=ϕ r. As before, by definition rL is bounded above and below.

Example 2. When driving from A to B after it has rained, followed by temperature below zero and very low temperature since, there is a 0.1 probability of reaching B with some damage, and 0.1 probability of not reaching B at all (with some damage). Using ϕ4 defined earlier, and A, B, d for at A, at B, damaged, respectively, we can write: (ϕ4 ∧ atlast (A ∧ ¬d ), drive, {A, B, d}), π), where π(¬A ∧ B∧d) = 0.1, π(¬A∧¬B∧d) = 0.1, π(¬A∧B∧¬d) = 0.8. If it has only rained and the temperature was not high since, then these probabilities drop to 0.01. We can write: (ϕ3 ∧ ¬ϕ4 ∧ atlast(A ∧ ¬d), drive, {A, B, d}), π), where π(¬A ∧ B ∧ d) = 0.01, π(¬A ∧ ¬B ∧ d) = 0.01, π(¬A ∧ B ∧ ¬d) = 0.98. To reward the robot for delivering coffee to Ann only if she requested it earlier, we can write (〈true∗ ; RqstAnn, (¬DlvdAnn)∗ ; DlvdAnn〉end , 10).

LDLf has the same expressive power as RE. Hence, dependence on non-regular constructs cannot be specified by RDPs. For example, it is not possible to express something that says that the robot will be rewarded if the number of coffee cups served is equal precisely to the number of requests made - this requires the strength of a context-free language.

4 Solving RDPs

RDPs are attractive because they provide a natural way of using the rich, yet intuitive, language of regular expressions to specify a decision process in which transitions and rewards can depend on an unbounded history, unlike, for example, k-order MDPs. Of course, the ability to specify them is of little use if we cannot solve them. Using the well-known relationship between LDLf formulas and automata, we can exploit a construction used in past work on decision processes with non-Markovian reward, to automatically transform RDPs into MDPs, on which we can apply known methods. This makes RDPs a useful tool for specifying more complex decision processes, that combined with existing automated tools for constructing a DFA from an LTLf /LDLf formula (e.g., https://flloat.herokuapp.com [Favorito, 2018] http://ltlf2dfa.diag.uniroma1.it [Fuggitti, 2018]), can save the modeler the effort and potential errors associated with attempting to transform them manually into MDPs.

In principle, one could directly apply Monte-Carlo methods to solve RDPs. Yet, one must still be able to recognize which formulas are satisfied by the current trace, and this is most efficiently and conveniently done by tracking the state of the formula using the construction described above.

Given a RDP ML = 〈P, A, S, trL, rL, s0〉 as above, we can construct an equivalent MDP M as follows: Let T be the set of quadruples (ϕ, a, P ′ , π(P ′ )) defining trL. Let R be the set of pairs (ϕ, r) defining rL. Enumerate the quadruples in T as (ϕ1, a1, P ′1 , π(P ′1 )), . . . , (ϕm, am, P ′m, π(P ′m)), and the pairs in R as (ϕm+1, rm+1), . . . , (ϕn, rn). For each formula ϕi, build the corresponding DFA Ai = 〈2P , Qi, δi, Fi, , qi,0〉 that accepts exactly those traces that satisfy ϕi. Here, 2P , the set of all truth assignments to the propositions in P, is Ai's alphabet, Qi is its state space, qi,0 is the initial state, δi is its transition function, and Fi is the set of accepting/goal states. For details of this well known construction see [De Giacomo and Vardi, 2013; Brafman et al., 2018]. The complexity of generating a deterministic automaton for ϕi is 2EXPTIME, and its size is doubly exponential in the worst case. In practice, this transformation often does not involve exponential blow up and yields compact automata [Tabakov and Vardi, 2005]. We define the MDP M = 〈P ′ , Q, tr, r, q0〉 where

• Q = S ×Q1 × · · · ×Qn
• P ′ extends P with propositions that capture the states of A1, . . . , An. (The finite state of Ai can be encoded using log(|Qi|) propositions.)
• tr((s, q1, . . . , qn), a, (s′ , q′1 , . . . , q′n )) = trL(¯ s, a, s′ ) if (1) there exists a (unique by assumption) 1 ≤ i ≤ m such that qi ∈ Fi, (2) ¯ s is some trace that satisfies ϕi, and (3) for every 1 ≤ j ≤ n we have q′i = δi(qi, s′ ). Otherwise, tr((s, q1, . . . , qn), a, (s′ , q′1 , . . . , q′n )) = 0.
• r((s, q1, . . . , qn), a) = ∑{i∈{m+1...,n}|qi∈Fi} ri
• q0 = (s0, q1,0, . . . , qn,0)

In words: the MDP state reflects the states of the RDP and all automata tracking the satisfaction of ϕ1, . . . , ϕn. The initial state is the RDP's initial state combined with the initial states of all automata. The transition function updates the RDP state component identically to trL, and deterministically updates the state of each automaton using its transition function. Note that the automata transitions depend on the new RDP state s′ , and recall s′ reflects the last action, too. Our requirement on the quadruples ensures that for every action, there is exactly one formula that is satisfied (or, for inapplicable actions, no formula). Finally, the reward is the sum of the rewards associated with formulas satisfied by the current trace, which correspond exactly to all automata entering an accepting state. The computation tree ΥM of NMDP M =

〈P, A, S, tr, r, s0〉 is defined by induction as follows.

• The root of ΥM is s0.
• If s0, . . . , sk is a node of ΥM, then for each action a and state s′ such that tr((s0, . . . , sk), a, s′ ) > 0, the node s0, . . . , sk in ΥM has a successor s0, . . . , sk, s′ , and the edge between them is labeled a, (tr((s0, . . . , sk), a, s′ ), r(s0, . . . , sk, s′ ).

The computation tree of an MDP is similarly defined.

Lemma 1. Given RDP ML = 〈P, A, S, trL, rL, s0〉 let M = 〈P, A, S, tr, r, s0〉 be the MDP constructed as above. ML and M generate computation trees (and hence sets of traces) that are isomorphic.

Proof (sketch). We map nodes in ML's computation tree to nodes in M's computation tree as follows: The RDP state component of the MDP state is identical to the RDP state in ML. The value of Q1 × · · · × Qn is a deterministic function of the sequence of RDP states. Since the Qi states encode the satisfiability of the formulas ϕ1, . . . , ϕn, there is a one-to-one correspondence between traces in which Qi reaches a final state and ones in which ϕi is satisfied. This implies that the same transitions are possible in both cases, and the same rewards are obtained. The formal proof proceeds by induction on the length of the trace/branch.

Theorem 1. An optimal RDP policy can be computed in 2EXPTIME; finding a policy with value ≥ c is 2EXPTIME-hard.

Proof (sketch). Membership comes from the construction above: the generation of the automata from the formulas is in 2EXPTIME (but their factored encoding is only exponential) while computing a policy for an MDP is polynomial in |S||A|. Hardness comes from Planning for LDLf (actually its fragment LTLf ) goals in fair FOND, see [De Giacomo and Rubin, 2018] which is a special case of stochastic planning, and a goal can be captured by a reward + transition to a sink state.

A policy ρ is regular if it has the form {(ϕi, ai)} where ϕi is an LDLf formula and ai an action, such that for every trace s0, . . . , sk reachable given ρ, either no transition is possible after s0, . . . , sk, or there exists exactly one (ϕi, ai) ∈ ρ such that s0, . . . , sk |= ϕi. A by-product of the results above is:

Theorem 2. Every RDP has a regular policy which is optimal.

Due to space restrictions, proofs of most results are omitted.

5 Partially Observable Stochastic Domains

MDPs assume the agent is always aware of its current state. This is unrealistic for many, if not most, real-world domains in which the state is only partially observable. Consequently, much effort has been made to solve partially observable Markov decision processes (POMDPs) [Cassandra et al., 1994] and partially observable contingent planning problems [Albore et al., 2009].

The standard approach for solving partially observable problems is to transform them into fully observable problems over a different state space. POMDPs can be transformed into an (fully observable) MDP over (probabilistic) belief states, i.e., distributions over world states, and contingent planning problems can be transformed into classical planning problems over classical belief states, i.e., sets of world states.

However, just the formulation of a partially observable model presupposes knowledge of the nature of the unobservable part of the world. This is a serious drawback when we consider the problem of learning such domains from observable data when no additional domain knowledge exists. This problem is well-known, and has given rise to models such as predictive-state representations (PSR) [Singh et al., 2001] whose core idea is to work with the observations only. NMDPs and RDPs have this feature, too.

Lemma 2. For every POMDP M = 〈P, S, A, T r, R, O, PO, b0〉, there exists an NMDP M ′ = 〈PO,A, 2PO , tr, r, ϵ〉, where ϵ, the empty string, denotes the initial, empty observation, and tr and r are defined based on Tr,R, and O, such that the computation trees for M and M ′ are isomorphic.

This essentially follows from the history-based MDP formulation of a POMDP.

The key difference between the NMDP and POMDP formulation is that the former makes no reference to hidden variables/state. Thus, its policy is also based on observables only. But as noted, general NMDPs are not practically useful. Therefore, the history-based view is used only to represent finite-horizon policies. We suggest investigating RDPs as a tractable approximation of POMDPs. To understand this option, first we characterise the type of POMDPs that RDPs can capture - this can be understood from the construction of the equivalent MDP in Section 4.

Lemma 3. For every POMDP M = 〈P, S,A, Tr,R,O, PO, b0〉 if in all reachable states the value of every p ∈ P is a regular function of the past and current values (trace) of PO (i.e., p is true iff some RE over PO is satisfied), there exists an RDP with an equivalent computation tree.

Proof (sketch). If the POMDP's hidden variables are a regular function of the observable variables, then we know that they can be represented using an automaton whose alphabet is 2PO , and so its language can be represented by an LDLf formula.

The converse is also easy to show:

Lemma 4. Every RDP can be transformed into a POMDP with the same set of observable variables in which the hidden variables are a regular function of the observable variables.

This establishes the equivalence between RDPs and the restricted class of POMDPs whose hidden variables are a regular function of their observable variables.

However, we can show the following:

Theorem 3. For every infinite horizon discounted reward POMDP M, and for every ϵ > 0, there exists a RDP ML over PO, such that the optimal policy for ML is ϵ-optimal for M.

Proof (sketch). First, we prove the following claim: every finite horizon POMDP M is equivalent to a RDP with variables P = PO. Starting from the POMDP M = 〈P, S,A, Tr,R,O, PO, b0〉, we construct the history-based MDP Mh = 〈Q, A, tr, r, ϵ〉. Q contains all histories bounded by the horizon, and is thus finite. We define the corresponding RDP ML = 〈P, A, S, trL, rL, s0〉. trL is defined as follows: first, we partition, for each action, the states in Q into subsets {Qi|i ∈ Ia} such that a changes the values of exactly the same set of propositions when applied in each q ∈ Qi, and such that the marginal distribution over P ′ values in a(q) is identical for all q ∈ Qi. Note that some Qi can be singletons. Let {(Qi, aj)|i ∈ Iaj , aj ∈ A} denote all pairs of such state set and relevant action.

For every (Qi, aj) pair we consider the DFA AQi Tr defined as AQi Tr = 〈2P ,Q, δ,Qi, q0〉, where δ(q, s) = q · s. That is the new state is the history obtained by concatenating the new state with the current history. (Recall the last action is represented in the new state). The final states are Qi. Notice that all the DFAs AQi Tr for all Qi are identical except for their accepting state. From basic automata theory, we know that there is a regular expression rQi that accepts the paths, i.e., the traces in S+ leading from the initial state q0 to Qi. Hence we can express reaching Qi by the LDLf formula ϕi = 〈rQi 〉end.

As noted above, the next state distribution for states in Qi and action a is characterised by some common (P ′ , π(P ′ )). Hence, we can represent this transition by the quadruple: (ϕi, a, P ′ , π(P ′ )), and we add it to the set of quadruples T . A similar method will let us generate the elements of R. Thus, this concluded the proof of the claim.

Because of discounting, we can compute an ϵ-optimal policy to an infinite horizon POMDP by solving a finite-horizon POMDP with a sufficiently long horizon.

An important challenge for future work is finding more effective strategies for generating approximate RDP, and bounding their size. Such strategies would open the possibility of solving POMDPs by first approximating them using RDPs, and then solving the resulting RDP.

6 RDP Learning

We now outline a potential approach for learning RDPs with no background information by combining ideas from automata learning and RL. This is a purely theoretic proposal attempting to lay foundations for future practical methods. Learning algorithms might also prove useful for constructing RDPs that approximate a known POMDP.

Algorithm 1 outlines an RDP learning method. The algorithm requires access to an automata learning algorithm, such as [Lang et al., 1998; Lambeau et al., 2008], and assumes restarts. Recall that we assume there are observable variables denoting the action performed. Hence, we do not mention actions explicitly in the algorithm. Also, note that the automata for transitions are constructed so that only traces from one set Htr i are accepted. This ensures that we are never in an accepting state in more than one component M tr i , and so only one quadruple formula is satisfied.

Algorithm 1 Pseudocode for Learning Finite NMDPs

• 1: Generate a set of traces with their associated rewards
• 2: The set of propositions of the RDP corresponds to the set of observable propositions
• 3: for all traces τ do
• 4: Compute (a, P ′ , π(P ′ ))τ the empirical distribution over traces extending τ with action a and one observation.
• 5: Group traces with identical (a, P ′ i , π(P ′ i )) into sets {Htr i |i ∈ T }.
• 6: Group traces with identical reward into sets {Hr j |j ∈ R}
• 7: for all i ∈ T do
• 8: Learn an automatonM tr i that accepts Htr i and rejects all Htr j for j ̸= i
• 9: Generate formula ϕtr i that captures language of M tr i
• 10: Insert the quadruple (ϕtr i , a, P ′ i , π(P ′ i )) to trL
• 11: for all i ∈ R do
• 12: Learn an automatonM r i that accepts Hr i and rejects all Hr j for j ̸= i
• 13: Generate formula ϕri that captures language of M r i
• 14: Insert the pair (ϕri , ri) into rL

We can control the quality of the approximation by increasing the number of samples in each set of traces to obtain more accurate estimates of (P ′ i , π(P ′ i )). We note that, unfortunately, automata learning, used in Lines 8 and 12, is a difficult problem, with many hardness results as far as sample complexity, unless input beyond positive and negative instances is available [Angluin et al., 2013]. However, practical algorithms developed in the area of grammatical inferences exist [Lang et al., 1998; Lambeau et al., 2008].

7 Discussion and Summary

It is worthwhile to compare RDPs with the Predictive State Representation model (PSR) [Singh et al., 2001]. PSRs were introduced explicitly to model dynamical systems without referring to a hidden state, and RDPs are also motivated by the desire to model rich dynamical systems without postulating some hidden state structure. A basic element of a PSR is its set of core tests, where a test is simply a sequence of actions and observations q = a1 o1 · · · an on . A key computation for a test is its probability given a history h = a1o1 · · · amom. That is, p(q|h) is the probability that following history h, one will observe o1 · · · on if one performs a1 · · · an . In a linear PSR, one can compute p(q|h) for every q and every finite h as a linear combination of p(q1|h), · · · , p(qn|h), where q1, . . . qn are the core tests. n is called the dimensionality of the system. [Singh et al., 2001] proved that a linear PSR can represent any POMDP using no more core tests than the number of underlying states of the POMDP. Later work showed examples of non-linear PSRs that require exponentially fewer tests than an equivalent POMDP model [Rudary and Singh, 2003] and algorithms for learning PSRs [Singh et al., 2003].

Given this representational power of PSRs, we have the following progression in terms of expressivity:

Earlier, we saw that RDPs are equivalent to a (most likely strict) sub-class of POMDPs. So RDPs are most likely less expressive than POMDPs. Support for this conjecture comes from the fact that, unlike POMDPs, RDPs can be translated into a, possibly much larger, but still finite MDP. Interestingly, if we replace the stochastic transition function in RDPs and POMDPs with a non-deterministic one (obtaining the contingent planning model in the latter), the two models have equivalent expressive power [Brafman and De Giacomo, 2019].

Complexity-wise, a similar relation exists. There is a polynomial reduction from POMDPs to linear PSRs, so PSRs are at least as hard to solve as POMDPs. POMDP optimization is undecidable for the infinite horizon case, while for (factored) RDPs, it is 2EXPTIME, thus much easier. For finite horizons, solving flat POMDPs is in PSPACE. For a factored model, one likely incurs another exponential blowup (thus EXPSPACE) so it is likely no easier then RDP optimization. However, the 2EXPTIME complexity of RDPs is for unbounded plan sizes, and with bounded horizon, the problem should be easier.

Moreover, one exponential in the complexity of RDP optimization comes from the need to generate a factored representation of the automaton for each formula, which is worst-case exponential in the size of the formulas used (and thus, the reduction from RDPs to POMDPs is not polynomial). There is evidence that this transformation is fast in practice, and yields compact automata [Tabakov and Vardi, 2005], and if one were to restrict attention to RDPs with bounded size formulas, one could still refer to arbitrary events in the past, yet get rid of this exponential factor. Hence, RDPs with bounded formulas should be much easier to solve than POMDPs.

So while precise characterization of the finite-horizon case for RDPs is still missing, RDPs seem to offer a middle ground between MDPs and POMDPs: they are more expressive and potentially more succinct than k-order MDPs, are easier to solve than POMDPS, yet refer only to observable variables.

Summary. We studied a newmodel for controlled dynamical systems. This model allows for compact and convenient specification of non-Markovian transitions and rewards, generalizes k-order MDPs, can ϵ-approximate POMDPs, yet makes no reference to hidden variables. This last property makes it a potential target model for learning dynamical systemwithout background knowledge. In future work we hope to farther explore methods for approximating POMDPs using RDPs, and to develop practical RDP learning algorithms. Finally, RDPs suggest that it may be worth studying additional models that restrict the nature of the hidden state of a POMDP for which better inference and learning algorithms may exist.

Acknowledgements

This work is supported in part by the Israel Ministry of Science and Technology grant 877017, the Lynn and William Frankel Center for Computer Science, and Sapienza project "Immersive Cognitive Environments".