{"id":923,"date":"2019-01-09T10:54:24","date_gmt":"2019-01-09T10:54:24","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=923"},"modified":"2019-01-09T11:42:58","modified_gmt":"2019-01-09T11:42:58","slug":"temporal-difference-learning","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/temporal-difference-learning\/","title":{"rendered":"Temporal Difference Learning"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022 To understand Temporal Difference Learning \u2022 To describe the Optimal Value Functions\r\n\r\n\u2022 To analyse TD-Prediction\r\n\r\n\u2022 To describe Learning an action value function\r\n\r\n \r\n\r\n40.1 Introduction<\/strong>\r\n\r\n \r\n

Policy evaluation algorithms are\u00a0\u00a0 intended to estimate the value functions V<\/em> \u03c0\u00a0<\/em>or\u00a0Q\u03c0 <\/em>for a given policy \u03c0<\/em>. Typically these are on-policy algorithms, and the considered policy is assumed to be stationary (or \u201calmost\u201d stationary). There are three classes of policy evaluation algorithms namely Monte Carlo methods, Dynamic Programming, and Temporal Difference Learning or TD learning. Monte Carlo methods do not need a model of the learning environment. From experience in form of sequences of state -action-reward-samples they can approximate future rewards. Monte-Carlo methods are based on the simple idea of averaging a number of random samples of a random quantity in order to estimate its average. Dynamic Programming is based on the Bellman Equation where the problem is broken down into sub problems and depends on a perfect model of the environment. However both Dynamic Programming and Monte Carlo methods only update after a complete sequence that is when the final state is reached. The main issues are whether it is possible to avoid the computational expense and space requirements for storing the transition model estimate of a full Dynamic programming policy evaluation.<\/p>\r\n \r\n

TD learning is considered as the most novel idea in reinforcement learning. Temporal Difference Learning is a model free approach which does not store an estimate of entire transition function but instead stores estimate of Vp, which requires only O(n) space. It carries out local, cheap updates of utility\/value function on a per-action basis. As you may recall Value Functions are state-action pair functions that estimate how good a particular action will be in a given state, or what the return for\u00a0that action is expected to be a Temporal Difference (TD). Learning methods can be used to estimate these value functions. If the value functions were to be calculated without estimation, the agent would need to wait until the final reward was received before any state-action pair values can be updated. Once the final reward was received, the path taken to reach the final state would need to be traced back and each value updated accordingly.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n40.1.1 Comparison \u2013 Monte Carlo, Dynamic Programming and TD Approaches<\/strong>\r\n\r\n \r\n

Before we discuss TD method let us compare Monte Carlo and Dynamic Programming methods. We will discuss two aspects namely bootstrapping and sampling. In bootstrapping update involves an estimate from a nearby state . While Monte Carlo method does not bootstrap that is each state is independently estimated, Dynamic Programming methods bootstraps that is estimates for each state is dependent on nearby states. In sampling update involves an actual return Monte Carlo method does sampling that is learns from experience in the environment and gets an actual return. Dynamic programming does not sample but learns by spreading constraints until convergence through iterating the Bellman equations without interaction with the environment.<\/p>\r\n \r\n

TD bootstraps that is learning involves an estimate of a nearby state. TD also samples where update involves an actual return.<\/p>\r\n \r\n\r\n40.2\u00a0 Optimal Value Functions<\/strong>\r\n\r\n \r\n\r\nBefore we discuss TD learning let us recall that for finite MDPs, policies can be partially ordered <\/strong>that is there is always at least one (and possibly many) polic y that is better than or equal to all the others. This is an optimal policy<\/strong>. We denote them all p<\/em>*.<\/em> Optimal policies share the same optimal state-value function<\/strong>:\r\n\r\n \r\n\r\n\"\"<\/em>\r\n

This is the expected return for taking action \u2018a\u2019<\/em> in state \u2018s\u2019<\/em> and thereafter following an optimal policy. Now let us discuss the Bellman optimality equation for V*.<\/p>\r\n \r\n\r\n40.2.1 Bellman Optimality Equation for V*<\/strong>\r\n\r\n \r\n

The value of a state under an optimal policy must equal the expected return for the best action from that state where V*<\/strong>is the unique solution of this system of nonlinear equations.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\"\"\r\n\r\n \r\n\r\nThe relevant backup diagram is shown in Figure 40.1.\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Figure 40.1 Backup diagram<\/strong><\/p>\r\n \r\n

40.2.2 Bellman Optimality Equation for Q*<\/strong><\/p>\r\n \r\n

The unique solution of this system is given by the nonlinear equations, where Q*<\/strong> is the unique solution of this system of nonlinear equations<\/p>\r\n\"\"\r\n\r\n \r\n\r\nThe relevant backup diagram is shown in Figure 40.2.\r\n\r\n\"\"\r\n

Given Q<\/em>* , the agent does not even have to do a one-step-ahead search in order to find the optimal Action-Value functions.<\/p>\r\n \r\n\r\n\"\"\r\n40.2.3 Solving the Bellman Optimality Equation<\/strong>\r\n\r\n \r\n

Finding an optimal policy by solving the Bellman Optimality Equation requires the following that is accurate knowledge of environment dynamics, enough space and time to do the computation, and the Markov Property must be satisfied. The space\u00a0required is polynomial in number of states but the number of states is often huge (e.g., backgammon has about 10**20 states). Therefore usually we have to settle for approximations. Many reinforcement learning methods can be understood as approximately solving the Bellman Optimality Equation.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n40.3 Policy Evaluation<\/strong>\r\n\r\n \r\n\r\n\"\"\r\n

Monte Carlo methods do not need full knowledge of environment, but just needs experience, or simulated experience (Figure 40.3). One method is by averaging sample returns which is generally defined only for episodic tasks. This method is similar to DP in terms of policy evaluation, policy improvement.<\/p>\r\n\"\"\r\n

Figure 40.3 Simple Monte Carlo Method<\/strong><\/p>\r\n \r\n

Dynamic Programming (Figure 40.4) needs complete model of the environment and rewards. DP bootstraps that is updates estimates on the basis of other estimates<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n\r\n \r\n

In TD prediction we estimate the actual return as the sum of the next reward plus the value of the next state (Figure 40.5). As we discussed earlier when the environment,<\/p>\r\n\r\n