Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposed a distributional RL algorithm that based on Sinkhorn divergence. It derived the theoretical guarantee for Sinkhorn divergence with the distributional Bellman operators and evaluated empirical performances on Atari games.

strengths_and_weaknesses: Strengths: 

This paper is well-written and easy to follow, and it is interesting to learn the connections between different approaches from a unified framework. 

Weakness:
I have two major concerns about this paper:
1. The novelty of this paper. The relationship among Wasserstein distance, MMD and Sinkhorn divergence has been studied in existing literatures [1]. 
The discussion of the Sinkhorn divergence and MMD and a Gaussian kernel looks very interesting, however, it seems unrelated to the experiment part given that SinkhornDRL is not using a Gaussian kernel.

2. The empirical performances (Figure 1 and Figure 4) of SinkhornDRL is not strong enough to demonstrate SinkhornDRL outperforms the other algorithms, where MMD and SinkhornDRL perform similarly on 10/18 tasks.

[1]: Genevay, Aude, Gabriel Peyré, and Marco Cuturi. "Learning generative models with sinkhorn divergences." International Conference on Artificial Intelligence and Statistics. PMLR, 2018.
questions: 1. It would be great to have more justifications on why the 2nd term on eq(12) will goes to 0 when $\epsilon\rightarrow\infty$ since the multiplication of $\infty$ and $\log(1)$ can be undetermined.
2. Why not using the same Gaussian kernel for MMD and SinkhornDRL to validate their theoretical relations by changing $\epsilon$?
3. Is the conclusion from Figure 2 (a) and Figure 3 (a) not super aligned with each other? Figure 2(a) demonstrates that a Sinkhorn divergence in DRL is better than QRDQN with Wasserstein distance, while Figure 3 (a) shows that a smaller $\epsilon$ doesn't affect the performance much. I didn't fully get it because the Sinkhorn divergence with a small $\epsilon$ will degenerate to Wasserstein distance as shown in Theorem 1.

limitations: The authors have addressed the major limitation of this paper with potential future directions.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper under review studied the problem of distributional reinforcement learning (DRL).
Instead of (expected) value function, DRL aim to learn the entire value distribution.
Hence to optimize (solve distributional Bellman equation), 
one needs to pick a norm to measure distances between distributions.
In this paper, the authors proposed to use Sinkhorn divergence.
They proved that distributional Bellman operator under Sinkhorn divergence 
interpolates between Wasserstein distance and MMD. 
Moreover, they show that distributional Bellman operator is non-expansive 
and approximately performs a regularized moment matching.
Furthermore, based on Sinkhorn iteration, the authors provided algorithms 
for DRL with Sinkhorn divergence, and demonstrated its efficiency under Atari games.

strengths_and_weaknesses: Strengths:
The paper is well written and easy to follow.
The idea of using Sinkhorn divergence is natural and interesting.
The theoretical results are nicely stated and proved.
The non-expansive on Bellman operator (Thm 1) 
and Equivalence to Regularized MMD (Cor 1) have potential applications in the field. 


Weaknesses:
The main concern is the motivation.

It is unclear why the authors proposed to use Sinkhorn divergence as a norm.
Because it interpolates between Wasserstein distance and MMD
or because it has properties that other existing approaches do not have? 
Or it is just another norm, out preform other algos in some cases.

In the experiment section, the authors demonstrated that SinkhornDRL
is "extremely superior over existing algorithms" on some games. 
The question is then what is the characterization of these games?
and why Sinkhorn is better in these cases? 

More interestingly, could the authors say a bit more on 
when Wasserstein is better, and when MMD is better 
(probably depends on the sparsity of the OT plan).
This may lead to some guideline on choice of $\epsilon$ per game.

questions: Q1: Does the choice of $\epsilon$ matter? The authors mentioned multiple times that Sinkhorn allows 
a trade-off that simultaneously leverages the geometry of the Wasserstein distance ($\epsilon \to 0$) and the
unbiased gradient estimate property of MMD ($\epsilon \to \infty$). 
However, in the sensitivity analysis (sec 5.2), the authors claimed that SinkhornDRL is robust to the choice of $\epsilon$ along with 
other hyper-parameters.



Q2: Fig 3 are plots for the game Breakout. Do similar behaviors appear for other Atari games? For example, seaquest.
According to Fig 2, Sinkhorn shows near zero improvement compare to MMD and QRDQN (i.e. three of them behaved similarly).
Hence it seems that Breakout, the game itself is not sensitive to the choice of $\epsilon$, 
or even the choice of norm (its hard to believe L=2 and L=50 give the same norm Fig 3(c)).
What is the cost function for Breakout? 
maybe the cost is either close to a uniform or diagonal matrix, which makes hyper-parameters no long matter.


limitations: The authors mentioned that the main limitation of SinkhornDRL is that the superiority over existing state-of-the-art algorithms may
not be sufficiently significant. And also authors conjectured that to extend  SinkhornDRL for better performance, implicit generative
models, including parameterizing the cost function in Sinkhorn divergence shall be further incorporated. 
Maybe hyperparameter tuning shall be take into consideration too.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper presents a new approach to distributional reinforcement learning based on regularized optimal transport. The authors present an implementable algorithm based on Sinkhorn iterations for approximating the Sinkhorn divergence, and investigate the performance of this approach on the Atari suite of games.

---

I thank the authors for their engagement during the discussion. The updates made during this period have improved the paper in my view, particularly regarding the main theoretical result. I still have two key reservations about this result in its current form, which was uploaded shortly before the end of the discussion period:
 - First, the statement is not presented clearly: "T^pi is a closely non-expansive operator" is not a precise mathematical statement. Reading the appendix proof means it can be inferred what is meant here, but in terms of clarity I found this to be poor.
 - Second, the proof is not written clearly, and this makes checking the proof more difficult as well, and I am not 100% confident about the validity of the proof. Aside from a general lack of clarity in the mathematical argument, some of the issues include:
    - Assuming the existence of densities.
    - Some typos (Eqns (39), (40), 1/Z_1 should be 1/Z_2; equation below Line 518 is missing an implication sign; Line 510 K(2U,2V) should be K(aU, aV)).
    - In the proof, it is apparent that the term Delta^c_{mu, nu} depends on the two distributions mu and nu, meaning that the operator is not uniformly "almost a contraction", but this is not made clear in the theorem statement, which is potentially misleading.

My current standing is that the core algorithmic contribution is interesting, although I still have reservations about the quality of the presentation (including the description above) and the experimental results.
strengths_and_weaknesses: Overall, I think there is a nice central algorithmic contribution in this paper. The Sinkhorn approach to distributional RL is novel as far as I am aware, and is likely to be of interest to the deep RL community at NeurIPS. I think there are some instances of incorrect results in the paper currently, which means I don't think the paper can be accepted currently, but I would be happy to revise my rating if the authors can address this, or potentially remove the incorrect parts of the results if they can't be resolved.

Strengths:
 - In my view, this is an interesting, unexplored approach to distributional reinforcement learning, which interpolates between two known approaches, based on Wasserstein distances and MMD.
 - The implemented algorithm performs well in Atari, generally comparing favorably to several existing approaches to distributional RL, and this approach is likely to be of interest to deep reinforcement learning researchers.
 - In addition to the core Atari results, the authors also include a sensitivity analysis regarding the two key hyperparameters their method uses, demonstrating that the method is fairly robust to the choice of these hyperparameters.

Weaknesses:
 - I think Theorem 1 as stated is not true. More details are given below. This is partly the reason for a "reject" recommendation currently, but I would be very happy to revise this rating if the authors can address the concerns.
 - The experimental evaluation setting is slightly non-standard, training for 10M rather than 200M frames on Atari. I couldn't find information about how hyperparameters were selected, e.g. were any sweeps/preliminary runs carried out? This is important information for properly interpreting the reported results.
 - I think there are currently some overly-strong claims made in the paper (e.g. "SinkhronDRL only slightly increases the computational cost", see below) that the authors could consider revising.

questions: Theorem 1: (1) & (2). These results are making limiting statements as eps -> 0, infty, but then seem to be drawing conclusions about general epsilon, which I don't think is valid; perhaps there is a typo here? If these are just statements about the limited values eps=0, and eps->infty, it should be made clearer that these results are not original to this paper. This is the same for the expectation part of (3), which I think is attributable to Bellemare et al. (2017).

Part (3) seems to contradict the counterexample given by Nguyen et al. (2020). More specifically, Nguyen et al. provide an example in which sup-MMD_k(T^pi Z_1, T^pi Z_2) > sup-MMD_k(Z_1, Z_2). Given that the Sinkhorn divergence approaches the MMD as eps -> infty, this example must also apply to the case of Sinkhorn divergences for sufficiently large epsilon, so I don't think it is true that the distributional Bellman operator is a non-expansion under Sinkhorn divergences in general.

Looking at the proof, I think there are a couple of steps which aren't valid/require more care:
 - Equation (28). It seems to be forgotten here that s', a' are random variables, and so the inequality that appears in this sequence of equations requires further justification.
 - Equation (30). I think one of the key issues here is that Pi^* depends on the distributions of the input random variables in a potentially complicated way, while I think the claimed derivation here assumes that Pi* for aX and aY is obtainable through a simple change of variables from that of X and Y. 

In summary, I think part (3) of Theorem 1 is not correct as stated.

Other questions/notes:

It is unclear to me what Table 1 is intended to communicate. The convergence rates/contraction rates stated are with respect to different metrics, so these are difficult to compare. I was also unsure the relevance of the sample complexity column it looks as though these are upper-bounds on expected error in estimating the metric with empirical distributions, but it is unclear to me why this is relevant to distributional reinforcement learning, where generally single transition samples are used. These bounds are also stated with general d in some cases, whereas d=1 in distributional reinforcement learning. Can the authors clarify what readers are intended to take from this table?

Line 289: The authors state "SinkhronDRL only slightly increases the computational cost", but Figure 10 in Appendix F seems to indicate that SinkhornDRL is around 50% slower than baselines such as QR-DQN, which is arguably more than a slight increase. It would have been interesting to see how dependent this is on the value of L too. The sensitivity analysis indicates (on Breakout) that the approach is robust to taking L as low as 2. Does this bring the computational cost in line with other distributional RL approaches? Does this robustness generalize to other games?

In general I found the experiments to be clearly presented, although further information on hyperparameter sweeps, preliminary runs, and selection would help improve their interpretability; can the authors provide this information? Were 10M frames (rather than 200M) used for computational/resource reasons (this is not necessarily a problem if so)? How were the 9 games in Figure 1 selected for the main paper?

There are some typos to address throughout the paper. Some examples are:
Line 8: "Bellmen" -> "Bellman"
Line 19: Duplicate reference 7 -> I expect one of these is meant to be [6]?
Line 205: "Proof of Corollary" -> "Proof of Corollary 1"
Line 219: "differential" -> "differentiable"?

Minor technical notes:
Equation (1): Should be equal in distribution.
Line 174: "General case eps in (0, eps)". This is presumably a typo? Can the authors clarify what is meant here?
limitations: The inclusion of the computational cost comparison in Appendix F is very useful, although I think the comparison is not currently accurately reflected in the main text (see above).
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes to use the Sinkhorn divergence in distributional RL (DRL),  a relatively novel framework for RL that uses the full action-value distribution rather than its expected value, the Q-function, and that has led to good results in various application domains.  The Sinkhorn divergence has been studied previously in non-RL ML settings, and was shown to interpolate between optimal transport measures and the MMD divergence, both of which account for the geometry of the underlying spaces, and were studied in previous DRL papers. From a theoretical perspective the authors analyze the convergence properties of the distributional Bellman operators, and establish a regularized MMD equivalent form. Empirical comparisons are provided for ATARI problems. 

Following the discussion and authors' response I have increased my grade from 5 to 6, supporting the acceptance of the paper. 
strengths_and_weaknesses: **Strengths** The paper is based on previous DRL methods using the optimal transport (OT) measures and MMD, by combining them into the Sinkhorn divergence, as done previously in different ML contexts (e.g., [10]). Their main theoretical contribution is item 3 in Theorem 1, demonstrating the contraction properties of the Sinkhorn divergence (items 1 and 2 follow directly from previous work, and are stated in [11]). On the empirical side, they demonstrate competitive results on the ATARI tasks. 

**Weakness**
The main issue with the paper, as far as I see it, pertains to its level of novelty w.r.t. previous work. It essentially combines known previous ideas (the Sinkhorn divergence as an interpolant between OT and MMD measures, and DRL), and suggests a new DRL algorithm that takes advantage of the combined merits. Importantly, the main merit of using the Sinkhorn measure, its lack of dependence on the dimension, appears already in [11].  
If I understood correctly, there is no proof that Algorithm 2 converges, or bounding its finite sample error for a given value of L. This is an important issue in the overall convergence of the algorithm. Below Algorithm 2 the authors state that “It suggests that the Sinkhorn iteration can asymptotically converge to the true loss in a linear rate” – what does ‘suggest’ mean? What does ‘can converge’ imply? Under what conditions? 

The authors refer several times to the ‘unbiased gradient estimate of MMD’ that leads to superior performance. However, this is never discussed or explained, while playing a major role in their arguments. 

Re the empirical results, it would be good if the authors discussed the exploratory properties of the algorithm, vis-à-vis other DRL methods, as these play a key role in many challenging RL tasks. For example, it appears that in the Montezuma Revenge game, that is known to require careful exploration, they do worse than other DRL approaches. 

**Minor points** Section 2.2 does not distinguish between scalar and vector random variables (as is done in the appendix). For example, eq. (3) holds only for scalars. Even if they only use this case, this point should be mentioned. In eq. (4) the MMD should include arguments (distributions or RVs). Also, X’ and Y’ are not defined. 

Algorithm 1 is described as an “RL Algorithm”. However, it is not a full RL algorithm, but, rather, just the update step. For the reader’s sake, it would be clearer if the authors presented pseudo-code for the full RL algorithm, even if parts of it are standard. 

questions: (1) Please address the convergence issues raised for algorithm 2. (2) The notion of exploration is not mentioned in the present work, and, indeed, it seems that the performance of the algorithm on problems requiring significant explorations, such as the Montezuma revenge, are inferior. It would be nice to get some insight from the authors on this issue. 
limitations: The paper, while nicely combining previous ideas, does not go much beyond previous results.
review_title: null

Meta-review: metareview: All reviewers acknowledged that this paper is an interesting contribution to the distributional RL literature. Some concerns brought up by reviewers in their initial reports included issues with the statement of Theorem 1, a non-standard evaluation protocol for the Atari experiments, and that some claims were overly strong, such as the robustness claim of Figure 3. 

During the discussion, reviewers found that the rebuttal addressed a few of these concerns, but that a few concerns still remained.
While the claims of Theorem 1 have been revised significantly, and the reviewers appreciated this. However, the clarify of the statement is still not clearly presented, and the reviewers could not verify the correctness of the proof in its current form. For instance, one reviewer pointed out that"T^pi is a closely non-expansive operator" is not a precise mathematical statement and is not clearly defined in the paper. Another point was that the proof could be more clear and therefore it was difficult to verify its correctness, in addition to a number of typos: (Eqns (39), (40), 1/Z_1 should be 1/Z_2; equation below Line 518 is missing an implication sign; Line 510 K(2U,2V) should be K(aU, aV)).

Several other reviewers were not convinced by the empirical results in that they felt like the paper would be stronger if (1) it used the same evaluation protocol as other distributional RL papers and (2) results on the behavior of the algorithm when sweeping over key hyperparameters (epsilon, cost choice, L), would also considerably strengthen the paper by clarifying how the method works in practice.

Overall, reviewers found the contribution to be promising and a step in the right direction. After another revision addressing these issues, I think the paper will be a strong contribution to the distributional RL literature. 

confidence: Certain
Decision: Reject