mlsanityData to 14 Oct 2026

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

arXiv 2206.04266 ↗First posted 9 Jun 2022cs.LGcited by 4

Not on the map. Why?

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.

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

12 of 26 references.

References · 12

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2021Interpretable Machine Learning: Fundamental Principles and 10 Grand Challengescited by 367
  3. 2018Programmatically Interpretable Reinforcement Learningcited by 193
  4. 2018Verifiable Reinforcement Learning via Policy Extractioncited by 177
  5. 2017Hierarchical and Interpretable Skill Acquisition in Multi-task Reinforcement Learningcited by 77
  6. 2020Explainable k-Means and k-Medians Clusteringcited by 67
  7. 2018Toward Interpretable Deep Reinforcement Learning with Linear Model U-Treescited by 65
  8. 2019Interestingness Elements for Explainable Reinforcement Learning: Understanding Agents' Capabilities and Limitationscited by 50
  9. 2019Conservative Q-Improvement: Reinforcement Learning for an Interpretable Decision-Tree Policycited by 29
  10. 2018Deep Reinforcement Learning for Dynamic Treatment Regimes on Medical Registry Datacited by 23
  11. 2021Connecting Interpretability and Robustness in Decision Trees through Separationcited by 16
  12. 2021Explainable k-means. Don't be greedy, plant bigger trees!cited by 15

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2024DILA: Dictionary Label Attention for Mechanistic Interpretability in High-dimensional Multi-label Medical Coding Predictioncited by 4
  2. 2025A Survey of Reinforcement Learning for Optimization in Automationcited by 4
  3. 2025Evaluating Interpretable Reinforcement Learning by Distilling Policies into Programscited by 3
  4. 2026Price of Fairness in Short-Term and Long-Term Algorithmic Selectionscited by 0