Title: BOLTZMANN WEIGHTING DONE RIGHT IN REIN-FORCEMENT LEARNING

Abstract: The Boltzmann softmax operator can trade-off well between exploration and exploitation according to current estimation in an exponential weighting scheme, which is a promising way to address the exploration-exploitation dilemma in reinforcement learning. Unfortunately, the Boltzmann softmax operator is not a non-expansion, which may lead to unstable or even divergent learning behavior when used in estimating the value function. The convergence of value iteration is guaranteed in a restricted set of non-expansive operators and how to characterize the effect of such non-expansive operators in value iteration remains an open problem. In this paper, we propose a new technique to analyze the error bound of value iteration with the the Boltzmann softmax operator. We then propose the dynamic Boltzmann softmax(DBS) operator to enable the convergence to the optimal value function in value iteration. We also present convergence rate analysis of the algorithm. Using Q-learning as an application, we show that the DBS operator can be applied in a model-free reinforcement learning algorithm. Finally, we demonstrate the effectiveness of the DBS operator in a toy problem called Grid-World and a suite of Atari games. Experimental results show that outperforms DQN substantially in benchmark games.

1. INTRODUCTION:

In sequential decision making problem, an agent learns to find an optimal policy that maximizes the expected discounted long-term reward, which can be modeled by a Markov decision process (MDP). In an MDP, the optimal value function is the fixed point of the Bellman operator. Thus, the optimal value function can be computed by iterative updates from arbitrary initial value function, i.e., value iteration (Bellman (2013) ). Littman & Szepesvári (1996) proposed the generalized MDP considering generalized action selection operators, according to which the value function is estimated. If the generalized action selection operator satisfies the non-expansion property, the uniqueness of the fixed-point of the generalized Bellman operator is guaranteed, thus ensuring the convergence of generalized value iteration algorithm. Examples of non-expansive operators include the max and the mean operators.

Without full information about transition dynamics and reward function of the environment, in reinforcement learning, the agent aims to learn an optimal policy by interacting with the unknown environment from experience. Reinforcement learning has achieved groundbreaking success for many decision making problems, both in discrete and continuous domains, including robotics (Kober et al. (2013) ), game playing (Mnih et al. (2015) ), and many others. One of the most fundamental challenges is how to balance exploration and exploitation, where the exploration-exploitation dilemma occurs in action selection and value function optimization (Asadi & Littman (2016) ). For value function optimization, the agent estimates the value function according to the action selection operator and then updates the estimated value. A number of effective algorithms to address explorationexploitation dilemma have their root in alternating the action selection operator, which falls in the generalized MDP framework.

One of the most important reinforcement learning algorithm, Q-learning, employs the the max operator for value function optimization. The max operator always greedily selects the action that gives the best value and updates current estimation according to the value. As the current estimation for value functions is not accurate, such greedy selection may lead to misbehavior, e.g., the overesti-mation phenomenon (Hasselt (2010) ). In fact, the max operator is the extreme case of exploitation, lacking the ability to explore or consider other choices. On the other hand, the mean operator estimates the value by computing the average. Thus, the mean operator solely explores which fails to utilize current estimation.

The Boltzmann softmax operator is a natural summary operator that has been widely applied (Cesa-Bianchi et al. (2017) ). Specifically, it is an exponentially weighting scheme, where the weights are computed according to the current estimation and its parameter β. The parameter β trades off between exploration and exploitation. When β → ∞, it behaves as the max operator which solely favors exploitation while it behaves as the mean operator when β → 0 which purely focuses on exploration. However, despite from the advantages, it is very challenging to apply the operator in value function optimization. First, the parameter β is difficult to choose (Sutton et al. (1998) ). Second, as shown in (Littman & Szepesvári (1996) ; Asadi & Littman (2016) ), the Boltzmann softmax operator is not a non-expansion, which may lead to multiple fixed-points and thus the value function of this policy is not well-defined. The non-expansive property is vital to guarantee the uniqueness of the fix-point and the convergence of the learning algorithm. Without such property, the learning algorithm may misbehave or even diverge. Thus, it is widely believed that the Boltzmann softmax operator cannot be used directly due to the violation of the non-expansive property (Littman & Szepesvári (1996) ; Asadi & Littman (2016) ). In fact, as far as we know, how to characterize the use of the Boltzmann softmax operator, which violates the property of non-expansion in value iteration, remains an open problem (Littman (1996) ).

In this paper, we study the property of the Boltzmann softmax operator and propose a new technique to characterize its error bound in value iteration with fixed parameter β. To be specific, we show that for the error bound between the value function induced by the Boltzmann softmax operator and the optimal value function, there remains a term related to β that will not converge to 0. Thus, although the Boltzmann softmax operator guarantees the approximate convergence of value iteration, it would converge to a sub-optimal policy unfortunately. Indeed, the direct use of the Boltzmann softmax operator inevitably introduces performance drop in value iteration.

We then take a step further and study an essential problem, is there a way that the Boltzmann softmax operator be applied in value iteration which guarantees the convergence to the optimal policy? Based on this technique, we propose the dynamic Boltzmann softmax operator boltz βt , termed the DBS operator, to eliminate the loss and enable the convergence of value iteration to the optimal value function. Our core idea is to dynamically change β t in value iteration and present its convergence rate analysis. Then, we propose the DBS Q -learning algorithm with the application of the DBS operator in a popular model-free reinforcement learning algorithm, i.e., Q-learning (Watkins & Dayan (1992) ), and prove the convergence of the DBS Q-learning.

We conduct experiments to verify the effectiveness and efficiency of our proposed dynamic Boltzmann softmax operator. We first evaluate DBS value iteration and DBS Q-learning on a tabular case, the GridWorld. Results show that the DBS operator leads to smaller error and faster convergence. We then demonstrate that the DBS operator can be extended to large scale problems, Atari games. Using DQN as baseline, we show that DQN with the dynamic Boltzmann softmax operator (abbreviated as DBS-DQN) substantially outperforms DQN in a suite of Atari benchmark games.

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) represents the transition probability from state s to state s under action a, and r(s, a) is the corresponding immediate reward. The discount factor is denoted by γ ∈ [0, 1), which controls the degree of importance of future rewards.

At each time, 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 r t |π], which can be solved by estimating value functions. The state value of s and state-action value of s and a under policy π are defined as

V π (s) = E π [ ∞ t=0 γ t r t |s 0 = s] and Q π (s, a) = E π [ ∞ t=0 γ t r t |s 0 = s, a 0 = a].

The optimal value functions are defined as

V * (s) = max π V π (s) and Q * (s, a) = max π Q π (s, a).

Littman & Szepesvári (1996) proposed a general framework for reinforcement learning, where the generalized action selection operator is denoted by . The optimal value function V * satisfies the generalized Bellman equation, which is defined recursively as in Equation (1):

EQUATION

Starting from arbitrary initial value function V 0 , the optimal value function V * can be computed by value iteration (Bellman (2013) ) according to an iterative update: V k+1 = T V k , where T is the generalized the Bellman operator as defined in Equation ( 2).

EQUATION

The convergence of value iteration is guaranteed if is a non-expansion, which guarantees the unique solution of the generalized Bellman equation (1), i.e., T V * = V * . The non-expansion is defined as:

EQUATION

where

|| • || ∞ denotes the ∞ -norm.

The Boltzmann softmax operator is one kind of the action selection operator , which is defined as:

boltz β (X) = n i=1 x i e βxi n i=1 e βxi .

(4)

3. ANALYSIS OF THE BOLTZMANN SOFTMAX OPERATOR:

In this section, we first analyze the property of the Boltzmann softmax operator and then propose a new technique to analyze its error bound in value iteration.

It has been shown that the Boltzmann softmax operator is not a non-expansion ((Littman & Szepesvári (1996) ; Asadi & Littman (2016) )) as it does not satisfy Inequality (3). Indeed, the non-expansive property is vital to the convergence of the learning algorithm, which guarantees the uniqueness of the fixed point. We first analyze the property of the Boltzmann softmax operator, which paves the path for studying the effect of using such operators that violates the non-expansive property in value iteration.

Proposition 1 For β > 0 and X, Y ∈ R n , the Boltzmann softmax operator satisfies the following property:

EQUATION

where

• ∞ is the ∞ -norm in R n .

In Proposition 1, we show that although the Boltzmann softmax operator is not a non-expansive operator, the degree of the violation of the non-expansive property is controlled by β. The larger the value of β is, the closer it is to the non-expansion. Due to space limit, we put the proof of Proposition 1 in Appendix A.

Next, we propose a new technique to characterize the error bound of value iteration with Boltzmann softmax operator in value iteration, where the full proof is referred to Appendix B.

Theorem 1 (Error bound of value iteration with Boltzmann softmax operator) Let V t be the value function computed by the Boltzmann softmax operator at the t-th iteration and V 0 denote the initial value. After t iterations,

EQUATION

Taking the limit of t in both sides of Inequality ( 6), we obtain the following result:

Corollary 1 For the Boltzmann softmax operator boltz β , the error of value functions is

lim t→∞ ||V t+1 -V * || ≤ 4 log(|A|) β(1-γ) .

Corollary 1 characterizes the error bound of value iteration with the Boltzmann softmax operator. With a fixed parameter β, the error is upper bounded by 4 log(|A|) β(1-γ) , which decreases with an increasing value of β. Thus, the direct use of the Boltzmann softmax operator inevitably introduces performance drop in practice. Motivated by the theoretical findings, we propose the dynamic Boltzmann softmax operator, which enables the convergence to the optimal.

4. DYNAMIC BOLTZMANN SOFTMAX OPERATOR:

In this section, we propose the dynamic Boltzmann softmax (DBS) operator boltz βt to eliminate the error in value iteration. Next, we give theoretical analysis of the proposed DBS value iteration algorithm. We prove that it converges to the optimal policy if β t approaches ∞, as shown in Theorem 2. We then present the convergence rate analysis in Theorem 3. Finally, we show that the DBS operator can be applied in a prominent model-free reinforcement learning algorithm, Q-learning, with convergence guarantee.

From Corollary 1, although the Boltzmann softmax operator can converge, it may suffer from error due to the violation of the non-expansive property. We propose the dynamic Boltzmann softmax (DBS) operator to eliminate the error, which is motivated by Corollary 1 that although boltz β is not a non-expansive operator, it performs very close to the non-expansion when β is large enough.

Based on the DBS operator, we design the corresponding DBS value iteration algorithm. DBS value iteration algorithm admits a dynamically changing series {β t } (line 1) and update the value function according to the dynamic Boltzmann softmax operator boltz βt (line 6). Thus, the way to update the value function is according to the exponential weighting scheme, which is related to both the current estimation value and the parameter β t .

Algorithm 1: DBS Value Iteration:

Input: An increasing series {βt}; termination condition θ 1 Initialize V (s), ∀s ∈ S arbitrarily 2 for each episode t = 1, 2, ...

do 3 ∆ ← 0 4 for each s ∈ S do 5 v ← V (s) 6 V (s) ← boltz β t s ,r p(s , r|s, a)[r + γV (s )] 7 ∆ ← max(∆, |v -V (s)|) 8 if ∆ < θ then 9 break 4.1 CONVERGENCE ANALYSIS

In Theorem 2, we demonstrate that the DBS operator can enable the convergence of DBS value iteration to the optimal. Due to space limit, see Appendix C for proof of the theorem.

Theorem 2 (Convergence of value iteration with the DBS operator) For a sequence of dynamic Boltzmann softmax operator {β t }, if β t → ∞, V t converges to V * , where V t and V * denote the value function after t iterations and the optimal value function.

Theorem 2 implies that DBS value iteration does converge to the optimal policy if β t approaches infinity. Although the Boltzmann softmax operator may violate the non-expansive property for some values of β, we only need β approaches infinity to guarantee the convergence.

The convergence rate of the DBS operator is shown in Theorem 3, where the proof is provided in Appendix C.

Theorem 3 (Convergence rate of value iteration with the DBS operator) For any power series β t = t p (p > 0), we have that for any ∈ (0, min{0.25, ||R|| -1 }), after

max{O log( 1 +log( 1 1-γ ) log( 1 γ ) ), O ( 1 (1-γ) ) 1 p } steps, the error ||V t -V * || ≤ .

For the larger value of p, the convergence rate is faster. Note that when p approaches ∞, the convergence bound is dominated by the first term.

From the above theoretical analysis of the DBS operator, we demonstrate that value iteration can still converge to the optimal even with an operator violating the non-expansive property. Such finding generalizes previous understanding of the convergence of value iteration, which is restricted to a class of non-expansive operators. In addition, the convergence rate is of the same order as the standard Bellman operator. This implies that the DBS operator will not lose too much in terms of the convergence rate in value iteration. These findings provide theoretical background and pave the way for the study of the use of the DBS operator in reinforcement learning algorithms, e.g., Qlearning, which does not have full information about the model. In the absence of full information about the model, the agent has to explores in the environment and exploits the optimal strategy.

4.2. APPLICATION: Q-LEARNING:

In this section, we show that the DBS operator can be applied in a model-free Q-learning algorithm (Algorithm 9), which requires careful trade-off between exploration and exploitation.

The DBS Q-learning updates the Q-value according to the DBS operator, where it admits a dynamically changing series β t . It is worth noting that in Theorem 3, the larger value of p results in faster convergence rate in value iteration. However, this is not the case in Q-learning. Indeed, Q-learning differs from value iteration in that it knows nothing about the environment, which means the agent has to learn from experience. Thus, the agent needs to balance between exploration and exploitation.

If p is too large, it quickly approximates the max operator that favors pure exploitation. 

Q(s, a) ← Q(s, a) + α[r + γboltz β t (Q(s, •)) -Q(s, a)] 9 s ← a

In Theorem 4, we prove that DBS Q-learning converges to the optimal policy under the same additional condition as in DBS value iteration. The proof is based on the stochastic approximation lemma in (Singh et al. (2000) ), and the full proof is referred to Appendix E.

Theorem 4 (Convergence of DBS Q-learning) The Q-learning algorithm with dynamic Boltzmann softmax policy given by Note that different from value iteration, Q-learning does not know the full information about the model and has to learn from experience. Thus, it is vital to trade-off exploration and exploitation. Unlike the max operator, the DBS operator enables exploration in the begining of learning with a small value of β t . Since the estimated value function is not accurate in the begining of learning, it is better to weight possible choices according to the current estimation rather than greedily selecting the maximum estimated value. The DBS favors exploitation more as β t increases, meaning that it is able to utilize the information of current estimation.

EQUATION

5. EXPERIMENTS:



5.1. GRIDWORLD:

We first evaluate the performace of DBS value iteration DBS Q-learning in a toy problem, the GridWorld (Figure 1 (a)), which is a larger variant of the environment of (O'Donoghue et al. ( 2016)).

The GridWorld consists of 10 × 10 grids, 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. An episode ends if 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.

The training loss of value iteration is shown in Figure 2 (a). As expected, larger value of β leads to smaller loss. Figure 2 (b) and Figure 2 (c) demonstrate the training loss in logarithmic form for the last episode. For static β, the value iteration algorithm suffers from some loss which decreases as β increases. For dynamic β t , the performance of t 2 and t 3 are the same and achieve the smallest loss. The convergence rate is illustrated in Figure 2 (d). For higher order p of β t = t p , the convergence rate is faster. We also see that the convergence rate of t 2 and t 10 is very close as discussed before.

Figure 1 (b) demonstrates the number of steps the agent spent in each episode. DBS Q-learning with β t = t 2 achieves the best performance as it best trades off between exploration and exploitation. When the power p of β t = t p increases, it performs closer to the max operator for exploitation. When p = 1, it performs worse than Q-learning in this simple game as it explores more. Thus, considering trading off between exploration and exploitation, we choose p = 2 in the following experiments. 2013)) 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. Note that DBS-DQN estimates the value for the next state according to the DBS operator, where β t = ct 2 and c is the coefficient. See Appendix F for full implementation details. For each game, we train each algorithm for 50M steps. The evaluation procedure is identical to Mnih et al. (2015) , 30 no-op evaluation, where the agent performs a random number (up to 30) of "do nothing" actions in the beginning of an episode.

Table 1 shows the summary of results in human normalized score, which is defined as (Van Hasselt et al. (2016)) :

EQUATION

where human score and random score are taken from Wang et al. (2015) . As illustrated in Table 1 , DBS-DQN significantly outperforms DQN in terms of both the mean and the median of the human normalized score. To better characterize the effectiveness of DBS-DQN, its improvement over DQN is shown in Figure 3 , where the improvement is defined as the relative human normalized score:

EQUATION

with DQN serving as the baseline. In all, DBS-DQN exceeds the performace of DQN in 33 out of 49 Atari games. Full scores of comparison is referred to Appendix G. Figure 4 shows the learning curves for each algorithm. The results provide emprical evidence that the DBS operator trades-off well exploration and exploitation in value function optimization.

6. RELATED WORK:

In reinforcement learning, avoiding the exploration-exploitation dilemma is a vital task. The Boltzmann softmax operator is a popular way to balance exploration and exploitation by exponentially weighting its current estimation (Kaelbling et al. (1996) ). To address the problem, a line of research focuses on the exploration strategy where the agent should exploit current best action on the one hand, but it needs to explore whether there are better possibilities on the other hand. (Singh et al. (2000) ) studied the convergence of on-policy algorithm, i.e., Sarsa. They show that the strategy needs to be greedy in the limit, which guarantees that the optimal action can be selected. Although they considered a dynamic parameter of β in the Boltzmann softmax operator, it depends on the state, which is impractical in complex problems as Atari games. The other line studies the use of alternative operators in value function estimation. To better trade-off between exploration and exploitation, Asadi & Littman (2016) proposed the "Mellowmax" operator, where the degree of exploration and exploitation is controlled by its parameter. However, although the "Mellowmax" operator can approximate maximization in the limit, it converges to a sub-optimal policy rather than the optimal policy. Haarnoja et al. (2017) utilized the log-sum-exp operator, which enables better exploration and learns deep energy-based policies.

It is worth noting that meta learning cannot be applied to solve the problem since the Boltzmann softmax operator with a fixed parameter would inevitably lead to error in value iteration, so there is no optimal value of β.

7. CONCLUSION:

We provide a new theoretical technique to analyze the error bound of the value iteration algorithm with the Boltzmann softmax operator. Then, we develop the DBS value iteration algorithm based on our proposed dynamic Boltzmann softmax (DBS) operator which enables convergence to the optimal value function and present convergence rate analysis. We show that the DBS operator can be applied in a model-free reinforcement learning algorithm, Q-learning. Experimental results demonstrate the effectiveness of the DBS operator and show that it can be extended to complex problems as Atari games. For future work, it is worth studying the sample complexity of our proposed DBS Qlearning algorithm. It is also a promising direction to apply the DBS operator to other state-of-the-art DQN-based algorithms, such as Rainbow (Hessel et al. (2017) ).

A PROPERTY OF THE BOLTZMANN SOFTMAX OPERATOR:

Proposition 1 For β > 0 and X, Y ∈ R n , the Boltzmann softmax operator satisfies the following property:

EQUATION

)

where • ∞ is the ∞ -norm in R n .

Proof 1 Let L β denote a log-sum-exp function, i.e., L β (X) = 1 β log(

n i=1 e βxi ) |boltz β (X) -boltz β (Y)| = |(boltz β (X) -L β (X)) -(boltz β (Y) -L β (Y)) + (L β (X) -L β (Y))| ≤ |boltz β (X) -L β (X)| + |boltz β (Y) -L β (Y)| + |L β (X) -L β (Y)| (11) From MacKay & Mac Kay (2003), we have |boltz β (X) -L β (X)| ≤ log(|X|) β

Substitute the above inequality into Equation ( 11), we have )

EQUATION

Let ∆ i = |x i -y i |

EQUATION

So we have

EQUATION

B ERROR BOUND OF THE BOLTZMANN SOFTMAX OPERATOR Theorem 1 (Error bound of value iteration with Boltzmann softmax operator) Let V t be the value function computed by the Boltzmann softmax operator at the t-th iteration and V 0 denote the initial value. After t iterations,

||V t -V * || ∞ ≤ γ t ||V 0 -V * || ∞ + 4 log(|A|)(1-γ t ) β(1-γ)

.

Proof 2 Let T β and T m denote the dynamic programming operators for the Boltzmann softmax operator boltz β and the max operator respectively, so

EQUATION

For the term (A), we have

||(T β V 1 ) -(T βt V 2 )|| ∞ = max s |boltz β (Q 1 (s, •)) -boltz β (Q 2 (s, •))| ≤ max s max a |Q 1 -Q 2 | + 2 log(|A|) β ≤ max s max a γ s p(s |s, a)|V 1 (s ) -V 2 (s )| + 2 log(|A|) β ≤ γ||V 1 -V 2 || ∞ + 2 log(|A|) β (17)

For the term (B), we have

EQUATION

Thus,

EQUATION

As for the max operator, T m is a contraction mapping, then from Banach fixed-point theorem we have T m V * = V * Let T t b denote the dynamic programming operator for a sequence of Boltzmann softmax operators, then we have

EQUATION

C CONVERGENCE OF DBS VALUE ITERATION:

Theorem 2 (Convergence of value iteration with the DBS operator) For a sequence of dynamic Boltzmann softmax operator {β t }, if β t → ∞, V t converges to V * , where V t and V * denote the value function after t iterations and the optimal value function.

Proof 3 Let T βt and T m denote the dynamic programming operators for dynamic Boltzmann softmax operator boltz βt and the max operator respectively, so

(T βt V )(s) = boltz βt (Q(s, •)), (T m V )(s) = max(Q(s, •))

. Thus, we have

EQUATION

By similar techniques as in Theorem 6, we have

EQUATION

As the max operator T m is a contraction mapping, then from Banach fixed-point theorem we have T m V * = V * Let T t b denote the dynamic programming operator for a sequence of dynamic Boltzmann softmax operators, so T t b = T βt T βt-1 ...T β1 , then we have

||V t -V * || ∞ = ||T t b V 0 -T t m V * || ∞ = ||(T βt ...T β1 )V 0 -(T m ...T m )V * || ∞ ≤ γ||(T βt-1 ...T β1 )V 0 -(T m ...T m )V * || ∞ + 4 log(|A|) β t ≤ ... ≤ γ t ||V 0 -V * || ∞ + 4 log(|A|) t k=1 γ t-k β k (23) Since lim k→∞ 1 β k = 0, we have that ∀ 1 > 0, ∃K > 0, such that ∀k > K, | 1 β k | < 1 . Thus, t k=1 γ t-k β k = K( 1) k=1 γ t-k β k + t k=K( 1)+1 γ t-k β k ≤ 1 min β K( 1) k=1 γ t-k + 1 t k=K( 1)+1 γ t-k = 1 min β γ t-K( 1) (1 -γ K( 1) ) 1 -γ + 1 1(1 -γ t-K( 1 ) ) 1 -γ ≤ 1 1 -γ γ t-K( 1 ) min β + 1 (24) If t > log(( 2(1-γ)-1 ) min β) log γ + K( 1 ) and 1 < 2 (1 -γ), then t k=1 γ t-k β k < 2 .

So we obtain that ∀ 2 > 0, ∃T > 0, such that ∀t > T,

| t k=1 γ t-k β k | < 2 .

Thus, lim t→∞ t k=1 γ t-k β k = 0. Taking the limit of Equation ( 23), we have that

EQUATION

D CONVERGENCE BOUND:

Theorem 3 (Convergence rate of value iteration with the DBS operator) For any power series β t = t p (p > 0), we have that for any ∈ (0, min{0.25, ||R|| -1 }), after

max{O log( 1 +log( 1 1-γ ) log( 1 γ ) ), O ( 1 (1-γ) ) 1 p } steps, the error ||V t -V * || ≤ . Proof 4 t k=1 γ t-k k p = γ t ∞ k=1 γ -1 k p - ∞ k=t+1 γ -1 k p = γ t Li p (γ -1 )

Polylogarithm -γ -(t+1) Φ(γ -1 , p, t + 1) Proof 5 Let ∆ t (s, a) = Q t (s, a) -Q * (s, a) and F t (s, a) = r t + γboltz βt (Q t (s t+1 , •)) -Q * (s, a) Thus, from (29) we have ∆ t+1 (s, a) = (1 -α t (s, a))∆ t (s, a) + α t (s, a)F t (s, a), which has the same form as the process defined in Lemma 2.

Next, we verify F t (s, a) meets the required properties. 

F t (s, a) = r t + γboltz βt (Q t (s t+1 , •)) -Q * (

:



Figures and Tables:

DBS Q-learning Input: An increasing series {βt} 1 Initialize Q(s, a), ∀s ∈ S, a ∈ A arbitrarily, and Q(terminal)-(state, •) = 0 2 for each episode t = 1, 2, ... do 3 Initialize s 4 βt = f (t) 5 for each step of episode do 6 choose a from s using policy derived from Q 7 take action a, observe r, s 8

converges to the optimal Q * (s, a) values if 1. The state and action spaces are finite.2.t α t (s, a) = ∞ and t α 2 t (s, a) < ∞ 3. lim t→∞ β t = ∞ 4. Var(r(s, a)) is bounded.

learning ( t = t) DBS Q-learning ( t = t2) DBS Q-learning ( t = t3) DBS Q-learning ( t = t7) (b) Results of Q-learning.

Figure 1: The grid world experiment.

Figure 2: Value iteration in the GridWorld.

Figure 3: Relative human normalized score on Atari games.

Figure 4: Learning curves in Atari games.

Summary of Atari games.

Table content: <table><tr><td/><td>Mean</td><td>Median</td></tr><tr><td>DQN</td><td>495.76%</td><td>84.72%</td></tr><tr><td colspan="3">DBS-DQN 1611.49% 103.95%</td></tr></table>

From Theorem 2 we have||V t -V * || ≤ γ t ||V 1 -V * || + 4 log(|A|) (1 -γ)(t + 1) p ≤ 2 max{γ t ||V 1 -V * ||, 4 log(|A|) (1 -γ)(t + 1) p } (28)Thus, for any > 0, after at most t = max{ CONVERGENCE OF DBS Q-LEARNING Theorem 4 (Convergence of DBS Q-learning) The Q-learning algorithm with dynamic Boltzmann softmax policy given byQ t+1 (s t , a t ) = (1 -α t (s t , a t ))Q t (s t , a t ) + α t (s t , a t )[r t + γboltz βt (Q t (s t+1 , •))](29) converges to the optimal Q * (s, a) values if 1. The state and action spaces are finite. 2. t α t (s, a) = ∞ and t α 2 t (s, a) < ∞ 3. lim t→∞ β t = ∞ 4. Var(r(s, a)) is bounded.

Table content: <table><tr><td colspan="3">log( 1 )+log( 1 1-γ )+log(||R||)+log(4) log( 1 γ )</td><td>, 8 log(|A|) (1-γ)</td><td>1 p -1}</td></tr><tr><td>steps, we have ||V</td><td/><td/><td/></tr><tr><td/><td/><td/><td/><td>(26)</td></tr><tr><td/><td colspan="2">Lerch transcendent</td><td/></tr><tr><td>By Ferreira &amp; López (2004), we have</td><td/><td/><td/></tr><tr><td>Eqaution(26) ≈ γ t γ -(t+1) γ -1 -1</td><td>1 (t + 1) p =</td><td>1 (1 -γ)(t + 1) p</td><td/><td>(27)</td></tr></table>

For G t , it is indeed the F t function as that in Q-learning with static exploration parameters, which satisfies||E[G t (s, a)]|P t || w ≤ γ||∆ t || Let h t = 2γ log(|A|)

Table content: <table><tr><td>≤</td><td>γ log(|A|) β t</td><td>+ γ max s</td><td>|</td><td>1 β t</td><td>log( a ∈A</td><td>e βtQt(s ,a ) ) -max a</td><td>Q t (s , a )|</td></tr><tr><td>≤</td><td colspan="2">2γ log(|A|) β t</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>(32)</td></tr></table>

Peer review (iclr2019):
 Summary: This work demonstrates that, although the Boltzmann softmax operator is not a non-expansion, a proposed dynamic Boltzmann operator (DBS) can be used in conjunction with value iteration and Q-learning to achieve convergence to V* and Q*, respectively. This time-varying operator replaces the traditional max operator. The authors show empirical performance gains of DBS+Q-learning over Q-learning in a gridworld and DBS+DQN over DQN on Atari games. Novelty: (1) The error bound of value iteration with the Boltzmann softmax operator and convergence & convergence rate results in this setting seem novel. (2) The novelty of the dynamic Boltzmann operator is somewhat thin, as (Singh et al. 2000) show that a dynamic weighting of the Boltzmann operator achieves convergence to the optimal value function in SARSA(0). In that work, the weighting is state-dependent, so the main algorithmic novelty in this paper is removing the dependence on state visitation for the beta parameter by making it solely dependent on time. A question for the authors: How does the proof in this work relate to / differ from the convergence proofs in (Singh et al. 2000)? Clarity: In the DBS Q-learning algorithm, it is unclear under which policy actions are selected, e.g. using epsilon-greedy/epsilon-Boltzmann versus using the Boltzmann distribution applied to the Q(s, a) values. If the Boltzmann distribution is used then the algorithm that is presented is in fact expected SARSA and not Q-learning. The paper would benefit from making this clear. Soundness: (1) The proof of Theorem 4 implicitly assumes that all states are visited infinitely often, which is not necessarily true with the given algorithm (if the policy used to select actions is the Boltzmann policy). (2) The proof of Theorem 1 uses the fact that |L(Q) - max(Q)| <= log(|A|) / beta, which is not immediately clear from the result cited in McKay (2003). (3) The paper claims in the introduction that “the non-expansive property is vital to guarantee … the convergence of the learning algorithm.” This is not necessarily the case -- see Bellemare et al., Increasing the Action Gap: New Operators for Reinforcement Learning, 2016. Quality: (1) I appreciate that the authors evaluated their method on the suite of 49 Atari games. This said, the increase in median performance is relatively small, the delta being about half that of the increase due to double DQN. The improvement in mean score in great part stems from a large improvement occurs on Atlantis. There are also a number of experimental details that are missing. Is the only change from DQN the change in update rule, while keeping the epsilon-greedy rule? In this case, I find a disconnect between the stated goal (to trade off exploration and exploitation) and the results. Why would we expect the Boltzmann softmax to work better when combined to epsilon-greedy? If not, can you give more details e.g. how beta was annealed over time, etc.? Finally, can you briefly compare your algorithm to the temperature scheduling method described in Fox et al., Taming the Noise in Reinforcement Learning via Soft Updates, 2016? Additional Comments: (1) It would be helpful to have Atari results provided in raw game scores in addition to the human-normalized scores (Figure 5). (2) The human normalized scores listed in Figure 5 for DQN are different than the ones listed in the Double DQN paper (Van Hasselt et al, 2016). (3) For the DBS-DQN algorithm, the authors set beta_t = ct^2 - how is the value of c determined? (4) Text in legends and axes of Figure 1 and Figure 2 plots is very small. (5) Typo: citation for MacKay - Information Theory, Inference and Learning Algorithms - author name listed twice. Similarly, if the main contribution is DBS, it would be interesting to have a more in-depth empirical analysis of the method -- how does performance (in Atari or otherwise) vary with the temperature schedule, how exploration is affected, etc.? After reading the other reviews and responses, I still think the paper needs further improvement before it can published.