In the emerging area of personal health tracking, one records one’s pulse, blood pressure, glucose levels, activity levels, nutritional information and much more, in an attempt to learn how to improve one’s physical and mental health. In this domain, the state of many variables of interest and the effects of various actions are most likely not Markovian functions of the value of the most recently measured variables. Hence, applying standard, MDP-based, RL algorithms [Sutton and Barto, 1998] to a state model consisting of the value of these observed variables will most likely lead to sub-optimal behavior.

Motivated by such application domains, Regular Decision Processes (RDPs) [Brafman and De Giacomo, 2019] have been recently introduced as a non-Markovian extension of MDPs that does not require knowing or hypothesizing a hidden state. An RDP is a fully observable, non-Markovian model in which the next state and reward are a stochastic function of the entire history of the system. However, this dependence on the past is restricted to regular functions. That is, the next state distribution and reward depends on which regular expression the history satisfies.

An RDP can be transformed into an MDP by extending the state of the RDP with variables that track the satisfaction of the regular expression governing the RDP dynamics. Thus, essentially, to learn an RDP, we need to learn these regular expressions. For example, in the context of personal health-tracking, one might learn which sequences of activities and measurements make a state of hyperglycaemia, hypoglycaemia, or depression, likely, and consequently, adapt behavior policies that prevent them.

An optimal policy for an RDP is a mapping from regular properties of history to actions. Thus, it provides users with clear, understandable guidelines, based on observable properties of the world, in contrast to, e.g., arbitrary hidden states in a learned POMDP, or unclear features in a neural network.

This paper makes two contributions to the emerging theory of RDPs. Our first contribution is the use of a deterministic Mealy Machine to specify the RDP. For each state and action, this Mealy machine emits as its output, a class label. This class label is associated with a distribution over the underlying system states and a reward signal. This idea extends the use of Mealy Machines to specify non-Markovian rewards, introduced recently by [Camacho et al., 2019], to RDPs. Our second, and main contribution is to use this idea to formulate the first algorithm for learning RDPs from data, and to evaluate it on two non-Markovian domains. Our algorithm identifies, through exploration, histories that have similar dynamics based on their empirical distributions and then learns a Mealy Machine that outputs, for each history, an appropriate label. Then, we solve this Mealy Machine to obtain an optimal policy. This can be done by either reducing it to an explicit MDP, or by using the Mealy Machine to provide the distributions needed for running MCTS [Kocsis and Szepesv´ari, 2006; Silver and Veness, 2010]. This algorithm was implemented and tested on two domains modelled as RDPs, demonstrating its ability to learn RDPs from observable data and to generate a near-optimal policy for these models.

We assume familiarity with MDPs, recalling basic notation only. We briefly discuss NMDPS, RDPs, and Mealy Machine.

2.1 MDP and NMDPs

A Markov Decision Process (MDP) is a tuple M = is the set of states, A a set of actions, is the transition function that returns for every state s and action a the distribution over the next state. is the reward function that returns the real valued reward received by the agent after performing action a at state is the initial state.

A solution to an MDP is a policy that maps each state to an action. The value of expected sum of discounted rewards when starting at state s and selecting actions based on policy, denoted , maximizes the expected sum of discounted rewards for every starting state . Such a policy always exists for infinite horizon discounted reward problems.

A non-Markovian Decision Process (NMDP) is defined identically to an MDP, except that the domains of Tr and R are finite sequences of states instead of single states: . With this dependence on the history, to act optimally, a policy must, in general, take the form: is a partial function defined on every sequence reachable from under . We define reachability under inductively: is reachable; if is reachable and is reachable.

The value of a trace is its discounted sum of rewards: . Because we assume the reward value is lower and upper bounded and , this discounted sum is always finite and bounded from above and below.

2.2 RDPs

A Regular Decision Processes (RDP) [Brafman and De Gia- como, 2019] is a factored NMDP in which the dependence on history is restricted to regular functions. By factored, we mean that its states consist of assignments to state variables and the transition function exploits this structure. Here, we assume Boolean state variables for convenience. To specify the dependence of the transition and reward on the history, we need a language that can compactly specify sets of histories. Histories are essentially strings over an alphabet of states (for convenience, we can assume that the last action executed is part of the state). Regular expressions (RE) are an intuitive and much used language for specifying languages, i.e., sets of strings. However, they do not have the logical structure to exploit more fine-grained properties of the internal assignments of a state, and do not efficiently support various useful operations on sets of strings. Linear dynamic logic on finite traces (LDL) [De Giacomo and Vardi, 2013] combines linear-time temporal logic (LTL) with the syntax of propositional dynamic logic (PDL) but interpreted over finite traces. LDLhas the same expressive power as RE, allows us to refer to properties of states, and supports simple specification of conjunction, disjunction, and negation. RDPs use LDLformulas to specify properties or classes of histories. To simplify their exposition, in this paper we do not make explicit use of them, and it is enough to know about RE and to think of each formula we mention as specifying an RE. For more details, see [Brafman and De Giacomo, 2019].

An RDP is a tuple is aset of propositions inducing a state-space S with as the initial state. A is the set of actions. is a transition function represented by a finite set T of quadruples of the form: formula over is the set of propositions affected by a when holds, and is a joint-distribution over describing its post-action distribution. The basic assumption is that the value of variables not in is not impacted by a.

If are all quadruples for a, then the ’s must be mutually exclusive, i.e., is inconsistent, for . We also assume that the formulas are exhaustive.Letting denote projected to is defined as follows: if quadruple is the (single) one s.t. and and agree on all variables in

That is, given current trace and action a let the quadruple with a condition that is satisfied by (by assumption, exactly one such exists). is a possible next state only if it assigns propositions not in exactly the same value to as does , i.e., they are not impacted by the action. Then, the probability that next state equals the probability assigns to the value of the propositions in

The reward function is specified via a finite set R of pairs of the form is an LDLformula over P, and is a real-valued reward. Given a trace , the agent receives the reward: . By definition is bounded above and below.

2.3 Mealy-Machine

A Mealy machine is a deterministic finite-state transducer whose output values are determined both by its current state and the current inputs. Formally, a Mealy Machine is a tuple is the finite set of states, is the initial state. is the input alphabet and is the output alphabet. The transition function maps pairs of state and input symbol to the corresponding next state. The output function maps pairs of state and input symbol to the corresponding output symbol.

Let be the set of LDLformulas that specify the transitions and rewards of an RDP. This set is finite because T and R are finite. Since each formula is equivalent to an RE, there is an automaton that can track its satisfaction [Baier et al., 2008; De Giacomo and Vardi, 2013]. The automaton’s input alphabet is the product of the sets of RDP states and actions, and it accepts a history IFF it satisfies the corresponding formula. Let be the automaton tracking . Let be the product automaton of all the ’s. This automaton will be at an accepting state of exactly one of its transition tracking components given any string because the transition formulas are mutually exclusive and exhaustive. In addition, some reward tracking automata may also accept.

Building on the idea of using Mealy Machines to specify non-Markovian rewards [Camacho et al., 2019], our key observation is that an RDP can also be specified by a Mealy Machine. The machine’s input alphabet is the product of the sets of RDP states and actions. Its output function assigns to each triple of machine state , RDP state and action a, a set of propositions, , a distribution over their value in the next RDP state, and a reward.

Such a Mealy Machine represents an RDP because we can reconstruct the RDP from it as follows: Given history h, let s(h) be the Mealy Machine state reached on string h from its initial state. Let be the current RDP state. The Mealy Machine output provides us with a specification of the transition function and reward for history and action a.

The Mealy Machine that describes an RDP is constructed from the product automaton M defined above by adding to it an output function. Let be a state of M, such that is the (only) transition tracking automaton in an accepting state. That is is an accepting state of . Let be the formula which accepts, and let be the corresponding quadruple. Let r be the sum of rewards associated with all the reward tracking automata that are in an accepting state in s. Define , i.e., the propositions and distributions associated with and the sum of rewards of accepting reward-tracking automata.

The correctness of this construction follows from the definition of RDPs and the correctness of the construction of automata tracking the satisfiability of LDLformulas. The main benefit of this representation of an RDP is that it can serve as a target for learning algorithms that use existing methods for learning Mealy Machines, as we do in Section 4.

To solve an RDP, we can transform it into an MDP by taking the product of with the original state space of the RDP [Brafman and De Giacomo, 2019]. The state reflects the relevant aspects of the entire history. Every deterministically, but induce a Markovian stochastic transition over ’s reward function is fully specified given the state, the current RDP state, and the current action. can be solved using standard MDP solution techniques [Put- erman, 2005]. We use UCT [Kocsis and Szepesv´ari, 2006], an MCTS algorithm, because MCTS can be applied to RDPs without generating explicitly. We maintain the current RDP state, i.e., the most recent set of observations, and the state of the Mealy Machine. From , for each action and current RDP state, we can obtain as output the information needed to sample the next set of observations and rewards. The new observations replace the old ones, and are used (with the action) to update the Mealy Machine. The choice of which action to apply follows the standard UCB1 criterion [Auer et al., 2002]

, with used here instead of the current RDP state as it captures all history dependent properties of interest.

MDP learning algorithm rely on the Markov assumption and full observability of the state for their correctness. These algorithms are not suitable for learning non-Markovian models, such as an RDP. Instead, we can exploit the alternative, Mealy Machine representation of RDPs and use Mealy Machine learning algorithms to learn the RDP model. More specifically, we use Flexfringe [Verwer and Hammerschmidt, 2017] (using EDSM with the Mealy Machine heuristic) to learn a Mealy Machine that represents the underlying RDP. Then, we use MCTS to generate an optimal policy for the learned model.

Thus, our approach can be characterized as a Model-based RL algorithm for non-Markovian domains.

4.1 Learning Algorithm Overview

Algorithm 1 provides the pseudo-code of our learning algorithm S3M (Sample, Merge, Mealy Machine). The next subsections describe each step in detail.

A Mealy Machine learning algorithm expects input of the form (input sequence, output), where output can be the last output following this input sequence. Thus, in our case, we need to generate inputs of the form (), where is a trace and is a distribution over the next observation (RDP state) and reward. To create this input, we first generate traces from the RDP by interacting with the environment (Line 3). These are traces of the form the action executed at the step, is the reward received following its execution, and is the next RDP state. We use to denote the RDP state to stress that it is fully observable.

To transform these traces to pairs of the form (identify a set of histories for which we have enough samples (min samples). We refer to the empirical next-state distributions associated with these histories as base distributions (L. 4). Next, in Lines 6-12, the rest of the histories are merged with the closest history based on the distance of their distribution from one of the base distributions. The merge choice depends on a parameter , and we try a range of possible values, attempting to balance model size and accuracy. Associating each of the resulting distribution with some symbol, we can now provide the needed input to the Mealy Machine learning algorithm in the form of pairs (trace,distribution) (L.14). Finally, by taking the product of the learned Mealy Machine with the RDP’s state space, we obtain an MDP that can be solved for an optimal policy.

We repeat this process multiple times, each time with a more informed state space. Initially, we use the RDP state space to guide exploration. Once we learn a Mealy machine, or improve our current Machine, we update the state space to reflect our new model to help better guide exploration.

4.2 Sampling

To learn the SDR model we need to generate sample traces. We considered two methods for doing this. One is purely exploratory and does not attempt to exploit during the learning process, while the other does.

The Pure Exploration approach uses a stochastic policy that is biased towards actions that were sampled less. More specifically, for every and , where is the RDP state space, define:

Here, n(a,s) stands for the number of times action a was performed in state s of the RDP. This distribution favours actions that were sampled fewer times in a state.

The Smart Sampling approach is essentially Qlearning [Watkins and Dayan, 1992] with some exploration using the above scheme. Specifically, Q values are maintained for each state-action pair, where states are defined and updated as above, starting with a single-state Mealy Machine. Q(s,a) is initialize to 0 for all states and actions, and are updated following each sample of the form using Q(s,a) = probability , we select the greedy action in state s, and with probability we sample an action based on the distribution defined in Equation 1.

4.3 Trace Distributions

Next, we associate with every trace encountered a set of propositions and a distribution over their probability. (Note that each prefix of a trace is also a trace.) Let h = be a given trace. We define , the set of propositions affected by action a given history to be all propositions such that there exists a trace in our sample where differ on the value of p. We expect to be small, typically, because action effects are usually local. Next, we compute the empirical post-action distribution over for history h, RDP state o and action a. That is, the frequency of each assignment to in the last RDP state of over traces of the form in our sample.

4.4 Merging Histories and Their Distributions

By modeling a domain as an RDP, our basic assumption is that what dictates the next state distribution of a history is the class of regular expressions it belongs to. Hence, many different histories are likely to display similar behavior because they are instances of the same regular expression. Of course, we do not know what these regular expressions are, and because of the noisy nature of our sample, we cannot expect two histories that belong to the same class to have the same empirical distribution. Moreover, many histories will be sampled rarely, in which case their empirical next-state distribution is likely to significantly differ from the true one. For this reason, we attempt to cluster similar histories together based on their empirical next-state distribution, using KL Di-

vergence [Kullback and Leibler, 1951] as a distance measure. However, we consider merging only histories that affect the same set of propositions. Our goal is to create clusters s.t. each cluster represents

a certain distribution and each trace is assigned to a single

cluster. We create the clusters bottom-up. First, we create a single cluster for each trace hoa as described in 4.2. Each such cluster has also a weight w denoting the number of samples used to create it. Then, for every two clusters with distributions and (affecting the same propositions) with weights

Note that condition 1 is required for to be well defined. The new cluster has weight and a distributionP such that:

If a cluster has multiple other clusters with which it can merge, then the one with the smallest KL divergence is selected. We repeat this procedure until no merges are possible.

Next, for each distribution P whose weight < min samples, we find the distribution Q from the above clusters that affects the same set of propositions such that is well defined and minimal, and merge the two using Equation 2 to obtain the new distribution. Notice that such a merge implies that the support of P is a subset of the support of Q.

The above is repeated for different values of , resulting in different models. We now explain how we select the final model. Each model has the form . Each is a distribution over the set of assignments to some subset of the RDP’s set of propositions, with one such distribution associated with each cluster. maps each history in the sample to the distribution associated with its cluster.

To compare the models we define the following loss function:

Where is the size of the support of distribution . Thus, our loss function is the log-likelihood of the data with a regulizer that penalizes models with many clusters, and models with ”mega”-clusters with large support.

4.5 Generate a Mealy Machine and an MDP

We now use the flexfringe algorithm [Verwer and Hammer- schmidt, 2017] to learn a Mealy Machine from our data. With every trace in our original sample, we associate the index of the cluster it belongs to. The result is a Mealy Machine representing the RDP.

Let be the learned MealyMachine. From this Mealy Machine we can generate an MDP is the (observable) state space of the RDP; A is the set of RDP actions; is the initial RDP state. Tr and R are defined as follows: For a given state of M and action a, let transforms the Mealy Machine state deterministically based on the transition function T of , i.e., to . It transforms the RDP state based on the distribution (leaving the value of all propositions in unchanged). Finally, . The optimal policy for this MDP is optimal for the RDP – associating actions with regular functions of the RDP history.

As this is the first paper to explore the problem of learning and solving RDPs, our goal is to evaluate the ability of our algorithms to address this problem, to assess our ability to scale-up, and to set up a baseline for future work. To this effect, we define two new RDP domains and use them to test the two variants of our algorithm.

5.1 The Domains

We define two domains: Non Markovian Multi-Arm Bandit (MAB) and Rotating Maze. The original MAB is stateless. In our version transition probabilities depend on the history of success for each arm, making it a two states domain. The Maze problem is based on an agent navigating on a grid toward a designated location, while the orientation might change. For Mealy Machine learning we used the EDSM implementation from the FlexFringe library [Verwer and Hammerschmidt, 2017]. To solve the learned RDPs we use UCT, extended to RDPs, and compare it with a baseline of Rmax – a model-based MDP learning algorithm [Brafman and Tennenholtz, 2002]. This learning algorithm essentially assumes (wrongly) that the RDP transitions are Markovian.

Multi-Arm Bandit Domain

The Multi-Arm Bandit (MAB) is the simplest class of RL domains. Standard MAB is state-less – hence there are no transition function to learn. At each step the agent chooses one of n actions, and receives a reward that depends (possibly stochastically) on the choice of action. Our Non-Markovian MAB extends this by making the probability of receiving a (fixed-size) reward depend on the entire history of previous actions. It is essentially a two-state RDP – where the state indicates whether a reward was received or not. We created three MAB-based RDP models:

1. RotatingMAB: Let be a vector that assigns the probability of winning the reward for each action. This probability shifts right (i.e., +1 mod n) every time the agent receives a reward. Therefore, the probability to win for each arm depends on the entire history, but via a regular function.

2. MalfunctionMAB: One of the arms is broken, s.t. after the corresponding action is performed k times, its probability of winning drops to zero for one turn.

3. CheatMAB: There exists a sequence of actions s.t. after performing that sequence, all actions lead to a reward with probability 1 from that point on.

In our experiment we used 2 arms/actions for all of the three variations of the domain. The winning probabilities of the machines of the RotatingMAB were (0.9,0.2), for CheatMAB (0.2,0.2) and for MalfunctionMAB (0.8,0.2).

Maze Domain

The Maze domain is an grid, where the agent starts in a fixed position. The possible actions of the agent are up/down/left/right. These actions succeed 90% of the time, and in the rest 10% the effect is to move in the opposite direction. The goal of the domain is to get to the designated location where a final reward is received. In a normal MDP this task would be quite easy to solve using conventional RL algorithms. However, in this maze, every three actions the agent’s orientation changes by . Thus, the effects of the actions are a regular function of the history. In our experiment we used a maze, where the goal is five steps away from the initial position.

5.2 Results

For each domain we used three configurations: (1) Random Sampler: S3M with Pure Exploration sampling; (2) Smart Sampler: S3M with Smart Sampling; (3) RMax: The model-based RL algorithm Brafman and Tennenholtz, 2002] that uses the RDP states as its states, used as baseline.

The results are displayed in Figure 1. We show the value of the optimal policy (Optimal), the quality of the policies learned by the above three algorithms at each evaluation step, and the average reward accumulated during learning by the first two algorithms. Each experiment was repeated five times. We plot the average over these five repetitions with error bars representing the std. To evaluate the quality of the current policy during the learning process, the optimal policy for the current model was computed online using UCT. 50 trials were conducted using the currently learned Mealy Machine. MAB trials were 10 steps long, and Maze trials were terminated after 15 steps if the goal was not reached. The graph shows the average (over 50 trials) per-step rewards of these policies (averaged over 5 trials), and the average (over 5 trials) accumulated reward obtained as S3M was sampling traces.

Overall, S3M Smart Sampler does quite well, yielding optimal or near optimal average reward. It also does well in terms of accumulated rewards. Random Sampler does reasonably well, too, except on the CheatMAB, but its accumulate reward is typically much worse. , which cannot capture the non-Markovian dynamics does much worse. Even in the Maze domain, a closer look reveals that the difference in its performance is exactly what we would expect when we ignore the non-Markovian behavior – this margin in that case is simply smaller than in the MAB domains.

Proper exploration is a key issue in RL. In the case of RDPs, it is not enough to explore states because we need to gather statistics on histories. In this respect, it is interesting to compare the performance of the two sampling approaches. We expected that Smart Sampler will accumulate more reward, as it does more exploitation and this exploitation is informed by the learned Mealy Machine, and hence takes history into account. Indeed, in the MAB domain, we see such behavior: S3M with smart sampling converges to an optimal or near-optimal policy

Figure 1: Results

quickly, and the accumulated rewards increase steadily, while the random sampler does worse. This is especially pronounced in the Cheat MAB domain, which is the most complex domain. We believe the reason for the weak performance of random sampling in this domain is that too many of the samples are not along the more interesting traces that discover the ”cheat” sequence. Therefore, it is more difficult for it to learn a good Mealy Machine that can exploit it. Surprisingly, in the Maze domain, unlike in the MAB domains, there is no significant difference between the two S3M versions. We hypothesize that in Maze, there is more to learn about the general behavior of transitions because there are more states, and the random sampler generates more diverse samples that provide a more accurate statistics on various states. The smart sampler, on the other hand, does not. Moreover, while the domain has more states, the regular expression that governs the dynamics is relatively simple, and so the random sampler is still able to learn the corresponding automaton.

Generally speaking, we see a high correlation between the

quality of the samples collected by the sampler and the quality of the learned model: when the average reward of the samples is monotonically increasing so does the averaged reward of the policy obtained by MCTS. An open question is what is the exact relation: do samples that concentrate along desirable traces yield better Mealy Machines, or is it the case that because we learn a better Mealy Machine, the traces generated by the Smart Sampler have higher rewards (naturally).

We presented the first algorithm for learning Regular Decision Processes. By viewing the RDP specification as a Mealy Machine, we were able to combine Mealy Machine and RL algorithms to obtain an algorithm for learning RDPs that quickly learns a good Mealy Machine representation in our experiments. Naturally, there is much room for improvement, especially in methods for better sampling and better aggregation of histories.

[Auer et al., 2002] Peter Auer, Nicol`o Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235–256, 2002.

[Baier et al., 2008] Jorge A. Baier, Christian Fritz, Meghyn Bienvenu, and Sheila McIlraith. Beyond classical planning: Procedural control knowledge and preferences in state-of-the-art planners. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), Nectar Track, pages 1509–1512, Chicago, Illinois, USA, July 13-17 2008.

[Brafman and De Giacomo, 2019] Ronen I. Brafman and Giuseppe De Giacomo. Planning for ltlf /ldlf goals in non-markovian fully observable nondeterministic domains. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 1602–1608, 2019.

[Brafman and Tennenholtz, 2002] Ronen I. Brafman and Moshe Tennenholtz. R-MAX - A general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 3:213–231, 2002.

[Camacho et al., 2019] Alberto Camacho, Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. McIlraith. LTL and beyond: Formal languages for reward function specification in reinforcement learning. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI), 2019.

[De Giacomo and Vardi, 2013] Giuseppe De Giacomo and Moshe Y. Vardi. Linear temporal logic and linear dynamic logic on finite traces. In IJCAI-13, pages 854–860, 2013.

[Kocsis and Szepesv´ari, 2006] Levente Kocsis and Csaba Szepesv´ari. Bandit based monte-carlo planning. In Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18-22, 2006, Proceedings, pages 282–293, 2006.

[Kullback and Leibler, 1951] Solomon Kullback and Richard Leibler. On information and sufficiency. Annals of Mathematical Statistics, 22(1):79–86, 1951.

[Puterman, 2005] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 2005.

[Silver and Veness, 2010] David Silver and Joel Veness. Monte-carlo planning in large pomdps. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, pages 2164–2172, 2010.

[Sutton and Barto, 1998] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998.

[Verwer and Hammerschmidt, 2017] Sicco Verwer and Christian A. Hammerschmidt. flexfringe: A passive automaton learning package. In 2017 IEEE International Conference on Software Maintenance and Evolution, ICSME 2017, Shanghai, China, September 17-22, 2017, pages 638–642, 2017.

[Watkins and Dayan, 1992] Christopher J. C. H. Watkins and Peter Dayan. Technical note q-learning. Machine Learning, 8:279–292, 1992.