--- title: "Reinforcement Learning with Dynamic Boltzmann Softmax Updates" authors: - "Ling Pan" - "Qingpeng Cai" - "Qi Meng" - "Wei Chen" - "Longbo Huang" doi: "10.24963/ijcai.2020/276" url: "https://ijcai.org/proceedings/2020/276" pdf: "https://ijcai.org/proceedings/2020/0276.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "1992-1998" track: "Main track" keywords: - "Machine Learning: Reinforcement Learning" - "Machine Learning: Deep Reinforcement Learning" --- # Reinforcement Learning with Dynamic Boltzmann Softmax Updates Ling Pan, Qingpeng Cai, Qi Meng, Wei Chen, Longbo Huang *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 1992-1998. DOI: [10.24963/ijcai.2020/276](https://doi.org/10.24963/ijcai.2020/276) ## Abstract Value function estimation is an important task in reinforcement learning, i.e., prediction. The Boltzmann softmax operator is a natural value estimator and can provide several benefits. However, it does not satisfy the non-expansion property, and its direct use may fail to converge even in value iteration. In this paper, we propose to update the value function with dynamic Boltzmann softmax (DBS) operator, which has good convergence property in the setting of planning and learning. Experimental results on GridWorld show that the DBS operator enables better estimation of the value function, which rectifies the convergence issue of the softmax operator. Finally, we propose the DBS-DQN algorithm by applying the DBS operator, which outperforms DQN substantially in 40 out of 49 Atari games. ## Full text ## 1 Introduction Reinforcement learning has achieved groundbreaking success for many decision making problems [Kober et al., 2013; Mnih et al., 2015]. Without full information of the environment, the agent learns an optimal policy by interacting with the environment from experience. Value function estimation, i.e., prediction, is an important task in reinforcement learning [Xu et al., 2018; Pan et al., 2019]. In the prediction task, it requires the agent to have a good estimate of the value function in order to update towards the true value function. A key factor to prediction is the action-value summary operator. The action-value summary operator for a popular off-policy method, Q-learning [Watkins, 1989], is the hard max operator, which always commits to the maximum action-value function according to current estimation for updating the value estimator. The "hard max" updating scheme may lead to misbehavior due to noise in stochastic environments [Hasselt, 2010; van Hasselt, 2013; Fox et al., 2015]. Even in deterministic environments, this may not be accurate as the value estimator is not correct in the early stage of the learning process. Consequently, it is important to choose an appropriate action-value summary operator. The Boltzmann softmax operator is a natural value estimator based on the Boltzmann softmax distribution, which is a widely-used scheme to address the exploration-exploitation dilemma in reinforcement learning [Azar et al., 2012; CesaBianchi et al., 2017]. In addition, the Boltzmann softmax operator provides benefits for reducing overestimation and gradient noise in deep Q-networks [Song et al., 2019]. However, despite the advantages, it is challenging to apply the Boltzmann softmax operator in value function estimation. As shown in [Littman and Szepesv´ari, 1996; Asadi and Littman, 2017], it is not a non-expansion, which may lead to multiple fixed-points and thus the optimal value function of this policy is not well-defined. Non-expansion is a vital and widelyused sufficient property to guarantee the convergence of the planning and learning algorithm. Without such property, the algorithm may misbehave or even diverge. We propose to update the value function using the dynamic Boltzmann softmax (DBS) operator with good convergence guarantee. Our idea is to make the parameter β time-varying while being state-independent. We prove that having βt approach ∞ suffices to guarantee the convergence of value iteration with the DBS operator. Therefore, the DBS operator rectifies the convergence issue of the Boltzmann softmax operator with fixed parameters. Note that we also achieve a tighter error bound for the fixed-parameter softmax operator in general cases compared with [Song et al., 2019]. In addition, we show that the DBS operator achieves good convergence rate. Based on this theoretical guarantee, we apply the DBS operator to estimate value functions in the setting of model-free reinforcement learning without known model. We prove that the corresponding DBS Q-learning algorithm also guarantees convergence. Finally, we propose the DBSDQN algorithm, which generalizes our proposed DBS operator from tabular Q-learning to deep Q-networks using function approximators in high-dimensional state spaces. It is crucial to note the DBS operator is the only one that meets all desired properties proposed in [Song et al., 2019] up to now, as it ensures Bellman optimality, enables overestimation reduction, directly represents a policy, can be applicable to double Q-learning [Hasselt, 2010], and requires no tuning. To examine the effectiveness of the DBS operator, we conduct extensive experiments to evaluate the effectiveness and efficiency. We first evaluate DBS value iteration and DBS Q-learning on a tabular game, the GridWorld. Our results show that the DBS operator leads to smaller error and better performance than vanilla Q-learning and soft Q-learning [Haarnoja et al., 2017]. We then evaluate DBS-DQN on large scale Atari2600 games, and we show that DBS-DQN outperforms DQN in 40 out of 49 Atari games. The main contributions can be summarized as follows: - We analyze the error bound of the Boltzmann softmax operator with arbitrary parameters, including static and dynamic. - We propose the DBS operator, which has good convergence property in the setting of planning and learning. - We conduct extensive experiments to verify the effectiveness of the DBS operator in 49 Atari games. Experimental results verify our theoretical analysis and demonstrate the effectiveness of the DBS operator. ## 2 Preliminaries A Markov decision process (MDP) is defined by a 5-tuple (S, A, p, r, γ), where S and A denote the set of states and actions, p(s′ |s, a) the transition probability from state s to state s′ under action a, and r(s, a) the corresponding immediate reward. The discount factor is denoted by γ ∈ [0, 1). The agent interacts with the environment with its policy π, a mapping from state to action. The objective is to find an optimal policy that maximizes the expected discounted long-term reward E[∑∞t=0 γ t rt|π], which can be solved by estimating value functions. The state value of s and stateaction value of s and a under policy π are defined as V π (s) = Eπ[∑∞t=0 γ t rt|s0 = s] and Qπ (s, a) = Eπ[∑∞t=0 γ t rt|s0 = s, a0 = a]. The optimal value functions are defined as V ∗ (s) = maxπ V π (s) and Q∗ (s, a) = maxπ Qπ (s, a). The optimal value function V ∗ and Q∗ satisfy the Bellman equation, which is defined recursively as in Eq. (1): Starting from an arbitrary initial value function V0, the optimal value function V ∗ can be computed by value iteration [Bellman, 1957] according to an iterative update Vk+1 = T Vk, where T is the Bellman operator defined by (T V )(s) = maxa∈A [r(s, a) + ∑s′∈S p(s′ |s, a)γV (s′ )] . When the model is unknown, Q-learning [Watkins and Dayan, 1992] is an effective algorithm to learn by exploring the environment. Value estimation and update for a given trajectory (s, a, r, s′ ) for Q-learning is defined as: where α denotes the learning rate. Note that Q-learning employs the hard max operator for value function updates, i.e., max(X) = maxi xi. Another common operator is the log-sum-exp operator (Eq. (5) in [Haarnoja et al., 2017]): Lβ(X) = 1β log(∑ni=1 eβxi ). The Boltzmann softmax oper- ## 3 Dynamic Boltzmann Softmax Updates In this section, we propose the dynamic Boltzmann softmax operator (DBS) for value function updates. The DBS operator is defined as: ∀s ∈ S, where βt is non-negative. Our core idea of the DBS operator is to dynamically adjust the value of βt during the iteration. We now give theoretical analysis of the proposed DBS operator and show that it has good convergence guarantee. ## 3.1 Value Iteration with DBS Updates DBS value iteration admits a time-varying, state-independent sequence {βt} and updates the value function according to boltzβt by iterating the following steps: For the ease of notations, we denote Tβt the function that iterates any value function by Eq. (4). Therefore, the way to update the value function is according to the exponential weighting scheme which is related to both the current estimator and the parameter βt. ## Theoretical Analysis It has been shown that the Boltzmann softmax operator is not a non-expansion [Littman and Szepesv´ari, 1996], as it does not satisfy Ineq. (5). Indeed, the non-expansion property is a vital and widely-used sufficient condition for achieving convergence of learning algorithms. If the operator is not a non-expansion, the uniqueness of the fixed point may not be guaranteed, which can lead to misbehaviors in value iteration. In Theorem 1, we provide a novel analysis which demonstrates that the DBS operator enables the convergence of DBS value iteration to the optimal value function. We give the proof sketch due to limited space. Theorem 1 (Convergence of value iteration with the DBS operator). For any dynamic Boltzmann softmax operator boltzβt , if βt approaches ∞, the value function after t iterations Vt converges to the optimal value function V ∗ . Proof Sketch. Let Tm be the function that iterates any value function by the max operator. Then, we have For the term (I), we have Combining (6), (7), and (8), we have As max is a contraction mapping, then from Banach fixedpoint theorem [Banach, 1922] we have TmV ∗ = V ∗ . By the definition of DBS value iteration in Eq. (4), During the process of dynamically adjusting βt, although the non-expansion property may be violated for some certain values of β, we only need the state-independent parameter βt to approach infinity to guarantee the convergence. Next, we justify that the DBS operator has good convergence rate guarantee. We omit the proof due to lack of space. Theorem 2 (Convergence rate of value iteration with the DBS operator). For any power series βt = tp (p > 0), let V0 be an arbitrary initial value function such that ||V0||∞ ≤ R 1-γ , where R = maxs,a |r(s, a)|, we have that for any non-negative ϵ < 1/4, after max{O( log( 1ϵ )+log( 1 1-γ )+log(R) log( 1 γ ) ),O(( 1 (1-γ)ϵ ) 1p )} steps, the error ||Vt - V ∗ ||∞ ≤ ϵ. For the larger value of p, the convergence rate is faster. Note that when p approaches ∞, the convergence rate is dominated by the first term, which has the same order as that of the standard Bellman operator, implying that the DBS operator is competitive with the standard Bellman operator in terms of the convergence rate in known environment. From the proof techniques in Theorem 1, we derive the error bound of value iteration with the Boltzmann softmax operator with fixed parameter β in Corollary 1. Corollary 1 (Error bound of value iteration with the Boltzmann softmax operator). For any Boltzmann softmax operator with fixed parameter β, we have limsupt→∞ ||Vt - V ∗ ||∞ ≤ min { log(|A|) β(1-γ) , 2R (1-γ)2 } . Here, we show that after an infinite number of iterations, the error between the value function Vt computed by the Boltzmann softmax operator with the fixed parameter β at the t-th iteration and the optimal value function V ∗ can be upper bounded. However, although the error can be controlled, the direct use of the Boltzmann softmax operator with fixed parameter may introduce performance drop in practice, due to the fact that it violates the non-expansion property. Thus, we conclude that the DBS operator performs better than the traditional Boltzmann softmax operator with fixed parameter in terms of convergence. ## Relation to Existing Results In this section, we compare the error bound in Corollary 1 with that in [Song et al., 2019] (Theorem 3), which studies the error bound of the softmax operator with a fixed parameter β. Theorem 3 (Song et al., 2019). Let Tsoft be the function that iterates any value function by the Boltzmann softmax operator, then ∀(s, a), liminft→∞T t softQ0(s, a) ≥ Q∗ (s, a) - Different from [Song et al., 2019], we provide a more general convergence analysis of the softmax operator covering both static and dynamic parameters. We also achieve a tighter error bound when where R can be normalized to 1 and |A| denotes the number of actions. The term on the RHS of Eq. (11) is quite small as shown in Figure 1(a), where we set γ to be some commonly used values in {0.85, 0.9, 0.95, 0.99}. The shaded area corresponds to the range of β within our bound is tighter, which is a general case. Note that the case where β is extremely small, i.e., approaches 0, is usually not considered in practice. Figure 1(b) shows the improvement of the error bound that is defined as their bound-our bound their bound × 100%, where |A| ranges from 3 to 18 which is common in the Arcade Learning Environment [Bellemare et al., 2013]. Moreover, we also give an analysis of the convergence rate of the DBS operator. (a) Range of β within which our bound is tighter. ![Image](https://ijcai.org/proceedings/2020/fulltext/276/image_000000_caf09f8016335142b50b31cbd545a1835db3d776d686583152358bcbbd343cc1.png) ![Image](https://ijcai.org/proceedings/2020/fulltext/276/image_000001_12a7bed694c547f126e8e1ed0f244aa2e187e9ef4fe45f869d5a1e1d65a23424.png) (b) Improvement ratio. Figure 1: Error bound comparison. Please note that our comparison with [Song et al., 2019] is fair. In particular, [Song et al., 2019] claim that Tsoft converges to T with exponential rate in terms of β. However, we find that the analysis is incorrect (refer to the proof of Theorem 3 in Appendix A.1). 1 1 Eq. (A8) in the proof [Song et al., 2019] relies on the assumption that the the gap function δi(s) = Q(s, a[1]) - Q(s, a[i]) is constant. However, the gap function is varying during value iteration. Thus, Eq. (A7) only leads to the following result: T kQ0(s, a)-T k softQ0(s, a) ≤ γ(1-γk ) 1-γ maxδ∈∆ ∑mi=2 δi (s) 1+eβδi(s) , where ∆ denotes all possible gap functions during value iteration, instead of a fixed gap function. ## Empirical Results We first evaluate DBS value iteration to verify our convergence results in a 10 × 10 GridWorld (Figure 2(a)), which is a larger variant of the environment of [O'Donoghue et al., 2016], with the dark grids representing walls. The agent starts at the upper left corner and aims to eat the apple at the bottom right corner upon receiving a reward of +1. Otherwise, the reward is 0. The terminal state is that the agent successfully eats the apple or a maximum number of steps 300 is reached. For this experiment, we consider the discount factor γ = 0.9. (a) GridWorld. ![Image](https://ijcai.org/proceedings/2020/fulltext/276/image_000002_7ca08ee0b51ba5eda59e4edbcd56803f7c6221f4fb6f9a23958cd2749a3a739d.png) (b) Value loss. ![Image](https://ijcai.org/proceedings/2020/fulltext/276/image_000003_04e758eb79c574df89f2ffbb8e4864ec73008e0a231882db6d3fadeb06ae4eb8.png) (c) Value loss of the last iteration in log scale. ![Image](https://ijcai.org/proceedings/2020/fulltext/276/image_000004_d31a65b1a28212e349106dac25749138d859c1d43a171c97425b7cfb0aa17cc6.png) ![Image](https://ijcai.org/proceedings/2020/fulltext/276/image_000005_b4d4ea2b0662863f72298080bf6ebdac3bdf59cc33934a664fcbd4bba17f7674.png) (d) Convergence rate. Figure 2: DBS value iteration in GridWorld. The value loss of value iteration is shown in Figure 2(b). As expected, for fixed β, a larger value leads to a smaller loss. We then zoom in on Figure 2(b) to further illustrate the difference between fixed β and dynamic βt in Figure 2(c), which shows the value loss for the last episode in log scale. For any fixed β, value iteration suffers from some loss which decreases as β increases. For dynamic βt, the performance of t2 and t3 are the same and achieve the smallest loss in the domain game. Results for the convergence rate is shown in Figure 2(d). For higher order p of βt = tp , the convergence rate is faster. We also observe that the convergence rate of t2 and t10 is very close and matches the performance of the standard Bellman operator as discussed before. From the above results, we find a convergent variant of the Boltzmann softmax operator with good convergence rate, which paves the path for its use in reinforcement learning algorithms with little knowledge about the environment. ## 3.2 Q-learning with DBS Updates In this section, we show that the DBS operator can be applied in a model-free Q-learning algorithm. According to the DBS operator, we propose the DBS Qlearning algorithm, where the value function is updated by Please note that the action selection policy is different from the Boltzmann distribution (e.g., ϵ-greedy policy). As seen in Theorem 2, a larger p results in faster convergence rate in value iteration. However, this is not the case in Q-learning, which differs from value iteration in that it knows little about the environment, and the agent has to learn from experience. If p is too large, it quickly approximates the max operator that favors commitment to current action-value function estimations. This is because the max operator always greedily selects the maximum action-value function according to current estimation, which may not be accurate in the early stage of learning or in noisy environments. ## Theoretical Analysis We get that DBS Q-learning converges to the optimal policy as in Theorem 4, which is under the same additional condition as in DBS value iteration. Theorem 4 (Convergence of DBS Q-learning). DBS Qlearning converges to optimal Q∗ (s, a) values if (1) the state and action spaces are finite, and all state-action pairs are visited infinitely often; (2) ∑t αt(s, a) = ∞ and ∑t α2 t (s, a) < ∞; (3) limt→∞βt =∞; (4) Var(r(s, a)) is bounded. Besides the convergence guarantee, we show that the DBS operator can mitigate the overestimation phenomenon of the max operator in Q-learning [Watkins, 1989]. Let X = {X1, ...,XM} be a set of random variables, where the mean of variable Xi is denoted by µi. Note that in value function estimation, Xi denotes random values of action i for a fixed state. The true value of the maximum expected value is µ∗ (X) = maxi µi. Let ˆµi denote the sample mean of µi and ˆ F denote the joint distribution of ˆµ, where ˆµ = (ˆµ1, ..., ˆµM). The bias of any action-value summary operator ⊗ is defined as Bias(ˆµ∗⊗) = Eˆµ∼ˆF[⊗ ˆµ] - µ∗ (X), i.e., the difference between the expected estimated value output by the operator and the maximum expected value. We now compare the bias for different common operators and we derive the following theorem. Theorem 5. Let ˆµ∗Bβt , ˆµ∗max , ˆµ∗Lβ denote the estimator with the DBS operator, the max operator, and the log-sum-exp operator. For any given set of M random variables, we have ∀t, ∀β, Bias(ˆµ∗Bβt ) ≤ Bias(ˆµ∗max ) ≤ Bias(ˆµ∗Lβ ). In Theorem 5, we show that although the log-sum-exp operator [Haarnoja et al., 2017] is able to encourage exploration because its objective is an entropy-regularized form of the original objective, it may worsen the overestimation phenomenon. In addition, the optimal value function induced by the log-sum-exp operator is biased from the optimal value function of the original MDP [Dai et al., 2018]. In contrast, the DBS operator ensures convergence to the optimal value function as well as reduction of overestimation. ## Empirical Results We now evaluate DBS Q-learning in the same GridWorld environment. Figure 3 shows the number of steps the agent spent until eating the apple in each episode, and a fewer number of steps corresponds to a better performance. For DBS Q-learning, we apply the power function βt = tp with p denoting the order. As shown, DBS Q-learning with the quadratic function achieves the best performance. Note that when p = 1, it performs worse than Q-learning in this simple game, which corresponds to our results in value iteration (Figure 2) as p = 1 leads to an nonnegligible value loss. When the power p of βt = tp increases further, it performs closer to Q-learning. Soft Q-learning [Haarnoja et al., 2017] uses the log-sum-exp operator, where the parameter is chosen with the best performance for comparison. In Figure 3, soft Q-learning performs better than Q-learning as it encourages exploration by entropy regularization. However, it underperforms DBS Q-learning (βt = t2 ) as DBS Q-learning can guarantee convergence to the optimal value function and can eliminate the overestimation phenomenon. Thus, we choose p = 2 in the following Atari experiments. Figure 3: Performance comparison of DBS Q-learning, Soft Qlearning, and Q-learning in GridWorld. ![Image](https://ijcai.org/proceedings/2020/fulltext/276/image_000006_ee05db7b024d5b109c93fa3f18119deab556cdd918f00a9d99bc556eae8a26a8.png) ## 4 The DBS-DQNAlgorithm Now we show that the DBS operator can further be applied to problems with high dimensional state space and action space. The DBS-DQN algorithm is shown in Algorithm 1. We compute the parameter of the DBS operator by applying the power function βt(c) = c · t2 as the quadratic function performs the best in our previous analysis. Here, c denote the coefficient, and contributes to controlling the speed of the increase of βt(c). In many problems, it is critical to choose the hyper-parameter c. In order to make the algorithmmore practical in problems with high-dimensional state spaces, we propose to learn to adjust c in DBS-DQN by the meta gradientbased optimization technique based on [Xu et al., 2018]. The gradient-based optimization method follows the online cross-validation principle [Sutton, 1992]. Given current experience τ = (s, a, r, snext), the parameter θ of the function approximator is updated according to where α denotes the learning rate, and the loss of the neural network is The corresponding gradient of J(τ, θ, c) over θ is ## Algorithm 1 DBS Deep Q-Network - 1: initialize experience replay buffer B - 2: initialize Q-function and target Q-function with random weights θ and θ- - 3: initialize the coefficient c of βt of the DBS operator - 4: for episode t = 1, ..., Mdo - 5: initialize state s - 6: calculate βt(c) = c · t2 - 7: for step = 1, ..., T do - 8: choose a from s using ϵ-greedy policy - 9: execute a, observe reward r, next state snext, and done flag d - 10: store experience (s, a, r, snext, d) in B - 11: sample random minibatch of experiences (s, a, r, snext, d) from B - 12: set y = r + γ(1 - d)boltzβt ( ˆQ(snext, ·; θ-)) - 13: perform a gradient descent step on (y - Q(s, a; θ))2 w.r.t. θ - 14: update c according to Eq.(18) - 15: reset ˆQ = Q every C steps Then, the coefficient c is updated based on the subsequent experience τ ′ = (s′ , a, r′ , s′next ) according to the gradient of the squared error J(τ ′ , θ′ , ¯ c) between the value function approximator Q(s′next , a′ ; θ′ ) and the target value function V (τ ′ , ¯ c; θ-), where ¯ c is the reference value. The gradient is computed according to the chain rule in Eq. (16). For the term (B), according to Eq. (13), we have Then, the update of c is as in Eq. (18), with η denoting the learning rate. 2 Note that it can be hard to choose an appropriate static value of sensitive parameter β. Therefore, it requires rigorous tuning of the task-specific fixed parameter β in different games in [Song et al., 2019], which may limit its efficiency and applicability [Haarnoja et al., 2018]. In contrast, the DBS operator is effective and efficient as it does not require tuning. ## 4.1 Experimental Setup We evaluate the DBS-DQN algorithm on 49 Atari video games from the Arcade Learning Environment [Bellemare et al., 2013], a standard challenging benchmark for deep reinforcement learning algorithms, by comparing it with DQN. For fair comparison, we use the same setup of network architectures and hyper-parameters as in [Mnih et al., 2015] for both DQN and DBS-DQN. Our evaluation procedure is 30 no-op evaluation which is identical to [Mnih et al., 2015], where the agent performs a random number (up to 30) of "do nothing" actions in the beginning of an episode. For each game, we train each algorithm for 50M steps for 3 independent runs to evaluate the performance. 2 In implementation, c is clipped to max{0.01, c}. ## 4.2 Performance Comparison To characterize the effectiveness of DBS-DQN, its improvement over DQN is shown in Figure 4, where the improvement is defined as the relative human normalized score: scoreagent-scorebaseline max{scorehuman,scorebaseline}-scorerandom × 100%, with DQN serving as the baseline. In all, DBS-DQN exceeds the performance of DQN in 40 out of 49 Atari games. Figure 4: Relative human normalized score on Atari games. ![Image](https://ijcai.org/proceedings/2020/fulltext/276/image_000007_c42fd21542074f7b9b7f79a8fadd16cbb940f2d0d87bc9f70683720eab941de9.png) We also compare the median in human normalized score [Van Hasselt et al., 2016] defined as: scoreagent-scorerandom scorehuman-scorerandom × 100%, where human score and random score are taken from [Wang et al., 2015]. The medians for DQN and DBS-DQN are 84.72% and 104.49%, respectively. As shown, DBSDQN significantly outperforms DQN in terms the median of the human normalized score, and surpasses human level. In addition, we compare DBS-DQN with its variant using fine-tuned fixed coefficient c in βt(c), i.e., without gradientbased optimization, in each game, to further demonstrate the effectiveness and efficiency of DBS-DQN. The median of the human normalized score for DBS-DQN (fine-tuned c) is 103.95%, which underperforms DBS-DQN but outperforms DQN. Note that DBS-DQN (fine-tuned c) achieves fairly good performance in term of the median and beats DQN in 33 out of 49 Atari games, which further illustrate the strength of our proposed DBS updates without gradient-based optimization of c. Figure 5 shows the learning curves (moving averaged) of different algorithms, where S-DQN [Song et al., 2019] is with the best parameter β for each game from grid search in {1, 5, 10} (which is the same experimental setting in [Song et al., 2019]). As shown, DBS-DQN outperforms other algorithms. It is also worth noting that S-DQN can fail in some games even with best parameter β. ## 5 RelatedWork The Boltzmann softmax distribution is widely used in reinforcement learning [Littman et al., 1996; Azar et al., 2012; Song et al., 2019]. [Singh et al., 2000] studied convergence of on-policy algorithm Sarsa, where they considered a dynamic scheduling of the parameter in softmax action selection strategy. However, the state-dependent parameter is impractical in complex problems, e.g., Atari. Our work differs from theirs as our DBS operator is state-independent, which can be readily scaled to complex problems with high-dimensional state space. Recently, [Song et al., 2019] applied the softmax operator in DQNs, and also studied the error bound of softmax. In contrast, we propose the DBS operator which rectifies the convergence issue of softmax, where we provide a more general analysis of the convergence property. A notable difference in the theoretical aspect is that we achieve a tighter error bound for softmax in general cases, and we investigate the convergence rate of the DBS operator. Besides the guarantee of Bellman optimality, the DBS operator is efficient as it does not require hyper-parameter tuning. Note that it can be hard to choose an appropriate static value of β in [Song et al., 2019], which is game-specific and can result in different performance. Figure 5: Learning curves in Atari games (shaded area represent mean ± standard deviation). ![Image](https://ijcai.org/proceedings/2020/fulltext/276/image_000008_01e0a7d404f0c7c295e06e3776fe665b239ad3f1aba8e6f66c952535ff0c65fe.png) [Haarnoja et al., 2017] utilized the log-sum-exp operator, which enables better exploration and learns deep energybased policies. The connection between our proposed DBS operator and the log-sum-exp operator is discussed above. [Bellemare et al., 2016] proposed a family of operators which are not necessarily non-expansions, but still preserve optimality while being gap-increasing. However, such conditions are still not satisfied for the Boltzmann softmax operator. ## 6 Conclusion We propose the DBS operator in value function estimation with a time-varying, state-independent parameter. The DBS operator has good convergence guarantee in the setting of planning and learning, which rectifies the convergence issue of the Boltzmann softmax operator. Results validate the effectiveness of DBS-DQN in a suite of Atari games. For future work, it is worth studying the sample complexity of our proposed DBS Q-learning algorithm. It is also promising to apply the DBS operator to other state-of-the-art DQN-based algorithms, such as Rainbow [Hessel et al., 2017]. ## Acknowledgments We would like to thank Tie-Yan Liu for insightful discussions on this paper. The work of Ling Pan and Longbo Huang was supported in part by the National Natural Science Foundation of China Grant 61672316, the Zhongguancun Haihua Institute for Frontier Information Technology and the Turing AI Institute of Nanjing. ## References 1. [Asadi and Littman, 2017] Kavosh Asadi and Michael L Littman. An alternative softmax operator for reinforce- ment learning. In International Conference on Machine Learning, pages 243-252, 2017. 2. [Azar et al., 2012] Mohammad Gheshlaghi Azar, Vicenc ¸ Gómez, and Hilbert J Kappen. Dynamic policy pro- gramming. Journal of Machine Learning Research, 13(Nov):3207-3245, 2012. 3. [Banach, 1922] Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fund. math, 3(1):133-181, 1922. 4. [Bellemare et al., 2013] Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013. 5. [Bellemare et al., 2016] Marc G Bellemare, Georg Ostro- vski, Arthur Guez, Philip S Thomas, and Rémi Munos. In- creasing the action gap: New operators for reinforcement learning. In AAAI, pages 1476-1483, 2016. 6. [Bellman, 1957] Richard Ernest Bellman. Dynamic pro- gramming. 1957. 7. [Cesa-Bianchi et al., 2017] Nicolò Cesa-Bianchi, Claudio Gentile, Gábor Lugosi, and Gergely Neu. Boltzmann ex- ploration done right. In Advances in Neural Information Processing Systems, pages 6284-6293, 2017. 8. [Dai et al., 2018] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear func- tion approximation. In International Conference on Ma- chine Learning, pages 1133-1142, 2018. 9. [Fox et al., 2015] Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft up- dates. arXiv preprint arXiv:1512.08562, 2015. 10. [Haarnoja et al., 2017] Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learn- ing with deep energy-based policies. arXiv preprint arXiv:1702.08165, 2017. 11. [Haarnoja et al., 2018] Tuomas Haarnoja, Aurick Zhou, Se- hoon Ha, Jie Tan, George Tucker, and Sergey Levine. Learning to walk via deep reinforcement learning. arXiv preprint arXiv:1812.11103, 2018. 12. Hado V Hasselt. Double q-learning. In Ad- vances in Neural Information Processing Systems, pages 2613-2621, 2010. 13. [Hessel et al., 2017] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dab- ney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep re- inforcement learning. arXiv preprint arXiv:1710.02298, 2017. 14. [Kober et al., 2013] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11):1238- 1274, 2013. 15. [Littman and Szepesvári, 1996] Michael L Littman and Csaba Szepesvári. A generalized reinforcement-learning model: Convergence and applications. In International Conference on Machine Learning, pages 310-318, 1996. 16. [Littman et al., 1996] Michael L Littman, Andrew W Moore, et al. Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4(11, 28):237-285, 1996. 17. [Mnih et al., 2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidje- land, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015. 18. [O'Donoghue et al., 2016] Brendan O'Donoghue, Remi Munos, Koray Kavukcuoglu, and Volodymyr Mnih. Combining policy gradient and q-learning. arXiv preprint arXiv:1611.01626, 2016. 19. [Pan et al., 2019] Ling Pan, Qingpeng Cai, and Longbo Huang. Multi-path policy optimization. arXiv preprint arXiv:1911.04207, 2019. 20. [Singh et al., 2000] Satinder Singh, Tommi Jaakkola, Michael L Littman, and Csaba Szepesvári. Convergence results for single-step on-policy reinforcement-learning algorithms. Machine learning, 38(3):287-308, 2000. 21. [Song et al., 2019] Zhao Song, Ronald Parr, and Lawrence Carin. Revisiting the softmax bellman operator: New ben- efits and new perspective. 2019. 22. [Sutton, 1992] Richard S Sutton. Adapting bias by gradi- ent descent: An incremental version of delta-bar-delta. In AAAI, pages 171-176, 1992. 23. [Van Hasselt et al., 2016] Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with dou- ble q-learning. In Thirtieth AAAI conference on artificial intelligence, 2016. 24. [van Hasselt, 2013] Hado van Hasselt. Estimating the max- imum expected value: an analysis of (nested) cross vali- dation and the maximum sample average. arXiv preprint arXiv:1302.7175, 2013. 25. [Wang et al., 2015] Ziyu Wang, Tom Schaul, Matteo Hes- sel, Hado Van Hasselt, Marc Lanctot, and Nando De Fre- itas. Dueling network architectures for deep reinforcement learning. arXiv preprint arXiv:1511.06581, 2015. 26. [Watkins and Dayan, 1992] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279- 292, 1992. 27. [Watkins, 1989] Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD thesis, King's Col- lege, Cambridge, 1989. 28. [Xu et al., 2018] Zhongwen Xu, Hado van Hasselt, and David Silver. Meta-gradient reinforcement learning. arXiv preprint arXiv:1805.09801, 2018.