RECURRENT POLICY NETWORKS
Year: 2019

Abstract:
Recurrent neural networks (RNNs) are an effective representation of control policies for a wide range of reinforcement and imitation learning problems. RNN policies, however, are particularly difficult to explain, understand, and analyze due to their use of continuous-valued memory vectors and observation features. In this paper, we introduce a new technique, Quantized Bottleneck Insertion, to learn finite representations of these vectors and features. The result is a quantized representation of the RNN that can be analyzed to improve our understanding of memory use and general behavior. We present results of this approach on synthetic environments and six Atari games. The resulting finite representations are surprisingly small in some cases, using as few as 3 discrete memory states and 10 observations for a perfect Pong policy. We also show that these finite policy representations lead to improved interpretability.

heading: 1 INTRODUCTION
text: Deep reinforcement learning (RL) and imitation learning (IL) have demonstrated impressive performance across a wide range of applications. Unfortunately, the learned policies are difficult to understand and explain, which limits the degree that they can be trusted and used in high-stakes applications. Such explanations are particularly problematic for policies represented as recurrent neural networks (RNNs) (Mnih et al., 2016; Mikolov et al., 2010), which are increasingly used to achieve state-of-the-art performance (Mnih et al., 2015; Silver et al., 2017). This is because RNN policies use internal memory to encode features of the observation history, which are critical to their decision making, but extremely difficult to interpret. In this paper, we take a step towards comprehending and explaining RNN policies by learning more compact memory representations.
Explaining RNN memory is challenging due to the typical use of high-dimensional continuous memory vectors that are updated through complex gating networks (e.g. LSTMs, GRUs (Hochreiter & Schmidhuber, 1997; Chung et al., 2014; Cho et al., 2014)). We hypothesize that, in many cases, the continuous memory is capturing and updating one or more discrete concepts. If exposed, such concepts could significantly aid explainability. This motivates attempting to quantize the memory and observation representation used by an RNN to more directly capture those concepts. In this case, understanding the memory use can be approached by manipulating and analyzing the quantized system. Of course, not all RNN policies will have compact quantized representations, but many powerful forms of memory usage can be captured in this way.
Our main contribution is to introduce an approach for transforming an RNN policy with continuous memory and continuous observations to a finite-state representation known as a Moore Machine. To accomplish this we introduce the idea of Quantized Bottleneck Network (QBN) insertion. QBNs are simply auto-encoders, where the latent representation is quantized. Given a trained RNN, we train QBNs to encode the memory states and observation vectors that are encountered during the RNN operation. We then insert the QBNs into the trained RNN policy in place of the “wires” that propagated the memory and observation vectors. The combination of the RNN and QBN results in a
∗Work done at Oregon State University
policy represented as a Moore Machine Network (MMN) with quantized memory and observations that is nearly equivalent to the original RNN. The MMN can be used directly or fine-tuned to improve on inaccuracies introduced by QBN insertion.
While training quantized networks is often considered to be quite challenging, we show that a simple approach works well in the case of QBNs. In particular, we demonstrate that “straight through” gradient estimators as in (Bengio et al., 2013; Courbariaux et al., 2016) are quite effective.
We present experiments in synthetic domains designed to exercise different types of memory use as well as benchmark grammar learning problems. Our approach is able to accurately extract the ground-truth MMNs, providing insight into the RNN memory use. We also did experiments on 6 Atari games using RNNs that achieve state-of-the-art performance. We show that in most cases it is possible to extract near-equivalent MMNs and that the MMNs can be surprisingly small. Further, the extracted MMNs give insights into the memory usage that are not obvious based on just observing the RNN policy in action. For example, we identify games where the RNNs do not use memory in a meaningful way, indicating the RNN is implementing purely reactive control. In contrast, in other games, the RNN does not use observations in a meaningful way, which indicates that the RNN is implementing an open-loop controller.

heading: 2 RELATED WORK
text: There have been efforts made in the past to understand the internals of Recurrent Networks (Karpathy et al., 2015; Arras et al., 2017; Strobelt et al., 2016; Murdoch & Szlam, 2017; Jacobsson, 2005; Omlin & Giles, 1996). However, to the best of our knowledge there is no prior work on learning finite-memory representations of continuous RNN policies. Our work, however, is related to a large body of work on learning finite-state representations of recurrent neural networks. Below we summarize the branches of that work and the relationship to our own.
There has been a significant history of work on extracting Finite State Machines (FSMs) from recurrent networks trained to recognize languages (Zeng et al., 1993; Tiňo et al., 1998; Cechin et al., 2003). Typical approaches include discretizing the continuous memory space via gridding or clustering followed by minimization. A more recent approach is to use classic query-based learning algorithms to extract FSMs by asking membership and equivalence queries (Weiss et al., 2017). However, none of these approaches directly apply to learning policies, which require extending to Moore Machines. In addition, all of these approaches produce an FSM approximation that is separated from the RNN and thus serve as only a proxy of the RNN behavior. Rather, our approach directly inserts discrete elements into the RNN that preserves its behavior, but allows for a finite state characterization. This insertion approach has the advantage of allowing fine-tuning and visualization using standard learning frameworks.
The work most similar to ours also focused on learning FSMs (Zeng et al., 1993). However, the approach is based on directly learning recurrent networks with finite memory, which are qualitatively similar to the memory representation of our MMNs. That work, however, focused on learning from scratch rather than aiming to describe the behavior of a continuous RNN. Our work extends that approach to learn MMNs and more importantly introduces the method of QBN insertion as a way of learning via guidance from a continuous RNN.This transforms any pre-trained recurrent policy into a finite representation.
We note that there has been prior work on learning fully binary networks, where the activation functions and/or weights are binary (e.g. (Bengio et al., 2013; Courbariaux et al., 2016; Hinton, 2012)). The goal of that line of work is typically to learn more time and space efficient networks. Rather, we focus on learning only discrete representations of memory and observations, while allowing the rest of the network to use arbitrary activations and weights. This is due to our alternative goal of supporting interpretability rather than efficiency.

heading: 3 RECURRENT POLICY NETWORKS: CONTINUOUS AND QUANTIZED
text: Recurrent neural networks (RNNs) are commonly used in reinforcement learning to represent policies that require or can benefit from internal memory. At each time step, an RNN is given an observation ot (e.g. image) and must output an action at to be taken in the environment. During
execution an RNN maintains a continuous-valued hidden state ht, which is updated on each transition and influences the action choice. In particular, given the current observation ot and current state ht, an RNN performs the following operations: 1) Extract a set of observation features ft from ot, for example, using a CNN when observations are images, 2) Outputting an action at = π(ht) according to policy π, which is often a linear softmax function of ht, 3) transition to a new state ht+1 = δ(ft, ht) where δ is the transition function, which is often implemented via different types of gating networks such as LSTMs or GRUs.
The continuous and high dimensional nature of ht and ft can make interpreting the role of memory difficult. This motivates our goal of extracting compact quantized representations of ht and ft. Such representations have the potential to allow investigating a finite system that captures the key features of the memory and observations. For this purpose we introduce Moore Machines and their deep network counterparts.
Moore Machines. A classical Moore Machine (MM) is a standard finite state machine where all states are labeled by output values, which in our case will correspond to actions. In particular, a Moore Machine is described by a finite set of (hidden) states Ĥ , an initial hidden state ĥ0, a finite set of observations Ô, a finite set of actions A, a transition function δ̂, and a policy π̂ that maps hidden states to actions. The transition function δ̂ : Ĥ × Ô → Ĥ returns the next hidden state ĥt+1 = δ̂(ĥt, ôt) given the current state ĥt and observation ôt. By convention we will use ht and ĥt to denote continuous and discrete states respectively and similarly for other quantities and functions.
Moore Machine Networks. A Moore Machine Network (MMN) is a Moore Machine where the transition function δ̂ and policy π̂ are represented via deep networks. In addition, since the raw observations given to an MMN are often continuous, or from an effectively unbounded set (e.g. images), an MMN will also provide a mapping ĝ from the continuous observations to a finite discrete observation space Ô. Here ĝ will also be represented via a deep network. In this work, we consider quantized state and observation representations where each ĥ ∈ Ĥ is a discrete vector and each discrete observation in Ô is a discrete vector that describes the raw observation. We will denote the quantization level as k and the dimensions of ĥ and f̂ by Bh and Bf respectively.
Based on the above discussion, an MMN can be viewed as a traditional RNN, where: 1) The memory is restricted to be composed of k-level activation units, and 2) The environmental observations are intermediately transformed to a k-level representation f̂ before being fed to the recurrent module. Given an approach for incorporating quantized units into the backpropagation process, it is straightforward, in concept, to learn MMNs from scratch via standard RNN learning algorithms. However, we have found that learning MMNs from scratch can be quite difficult for non-trivial problems, even when an RNN can be learned with relative ease. For example, we have not been able to train highperforming MMNs from scratch for Atari games. Below we introduce a new approach for learning MMNs that is able to leverage the ability to learn RNNs.

heading: 4 LEARNING MOORE MACHINE NETWORKS FROM RNNS
text: Given a trained RNN, our key idea is to first learn quantized bottleneck networks (QBNs) for embedding the continuous observation features and hidden state into a k-level quantized representation. We will then insert the QBNs into the original recurrent net in such a way that its behavior is minimally changed with the option of fine-tuning after insertion. The resulting network can be viewed as consuming quantized features and maintaining quantized state, which is effectively an MMN. Below we describe the steps in further detail, which are illustrated in Figure 1.

heading: 4.1 QUANTIZED BOTTLENECK NETWORKS
text: A QBN is simply an autoencoder where the latent representation between the encoder and decoder (i.e. the bottleneck) is constrained to be composed of k-level activation units. While, traditional autoencoders are generally used for the purpose of dimensionality reduction in continuous space (Hinton & Salakhutdinov, 2006), QBNs are motivated by the goal of discretizing a continuous space. Conceptually, this can be done by quantizing the activations of units in the encoding layer.
We represent a QBN via a continuous multilayer encoder E, which maps inputs x to a latent encoding E(x), and a corresponding multilayer decoder D. To quantize the encoding, the QBN output is given by
b(x) = D(quantize(E(x)))
In our case, we use 3-level quantization in the form of +1, 0 and −1 using the quantize function, which assumes the outputs of E(x) are in the range [−1, 1].1 One choice for the output nodes of E(x) would be the tanh activation. However, since the gradient of tanh is close to 1 near 0, it can be difficult to produce quantization level 0 during learning. Thus, as suggested in Pitis (2017), to support 3-valued quantization we use the following activation function, which is flatter in the region around zero input. φ(x) = 1.5 tanh(x) + 0.5 tanh(−3x) Of course introducing the quantize function in the QBN results in b(x) being non-differentiable, making it apparently incompatible with backpropagation, since the gradients between the decoder and encoder will almost always be zero. While there are a variety of ways to deal with this issue, we have found that the straight-through estimator, as suggested and used in prior work (Hinton, 2012; Bengio et al., 2013; Courbariaux et al., 2016) is quite effective. In particular, the standard straightthrough estimator of the gradient simply treats the quantize function as the identity function during back-propagation. Overall, the inclusion of the quantize function in the QBN effectively allows us to view the last layer ofE as producing a k-level encoding. We train a QBN as an autoencoder using the standard L2 reconstruction error ‖x− b(x)‖2 for a given input x.

heading: 4.2 BOTTLENECK INSERTION
text: Given a recurrent policy we can run the policy in the target environment in order to produce an arbitrarily large set of training sequences of triples (ot, ft, ht), giving the observation, corresponding observation feature, and hidden state at time t. Let F and H be the sets of all observed features and states respectively. The first step of our approach is to train two QBNs, bf and bh, on F and H respectively. If the QBNs are able to achieve low reconstruction error then we can view latent “bottlenecks” of the QBNs as a high-quality k-level encodings of the original hidden states and features.
We now view bf and bh as “wires” that propagate the input to the output, with some noise due to imperfect reconstruction. We insert these wires into the original RNN in the natural way (stage-3 in Figure 1). The bf QBN is inserted between the RNN units that compute the features f and the nodes those units are connected to. The bh QBN is inserted between the output of the recurrent network block and the input to the recurrent block. If bf and bh always produced perfect reconstructions, then
1This three valued approach was chosen for its potential interpretability of a quantized output having negative, positive, or zero influence. Other quantizations are worth future exploration.
the result of inserting them as described would not change the behavior of the RNN. Yet, the RNN can now be viewed as an MMN since the bottlenecks of bf and bh provide a quantized representation of the features ft and states ht.
Fine Tuning. In practice, the QBNs will not achieve perfect reconstruction and thus, the resulting MMN may not behave identically to the original RNN. Empirically, we have found that the performance of the resulting MMN is often very close to the RNN directly after insertion. However, when there is non-trivial performance degradation, we can fine-tune the MMN by training on the original rollout data of the RNN. Importantly, since our primary goal is to learn a representation of the original RNN, during fine-tuning our objective is to have the MMN match the softmax distribution over actions produced by the RNN. We found that training in this way was significantly more stable than training the MMN to simply output the same action as the RNN.

heading: 4.3 MOORE MACHINE EXTRACTION AND MINIMIZATION
text: After obtaining the MMN, one could use visualization and other analysis tools to investigate the memory and it’s feature bits in order to gain a semantic understanding of their roles. Solving the full interpretation problem in a primitive way is beyond the scope of this work.
Extraction. Another way to gain insight is to use the MMN to produce an equivalent Moore Machine over atomic state and observation spaces, where each state and observation is a discrete symbol. This machine can be analyzed to understand the role of different machine states and how they are related. In order to create the Moore Machine we run the learned MMN to produce a dataset of < ĥt−1, f̂t, ĥt, at >, giving the consecutive pairs of quantized states, the quantized features that led to the transition, and the action selected after the transition. The state-space of the Moore Machine will correspond to the p distinct quantized states in the data and the observation-space of the machine will be the q unique quantized feature vectors in the data. The transition function of the machine δ̂ is constructed from the data by producing a p× q transaction table that captures the transitions seen in the data.
Minimization. In general, the number of states p in the resulting Moore Machine will be larger than necessary in the sense that there is a much smaller, but equivalent, minimal machine. Thus, we apply standard Moore Machine minimization techniques to arrive at the minimal2 equivalent Moore Machine (Paull & Unger, 1959). This often dramatically reduces the number of distinct states and observations.

heading: 5 SYNTHETIC EXPERIMENTS
text: Our experiments address the following questions: 1) Is it possible to extract MMNs from RNNs without significant loss in Performance? 2) What is the general magnitude of the number of states and observations in the minimal machines, especially for complex domains such as Atari? 3) Do the learned MMNs help with interpretability of the recurrent policies? In this section, we begin addressing these questions by considering two domains where ground truth Moore Machines are known. The first is a parameterized synthetic environment, Mode Counter, which can capture multiple types of memory use. Second, we consider benchmark grammar learning problems.

heading: 5.1 MODE COUNTER
text: The class of Mode Counter Environments (MCEs) allows us to vary the amount of memory required by a policy (including no memory) and the required type of memory usage. In particular, MCEs can require varying amounts of memory for remembering past events and implementing internal counters.
An MCE is a restricted type of Partially Observable Markov Decision Process, which transitions between one of M modes over time according to a transition distribution, which can depend on
2Typically minimization algorithms focus on minimizing only the number of states and do not change the number of observations. We also aim to minimize the observations. In particular, if there are observations that have identical transition dynamics, then we merge them into one observation. This preserves equivalence to the original machine, but can dramatically decrease the number of required observation symbols.
the current mode and amount of time spent in the current mode. There are M actions, one for each mode, and the agent receives a reward of +1 at the end of the episode if it takes the correct action associated with the active mode at each time step. The agent does not observe the mode directly, but rather must infer the mode via a combination of observations and memory use. Different parameterizations place different requirements on how (and if) memory needs to be used to infer the mode and achieve optimal performance. Below we give an intuitive description of the MCEs3 in our experiments.
We conduct experiments in three MCE instances, which use memory and observations in fundamentally different ways. This tests our ability to use our approach for determining the type of memory use. 1) Amnesia. This MCE is designed so that the optimal policy does not need memory to track past information and can select optimal actions based on just the current observation. 2) Blind. Here we consider the opposite extreme, where the MCE observations provide no information about optimal actions. Rather, memory must be used to implement counters that keep track of a deterministic mode sequence for determining the optimal actions. 3) Tracker. This MCE is designed so that the optimal policy must both use observations and memory in order to select optimal actions. Intuitively the memory must implement counters that keep track of key time steps where the observations provide information about the mode. In all above instances, we used M = 4 modes.
RNN Training. For each MCE instance we use the following recurrent architecture: the input feeds into 1 feed-forward layer with 4 Relu6 nodes (Krizhevsky & Hinton, 2010) (ft), followed by a 1-layer GRU with 8 hidden units (ht), followed by a fully connected softmax layer giving a distribution over the M actions (one per mode). Since we know the optimal policy in the MCEs we use imitation learning for training. For all of the MCEs in our experiments, the trained RNNs achieve 100% accuracy on the imitation dataset and appeared to produce optimal policies.
MMN Training. The observation QBN bf and hidden-state QBN bh have the same architecture, except that the number of quantized bottleneck units Bf and Bh are varied in our experiments. The encoders consist of 1 feed-forward layer of tanh nodes, where the number of nodes is 4 times the size of the bottleneck. This layer feeds into 1 feedforward layer of quantized bottleneck nodes (see Section 4). The decoder for both bf and bh has a symmetric architecture to the encoder. Training of bf and bh in the MCE environments was extremely fast compared to the RNN training, since QBNs do not need to learn temporal dependencies. We trained QBNs with bottleneck sizes of Bf ∈ {4, 8} and Bh ∈ {4, 8}. For each combination of Bf and Bh we embedded the QBNs into the RNN to give a discrete MMN and then measured performance of the MMN before and after fine tuning. Table 1 gives the average test score over 50 test episodes. Score of 1 indicates the agent performed optimally for all episodes. In most of the cases no fine tuning was required (marked as ’-’) since the agent achieved perfect performance immediately after bottleneck insertion due to low reconstruction error. In all other cases, except for Tracker (Bh = 4, Bf = 4) fine-tuning resulted in perfect MMN performance. The exception yielded 98% accuracy. Interestingly in that case, we see that if we only insert one of the bottlenecks at a time, we yield perfect performance, which indicates that the combined error accumulation of the two bottlenecks is responsible for the reduced performance.
Moore Machine Extraction. Table 1 also gives the number of states and observations of the MMs extracted from the MMNs both before and after minimization. Recall that the number of states and obsevations before minimization is the number of distinct combinations of values observed for the bottleneck nodes during long executions of the MMN. We see that there are typically significantly more states and observations before minimization than after. This indicates that the MMN learning does not necessarily learn minimal discrete state and observation representations, though the representations accurately describe the RNN. After minimization (Section 4.3), however, in all but one case we get exact minimal machines for each MCE domain. The ground truth minimal machines that are found are shown in the Appendix (Figure 3). This shows that the MMNs learned via QBN insertions were equivalent to the true minimal machines and hence indeed optimal in most cases. The exception matches the case where the MMN did not achieve perfect accuracy.
Examining these machines allows one to understand the memory use. For example, the machine for Blind has just a single observation symbol and hence its transitions cannot depend on the input observations. In contrast, the machine for Amnesia shows that each distinct observation symbol
3Appendix has full details of how MCEs are parameterized and the specific instances used in our experiments.
leads to the same state (and hence action choice) regardless of the source state. Thus, the policies action is completely determined by the current observation.

heading: 5.2 TOMITA GRAMMARS
text: The Tomita Grammars are popular benchmarks for learning finite state machines (FSMs), including work on extracting FSMs from RNNs (e.g. (Watrous & Kuhn, 1992; Weiss et al., 2017)). Here we evaluate our approach over the 7 Tomita Grammars4, where each grammar defines the set of binary strings that should be accepted or rejected. Since, our focus is on policy learning problems, we treat the grammars as environments with two actions ‘accept’ and ‘reject’. Each episode corresponds to a random string that is either part of the particular grammar or not. The agent receives a reward of 1 if the correct action accept/reject is chosen on the last symbol of a string.
RNN Training. The RNN for each grammar is comprised of a one-layer GRU with 10 hidden units, followed by a fully connected softmax layer with 2 nodes (accept/reject). Since we know the optimal policy, we again use imitation learning to train each RNN using the Adam optimizer and learning rate of 0.001. The training dataset is comprised of an equal number of accept/reject strings with lengths uniformly sampled in the range [1,50]. Table 2 presents the test results for the trained RNNs giving the accuracy over a test set of 100 strings drawn from the same distribution as used for training. Other than grammar #65, the RNNs were 100% accurate.
MMN Training. Since the raw observations for this problem are from a finite alphabet, we don’t need to employ a bottleneck encoder to discretize the observation features. Thus the only bottleneck learned here is bh for the hidden memory state. We use the same architecture for bh as used for the MCE experiments and conduct experiments with Bh ∈ {8, 16}. These bottlenecks were then inserted in the RNNs to give MMNs. The performance of the MMNs before and after fine-tuning are shared in Table 2. In almost all cases, the MMN is able to maintain the performance of the RNN without fine-tuning. Fine tuning provides only minor improvements in other cases, which already are achieving high accuracy.
Moore Machine Extraction. Our results for MM extraction and minimization are in Table 2. In each case, we see a considerable reduction in the MM’s state-space after minimization while accurately maintaining the MMN’s performance. Again, this shows that the MMN learning does not directly result in minimal machines, yet are equivalent to the minimal machines and hence are exact
4The Tomita grammars are the following 7 languages over the alphabet {0, 1}: [1] 1∗, [2] (10)∗, [3] any string without an odd number of consecutive 0’s after an odd number of consecutive l’s, [4] any string not containing ”000” as a substring, [5] all w for which #0(w) and #1(w) are even (where #a(w) is the number of a’s in w), [6] any string such that the difference between the numbers of l’s and 0’s is 3n , and [7] 0∗1∗0∗1∗.
5Similar results are reported in Weiss et al. (2017)
solutions. In all cases, except for grammar 6 the minimized machines are identical to the minimal machines that are known for these grammars (Tomita, 1982).

heading: 6 ATARI EXPERIMENTS
text: In this section, we consider applying our technique to RNNs learned for six Atari6 games using the OpenAI gym (Brockman et al., 2016). Unlike the above experiments, where we knew the ground truth MMs, for Atari we did not have any preconception of what the MMs might look and how large they might be. The fact that the input observations for Atari (i.e. images) are much more complex than the previous experiments inputs makes it completely unclear if we can expect similar types of results. There have been other recent efforts towards understanding Atari agents (Zahavy et al., 2016; Greydanus et al., 2017). However, we are not aware of any other work which aims to extract finite state representations for Atari policies.
RNN Training. All the Atari agents have the same recurrent architecture. The input observation is an image frame, preprocessed by gray-scaling, 2x down-sampling, cropping to an 80 × 80 square and normalizing the values to [0, 1]. The network has 4 convolutional layers (kernel size 3, strides 2, padding 1, and 32,32,16,4 filters respectively). We used Relu as the intermediate activation and Relu6 over the last convolutional layer. This is followed by a GRU layer with 32 hidden units and a fully connected layer with n+1 units, where n is the dimension of the Atari action space. We applied a softmax to first n neurons to obtain the policy and used the last neuron to predict the value function. We used the A3C RL algorithm (Mnih et al., 2016) (learning rate 10−4, discount factor 0.99) and computed loss on the policy using Generalized Advantage Estimation (λ = 1.0) (Schulman et al., 2015). We report the trained RNN performance on our six games in the second column of Table 3.
MMN Training. We used the same general architecture for the QBN bf as used for the MCE experiments, but adjusted the encoder input and decoder output sizes to match the dimension of the continuous observation features ft. For bh, the encoder has 3 feed-forward layers with (8 × Bh), (4× Bh) and Bh nodes. The decoder is symmetric to the encoder. For the Atari domains, the training data for bf and bh was generated using noisy rollouts. In particular, each training episode was generated by executing the learned RNN for a random number of steps and then executing an -greedy (with = 0.3) version of the RNN policy. This is intended to increase the diversity of the training data and we found that it helps to more robustly learn the QBNs. We trained bottlenecks for
6We use deterministic Atari games with frame-skip 4. Action Space of Pong and SpaceInvaders has been modified to [Noop, RightFire, LeftFire], [Noop, Fire, Right, Left], for the ease of training and interpretability.
Bh ∈ {64, 128} and Bf ∈ {100, 400} noting that these values are significantly larger than for our earlier experiments due to the complexity of Atari. Note that while there are an enormous number of potential discrete states for these values of Bh the actual number of states observed and hence the number of MMN states can be substantially smaller. Each bottleneck was trained to the point of saturation of training loss and then inserted into the RNN to give an MMN for each Atari game.
MMN Performance. Table 3 gives the performance of the trained MMNs before and after finetuning for different combinations of Bh and Bf . We see that for 4 games, Pong, Freeway, Bowling, and Boxing, the MMNs after fine tuning either achieve identical scores to the RNN or very close (in the case of boxing). This demonstrates the ability to learn a discrete representation of the input and memory for these complex games with no impact on performance. We see that for Boxing and Pong fine tuning was required to match the RNN performance. In the case of Freeway and Bowling, fine-tuning was not required.
In the remaining two games, Breakout and Space Invaders, we see that the MMNs learned after fine tuning achieve lower scores than the original RNNs, though the scores are still relatively good. On further investigation, we found that this drop in performance was due to poor reconstruction on some rare parts of the game. For example, in Breakout, after the first board is cleared, the policy needs to press the fire-button to continue, but the learned MMN does not do this and instead times out, which results in less score. This motivates the investigation into more intelligent approaches for training QBNs to capture critical information in such rare, but critically important, states.
MM Minimization. We see from Table 3 that before minimization, the MMs often have relatively large numbers of discrete states and observations. This is unsurprising given that we are using relatively large values of Bh and Bf . However, we see that after minimizing the MMNs the number of states and observations reduces by orders of magnitude, sometimes to just a single state and/or single observation. The number of states and observations in many cases are small enough to write out and analyze by hand, making them amenable to careful analysis. However, this analysis is likely to be non-trivial for moderately complex policies due to the need to understand the “meaning” of the observations and in turn of the states.
Understanding Memory Use. We were surprised to observe in Atari the same three types of memory use considered for the MCE domains above. First, we see that the MM for Pong has just three states (one per action) and 10 discrete observation symbols (see Figure 2a). Most importantly we see that each observation transitions to the same state (and hence action) regardless of the current state. So we can view this MM as defining a set of rule that maps individual observations to actions with no memory necessary. In this sense, the Pong policy is analogous to the Amnesia MCE [5.1].
In contrast, we see that in both Bowling and Freeway there is only one observation symbol in the minimal MM. This means that the MM actually ignores the input image when selecting actions. Rather the policies are open-loop controllers whose action just depends on the time-step rather than the observations. Thus, these policies are analogous to the Blind MCE [5.1]. Freeway has a particularly trivial policy that always takes the Up action at each time step. While this policy behavior could have been determined by looking at the action sequence of the rollouts, it is encouraging that our MM extraction approach also discovered this. As shown in Figure 2b, Bowling has a more interesting open-loop policy structure where it has an initial sequence of actions and then a loop is entered where the action sequence is repeated. It is not immediately obvious that this policy has such an open-loop structure by just watching the policy. Thus, we can see that the MM extraction approach we use here can provide significant additional insight.
Breakout, Space Invaders and Boxing use both memory and observations based on our analysis of the MM transition structures. We have not yet attempted a full semantic analysis of the discrete observations and states for any of the Atari policies. This will require additional visualization and interaction tools and is an important direction of future work that is enabled by our approach.

heading: 7 SUMMARY AND FUTURE WORK
text: Motivated by the goal of better understanding memory use in RNN polices, we introduced an approach for extracting finite state Moore Machines from those policies. The key idea, bottleneck insertion, is to train Quantized Bottleneck Networks to produce binary encodings of continuous RNN memory and input features, and then insert those bottlenecks into the RNN. This yields a
near equivalent Moore Machine Network (MMN) which has quantized memory and observation features. From the MMN we then extract a discrete Moore machine that can then be transformed into an equivalent minimal machine for analysis and usage. Our results on two environments where the ground truth machines are known show that our approach is able to accurately extract the ground truth. We also show experiments in six Atari games, where we have no prior insight into the ground truth machines. We show that, in most cases, the learned MMNs maintain similar performance to the original RNN policies. Further, the extracted machines provide insight into the memory usage of the policies. First, we see that the number of required memory states and observations is surprisingly small. Second, we can identify cases where the policy did not use memory in a significant way (e.g. Pong) and policies that relied only on memory and ignored the observations (e.g. Bowling and Freeway). To our knowledge, this is the first work where this type of insight was reported for policies in such complex domains. A key direction for future work is to develop tools and visualizations for attaching meaning to the discrete observations and in turn states, which will allow for an additional level of insight into the policies. It is also worth considering the use of tools for analyzing finite-state machine structure to gain further insight and analyze formal properties of the policies.

heading: 7.1 FORMAL DEFINITION OF MODE COUNTER ENVIRONMENT
text: An MCE is parameterized by the mode number M , a mode transition function P , a mode life span mapping ∆(m) that assigns a positive integer to each mode, and a count set C containing zero or more natural numbers. At time t the MCE hidden state is a tuple (mt, ct), where mt ∈ {1, 2, . . . ,M} is the current mode and ct is the count of time-steps that the system has been consecutively in mode mt. The mode only changes when the lifespan is reached, i.e. ct = ∆(mt) − 1, upon which the next mode mt+1 is generated according to the transition distribution P (mt+1 | mt). The transition distribution also specifies the distribution over initial modes. The agent does not directly observe the state, but rather, the agent only receives a continuous-valued observations ot ∈ [0, 1] at each step, based on the current state (mt, ct). If ct ∈ C then ot is drawn uniformly at random from [mt/M, (mt + 1)/M)] and otherwise ot is drawn uniformly at random from [0, 1]. Thus, observations determine the mode when the mode count is in C and otherwise the observations are uninformative. Note that the agent does not observe the counter. This means that to keep track of the mode for optimal performance the agent must remember the current mode and use memory to keep track of how long the mode has been active, in order to determine when it needs to “pay attention” to the current observation.
We conduct experiments with the following three MCE instances 7: 1) Amnesia. This MCE uses ∆(m) = 1 for all modes, C = {0}, and uniformly samples random initial mode and transition distributions. Thus, an optimal policy will not use memory to track information from the past, since the current observation alone determines the current mode. This tests our ability to use MMN extraction to determine that a policy is purely reactive, i.e. not using memory. 2) Blind. Here we use deterministic initial mode and transition distributions, mode life spans that can be larger than 1, and C = {}. Thus, the observations provide no information about the mode and optimal performance can only be achieved by using memory to keep track of the deterministic mode sequence. This allows us to test whether the extraction of an MMN could infer that the recurrent policy is ignoring observations and only using memory. 3) Tracker. This MCE is identical to Amnesia, except that the ∆(m) values can be larger than 1. This requires an optimal policy to pay attention to observations when ct = 0 and use memory to keep track of the current mode and mode count. This is the most general instance of the environment and can result in difficult problems when the number of modes and their life-spans grow. In all above instances, we used M = 4.
7Implementations available @ https://github.com/koulanurag/gym_x
7.2 GROUND TRUTH MCE MOORE MACHINES

heading: 8 TOMITA MOORE MACHINES

Review summaries:
RNNs are difficult to explain, understand and analyze due to the continuous-valued memory vectors and observations features they use. Thus, this paper attempts to extract finite representation from RNNs so as to better interpret or understand RNNs. They introduce a new technique called Quantized Bottleneck Insertion to extract Moore Machines (MM). The extracted MM can be analyzed to improve the understanding of memory use and general behavior on the policies. The experiments on synthetic datasets and six Atari games validate the effectiveness of the proposal.