Temporal-Difference learning. Temporal-Difference (TD) learning is a significant and novel idea to RL, which combines Monte Carlo ideas and dynamic programming ideas [110]. Using Monte Carlo ideas, TD methods can learn directly from raw experience without prior knowledge of the environment’s dynamics. Using dynamic programming ideas, TD methods can continuously update estimates without waiting for a final outcome. TD methods are usually applied to the policy evaluation, prediction problem or control problem. Before introducing TD methods, we first review the simplest every-visit Monte Carlo method for non-stationary environment, expressed as where Gt is the actual return following time t, and α is a constant step size. Note that the return Gt is only revealed at the end of an episode, thus Monte Carlo methods update must wait until the end. However, TD methods can update estimates each step of the episode. Given some experience following a policy π, TD methods update the estimate V of the value function vπ for the state St occurring in that experience. At time t + 1, the update of the simplest TD method is given by where Rt+1 is the observed reward, γ is a constant discount factor. This methods is termed as TD(0) or one-step TD, because it is a special case of the TD(λ) or n-step TD methods developed in [88]. TD methods update estimates based on existing estimates V (St+1), which are called as bootstrapping, i.e., learn a guess from a guess. For the control problem, the alternating sequence of states and state-action pairs in an episode are usually described in Fig. 2.4, as follows Figure 2.4: An alternating sequence of states and state-action pairs. Many RL algorithms using TD methods have been developed to solve the control problem, e.g., Sarsa (on-policy TD control) in [109] and Q-learning (off- policy TD control) in [125]. Both of Sarsa and Q-learning algorithms attempts to learn an action-value function rather than a state-value function. Take Q-learning as an example, the update of Q-learning is defined by a Q(St, At) ← Q(St, At) + α Rt+1 + γ max Q(St+1, a) − Q(St, At) , (2.8) where Q(·) is the action-value function. Q-learning algorithm has been proved that it converges with probability 1 to the optimal action-values [110]. The generalized Q-learning algorithm is depicted in the following Algorithm 2.1. Algorithm 2.1 Q-learning (off-policy TD control) ∈ S ∈ A ·
Temporal-Difference learning. Commented [D(15]: can this be left out? Commented [D(16R15]: Hmm, yes, its a bit of a dilemma. On the one hand you have to introduce a lot of terms for an intro into RL, and TD-learning and the replay-buffer are landmark publications. On the other hand, pretty soon you are copying an entire RL textbook. Commented [DR(17R15]: I only mean the 4 words here. Informally, we would like the agent to learn while it interacts with the environment. In the previous example, it needed complete episodes before updating the Q-table with the collected rewards. In temporal difference learning (TD), the agent learns or updates from rewards collected every action. This means that all learning is done from Q and V values at a time t and t+1. A pair of two. Instead of playing an entire game of chess from start to finish, the agent takes a (state, action, reward, next-state) pair and performs a learning update. Slightly more formal, TD updates using existing estimates rather than actual rewards and complete returns Version Status Date Page 2.0 Non-Confidential 2024.05.1172022.03.1 19/100 Figure 6 Learning strategy using only two states.
