MAVIPER: Learning Decision Tree Policies
for Interpretable Multi-Agent
Reinforcement Learning

In MARL, agents act in an environment defined by a Markov game [19, 38]. A Markov game for $N$ agents consists of a set of states $\mathcal{S}$ describing all possible configurations for all agents, the initial state distribution $\rho:\mathcal{S}\rightarrow[0,1]$, and the set of actions $\mathcal{A}_{1},...,\mathcal{A}_{N}$ and observations $\mathcal{O}_{1},...,\mathcal{O}_{N}$ for each agent $i\in[N]$. Each agent aims to maximize its own total expected return $R_{i}=\sum_{t=0}^{\infty}\gamma^{t}r_{i}^{t}$, where $\gamma$ is the discount factor that weights the relative importance of future rewards. To do so, each agent selects actions using a policy $\pi_{\theta_{i}}:\mathcal{O}_{i}\rightarrow\mathcal{A}_{i}$. After the agents simultaneously execute their actions $\overrightarrow{a}$ in the environment, the environment produces the next state according to the state transition function $P:\mathcal{S}\times\mathcal{A}_{1}\times...\times\mathcal{A}_{N}\rightarrow\mathcal{S}$. Each agent $i$ receives reward according to a reward function $r_{i}:\mathcal{S}\times\mathcal{A}_{i}\rightarrow\mathbb{R}$ and a private observation, consisting of a vector of features, correlated with the state $o_{i}:\mathcal{S}\rightarrow\mathcal{O}_{i}$.

Given a policy profile $\pi=(\pi_{1},...,\pi_{N})$, agent $i$’s value function is defined as: $V^{\pi}_{i}(s)=r_{i}+\gamma\sum_{s^{\prime}\in\mathcal{S}}P(s,\pi_{1}(o_{1}),...,\pi_{N}(o_{N}),s^{\prime})V^{\pi}_{i}(s^{\prime})$ and state-action value function is: $Q^{\pi}_{i}(s,a_{1},...,a_{N})=r_{i}+\gamma\sum_{s^{\prime}\in S}P(s,a_{1},...,a_{N},s^{\prime})V^{\pi}_{i}(s^{\prime})$. We refer to a policy profile excluding agent $i$ as $\pi_{-i}$.

MARL algorithms fall into two categories: value-based [35, 39, 41] and actor-critic [11, 16, 20, 48]. Value-based methods often approximate $Q$-functions for individual agents in the form of $Q^{\pi}_{i}(o_{i},a_{i})$ and derive the policies $\pi_{i}$ by taking actions with the maximum Q-values. In contrast, actor-critic methods often follow the centralized training and decentralized execution (CTDE) paradigm [30]. They train agents in a centralized manner, enabling agents to leverage information beyond their private observation during training; however, agents must behave in a decentralized manner during execution. Each agent $i$ uses a centralized critic network $Q^{\pi}_{i}$, which takes as input some state information $x$ (including the observations of all agents) and the actions of all agents. This assumption addresses the stationarity issue in MARL training: without access to the actions of other agents, the environment appears non-stationary from the perspective of any one agent. Each agent $i$ also has a policy network $\pi_{i}$ that takes as input its observation $o_{i}$.

DTs are tree-like models that recursively partition the input space along a specific feature using a cutoff value. These models produce axis-parallel partitions: internal nodes are the intermediate partitions, and leaf nodes are the final partitions. When used to represent policies, the internal nodes represent the features and values of the input state that the agent uses to choose its action, and the leaf nodes correspond to chosen actions given some input state. For an example of a DT policy, see Figure 1.

VIPER [2] is a popular algorithm [7, 21, 25] that extracts DT policies for a finite-horizon Markov decision process given an expert policy trained using any single-agent RL algorithm. It combines ideas from model compression [6, 13] and imitation learning [1] — specifically, a variation of the DAGGER algorithm [36]. It uses a high-performing deep NN that approximates the state-action value function to guide the training of a DT policy.

VIPER trains a DT policy $\hat{\pi}^{m}$ in each iteration $m$; the final output is the best policy among all iterations. More concretely, in iteration $m$, it samples $K$ trajectories $\{(s,\hat{\pi}^{m-1}(s))\sim d^{\hat{\pi}^{m-1}}\}$ following the DT policy trained at the previous iteration. Then, it uses the expert policy $\pi^{*}$ to suggest actions for each visited state, leading to the dataset $D^{m}=\{(s,\pi^{*}(s))\sim d^{\hat{\pi}^{m-1}}\}$ (Line 4, Alg. 3). VIPER adds these relabeled experiences to a dataset $\mathcal{D}$ consisting of experiences from previous iterations. Let $V^{\pi^{*}}$ and $Q^{\pi^{*}}$ be the state value function and state-action value function given the expert policy $\pi^{*}$. VIPER resamples points $(s,a)\in\mathcal{D}$ according to weights: $\tilde{l}(s)=V^{\pi^{*}}(s)-\min_{a\in A}Q^{\pi^{*}}(s,a)$. See Algorithm 3 in Appendix 0.A for the full VIPER algorithm.

Motivated by the practical success of single-agent RL algorithms in the MARL setting [23, 3], we extend single-agent VIPER to the multi-agent setting by independently applying the single-agent algorithm to each agent, with a few critical changes described below. Algorithm 1 shows the full IVIPER pseudocode.

First, we ensure that each agent has sufficient information for training its DT policy. Each agent has its own dataset $\mathcal{D}_{i}$ of training tuples. When using VIPER with multi-agent actor-critic methods that leverage a per-agent centralized critic network $Q^{\pi}_{i}$, we ensure that each agent’s dataset $\mathcal{D}_{i}$ has not only its observation and actions, but also the complete state information $x$ — which consists of the observations of all of the agents — and the expert-labeled actions of all of the other agents $\pi^{*}_{j}(o_{j})\forall j\neq i$. By providing each agent with the information about all other agents, we avoid the stationarity issue that arises when the policies of all agents are changing throughout the training process (like in MARL).

Second, we account for important changes that emerge from moving to a multi-agent formalism. When we sample and relabel trajectories for training each agent’s DT policy, we sample from the distribution $d^{\hat{\pi}_{i}^{m-1},\pi^{*}_{-i}}$ induced by agent $i$’s policy at the previous iteration $\hat{\pi}_{i}^{m-1}$ and the expert policies of all other agents $\pi^{*}_{-i}$. We only relabel the action for agent $i$ because the other agents choose their actions according to $\pi^{*}$. It is equivalent to treating all other expert agents as part of the environment and only using DT policy for agent $i$.

Third, we incorporate the actions of all agents when resampling the dataset to construct a new, weighted dataset (6, Algorithm 1). If the MARL algorithm uses a centralized critic $Q(s,\overrightarrow{a})$, we resample points according to:

where,

Crucially, we include the actions of all other agents in Equation 2 to select agent $i$’s minimum Q-value from its centralized state-action value function.

When applied to value-based methods, IVIPER is more similar to single-agent VIPER. In particular, in 4, Algorithm 1, it is sufficient to only store $o_{i}$ and $\pi_{i}^{*}(o_{i})$ in the dataset $\mathcal{D}_{i}^{m}$, although we still must sample trajectories according to $\hat{\pi}_{i}^{m-1}$ and $\pi_{-i}^{*}$. In 6, we use $\tilde{l}(x)=V^{\pi^{*}}_{i}(s)-\min_{a_{i}\in\mathcal{A}_{i}}Q^{\pi^{*}}_{i}(o_{i},a_{i})$ from single-agent VIPER, removing the reliance of the loss on a centralized critic.

Taken together, these algorithmic changes form the basis of the IVIPER algorithm. This algorithm can be viewed as transforming the multi-agent learning problem to a single-agent one, in which other agents are folded into the environment. This approach works well if i) we only want an interpretable policy for a single agent in a multi-agent setting or ii) agents do not need to coordinate with each other. When coordination is needed, this algorithm does not reliably capture coordinated behaviors, as each DT is trained independently without consideration for what the other agent’s resulting DT policy will learn. This issue is particularly apparent when trees are constrained to have a small maximum depth, as is desired for interpretability.

To address the issue of coordination, we propose MAVIPER, our novel algorithm for centralized training of coordinated multi-agent DT policies. For expository purpose, we describe MAVIPER in a fully cooperative setting, then explain how to use MAVIPER for mixed cooperative-competitive settings. At a high-level, MAVIPER trains all of the DT policies, one for each agent, in a centralized manner. It jointly grows the trees of each agent by predicting the behavior of the other agents in the environment using their anticipated trees. To train each DT policy, MAVIPER employs a new resampling technique to find states that are critical for its interactions with other agents. Algorithm 2 shows the full MAVIPER algorithm. Specifically, MAVIPER is built upon the following extensions to IVIPER that aim at addressing the issue of coordination.

First, MAVIPER does not calculate the probability $p(x)$ of a joint observation $x$ by viewing the other agents as stationary experts. Instead, MAVIPER focuses on the critical states where a good joint action can make a difference. Specifically, MAVIPER aims to measure how much worse off agent $i$ would be, taking expectation over all possible joint actions of the other agents, if it acts in the worst way possible compared with when it acts in the same way as the expert agent. So, we define $l_{i}(x)$, as in Equation 2, as:

MAVIPER uses the DT policies $(\hat{\pi}_{1}^{m-1},\dots,\hat{\pi}_{N}^{m-1})$ from the last iteration to perform rollouts and collect new data.

Second, we add a prediction module to the DT training process to increase the joint accuracy, as shown in the Predict function. The goal of the prediction module is to predict the actions that the other DTs $\{\hat{\pi}_{j}\}_{j\neq i}$ might make, given their partial observations. To make the most of the prediction module, MAVIPER grows the trees evenly using a breadth-first ordering to avoid biasing towards the result of any specific tree. Since the trees are not complete at the time of prediction, we use the output of another DT trained with the full dataset associated with that node for the prediction. Following the intuition that the correct prediction of one agent alone may not yield much benefit if the other agents are wrong, we use this prediction module to remove all data points whose proportion of correct predictions is lower than a predefined threshold. We then calculate the splitting criteria based on this modified dataset and continue iteratively growing the tree.

In some mixed cooperative-competitive settings, agents in a team share goals and need to coordinate with each other, but they face other agents or other teams whose goals are not fully aligned with theirs. In these settings, MAVIPER follows a similar procedure to jointly train policies for agents in the same team to ensure coordination. More specifically, for a team $Z$, the Build and Predict function is constrained to only make predictions for the agents in the same team. Equation 3 now takes the expectation over the joint actions for agents outside the team and becomes:

Taken together, these changes comprise the MAVIPER algorithm. Because we explicitly account for the anticipated behavior of other agents in both the predictions and the resampling probability, we hypothesize that MAVIPER will better capture coordinated behavior.

We evaluate our algorithms on three multi-agent particle world environments [20], described below. Episodes terminate when the maximum number of timesteps $T=25$ is reached. We choose the primary performance metric based on the environment (detailed below), and we also provide results using expected return as the performance metric in Appendix 0.C.

For each environment, we compare the DT policies generated by different methods and check if IVIPER and MAVIPER agents achieve better performance ratio than the baselines overall. We also investigate whether MAVIPER learns better coordinated behavior than IVIPER. Furthermore, we investigate which algorithms are the most robust to different types of opponents. We conclude with an ablation study to determine which components of the MAVIPER algorithm contribute most to its success.