# Enhancing Reinforcement Learning with discrete interfaces to learn the Dyck Language

arXiv: https://arxiv.org/abs/2110.14350 · HTML: https://mlsanity.com/paper/2110.14350/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 22 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 15 of 15)

- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [PathNet: Evolution Channels Gradient Descent in Super Neural Networks](https://mlsanity.com/paper/1701.08734/) (2017)
- [Memory Networks](https://mlsanity.com/paper/1410.3916/) (2014)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [Neuro-Symbolic Program Synthesis](https://mlsanity.com/paper/1611.01855/) (2016)
- [Learning Compositional Rules via Neural Program Synthesis](https://mlsanity.com/paper/2003.05562/) (2020)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Neural Random-Access Machines](https://mlsanity.com/paper/1511.06392/) (2015)
- [Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages](https://mlsanity.com/paper/1911.03329/) (2019)
- [Evaluating the Ability of LSTMs to Learn Context-Free Grammars](https://mlsanity.com/paper/1811.02611/) (2018)
- [Lie Access Neural Turing Machine](https://mlsanity.com/paper/1602.08671/) (2016)
- [Learning Operations on a Stack with Neural Turing Machines](https://mlsanity.com/paper/1612.00827/) (2016)
- [Interaction Networks: Using a Reinforcement Learner to train other Machine Learning algorithms](https://mlsanity.com/paper/2006.08457/) (2020)

## Abstract (arXiv)

Even though most interfaces in the real world are discrete, no efficient way exists to train neural networks to make use of them, yet. We enhance an Interaction Network (a Reinforcement Learning architecture) with discrete interfaces and train it on the generalized Dyck language. This task requires an understanding of hierarchical structures to solve, and has long proven difficult for neural networks. We provide the first solution based on learning to use discrete data structures. We encountered unexpected anomalous behavior during training, and utilized pre-training based on execution traces to overcome them. The resulting model is very small and fast, and generalizes to sequences that are an entire order of magnitude longer than the training data.