# Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methods

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 65 references that are in the map.
- First posted on arXiv 25 Feb 2021.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [Policy Distillation](https://mlsanity.com/paper/1511.06295/) (2015)
- [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)
- [Neural Episodic Control](https://mlsanity.com/paper/1703.01988/) (2017)
- [Visualizing and Understanding Atari Agents](https://mlsanity.com/paper/1711.00138/) (2017)
- [Model-Free Episodic Control](https://mlsanity.com/paper/1606.04460/) (2016)
- [Reinforcement Learning with Parameterized Actions](https://mlsanity.com/paper/1509.01644/) (2015)
- [Neuroevolution of Self-Interpretable Agents](https://mlsanity.com/paper/2003.08165/) (2020)
- [Interpretable Policies for Reinforcement Learning by Genetic Programming](https://mlsanity.com/paper/1712.04170/) (2017)
- [Transparency and Explanation in Deep Reinforcement Learning Neural Networks](https://mlsanity.com/paper/1809.06061/) (2018)
- [Learning Finite State Representations of Recurrent Policy Networks](https://mlsanity.com/paper/1811.12530/) (2018)
- [Generation of Policy-Level Explanations for Reinforcement Learning](https://mlsanity.com/paper/1905.12044/) (2019)
- [What can I do here? A Theory of Affordances in Reinforcement Learning](https://mlsanity.com/paper/2006.15085/) (2020)
- [Conservative Q-Improvement: Reinforcement Learning for an Interpretable Decision-Tree Policy](https://mlsanity.com/paper/1907.01180/) (2019)
- [Towards Better Interpretability in Deep Q-Networks](https://mlsanity.com/paper/1809.05630/) (2018)
- [Explaining Reinforcement Learning to Mere Mortals: An Empirical Study](https://mlsanity.com/paper/1903.09708/) (2019)
- [Particle Swarm Optimization for Generating Interpretable Fuzzy Reinforcement Learning Policies](https://mlsanity.com/paper/1610.05984/) (2016)
- [Retrospective Analysis of the 2019 MineRL Competition on Sample Efficient Reinforcement Learning](https://mlsanity.com/paper/2003.05012/) (2020)
- [Mo"ET: Mixture of Expert Trees and its Application to Verifiable Reinforcement Learning](https://mlsanity.com/paper/1906.06717/) (2019)
- [Distal Explanations for Model-free Explainable Reinforcement Learning](https://mlsanity.com/paper/2001.10284/) (2020)
- [Learn to Interpret Atari Agents](https://mlsanity.com/paper/1812.11276/) (2018)

## Built on by (most cited first, 30 of 31)

- [A Survey on Interpretable Reinforcement Learning](https://mlsanity.com/paper/2112.13112/) (2021)
- [A Survey of Explainable Reinforcement Learning](https://mlsanity.com/paper/2202.08434/) (2022)
- [Interpretable and Editable Programmatic Tree Policies for Reinforcement Learning](https://mlsanity.com/paper/2405.14956/) (2024)
- [End-to-End Neuro-Symbolic Reinforcement Learning with Textual Explanations](https://mlsanity.com/paper/2403.12451/) (2024)
- [MAVIPER: Learning Decision Tree Policies for Interpretable Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2205.12449/) (2022)
- [MIXRTs: Toward Interpretable Multi-Agent Reinforcement Learning via Mixing Recurrent Soft Decision Trees](https://mlsanity.com/paper/2209.07225/) (2022)
- [A Snapshot of Influence: A Local Data Attribution Framework for Online Reinforcement Learning](https://mlsanity.com/paper/2505.19281/) (2025)
- [Explainable Multi-Agent Reinforcement Learning for Temporal Queries](https://mlsanity.com/paper/2305.10378/) (2023)
- [Optimal Decision Tree Policies for Markov Decision Processes](https://mlsanity.com/paper/2301.13185/) (2023)
- [Breiman meets Bellman: Non-Greedy Decision Trees with MDPs](https://mlsanity.com/paper/2309.12701/) (2023)
- [Fairness and Sequential Decision Making: Limits, Lessons, and Opportunities](https://mlsanity.com/paper/2301.05753/) (2023)
- [LICORICE: Label-Efficient Concept-Based Interpretable Reinforcement Learning](https://mlsanity.com/paper/2407.15786/) (2024)
- [Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization](https://mlsanity.com/paper/2408.08761/) (2024)
- [Optimizing Interpretable Decision Tree Policies for Reinforcement Learning](https://mlsanity.com/paper/2408.11632/) (2024)
- [A Survey on Explainable Reinforcement Learning: Concepts, Algorithms, Challenges](https://mlsanity.com/paper/2211.06665/) (2022)
- [Evaluating Interpretable Reinforcement Learning by Distilling Policies into Programs](https://mlsanity.com/paper/2503.08322/) (2025)
- [Learning Decision Trees as Amortized Structure Inference](https://mlsanity.com/paper/2503.06985/) (2025)
- [Limits of Actor-Critic Algorithms for Decision Tree Policies Learning in IBMDPs](https://mlsanity.com/paper/2309.13365/) (2023)
- [In Search of Trees: Decision-Tree Policy Synthesis for Black-Box Systems via Search](https://mlsanity.com/paper/2409.03260/) (2024)
- [Why the Agent Made that Decision: Contrastive Explanation Learning for Reinforcement Learning](https://mlsanity.com/paper/2411.16120/) (2024)
- [Towards Automated Semantic Interpretability in Reinforcement Learning via Vision-Language Models](https://mlsanity.com/paper/2503.16724/) (2025)
- [Selecting Decision-Relevant Concepts in Reinforcement Learning](https://mlsanity.com/paper/2604.04808/) (2026)
- [Optimal Interpretability-Performance Trade-off of Classification Trees with Black-Box Reinforcement Learning](https://mlsanity.com/paper/2304.05839/) (2023)
- [Constraint-Generation Policy Optimization (CGPO): Nonlinear Programming for Policy Optimization in Mixed Discrete-Continuous MDPs](https://mlsanity.com/paper/2401.12243/) (2024)
- [Towards a Research Community in Interpretable Reinforcement Learning: the InterpPol Workshop](https://mlsanity.com/paper/2404.10906/) (2024)
- [From Actions to Words: Towards Abstractive-Textual Policy Summarization in RL](https://mlsanity.com/paper/2503.10509/) (2025)
- [Exploring Explainable Multi-agent MCTS-minimax Hybrids in Board Game Using Process Mining](https://mlsanity.com/paper/2503.23326/) (2025)
- [Understanding Action Effects through Instrumental Empowerment in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2508.15652/) (2025)
- [SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes](https://mlsanity.com/paper/2510.19241/) (2025)
- [Explaining Reinforcement Learning Agents via Inductive Logic Programming](https://mlsanity.com/paper/2607.13655/) (2026)

## Abstract (arXiv)

Current work in explainable reinforcement learning generally produces policies in the form of a decision tree over the state space. Such policies can be used for formal safety verification, agent behavior prediction, and manual inspection of important features. However, existing approaches fit a decision tree after training or use a custom learning procedure which is not compatible with new learning techniques, such as those which use neural networks. To address this limitation, we propose a novel Markov Decision Process (MDP) type for learning decision tree policies: Iterative Bounding MDPs (IBMDPs). An IBMDP is constructed around a base MDP so each IBMDP policy is guaranteed to correspond to a decision tree policy for the base MDP when using a method-agnostic masking procedure. Because of this decision tree equivalence, any function approximator can be used during training, including a neural network, while yielding a decision tree policy for the base MDP. We present the required masking procedure as well as a modified value update step which allows IBMDPs to be solved using existing algorithms. We apply this procedure to produce IBMDP variants of recent reinforcement learning methods. We empirically show the benefits of our approach by solving IBMDPs to produce decision tree policies for the base MDPs.