On Average versus Discounted Reward Temporal{diierence Learning 1

We provide an analytical comparison between discounted and average reward temporal di erence TD learning with linearly parameterized approximations We rst consider the asymptotic behavior of the two algorithms We show that as the discount factor approaches the value function produced by discounted TD approaches the di erential value function generated by average reward TD We further argue that if the constant function which is typically used as one of the basis functions in discounted TD is appropriately scaled the transient behaviors of the two algorithms are also similar Our analysis suggests that the computational advantages of average reward TD that have been observed in some prior empirical work may have been caused by inappropriate basis function scaling rather than fundamental di erences in problem formulations or algorithms Introduction Sequential decision making problems under uncertainty are often formulated as in nite horizon dynamic programming problems and can be tackled by a variety of tools For rela tively small and well modeled problems classical methods apply Bertsekas When a problem is large or when a model is unavailable one is led to consider simulation based approximation methods including temporal di erence TD methods Sutton The original version of TD as well as most of the subsequent literature has focused on problems with a discounted reward criterion This was a natural rst step for two reasons a Average reward problems can be accurately approximated in a well de ned sense by discounted problems as the discount factor approaches b The mathematical structure and analysis of average reward formulations can be com plicated This is because the favorable contraction properties of the dynamic pro gramming operator are only present in the discounted case For these reasons a discounted formulation with a discount factor very close to is often used a proxy for an average reward problem While there has been an emerging literature on the development and deployment of average reward reinforcement learning algorithms see e g Abounadi Mahadevan Marbach Mihatsch and Tsitsiklis Schwartz Singh Tsitsiklis and Van Roy b Tadepalli and Ok Van Roy the picture is far from complete as only some of these methods can be adequately justi ed mostly for the case of lookup table representations It is natural to inquire whether the practice of avoiding average reward formulations is necessary and or sound Our earlier work Tsitsiklis and Van Roy b Van Roy has answered the rst question it has provided a variant of TD that can be applied to average reward problems Furthermore it has established that average reward TD has the same theoretical guarantees as were established in Tsitsiklis and Van Roy a Van Roy for discounted TD Assuming a linearly parameterized approximation architecture we have convergence with probability a characterization of the limit and bounds on approximation error Results of this type for both discounted and average reward versions refer to Markov chains that are operated under a xed policy When the policy is allowed to change during the learning process one usually hopes that such methods will deliver good performance This has been the case for discounted TD in many applications The experience with average TD is limited but has also been positive Marbach Mihatsch and Tsitsiklis This paper focuses on the second issue namely soundness Is it safe to replace an av erage reward problem by a discounted one Does discounted TD become more and more ill conditioned as the discount factor approaches Could there be an inherent advantage to average reward TD These questions have been prompted to a large extent by available ex perience which suggests that average reward methods may o er computational advantages Marbach Mihatsch and Tsitsiklis Tadepalli and Ok The analysis provided in the remainder of the paper indicates that discounted TD with a discount factor approaching is essentially identical to average reward TD The two methods converge to the same limit Furthermore as long as the constant function which is typically used as one of the basis functions in discounted TD is appropriately scaled their transient behaviors are also similar This analysis suggests that the observed computational advantages of average reward TD may have been caused by inappropriate basis function scaling rather than fundamental di erences in problem formulations or algorithms We will limit the discussion in this paper to the special case of TD that is known as TD This will allow us to keep the exposition simple However similar arguments apply to TD for general and lead to the same conclusions The remainder of this paper is organized as follows The next section reviews discounted and average reward temporal di erence learning and discusses how to relate the basis func tions used by the two algorithms in any meaningful comparison Section establishes the similarity of the limits of convergence of the two algorithms The transient behaviors are compared in Section Concluding remarks are made in Section Temporal Di erence Learning Algorithms In this section we review the discounted and average reward TD algorithms and set the stage for their comparison Our discussion will be somewhat brief We refer the reader to Tsitsiklis and Van Roy a b for more details We consider a Markov chain fxt j t g with state space S f ng The Markov chain is de ned in terms of a transition probability matrix P whose i j th entry is the probability that xt j given that xt i We assume that the chain is irreducible and aperiodic and therefore has a unique invariant distribution vector n which satis es P and x for all x S In our notation stands for the transpose of and x is the xth component A similar notational convention will be used for all other vectors to be encountered later on For each state x S there is a scalar g x that represents the one stage reward for being at that state We let g n be a vector whose xth component is g x We will make use of an inner product h i de ned by hJ Ji X