From Q(lambda) to Average Q-learning: Efficient Implementation of an Asymptotic Approximation
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 959-963.
© 2001 International Joint Conferences on Artificial Intelligence
Abstract
Q( ) is a reinforcement learning algorithm that combines Q-learning and TD( ). Online implementations of Q( ) that use eligibility traces have been shown to speed basic Q-learning. In this paper we present an asymptotic analysis of Watkins’ Q( ) with accumulative eligibility traces. We first introduce an asymptotic approximation of Q( ) that appears to be a gain matrix variant of basic Qlearning. Using the ODE method, we then determine an optimal gain matrix for Q-learning that maximizes its rate of convergence toward the optimal value function . The similarity between this optimal gain and the asymptotic gain of Q( ) explains the relative efficiency of the latter for . Furthermore, by minimizing the difference between these two gains, optimal values for the parameter and the decreasing learning rates can be determined. This optimal strongly depends on the exploration policy during learning. A robust approximation of these learning parameters leads to the definition of a new efficient algorithm called AQ-learning (Average Q-learning), that shows a close resemblance to Schwartz’ R-learning. Our results have been demonstrated through numerical simulations.
- [Benveniste et al., 1990] A. Benveniste, M. Metivier, and P. Priouret. Adaptive Algorithms and Stochastic Approx- imation. Springer-Verlag, Berlin,New York, 1990.
- [Bertsekas and Tsitsiklis, 1996] D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scien- tific, Belmont (MA), 1996.
- [Borkar and Meyn, 2000] V. S. Borkar and S. P. Meyn. The O.D.E. method for convergence of stochastic approxima- tion and reinforcement learning. SIAM Journal of Control and Optimization, 38:447-469, 2000.
- [Borkar, 1996] V. S. Borkar. Stochastic approximation with two-time scales. System and Control Letters, 29:291-294, 1996.
- [Cichosz, 1995] P. Cichosz. Truncating temporal differ- ences: On the efficient implementation of TD( ) for rein- forcement learning. Journal of Artificial Intelligence Re- search (JAIR), 2:287-318, 1995.
- [Garcia and Ndiaye, 1998] F. Garcia and S. Ndiaye. A Learning Rate Analysis of Reinforcement-Learning Algo- rithms in Finite-Horizon. In International Conference on Machine Learning, volume 15, Madison, USA, 1998.
- [Garcia and Serre, 2000] F. Garcia and F. Serre. Efficient asymptotic approximation in temporal difference learning. In Proceedings of the 14th European Conference on Arti- ficial Intelligence (ECAI 2000), Berlin, 2000.
- [Kearns and Singh, 2000] M. Kearns and S.P. Singh. "bias- Variance" error bounds for temporal difference updates. In Proceedings of the COLT 2000 conference, 2000.
- [Kushner and Yin, 1997] H. J. Kushner and G. G Yin. Stochastic Approximation Algorithms and Applications. Springer, 1997.
- [Peng and Williams, 1994] J. Peng and R. J. Williams. In- cremental Multi-Step Q-Learning. In International Con- ference on Machine Learning, volume 11, pages 226-232, 1994.
- [Puterman, 1994] M. L. Puterman. Markov decision pro- cesses: discrete stochastic dynamic programming. Wiley- Interscience, New York, 1994.
- [Schwartz, 1993] A. Schwartz. A Reinforcement Learning Method for Maximizing Undiscounted Rewards. In In- ternational Conference on Machine Learning, volume 10, 1993.
- [Singh and Dayan, 1998] S. P. Singh and P. Dayan. Analyt- ical Mean Squared Error Curves for Temporal Difference learning. Machine Learning, 1998.
- [Singh and Sutton, 1996] S. P. Singh and R. S. Sutton. Re- inforcement learning with replacing eligibility traces. Ma- chine Learning, 1996.
- [Sutton, 1988] R. S. Sutton. Learning to predict by the meth- ods of temporal differences. Machine Learning, 3:9-44, 1988.
- [Watkins, 1989] C. J. Watkins. Learning from Delayed Re- wards. PhD thesis, Cambridge University, Cambridge, England, 1989.
- [Wiering and Schmidhuber, 1997] M. A. Wiering and J. Schmidhuber. Fast online Q( ). Machine Learning, 1997.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
TD( ✂ ) and Q-learning are undoubtedly two of the most important methods that have been proposed in Reinforcement Learning. Q-learning is a simple direct algorithm for learning optimal policies, and the TD(✂ ) rule is used in many existing reinforcement learning and stochastic dynamic programming algorithms for efficiently evaluating a given policy.
The Q-learning algorithm basically implements the TD(0) update rule. In order to improve the convergence rate of Qlearning, it has been proposed to integrate the TD( ✂ ), ✂ ✝ ✟ , with the Q-learning update rule. That resulted in the family of Q(✂ ) algorithms [Watkins, 1989; Peng and Williams, 1994]. It is commonly believed that Q(✂ ), ✂ ✝ ✟ , improves the Q-learning behaviour, but no definite theoretical analysis of Q( ✂ ) has come in support of this conjecture: there is no proof of convergence for Q(✂ ), and as for TD(✂ ), the issue of the rational choice of ✂ remains [Singh and Dayan, 1998; Kearns and Singh, 2000].
The use of Q(✂ ) is hampered by another important difficulty. Eligibility trace implementations of Q(✂ ) based on look-up tables require many updates of Q-value and trace components after each transition. The time complexity of this approach may be very high for large state and action spaces. In spite of several recent attempts [Cichosz, 1995; Wiering and Schmidhuber, 1997], the multi-component update rule of Q(✂ ) remains problematic.
In this paper we propose a new algorithm that eliminate the above-mentioned shortcoming of Q(✂ ). Our approach relies on an asymptotic approximation of Watkins' Q(✂ ) (section 2 and 3), that appears to be a gain matrix variant of basic Q-learning. Then an optimal convergence rate analysis of Q-learning based on the ODE method leads us to determine an optimal gain matrix for Q-learning (section 4). The similar structure of these two gains explains the relative efficiency of Q(✂ ). Furthermore, by minimizing the difference between these two gains, we are able to determine nearoptimal ✂ and learning rates that allowen efficient implementation of a new reinforcement learning algorithm called AQlearning (average Q-learning), which shows a close resemblance to Schwartz' R-learning [Schwartz, 1993] (section 5). We present in section 6 some experimental results that confirm the soundness of the asymptotic analysis and the nearoptimal behaviour of AQ-learning.
2 The Watkins' Q( ☛ ) algorithm
Like the TD(✂ ) and Q-learning reinforcement learning algorithms, Q(✂ ) can be described within the framework of Markov Decision Processes (MDP) [Puterman, 1994]. Assume a stationary infinite-horizon MDP model that is defined by a state space ☞ of size ✌ ✍ and an action space ✏ of size ✌ ✑ , by aMarkovian dynamics on ☞ characterized by the transition probabilities ✓ ✔ ✖ ✘ ✚ ✖ ✜ ✣ ✥ of moving from ✖ to ✖ ✘ after applying the action ✣ , and by the instantaneous reward functions ★ ✔ ✖ ✜ ✣ ✜ ✖ ✘ ✥ ✭ ✯ ✱ associated to each transition ✔ ✖ ✜ ✣ ✜ ✖ ✘ ✥ .
A policy is a function ✳ ✴ ☞ ✷ ✏ that assigns an action ✣ ✹ ✳ ✔ ✖ ✥ to any possible state ✖ . Given an initial state ✖ ✼ , following a policy ✳ defines a random trajectory ✔ ✖ ✼ ✜ ✣ ✼ ✜ ★ ✼ ✥ ✷ ✔ ✖ ✿ ✜ ✣ ✿ ✜ ★ ✿ ✥ ✷ ❃ ❃ ❃ with ✣ ❅ ✹ ✳ ✔ ✖ ❅ ✥ , ★ ❅ ✹ ★ ✔ ✖ ❅ ✜ ✳ ✔ ✖ ❅ ✥ ✜ ✖ ❅ ❊ ✿ ✥ , according to the probabilities ✓ ✔ ✖ ❅ ❊ ✿ ✚ ✖ ❅ ✜ ✣ ❅ ✥ .
The optimization problem associated to a discounted Marko ❍ v Decision Problem is to find a policy ✳ ☎ that maximizes for any initial state ✖ ✼ the expected sum of the discounted rewards along a trajectory ■ ❏ ✔ ✖ ✼ ✥ ✹ ▲ ◆ a80 ◗ ❅ ❙ ✼ ❚ ❅ ★ ✔ ✖ ❅ ✜ ✳ ✔ ✖ ❅ ✥ ✜ ✖ ❅ ❊ ✿ ✥ ❱ , where ✟ ❲ ❚ ❨ ❬ is the discount factor.
The value function ■ ❏ of a policy ✳ can be directly learnt from observed trajectories by using the TD(✂ ) algorithm, without maintaining an estimation of the transition probabilities ✓ ✔ ✖ ✘ ✚ ✖ ✜ ✳ ✔ ✖ ✥ ✥ [Sutton, 1988]. It is also possible to learn directly an estimation of the optimal value function of the problem with the Q-learning algorithm [Watkins, 1989]. Qlearning regularly updates an estimation ✄ ❫ of the optimal Q-value function denoted by ✄ ☎ :
which is characterized by the optimality equations: ❵ ✖ ✜ ✣
An optimal policy can then be directly derived from ✄ ☎ by ✳ ☎ ✔ ✖ ✥ ✹ a115 ② ④ a113 a115 ✉ ✈ ❢ ✑ ✄ ☎ ✔ ✖ ✜ ✣ ✥ , ❵ ✖ .
The principle of Q( ✂ ) is to combine Q-learning and the temporal difference error used in the TD(✂ ) method, in order to accelerate the convergence of Q-learning. For the discounted value function, the potentially infinite length of the trajectories leads us to consider the Q( ✂ ) methods based on eligibility traces. After each observed transition ✔ ✖ ❫ ✜ ✣ ❫ ✜ ✖ ❫ ❊ ✿ ✜ ★ ❫ ✥ , these algorithms update the estimated value function ✄ ❫ by
where ❹ ❫ ✹ ★ ❫ ❤ ❚ a113 a115 ✉ ✈ ❡ ❢ ✑ ✄ ❫ ✔ ✖ ❫ ❊ ✿ ✜ ✣ ✘ ✥ ❻ ✄ ❫ ✔ ✖ ❫ ✜ ✣ ❫ ✥ is the current temporal difference, ⑩ ❫ ✔ ✖ ✜ ✣ ✥ is the stepsize and ❷ ❫ ✔ ✖ ✜ ✣ ✥ is the eligibility trace.
Usually, stepsizes decay regularly toward 0, or are very small constants. The dynamics of the eligibility trace is more complex. Like in TD( ✂ ), the value ❷ ❫ ✔ ✖ ✜ ✣ ✥ is increased for the pair ✔ ✖ ❫ ✜ ✣ ❫ ✥ , and decays exponentially according to the parameter ✂ ✭ ◆ ✟ ✜ ❬ ❱ for all pairs ✔ ✖ ✜ ✣ ✥ ❼ ✹ ✔ ✖ ❫ ✜ ✣ ❫ ✥ . Following this general principle, several eligibility trace dynamics for Q(✂ ) have been proposed [Watkins, 1989; Peng and Williams, 1994; Singh and Sutton, 1996]. The simplest one, due toWatkins [Watkins, 1989], is directly derived from the accumulative eligibility trace of TD( ✂ ), and has the supplementary effect of resetting to 0 the whole trace vector when the current action ✣ ❫ is not a greedy action, that is ✣ ❫ ❼ ✹ ✣ ☎ ❫ ❾ ✹ a115 ② ④ a113 a115 ✉ ✈ ✄ ❫ ✔ ✖ ❫ ✜ ✣ ✥ . The complete definition of this trace is given by:
Q(✂ ) with accumulative eligibility trace is a direct generalization of Q-learning; Q(0) exactly corresponds to Qlearning, where ✄ ❫ ✔ ✖ ❫ ✜ ✣ ❫ ✥ is the only component updated after each transition. Unlike the convergence of Q-learning that has been proved [Bertsekas and Tsitsiklis, 1996; Borkar and Meyn, 2000], the convergence of Q(✂ ) and its overcoming of Q-learning have only been shown experimentally [Peng and Williams, 1994; Wiering and Schmidhuber, 1997]. In practice, the main drawback of Q( ✂ ) is relative to the update costs of ✄ ❫ and ❷ ❫ that are proportional to the size ✌ ✍ ✌ ✑ of ☞ ➏ ✏ for ✂ ✝ ✟ . For large state-action space problems, the computation time of Q( ✂ ), ✂ ✝ ✟ , can be very high.
3 Asymptotic approximation of Q( ☛ )
In this section we intend to define an asymptotic approximation of Watkins' Q(✂ ) when ✌ ✷ ➑ . The following assumptions are made. At each iteration the action ✣ ❫ is chosen with a semi-uniform exploration policy: a greedy action ✣ ☎ ❫ is selected with a probability ✟ ❨ ➓ ❨ ❬ , or any other action in ✏ is chosen randomly. Asymptotically, when ✄ ❫ has converged toward ✄ ☎ , this process defines a Markov chain ✔ ✖ ❫ ✜ ✣ ❫ ✥ on ☞ ➏ ✏ . We assume that this Markov chain is regular (recurrent, aperiodic, irreducible) and therefore has a unique invariant distribution → ✝ ✟ .
3.1 Asymptotic accumulating trace
Let us consider a trajectory ✔ ✖ ✼ ✜ ✣ ✼ ✜ ★ ✼ ✥ ✷ ✔ ✖ ✿ ✜ ✣ ✿ ✜ ★ ✿ ✥ ✷ ➣ ➣ ➣ ✔ ✖ ❫ ✜ ✣ ❫ ✜ ★ ❫ ✥ obtained by Q(✂ ), such that ✄ ❫ converges toward ✄ ☎ . Generalizing our work developed for TD(✂ ) [Garcia and Serre, 2000], the average asymptotic behaviour of the accumulative trace ❷ ❫ ✔ ✖ ✜ ✣ ✥ on this trajectory can be calculated:
For ➓ ✷ ❬ the formula is similar to the one developed for TD(✂ ). For ➓ ✷ ✟ , the trace is regularly set to 0 or 1, and its average value is equal to the invariant distribution → . In the general case, we can see that the role of the trace ❷ ❫ ✔ ✖ ✜ ✣ ✥ in the update rule (1) is to increase credit of state-action pairs that occur more frequently, particularly when the factor ❬ ❻ ❚ ✂ ➓ is small.
Proposition 1 gives the average asymptotic value of ❷ ❫ ✔ ✖ ✜ ✣ ✥ when ✌ ✷ ➑ . From the update rule (2), we can derive an approximation of the asymptotic expectation of the trace at time ✌ conditioned on the current state-action pair ✔ ✖ ❫ ✜ ✣ ❫ ✥ :
3.2 Asymptotic Q(➩ )
We consider the asymptotic approximation AQ( ✂ ) of Q( ✂ ) obtained by substituting in the Q(✂ ) update rule (1) the trace factor ❷ ❫ ✔ ✖ ✜ ✣ ✥ by its approximation ➞ ❷ ❫ ✔ ✖ ✜ ✣ ✥ .
Let us denote by ✏ ❫ the ✌ ✍ ✌ ✑ ➏ ✌ ✍ ✌ ✑ diagonal matrix with diagonal entries ⑩ ❫ ✔ ✖ ✜ ✣ ✥ , and by ➫ ➭ the ✌ ✍ ✌ ✑ ➏ ✌ ✍ ✌ ✑ eligibility matrix
where the state-action pairs of ☞ ➏ ✏ are ordered as follows: ✔ ✖ ✿ ✜ ✳ ☎ ✔ ✖ ✿ ✥ ✥ ✜ ❃ ❃ ❃ ✜ ✔ ✖ ❫ ➳ ✜ ✳ ☎ ✔ ✖ ❫ ➳ ✥ ✥ , ❃ ❃ ❃ ✜ ✔ ✖ ❅ ✜ ✣ ➚ ✚ ✣ ➚ ❼ ✹ ✳ ☎ ✔ ✖ ❅ ✥ ✥ ✜ ❃ ❃ ❃ (the column headings indicate the block dimensions).
Let ➶ ❫ ✭ ✯ ✱ ❫ ➳ ❫ ➺ be the temporal difference vector :
In vector notation, the asymptotic approximation AQ(✂ ) of Q(✂ ) is defined by
4 Optimal gain matrix for Q-learning
One can see that (3) is a gain matrix variant of the basic Qlearning algorithm:
Using a gain matrix in order to guide and accelerate the convergence of a stochastic adaptive algorithm is a well-known approach in stochastic approximation theory [Benveniste et al., 1990; Kushner and Yin, 1997]. In this section, we calculate the optimal gain matrix for Q-learning that maximizes its rate of convergence.
The ordinary differential equation (ODE) method provides some analytic tools for analysing the convergence of the general stochastic algorithm
where ➬ ❫ is the current estimation of the target ➬ ☎ , and ➱ ❫ is the observed input random vector at time ✌ . Classic reinforcement learning algorithms like Q-learning or TD( ✂ ) have already been analysed with the ODE method [Bertsekas and Tsitsiklis, 1996; Borkar and Meyn, 2000], in order to prove their convergence.
Another potential application of the ODE method concerns the optimization of the rate of convergence of stochastic algorithms. One can show that under some general stability conditions [Benveniste et al., 1990] the new algorithm
where ➫ ☎ is the gain matrix defined by
and ❐ ❒ is the Jacobian matrix of the function
still converges toward ➬ ☎ , with aminimal asymptotic variance ↕ ➙ a113 ❫ ➛ ◗ ✌ ▲ ◆ a207 ➬ ❫ ❻ ➬ ☎ a207 a208 ❱ .
This approach, that has already been applied to Q-learning in finite horizon [Garcia and Ndiaye, 1998] and TD(✂ ) [Garcia and Serre, 2000], is developed here for Q-learning. We have ➬ ❫ ✹ ✄ ❫ ✭ ✯ ✱ ❫ ➳ ❫ ➺ , ➬ ☎ ✹ ✄ ☎ , ➱ ❫ ✹ ✔ ✖ ❫ ✜ ✣ ❫ ✜ ✖ ❫ ❊ ✿ ✥ and ➮ ✔ ➬ ❫ ✜ ➱ ❫ ✥ ✹ ➶ ❫ . The Jacobian matrix and its inverse can be calculated:
where a212 ☎ is the ✌ ✍ ➏ ✌ ✍ diagonalmatrixwith diagonal coefficients → ✔ ✖ ✜ ✳ ☎ ✔ ✖ ✥ ✥ , a212 is the ✌ ✍ ✔ ✌ ✑ ❻ ❬ ✥ ➏ ✌ ✍ ✔ ✌ ✑ ❻ ❬ ✥ diagonal matrix with diagonal coefficients → ✔ ✖ ✜ ✣ ✥ for ✣ ❼ ✹ ✳ ☎ ✔ ✖ ✥ , a213 ☎ is the ✌ ✍ ➏ ✌ ✍ transitionmatrix of theMarkov chain on ☞ defined by ✳ ☎ , and a213 the ✌ ✍ ✔ ✌ ✑ ❻ ❬ ✥ ➏ ✌ ✍ rectangular matrix of coefficients a213 ➵ ❞ ➴ ✈ ➻ ➴ ❞ ❡ ✹ ✓ ✔ ✖ ✘ ✚ ✖ ✜ ✣ ✥ for ✣ ❼ ✹ ✳ ☎ ✔ ✖ ✥ .
By developing this expression, we show
Proposition 2
The optimal gain matrix for Q-learning is
where
is the diagonal matrix with diagonal coefficients → ✔ ✖ ✜ ✣ ✥ , and a213 ☎ ➦ is the ✌ ✍ ✔ ✌ ✑ ❻ ❬ ✥ ➏ ✌ ✍ rectangular matrix of coefficients
where ✓ ☎ ❫ ✔ ✖ ✘ ✚ ✖ ✜ ✣ ✥ is the probability of moving from ✖ to ✖ ✘ by applying the first action ✣ and then by following the optimal policy ✳ ☎ on the next ✌ transitions.
This optimal gain ➫ ☎ leads to an "ideal" algorithm, called Optimal-Q-learning:
This algorithm theoretically maximizes the rate of convergence of Q-learning, by minimizing its asymptotic variance ↕ ➙ a113 ❫ ➛ ◗ ✌ ▲ ◆ a207 ✄ ❫ ❻ ✄ ☎ a207 a208 ❱ . One can see that the structure of ➫ ☎ implies that when a greedy action is chosen in ✖ ❫ , all the ✄ ❫ ✔ ✖ ✜ ✣ ✥ components have to be updated, and when an exploratory action has been selected, only ✄ ❫ ✔ ✖ ❫ ✜ ✣ ❫ ✥ is modified. Note that ➫ ☎ is independent of the reward functions ★ ✔ ✥ , and depends on the parameter ➓ that characterizes the exploration policy, through the → invariant distribution.
5 Average Q-learning
Optimal-Q-learning cannot be directly implemented since it would require the costly online estimation of the a213 ☎ ➦ coefficients. However, as shown next, it is possible to determine some ✂ and ⑩ ❫ parameters that minimize the distance between the gain matrix of AQ( ✂ ) and ➫ ☎ , and that allow an efficient implementation of the corresponding AQ(✂ ) algorithm.
5.1 Optimization of AQ( ➩ )
To be consistent with the definition of ➫ ☎ that assumes a stepsize equal to ✿ ❫ , we consider the case ✏ ❫ ✹ ✿ ❫ ✏ , where
is the ✌ ✍ ✌ ✑ ➏ ✌ ✍ ✌ ✑ diagonal matrix with constant coefficients ⑩ ✔ ✖ ✜ ✣ ✥ . We propose to optimize the choice of the ⑩ and ✂ parameters byminimizing the quadratic norm a207 ✏ ➫ ➭ ❻ ➫ ☎ a207 of the difference between the gain of AQ(✂ ) and the optimal gain of Q-learning.
We have
where the ✌ ✍ ➏ ✌ ✍ matrix a217 ☎ and the ✌ ✍ ✔ ✌ ✑ ❻ ❬ ✥ ➏ ✌ ✍ matrix a217 have coefficients equal to 1.
Making equal the lower right blocks leads to the choice ✏ ✹ a212 ➁ ✿ . A numerical analysis of the upper left blocks, similar to the one developed in [Garcia and Serre, 2000] for TD(✂ ), results in the choice ✏ ☎ ✹ a212 ☎ ➁ ✿ , and thus ✏ ✹ a212 ➁ ✿ . Then
This equality exhibits some similarity with equation (4). As we can note, the structures of the two gains are identical, which might explain the efficiency of Q(✂ ) for ✂ ✝ ✟ .
Minimizing
yields
Like for ➫ ☎ , this ➤ a222 a224 a226 value cannot be exactly implemented in practice in AQ(✂ ). However, ➤ a222 a224 a226 a227 ✿ ➨ ➦ ✿ ➁ ➦ for uniform MDPs where all the transition probabilities are nearly equal to ✿ ❫ ➳ (then a213 ☎ ➦ ✔ ✖ ✘ ✚ ✖ ✜ ✣ ✥ a227 ✿ ❫ ➳ ✿ ✿ ➁ ➦ , → ✔ ✖ ✘ ✜ ✳ ☎ ✔ ✖ ✘ ✥ ✥ a227 ➨ ❫ ➳ and so ➤ a222 a224 a226 a227 ✿ ➨ ➦ ✿ ➁ ➦ ). It appears experimentally that for large randomMDP, this approximation is still valid.
The value ➤ a222 a224 a226 a227 ✿ ➨ ➦ ✿ ➁ ➦ leads to ✂ a222 a224 a226 ✹ ✿ ➦ a228 a230 a231 a232 ✿ ❊ ➨ a228 a230 a231 a232 a227 ✿ ➨ . This value greater than 1 could be surprising. In fact convergence of eligibility trace methods requires that ❚ ✂ ❨ ❬ [Bertsekas and Tsitsiklis, 1996], and so ✂ ✹ ✿ ➨ could be implemented in Q(✂ ) assuming ➓ ✝ ❚ . In case ➓ ❲ ❚ , ✿ ➨ is no more an admissible value for ✂ , and the distance is minimized for ✂ ✹ ✿ ➦ on the boundary.
We are thus able to define a new optimized update rule from the asymptotic approximation (3) where ➤ ✹ ✿ ➨ ➦ ✿ ➁ ➦ and
5.2 Efficient implementation of AQ-learning
A direct implementation of the update rule (6) would have a complexity similar to Q(✂ ), proportional to ✌ ✍ ➏ ✌ ✑ . Fortunately, an equivalent expression can be derived. It only requires a small number of updates per iteration, independent of the number of states and actions.
Proposition 3
The update rule (6) is equivalent to
Proof: From (6) we have ✄ ❫ ✹ a80 a224 a237 ❫ ✿ a224 a212 ➁ ✿ ➶ a224 ❤ ✿ ➨ ➦ ✿ ➁ ➦ a80 a224 a237 ❫ ✿ a224 ❹ a224 a238 ➏ ❬ ❬ ✈ a231 ❙ ❏ ✐ ➵ ❞ a231 ➻ , where a238 denotes the vector with coefficients equal to ❬ , and ❬ ❬ a239 ❙ a240 equals 0 or 1 according as a241 ❼ ✹ a242 or a241 ✹ a242 . We then define the new relative value function a235 ❫ and the scaling factor a236 ❫ by
The ❹ ❫ error can be expressed as a function of a236 ❫ and a235 ❫ :
Note that the greedy action ✣ ☎ ❫ is defined by ✣ ☎ ❫ ✹ a115 ② ④ a113 a115 ✉ ✈ ✄ ❫ ✔ ✖ ❫ ✜ ✣ ✥ ✹ a115 ② ④ a113 a115 ✉ ✈ a235 ❫ ✔ ✖ ❫ ✜ ✣ ✥ . The update rule of a235 ❫ can be implemented by replacing the stepsize ✿ a233 ➵ ❞ ➘ ➴ ✈ ➘ ➻ ❫ with its approximation ✿ a245 ➘ ➵ ❞ ➘ ➻ a224 ➵ ✈ ➘ ➻ , where a246 ❫ ✔ ✖ ❫ ✥ is the number of times the state ✖ ❫ has been visited at time ✌ , and ✓ ✔ ✣ ❫ ✥ equals ➓ or ✿ ➁ ➨ ❫ ➺ ➁ ✿ whether ✣ ❫ ✹ ✣ ☎ ❫ or ✣ ❫ ❼ ✹ ✣ ☎ ❫ . Similarly, the condition ✣ ❫ ✹ ✳ ☎ ✔ ✖ ❫ ✥ for updating a236 ❫ might be replaced by ✣ ❫ ✹ ✣ ☎ ❫ . This leads to the following algorithm AQ-learning, or Average Q-learning:

In that algorithm, a246 a226 a222 a226 is the length of the learning trajectory. AQ-learning is particularly interesting, since it only requires 3 updates per iteration, namely a235 ❫ ✔ ✖ ❫ ✜ ✣ ❫ ✥ , a236 ❫ and a246 ❫ ✔ ✖ ❫ ✜ ✣ ❫ ✥ . AQ-learning should therefore improve the performance of Watkins' Q( ✂ ) for two distinct reasons. First, AQ-learning is an optimized approximation of Q(✂ ) that minimizes the asymptotic variance around ✄ ☎ . Second, like Q-learning, AQ-learning is an asynchronous algorithm that only updates one component of the value function (here a235 ❫ ) per iteration. It is clear that for large state-action space problems, this feature is of crucial importance regarding the time complexity of the algorithm, as it is shown in simulations in the next section.
Amazingly it appears that AQ-learning is very close to the R-learning algorithm proposed by Schwartz [Schwartz, 1993]. R-learning is supposed to converge to gain optimal policies, that maximize the average-cost
❃
AQ-learning and R-learning are identical when ❚ ✷ ❬ , with a correct choice of the R-learning learning rates. The fact that AQ-learning is a near-optimal gain matrix variant of Q-learning could explain why several experiments have demonstrated that R-learning could outperform Q-learning, despite the fact that these two algorithms have not been designed for the same optimality criterion.
We do not provide in this article a convergence proof for AQ-learning. We think, however, that it might be possible to establish such a proof either by checking the stability condition of the gain matrix a212 ➁ ✿ ➫ ➭ for ➤ ✹ ✿ ➨ ➦ ✿ ➁ ➦ , or by exploiting the ODE approach of Borkar [Borkar, 1996] for two-time scale algorithms (it might be necessary in that case to modify the a236 ❫ update rule).
6 Simulations
We made numerical experiments in order to study the relative performance of Q-learning, Optimal-Q-learning, Watkins' Q( ✂ ) and AQ-learning. These reinforcement learning algorithms were applied to randomly generated Markov Decision Problems, with all components ✓ ✔ ✖ ✘ ✚ ✖ ✜ ✣ ✥ ✝ ✟ , and with state rewards ★ ✔ ✖ ✥ ✭ ◆ ✟ ✜ ❬ ❱ .


We present here two kinds of learning results that fairly describe the general behaviour of these algorithms. For both of them, the value functions ✄ ❫ , a235 ❫ and a236 ❫ were updated on a unique long trajectory on ☞ ➏ ✏ with random initial state. All parameters were initially set to 0. The stepsizes ⑩ ❫ ✔ ✖ ✜ ✣ ✥ were equal to ✿ a245 ➘ ➵ ❞ ➴ ✈ ➻ . We chose a semi-uniform exploration strategy with ➓ ✝ ❚ . For each problem, ■ ☎ , ➫ ☎ and ✂ a222 a224 a226 were exactly calculated fromthe data ✓ ✔ ✥ and ★ ✔ ✥ .
Figure 1 shows the relative learning error a251 a252 ➘ ➁ a252 ✐ a251 a251 a252 ✐ a251 as a function of ✌ (average value and standard deviation on 20
random trajectories). The size of the MDP was ✌ ✍ ✹ ❬ ✟ ✟ , ✌ ✑ ✹ a253 , with ❚ ✹ ✟ ❃ a254 and ➓ ✹ ✟ ❃ a255 . This graph illustrates the different rates of convergence of Q-learning, AQ-learning, Q(✂ ) for ✂ ✹ ✂ a222 a224 a226 , and Optimal-Q-learning. These experimental results confirm that the faster rate of convergence is obtained with Optimal-Q-learning, and that AQ-learning converges nearly as fast as this ideal algorithm. AQ-learning even performs slightly better than Q( ✂ ) with the same learning rates and the ✂ a222 a224 a226 value. These three algorithms appear to be considerably faster than Q-learning.
Figure 2 illustrates for the same algorithms the different computation times required to achieve a relative learning error equal to 5%, as a function of the size ✌ ✍ of the state space, for a constant number of actions ✌ ✑ ✹ a253 , with ❚ ✹ ✟ ❃ a0 and ➓ ✹ ✟ ❃ a255 . We first observe on that graph that Q-learning is very slow, despite the fact that it only updates one component per iteration. But the main observation is that AQ-learning can be really more efficient than Q(✂ ), especially when the number of states is important; for 200 states, AQ-learning is 10 times faster than Q(✂ ).
7 Conclusions
We have shown that an asymptotic approximation of Q(✂ ) could be efficiently implemented through two simple update rules on a relative value function a235 ❫ ✔ ✖ ✜ ✣ ✥ and on a scaling factor a236 ❫ . This new algorithm AQ-learning can be described as an average variant of Q-learning for the discounted criterion. Its update complexity is independent of the number of states and actions, and experimental results show that its convergence toward the optimal value function is always faster than for Q-learning or Q( ✂ ).
Our results have been obtained for the Watkins' Q( ✂ ) with accumulating eligibility trace. It would be interesting to apply the same approach to the case of replacing traces [Singh and Sutton, 1996], or to Peng and Williams' Q( ✂ ) [Peng and Williams, 1994] where the trace is never reset to 0, and for which an efficient implementation has been proposed by Wiering and Schmidhuber [Wiering and Schmidhuber, 1997].
Another direction for future work concerns the development of new reinforcement learning algorithms that approximate Optimal-Q-learning. Furthermore, we have seen that the ➫ ☎ optimal gain forQ-learning depends on the exploration policy parameterized by ➓ . The question of finding the best value of ➓ remains open.
Finally, we need a better understanding of the relation between AQ-learning the Schwartz' R-learning algorithm [Schwartz, 1993].
@inproceedings{ijcai2001p131,
title = {From Q(lambda) to Average Q-learning: Efficient Implementation of an Asymptotic Approximation},
author = {Garçia, Frédérick and Serre, Florent},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bernhard Nebel},
pages = {959--963},
year = {2001},
url = {https://ijcai.org/proceedings/2001/131},
}
TY - CPAPER TI - From Q(lambda) to Average Q-learning: Efficient Implementation of an Asymptotic Approximation AU - Garçia, Frédérick AU - Serre, Florent T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 959 EP - 963 UR - https://ijcai.org/proceedings/2001/131 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: