# There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 26 references that are in the map.
- First posted on arXiv 9 Jun 2022.

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [Hierarchical and Interpretable Skill Acquisition in Multi-task Reinforcement Learning](https://mlsanity.com/paper/1712.07294/) (2017)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Toward Interpretable Deep Reinforcement Learning with Linear Model U-Trees](https://mlsanity.com/paper/1807.05887/) (2018)
- [Interestingness Elements for Explainable Reinforcement Learning: Understanding Agents' Capabilities and Limitations](https://mlsanity.com/paper/1912.09007/) (2019)
- [Conservative Q-Improvement: Reinforcement Learning for an Interpretable Decision-Tree Policy](https://mlsanity.com/paper/1907.01180/) (2019)
- [Deep Reinforcement Learning for Dynamic Treatment Regimes on Medical Registry Data](https://mlsanity.com/paper/1801.09271/) (2018)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)

## Built on by (most cited first, 4 of 4)

- [DILA: Dictionary Label Attention for Mechanistic Interpretability in High-dimensional Multi-label Medical Coding Prediction](https://mlsanity.com/paper/2409.10504/) (2024)
- [A Survey of Reinforcement Learning for Optimization in Automation](https://mlsanity.com/paper/2502.09417/) (2025)
- [Evaluating Interpretable Reinforcement Learning by Distilling Policies into Programs](https://mlsanity.com/paper/2503.08322/) (2025)
- [Price of Fairness in Short-Term and Long-Term Algorithmic Selections](https://mlsanity.com/paper/2605.06227/) (2026)

## Abstract (arXiv)

Interpretability is an essential building block for trustworthiness in reinforcement learning systems. However, interpretability might come at the cost of deteriorated performance, leading many researchers to build complex models. Our goal is to analyze the cost of interpretability. We show that in certain cases, one can achieve policy interpretability while maintaining its optimality. We focus on a classical problem from reinforcement learning: mazes with k obstacles in ℝd. We prove the existence of a small decision tree with a linear function at each inner node and depth O(log k + 2d) that represents an optimal policy. Note that for the interesting case of a constant d, we have O(log k) depth. Thus, in this setting, there is no accuracy-interpretability tradeoff. To prove this result, we use a new "compressing" technique that might be useful in additional settings.