Reinforcement Learning with Dynamic Boltzmann Softmax Updates

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.

(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.

(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.

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.

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.

[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.