Learning Finite State Representations of Recurrent Policy Networks

Anurag Koul, Alan Fern, Sam Greydanus

Recurrent Neural Networks (RNNs) are the go-to architecture for reinforcement learning (RL) agents that need to remember the past to act in the present. However, their "memory" is usually a high-dimensional, continuous-valued vector—a mathematical black box that is notoriously difficult for humans to interpret.

In the paper "Learning Finite State Representations of Recurrent Policy Networks" (ICLR 2019), researchers Anurag Koul, Alan Fern, and Sam Greydanus propose a clever way to "discretize" these memories. Their method turns opaque neural networks into transparent, minimal Moore Machines, revealing the surprisingly simple logic driving many complex RL agents.

The Interpretability Problem in Deep RL

Deep RL agents are increasingly deployed in complex tasks, but we rarely understand why they make specific decisions. This is especially true for RNNs (like LSTMs or GRUs), where an agent’s decision-making depends on a hidden state that evolves over time.

Because these hidden states are continuous and high-dimensional, it is nearly impossible to tell if an agent is actually "remembering" a specific event or just processing noise. This lack of interpretability is a major barrier to deploying RL in high-stakes environments where trust and safety are paramount. The authors aim to bridge this gap by forcing the RNN to use a finite, discrete set of memory states and observations.

The Solution: Quantized Bottleneck Insertion (QBI)

The core of the paper is a process called Quantized Bottleneck Insertion (QBI), which transforms complex RNN policies into compact, discrete finite-state machines.

The three-stage Quantized Bottleneck Insertion process.

The methodology follows a distinct pipeline:

  1. Training the "Teacher" (Stage 1): First, a standard RNN policy is trained on a task until it performs well.
  2. Bottleneck Training (Stage 2): The researchers train Quantized Bottleneck Networks (QBNs). These act as autoencoders where the middle "bottleneck" layer is forced to take on discrete values (specifically -1, 0, or 1). One QBN learns to compress the RNN’s hidden memory states, while another learns to compress the observation features.
  3. Insertion and Fine-Tuning (Stage 3): These QBNs are literally "spliced" into the original RNN, replacing the continuous "wires" that carry memory and observation data. If the agent's performance drops due to the discretization, the system is fine-tuned to match the original RNN’s behavior.
  4. Minimization: Once the policy is discrete, it can be represented as a Moore Machine (a type of finite state machine). The authors then apply classic state-minimization algorithms to find the smallest possible version of that machine.

Experimental Datasets

The authors evaluated their approach across three distinct domains:

  • Mode Counter Environments (MCE): Synthetic tasks designed to test specific memory types, such as "Amnesia" (reactive tasks), "Blind" (tasks requiring internal counters), and "Tracker" (tasks requiring both).
  • Tomita Grammars: Seven classic formal language benchmarks used to test an agent's ability to recognize patterns in strings.
  • Atari Games: Six popular games (Pong, Freeway, Breakout, Space Invaders, Bowling, and Boxing) using agents trained via the A3C algorithm.

Key Insights and Results

The most striking takeaway from the research is that large neural networks do not necessarily imply complex logic. Many high-performing agents can be reduced to incredibly simple state machines.

Results on Tomita Grammars showing dramatic state reduction after minimization while maintaining 100% accuracy.
  • Perfect Extraction: On synthetic tasks and Tomita grammars, the method successfully extracted the exact "ground truth" minimal machines, drastically reducing the number of hidden states without losing accuracy.
  • Extreme Compression in Atari: For Pong, a policy that originally used a 32-unit GRU was reduced to a machine with only 3 memory states and 10 discrete observation symbols without losing performance. In 4 out of 6 Atari games, the discrete Moore Machine Network achieved scores identical to or very near the original continuous RNN.
  • Policy Archetypes & "Cheating": The extraction revealed how different agents use memory. Pong agents are largely reactive (ignoring past memory). Freeway and Bowling agents are open-loop; extraction revealed the Bowling agent wasn't actually "playing" the game visually, but executing a hard-coded loop of timed actions that happened to work. Games like Breakout represent a hybrid, requiring a genuine mix of memory and observation.
  • Actionable Interpretability: By looking at the minimized Moore Machine, researchers can literally draw a flowchart of the agent's "brain," making it possible to verify its logic or find flaws.

Limitations and Future Work

The primary limitation identified is the "Rare State" problem. In games like Breakout, the agent needs to perform a specific action (like pressing "fire") only once every few hundred frames. Because these events are rare, the QBN autoencoder sometimes fails to prioritize them during compression, leading to a "timed out" agent that stops playing after clearing a level.

Future work suggests developing better tools to map the "meaning" of the discrete observation symbols back to the original image pixels (e.g., understanding that "Symbol 1" means the ball is in the top-left corner). Additionally, the authors hope to use formal verification tools on these extracted machines to mathematically prove that an agent will never enter an "unsafe" state.

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 Alan Fern and Sam Greydanus},
  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