As deep reinforcement learning (RL) is applied to more tasks, there is a need to visualize and understand the behavior of learned agents. Saliency maps explain agent behavior by highlighting the features of the input state that are most relevant for the agent in taking an action. Existing perturbation-based approaches to compute saliency often highlight regions of the input that are not relevant to the action taken by the agent. Our approach generates more focused saliency maps by balancing two aspects (specificity and relevance) that capture different desiderata of saliency. The first captures the impact of perturbation on the relative expected reward of the action to be explained. The second downweights irrelevant features that alter the relative expected rewards of actions other than the action to be explained. We compare our approach with existing approaches on agents trained to play board games (Chess and Go) and Atari games (Breakout, Pong and Space Invaders). We show through illustrative examples (Chess, Atari, Go), human studies (Chess), and automated evaluation methods (Chess) that our approach generates saliency maps that are more interpretable for humans than existing approaches.
[score raised from weak reject to weak accept after rebuttal - on a more fine-grained scale, I would rate this paper now an accept (7), but not a strong accept (8), however since this year's scale is quite coarse, I'll stick with a score of 6]
Summary
The paper proposes a new perturbation-based measure for computing input-saliency maps for deep RL agents. As reported in a large body of literature before, such saliency maps are supposed to help “explain” why a deep RL system picked a certain action. The measure proposed in the paper aims at combining two aspects: specificity and relevance, which should ensure that the saliency map highlights inputs that are relevant for a particular action to be explained (specificity), and this particular action only (relevance). The paper shows illustrative examples of the proposed approach and two previously proposed alternatives on Chess, Go and three Atari games. Additionally the paper evaluates the method and the two previous alternatives on two interesting chess-tasks: chess-puzzles where human players were shown to be able to solve puzzles faster and with higher accuracy when given the proposed saliency map in addition, and evaluation against a curated dataset of human-expert saliency maps for 100 chess puzzles. 
Contributions
i) Novel, perturbation-based saliency measure composed of two parts. Main idea of specificity is (similar to Iyer et al. 2018) to use State-Action value function (Q-function) with a specific action, instead of State-Value function only. Main idea of relevance is to “normalize” by taking into account change in Q-value for all other actions as well. Both parts are combined in a heuristic fashion.
ii) More objective/reproducible assessment of how saliency maps produced by different methods overlap with human judgement of saliency of pieces in chess. To this end: two experiments with human chess players/experts (puzzle solving, and expert-designed saliency maps).
Quality, Clarity, Novelty, Impact
The paper is well written and most sections are easily understandable, though for some parts it might help if the reader is quite familiar with Chess/Go. The proposed saliency measure seems to address some shortcomings of previously proposed measures - my main criticism is that the construction of the measure seems rather ad-hoc and heuristic. It would have been great to formally define specificity and relevance (e.g. in an information-theoretic framework as Sparse Relevant Information) and then derive a suitable measure that is shown to satisfy/approximate the formal definitions. At least, there is one ablation study that justifies parts of the heuristic construction to some degree. 
The proposed measure seems to do reasonably well on board-game domains, in particular chess. However it might also be the case that the measure does particularly well for generating saliency maps for Stockfish (which is the agent that happens to be evaluated in the chess domain), which might be quite different from previously reported methods that have been designed for deep neural network RL agents. The illustrative examples on Atari and Go do not allow for a statistically significant judgement of the quality of the proposed method.
On a conceptual level, a bigger issue (of many saliency methods in general, but the criticism also applies to the paper) is that the “explanations” drawn from saliency maps are rarely evaluated rigorously. The paper makes a nice attempt by trying to establish some “ground-truth” saliency in chess using humans to increase the degree of objectivity, which I greatly appreciate. However, it remains unclear whether explanations that happen to coincide with human notions of saliency really are of higher quality for assessing how an artificial system makes its decisions. The main goal of explainability/interpretability methods must be to come up with testable hypotheses that tell us something about how the artificial system makes its decisions in novel/unseen situations. The goal is not to explain a decision mechanistically after the fact (which is trivial, given a deterministic, differentiable feed-forward system), but to come up with non-trivial explanations that extrapolate/generalize. Specificity and Relevance are probably important ingredients of such explanations, but I think it’s important to formalize them properly first. Currently I am in favor of suggesting a major revision of the work, but I am happy to reconsider my decision based on the rebuttal and other reviewers’ assessment. Having said that, I do want to reiterate that I think it is great that the authors included some ablation studies and measures of “usefulness” of the saliency method.
Improvements / Major comments
i) Formally define specificity and relevance (e.g. as sparsity and compression?). Ideally derive a saliency measure based on these formal definitions.
ii) Show how saliency maps (of the same situation) change when producing explanations for different actions. I assume that currently the illustrative examples only show the action with the highest Q-value, what changes when using e.g. a less likely action?
iii) Show that the saliency map stays roughly constant for seemingly irrelevant perturbations. In particular, using the chess-dataset with expert annotations, apply various kinds of perturbations to non-salient pieces (e.g. removing them, swapping them for other pieces and potentially moving them in irrelevant ways) and see whether the AUC stays roughly constant.
iv) Apply non-relevant perturbations to the salient pieces. I.e. take the same puzzle/scene and move it across the board, does the saliency-map move in (roughly) the same way.
v) The saliency method might be particularly suited for Stockfish (whose action-value estimates might be strongly influenced by human saliency and chess theory). See whether the method still produces good results for other chess agents (ideally trained without human heuristics or data). If this is hard to do for chess, think about a different application where this is easier.
vi) Add a section that discusses current shortcomings and caveats with the method, and saliency maps for explainability in general.
vii) (Experimental details) For each domain, please explain the perturbations that you used (removing pieces in Chess/Go, blurring pixels in Go, anything else e.g. replacing pieces?). In all experiments, was it always the action with the highest Q-value that was being explained?
Minor comments
a) Table 1: (add error-bars) What is the variance across players? Are the results for the proposed method statistically significant?
b) Chess saliency dataset. Are the expert saliency ratings binary? Why not have multiple degrees of saliency?
c) Would the Greydanus et al. 2018 approach deliver similar results when using a threshold to cut off low-saliency inputs?
d) Why is the saliency map in 3.4 binary (pieces are either salient or not)? How was the binarization threshold chosen? What would the non-binary saliency maps look like?
e) Please provide all experimental details (in the appendix) that are necessary to reproduce the experiments. Referring to a code-repository is not a replacement for describing the methods in detail.