Year: 2018

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 GridWorld and a suite of Atari games. Experimental results show that outperforms DQN substantially in benchmark games.

heading: 1 INTRODUCTION
text: 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 & Szepesvá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 (CesaBianchi 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 & Szepesvá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 & Szepesvá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.

heading: 2 PRELIMINARIES
text: 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 γ
trt|π], 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 γ
trt|s0 = s] and Qπ(s, a) = Eπ[ ∑∞ t=0 γ
trt|s0 = s, a0 = a]. The optimal value functions are defined as V ∗(s) = maxπ V π(s) and Q∗(s, a) = maxπ Qπ(s, a).
Littman & Szepesvá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):
V ∗(s) = ⊗ a∈A [ r(s, a) + ∑ s′∈S p(s′|s, a)γV ∗(s′) ]
(1)
Starting from arbitrary initial value function V0, the optimal value function V ∗ can be computed by value iteration (Bellman (2013)) according to an iterative update: Vk+1 = T Vk, where T is the generalized the Bellman operator as defined in Equation (2).
(T V )(s) = ⊗ a∈A [ r(s, a) + ∑ s′∈S p(s′|s, a)γV (s′) ] . (2)
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: ∣∣⊗
a Q1(s, a)− ⊗ a Q2(s, a) ∣∣ ≤ ||Q1(s, ·)−Q2(s, ·)||∞, (3)
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 xie
βxi∑n i=1 e βxi . (4)

heading: 3 ANALYSIS OF THE BOLTZMANN SOFTMAX OPERATOR
text: 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 & Szepesvá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 ∈ Rn, the Boltzmann softmax operator satisfies the following property:
|boltzβ(X)− boltzβ(Y)| ≤ ||X−Y||∞ + 2 log(n)
β , (5)
where ‖ · ‖∞ is the `∞-norm in Rn.
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 Vt be the value function computed by the Boltzmann softmax operator at the t-th iteration and V0 denote the initial value. After t iterations,
||Vt − V ∗||∞ ≤ γt||V0 − V ∗||∞ + 4 log(|A|)(1− γt)
β(1− γ) . (6)
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 limt→∞ ||Vt+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.

heading: 4 DYNAMIC BOLTZMANN SOFTMAX OPERATOR
text: 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

heading: 4.1 CONVERGENCE ANALYSIS
text: 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 → ∞, Vt converges to V ∗, where Vt 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 = tp(p > 0), we have that for any ∈ (0,min{0.25, ||R||−1}), after max{O ( log( 1 )+log( 11−γ )
log( 1γ ) ), O
( ( 1(1−γ) ) 1 p ) } steps, the error ||Vt − 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.

heading: 4.2 APPLICATION: Q-LEARNING
text: 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.
Algorithm 2: 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 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
Qt+1(st, at) = (1− αt(st, at))Qt(st, at) + αt(st, at)[rt + γboltzβt(Qt(st+1, ·))] (7)
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. limt→∞ βt =∞
4. Var(r(s, a)) is bounded.
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.

heading: 5 EXPERIMENTS

heading: 5.1 GRIDWORLD
text: 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 t2 and t3 are the same and achieve the smallest loss. The convergence rate is illustrated in Figure 2(d). For higher order p of βt = tp, the convergence rate is faster. We also see that the convergence rate of t2 and t10 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 = tp 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.

heading: 5.2 ATARI
text: We evaluate the DBS-DQN algorithm on 49 Atari games from the Arcade Learning Environment (Bellemare et al. (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)):
scoreagent − scorerandom scorehuman − scorerandom × 100%, (8)
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:
scoreagent − scorebaseline max{scorehuman, scorebaseline} − scorerandom × 100%, (9)
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.

heading: 6 RELATED WORK
text: 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 β.

heading: 7 CONCLUSION
text: 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)).

heading: A PROPERTY OF THE BOLTZMANN SOFTMAX OPERATOR
text: Proposition 1 For β > 0 and X,Y ∈ Rn, the Boltzmann softmax operator satisfies the following property:
|boltzβ(X)− boltzβ(Y)| ≤ ||X−Y||∞ + 2 log(n)
β , (10)
where ‖ · ‖∞ is the `∞-norm in Rn.
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
|boltzβ(X)− boltzβ(Y)| ≤ 2 log(n) β + | 1 β log( n∑ i=1 eβxi)− 1 β log( n∑ i=1 eβyi)|
= 2 log(n)
β +
1
β ∣∣ log(∑ni=1 eβxi∑n i=1 e βyi ) ∣∣ (12)
Let ∆i = |xi − yi| and assume ∑n i=1 e βxi ≥ ∑n i=1 e βyi without loss of generality. Then, we have
1
β ∣∣ log(∑ni=1 eβxi∑n i=1 e βyi ) ∣∣ ≤ 1 β ∣∣ log(∑ni=1 eβ(yi+∆i)∑n i=1 e βyi ) ∣∣
≤ 1 β ∣∣ log(∑ni=1 eβ(yi+||∆i||∞)∑n i=1 e βyi ) ∣∣ ≤ ||∆i||∞ = ||x− y||∞
(13)
So we have
|boltzβ(X)− boltzβ(Y)| ≤ 2 log(n)
β + ||x− y||∞ (14)

heading: B ERROR BOUND OF THE BOLTZMANN SOFTMAX OPERATOR
text: Theorem 1 (Error bound of value iteration with Boltzmann softmax operator) Let Vt be the value function computed by the Boltzmann softmax operator at the t-th iteration and V0 denote the initial value. After t iterations, ||Vt − V ∗||∞ ≤ γt||V0 − V ∗||∞ + 4 log(|A|)(1−γ t) β(1−γ) .
Proof 2 Let Tβ and Tm denote the dynamic programming operators for the Boltzmann softmax operator boltzβ and the max operator respectively, so
(TβV )(s) = boltzβ(Q(s, ·)), (TmV )(s) = max(Q(s, ·)) (15)
Thus, ||(TβV1)− (TmV2)||∞ ≤ ||(TβV1)− (TβV2)||∞︸ ︷︷ ︸
(A)
+ ||(TβV2)− (TmV2)||∞︸ ︷︷ ︸ (B)
(16)
For the term (A), we have
||(TβV1)− (TβtV2)||∞ = max s |boltzβ(Q1(s, ·))− boltzβ(Q2(s, ·))|
≤ max s max a |Q1 −Q2|+ 2 log(|A|) β
≤ max s max a γ ∑ s′ p(s′|s, a)|V1(s′)− V2(s′)|+ 2 log(|A|) β
≤ γ||V1 − V2||∞ + 2 log(|A|)
β
(17)
For the term (B), we have
||(TβV1)− (TmV1)||∞ = max s |boltzβ(Q1(s, ·))−max(Q1(s, ·))|
≤ max s
[ |boltzβ(Q1(s, ·))− Lβ(Q1(s, ·))|+ |Lβ(Q1(s, ·))−max(Q1(s, ·))| ] ≤ 2 log(|A|)
β (18)
Thus,
||(TβV1)− (TmV2)||∞ ≤ γ||V1 − V2||∞ + 4 log(|A|)
β (19)
As for the max operator, Tm is a contraction mapping, then from Banach fixed-point theorem we have TmV ∗ = V ∗
Let T tb denote the dynamic programming operator for a sequence of Boltzmann softmax operators, then we have
||Vt − V ∗||∞ = ||T tb V0 − T tmV ∗||∞
≤ γ||(T t−1b V0 − T t−1 m V ∗||∞ + 4 log(|A|)
β
≤ ...
≤ γt||V0 − V ∗||∞ + 4 log(|A|)
β
t∑ k=1 γt−k
= γt||V0 − V ∗||∞ + 4 log(|A|)(1− γt)
β(1− γ)
(20)

heading: C CONVERGENCE OF DBS VALUE ITERATION
text: Theorem 2 (Convergence of value iteration with the DBS operator) For a sequence of dynamic Boltzmann softmax operator {βt}, if βt → ∞, Vt converges to V ∗, where Vt and V ∗ denote the value function after t iterations and the optimal value function.
Proof 3 Let Tβt and Tm denote the dynamic programming operators for dynamic Boltzmann softmax operator boltzβt and the max operator respectively, so (TβtV )(s) = boltzβt(Q(s, ·)), (TmV )(s) = max(Q(s, ·)). Thus, we have
||(TβtV1)− (TmV2)||∞ ≤ ||(TβtV1)− (TβtV2)||∞︸ ︷︷ ︸ (A) + ||(TβtV2)− (TmV2)||∞︸ ︷︷ ︸ (B)
(21)
By similar techniques as in Theorem 6, we have
||(TβtV1)− (TmV2)||∞ ≤ γ||V1 − V2||∞ + 4 log(|A|)
βt (22)
As the max operator Tm is a contraction mapping, then from Banach fixed-point theorem we have TmV ∗ = V ∗
Let T tb denote the dynamic programming operator for a sequence of dynamic Boltzmann softmax operators, so T tb = TβtTβt−1 ...Tβ1 , then we have
||Vt − V ∗||∞ = ||T tb V0 − T tmV ∗||∞ = ||(Tβt ...Tβ1)V0 − (Tm...Tm)V ∗||∞
≤ γ||(Tβt−1 ...Tβ1)V0 − (Tm...Tm)V ∗||∞ + 4 log(|A|) βt ≤ ... ≤ γt||V0 − V ∗||∞ + 4 log(|A|) t∑
k=1
γt−k
βk
(23)
Since limk→∞ 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, limt→∞ ∑t k=1 γt−k βk = 0.
Taking the limit of Equation (23), we have that
lim t→∞ ||Vt+1 − V ∗||∞ ≤ lim t→∞
[ γt||V1 − V ∗||∞ + 4 log(|A|) t∑ k=1 γt−k βk ] = 0 (25)

heading: D CONVERGENCE BOUND
text: Theorem 3 (Convergence rate of value iteration with the DBS operator) For any power series βt = tp(p > 0), we have that for any ∈ (0,min{0.25, ||R||−1}), after max{O ( log( 1 )+log( 11−γ )
log( 1γ ) ), O
( ( 1(1−γ) ) 1 p ) } steps, the error ||Vt − V ∗|| ≤ .
Proof 4 t∑
k=1
γt−k
kp = γt [ ∞∑ k=1 γ−1 kp − ∞∑ k=t+1 γ−1 kp ]
= γt [
Lip(γ −1)︸ ︷︷ ︸
Polylogarithm −γ−(t+1) Φ(γ−1, p, t+ 1)︸ ︷︷ ︸ Lerch transcendent ] (26) By Ferreira & López (2004), we have
Eqaution(26) ≈ γt γ −(t+1)
γ−1 − 1 1 (t+ 1)p =
1
(1− γ)(t+ 1)p (27)
From Theorem 2 we have
||Vt − V ∗|| ≤ γt||V1 − V ∗||+ 4 log(|A|)
(1− γ)(t+ 1)p ≤ 2 max{γt||V1 − V ∗||, 4 log(|A|) (1− γ)(t+ 1)p } (28)
Thus, for any > 0, after at most t = max{ log( 1 )+log( 1 1−γ )+log(||R||)+log(4) log( 1γ ) , ( 8 log(|A|) (1−γ) ) 1 p − 1} steps, we have ||Vt − V ∗|| ≤ .

heading: E CONVERGENCE OF DBS Q-LEARNING
text: Theorem 4 (Convergence of DBS Q-learning) The Q-learning algorithm with dynamic Boltzmann softmax policy given by
Qt+1(st, at) = (1− αt(st, at))Qt(st, at) + αt(st, at)[rt + γboltzβt(Qt(st+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. limt→∞ βt =∞ 4. Var(r(s, a)) is bounded.
Proof 5 Let ∆t(s, a) = Qt(s, a)−Q∗(s, a) and Ft(s, a) = rt + γboltzβt(Qt(st+1, ·))−Q∗(s, a) Thus, from (29) we have ∆t+1(s, a) = (1 − αt(s, a))∆t(s, a) + αt(s, a)Ft(s, a), which has the same form as the process defined in Lemma 2.
Next, we verify Ft(s, a) meets the required properties. Ft(s, a) = rt + γboltzβt(Qt(st+1, ·))−Q∗(s, a)
= (rt + γmax a+1 Qt(st+1, at+1)−Q∗(s, a)) + γ(boltzβt(Qt(st+1, ·))−max at+1 Qt(st+1, at+1))
∆ = Gt(s, a) +Ht(s, a)
(30)
For Gt, it is indeed the Ft function as that in Q-learning with static exploration parameters, which satisfies
||E[Gt(s, a)]|Pt||w ≤ γ||∆t||w (31)
For Ht, we have |E[Ht(s, a)]| = γ ∣∣∑ s′ p(s′|s, a)[boltzβt(Qt(s′, ·))−max a′ Qt(s ′, a′)] ∣∣ ≤ γ ∣∣max s′ [boltzβt(Qt(s ′, ·))−max a′ Qt(s ′, a′)] ∣∣
≤ γmax s′ ∣∣boltzβt(Qt(s′, ·))−max a′ Qt(s ′, a′) ∣∣ = γmax
s′ ∣∣(boltzβt(Qt(s′, ·))− Lβt(Qt(s′, ·))) + (Lβt(Qt(s′, ·))−max a′ Qt(s ′, a′)) ∣∣ ≤ γmax
s′
( |boltzβt(Qt(s′, ·))− Lβt(Qt(s′, ·))|+ |Lβt(Qt(s′, ·))−max
a′ Qt(s
′, a′)| )
≤ γ log(|A|) βt + γmax s′ | 1 βt log( ∑ a′∈A eβtQt(s ′,a′))−max a′ Qt(s ′, a′)|
≤ 2γ log(|A|) βt
(32)
Let ht = 2γ log(|A|)
βt , so we have
||E[Ft(s, a)]|Pt||w ≤ γ||∆t||w + ht, (33) where ht converges to 0
F IMPLEMENTATION DETAILS
The network architecture is the same as in (Mnih et al. (2015)). The input to the network is a raw pixel image, which is pre-processed into a size of 84 × 84 × 4. Table 2 summarizes the network architecture.

heading: G ATARI SCORES

Review summaries:
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.