There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes
This addresses the challenge of building trustworthy RL systems by demonstrating that interpretability can be maintained without performance loss in specific maze environments, though it is incremental as it focuses on a classical problem.
The paper tackles the problem of achieving interpretability in reinforcement learning without sacrificing performance, specifically for mazes with k obstacles in ℝ^d, and proves the existence of a small decision tree with depth O(log k + 2^d) that represents an optimal policy, showing no tradeoff for constant d.
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 $\mathbb{R}^d$. We prove the existence of a small decision tree with a linear function at each inner node and depth $O(\log k + 2^d)$ 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.