Learning Finite State Representations of Recurrent Policy Networks

Anurag Koul, Sam Greydanus, Alan Fern

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.

Introduction

In deep reinforcement learning (RL) and imitation learning, agents often require memory to navigate partially observable environments. Recurrent Neural Networks (RNNs), such as LSTMs or GRUs, are typically employed for this purpose because they maintain a continuous-valued hidden state that evolves over time. However, this high-dimensional, continuous memory often functions as a "black box," making it nearly impossible to discern how an agent utilizes its memory or which specific features of the observation history it prioritizes.

This lack of interpretability poses a significant barrier to deploying RL agents in high-stakes environments where explainability is paramount. This research investigates the hypothesis that despite their continuous architecture, these networks often track discrete concepts. We propose a method to extract compact, human-readable finite-state machines (specifically, Moore Machines) from continuous RNNs without compromising performance.

Methodology: Quantized Bottleneck Insertion

The core of our approach is a multi-step pipeline designed to discretize the continuous components of a trained RNN policy.

The three-stage pipeline for Quantized Bottleneck Insertion: (1) Training the base RNN, (2) Training discrete autoencoders (QBNs), and (3) Integrating and fine-tuning the Moore Machine Network.
  1. Base RNN Training: A standard continuous RNN policy is trained on the target environment.
  2. Quantized Bottleneck Networks (QBNs): We train two autoencoders with a discrete latent "bottleneck" layer (using 3-level quantization: -1, 0, and 1). One QBN reconstructs continuous observation features ($f_t$), while the other reconstructs hidden memory states ($h_t$). To overcome the non-differentiability of quantization, we utilize a "straight-through" gradient estimator.
  3. Moore Machine Network (MMN) Integration: The trained QBNs are inserted into the original RNN, effectively creating discrete "wires" for observations and memory. If necessary, the resulting MMN is fine-tuned to match the original policy's action distribution.
  4. Extraction and Minimization: By executing the MMN, we collect discrete state transitions to build a symbolic Moore Machine. This machine is then reduced to its minimal equivalent form using standard finite-state machine minimization algorithms.

Experimental Evaluation

We evaluated the pipeline across synthetic Mode Counter Environments (MCEs), Tomita Grammars, and six Atari games.

Synthetic and Formal Benchmarks

For the MCEs (Amnesia, Blind, Tracker) and Tomita Grammars, the extracted Moore Machines achieved near-perfect accuracy. As shown in the table below, the minimization process significantly reduces the number of states and observations required to represent the policy.

Performance and state reduction on Mode Counter Environments. The 'After Minimization' columns highlight the discovery of compact, discrete representations.

Atari Games

In complex Atari environments, the method successfully extracted remarkably compact machines. For instance, a high-performing Pong agent was reduced to just 3 memory states and 10 discrete observations. In 4 out of 6 games, the discrete MMNs maintained performance levels identical to the original continuous RNNs.

Interpretability and Behavioral Analysis

The extracted finite-state machines (FSMs) act as "behavioral X-rays," revealing the underlying strategies of the agents:

  • Reactive vs. Open-Loop: The analysis revealed that the Pong agent was purely reactive, as its transitions depended solely on current observations rather than memory. Conversely, Freeway and Bowling agents were found to be open-loop controllers, ignoring visual input and executing timed sequences of actions.
  • Identifying "Cheating": In some cases, the FSMs proved that agents were ignoring the environment entirely, a behavior that would be difficult to detect in a continuous RNN.

Conclusion and Future Work

Quantized Bottleneck Insertion demonstrates that complex recurrent policies often mask surprisingly simple discrete logic. While highly effective, the method currently struggles with rare but critical states in games like Breakout, where the QBNs may fail to reconstruct infrequent events. Future research will focus on improving QBN training for these edge cases and developing tools to provide semantic, visual interpretations of the extracted discrete states.

Summary updated

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.
BibTeX
@inproceedings{koul2019learning,
  author = {Anurag Koul and Sam Greydanus and Alan Fern},
  title = {{Learning Finite State Representations of Recurrent Policy Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=Q85VYZg2Wx},
}
Figure