General Munchausen Reinforcement Learning with Tsallis Kullback-Leibler Divergence
Authors: Lingwei Zhu
Zheng Chen
Matthew Kyle Schlegel
Martha White
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning
entropy regularization
Tsallis KL divergence

Abstract: Many policy optimization approaches in reinforcement learning incorporate a Kullback-Leilbler (KL) divergence to the previous policy, to prevent the policy from changing too quickly. This idea was initially proposed in a seminal paper on Conservative Policy Iteration, with approximations given by algorithms like TRPO and Munchausen Value Iteration (MVI). We continue this line of work by investigating a generalized KL divergence---called the Tsallis KL divergence. Tsallis KL defined by the $q$-logarithm is a strict generalization, as $q = 1$ corresponds to the standard KL divergence; $q > 1$ provides a range of new options. We characterize the types of policies learned under the Tsallis KL, and motivate when $q >1$ could be beneficial.  To obtain a practical algorithm that incorporates Tsallis KL regularization, we extend MVI, which is one of the simplest approaches to incorporate KL regularization. We show that this generalized MVI($q$) obtains significant improvements over the standard MVI($q = 1$) across 35 Atari games.

General Munchausen Reinforcement Learning with Tsallis Kullback-Leibler Divergence
Lingwei Zhu University of Alberta Lingvei4bualberta.cm
Zheng Chen Osaka University chenzōsanken. osaka-u. ac. jp
Matthew Schlegel University of Alberta mkschleg@ualberta.c ca
Martha White
University of Alberta
CIFAR Canada AI Chair, Amii whi whitemQualberta
Abstract
Many policy optimization approaches in reinforcement learning incorporate Kullback-Leilbler (KL) divergence to the previous policy, to prevent the policy from changing too quickly. This idea was initially proposed in seminal paper on Conservative Policy Iteration, with approximations given by algorithms like TRPO and Munchausen Value Iteration (MVI). We continue this line of work by investigating a generalized KI. divergence divergence-called called the Tsallis KI. divergence. strict generalization, as q
Tsallis KL defined by the g-logarithm sponds to the standard KL divergence; > 1 provides range of new options. We characterize the types of policies learned under the Tsallis KL, and motivate when could be beneficial. To obtain a practical algorithm that incorporates Tsallis KL regularization, we extend MVI, which is one of the simplest approaches to incorporate KL regularization. We show that this generalized MVI(g) obtains significant improvements over the standard MVI(g 1) across 35 Atari games.
corre-
Introduction
There is ample theoretical evidence that it is useful incorporate KI. regularization into policy optimization in reinforcement learning. The most basic approach is to regularize towards uniform policy, resulting in entropy regularization. More effective. however, previous policy. By choosing KL regularization between consecutively updated policies, the optimal policy becomes softmax over uniform average of the full history of action value estimates [Vieillard et al., 2020a]. This averaging smooths out noise, allowing for better theoretical results [Azar al., 2012, Kozuno al., 2019, Vieillard al., 2020a, Kozuno et al., 2022].
regularize towards the
Despite these theoretical benefits, there are some issues with using KL regularization in practice. It is well-known that the uniform average is susceptible outliers; this issue is inherent to KL. divergence [Futami et al., 2018]. In practice, heuristics such as assigning vanishing regularization coefficients some estimates have been implemented widely to increase robustness and accelerate learning [Grau-Moya et al., 2019, Haarnoja et al., 2018, Kitamura et al., 2021]. However, theoretical guarantees no longer hold for those heuristics [Vieillard et al., 2020a, Kozuno al., 2022]. natural question is what alternatives we can consider to this KL. divergence regularization, that allows us overcome some of these disadvantages while maintaining the benefits associate with restricting aggressive policy changes and smoothing errors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this work, we explore one possible direction by generalizing to Tsallis KL divergences. Tsallis KL divergences were introduced for physics [Tsallis, 1988, 2009] using a simple idea: replacing the use of the logarithm with the deformed g-logarithm. The implications for policy optimization, however, are that we get quite a different form for the resulting policy. Tsallis entropy with g = has actually already been considered for policy optimization [Chow et al., 2018, Lee et al., 2018], by replacing Shannon entropy with Tsallis entropy to maintain stochasticity in the policy, The resulting policies are called sparsemax policies, because they concentrate the probability on higher-valued actions and truncate the probability to zero for lower-valued actions. Intuitively, this should have the benefit of maintaining stochasticity, but only amongst the most promising actions, unlike the Boltzmann policy which maintains nonzero probability on all actions. Unfortunately, using only Tsallis entropy did not provide significant benefits, and in fact often performed worse than existing methods. We find, however, that using a Tsallis KI. divergence to the previous policy does provide notable gains.
We first show how to incorporate Tsallis KI. regularization into the standard value iteration updates, and prove that we maintain convergence under this generalization from KI. regularization to Tsallis KL regularization. We then characterize the types of policies learned under Tsallis KL, highlighting that there is now a more complex relationship to past action-values than a simple uniform average. We then show how to extend Munchausen Value Iteration (MVI) [Vieillard et al., 2020b], to use Tsallis KL regularization, which we call MVI(g). We use this naming convention to highlight that this is strict generalization of MVI: by setting q = 1, we exactly recover MVI. We then compare MVI(g = 2) with MVI (namely the standard choice where q = 1). and find that we obtain significant performance improvements in Atari.
Remark: There is growing body of literature studying generalizations of KI. divergence in RL [Nachum et al., 2019, Zhang et al., 2020]. Futami et al. [2018] discussed the inherent drawback of KL divergence in generative modeling and proposed to use B- and y-divergence to allow for weighted average of sample contribution. These divergences fall under the category known as the f-divergence [Sason and Verdú, 2016], commonly used in other machine learning domains including generative modeling [Nowozin et al., 2016, Wan et al., 2020, Yu et al., 2020] and imitation learning [Ghasemipour et al., 2019, Ke et al., 2019]. In RL, Wang et al. [2018] discussed using tail adaptive f f-divergence to enforee the mass-covering property. Belousov and Peters [2019] discussed the use of a-divergence. Tsallis KL divergence, however, has not yet been studied in RL.
2 Problem Setting
We focus on discrete-time discounted Markov Decision Processes (MDPs) expressed by the tuple AS,A, d, P, p,r,7 7). where S and A denote state space and finite action space, respectively. Let A (x) denote the set of probability distributions over X. d E (88) denotes the initial state distribution. P : S x AA- - (SS) denotes the transition probability function, and r(s. a) defines the reward associated with that transition. 7 E (0, 1) is the discount factor. A policy π. S + ((A) a mapping from the state space to distributions over actions. We define the action value function following policy т and starting from 8p d(-) with action ag taken as Qx (s. a) E. ?
8, An - =a]. A standard approach to find the optimal value function Q. is value iteration. To define the formulas for
value iteration, it will be convenient to write the action value function as a matrix Q E [ For
notational convenience, we define the inner product for any two functions F1, F2 RR S| over actions as (Fi, E Ig|s
We are interested in the entropy- regularzee MDPs where the recursion is augmented with ((T)):
Tk+1 = arg max_ (T,, Qx) - -(((T))
Q = r + ,
P (T4+1, Qx) +5((T++1))
This modified recursion is guaranteed to converge if Ω is concave in π. For standard (Shannon) entropy regularization, we use (?(T) = - H. (m) = (TT, In.).. The resulting optimal policy has Tk+1 x exp -Qx). where & indicates proportional to up to a constant not depending on actions.
More generally, we can consider a broad class of regularizers known as f-divergences [Sason and Verdú, 2016]: ((=)= = (T(lA) == (u. f (=/n)), where / is a convex function. For example, the KL divergence DKr. (1) = (T,, In -ln Inj1) jr) can be recovered by s(() = - In In this work, when we say KI. regularization, we mean the standard choice of setting μ = ku. the estimate from the previous update. Therefore, DKL serves as a penalty to penalize aggressive policy changes. The
2

---

Toolis Entroge -x1 111nn
0.3
0000
0.2
3 22
Figure 1: Ing v, exp, and Tsallis entropy component - In, for -1 to 5. When = 11 they respectively recover their standard counterpart. a is chosen to be Gaussian NV2, 1). As gets larger In, x (and hence Tsallis entropy) becomes more flat and exp, x: steep.
optimal policy in this case takes the form 7441 x my exp (x=).)). By induction, we can show this KL-regularized optimal policy T*++1 is a softmax over uniform average over the history of action
value estimates [Vieillard et al., 2020a]: Th+1 Ty exp QQx) x ... & exp EE 2,). Using KL regularization has been shown to be theoretically superior entropy regularization in terms of error tolerance [Azar et al., 2012, Vieillard et al., 2020a, Kozuno et al., 2022, Chan et al., 2022].
The definitions of H-(-) and D-I(-11) rely on the standard logarithm and both induce softmax policies exponential (inverse function) over (weighted) action-values [Hiriart- Urruty and Lemaréchal, 2004, Nachum and Dai, 2020]. Convergence properties of the resulting regularized algorithms have been well studied [oozuno al., 2019, Geist et al., 2019, Vieillard al., 2020a]. In this paper, we investigate Tsallis entropy and Tsallis KL divergence as the regularizer, which generalize Shannon entropy and KL divergence respectively.
3 Generalizing to Tsallis Regularization
We can easily incorporate other regularizers in to the value iteration recursion, and maintain conver- gence long those regularizers are strongly convex in π. We characterize the types of policies that arise from using this regularizer, and prove the convergence of resulting regularized recursion.
3.1 Tsallis Entropy Regularization
Tsallis entropy was first proposed by Tsallis [1988] and is defined by the g-logarithm. The loggatit and its unique inverse function, the g-exponential, are defined as:
x:1
Ing
exPa x = [1 + - for q E (R(11)
(2)
where F++ m 0}. We define In = In exp1 exp, in the limit 9 1, the formulas in Eq. (2) approach these functions. Tsallis entropy can be defined by (T) ;= T,, In, p E R [Suyari and Tsukada, 2005]. We visualize the g-logarithm, g-exponential and Tsallis entropy for different g in Figure As q gets larger, q-logarithm (and hence Tsallis entropy) becomes more flat and g-exponential more steep'. Note that cxp, is only invertible for 1-9.
Tsallis policies have similar form to softmax, but using the g-exponential instead. Let us provide some intuition for these policies. When p 9 2, S2(m) 2 (Tr, x), the optimization
problem arg max (IT, Q) + S2(T) arg min (22(4))(4))) | Q1, is known to be the Euclidean projection onto the probability simplex. Its solution IQ - =)__ is called the sparsemax [Martins and Astudillo, 2016, Lee et al., 2018] and has sparse support [Duchi et al., 2008, Condat, 2016, Blondel al., 2020]. v
A + S is the unique function satisfying (1, IQ > =1
As our first result, we unify the Tsallis entropy regularized policies for all q E R4, with the q- exponential, and show that and are interchangeable for controlling the truncation.
'The llgaarihh detined here is consistent with the physics literature and different from prior RL works [Lee al., 2020]. where change of variable g* 2 q made. We analyze both cases in Appendix A.

---

Tellis -Sylne
1.0
Daltamann polley g 50
Holtamamm policy
0G
[2.75 1 (3.25.1 1)
Figure 2: (Left) Tsallis KL component - Ing between two Gaussian policies (2.775, 1), T2 = (3.25, 1) for q = to 5. When 9 TKL recovers KL. For > 1. TKL more mode-covering than KI. (Mid) The sparsemax operator acting on Boltzmann policy when q 2. (Right) The sparsemax when q 50. Truncation gets stronger as gets larger. The same effect can be also controlled by r.
Theorem 1. Let (((T) (Tg(T) in Eq. (1). Then the regularized optimal policies can be expressed:
"11000000 x(ass)= Q(s,a) -Wa (((s.)) )
(1 - =exp, ( (Q(s,a) 1/4 (Q(s:)))
(3)
where Vig = Vig + T-q- Additionally, for arbitrary (g,7) 7) pair with >> 1, the same truncation effect (support) can be achieved using (q --).
Proof. See Appendix B for the full proof.
Theorem I characterizes the role played by q: controlling the degree of truncation. We show the truncation effect when q and q = 50 in Figure confirming that Tsallis policies tend to truncate more gets larger. The theorem also highlights that we can set 2 and still get more or less truncation using different r, helping to explain why in our experiments q = 2 is a generally effective choice.
Unfortunately, the threshold 4i, (and (h,)) does not have a closed-form solution for q * 1,2, co. Note that g 1 corresponds to Shannon entropy and co to no regularization. However, we can resort Taylor's expansion to obtain approximate sparsemax policies.
Theorem 2. For + oc, we can obtain approximate threshold é, = th using Taylor's 's expansion, and therefore an approximate policy:
(Q(5,0) - 11g (066))))))) 0y (Q(5.)) EacK(s) Q(a.1
(als) x exP,
[K(s) +1.
((aaa)) > EE=1 Q(aam))
K(s) the set of tighest-valuedd actions, satisfying the relation
where (()) indicates the action with jth largest action value. The sparsemax policy sets the prob- abilities lowest-valued actions zero: ={a[))s) 0, = 1,..,... 1,...,,,44 where Q(s, a())) >
-- ((x..) Q(8,0(=+1)) When g = 2, vi recovers vi.
Proof. See Appendix B for the full proof.
Lee et al. [2020] also used exp, to represent policies but they consider the continuous action setting and do not give any computable threshold. By contrast, Theorem presents an easily computable di for all q & [1,
3.2 Tsallis KL Regularization and Convergence Results
The Tsallis KL divergence is defined as D& (TT μ4) (I,, - Inn 4)) [Furuichi et al., 2004]. It is member of f fddivergence and can be recovered by choosing f(t) Ing As divergence penalty,

---

it is required that > 0 since f(t) should be convex. We further assume that q > 1 to align with standard divergences: i.c. penalize large value of x since for < q the regularization would penalize и instead. In practice, we find that 0 < q < 1 tend to perform poorly. In contrast to KL, Tsallis KL more mass-covering; i.e. its value is proportional to the q-th power of the ratio z. When q is big, large values of I are strongly penalized [Wang et al., 2018]. This behavior of Tsallis KL f divergence can also be found in other well- kolln divergences: the a-divergence [Wang et al., 2018, Belousov and Peters, 2019] coincides with Tsallis KL when = 2: Rényi's 's divergence also penalizes large policy ratio by raising to the power g, but inside the logarithm, which is therefore an additive extension of KL [Li and Turner, 2016]. In the limit of - 1, Tsallis entropy recovers Shannon entropy and the Tsallis KI. divergence recovers the KI. divergence. We plot the Tsallis KI. divergence behavior in Figure 2.
z.
Now let turn formalizing when value iteration under Tsallis regularization converges. The q-logarithm has the following properties: Convexity: Iny is convex for S. 0, concave for > 0. When g O. both Ing exp, become linear. Monotonicity: Ing x monotonically increasing with respect to т. These two properties can be simply verified by checking the first and second order derivative. We prove in Appendix A the following similarity between Shannon entropy (reps. KL) and Tsallis entropy (resp. Tsallis KL). Bounded entropy: we have 0 S H (T) I In [A]; and
Vq, < (T) < In, Al. Generalized KL property: Yq, D (1 2 0. D& (T (4] = 0 if and only if π = J almost everywhere, and D&z ( [1]
whenever x (als) 0 and μ(aass) 0.
However, despite their similarity, crucial difference is that In, is non-extensive, which means it is not additive [Tsallis, 1988]. In fact, In, is only pseudo-additive:
Ing TH Ing In, μr + (1 q) In, Ing n..
(5)
Pseudo-additivity complicates obtaining convergence results for Eq. (1) with q-logarithm regularizers, since the techniques used for Shannon entropy and KL divergence are generally not applicable to their In, counterparts. Moreover, deriving the optimal policy may be nontrivial. Convergence results have only been established for Tsallis entropy [Lee et al., 2018, Chow et al., 2018].
We know that Eq. (1) with ((())) D& (T p.), for any μ., converges for that make D (- (1) strictly convex [Geist et al., 2019]. When 2, it is strongly convex, and so also strictly convex, guaranteeing convergence.
Theorem 3.
The regularized recursion Eq. (1) with (TT) = Dig (T I.) when 2 converges to the unique regularized optimal policy.
Proof. See Appendix C. It simply involves proving that this regularizer is strongly convex.
3.3 TKL. Regularized Policies Do More Than Averaging
We next show that the optimal regularized policy under Tsallis KI. regularization does more than uniform averaging. It can be seen as performing a weighted average where the degree of weighting is controlled by g. Consider the recursion
Th+1 arg max (T,, Qs D2 (T (x))
(6)
(Q r 11, Q+ D&u (*x+)l|T*)).
where we dropped the regularization coefficient for convenience. Theorem 4. The greedy policy Th41 in Equation (6) satisfies
9-1
Th+1 X (exP, ... Qx) .x) = exPa Σ
Qj
+
Σ Qi Qn Q., 4=1<<..
J=2
When q 1, Eq. (6) reduces to KL regularized recursion and hence Eq. (7) reduces to the KL- regularized policy. When 22 Eq. (7) becomes:
exp2 Q1 exx22 Q exx2
Qj
+
Qi
...Q.s
5

---

i.e, Tsallis KL regularized policies aveeaae over the history of value estimates as well as computing the interaction between them Ei Qi Qi.-
Proof. See Appendix D for the full proof. The proof comprises two parts: the first part shows Tk+1 x exp, ................... eeepp....ppp............ exp, Qr. and the second part establishes the more-than-aven averaaigggggingggggg property by two-point equation [Yamano, 2002] and the 2 q duality [Naudts, 2002, Suyari and Tsukada, 2005] to conclude (exp,r exp,,) -- expy (ar + y) (q 1)-
The form of this policy is harder to intuit, but can try to understand each component. The first component actually corresponds to a weighted averaging by the property of the expyi
Q2 - exp, Q1 exP4 11 (1 9)Q1 (1-1)))
QK
exPa
1+ (1
(8)
Eq. (8) is a possible way to expand the summation: the left-hand side of the equation is what one might expect from conventional KL regularization; while the right-hand side shows weighted scheme such that any estimate 2j is weighted by the summation of estimates before 2j times 1 (Note that we can exchange and q, see Appendix A). Weighting down numerator by the sum of components in the demoninator has been analyzed before in the literature of weighted average by robust divergences, e.g., the --divergence [Futami et al., 2018, Table IJ. Therefore, we conjecture this functional form helps weighting down the magnitude of excessively large Qk. which also be controlled by choosing q. In fact, obtaining a weighted average has been an important topic in RL, where many proposed heuristics coincide with weighted averaging [Grau-Moya al., 2019, Haarnoja et al., 2018, Kitamura et al., 2021].
Now let us consider the second term with = 2, therefore the leading (q - 1) vanishes. The action-value cross-product term can be intuitively understood as further increasing the probability for any actions that have had consistently larger values across iterations. This observation agrees with the mode-covering property of Tsallis KI.. However, there no concrete evidence yet how the average inside g-exponential and the cross-product action values may work jointly to benefit the policy, and their benefits may depend on the task and environments, requiring further categorization and discussion. Empirically, we find that the nonlinearity of Tsallis KL policies bring superior performance to the uniform averaging KL policies on the testbed considered.
Practical Algorithm for Tsallis KL Regularization
In this section we provide practical algorithm for implementing Tsallis regularization. We first explain why this is not straightforward to simply implement KL-regularized value iteration, and how Munchausen Value Iteration (MVI) overcomes this issue with a clever implicit regularization trick. We then extend this algorithm to > 1 using a similar approach, though now with some approximation due once again the difficulties of pseudo-additiitty
4.1 Implicit Regularization With MVI
Even for the standard KL, it is difficult to implement KL-regularized value iteration with function approximation. The difficulty arises from the fact that cannot exactly obtain Tk+1 x my cxp (Qx). This policy might not be representable by our function approximator. For q = 1, one needs to store all past Q2 which is computationally infeasible.
An alternative direction has been to construct a different value function iteration scheme, which is equivalent to the original KI. regularized value iteration [Azar et al., 2012, Kozuno et al., 2019]. recent method of this family Munchausen VI (MVI) [Vieillard al., 2020b]. MVT implicitly enforces KL regularization using the recursion
T arg max, (T, Qx - In
Q ar - + P (T Qk-TIun In
We see that Eq. (9) is Eq. (1) with ((T)) = -H()) (T) (blue) plus an additional red Munchausen term, with coefficient a. Vieillard et al. [2020b] showed that implicit KL regularization performed

---

Caripoe
Caripole
0.0
20
-05
1.
0-
50
40
80
90 100
40
80
100
Iroration
Iteration
Figure 3: MVI((q) on CartPole-vl for q 2,3, 4, 5, averaged over 50 seeds, with 0.03, a 0.9. (Left) The difference between the proposed action gap Qx - -M and the general Munchausen term Iy *++1 converges
constant. (Right) The residual (Tx+1 T&) becomes larger increases. For q = 2, it remains negligible throughout the learning.
under the hood, even though we still have tractable Th+1 exp (T~
Qk+1 = at In 1 1 yP (m Qk r In Q 1 m++1=
+ (++PP( (T++11 Qs ot in πT) (7
a In
+ Q = r P ( Q+) ar DRz. (=t (1 a (ax-1))
(10)
where := Qx+1 - ar In T is the generalized action value function.
The implementation of this idea uses the fact that aT In Tk+1 = a(Qu - MM) where M,Qu == 2, (exp
Z& (1. exp (=xx)x)) is the Boltzmann softmax operator. In the original work, computing this advantage term was found to be more stable than directly using the log of the policy. In our extension, we use the same form.
4.2 MVI(g) For General q
The MVI(q) algorithm simple extension of MVI: replaces the standard exponential in the definition of the advantage with the g-exponential. We can express this action gap Q2 My.
where Mz
exp,, Qu 14 Qx Qn)). When q 1, it recovers Qx M,Qu. We the Appendix. When = 1, we recover MVL.
summarize this MVI(q) algorithm in Algorithm For q oG, get that MR is max, (& a)-no no regularization-aae and recover advantage learning [Baird and Moore, 1999]. Similar to the original MVI algorithm, MVI(g) enjoys tractable policy expression with mk+1 X exp, (T-))
Unlike MVI, however, MVI(g) no longer exactly implements the implicit regularization shown in Eq. (10). Below, go through similar derivation MVI, show why there is approximation and motivate why the above advantage term is a reasonable approximation. addition to this reasoning, 1 was to inherit the same simple form as MVI as well as because empirically we found it to be effective.
primary motivation for this extension of MVI to
Let us similarly define generalized action value function 2k+1 QK+1 - ar I1 Using the 1
relationship IT Ing In F411
1ng
-Q) In Ing mMIn" get
Qk+1 a7 Tx+1 + 7P (T&+I, Qs ar In a7 In + TS (Tx+1))
1h41 r xP (TTTIIII Qs TS (Tx+1)) +
In 1
P aT Ing Tk+1
(1- 9) Ing Tk+1
Iy
(11)
= 7P (T O' + (1- ( 7P (TT+1; or D&g (Tx+1l1TH)) - or (T mp))
Using M-Q is equivalent to the log- sum-uumexpp operator up constant shift [Azar et al., 2012).
7

---

Amidar
Assauit
Beurniider
2500
Melig)
M-VI
10
Return
.00
Enduro
Hero
MiPaccann
Spucelmaders
4000
20
2000
10
Figure 4: Learning curves of MVI(g) and M-VI on the selected Atari games, averaged over inde- pendent runs, with ribbon denoting the standard error. On some environments MVI(g) significantly improve upon M-VT. Quantitative improvements over M-VT and Tsallis- VI are shown in Figures 5.
where we leveraged the fact that - QT Tk+1, Ing - - at ( and defined the residual 1 mn When q 2, it is expected that the residual term remains negligible, but can become larger as q increases. We visualize the trend of the residual R2( (T (T)+1.TT)&00 for 2, 3, 4, on the CartPole-vi environment [Brockman et al., 2016] in Figure Learning consists of 2.5 10 steps, evaluated every 2500 steps (one iteration), averaged over 50 independent runs. It is visible that the magnitude of residual jumps from q 4 to 5, while 2 remains negligible throughout.
term Rg (TK++1, Tk)) == (1 q) Ing #k-1
A reasonable approximation, therefore, is to use Ing Th+1 and omit this residual term. Even this approximation, however, has an issue. When the actions are in the support, In, is the unique inverse However, for actions outside the support, we cannot get the inverse, because many inputs to exP, can result in zero. We could still use Qx) as sensible choice, and it appropriately does negative values for the Munchausen term for these zero-probability actions. Empirically, however, we found this to be less effective than using the action gap.
function of exp, and Iny Tk+1 yields Q. + 1ig Q+
Q+ Q tig r
Though the action gap is yet another approximation, there are clear similarities between using ti (2s) and the action gap Qx My Qu. The primary difference is in how the values are centered. We can see 1h using a uniform average value of the actions in the support, as characterized in Theorem 2. MM. on the other hand, is weighted average of action-values.
We plot the difference between Qx - ~M and In, Th+1 in Figure 3, again in Cartpole. The difference stabilizes around -0.5 for most of learning-in other words primarily just shifting by constant-but in early learning In, Th+1 is larger, across all g. This difference in magnitude might explain why using the action gap results in more stable learning, though more investigation needed to truly understand the difference. For the purposes of this initial work, we pursue the use of the action gap. both as itself a natural extension of the current implementation of MVI and from our own experiments suggesting improved stability with this form.
Experiments
In this section we investigate the utility of MVI(q) in the Atari 2600 benchmark [Bellemare et al., 2013]. We test whether this result holds in more challenging environments, Specifically, we compare to standard MVI (q 1), which was already shown have competitive performance on Atari [Vieillard et al., 2020b]. We restrict our attention to q = 2, which was generally effective in other settings and also allows us to contrast to previous work [Lee et al., 2020] that only used entropy regularization with KL regularization. For MVI(g = 2), we take the exact same learning setup- hyperparameters and architecture-aa as MVI(g = 1) and simply modify the term added to the VI update, as in Algorithm I.
8

---

() improvement over
MVI(q) improvement over Tsallis-VI
600
1000
Improvement (%)
Suprovenne (%)
400
600
200
200
Mor
Rierri
200000
part
chappe
si
Figure 5: (Left) The percent improvement of MVI(g) with q over standard MVI (where q = 1) on select Atari games. The improvement is computed by subtracting the scores from MVI(q) and MVI and normalizing by the MVI scores. (Right) Improvement over Tsallis- VI on Atari environments, normalized with Tsallis-V VI scores.
For the Atari games we implemented MVI(), Tsallis-VI and M-VI based on the Quantile Regression DQN [Dabney et al., 2018]. We leverage the optimized Stable-Baselines, architecture [Raffin et al., 2021] for best performance and average over 3 independent runs following [Vieillard et al.. 2020b], though run 50 million frames instead of 200 million. From Figure 4 it is visible that MVI(g) stable with no wild variance shown, suggesting 3 seeds might be sufficient. We perform grid searches for the algorithmic hyperparameterss on environments Asterix and Seaquest: the latter environment is regarded as a hard exploration environment. MVI(g) a {0.01, 0.1, 0.5, 0.9, 0.99}; (0.01, 0.1, 1.0, 10, 100). Tsallis VI r {0.01, 1.0, 10, 100). For MVI hyperparameters in [Vieillard et al., 2020b]. Hyperparameters can be seen from Table 2 and full results are provided in Appendix E.
the reported
5.1 Comparing MVI with q = to q 2
We provide the overall performance of MVI versus MVI(g = 2) in Figure 5. Using q = provides a large improvement in about 5 games, about double the performance in the next 5 games, comparable performance in the next 7 games and then slightly worse performance in 3 games (PrivateEye Chopper and Seaquest). Both PrivateEye and Seaquest games, which might explain this discrepancy. The Tsallis policy with on actions, truncating some probabilities zero. In general, with a higher q. the resulting policy is greedier, with & = & corresponding to exactly the greedy policy. It is possible that for these harder exploration games, the higher stochasticity in the softmax policy from MVI whre q 1 promoted more exploration. A natural next step is to consider incorporating more directed exploration approaches, into MVI(g = 2). benefit from the fact that lower-value actions are removed (avoiding taking poor actions) while exploring in a more directed way when needed.
considered harder exploration
2 reduces the support
We examine the learning curves for the games where MVI()) had the most significant improvement, in Figure 4. Particularly notable is how much more quickly MVI(g) learned with = 2, in addition to plateauing a higher point. In Hero, MVI(g) learned a stably across the runs, whereas standard MVI with g clearly has some failures.
These results are quite surprising. The algorithms are otherwise very similar, with the seemingly small change of using Munchausen term (x(8,a) My=2,+ Q2 instead of Q Qx and using the g-logarithm and g-exponential for the entropy regularization and policy parameterization. Previous work using q = 2 to get the sparsemax with entropy regularization generally harmed performance [Lee et al., 2018, 2020]. It seems that to get the benefits of the generalization q 1, the addition of the KL regularization might be key. We validate this in the next section.
-
5.2 The Importance of Including KI. Regularization
In the policy evaluation step of Eq. (11), if we set = 0 then we recover Tsallis VI which uses regularization ((T)) = -S,(z) (T) in Fq. (1). In other words, we recover the algorithm that incorporates entropy regularization using the q-logarithm and the resulting sparsemax policy. Unlike MVL, Tsallis-

---

VI has not been comprehensively evaluated on Atari games, so we include results for the larger benchmark set comprising 35 Atari games. We plot the percentage improvement MVI(g) over Tsallis-VI in Figure 5.
The improvement from including the Munchausen term (a 0) is stark. For than half of the games, MVI(() resulted in more than 100% improvement. For the remaining games it was comparable. For 10 games, it provided more than 400% improvement. Looking more specifically at which games there was notable improvement, it seems that exploration may again have played role. MVI(q) performs much better on Seaquest and PrivateEye. Both MVI(q) and Tsallis- VI have policy parameterizations that truncate action support, setting probabilities to zero for some actions. The KL regularization term, however, likely slows this down. It possible the Tsallis VI is concentrating too quickly, resulting in insufficient exploration.
Conclusion and Discussion
We investigated the use of the more general q- g-logarithm for entropy regularization and KI. regular- ization, instead of the standard logarithm (g = 1), which gave rise to Tsallis entropy and Tsallis KL regularization. We extended several results previously shown for q 1, namely proved (a) the form of the Tsallis policy can be expressed by g-exponential function; (b) Tsallis KL-regularized policies are weighted average of past action-values; (c) the convergence of value iteration for q 2 and (d) a relationship between adding a g-logarithm of policy to the action-value update, to provide implicit Tsallis KL regularization and entropy regularization, generalizing the original Munchausen Value Iteration (MVI). We used these results to propose a generalization to MVI, which we call MVI(g), because for 1 exactly recover MVI. We showed empirically that the generalization to can be beneficial, providing notable improvements in the Atari 2600 benchmark.
References
M. G. Azar, V. Gómez, and H. J. Kappen. Dynamic policy programming. Journal of Machine Learning Research, 13(1):3207-3245, 2012.
L. Baird and A. Moore. Gradient descent for general reinforcement learning In Proceedings of the 1998 Conference on Advances in Neural Information Processing Systems 11, page 968-999999 984,,,4, 1999.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47(1):253-279 2013. ISSN 1076-9757.
B. Belousov and J. Peters. Entropic regularization of markov decision processes. Entropy, 21(7), 2019.
M. Blondel, A. F. Martins, and V. Niculae. Learning with fenchel-young losses. Journal of Machine Learning Research, 21(35): 1-69, 2020.
G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym. arXiv preprint 1rXiv:1606.000 (0060000040 2016.
A. Chan, H. Silva, S. Lim, T. Kozuno, A. R. Mahmood, and M. White. Greedification operators for policy optimization: Investigating forward and reverse kl divergences. Journal of Machine Learning Research, 23(253): 2022.
G. Chen, Y. Peng, and M. Zhang. Effective exploration for deep reinforcement learning via boot- strapped q-ensembles under tsallis entropy regularization. urXiv:abw/1809.004003 2018. URL hatgg/ab/1800 weee//88...00 00403..
Y. Chow, O. Nachum, and M. Ghavamzadeh. Path consistency learning in Tsallis entropy regularized MDPs. In International Conference on Machine Learning, pages 979-988, 2018.
L. Condat. Fast projection onto the simplex and the 11 ball. Mathematical Programming, 158: 575-585, 2016.
10

---

T. M. Cover and J. A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscienee USA, 2006.
W. Dabney, M. Rowland, M. Bellemare, and R. Munos. Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 32, pages 2892-2899, 2018.
J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the 11-ball for learning in high dimensions. In Proceedings of the 25th International Conference Machine Learning, page 272-279, 2008.
S. Furuichi, K. Yanagi, and K. Kuriyama. Fundamental properties of tsallis relative entropy. Journal of Mathematical Physics, 45(12):4868 4877,4877440 2004.
Futami, I. Sato, and M. Sugiyama. Variational inference based on robust divergences. In Pro- ceedings of the Twenty-Firy First International Conference Artificial Intelligence and Statistics, volume 84, pages 813-822, 2018.
M. Geist, B. Scherrer, and O. Pietquin. A theory of regularized Markov decission processes. 36th International Conference Machine Learning, volume 97, pages 21 2160-2169, 2019.
S. K. S. Ghasemipour, S. Zemel, and S. Gu. A divergence minimization perspective imitation learning methods. In Conference on Robot Learming, pages 1-19, 2019.
J. Grau-Moya, F. Leibfried, and P. Vrancx. Soft q-learning with mutual-ing inttuaal-iffommtiinn regularization. In International Conference on Learning Representations, pages 1-13, 2019.
Haamojj, A. Zhou, P. Abbeel, and Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In Proceedings of the 35th International Conference on Machine Learning, pages 1861-1870, 2018.
J. Hiriart-UUrutty and C. Lemaréchal. Fundamentals of Convex Analysis. Grundlehren Text Editions. Springer Berlin Heidelberg, 2004.
L. Ke, S. Choudhury, M. Barnes, W. Sun, Lee, and Srinivasa. Imitation learning as f-divergence minimization, 2019. URL https: //axxiv org/oog//////ooooooooo..ooeee /195 12888.
T. Kitamura, L. Zhu, and T. Matsubara. Geometric value iteration: Dynamic error-aware kl regu- larization for reinforcement learning. Proceedings of The 13th Asian Conference on Machine Learning, volume 157, pages 918-931, 2021.
T. Kozuno, E. Uchibe, and K. Doya. Theoretical analysis of efficiency and robustness of softmax and gap-increasing operators in reinforcement learning. Proceedings of the Twenty-Secon International Conference on Artificial Intelligence and Statistics, volume 89, pages 2995-3003, 2019.
T. Kozuno, W. Yang, N. Vieillard, T. Kitamura, Y. Tang, J. Mei, P. Ménard, M. G. Azar, M. Valko, R. Munos, O. Pietquin, M. Geist, and C. Szepesvári. Kl-entropy-rregularzeee model is minimax optimal, 2022. URL //app:://arxti org/ 222// 14211.
with generative
K. Lee, S. Choi, and S. Oh. Sparse markov decision processes with causal sparse tsallis entropy regularization for reinforcement learning. IEEE Robotics and Automation Letters, 3:1466-1473, 2018.
K. Lee, S. Kim, S. Lim, S. Choi, M. Hong. J. I. Kim, Y. Park, and S. Oh. Generalized tsallis entropy reinforcement learning and its application to soft mobile robots. In Robotics: Science and Systems XVI, pages 1-10, 2020.
Y. Li and E. Turner. Rényi divergence variational inference. In Advances in Neural Information Processing Systems, volume 29, 2016.
A. F. T. Martins and R. F. Astudillo. From softmax sparsemax: A sparse model of attention and multi-label classification. In Proceedings of the 33rd International Conference on Machine Learning, page 1614-1623, 2016.

---

O. Nachum and B. Dai. Reinforcement learning via fenchel-rockafellar duality. 2020. URL http://arxiv. wwapxiii.org/aaae arg/abs/20011.1. 01866.
O. Nachum, B. Dai, I. Kostrikov, Y. Chow, L. Li, and Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprini arXiv:1912.02074, 2019.
J. Naudts. Deformed exponentials and logarithms in generalized thermostatistics. Physica A-statistical Mechanics and Its Applications, 316:323-3344 2002.
S. Nowozin, B. Cseke, and R. Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In Advances in Neural Information Processing Systems, volume 29, pages 1-9, 2016.
J. Prehl, C. Essex, and K. H. Hoffmann. Tsallis relative entropy and anomalous diffusion. Entropy. 14(4):701-716, 2012.
A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormann. Stable-baselines:: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22 (268):1-8, 2021.
I. Sason and S. Verdú. f-divergence inequalities. IEEE Transactions on Information Theory, 62: 5973-6006, 2016.
H. Suyari and M. Tsukada. Law of error in tsallis statistics. IEEE Transactions on Information Theory, 51(2):553-777 2005.
H. Suyari, H. Matsuzoe, and A. M. Scarfone. Advantages of q-logarithm representation over q- exponential representation from the sense of scale and shift on nonlinear systems. The European Physical Journal Special Topics, 229(5):773-785 2020.
C. Tsallis. Possible generalization of boltzmann-giin gibbs statistics. Journal of Statistical Physics, 52: 479-487, 1988.
C. Tsallis. Introduction to Nonextensive Statistical Mechanics: Approaching Complex World. Springer New York, 2009. ISBN 9780387853581.
N. Vieillard, T. Kozuno, B. Scherrer, O. Pietquin, Munos, and M. Geist. Leverage the average: an analysis of regularization in rl. In Advances in Neural Information Processing Systems 33, pages 1-12, 2020a.
N. Vieillard, Pietquin, and M. Geist. Munchausen reinforcement learning. In Advances Neural Information Processing Systems 33, pages 2020b.
N. Wan, D. Li, and N. Hovakimyan. f-divergence variational inference. In Advances in Neural Information Processing Systems, volume 33, pages 17370-17379, 2020.
D. Wang, H. Liu, and Q. Liu. Variational inference with tail-adaptive f-divergence. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 5742-5752, 2018.
T. Yamano. Some properties of q-logarithm and q-exponential functions in tsallis statistics. Physica A: Statistical Mechanics and its Applications, 305(3):486 4466, 2002.
L. Yu, Song, Song, and S. Ermon. Training deep energy-based models with f-divergence minimization. In Proceedings the 37th International Conference Machine Learning, ICML'20, pages 1-11, 2020.
R. Zhang, B. Dai, L. Li, and D. Schuurmans. Gendice: Generalized offline estimation of stationary values. In International Conference Learning Representations, 2020.
12

---

A Basic facts of Tsallis KL divergence
We present some basic facts about g-logarithm and Tsallis KL divergence.
begin by introducing the - duality for Tsallis statistics. Recall that the q-logarithm and Tsallis entropy defined in the main paper are:
x
In
1-9 Sy(z) = - -x Img x)
In the RL literature, another definition 9" = 2 is more often used [Lee et al., 2020]. This is called the 2 - duality [Naudts, 2002, Suyari and Tsukada, 2005], which refers to that the Tsallis entropy can be equivalently defined as:
x
I
(x-(x) (x,, Ing x),
9"'
By the duality can show [Suyari and Tsukada, 2005, Eq.(1
x
(1, 1
x9 x9
(,(x)
9" =: Spr (z),
9"
Lee the duality between logarithms Ing" and Ing allows us to define Tsallis entropy by an alternative notation q that eventually reaches to the same functional form.
We now come to examine Tsallis KL divergence (or Tsallis relative entropy) defined in another form: Dis (ax (1) Ing" A [Prehl et al., 2012]. In the main paper we used the definition Diu (T (1) = (T, -ing #) [Furuichi et al., 2004]. We show they are equivalent by the same logic:
14
π = n. Ing
n1 Ing
(12)
P
The equivalence allows work with whichever of ing and Ing- that makes the proof casier to work out the following useful properties of Tsallis KL divergence:
Nonnegativity Diu (T 14) 2 O: since the function .mng π is convex, by Jensen's inequality
(T, Ing
Ing
= 0,
Conditions of Dj., (T (p) 0: directly from the above, in Jensen's inequality the equality holds implies almost everywhere.
only when # = almost everywhere, i.e. Dir. (T (4)
Conditions of D&r (TT (4) = oo: To better align with the standard KI. divergence, let us work with In following [Cover and Thomas, 2006), let define
0 Oln
π Ing 0 = oc. 0 = O, 0 Olg = 0,
We conclude that Dig (m (i) co whenever
and === 0.
Bounded entropy Vg. 0 < (T) & Ing |A]: let μ divergence:
1 [Al by the nonnegativity of Tsallis KL
(IA) π
8-1
Dig ( 11
TT, -.ng (IA] -T) )
T
= -|A
(1, T²)
LA
2 0.
-
Notice that
11.5 1-1
799 1--1--
(n, lngm))) (5)( and 14
9-1 In conclude
1-9
S₂(T) Iny LA|.
13

---

B Proof of Theorem 1 and 2
We structure this section as the following three parts:
1. Tsallis entropy regularized policy has general expression for all q. Moreover, and T are interchangeable for controlling the truncation (Theorem 1).
2. The policies can be expressed by g-exponential (Theorem 1).
3. We present computable approximate threshold ei (Theorem 2).
General expression for Tsallis entropy regularized policy. The original definition of Tsallis entropy is S (T(-|s)) -- (1 E. T² (a] .9" E R, p E R2,. Note that similar to Appendix A, we can choose whichever convenient of and q", since the domain of the entropic index is IR. To obtain the Tsallis entropy-regularize
follow [Chen al., 2018). The derivation begins with assuming an actor-critic framework where the policy network is parametrized by w. It well-known that the parameters should be updated towards the direction specified by the policy gradient theorem:
policies
O ln
8H (T) Dw
Σ>SS 0() dw
(1.
Aw E, Q
dw +
f(w).
(13)
Recall that H. (T) denotes the Shannon entropy and is the coefficient. X(s) are the Lagrange multipliers for the constraint (1, π = 1. In the Tsallis entropy framework, we replace H. (œ) with S (T). We can assume p to ease derivation, which is the case for sparsemax.
We can now explicitly write the optimal condition for the policy network parameters:
In Ow
aSg-(z) (x)
2 (1, π
f(w) = En
Qx
Σ A(s)
Ow
i In
1
a In π Ow
In π Sw
Er
Q
1, 1
(s)
(14)
Dw
9" 1
(
1
In
E.
Q
g'-11
(5)
9pt
dw
where we leveraged 88.- (a))
in the second step and absorbed terms into the expectation in the last step. (s) denotes the adjusted Lagrange multipliers by taking A(s) inside the expectation and modifying it according to the discounted stationary distribution.
9 Bin dw
I--
Now it suffices to verify either Bln
0 or
dr
Qx( 9"'
(alss) - (5)))) =
-1-1
Qx( V (s)
* (a|s)
(q" - 1),
(15)
1-1 1- [ Qnt (6)
/
or (a|s)) =
(1 4),
where changed the entropic index from 9 g. Clearly, the root does not affect truncation. Consider the pair (q" 50, r). then the same truncation effect can be achieved by choosing (9" 2, ). The same goes for q. Therefore,
conclude that and are interchangeable for
the truncation, and we should stick the analytic choice 9º 2(q 0).
Tsallis policies can be expressed by g-exponential. Given Eq. (15), by adding and subtracting 1, we have:
1 (1 -9) (Q=((,0) (++1-1)0a((50))) 4/
(Qr(),))
1
)1
(ox(1,0)
11 (ox(s,))
))
x" (als)
cxx,,
5
7
14

---

where we defined b/4 ,/ 1_ Note that this expression is general for all q. but whether ' has closed-form expression depends on the solvability of d.g
I-q"
Let us consider the extreme case q = co. is clear that limg 1-g -> Therefore, for any x >
we must have ,ー - 1; i.e., there is only one action with probability 1, with all others being O. This conclusion agrees with the fact that (T) 0 as q - oc: hence the regularized policy degenerates to arg max.
A computable Normalization Function. The constraint EaeK(e) x (als) is exploited to obtain the threshold & for the sparsemax [Lee et al., 2018, Chow et al., 2018J. Unfortunately, this is only possible when the root vanishes, since otherwise the constraint yields a summation of radicals. Nonetheless, we can resort to first-order Taylor's expansion for deriving approximate
policy. Following [Chen et al., 2018], 8], let us expand Eq. (15) by the first order Taylor's expansion
(=.a.)) 2hg (-((..) ) (1 - 1) f(x) = x 1-v
f(z) (x) 2), where we
1, x
['(x) = - that the unnormalized approximate policy has # **(ass) = f(z) + f') 2)
=1+ 1-9 ( (x((s,)) - ( (ox():)) (1- - T
(16)
T
Therefore it is clear as q - 00, (a(s)) + 1. This concords well with the limit case where x (a)s) degenerates to arg max. With Eq. (16), constraint Eo)K(s) x² (als) 1:
solve for the approximate normalization by the
@n(ss,)
(gale.))
(Q((..))) (1-1) -1)
1 1= Σ
1 + 1-
1/g
T
oEK(s)
= [K(ss]]
- - -
[K(}]+ + Σ
@x(8,
V (2x(,,))
aEK(s)
EeEK(s) (.().)
+ vig (n(s,))
1
[K(s]
EocK( Oaise) [K(a]]
In order for an action to be in K(s), it has to satisfy Qx(er) Therefore, the condition of ((s) satisfies:
1-9
1 + (x a()
2x +1
1 (1-111))
Therefore, we see the approximate threshold vh Vo + When y = 0 or q² 2, Sr recovers e and hence 5* recovers the exact sparsemax policy.
C Proof of convergence of Q(T))) = D (T II-) when q 2
Let us work with Iy from Appendix and define 1|-1p as the 1p-norm. The convergence proof for ((T) = Dia (T when = comes from that 2(T)) is strongly convex in m:
n, (5)
2
1(x) D (Tl1-)
Tr, Inz
1.
(17)
2
Similarly, the negative Tsallis sparse entropy - -2(T)) r) is also strongly convex. Then the propositions of [Geist et al., 2019] can be applied, which we restate in the following:
Lemma ([Geist et al., 2019]). Define regularized value functions as:
Q F PVV,r
Va. = (=.2)) 1(xx).
(m)) strongly convex, les (Q) max, (T,, Q) - 2((z)) denote the Legendre- Fenchel transform
of (TT)) then
15

---

Algorithm 1: MVI(g)
Input: number of iterations 7, entropy coefficient TKL. coefficient
Initialize Qo To arbitrarily
Let {|AA) (1, 2.... [A}
for = 1,2.....7 do
# Policy Improvement
for (s,a) a) E (S,A) do
Sort Qu(s, 2... Qu(s))(AA))
Find K(b) - max {iE {|il} 1 ( Ej=1
Pe(s,am) + (1)-))))
Dock(e) Delmms
Compute 1ig (n(s.))
K(a)]
# Normalize when 972 2
(als( exp, end for # Policy Evaluation for E AS do Qx+1(8,
Qu(ama) v4 (
r(s, a) ao (Qu(s, Mg.(u(()) +7 EEEE m--1(0)6)) (Q(('.b) - In, 1b)1()))))
end for end for
VΩ* Lipschitz and the unique maximizer of arg max, (T,, Q) - M(x).
Ta st is a conotrractoonn in the supremum norm, i.e. \T - TT 5 7 |V - V/2 Further, it has unique fixed point Va,0.
The policy T. = arg max (T,, Q-,a) - (2(T)) is the unique optimal regularized policy.
Note that in the main paper we dropped the subscript S for both the regularized optimal policy and action value function to lighten notations. It is now clear that Eq. (6) indeed converges for entropic indices that make Dz. ( strongly convex. But we mostly consider the case 2.
D Derivation of the Tsallis KL Policy
This section contains the proof for the Tsallis KLLrregularized policy (7). Section D.1 shows that Tsallis KL policy can also be expressed by a series of multiplications of exp, (Q); while Section D.2 shows its more-than-averaging property.
D.1 Tsallis KL Policies are Similar to KL
We extend the proof and use the same notations from [Lee et al., 2020, Appendix D] to derive the Tsallis regularized policy. Again us work with Iny- from Appendix Define state visitation as (s) E, Σ 1 (s; s)] and state-action visitaion p=(s,a) = E, IE 1 (s; = 8, a)). The core of the proof resides establishing the one-to-one correspondence between the policy and the induced state-action visitation Px. For example, Tsallis entropy is written
(=(s,
Sg-(T) = S.r (px) =
Epr(s, a) Ing En (x
8,a
This unique correspondence allows us to replace the optimization variable from a to pr. Indeed, one can always restore the policy by (als)) = (a(s.a)
Let write Tsallis KI. divergence as D ( Iu)
D& (pl)))
E.o p(s, ln ((s0)) Le p(a,a)) by replacing the policies with their state-action visita-
p(s.a) Enr u(s,a')
16

---

tion One can then convert the Tsallis MDP problem into the following problem:
Epss, a) Σ r(ss.a)(ss\sss)) DKi (pl
max
5,
subject to Vs, p(8, 00
(18)
-(s.a))=((s)) + Σ P(s)s'.a''pps''d
s',0!
where d((s) the initial state distribution. Eq. (18) known as the Bellman Flow Constraints [Lee et al., 2020, Prop. 5] and is concave in p since the first term is linear and the second term is concave in
p. Then the primal and dual solutions satisfy KKT conditions sufficiently and necessarily. Following [Lee et al., 2020, Appendix D.2], we define the Lagrangian objective
: Σ p(s, a)
Σ r(s. (r(s,a)P(s(ss,d) (e + Σ ((s,a)
8,a
Σ ((s)
d(s)+
P(sldd.dd)p -d)
El(s,a)
e'ia'
where X(s, a) and ((s) are dual variables for nonnegativity and Bellman flow constraints. The KKT conditions are:
Vs,a a, p=(s,a) 20, 0,
d(s) + Σ P(sls [p((s,)) = 0,
8/
X(ss,a) s0, (s,,))) 0,
aD (o lv) ap(s,a)
0 Σ (r +7 3
aDg. (0" (v) In v(8, a) ('(
() a) Ew,
(0((s,)) a) En v(s 9'
where
Op(s,a)
((s,a) Ea (',aa")))
+Σ
('(3,a)
(Enr v(s m(s,a)
(s,
The dual variable 5" (s) can be shown equal to the optimal state value function V*(s) following [Lee et al., 2020], and X (s, = 0 whenever p² (a a) O.
(a" 1) lng I + 1, we can show that aDg (p) ap(s,a)
By noticing that ----1
E. u(s,a') -q" Iy v(s.) Ea' x² (s,a")
E. ( d'(9,a)
) d' )d (Inr((aa)) u(s.a)
Substituting (*(s)
(s),,, (als) En' (x,a) 1¹, (als) "arvv((a.a) into the above KKT condition and lever-
p (((s.a)
(*(o))
age the equality Q" = a) + Eerp (7'5 (7)5" we have:
Q'(s,a) - ('() - q" ly T(lss)
((als)) (u(as))
1+ Σ ((ass)
=0
u(als)
(s,
(*(s) +1 Eve (als)
p(als)
(als) u(als) exp,
9"
9"
By comparing it to the maximum Tsallis entropy policy [Lee al., 2020, Eq.)] we see the only
difference lies in the baseline term (((as) m(a)s)-(4'-) which is expected since we are exploiting Tsallis KL regularization. Let us define the normalization function as
zb (2((.)) 9" = (*(s) +1 En Taas))
(als) [(ass)
9"
17

---

then we can write the policy as
(2 v (216)))
- (als) (lals) exp,-
In a way similar to KL regularized policies, at + 1-th update, take x² = 7k-1, = d and Q" Q write 1 1 Wa 2x since the normalization function does not depend actions. We ignored the scaling constant q² and regularization coefficient. Hence one can now expand Tsallis KL policies as:
Tk+1 Th expy (Qk) Tk-1 expy- exp-") (Qx) ... expy Q1. expy Qs+
which proved the first part of Eq. (7).
D.2 Tsallis KL Policies Do More than Average
We show the second part of Eq. (7), which stated that the Tsallis KI. policies do than average. This follows from the following lemma:
Lemma (Eq. (25) of [Yamano, 2002]).
1-q
(exp, D1P. exp, xn) 1-9 =exp
I
q)
Zi.
Dig
(19)
i=
However, the mismatch between the base q and the exponent 1 is inconvenient. We exploit the q 2 g" duality to show this property holds for q" as well:
(exp,- x expy- 2) 9- [1+ (q' - 1)x]+ [1 + (a" 1)y]
= [1 (q" - 1)x + (4' 1)y (q" 1)?
exp,,(x y) (4* 1
Now since we proved the two-point property for q" by the same induction steps in [Yamano, 2002, Eq. (25)] we conclude proof. The weighted average part Eq. (8) comes immediately from [Suyari et al., 2020, (1.()
E Implementation Details
We list the hyperparameters for Gym environments in Table 1. The epsilon threshold is fixed at 0.01 from the beginning of learning. FCn refers the fully connected layer with activation units.
The Q-network uses convolutional layers. The epsilon greedy threshold initialized 1.0 and gradually decays to 0.01 the end of first 10% of learning. We run the algorithms with the swept hyperparameters for full 5 x 10 steps on the selected two Atari environments to pick the best hyperparameters.
We show Figure the performance of MVI(q) on Cartpole-vi and Acrobot-vl. and the full learning curves of MVI(g) on the Atari games in Figure 7. Figures and 9 show the full learning curves of Tsallis- VI.
18

---

CartPole
Acrobot-v1
500
MVi(g)
M-VI Sy(m)
Average Return
250
Asarage
-10
-30
2
3.0
10.2
Iteration
1e5
Figure 6: (Left) MVI(() and MVI with logarithm In IT simply replaced to by Caripole-vl, when q 2. The results are averaged over 50 independent runs. The flat learning curve is due to the pseudo-additivitt. (Right) MVI(q) on Acrobot-vl with different choices. Each is independently fine-tuned. The black bar stands for 95% confidence interval, averaged over 50 independent runs.
MVlgg)
M-VI
Beanniide
2000
250038
200033
2000
0000
10503
1003
100030
7003
2000
50000
3000
ChopperCommand
Enduro
0002
300
6002
4002
3200
3000
1000
100
KanghuPaeter
Average Retum
25000
19000
20000
-303
1000
20000
10000
-1000
-1203
Powg
Prluste"ive
Riverra
2000
0000
1900
700
4000
50000
14000
11500
Spacelnuaders
20000
29000
UplDDwws
17000
13500
Zacxzn
7500
30000
5000
5000
2550
Figure 7: Learning curves of MVI(g) and M-VI on the selected Atari games.
19

---

MV
Tsallis-VI
Allen
Amiddar
2250
Asternlds
10003
Aosoult
0002
1850
0003
6432
1450
4002
1050
3392
1002
103
650
250
250000
Astertx
4.0
Atfenti
1000
Bankiteist
17900
SeomAider
200000
600
10000
150000
600
10000
100000
410
50000
0.0
Average Return
2300
Beraark
100
Bosing
Breakout
30000
Conti pedde
1002
1200
60
420
500
300
7000
5200
20
220
2000
120
ChosperConmand
Encuro
Prostotte
1400
2300
3003
4030
5900
#800
50000
#0000
3900
1900
1200
30000
Hero
esbond
10003
Krull
20000
64000
16000
11200
10000
4600
8400
5000
3200
5000
4000
2500
2000
barstoo
horatinn
Staration
Figure 8: Learning curves of MVI(g) and Tsallis- VI on the selected Atari games.
MVlllg
TullisVV
Kuster
MsFacman
Piitall
PrivacoEye
40000
32000
1000
-30
200
1000
24000
3600
400
2400
5000
1200
-000
1200
Pang
Riverridd
Roadit.md unnerr
Robotank
20000
20003
5500
24000
-32
4200
12000
-20
Seuqquast
Spacetiiaders
StarGunner
Tstankham
5000
17900
140300
250
6400
14000
112000
190
10908
04000
130
3200
T002
20
1600
10
-50
Itanaton
UpMioow
barution
30000
24000
16000
8930
Figure 9: (cont'd) d) MVI(g) and Tsallis- VI on the selected Atari games.
20

---

Table I: Parameters used for Gym.
Network Parameter
Value
Algorithm Parameter
Value
T (total steps)
5 x 10"
(discount rate)
0.99
C (interaction period)
6 (epsilon greedy threshold)
0.01
[B] (buffer size)
104
(Tsallis entropy coefficient)
0.03
B: (batch size)
128
(advantage coefficient)
0.9
I (update period)
100 (Car.) 2500 (Acro.)
Q-network architecture
FC512 FC512
activation units
ReLU
optimizer
Adam
optimizer learning rate
10-3
Table 2: Parameters used for Atari games.
Network Parameter
Value
Algorithmic Parameter
(total steps)
x 107
7 (discount rate)
0.99
C (interaction period)
"WIIG) (VI(() entropy coefficient)
[B (buffer size)
x
ayrr()) (MVI(g) advantage coefficient)
0.9
B, (batch size)
32
Premllix (Tsallis- VI entropy coef.)
10
(update period)
8000
dy.vI (M-VI advantage coefficient)
activation units optimizer
ReLU
Ty-V1 (M-VI entropy coefficient)
0.03
Adam
(epsilon greedy threshold)
1.0 - 0.01 10%
optimizer learning rate
Q-network architecture
Conva 32 Convi, 64 -o FC512 FC
21


Reviews:
[{"review_id": "cdD1fgb7GK", "reviewer": "Reviewer_FCv3", "summary": "Preface: this paper was assigned to me as an emergency review paper, so I had less time to do an in-depth review.\n\nThe paper tried to extend Munchausen Reinforcement learning by replacing the commonly used KL divergence with a more generalised form, i.e., Tsallis KL, and empirically demonstrated its benefits under various simulation experiments. The authors conduct theoretical proves to motivate their intuitive extension. Results showed that adding the Tsallis KL can bring impressive improvements over the simplest M-RL algorithm on game simulations. \n\n=======post-rebuttal=========\n\nBased on the clarifications and new experimental results, I raised my score to 6.", "questions": "Will the choice of q affect the performance significantly? Is it possible that some q choices are more suitable for some particular environments? If so, can you provide an empirical study of how to choose q adapting to the characteristic of task or environment?", "limitations": "None", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is generally well-motivated and well-written at the beginning, with a clear introduction to new concepts such as the Tsallis KL Divergence and its intuitive effect visualisation as in Figure 2. It extended the standard KL-based MVI to a more generalised form MVI(q), supported by theoretical proof of the feasibility of using Tsallis KL instead of KL. Further discussion had been made to explore how Tsallis KL reweights the current policy, in the analogy of other well-recognised algorithms. ", "weaknesses": "1.Contribution. The main contribution of this paper is the extension of Tsallis KL for M-RL and provided necessary math evidence of why can, which I sincerely appreciate. However, the authors fail to address why reweighting the policy distribution by the Tsallis q matters under the hood. From a critical point of view, this work extends an established work 3 years ago by replacing the policy regularisation function to a more variable form where a new hyper-parameter is introduced. Although the paper is self-contained, the contribution to RL community seems to be minor. \n\n2.Potentially misleading and inadequate experiment result. The experiments only showed MVI(q) (i.e., the proposed method) with MVI and Tsallis-VI. The authors would be appreciated if they are able to include more baselines, especially those which considers policy regularisation, such as SAC, TRPO, etc. Moreover, the experiments were not sufficiently standardized. The authors may consider compare their methods with commonly acceptable benchmarks, such as Atari-57, or Mojuco. I also have some concern about Figure 5. The performance is obtained by computing “Improvement over Tsallis-VI on Atari environments, normalized with Tsallis-VI scores”, which, in an extreme case, look exaggerated when the Tsallis-VI scores are small enough. An easy fix is to compare MVI(q) to existing benchmark.\n \n3.Lack of deeper explanation of experiments. It is yet clear to me how MVI(q) boosts performance. Figure 3 somehow tried to discuss it but still insufficient. The authors brought up many guesses in the paper, such as line 179 and line 272. However, they did not dig into any of those. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate you getting in an emergency review, and understand you did not have as much time. Your comments are nonetheless appreciated. \n\nWe would like to address the overall goal and contribution of the paper. It is not yet certain if Tsallis KL regularization will prove to be an effective choice in RL, nor when it might be preferable to the standard KL regularization developed for max-ent RL. However, we cannot even begin to answer the utility of this regularization until we develop approaches to use Tsallis KL. The purpose of this paper is to provide such a strategy and to begin the investigation into its properties, knowing that it will take several papers to properly investigate this line of work. The original max-ent paper also did not fully answer the utility of entropy regularization; rather, this direction has become an important line of inquiry and we are starting to better understand when it is and is not useful. \n\nThis paper 1) introduces Tsallis KL regularization to RL, a general class of regularizers that also includes regularizers like the alpha-divergence (see  e.g. Appendix A of [Li and Turner, 2016] or  [Wang et al., 2018, Belousov and Peters, 2019], mentioned in the  footnote on page 4.)  2) highlights theoretical properties of this regularizer including the form of the resulting policy, 3) provides some motivation for why this regularizer might be useful, 4) provides a practical, approximate implementation of the idea (MVI(q)) and 5) provides empirical evidence for the potential utility of generalizing q > 1. We are not setting out to get state-of-the-art, or show impressive performance on challenging benchmarks. We want to understand this regularizer. In that sense, we respectfully disagree that we needed to do benchmarks like Mujoco and compare to a different class of methods, like actor-critic methods (e.g, SAC). More on this below, explaining why we provide a normalized score to Tsallis-VI.\n\n\nExtending MVI to MVI(q) is by no means trivial. In fact, due to the properties of the Tsallis KL, it is downright difficult. We had to make approximations that took time to develop. Our extension does become the original MVI when $q=1$ (as we did intentionally), but MVI(q) for $q > 1$ is a totally new algorithm. Arguably, others might actually come up with better ways to approximate Tsallis KL regularization, because, as we discuss in the work, we had to make several approximation steps. We believe these to be reasonable, with some conceptual and empirical motivation, but they are approximations.\n\n\nWe compare to Tsallis-VI because we are asking: given the same system/architecture, what is the impact of adding this new Tsallis KL regularization? As mentioned above, we are not trying to outperform SAC or be state-of-the-art. In that sense, the performance is not exaggerated, because we are not making a bold claim that it provides this level of improvement over all approaches. We are simply asking how much improvement is obtained when incorporating Tsallis KL instead of just Tsallis entropy regularization; the answer is that it can give significant improvement, for this agent.\n\n\nFinally, for your question about the choice of $q$, it can affect performance significantly. For many settings, $q = 1$ and $q = 2$ perform reasonably well, where $q = 1$ corresponds to the standard Shannon entropy/KL divergence and $q = 2$ is what was previously used for Tsallis entropy to get the sparsemax. One conclusion from this work is that shifting from $q = 1$ to $q = 2$ can often provide performance improvements, without even considering the other possible values of q. In other words, a reasonable choice for this generalized MVI is to use $q = 2$. However, we did find other values of q could also be effective, see Figure 1 in the uploaded PDF, on Acrobot-v1, with all $q$ independently fine-tuned. Looking at Eq. (3), different q not only control truncation but also the root, hence the smoothing effect. We do not yet know why certain $q$ might be better than others, and how it relates to properties of the environment; this is absolutely one of the important next steps for this work. "}, {"review_id": "Vb76H1HQkx", "reviewer": "Reviewer_QmDX", "summary": "The paper introduces the idea of Tsallis KL divergence for regularizing RL algorithms. They first introduce the Tsallis entropy based regularization formally whilst intuiting the how the q exponential and q logarithm, as defined by Tsallis 1998, have a truncation effect on the divergence. They also formalise this idea of truncation in Theorem 1. They also provide a provably tractable approximation of the *threshold function*. The authors then go on to very interestingly analyze Tsallis KL regularized policy and assert that \"they average over history of value estimates\". They finally introduce an algorithm similar to Munchausen Value Iteration (Vieillard et al., 2020b) which uses the Tsallis KL regularization instead of vanilla KL. Their empirical results show significant gains in a lot of environments. ", "questions": "Please see the weaknesses section.", "limitations": "I do not see any major limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is largely well written. The manner in which the authors build on previous work in addition to explaining various concepts so well, section after section, is impressive. I liked how their theories and their empirical applications associated with Tsallis KL are explained via illustrations (figures 1,2,3). The empirical results suggest a strong improvement over MVI with numerous Atari environments. Figure 5 (left) shows that MVI(q) has significant improvements over MVI in various environments.", "weaknesses": "I see no major weaknesses. I have a couple of comments:\n1. For section 3.3: is this average of histories a feature of Tsallis KL or is it to be expected of other KL regularization as well? Please let me know if this is mentioned somewhere (maybe line 183-184?). I would be interested in knowing how come this is unique for Tsallis KL case.\n2. Section 4.2: you empirically choose to \"omit the residual term\" and judging from Section 5 this works well in practice. Despite this I would be interested in seeing the return on the cartpole environment as iterations increase. How is the the residual calculated or estimated for Figure 3? Please feel free to point me to the appendix or elsewhere in case I might have missed this.\n\nMinor issues and fixes:\n1. Line 77-78: citep for Sason and Verdu [2016]\n2. Line 102: the use of the constant $p$ is not defined or explained while being introduced\n3. How many seeds are the results of Figures 4 and 5 averaged over?\n4. I would expect some discussion of the computational overhead especially in terms of GPU compute time MVI(q) adds to the algorithm.\n5. For the sake of completeness, it would be beneficial to report all the hyper-params used by you even if you are porting them from past work. Additionally a detailed algorithm would also be a helpful addition in the Appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Averaging**: Averaging is a feature of other KL regularization as well. The primary difference is the form of averaging. KL regularization induces a uniform average of the history, as can be seen from line 84. On the other hand, Tsallis KL inherits this uniform average plus an additional cross product term between action values, which boost the probability of actions that have had consistently large values across iterations.\n\n\n**Residual**:  The residual is given by line 230. We apologize for not including the details for computing the residual. To compute it, we store a copy of the target network for $Q_{k-1}$. Policies $\\pi_{k+1}$ and $\\pi_k$ are then respectively computed as shown in Algorithm 1. To prevent divide by zero issue, we clip the policy to the range $[0.01, 0.99]$. \nFor the return on CartPole-v1, please refer to Figure 2 in the attached PDF. M-VI $S_2(\\pi)$ denotes simply replacing the standard logarithm in MVI by the $q$-log, which performed poorly due to the pseudo-additivity of the $q$-log. We will include the residual computation procedure and Figure 2 to the final version of the paper. \n\n\nTo answer the questions listed under minor issues and fixes:\n - Atari results were averaged 3 seeds, and the error bars denote 95% confidence intervals. We apologize that we did not make this information clear, and will include it in the final version of the paper. \n - Computational overhead of MVI(q) is approximately equal to MVI, with only an additional sorting for a list that is the length of  the number of actions, which is small for the environments we considered (please refer to the code or Algorithm 1 in page 16). \n - A detailed algorithm for implementing MVI(q) is provided in page 16 of the appendix.\n"}, {"review_id": "fJk4J5FBdR", "reviewer": "Reviewer_6PUw", "summary": "This paper introduces a principle way of generalizing KL-divergence regularized RL into Tsallis KL regularized RL. There have been studies that replaced Shannon entropy with Tsallis entropy to obtain sparsemax policies, but they had limited success. On the other hand, this paper extends Munchausen value iteration to get MVI(q). The extension is not straightforward due to the pseudo-additivity of $\\ln_q$, but the paper manages to do it with approximation, and empirically show that the apprixmation error remains negligible for small $q$. In the experiments, the paper achieves large performance gain across 35 Atari games, where the authors conjecture that the improvement is due to the change in how MVI(q) do the exploration.", "questions": "- The paper only explains in a way that MVI(q) does less exploration compared to MVI, and it better explores compared to Tsallis-VI. What happens if we control the regularization coefficient to negate thses effects (we can try adding shannon entropy regularization on top of Tsallis-VI if it concentrate to quickly)? If these effects are not able to be negated, in what aspects MVI(q) expores/exploits better than the other algorithms?\n- How sensitive is MVI(q) to the regularization coefficient $\\alpha$ compared to existing algorithms?", "limitations": "The authors have not addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear theoretical foundations for establishing the MVI(q) algorithm\n- The paper is written clearly and easy to follow\n- Proposed algorithm shows notable performance improvement over existing baselines", "weaknesses": "- The main characteristics/advantages of the proposed algorithm is less explained. While the authors assumed that the Tsallis policy can be better in exploitation allowing the policy to exploit high probability actions, It is also possible to control the regularization coefficient (i.e. temperature) to get similar effect, and it is hard to know the difference between these two options from the paper. The paper overall explains very well about the derivation of the algorithm, but it is hard to understand how it works and in what aspects it is better. The paper may benefit from including case scenarios on toy problems when MVI(q) works better than other algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Entropy**: Tsallis entropy truncates action support but Shannon entropy does not truncate. For softmax policies induced by Shannon entropy or KL divergence to ignore some actions, the temperature would have to be set to infinity, which is impossible in practice. On the other hand, the entropic index $q>1$ offers this flexibility. Moreover, for Tsallis-VI, adding Shannon entropy on top of Tsallis entropy would not only result in the loss of average of history but also sparsity, as can be seen from existing paper characterizing necessary conditions on the action sparsity, e.g., Theorem 2 of *A Regularized Approach to Sparse Optimal Policy in Reinforcement Learning* [Li et al., 2019]. In short, MVI(q) is capable of exploiting truncation of action support (controlled by $q$, not available to MVI ($q=1$)), as well as averaging the history of action values (controlled by $\\alpha$, not available to Tsallis-VI).\n \n**Sensitivity**: We believe MVI(q) is similar in terms of sensitivity to $\\alpha$. In Appendix Table 2 we provided hyperparameters of MVI(q) and MVI, which were respectively fine-tuned. They shared the same $\\alpha=0.9$.\n \nAs for the comment about not including limitations of our work. We do try to mention limitations throughout the work. In Section 3.3, we acknowledge that we as yet do not have a strong theoretical motivation for the policy form under Tsallis KL, and instead rely primarily on experiments to motivate it. The limitations of our approximation to obtain Tsallis KL regularization are discussed in line 230-239. However, it could be useful for the reader to have a paragraph dedicated to summarizing the limitations of the work, at the end of the paper. With the additional space for the final paper, we can add such a paragraph to the conclusion.\n\n"}, {"review_id": "8VyrMmyMGv", "reviewer": "Reviewer_3pbN", "summary": "This paper studies the Tsallis regularized MDPs, and proposes a practical algorithm for Tsallis KL divergence based on Munchausen RL. The experiments show that the resulting algorithm MVI($q$) performs notably better than its counterpart MVI.", "questions": "1. Theorem 4 seems to suggest that the Tsallis KL regularized policy focuses more on the Q values at early iterations based on the second term in Eq.(7). Is this desirable?\n2. Why would MVI($q$) provide notable gains while Tsallis value iteration provides no benefits?", "limitations": "The paper only considers $q>1$ for Tsallis regularization, but does not explore the case of $q<1$", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written with sufficient introduction of background\n2. Properties of Tsallis policies are sufficiently studied in the paper.", "weaknesses": "1. $\\exp_q Q_2$ in Eq.(8) should be removed. In fact, since the permutation is changeable, no weighted average is performed in Eq.(8).\n2. There is no clear theoretical justification nor intuition for why Tsallis regularization is beneficial for regularized value iteration", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Addressing the reviewer’s comments on weakness:\n\n1. We thank the reviewer for pointing out the typo $\\exp_q Q_2$ in Eq. (8). It should be corrected as $\\exp_q (\\frac{Q_2}{1 + (1-q)Q_1})$. As the reviewer pointed out, permutation is changeable so there exists many way to expand the term $\\exp_q (\\sum_{i=1}^{k} Q_i)$, and our Eq. (8) serves mainly illustrating the point that TKL policy differs from  the uniform average of KL. We can also see the difference between TKL and KL policies by inspecting the second term in Eq. (7):  this action-value cross-product term further increases the probability for any actions that have had consistently larger values across iterations. This observation agrees with the mode-covering property of Tsallis KL.\n\n\n\n\n2. It is true that we don’t have a theoretical justification for the benefits of Tsallis KL, but we would like to point out that this was the case for Shannon entropy and Tsallis entropy methods as well where only empirical evidence was provided. Our results do provide intuition and empirical evidence showing when Tsallis KL may be preferable.\n\n\nSpecifically, at Line 84 we explained the superiority of KL regularization in terms of uniform average of history, and in Eq. (7) and (8) we explained how Tsallis KL regularization inherits the uniform average of history plus an additional cross-product term boosting actions that have had values consistently large across iterations. The average is not available to Tsallis regularized value iteration (Tsallis-VI). On the other hand, compared to MVI, Tsallis KL regularization provides an additional degree of freedom in truncating action support and therefore in better exploiting high probability actions, which is not available to Shannon entropy/KL divergence regularized methods like MVI.\n\n\nAnswering the reviewer’s questions:\n\n\n1.  We would like to point out that TKL regularized policy does not focus more on Q values at early iterations. Though policies at iteration $k+1$ can only make use of action values up to $k$, all action values are equally weighted. Instead, as we explained in the above, TKL policy does boost actions with consistently large values across iterations.\n\n\n2. We hypothesize that it is the same reason that the KL divergence is usually better than using Shannon entropy: the KL results in a policy that averages over the history of action values, whereas Shannon entropy uses the most recent action values (see [Vieillard et al., 2020] *Leverage the average: an Analysis of KL Regularization in Reinforcement Learning*). MVI(q) has a parameter $\\alpha$ that weights the KL regularization; for $\\alpha = 0$, no KL regularization is used and we only have entropy regularization. In other words, for $\\alpha = 0$, we do not get averaging over the history of action values. Our results for $q > 1$, therefore, parallel what is often observed for $q = 1$ (namely for KL divergence and Shannon entropy). Tsallis-VI uses Tsallis entropy only and corresponds to alpha=0. MVI(q) with $\\alpha > 0$ averages over history of action value estimates to smooth out errors.\n \nAddressing the reviewer’s concern of not investigating $q<1$:\n\nWe did not investigate $q<0$ since the function $-\\ln_q x$ would be concave and no longer a member of $f$-divergence.\nWe tested some values from $q \\in (0,1)$, however, they all showed bad performance. Since Shannon entropy corresponds to $q=1$ (full support) and sparsemax entropy to $q=2$, no regularization to $q=\\infty$, we have decided to focus on $q>1$.\n"}]

Author rebuttal:
Included figures for rebuttal: 
 - Figure 1: MVI(q) on Acrobot-v1 across different $q$
 - Figure 2: MVI(q) on CartPole-v1

Meta-review: The paper investigates the effect of substituting the KL divergence, which is used as a regularizer, with a generalized KL divergence, called the Tsallis KL divergence. They perform empirical evaluation and present supporting theory.

The direction investigated by the paper is recognized to be interesting by the reviewers but to various extent.
Some limitations of the paper are be centered around limited as well as non-standard empirical evaluation.
Overall, however, the paper opens a new direction for research that is deemed interesting and which can lead to other works building on the present submission.
Decision: Accept (poster)