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

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-06
Main Authors: Mansour, Yishay, Moshkovitz, Michal, Rudin, Cynthia
Format: Article
Language:English
Subjects:
Cost analysis
Decision trees
Linear functions
Maze learning
Optimization
Tradeoffs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422