RGMDT: Return-Gap-Minimizing Decision Tree Extraction in Non-Euclidean Metric Space

📄 arXiv: 2410.16517v1 📥 PDF

作者: Jingdi Chen, Hanhan Zhou, Yongsheng Mei, Carlee Joe-Wong, Gina Adam, Nathaniel D. Bastian, Tian Lan

分类: cs.LG, cs.AI

发布日期: 2024-10-21

💡 一句话要点

RGMDT：非欧度量空间中基于回报差距最小化的决策树提取方法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 强化学习 可解释性 决策树 多智能体系统 非欧式聚类

📋 核心要点

  1. 现有强化学习决策树提取方法主要集中于单智能体环境，多智能体场景缺乏定量保证。
  2. 论文提出一种基于回报差距最小化的决策树提取方法RGMDT，将决策树提取问题转化为非欧式聚类问题。
  3. 实验结果表明，RGMDT在D4RL等任务上显著优于启发式基线，并在给定约束下接近最优回报。

📝 摘要（中文）

深度强化学习(DRL)算法在解决许多具有挑战性的任务中取得了巨大成功，但其黑盒特性阻碍了解释性和实际应用，使得人类专家难以解释和理解DRL策略。现有的可解释强化学习工作在从DRL策略中提取基于决策树(DT)的策略方面显示出希望，但大多集中在单智能体设置中，而先前在多智能体场景中引入DT策略的尝试主要集中在启发式设计上，没有提供关于预期回报的任何定量保证。本文建立了oracle专家策略和最优决策树策略之间的回报差距的上界。这使我们能够将DT提取问题重新定义为每个智能体的局部观察和动作值空间上的新型非欧式聚类问题，其中动作值作为聚类标签，回报差距的上界作为聚类损失。通过由以其他智能体的当前DT为条件的动作值函数引导的迭代增长DT过程，算法和上界都被扩展到多智能体分散DT提取。此外，我们提出了回报差距最小化决策树(RGMDT)算法，这是一个非常简单的设计，并通过利用一种新的正则化信息最大化损失与强化学习集成。在D4RL等任务上的评估表明，RGMDT显著优于基于启发式DT的基线，并且可以在给定的DT复杂性约束(例如，DT节点的最大数量)下实现接近最优的回报。

🔬 方法详解

问题定义：现有的深度强化学习算法具有黑盒特性，难以解释和理解其决策过程，限制了其在实际场景中的应用。虽然已有一些工作尝试从DRL策略中提取决策树，但大多集中在单智能体环境，并且在多智能体环境中缺乏对预期回报的定量保证。因此，如何有效地从DRL策略中提取可解释的决策树策略，并保证其性能，是一个重要的研究问题。

核心思路：论文的核心思路是将决策树的提取问题转化为一个非欧式空间的聚类问题。具体来说，对于每个智能体，将局部观察和动作值空间视为一个非欧式空间，动作值作为聚类标签，而决策树策略与最优策略之间的回报差距的上界作为聚类损失。通过最小化这个回报差距，可以得到一个性能较好的决策树策略。

技术框架：RGMDT算法的整体框架包括以下几个主要步骤：1) 建立oracle专家策略和最优决策树策略之间的回报差距的上界；2) 将决策树提取问题转化为非欧式聚类问题；3) 设计回报差距最小化决策树(RGMDT)算法，利用正则化信息最大化损失与强化学习集成；4) 在多智能体环境中，通过迭代增长DT的过程，扩展算法到多智能体分散DT提取。

关键创新：论文的关键创新在于：1) 建立了oracle专家策略和最优决策树策略之间的回报差距的上界，为决策树提取提供了理论基础；2) 将决策树提取问题转化为非欧式聚类问题，为解决该问题提供了一种新的视角；3) 提出了回报差距最小化决策树(RGMDT)算法，该算法简单有效，并且可以与强化学习算法集成。

关键设计：RGMDT算法的关键设计包括：1) 使用动作值作为聚类标签，利用回报差距的上界作为聚类损失；2) 设计正则化信息最大化损失，以鼓励决策树策略的多样性；3) 在多智能体环境中，使用迭代增长DT的过程，并利用其他智能体的当前DT来指导当前智能体的决策树增长。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，RGMDT算法在D4RL等任务上显著优于基于启发式DT的基线。例如，在给定的DT复杂性约束下，RGMDT可以实现接近最优的回报，证明了该算法的有效性。相比于启发式方法，RGMDT在性能上有显著提升。

🎯 应用场景

该研究成果可应用于需要可解释性的强化学习场景，例如自动驾驶、医疗诊断、金融交易等。通过提取易于理解的决策树策略，可以帮助人类专家理解和信任AI系统的决策过程，从而提高系统的可靠性和安全性，并促进人机协作。

📄 摘要（原文）

Deep Reinforcement Learning (DRL) algorithms have achieved great success in solving many challenging tasks while their black-box nature hinders interpretability and real-world applicability, making it difficult for human experts to interpret and understand DRL policies. Existing works on interpretable reinforcement learning have shown promise in extracting decision tree (DT) based policies from DRL policies with most focus on the single-agent settings while prior attempts to introduce DT policies in multi-agent scenarios mainly focus on heuristic designs which do not provide any quantitative guarantees on the expected return. In this paper, we establish an upper bound on the return gap between the oracle expert policy and an optimal decision tree policy. This enables us to recast the DT extraction problem into a novel non-euclidean clustering problem over the local observation and action values space of each agent, with action values as cluster labels and the upper bound on the return gap as clustering loss. Both the algorithm and the upper bound are extended to multi-agent decentralized DT extractions by an iteratively-grow-DT procedure guided by an action-value function conditioned on the current DTs of other agents. Further, we propose the Return-Gap-Minimization Decision Tree (RGMDT) algorithm, which is a surprisingly simple design and is integrated with reinforcement learning through the utilization of a novel Regularized Information Maximization loss. Evaluations on tasks like D4RL show that RGMDT significantly outperforms heuristic DT-based baselines and can achieve nearly optimal returns under given DT complexity constraints (e.g., maximum number of DT nodes).