{'fraction_non_alphanumeric': 0.0409375548662726, 'fraction_numerical': 0.016181892666939778, 'mean_word_length': 4.467125259958407, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Enforcing KL Regularization in General Tsallis Entropy Reinforcement Learning via Advantage Learning

Maximum Tsallis entropy (MTE) framework in reinforcement learning has gained popularity recently by virtue of its flexible modeling choices including the widely used Shannon entropy and sparse entropy. However, non-Shannon entropies suffer from approximation error and subsequent underperformance either due to its sensitivity or the lack of closed-form policy expression. To improve the tradeoff between flexibility and empirical performance, we propose to strengthen their error-robustness by enforcing implicit Kullback-Leibler (KL) regularization in MTE motivated by Munchausen DQN (MDQN). We do so by drawing connection between MDQN and advantage learning, by which MDQN is shown to fail on generalizing to the MTE framework. The proposed method Tsallis Advantage Learning (TAL) is verified on extensive experiments to not only significantly improve upon Tsallis-DQN for various non-closed-form Tsallis entropies, but also exhibits comparable performance to state-of-the-art maximum Shannon entropy algorithms.


INTRODUCTION
The successes of modern reinforcement learning (RL) rely crucially on implementing value-based methods with powerful function approximators [Mnih et al., 2015, Andrychowicz et al., 2020. However, the susceptibility of value-based methods is also magnified: various sources of error can perturb action value estimates such that the non-optimal actions have temporally higher values than the optimal ones, putting unit probability mass on such deceptive actions can greatly slow down learning [Fujimoto et al., 2018, Fu et al., 2019 or even cause divergence [Bertsekas and Tsitsiklis, 1996, Wagner, 2011, Bellemare et al., 2016. Recently there has seen promising progress towards alleviating this problem by leveraging entropy-regularized algorithms [Haarnoja et al., 2018, Ahmed et al., 2019: by introducing entropy the policy becomes stochastic, hence optimal actions with temporarily low values can still be selected and subsequently help correct the value estimate. Besides the well-known Shannon entropy giving rise to Boltzmann softmax policy, the maximum Tsallis entropy (MTE) framework has gained recent popularity in that it offers more flexible modeling choices: by varying its entropic index q, Shannon entropy (q = 1) and Tsallis sparse entropy (q = 2) [Martins and Astudillo, 2016, Lee et al., 2018] can be recovered [Lee et al., 2020]. Other values between 1 < q < 2 and q > 2 can also serve as an interesting substitute to Shannon or sparse entropy for more compact/diverse policies. However, a common problem of those entropies is the lack of robustness against errors: they do not enjoy closed-form policy expression when q = 1, 2, hence empirical underperformance is often incurred by significant greedy step error. The sensitivity to errors holds true even for the closed-form sparsemax policy (q = 2): due to its compactness, by contrast it is inherently less robust than the softmax [Chen et al., 2018, Lee et al., 2020. Implicit Kullback-Leibler (KL) regularization might come to rescue for improving the error-robustness of non-Shannon entropies. Currently one of the state-of-the-art methods Munchausen Deep Q-Network (MDQN) [Vieillard et al., 2020b] has demonstrated that significant performance boost can be attained by adding logarithm of the stochastic policy ln π as a bootstrapping term to any temporal difference learning algorithms for facilitating learning. The general claim and success of MDQN motivates us to investigate its Munchausen Tsallis DQN counterpart. However, as shown in Figure 1, MDQN typically fails to learn anything even for simple tasks with Tsallis entropy when q = 1, which suggests that directly resorting to MDQN for Tsallis entropy is infeasible.
In this paper, we connect three relevant ideas: MDQN, KL regularization and advantage learning. We show the implicit KL regularization of MDQN happens as a result of advantage learning which is due to the equivalence between log-policy and advantage function, which only holds for Shannon entropy q = 1. Therefore, the failure of MDQN in MTE is expected since for q = 1 the equivalence is lost. Motivated by this observation, we propose to enforce implicit KL regularization by explicitly enlarging the action gap in the MTE framework. By extensive experiments we demonstrate that TAL achieves significant improvement over the stateof-the-art value-based MTE method Tsallis-DQN, even for those entropic indices that do not have closed-form policy expression. We also show its performance is competitive with state-of-the-art advantage learning algorithms (including original MDQN), which brings a competitive substitute for the conventional Shannon entropy in relevant domains [Lee et al., 2020].
The rest of the paper is organized as follows: in Section 2 we briefly survey related work. In Section 3 we review the background for the proposed method in Section 4. The proposed framework is comprehensively evaluated in Section 5. We conclude the paper in Section 6.

RELATED WORK
The very recent success of MDQN shows significantly improved performance can be attained by simply augmenting reward function with logarithm of the policy. While the authors of [Vieillard et al., 2020b] claimed such log-policy augmentation is generally applicable for any stochastic policy and demonstrated the effectiveness for soft Q-learning, we found that in practice MDQN worked poorly with the more general Tsallis entropy that is more suited to risksensitive applications [Lee et al., 2018[Lee et al., , 2020, which begs the question of why MDQN achieved superior performance only with Shannon entropy. The connection with action gap maximization was mentioned in [Vieillard et al., 2020b], though the authors attributed the superior performance of MDQN to implicit KL regularization.
The concept of advantage learning due to [Baird and Moore, 1999] lies in increasing the action gap and hence increasingly distinguishing the optimal action from suboptimal ones. Besides rendering the algorithm empirically more robust, increased action gap comes with various benefits. For example, Farahmand [2011] showed that if the action gap regularity assumption holds, convergence rate of suboptimality gap towards zero can be much faster. Bellemare et al.
[2016] studied the non-stationary policy problem of Bellman optimality operator and proposed a solution by modifying based on the advantage learning scheme. Recently, advantage learning was extended by [Lu et al., 2019] to the setting of random action gap coefficients and by [Ferret et al., 2021] to self-imitation learning.
The connection between advantage learning and entropyregularized RL was first alluded to by [Azar et al., 2012] when studying KL-regularized policy iteration. This approach was followed by [Kozuno et al., 2019] to incorporate Shannon entropy. By defining a preference function, Kozuno et al. [2019] found that KL regularization is possible by iterating upon an advantage learning scheme. In [Vieillard et al., 2020b], the authors showed how to derive CVI starting from MDQN. In this paper, we derive MDQN from CVI from an advantage learning perspective. By connecting those ideas we justify the use of advantage learning for implicitly enforcing KL regularization in the MTE framework.

RL BASICS
Reinforcement learning problems are typically formulated by Markov decision processes (MDPs) which are expressed by the quintuple (S, A, P, r, γ), where S and A denote state space and action space, respectively. |S| defines the cardinality of state space and likewise for the action space. P denotes the transition probability kernel such that P (·|s, a) indicates the probability of transitioning to next state conditional upon taking action a in state s. Let r(s, a) denote the reward associated with that transition. When the time dependence t should be made explicit, we write r t := r(s t , a t ). The discount factor γ ∈ (0, 1) trades off the importance between current and future rewards. A policy π maps a state to a distribution over actions. We define the state-action value function Q π ∈ R |S|×|A| as: where the expectation is with respect to the trajectory induced by policy π and transition probability P .
Value-based methods typically iterate on an initial Q as: T π Q := r + γP π Q, where T π denotes the Bellman operator and γP π Q := γE s ∼P (·|s,a),a ∼π(·|s ) [Q(s , a )], with the definition being component-wise. Repeating the above it-eration guarantees convergence to its unique fixed point Q π . Our goal is to find an optimal policy π * such that T * Q = max π T π Q. The optimal policy can be extracted with the greedy operator π(a|s)= G(Q π ) := arg max π Q π . For convenience, for any two functions F 1 , F 2 ∈ R |S|×|A| we define their inner product as F 1 , F 2 ∈ R |S| . We also define 1 as an all-one vector whose dimension should be clear from the context.
To render the policy robust against suboptimal actions that have temporally deceptively high values, advantage learning scheme augments the standard Bellman operator T π Q with an additional action gap or advantage function: A π ∈ R |S|×|A| = Q π − V π , where V π = π, Q π is the average of action values. The agent is prompted to select actions that have values higher than the average to increasingly distinguish optimal actions from bad ones.

MAXIMUM ENTROPY RL
In the recently popular maximum entropy RL literature, the reward is augmented by the Shannon entropy τ H (π) := τ −π, ln π , where τ is the augmentation coefficient. By the Fenchel conjugacy [Geist et al., 2019], the Shannon entropy induced optimal policy is a Boltzmann distribution: V := τ ln 1, exp τ −1 Q is the soft value function. Its regularized Bellman operators are defined as T τ π Q = r + γP π, Q−τ ln π .
It turns out that the Shannon entropy is a special case of the well-known Tsallis entropy [Tsallis, 1988] parametrized by entropic index q: where α is its regularization coefficient. The Shannon entropy is recovered by letting k = 1 2 and q → 1. When q → ∞, the regularization effect vanishes. In this paper, we fix k = 1 2 and consider various cases of q. The corresponding regularized Bellman operator is hence given by T α π Q = r+γP π,Q + α 2(q−1) 1 − π q−1 . Tsallis entropy induces the stochastic optimal policy as: where the operation [·] + converts negative components to 0. ψ is the normalization term to ensure the policy sums to one. When q = 2, we recover the sparsemax policy [Lee et al., 2018, Chow et al., 2018] whose normalization is: where S(s) is the set of actions satisfying 1+i , a (j) indicates the action with jth largest action value, K(s) denotes the cardinality of S(s). The value function is The sparsemax policy has been recently demonstrated as a suitable candidate for safety-sensitive tasks such as robotics [Lee et al., 2018[Lee et al., , 2020. However, the performance of its value-based methods typically cannot match Shannon entropy since it often results in insufficient exploration.
When q = 1, 2, ∞, the normalization term and hence optimal policy might not have closed-form expression. But we can approximate the optimal policy by leveraging first order expansion following [Chen et al., 2018] 1 : . We denote its associated Bellman operator asT α π . Detailed derivation of approximate Tsallis policy is left to Appendix A.

MUNCHAUSEN RL
MDQN [Vieillard et al., 2020b] proposes optimizing for the immediate reward augmented by the scaled log-policy of the agent when using any TD scheme. Specifically, MDQN was implemented based on soft Q-learning as follows: where the red term is the Munchausen term, the blue term comes from soft Q-learning. For simplicity let β = 1, MDQN has the following equivalence: where Q k := Q k − τ ln π k is the newly defined action value function. Hence MDQN performs KL regularization by adding the Munchausen term ln π k+1 to soft Qlearning. One of the crucial properties of KL regularization is its optimal policy averages over past action values: π k+1 ∝ exp τ −1 k j=1 Q j [Vieillard et al., 2020a], which effectively cancels out errors under mild assumptions.
In the following section, we show the implicit KL regularization is performed when the Munchausen term ln π is equivalent to performing advantage learning under certain conditions, motivating our later proposal.

AN ADVANTAGE LEARNING PERSPECTIVE FOR MUNCHAUSEN RL
It is worth noting that in the lieu of Shannon entropy augmentation, from Eq. (2) one has ln π = τ −1 (Q − V ), hence adding the Munchausen term coincides with advantage learning. In the recent literature, conservative value iteration (CVI) [Kozuno et al., 2019] comprehensively analyzes the relationship between advantage learning and KL regularization: CVI states the conditions under which advantage learning could implicitly perform KL regularization.
The connection between MDQN, KL regularization and advantage learning motivates us to investigate the possibility of enforcing implicit KL regularization for the MTE framework via advantage learning. To do so, we need to verify that the superior performance of MDQN is due to advantage learning. We re-derive MDQN by manipulating the CVI update rule since CVI generalizes advantage learning. We provide full derivation in Appendix A.2 and succintly summarize the key steps here.
It turns out the CVI update rule can be written as the following, with Ψ, W being the CVI action and state value function, respectively: where β ∈ [0, 1] is a function of the Shannon entropy and KL divergence coefficients.
It is worth noting that Eq. (10) is itself a new value iteration scheme regardless of the definition of Ψ and π since we can arbitrarily initialize Ψ 0 , π 0 . CVI states that, if the policy π k+1 in Eq. (10) meets the Boltzmann assumption π k+1 ∝ exp τ −1 Ψ k (CVI itself uses Boltzmann policy but analyzes general advantage learning), then iterating upon Eq. (10) along results in KL regularization.
The simplest method to ensure π k+1 is Boltzmann is perhaps to perform soft Q-learning. By rewriting Eq. (10) as a soft Q-learning scheme and replacing Ψ, W with Q, V we have: Algorithm 1: TAL-DQN Input: total steps T , update period I, interaction period C, epsilon-greedy threshold Initialize: Network weightsθ = θ, where the blue part comes from soft Q-learning and the we recognize the red part is β(Q k − V k ) = βτ ln π k . We hence see this scheme is same with the MDQN update rule Eq. (8).
This above analysis implies that MDQN achieves implicit KL regularization and superior performance thanks to the equivalence between the Munchausen term and the action gap. This intuition is confirmed by that in practice, MDQN actually computes the ln π term by Q − V [Vieillard et al., 2020b, Appendix B.1]. Hence as learning proceeds, the probabilities of optimal actions increase and so do ln π, which implies the action gap is also increased as is shown in Figure 5.
The key for deriving the relationship between CVI and MDQN is the equivalence τ ln π k+1 = Q k − V k . It is hence natural to conjecture that, if the equivalence does not hold as when q = 1 in the general Tsallis entropy, MDQN can no longer perform implicit KL regularization, and learning performance might be significantly degraded. As an example, consider Eq. (4) which is q = 2. The Munchausen term ln π = ln Q(s,a) α − ψ Q(s,·) α + may be undefined since the policy assigns zero probabilities to some of the actions. Even if we add some small value ∆ in practice to prevent illdefined ln π, it does not encode action gap information since where V was defined in Eq. (6). This conclusion holds for other q as well. Hence it is confirmed that resorting to MDQN does not bring KL regularization for the MTE framework.

ADVANTAGE LEARNING FOR GENERAL TSALLIS ENTROPY RL
Motivated by the observation in the prior section, instead of relying on ln π, we propose to explicitly perform advantage learning by increasing the action gap Q − π, Q to conform to the advantage learning scheme of [Azar et al.,  2012, Kozuno et al., 2019]. Though the policy with q = 1 is no longer Boltzmann, by [Kozuno et al., 2019, Eq. (12)] the Tsallis policy can still be used. For justification the reader is referred to Appendix A.3.
We can succinctly summarize the proposed method: Tsallis advantage learning (TAL) as the following: whereG α is the approximate Tsallis policy defined in Eq. (7). We can also change the policy/Bellman operator pair (G α , T α π ) to (G τ , T τ π ), (G α , T α π ), (G, T π ) which correspond to settting q = 1, 2, ∞, respectively. When q = 1, this scheme coincides with Munchausen RL. When q = ∞, there is no regularization hence the scheme degenerates to advantage learning [Baird and Moore, 1999]. The superscript m indicates m times application of the Bellman operator. Typically m = 1, ∞ which correspond to value iteration and policy iteration schemes. β is the advantage coefficient and typically is between [0, 1]. π k+1 , Q k is used to approximate the regularized value function V . We found that this approximation led to significantly better performance.
In this paper we are interested in verifying effectiveness of the proposed method as a value iteration algorithm, i.e. m = 1. Specifically, we follow [Vieillard et al., 2020b] to implement our algorithm based on the DQN architecture. We maintain two networks with parameters θ,θ, with the latter being target network updated after a fixed number of timesteps. The loss function is defined by: where the policy πθ is computed following Eq. (11). The algorithm Tsallis Advantage Learning -DQN (TAL-DQN) is listed in Alg. 1. We provide implementation details in Appendix B.

EXPERIMENTS
We aim to demonstrate that the proposed algorithm TAL is an effective generalization of Munchausen RL, in that when entropic index q = 1 they coincide, but for other q the Munchasuen bootstrapping term ln π can significantly deteriorate learning, while TAL can effectively boost the performance even for those q that entail approximation.
For comprehensive evaluation, we select three different domains: simple Gym classic control [Brockman et al., 2016], lightweight Atari games [Young and Tian, 2019] and challenging full-fledged Atari games [Bellemare et al., 2013]. We aim to show TAL improves upon the SOTA value-based Tsallis entropy method Tsallis-DQN and achieves comparable performance with SOTA advantage learning methods.

GYM CLASSIC CONTROL
We first examine the simple Gym classic control problems CartPole-v1, LunarLander-v2 and Acrobot-v1. Their simplicity allows for evaluation with large number of seeds to verify our analysis. We name the algorithm Tsallis-DQN that sets β = 0 in Eq. (11) and compare Tsallis-DQN with TAL and Munchausen-Tsallis-DQN (MT-DQN) for entropic indices q = −1, 2, 3, 4. When q = 2 the policy has closed-form solution, for other indices the approximation introduced in Eq. (7) is employed. All algorithms are evaluated for 5 × 10 5 steps with 30 seeds. We decompose the 5 × 10 5 steps into 50 iterations. Implementation details such as network architecture and hyperparameters are provided in Appendix B.1. The results are shown in Figure 2.
Consistent with our analysis, Munchausen RL did not improve the performance for all entropic indices. For q = 2, MT-DQN failed to learn any meaningful behavior even with analytic policy expression, while Tsallis-DQN performed relatively well. For q = 3, 4, both MT-DQN and Tsallis-DQN failed to solve the CartPole environment. It is also interesting to inspect the case of q = −1, in which the Tsallis entropy becomes convex and hence the existing regularization results [Geist et al., 2019, Li et al., 2019 fail to hold. We show such result only for completeness, and one can expect the poor performance of all entropyregularized algorithms. One can see the same trend holds true for LunarLander-v2 and Acrobot-v1 as well in Figure 3. We quantitatively evaluate the action gap between the actions with the largest and second largest values, i.e. Q(s, a (1) )−Q(s, a (2) ) and show the averaged results in Figure 5, which proves that the action gap is indeed enlarged.
One might also be interested in non-integer value of q, since we might benefit from the intermediate values from the two analytic choices q = 1, 2. We therefore include the experiments with q = 3 2 , 5 2 and show them in Figure 4. It is apparent that that the trend still holds valid for non-integer values of q. For q = 3 2 ∈ [1, 2], we can expect this choice induces policy that stands between the softmax (q = 1) and the Sparsemax (q = 2), in that it is neither sparse nor assigns probability to all actions. However, with this choice, on both environments Tsallis-DQN and MT-DQN performed extremely poor, leading to the lowest scores possible. On the other hand, TAL managed to robustly converge to the optimal policy. For q = 5 2 the situation is similar, with small improvement of Tsallis-DQN and MT-DQN. But we can see TAL did not converge to the optimal solution on CartPole-v1, this might be due to the hyperparameters in Table 1 requires further fine-tuning for such specific choice.

MINATAR GAMES
We inspect whether TAL can still boost the performance of Tsallis-DQN and work well on relatively complicated problems with high dimensional image as the state space. MinAtar provides 5 lightweight Atari games with optimization on multiple aspects including sticky actions, training frequency and reward normalization, etc. We compare TAL with Tsallis-DQN, MT-DQN with entropic index q = 2 since it enjoys closed-form policy expression. We also compare with persistent AL (PAL) [Bellemare et al., 2016] that corrects the bias of the Bellman optimality operator; stochastic AL (SAL) that generalizes β to random variables drawn from various distributions [Lu et al., 2019]. Every run con-  sists of 10 7 frames without frame skipping. We define every 200, 000 frames as one iteration so totally 50 iterations. All algorithms are averaged over 3 seeds. Since we use image as input, convolutional network is necessary. We detail the network architecture and hyperparameters used for all algorithms in Appendix B.2.
We first examine whether TAL boosts the performance of Tsallis-DQN. From the upper row of Figure 6 it is clear that for relatively simple environments like Breakout and SpaceInvaders, TAL improved upon Tsallis-DQN slightly. However for challenging tasks like Seaquest, Asterix, Freeway, Tsallis-DQN failed to learn meaningful behavior while TAL successfully converged. By contrast, MT-DQN showed flat learning curves for all environments, validating our analysis that ln π does not encode action gap information and hence can deteriorate learning.
We also ask whether TAL can compete with state-of-the-art advantage learning algorithms. It is known that the hard max policy induced by Tsallis sparse entropy might cause brittle value function during learning, typically the performance of Tsallis entropy regularized algorithms cannot match SOTA algorithms such as PAL. From the lower row of Figure 6 we can see that PAL and MDQN performed the best, but TAL had similar performance throughout.
On the other hand, SAL with the empirically performant choice of β failed to keep up with other three algorithms due to the strong stochasticity in the advantage coefficient. This section confirms that Tsallis entropy regularized algorithms can perform competitively with SOTA advantage learning algorithms while enjoying strong theoretical properties for policies, whose good performance was due to the advantage learning and subsequent implicit KL regularization.

DISTRIBUTIONAL TAL ON ATARI GAMES
Similar to Munchausen RL that can be combined with distributional RL methods. We demonstrate that TAL can also be leveraged in the context of distributional RL. Specifically, we implement TAL on top of the quantile regression DQN (QR-DQN) [Dabney et al., 2018].
We compare TAL with MT-DQN with entropic index q = 2, since q = 1 coincides with MDQN. We choose a subset of 15 games from the full-fledged Atari games [Bellemare et al., 2013] for showing TAL remains effective for challenging problems. Implementation details are provided in Appendix B.3. Every single run consists of 3 × 10 7 steps. We define every 10 5 steps as one iteration so totally 300 iterations. All algorithms are averaged over 3 seeds.  The learning results in Figure 8 further confirmed our analysis that TAL is robust on complicated environments, and can work well with state-of-the-art RL algorithms. By contrast, MT-DQN failed to learn any meaningful behaviors.
Did TAL improve upon Tsallis-DQN? We compare TAL and Tsallis-DQN on KungFuMaster in which MT-DQN showed non-trivial performance. As illustrated by Figure  9, MT-DQN degraded the performance of Tsallis-DQN, proving the negative effect of the Tsallis Munchausen term. In Figure 10 we compare Tsallis-DQN and TAL, and one can see that TAL still improved upon Tsallis-DQN, which is consistent with the trend shown in Gym and MinAtar environments.

DISCUSSION AND CONCLUSION
In this paper we proposed to implicitly perform KL regularization in the maximum Tsallis entropy framework to im- prove its error-robustness since the non-Shannon entropies are inherently less robust. We showed simply resorting to recently successful Munchausen DQN led to significantly degraded performance, due to the loss of equivalence between log-policy and advantage learning. Accordingly, a novel algorithm Tsallis advantage learning was proposed to enforce implicit KL regularization. By extensive experiments we verified that TAL improved upon the SOTA value-based MTE method Tsallis-DQN by a large margin, and exhibited comparable performance to SOTA advantage learning methods.
Several interesting future directions include combining TAL with actor-critic methods for further scalability, and leveraging general logarithm function for the Munchausen term so the log-policy term again encodes advantage information.

A.1 DERIVATION OF APPROXIMATE TSALLIS POLICY
The derivation of approximate Tsallis policy basically follows [Chen et al., 2018] but with a general k value instead of k = 1.
The derivation begins with assuming an actor-critic framework where the policy network is parametrized by w. It is well-known that the parameters should be updated towards the direction specified by the policy gradient theorem: where d π denotes the stationary distribution induced by π, H (π) denotes the Shannon entropy and α is the coefficient. λ(s) are the Lagrange multipliers for the constraint 1, π = 1. In the Tsallis entropy framework, we replace H (π) with H q (π) := kq q−1 (1 − 1, π q ). We can now explicitly write the optimal condition for the policy network parameters: where we leveraged ∂Hq(π) ∂w = kq q−1 1, π q ∂ ln π ∂w in the second step and absorbed terms into the expectation with respect to π, d π in the last step. ψ(s) denotes the adjusted Lagrange multipliers by taking λ(s) inside the expectation and modifying it according to the discounted stationary distribution.
Now it suffices to verify either ∂ ln π ∂w = 0 or When q = 2, we recover the sparsemax policy Eq. (4) introduced in Section 3.2. When q = 1, 2, the closed-form expression of π, ψ might not exist. Following [Chen et al., 2018], we leverage first order expansion on the policy as: By the constraint 1, π = 1 we can approximately obtain the normalization as: The associated set S(s) of allowable actions must satisfy: In this paper, we consider the case k = 1 2 , which leads to the following approximate policy and normalization: where the set S(s) then allows actions satisfying 1 2 q + i Q(s,a) α > i j=1 Q(s,a (j) ) α + j( q 2 − q q−2 ). We denote its associated Bellman operator asT α π .

A.2 ADVANTAGE LEARNING AS KL REGULARIZATION
This section shows our derivation of connection between CVI and MDQN which is different from the connection shown in [Vieillard et al., 2020b, Appendix A.4], but our conclusions are essentially the same.
Conservative Value Iteration (CVI) [Kozuno et al., 2019] investigates the scheme maximizing: where H (π) := − π, ln π is the Shannon entropy and D KL (π||π) := π, ln π − lnπ is the KL divergence. By the Fenchel conjugacy, we can show that the optimal policy takes the form where V * π is the regularized value function. In practice, at the k + 1-th iteration,π is set to the previous policy π k . Hence Eq. (21) can be written as π k+1 ∝ π k σ σ+τ exp 1 σ+τ (r + γP V π k ) . While a two-loop policy iteration algorithm can be employed to obtain π k+1 , we can avoid computing the recursively defined π k by defining the action preference function: Now the optimal policy for k +1-th iteration can be compactly expressed as CVI converges to the maximum Shannon entropy optimal policy by iterating upon Ψ: where W k is the value function associated with Ψ k and π is a Boltzmann policy. Eq. (24) implies that CVI performs a recursion which evaluates the preference function first: this suggests CVI is different from the conventional value iteration methods such as Eq. (8): Without loss of generality we can reverse the order in Eq. (25) by assuming π 0 is a uniform policy: where the definition of the action preference function is modified as: We see if we set β := σ σ+τ ∈ [0, 1] and ζ := 1 σ+τ ∈ (0, ∞] in Eq. (26), we obtain Eq. (10). Hence the CVI recursion can now be rewritten as: It is worth noting that Eq. (28) is itself a new value iteration scheme, regardless of the definition of Ψ. CVI states that, if the policy satisfies the Boltzmann assumption, then simply iterating upon Eq. (28) results in KL regularization.
The above analysis implies that any value iteration methods could enjoy the KL regularization properties by replacing Ψ, W with Q, V without needing to care about the definition of Ψ, W since we can arbitrarily initialize Q 0 = Ψ 0 = 0.
The simplest method to ensure the policy meets the Boltzmann assumption is by performing soft Q-learning on top of Eq. (28). By rewriting Eq. (28) as a soft Q-learning scheme and replacing every appearance of Ψ, W with Q, V , we have: where the blue part is due to the definition of soft Q-learning as in Eq. (8) to ensure the policy is a Boltzmann distribution. By observing that β(Q k − V k ) = βτ ln π k we see this is the Munchausen DQN update rule Eq. (8).
The key for deriving the relationship between CVI and MDQN is the equivalence τ ln π k+1 = Q k − V k . It is hence natural to conjecture that, if the equivalence does not hold as when q = 1 in the general Tsallis entropy, MDQN can no longer perform implicit KL regularization. Furthermore, the contraction property might be lost by adding such ln π term.

A.3 TSALLIS ADVANTAGE LEARNING FOR KL REGULARIZATION
In Section A.2 we analyzed the relationship between advantage learning and KL regularization. In practice, the value function W k in CVI recursion Eq. (24) is approximated by π k , Ψ k as it saves computation and achieves numerical stability [Azar et al., 2012, Kozuno et al., 2019. The requirement of π being Boltzmann distribution is not a must, as can be seen from [Kozuno et al., 2019, Eq. (12)] which states that any policy µ k satisfying the relation µ k , Ψ k ≥ π k , Ψ k can be used. This constitutes the theoretical basis for our use of π k , Q k in Eq. (11) at the absence of analytic value function expression. Even for q = 2 where the closedform V is available, we found that using the advantage as Q k − π k , Q k significantly improved the performance and stability.

B IMPLEMENTATION DETAILS
In this section we provide implementation details for all environments we used. Specifically, three different architectures were leveraged for handling gym environments, MinAtar games and Atari games, detailed in Sections B.1, B.2 and B.3, respectively. We added a small number ∆ to π to ensure ln π is well defined. For fast and reproducible evaluation, we implemented all algorithms based on the Stable-Baselines3 library [Raffin et al., 2021].

B.1 GYM CLASSIC CONTROL
We introduce the parameters we used for the Gym environments in this section. Specifically, the hyperparameters are listed in Table 1. The epsilon threshold is fixed at 0.01 from the beginning of learning. The Munchausen number ∆ refers to the small value added to the policy to prevent ill-defined ln π. FC n refers to the fully connected layer with n activation units.

B.2 MINATAR GAMES
For MinAtar games we employed the configuration recommended by [Young and Tian, 2019]. The hyperparameters are listed in Table 2.
Since MinAtar games optimize different aspects of Atari games, no frame skipping is necessary and hence the for every frame we update the network. The epsilon greedy threshold : 1.0 → 0.05| 10% denotes that is initialized as 1.0 and gradually decays to 0.05 through the first 10% of learning.
The parameter τ is the Shannon entropy coefficient used for MDQN and plays a similar role as α. The advantage learning coefficient β is also used for PAL. For SAL, we use the empirically most performant choice β SAL of [Lu et al., 2019] which is drawn from the Beta(2, 9) distribution and adds a constant 7 9 . Then E [β SAL ] = 1 and Var [β SAL ] = 7 405 . The network architecture consists of only one convolutional layer where Conv d a,b c denotes a convolutional layer with c filters of size a × b and stride d.
In Appendix A.2 we analyzed the relationship between MDQN and CVI and in Figure 7 we compared TAL against CVI and TAL with entropic index q = 2 to see if TAL can achieve comparable performance to the state-of-theart algorithm. CVI used the same Boltzmann temperature 1 σ+τ = 0.03 and advantage coefficient β as in Table 2. Since CVI and TAL exhibited similar performance, it might be safe to replace the Shannon entropy with Tsallis entropy in many applications where safety or parsimonious descrip-

B.3 ATARI GAMES
We implemented TAL and MT-DQN on top of QR-DQN, which is a famous distributional RL algorithm. Instead of learning the conditional expectation of cumulative return Q as in Eq. (1), distributional RL attempts to learn the distribu-