Distributional Reinforcement Learning via Sinkhorn Iterations
Authors: Ke Sun
Yingnan Zhao
Yi Liu
Bei Jiang
Linglong Kong
Venue: NeurIPS 2022 Submitted (2022)
Keywords: distributional reinforcement learning
sinkhorn divergence

Abstract: Distributional reinforcement learning~(RL) is a class of state-of-the-art algorithms that estimate the whole distribution of the total return rather than only its expectation. The representation manner of each return distribution and the choice of distribution divergence are pivotal for the empirical success of distributional RL. In this paper, we propose a new class of \textit{Sinkhorn distributional RL~(SinkhornDRL)} algorithm that learns a finite set of statistics, i.e., deterministic samples, from each return distribution and then leverages Sinkhorn iterations to evaluate the Sinkhorn distance between the current and target Bellmen distributions. Remarkably, Sinkhorn divergence interpolates between the Wasserstein distance and Maximum Mean Discrepancy~(MMD). This allows our proposed SinkhornDRL algorithm to find a sweet spot leveraging the geometry of optimal transport-based distance and the unbiased gradient estimates of MMD. Finally, experiments on the suit of 55 Atari games reveal the competitive performance of SinkhornDRL algorithm as opposed to existing state-of-the-art algorithms.

Classical reinforcement learning (RL) algorithms normally based the expectation of discounted cumulative rewards that an agent observes while interacting with the environment. Recently, a new class of RL algorithms called distributional RL estimates the full distribution of total returns and has exhibited the state-of-the-art performance in a wide range of environments 2 Distributional Reinforcement Learning via Sinkhorn Iterations
Anonymous Author(s)
Affiliation Address
email
Abstract
Distributional reinforcement learning (RL) is class of state-of-ther of-thh--rttttttt algorithms that estimate the whole distribution of the total return rather than only its expec- tation. The representation manner of each return distribution and the choice of distribution divergence are pivotal for the empirical success of distributional RI. In this paper, we propose new class of Sinkhorn distributional RI. (Sinkhorn- DRL) algorithm that learns a finite set of statistics, i.c., deterministic samples, from each return distribution and then leverages Sinkhorn iterations to evaluate the Sinkhorn distance between the current and target Bellman distributions. Re- markably, Sinkhorn divergence interpolates between the Wasserstein distance and Maximum Mean Discrepancy (MMD). This allows our proposed SinkhorDDRL algorithm to find sweet spot leveraging the geometry of optimal transport based distance and the unbiased gradient estimates of MMD. Finally, experiments on the suit of 55 Atari games reveal the competitive performance of SinkhornDRI. algorithm as opposed to existing state-of-the-art algorithms.
10
12
14
Introduction
15
17
18
19
From the literature of distributional RL, it is easily recognized that algorithms based either Wasserstein distance or MMD have gained great attention due to their superior performance. As such, their mutual connection from the perspective of mathematical properties intrigues to explore further in order to design new algorithms. Particularly. Wasserstein distance, long known to be a powerful tool compare probability distributions with non-overlapping supports, has recently emerged appealing contender various machine learning applications. It is known that Wasserstein distance was long disregarded because of its computational burden in its original form to solve expensive network flow problem. However, recent works [21] [4] have shown that this cost can be largely mitigated by settling for cheaper approximations through strongly convex regularizers. The benefit of this regularization has opened the path to wider applications of the Wasserstein distance in relevant learning problems, including the design of distributional RL algorithms.
21
23
25
27
28
29
30
31 The Sinkhorn divergence [21] introduces the entropic regularization on the Wassertein distance, allowing it tractable for the evaluation especially in high-dimensions. It has been successfully applicd 39 in numerous crucial machine learning developments, including the Sinkhorn- GAN [1] and Sinkhorn- based adversarial training 23). More importantly, has been shown that Sinkhorn divergence interpolates Wasserstein ditance and MMD, and their equivalence form can be well established the
35
36 limit cases [II 18 17] However, Sinkhorn-based distributional RL algorithm has not yet been
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37 formally proposed and its connection with algorithms based on Wasserstein distance and MMD is
38 also less studied. Therefore, natural question can we design a new class of distributional RL algorithms via Sinkhorn divergence, thus bridging the gup between existing two main branches of distributional RL. algorithms? Moreover, the dominant quantile-bar -ased algorithms, e.g., QR-DQN [8], aimed at approximating Wasserstein distance, suffers from the non-crossing issue in the quantile estimation [26). while sample-based Sinkhorn algorithm can naturally circumvent this problem.
39
40
41
42
43
In this paper, we propose a novel distributional RL algorithm based on Sinkhorn divergence. Firstly, we point out the key roles of distribution divergence and representation of value distribution in the design of distributional RL. After detailed introduction of our proposed SinkhomDRL algorithm, we theoretically analyze its convergence guarantee and moment matching behavior of distributional Bellman operators under Sinkhorn divergence. Thus, regularized MMD equivalence form of Sinkhorn divergence is derived, interpreting the emprical success of our algorithms in real applications. Finally, we compare the performance of our SinkhornRI. algorithm with typical baselines on 55 Atari games, verifying the competitive performance of our proposal. Our approach inspires researchers
44
45
46
47
48
49
50
51 to find trade-off that simultaneously leverages the geometry of the Wasserstein distance and the
52 favorable unbiased gradient estimate property of MMD while designing new distributional RL algorithms in the future.
53
2
Preliminary Knowledge
54
55 2.1
Distributional Reinforcement Learning
56 In the classical RL setting, an agent interacts with an environment via a Markov decision pro- cess (MDP), a 5-tuple (S, (S,A, RG ?)),, where S and A are the state and action spaces, respectively. P the environment transition dynamics, R is the reward function and y E (0, 1) is the discount factor.
57
58
From Value function to Value distribution. Given a policy the discounted sum of future rewards is a random variable as,,a) Ei= ? R(st, az), where so s. ag a, St+1 ~ 61 P(-|st. oz), and 04 ~ TT([s)). In the control setting, expectation based RL is based on the action- value function (s a). which is the expectation of 2 (s, a), i.e., (s, a) = [2 (2 a)). By contrast, distributional RL focuses on the action-valus distribution, the full distribution of Z" (s. a). and the incorporation of additional distributional knowledge intuitively interprets its empirical success.
59
80
62
63
64
65
Distributional Bellman operators. For the policy evaluation in expectation- RI., the action- value function updated via the Bellman operator Q'Q a) = E|R(s a)] +.B./-pr IQ (s', (s',a') a²)] In distributional RL, the action-value distribution of Z a) is updated via the distributional Bellman operator T
66
68
Z²)(s,a)= R(s, a) 7 (s',a').
where s' ~ (()ss,a) and a' 1 (-|s'). The equality in Eq. D implies that random variables of both sides are equal in distribution. The distributional Bellman operator I contractive under certain distribution divergence metrics, but the distributional Bellman optimality operator I can only converge to a set of optimal non-stationary value distributions in a weak sense
70
71
72
73
2.2
Divergences between Measures
Optimal Transport (OT) and Wasserstein Distance The optimal transport (OT) metric between two probability measures (μ, v)) supported on two metric spaces is defined as the solution of the linear program:
75
f f(ae, ((x.))dl(zx.))
min I
(2)
77 where is the cost function and II is the joint distribution with marginals (,,v). Wasserstein distance
78 (a.k.a. earth mover distance) is special case of optimal transport with the Euclidean norm as the
79 cost function. In particular, given two scalar random variables X and Y, D-aasserstein metric W
80 between the distributions of X and Y can be simplified as
Wx,,X = ( F [x (w) Fy (w) dw) 1/p
(3)
2

---

81 where F-1 is the inverse cumulative distribution function of a random variable. The desirable
82 geometric property of Wasserstein distance allows recover full support of measures, but it suffers
83 from the curse of dimension 13
84 Maximum Mean Discrepancy The squared Maximum Mean Discrepancy (MMD) MMD with
85
the kernel & is formulated as
MMD = E x E - 2E (xX,
(4)
86
where k((,,)) is a continuous kernel on X. X' (resp. Y') is random variable independent of X (resp. Y). If & is a trivial kernel, MMD degenerates to the energy distance. Mathematically, the "flat" geometry that MMD induces on the space of probability measures does not faithfully lift the ground distance [[I,, but MMD is cheaper to compute than OT and has smaller sample complexity, i.e., We provide the detailed introduction of
87
86
90
approximating the distance with samples of measures [13 more distribution divergences in Appendix A
91
3
Roles of Distribution Divergence and Representation in distributional RL
93
3.1
Distributional RL: From Neural Q-Fitted Iteration to Neural Z-Fitted Iteration
94
Neural Q-Fitted Iteration. It is known that Deep Q Learning [16] can be simplified into Neural F-Fitee Iteration [T0] under tricks experience replay and the target network Qø where we update parameterized Q+(s,a) in each iteration k:
95
Q = aargmin
Σ y/ - Q6 (s a.)) n 1=1
(5)
Qo
97 where the target = r(;;, 0;) + max O (5/2 a) is fixed within every Turger steps to update
98 target network Qo- by letting H" and the experience buffer induces independent samples
99 {(s ae, Tú, sx) ve[m] In an ideal case that neglects the non-convexity and TD approximation errors,
100 we have Q = TQ². which is exactly equivalent to updating under Bellman optimality operator.
Neural Z-FFitted Iteration. Analogous to neural Q-fitted iteration, we can also simplify value-based distributional RL methods based on a parameterized Zo into Neural Z-fated Iteration as
102
1 dYi 2 (si, a:));
zk+1
argmin Za
(6)
where the target Y, R(s;, a;) ZZz (s/, (s()) with Tz('') argmax, E [Z]- (s', a')] is fixed within every Turget steps to update target network Zge, and d, is a divergence metric between two distributions.
104
105
3.2
Key Roles of d,, and Ze
107
Within the Neural Z-fitted Iteration framework proposed in Eq. 66 we observe that the choice of representation manner on Ze and the metric dp are pivotal for the distributional RL algorithms. For instance, QR-DQN 8 approximates Wasserstein distance W,, which leverages quantiles to represent
109
Algorithm
dp Distribution Divergence
Representation Ze
Convergence Rate of 3"
Sample Complexity of d,
CSI
Cramér distance Wasserstein distance
Histogram
V
QR-DQN
S
Quantiles
O(n 2) O(1/m)
MMDDRL
h
MMD
Samples
3 with kernel R
SinkhoruDRL
(5
Oln (E O(n } oc)
(ours)
Sinkhom divergence
Samples
0/2 (2 x0)
Table 1: Comparison between typical distributional RL algorithms under different distribution divergences and represention of Zg. k. - ||r: y|la in MMDDRL, d is the sample dimension and
2,dd + ||c|loe, where the cost function e 3-Lipschitz [[3] Sample complexity of MMD can be improved to (1/n) using kernel herding technique [5].
3

---

110
the distribution of Zg. C51 2 represents Zg via a categorical distribution under the convergence of Cramér distance 19, while MMD distributional RL (MMDDRL) [77] learns samples to represent the distribution of Zo based on MMD. We compare characteristics of these distribution divergence, including the convergence rate and sample complexity, in Table [ Theoretical results regarding Sinkhorn divergence is based on [ and the detailed convergence proof of other distances is also provided in Appendix A In summary, we argue that dp and Zg are two crucial factors in distributional RL design, based on which we introduce our Sinkhorn distributional RL.
111
112
113
114
115
4 Sinkhorn Distributional RL (SinkhornDRL)
118
In this section, we firstly introduce Sinkhorn divergence and apply it in distributional RL. Next, we conduct theoretical analysis about the convergence speed and new moment matching manner of our algorithm under the Sinkhorn divergence. Finally, a practical Sinkhorn iteration algorithm is introduced to evaluate the Sinkhorn divergence.
120
122
4.1
Sinkhorn Divergence and Genetic Algorithm
123
We design Sinkhorn distributional RL algorithm via Sinkhorn divergence. Sinkhorn divergence 21 a tractable loss to approximate the optimal transport problem by leveraging entropic regularization to turn the original Wasserstein distance into a differentiable and more robust quantity. The resulting loss can be computed using Sinkhorn fixed point iterations, which is naturally suitable for modern deep learning frameworks. In particular, the entropic smoothing generates a family of losses interpolating between Wasserstein distance and Maximum Mean Discrepancy (MMD). As such, it allows us to find a sweet trade-off that simultancously leverages the geometry of Wasserstein distance on the one hand, and the favorable high- high-dimensional sample complexity and unbiased gradient estimates of MMD. We introduce the entropic regularized Wassertein distance We, (H, 2/) as
124
125
127
129
131
/ c(2, (III)) ( &
min nell(().)
132 where ( = log (u(z)dr(y))
aTT v) is strongly convex regularization. The impact of this entropy regularization is similar to & ridge regularization in linear regression. Next, the
[1(ay))
133
134 sinkhorn loss [ 14] between two measures j and is defined as
We,c(u,)) = 2W..(u,v) - We,z(1, 11) W,,(U,
(8)
135
As demonstrated by (1I the Sinkhorn divergence We (u, v) is convex, smooth and positive definite that metrizes the convergence in law. In statistical physics, We,e v)) can be re-factored as a projection problem:
136
137
We,s (n, v) = min KL (1I)K),
NEl(())
where IC is the Gibbs distribution with the density function satisfies dK((x, y) clwa)) du(z)) dv(()).
138
139
This problem is often referred to as the "static Schrödinger problem" [5 20 as it was initially considered in statistical physics.
140
141
Distributional RL with Sinkhorn Divergence and Particle Representation. The key of apply- ing Sinkhorn divergence in distributional RI. is to simply leverage the Sinkhorn loss W..r to mea- sure the distance between the current action-value distribution Za a) and the target distribution I Zs, a), yielding We.e(Zo(s. a), T Zo(s.a)) for each s, pairs. In terms of the representation for (s, a). we employ the unrestricted statistics, i.e., deterministic samples, due to its superiority in MMDDRL [17). instead of using predefined statistic functionals, e.g., quantiles in QR-DQN g or histogram partitions in C51 22 More concretely, we use neural networks to generate samples that approximate the value distribution. This can be expressed Za(s, a) == (Zo(s, a): / where N is the number of generated samples. We refer to the samples (Zo(s, a) I particles. Then
142
143
145
146
147
148
leverage the Dirac mixture & òzals.a) to approximate the true density function of 27 a), thus minimizing the Sinkhorn divergence between the approximate distribution and its distributional Bellman target. A detailed and generic distributional RI. algorithm with Sinkhorn divergence and particle representation is provided in Algorithm
150
152

---

Algorithm Generic Sinkhorn distributional RL Update
Require: Number of generated samples N, the cost function and hyperparameter Input: Sample transition (s, as,a,7 r',',,r" r'))
1: if Policy evaluation then
2:
TT-Is").
3: else
4: a" <- arg max. 1 Ei Zo (s'
5: end if
SiSN Output: We.e ( (520(,)))))
6: IZ f- r + ZZ-
154
Remark. By comparing the state-of-the-ar MMDDRL algorithm [17. our Sinkhorn distributional
155
RL simply modifies the distribution divergence. Hence. we can also easily extend our generic Sinkhorn algorithm to DQN-like architecture well IQN 7 and FQF 241. A following question is whether there is any theoretical connection between Sinkhorn distributional RL and algorithms
156
157
158
based on MMD and Wasserstein distance. We provide this crucial analysis in Section 4.2
4.2
Theoretical Analysis under Sinkhorn Divergence
Convergence Analysis.
Firstly, we denote the supreme form of Sinkhorn divergence W (1, W (,,
161
sup Was(u(z,a)) v(x,
(10)
(z,a)ESXA
We will use W (1,, to establish the convergence of R in Theorem
169
Theorem 1. If we leverage Sinkhorn loss Wa.( v) in Eq. 8 as the distribution divergence in distributional RI, and choose the unrectified kernel hig - -Ia yll -c (a > 0), it holds that
164
As - W.elu,D) 2WW((,, When 0. I"h is c-cottraction under W
(2) +00, W.. (1,) - .MMD (H, v). When e +o0, T is 70/2 22//2-ccom -contractive under We.
186
(3) For any E E +00), I" is closely non-expansive operator under Wa and the difference term A(7) + 0 as +
187
188
Proof provided in Appendix B Theorem [ (1) and (2) are follow-up conclusions in terms of the convergence behavior of " based on the interpolation relationship between Sinkhorn divergence with Wasserstein distance and MMD [4. Our key theoretical contribution is for the general the convergence behavior is determined by the "joint" KL divergence in Eq. Detween the optimal joint distribution II" and the Gibbs distribution associated with the cost function c. We conclude that I" is close non-expansive operator and the different term A(r) + 0 as - 1. Note that is normally very close to 1 in practice, and this is beneficial for the convergence of I under W
169
170
171
(0, oc),
172
173
174
178
Remark Theorem (3). If consider to use Gaussian kernel, we can not guarantee I" is closely expaassae for any E (0, oo). This conclusion is consistent with those discussed in MMDDRL [7], where Ix is generally not a contraction operator under MMD equipped with Gaussian kernels as counterexample has been pointed out in MMDDRL (when e + +oc). When
177
178
179
180
E + 0, the y-contractive I under Wasserstein distance is also not contradictory to Theorem 1 (3). Moreover, although we can only obtain that Ix is closely non-expansive, the expectation of
182
7" remains 7-contraction (see Appendix B). In experiments, we thereby use ki, and we can also demonstrate the appealing empirical performance of our SinkhornDRI. algorithm in Section
183
194
Regularized Moment Matching under Sinkhorn Divergence. We further examine the potential
185
reason behind the empirical success for SinkhomDRL, although only non-expansive contraction can be guaranteed for the general case when e (0, +ox) as shown Theorem [ Inspired by the similar manner in MMDDRL. 17 we find that the Sinkhorn divergence with the Gaussian kernel can also promote to match all moments between two distributions. More specifically, the Sinkhorn divergence can be rewritten as regularized moment matching form in Proposition
186
188
5

---

190 Proposition 1. For & E (0, too), Sinkhorn divergence W We.e (p, associated with Gaussian kernels 191 k(r,y) = exp( - (x y) (2/2) as -c, can be equivalent to
00
(XT( n (Ma())- MMav)) &E log I!Ç(X, ([(XXX))TEE(X XY))
WaS We v)
(II)
where 11I denotes the optimal 11 determined by by evaluating the Sinkhorn divergence via minnem(py) Wo, (,,,H, Mn(H) = Eguu e -= (20()2))
xmm) and similarty for Mn).).
193
We provide the proof of Proposition I in Appendix C Similar to MMDDRL associated with Gaussian kernel [17] Sinkhorn divergence approximately performs regularized moment matching
195
scaled by e-=² /2=0 (20 This similar moment matching impact intuitively explains the empirical success of DiL MMDDRL, although the contraction of both MMD with Gaussian kernel [17 and Sinkhorn divergence for general é E (0, +oo) may not be guaranteed.
196
197
198
Based on Proposition I we can immedi- ately establish the connection between Sinkhorn divergence and MMD in Corollary I indicating that minimizing Sinkhorn divergence between two distributions is equivalent minimizing regularized
Equivalence to Regularized MMD distributional RL.
200
202
squared MMD.
Corollary 1. For E (0, +00) and denote II; as the optimal 11 by evaluating the Sinkhorn divergence, holds that
204
(I((XY)) We,e == MMD" v) + EE log IX, ("IXXX
(12)
205
where we use Wa. to replace Wo, (n, for short.
206
Proof of Corollary T is provided in Appendix C It worthy of noting that this equivalence is established for the general case when E (0, too), and it does not hold in the limit cases when ε + 0 or +00, For example, when E - +00, the second part including in Eq. 12 is not expected to dominate. This owing to the fact that the regularization term would be 0 as T. - μa when
208
209
210 8 + + In summary, even though the Sinkhorn divergence was initially proposed to serve as an regularized MMD, as This connection provides strong evidence for our empirical results, which SinkhorDDL achieves competitive performance opposed MMDDRL.
entropy regularized Wasserterin distance, it turns that it is equivalent
212
revealed in Corollary [
213
4.3
Distributional RL via Sinkhorn Iterations
215
The theoretical analysis in Section 4.2 sheds light on the behavior of distributional RL with Sinkhorn divergence, but another crucial issue we need to address is how to evaluate the Sinkhorn loss effectively. Due to the advantages of Sinkhorn divergence that both enjoys geometry property of optimal transport and the computational effectiveness of MMD, we can utilize Sinkhorn's 's algorithm, ie., Sinkhorn Iterations [21] [14, to evaluate the Sinkhorn loss. Notably, Sinkhorn itcration with L steps yields differentiable and solvable efficiently loss function the main burden involved in it is the matrix-vect vector multiplication, which streams well on the GPU with simply adding extra differentiable layers the typical deep neural network, such DQN architecture.
217
219
221
Specifically, given two sample sequences {Z,) [ in the distributional RL algorithm, the optimal transport distance is equivalent to the form:
PER x N (P, PIN 1N P 1n),
min
(13)
225
where the empirical cost function ر. (2, By adding entropic regularization on optimal transport distance, Sinkhorn divergence can be viewed to restrict the search space of P in the
226
227
following scaling form:
Pr a,K
(14)
where Kr.j / is the Gibbs kernel defined in Eq. This allows to leverage iterations regarding the vectors and b. More specifically, we initialize bp = 1v. and then the Sinkhorn iterations are expressed
229
230
01+1 f- In and b + KTa441
1N
(15)
Kb.

---

Algorithm 2 Sinkhorn Iterations Approximate We,e (Z {Σ
Input: Two samples sequences {2.1 i- 1 N rameter E.
f=1 number of Sinkhorn iterations L and hyperpa-
I: Ci.j c( (Zi,5Z)) [2,) for Vi = 1,... N,, N....N
2: Ki,j = =exp( exp(-(t,j/e)
3: bo 1N
4: for I = 1, 1,2, ..., do
5:
4 Kb x-
IN
K.:
1y
6: end for
7: WaS (Zi)]=1 (32]) ((K@(())))) @)b,
Return: We,6 ((2)) (52))
where: indicates entry-wise division. It has been proven that Sinkhorn iteration asymptotically converges to the true loss in a linear rate 62. We provide a detailed algorithm description of Sinkhorn iterations in Algorithm 2 With the efficient and differential Sinkhorn iterations, we can casily evaluate the Sinkhorn divergence and thus let our algorithm enjoy its theoretical advantages. In practice, we need to choose L and E, and we conduct a rigorous sensitivity analysis in Section 3
232
234
Experiments
236
We demonstrate the effectiveness of SinkhorDDRL as described in Algorithm on the full 55 Atari 2600 games. Specifically, we leverage the same architecture as QR-DQN (8). replace the quantiles output with N particles, i.e., samples. In contrast to MMDDRL, SinkhomDRL only changes the distribution divergence from MMD to Sinkhorn divergence, and therefore the potential superiority in the performance can be attributed to the advantages of Sinkhorn divergence. In Section |.11 we make
238
240
242 a rigorous comparison between SinkhornDRL with other typical distributional RL algorithms from the perspectives of learning curves and final ratio improvement of returns. An extensive sensitivity analysis in terms of multiple hyperparameters in SinkhornDRL. is provided in Section 5.2
244
245
Due to the interpolation characteristic of Sinkhorn divergence between Wassertein distance and MMDDRL, we choose three typical distributional RL algorithms as classic baselines, including QR-DQN 8 that approximates the Wasserstein distance, C51 and MMDDRL [17] as
Baselines.
248
247
well as DQN 16. MMDDRL. algorithm is implemented with the same architecture as QRDQN, and leverages Gaussian kernels k, (z. y) = cxp(-(x: y)²/h with the kernel mixture trick covering a range of bandwidths h, which is same as the basic setting in the original MMDDQN paper [17]. We deploy all algorithms on 55 Atari 2600 games, and reported results are averaged over 3 seeds with the shade indicating the standard deviation.
248
250
251
253
Hyperparameter settings. For a fair comparison with QR-DQN, C51 and MMDDRL, we used the same hyperparamters: the number of generated samples N 200, Adam optimizer with = 0.00005, Adamm = 0.01/33 We used a target network to compute the distributional Bellman target, which fits well in the neural Z-fitted iteration framework. In addition,
255
256
choose number of Sinkhorn iterations = 10 and smoothing hyperparameter & = 10.0 in Section 5.] as they are not sensitive within proper interval as demonstrated in Section 5.2 We choose the unrectified kernel as
257
258
259
the cost function, i.e.-c hig, and select a = 2 in ka in our SinkhornDRL. algorithm.
280
5.1
Performance of SinkhornDRL
261
Figure iillsttratss that SinkhorDRL can achieve the competitive performance across 55 Atari games compared with various baseline algorithms with different metrics dp and representation manners on Zo. On a large number of games, e.g., Tennis, Seaquest and Atlantis, SinkhornDRL can significantly outperform other baselines, especially on Tennis where other algorithms even fail to converge. The improvement of SinkhornDRI. over MMDDRL. empirically verifies the regularization advantage of
262
263
265
the Sinkhorn analyzed in Corollary [
On some games, e.g., Breakout, Pong and Invders,,,
7

---

Tennis
Se Beaquest
Atlantis
DOM
1480)
04
CCh
14.00
30
CE1
Average Return
MMC
PMO
Average Rotum
Sistium
8000
200
60
0.8
6. Steps (fc7)
80
02
Steps (107)
Time Steps (107)
Spaceinvaders
Breakout
Pong
2000
DGN
440
OROGN
Average Retum
VMC
Average Return
1750
NMD
Selknam
GHEON
100
Saninom
12:50
Average
1000
2.0
750
12
100
0.6
1.0
Time Steps (107)
Time Steps (1e7)
Time Steps (1e7)
Phoenix
Name Game Game
WizardOWWor
2200
50000
50000
Average Return
GRDON
MMD
20000
6000
Siretom
10000
5000
4000
18000
2000
Time Steps (107)
Time Steps (1e7)
Time Stops (1c7)
Figure 1: Learning curves of SinkhornDRI. algorithm compared with DQN, C51, QR-DQN and MMD, on nine typical Atari games over 3 seeds.
267
SinkhornDRLL is on par with MMDDRL and other baselines, while on the last row in Figure [ SinkhornDRL is slightly inferior to the state-of-the-arr algorithm. We provide learning curves of all typical distributional RL algorithms on all 55 Atari games in Appendix where SinkhornDRL still achieves the competitive performance in general.
269
271 To further demonstrate theoretical properties of SinkhomDRL in Theorem I we conduct ratio im- provement comparison across 55 Atari games between SinkhorDDRL with QRDQN and MMDDRL, respectively. Figure showcases that by comparing with QRDQN (left), SinkhornDRL achieves better performance across more than half of considered games. More importantly, the superiority of SinkhornDRI. is significant across a large amount of games, including Venture, Seaquest, Tennis and Phoenix. This empirical outperformance verifies the effectiveness and potential of smoothing Wassertein distance distributional RL, c.g., Sinkhorn divergence. In contrast with MMDDRL, the superiority of SinkhomDRL is reduced with the performance improvement only on a small proportion of games, while a remarkable boost of performance for SinkhorDDRL on a large amount of games can be easily observed. We also report mean and median of best of Appendix D where SinkhomDDL achieves almost state-of ofhthe-rrt performance as MMDDRL on average.
272
273
275
276
277
279
scores in Table
281
283
Therefore, we conclude that Sin is competitive with the state-of-the-art distributional RL algorithms, e.g., MMDDRI, and can be extremely superior over existing algorithms on large proportion of games. This empirical success can be owing to theoretical advantage of Sinkhorn divergence that simultaneously makes full use of the data geometry from Wasserstein distance and the unbiased gradient estimate property from MMD, which coincides with results in Theorem
285
287
208
5.2
Sensitivity Analysis and Computational Cost
Figure 3 (a) suggests the performance of our algorithm robust to E certain range, e.g., [1, 500), facilitating its deployment in practice. If we increase SinkhornDLL's performance tends to MMD,
289
8

---

Sinkhorn QRDQN (%)
Sinkhorn MMD (%)
Ratio Improvment (%)
Ratio Improvment (%)
(a) Sinkhorn vs QRDQN
(b) Sinkhorn vs MMDDRL
Figure 2: Ratio improvement of return for Sinkhorn distributional RL algorithm over QRDQN (left) and MMDDRL (right) over 3 seeds. For example, the ratio improvement is calculated by (Sinkhomn QRDQN) QRDQN in the left.
291 while we gradually decline E, SinkhornDRL's performance tends to QR-DQN. It is also noted that Sinkhorn iterations in Algorithm 2 will suffer from the numerical instability issue under an overly small or large &. More results with the discussion are provided in Appendix [F] is also illustrated that algorithm is insensitive the number of iterations 7. and samples N as well, but overly
283
295
large N can slightly worsen the performance of SinkhorDDRL, and at the same time increases the
298
computational burden. Therefore, proper number of samples, e.g., 200, sufficient to attain an appealing performance with the computational effectiveness.
297
For the computation cost, SinkhronDRL indeed increases around 50% computation cost compared with QR-DQN and C51, but only slightly increases the cost (by around 20%) in contrast to MMDDRL. Detailed comparison is given in Appendix
299
Breakout
Breakout
Breakout
e11
Saroks-s0
Sumoks-20
Average Relam
6-520
Sampkka-00
Samphee220
Avarage Retur
30
07
044
2.5
Steps (167)
(1e7)
(167)
(a) Hyper-parameter
(b) Number Samples
(c) Sinkhorn Iterations
Figure 3: Sensitivity analysis of SinkhomDRL Breakout regarding E, number of samples, and number of iteration L. Learning curves are reported over 3 seeds.
6 Discussions and Conclusion
The main limitation of our proposal is that the superiority over existing state-of-the-arr algorithms may not be sufficiently significant. To extend our algorithm for better performance, implicit generative models, including parameterizing the cost function in Sinkhorn loss, can be further incorporated. We leave it as the future work. Moreover, other divergences, e.g.. thoses that can also smooth Wassertein distance, can also be applied into the design of distributional RL algorithms in the future.
303
305
307
In this paper, a novel family of distributional RL algorithms based on Sinkhorn Divergence is proposed that accomplishes competitive performance compared with the-state-off of-te-of-the-aad
308
the-arhtrrrr art distributional RL algorithms on 55 Atari games. Theoretical analysis about the convergence and moment matching behavior is provided along with rigorous empirical verification. Albeit being associated with MMD algorithm, distributional RI. with Sinkhorn divergence is complementary to previous algorithms, leading to important contribution among the research community.
309
311

---

References
313
314
[1] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pages 214-223. PMLR, 2017.
[] Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspectivee reinforce- ment learning. International Conference on Machine Learning (ICML), 2017.
317
318
[3] Mare G Bellemare, Ivo Danihelka, Will Dabney, Shakir Mohamed, Balaji Lakshminarayanan, Stephan Hoyer, and Rémi Munos. The cramer distance as a solution to biased wasserstein gradients. arXiv preprint arXiv: 170.. 2017.
320
321
[4] Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Marc G Bellemare. Dopamine: A research framework for deep reinforcement learning. CoRR abs/1812.06110., 2018.
322
323
324
[5] Yutian Chen, Max Welling, and Alex Smola. Super-samples from kernel herding. UAI, 109-116.
325
AUAI Press, 2012.
[6] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
327
328
[7]
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. International Conference on Machine Learning (ICML), 2018.
330
331
88]
Will Dabney, Mark Rowland, Marc G Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. Association for the Advancement of Artificial Intelligence (AAAI), 2018.
332
333
99] Odin Elie and Charpentier Arthur. Dynamic Programming in Distributional Reinforcement 334
335
Learning. PhD thesis, Université du Québec à Montréal, 2020.
336
[10] Janning Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep g-learnigg In Learning for Dynamics and Control, pages 486-489. PMLR, 2020.
337
338
[1]] Jean Feydy, Thibault Séjourné, François-Xave Xavier Vialard, Shun-ichi Amari, Alain Trouvé, and Gabriel Peyré. Interpolating between optimal transport and mmd using sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2691-2690. PMLR, 2019.
339
340
341
342
[12] Joel Franklin and Jens Lorenz. On the scaling of multidimensional matrices. Linear Algebra and its applications, 114:717-735, 1989.
343
344
[13] Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré. Sample complexity of sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1574-1583 PMLR, 2019.
345
346
347
[14] Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning generative models with sinkhorn divergences. In International Conference on Artificial Intelligence and Statistics, pages 1608- 1617. PMLR, 2018.
348
349
350
[15] Christian Léonard. A survey of the schr\." odinger problem and some of its connections with optimal transport. arXiv preprint arXiv: 1 1308. 0215, 2013.
351
352
[16] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):599-533 2015.
353
354
355
[17] Thanh Tang Nguyen, Sunil Gupta, and Svetha Venkatesh. Distributional reinforcement learning with maximum mean discrepancy. Association for the Advancement of Artificial Intelligence (AAAI), 2020.
356
357
358
[18] Aaditya Ramdas, Nicolás Garefa Trillos, and Marco Cuturi. On wasserstein two-sample testing and related families of nonparametric tests. Entropy, 19(2):47, 2017.
10

---

380
[19]
Mark Rowland. Mare Bellemare, Will Dabney, Rémi Munos, and Yee Whye Teh. An analysis of categorical distributional reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 29-37. PMLR, 2018.
361
363
[0 Ludger Rüschendorf and Wolfgang Thomsen. Closedness of sum spaces andthe generalized schrödinger problem. Theory of Probability & Its Applicattons, 42(3):483-494, 1998.
364
[2]]
Richard Sinkhorn, Diagonal equivalence to matrices with prescribed row and column sums. The American Mathematical Monthly, 74(4))402-405, 1967.
366
387
[22] Gábor J Székely. E-statistics: The energy of statistical samples. Bowling Green State University, Department of Mathematics and Statistics Technical Report, 3(05):1-18, 2003.
388
369
[23] Eric Wong, Frank Schmidt, and Zico Kolter. Wasserstein adversarial examples via projected sinkhorn iterations. In International Conference Machine Learning, pages 6808 68177.
371
PMLR, 2019.
372
[24] Derek Yang, Li Zhao, Zichuan Lin, Tao Qin, Jiang Bian, and Tie-Yan Liu. Fully parameterized quantile function for distributional reinforcement learning. Advances in neural information processing systems, 32:6193-6202. 2012,
373
375
[25] Shangtong Zhang. Modularized implementation of deep algorithms in pytorch. https //github. Cerithub.com/haaee hhaa///Saaannttggngg/ge/eeee 2018.
378
[26] Fan Zhou, Jianing Wang, and Xingdong Feng, Non-crossing quantile regression for distri- butional reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
378
380
[27] Florian Ziel. The energy distance for ensemble and scenario reduction. arXiv preprint ar0iv:2005. /4670, 2020.
Checklist
382
383
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
385
(b) Did you describe the limitations of your work? [Yes] We provide the discussion about
387
the limitation of our proposal in Section
388
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
389
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
390
391
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Please refer to Appendix B
393
and C
(b) Did you include complete proofs of all theoretical results? [Yes] Please refer to
395
Appendix B
and C
396
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
398
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Our implementation is adapted from Pytorch distributional RL modules 225
400
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
403
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We provide the comparison of
405
computational cost in Figure 12 of Appendix
11

---

407
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
408
(a) If your work uses existing assets, did you cite the creators? [N/A]
409
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
411
412
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
413
414
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
416
5.
If you used crowdsourcing or conducted research with human subjects...
417
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
420
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
422
12


Reviews:
[{"review_id": "VXcvA9QwEf", "reviewer": "Reviewer_4n2i", "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.\n", "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.\n2. Why not using the same Gaussian kernel for MMD and SinkhornDRL to validate their theoretical relations by changing $\\epsilon$?\n3. 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.\n", "limitations": "The authors have addressed the major limitation of this paper with potential future directions.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nThis paper is well-written and easy to follow, and it is interesting to learn the connections between different approaches from a unified framework. \n\nWeakness:\nI have two major concerns about this paper:\n1. The novelty of this paper. The relationship among Wasserstein distance, MMD and Sinkhorn divergence has been studied in existing literatures [1]. \nThe 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.\n\n2. 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.\n\n[1]: Genevay, Aude, Gabriel Peyré, and Marco Cuturi. \"Learning generative models with sinkhorn divergences.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2018.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MGTbDJxHETm", "reviewer": "Reviewer_osMq", "summary": "The paper under review studied the problem of distributional reinforcement learning (DRL).\nInstead of (expected) value function, DRL aim to learn the entire value distribution.\nHence to optimize (solve distributional Bellman equation), \none needs to pick a norm to measure distances between distributions.\nIn this paper, the authors proposed to use Sinkhorn divergence.\nThey proved that distributional Bellman operator under Sinkhorn divergence \ninterpolates between Wasserstein distance and MMD. \nMoreover, they show that distributional Bellman operator is non-expansive \nand approximately performs a regularized moment matching.\nFurthermore, based on Sinkhorn iteration, the authors provided algorithms \nfor DRL with Sinkhorn divergence, and demonstrated its efficiency under Atari games.\n", "questions": "Q1: Does the choice of $\\epsilon$ matter? The authors mentioned multiple times that Sinkhorn allows \na trade-off that simultaneously leverages the geometry of the Wasserstein distance ($\\epsilon \\to 0$) and the\nunbiased gradient estimate property of MMD ($\\epsilon \\to \\infty$). \nHowever, in the sensitivity analysis (sec 5.2), the authors claimed that SinkhornDRL is robust to the choice of $\\epsilon$ along with \nother hyper-parameters.\n\n\n\nQ2: Fig 3 are plots for the game Breakout. Do similar behaviors appear for other Atari games? For example, seaquest.\nAccording to Fig 2, Sinkhorn shows near zero improvement compare to MMD and QRDQN (i.e. three of them behaved similarly).\nHence it seems that Breakout, the game itself is not sensitive to the choice of $\\epsilon$, \nor even the choice of norm (its hard to believe L=2 and L=50 give the same norm Fig 3(c)).\nWhat is the cost function for Breakout? \nmaybe the cost is either close to a uniform or diagonal matrix, which makes hyper-parameters no long matter.\n\n", "limitations": "The authors mentioned that the main limitation of SinkhornDRL is that the superiority over existing state-of-the-art algorithms may\nnot be sufficiently significant. And also authors conjectured that to extend  SinkhornDRL for better performance, implicit generative\nmodels, including parameterizing the cost function in Sinkhorn divergence shall be further incorporated. \nMaybe hyperparameter tuning shall be take into consideration too.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is well written and easy to follow.\nThe idea of using Sinkhorn divergence is natural and interesting.\nThe theoretical results are nicely stated and proved.\nThe non-expansive on Bellman operator (Thm 1) \nand Equivalence to Regularized MMD (Cor 1) have potential applications in the field. \n\n\nWeaknesses:\nThe main concern is the motivation.\n\nIt is unclear why the authors proposed to use Sinkhorn divergence as a norm.\nBecause it interpolates between Wasserstein distance and MMD\nor because it has properties that other existing approaches do not have? \nOr it is just another norm, out preform other algos in some cases.\n\nIn the experiment section, the authors demonstrated that SinkhornDRL\nis \"extremely superior over existing algorithms\" on some games. \nThe question is then what is the characterization of these games?\nand why Sinkhorn is better in these cases? \n\nMore interestingly, could the authors say a bit more on \nwhen Wasserstein is better, and when MMD is better \n(probably depends on the sparsity of the OT plan).\nThis may lead to some guideline on choice of $\\epsilon$ per game.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FoI9EXKiswN", "reviewer": "Reviewer_pZHW", "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. \n\nFollowing the discussion and authors' response I have increased my grade from 5 to 6, supporting the acceptance of the paper. ", "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. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\n**Weakness**\nThe 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].  \nIf 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? \n\nThe 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. \n\nRe 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. \n\n**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. \n\nAlgorithm 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. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "E7H89KlV5mu", "reviewer": "Reviewer_ptV9", "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.\n\n---\n\nI 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:\n - 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.\n - 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:\n    - Assuming the existence of densities.\n    - 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)).\n    - 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.\n\nMy 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.", "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).\n\nPart (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.\n\nLooking at the proof, I think there are a couple of steps which aren't valid/require more care:\n - 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.\n - 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. \n\nIn summary, I think part (3) of Theorem 1 is not correct as stated.\n\nOther questions/notes:\n\nIt 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?\n\nLine 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?\n\nIn 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?\n\nThere are some typos to address throughout the paper. Some examples are:\nLine 8: \"Bellmen\" -> \"Bellman\"\nLine 19: Duplicate reference 7 -> I expect one of these is meant to be [6]?\nLine 205: \"Proof of Corollary\" -> \"Proof of Corollary 1\"\nLine 219: \"differential\" -> \"differentiable\"?\n\nMinor technical notes:\nEquation (1): Should be equal in distribution.\nLine 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).", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nStrengths:\n - 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.\n - 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.\n - 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.\n\nWeaknesses:\n - 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.\n - 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.\n - 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject