# Questions tagged [temporal-difference-methods]

For questions related to the temporal-difference reinforcement learning (RL) algorithms, which is a class of model-free (that is, they do not use the transition and reward function of the MDP) RL algorithms which learn by bootstrapping from the current estimate of the value function (that is, they use one estimate to update another estimate).

87 questions
Filter by
Sorted by
Tagged with
1 vote
31 views

### Unclear sentence in Sutton-Barto in Temporal-Difference chapter

Sutton-Barto, Chapter 6, page:130 By 8000 time steps, the greedy policy was long since optimal (a trajectory from it is shown inset); continued $\epsilon$-greedy exploration kept the average episode ...
• 778
24 views

### Derivation of update rule for Off-policy TD(0) with importance sampling ratio

Sutton-Barto, second edt, page 128, Exercise 6.7: Design an off-policy version of the TD(0) update that can be used with arbitrary target policy $\pi$ and covering behavior policy $b$, using at each ...
• 778
19 views

### Pseudocode for batch TD(0)

This is from Sutton-Barto, second edt, page 126: Suppose there is available only a finite amount of experience, say 10 episodes or 100 time steps. In this case, a common approach with incremental ...
• 778
1 vote
69 views

### Calculating TD($\lambda$) returns, reinforcement learning

I am having some trouble with answering the following question: A rat is involved in an experiment. It experiences one episode. At the first step it hears a bell. At the second step it sees a light. ...
• 13
226 views

### Where does the TD formula for tic-tac-toe in Sutton & Barto come from?

In section $1.5$ of the book "Reinforcement Learning: An Introduction" by Sutton and Barto they use tic-tac-toe as an example of an RL use case. They provide the following temporal ...
• 167
353 views

• 1,948
96 views

### How to calculate TD error?

I just start to learn reinforcement learning and confuse with TD error. We calculate temporal difference with V(t) = V(t) + α[Rt+1 + γV(t+1) - V(t)] where inside bracket is called TD error. The ...
1 vote
75 views

### TD Leaf value function update

I'm currently watching a RL course by David Silver and he explains the update of TD Leaf, here is the slide: He says that if, at the next turn (after we played red and the opponent played blue) ...
71 views

### Consequence of Dvoretzky Stochastic Approximation Theorem

I am trying to understand all the steps to prove the TD0 algorithm, and I am following a proof which uses a theorem of Tommi Jaakkola, Michael I. Jordan and Satinder P. Singh, in the paper: On the ...
• 19
43 views

### Time index in TD(0) return

in TD(0). for the return we have: $G_{t:t+1}=r_{t+1}+\gamma v_t(s_{t+1})$. Why is the time index on right hand side in $v$ is $t$?
• 778
1 vote
45 views

### Confusion in subscript for n-step TD(0)

This is n-step TD(0) update rule: $v_{k+n}(x_k)=v_{k+n-1}(x_k)+\alpha [g_{k:k+n}-v_{k+n-1}(x_k)]$ Why is the subscript on the left hand-side of equation "k+n", not "k+n-1"? Does ...
• 778
1 vote
159 views

### Where is the problem: in batch TD(0) algorithm or in the code to solve AB problem in Sutton-Barto RL book?

Here is the batch TD(0) algorithm: Here is the AB example I want to solve using batch TD(0): And finally here is my Matlab code: % eps1: A 0 B 0 % eps2: B 1 % eps3: B 1 % eps4: B 1 % eps5: B 1 % ...
• 778
1 vote
386 views

### Proof of convergence of TD(0) algorithm

I am looking for a proof of the following tabular TD(0) algorithm: However, I can only find proofs with the more general TD($\lambda$) algorithm and I am having problems understanding them. In ...
• 19
90 views

### How can I get Q-Learning (1 step off policy) update from n-step off policy learning update?

In Sutton and Barto we have expressions for Q-Learning and n-step Off policy learning. The former ought to be the 1-step limit of the latter but I cannot see it working out that way. What am I missing?...
1 vote
242 views

### Using TD algorithms, if the value function of terminal states is always 0, why would a policy ever choose it?

Temporal difference algorithms (TD($\lambda$)) are tabular solutions to reinforcement learning problems. That is, they create a table of all the states in the problem, and estimate the expected long-...
• 148
1 vote
64 views

### Given a set of trajectories produced by a fixed policy, what is the the standard approach to estimate Q?

Let's say that I have a set of trajectories $\mathcal{D} = \{\tau_1, \dots, \tau_n\}$ produced by an agent acting in a (episodic) MDP with a fixed policy $\pi$. I would like to estimate the $Q$ ...
• 183
1 vote
112 views

### If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)?

In Sutton-Barto (Section: 9.8 Least-Squares TD, page 228): Authors say that Least-Squares TD is the most "data efficient" form of linear TD(0). Later, in this section, they say the ...
• 189
166 views

### When using TD(λ), how do you calculate the eligibility trace per input & weight of a neural network neuron?

I have a Neural Network, each Neuron is made up of inputs, weights, and output. I have potentially multiple hidden layers. The activation function executed against the output is not known by the ...
• 220
1 vote
106 views

### What is 'eligibility' in intuitive terms in TD($\lambda$) learning?

I am watching the lecture from Brown University (in udemy) and I am in the portion of Temporal Difference Learning. In the pseudocode/algorithm of TD(1) (seen in the screenshot below), we initialise ...
• 185
218 views

### Why $t=τ+n-1$ instead of $t=τ+n$ in n-step TD?

If $\tau$ is the time, whose state’s estimate is being updated, and $t$ is the current time, then, in n-step TD method, we have $t=\tau+n$ (because we have to wait n-steps, before we can update). ...
• 778
71 views

• 133
1 vote
368 views

### Is there a tutorial for understanding the proof of convergence for TD learning?

I'm reading the article An Analysis of Temporal-Difference Learning with Function Approximation (1997), but the mathematics inside seems overly complicated for me. Answers to some similar questions ...
796 views

### How does $\alpha$ affect the convergence of the TD algorithm?

In Temporal-Difference Learning, we update our value function by $V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\right)$ If we ...
• 143
271 views

### Why does TD (0) converge to the MLE solution of the Markov model?

Why does TD (0) converge to the MLE solution of the Markov model? Let's take the Example 6.4 in Sutton and Barto's book as an example. Example 6.4: You are the Predictor Place yourself now in the ...
• 143
535 views

### How to handle invalid actions for next state in Q-learning loss

I am implementing an RL application in an environment with illegal moves. For handling the illegal moves, I am currently just picking an action as the maximum Q-value from the set of legal Q-values. ...
• 118
142 views

### Why don't we bootstrap terminal state in n-step temporal difference prediction update equation?

In the algorithm below, when $\tau + n \geq T$, shouldn't the algorithm bootstrap with the value of the next state? For instance, when $T=5, \tau=3, \& \; n=2$, we don't bootstrap the sample ...
• 379
27 views

### Why does one-step TD strengthen only the last action of the sequence of actions that led to the high reward, while n-step TD the last n actions?

In the caption of figure 7.4 (p. 147) of Sutton & Barto's book (2nd edition), it's written The one-step method strengthens only the last action of the sequence of actions that led to the high ...
• 379
72 views

### How does n-step Temporal Difference remove the notion of time-step?

How does n-step TD removes the notion of time-step as referenced in Sutton and Barto (2nd edition, Page 163) below? Another way of looking at the benefits of n-step methods is that they free you from ...
• 379
326 views

### How does the learning rate $\alpha$ vary in stationary and non-stationary environments?

In Sutton and Barto's book (Chapter 6: TD learning, 2nd edition), he mentions two ways of updating value function: Monte Carlo method: $V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]$. TD(0) method: ...
• 379
145 views

### What are the recurrences used for updating state value function in $TD$ and $TD(\lambda)$ learning?

There are two types of value functions in reinforcement learning: State value function $V^{\pi} (s)$, state-action value function $Q^{\pi}(s, a)$. State value function: This value tells us how good ...
• 3,870
71 views

### Recursive Least squares (RLS) for mini batch

For my application I am considering a learning problem where I simulate a bunch of episodes say '$n$' first, and than carry out the recursive least squares update. Similar to $TD(1)$. I know that RLS ...
219 views

### Comparison between TD(0) and MC ( or GAE )?

I'm getting started with DRL and have trouble distinguishing TD(0), MC, and GAE; and which scenarios one's better than others. Here is what I understand so far: TD(0): increment learning, can learn ...
1 vote
295 views

1 vote
102 views

### How can I derive n-step off-policy temporal difference formula?

I was reading the book "Reinforcement Learning: An Introduction" by Sutton and Barto. In section 7.3, they write the formula for n-step off-policy TD as V(S_t) = V(S_{t-1}) + \alpha \rho_{...
• 693
509 views

### Why does TD Learning require Markovian domains?

One of my friends and I were discussing the differences between Dynamic Programming, Monte-Carlo, and Temporal Difference (TD) Learning as policy evaluation methods - and we agreed on the fact that ...
• 1,141
1 vote
49 views

### If the transition model is available, why would we use sample-based algorithms?

Sample-based algorithms, like Monte Carlo Algorithms and TD-Learning, are often presented as useful since they do not require a transition model. Assuming I do have access to a transition model, are ...
• 2,890
112 views

### Into which subcategories can reinforcement learning be divided?

In the course of a scientific work, I will discuss the different types of reinforcement learning. However, I have difficulties to find these different types. So, into which subcategories can ...
• 23
1 vote