  To this day, a variety of approaches for providing local interpretability of
black-box machine learning models have been introduced. Unfortunately, all of
these methods suffer from one or more of the following deficiencies: They are
either difficult to understand themselves, they work on a per-feature basis and
ignore the dependencies between features and/or they only focus on those
features asserting the decision made by the model. To address these points,
this work introduces a reinforcement learning-based approach called Monte Carlo
tree search for eXplainable Artificial Intelligent (McXai) to explain the
decisions of any black-box classification model (classifier). Our method
leverages Monte Carlo tree search and models the process of generating
explanations as two games. In one game, the reward is maximized by finding
feature sets that support the decision of the classifier, while in the second
game, finding feature sets leading to alternative decisions maximizes the
reward. The result is a human friendly representation as a tree structure, in
which each node represents a set of features to be studied with smaller
explanations at the top of the tree. Our experiments show, that the features
found by our method are more informative with respect to classifications than
those found by classical approaches like LIME and SHAP. Furthermore, by also
identifying misleading features, our approach is able to guide towards improved
robustness of the black-box model in many situations.
