# Limits of Actor-Critic Algorithms for Decision Tree Policies Learning in IBMDPs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 49 references that are in the map.
- First posted on arXiv 23 Sep 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI](https://mlsanity.com/paper/1910.10045/) (2019)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Interpretable machine learning: definitions, methods, and applications](https://mlsanity.com/paper/1901.04592/) (2019)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Asymmetric Actor Critic for Image-Based Robot Learning](https://mlsanity.com/paper/1710.06542/) (2017)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [Explainable Reinforcement Learning Through a Causal Lens](https://mlsanity.com/paper/1905.10958/) (2019)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [Interpreting CNNs via Decision Trees](https://mlsanity.com/paper/1802.00121/) (2018)
- [Supersparse Linear Integer Models for Optimized Medical Scoring Systems](https://mlsanity.com/paper/1502.04269/) (2015)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Learning When-to-Treat Policies](https://mlsanity.com/paper/1905.09751/) (2019)
- [Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methods](https://mlsanity.com/paper/2102.13045/) (2021)
- [A Survey of Explainable Reinforcement Learning](https://mlsanity.com/paper/2202.08434/) (2022)
- [Continuous Action Reinforcement Learning from a Mixture of Interpretable Experts](https://mlsanity.com/paper/2006.05911/) (2020)
- [Optimization Methods for Interpretable Differentiable Decision Trees in Reinforcement Learning](https://mlsanity.com/paper/1903.09338/) (2019)
- [Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policies](https://mlsanity.com/paper/1608.04996/) (2016)

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

- [Towards a Research Community in Interpretable Reinforcement Learning: the InterpPol Workshop](https://mlsanity.com/paper/2404.10906/) (2024)

## Abstract (arXiv)

Interpretability of AI models allows for user safety checks to build trust in such AIs. In particular, Decision Trees (DTs) provide a global look at the learned model and transparently reveal which features of the input are critical for making a decision. However, interpretability is hindered if the DT is too large. To learn compact trees, a recent Reinforcement Learning (RL) framework has been proposed to explore the space of DTs using deep RL. This framework augments a decision problem (e.g. a supervised classification task) with additional actions that gather information about the features of an otherwise hidden input. By appropriately penalizing these actions, the agent learns to optimally trade-off size and performance of DTs. In practice, a reactive policy for a partially observable Markov decision process (MDP) needs to be learned, which is still an open problem. We show in this paper that deep RL can fail even on simple toy tasks of this class. However, when the underlying decision problem is a supervised classification task, we show that finding the optimal tree can be cast as a fully observable Markov decision problem and be solved efficiently, giving rise to a new family of algorithms for learning DTs that go beyond the classical greedy maximization ones.