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).
80
questions
0
votes
0
answers
19
views
Finding a value at which TD(lambda) and Monte Carlo Are Similar
Let's say that I'm trying to find a value of lambda for which running a TD(lambda) method will produce the same results as a Monte Carlo method (within a small margin or error, of course). One of the ...
- 1
0
votes
0
answers
21
views
Correction of value update in off policy TD(0)
In this question (inherited from slides coming from D. Silver) they are arguing that the value update in off policy TD(0) should be:
$$
V(S_t) = V(S_t) + \alpha \left( \frac{ \pi(A_t|S_t)}{\mu (A_t|...
- 851
0
votes
1
answer
37
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 ...
- 101
0
votes
1
answer
55
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) ...
0
votes
1
answer
53
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
0
votes
1
answer
42
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$?
- 301
1
vote
1
answer
32
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 ...
- 301
0
votes
0
answers
51
views
Understanding SARSA with binary features and function approximation
I'm reading the Sutton and Barto Book on Reinforcement Learning (for oral exam preparation).
However, I'm stuck on the algorithm for SARSA($\lambda$) with binary features and linear function ...
- 1
1
vote
1
answer
120
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
% ...
- 301
1
vote
1
answer
232
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
0
votes
1
answer
50
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?...
- 191
1
vote
1
answer
136
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
0
votes
0
answers
53
views
Why don't approximate TD target use a sample mean?
In practice, we prefer to fit the action-value function by minimizing the Mean Squared Error (MSE) between a parameterized function $Q_{w}(s, a)$ and one-step td target,
\begin{equation}
y = r(s, a) ...
- 41
1
vote
2
answers
60
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$ ...
- 173
1
vote
1
answer
99
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 ...
- 179
0
votes
1
answer
129
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 ...
- 210
1
vote
0
answers
95
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 ...
- 175
0
votes
1
answer
150
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). ...
- 301
2
votes
1
answer
67
views
Why do we have $t$ as subscript in $V$ instead of $t+1$ in the expression of $G_{t:t+1}$?
In one-step TD updates, the target is the first reward plus the discounted estimated value of the next state, which we call the one-step return (page 143 of Sutton & Barto):
$$
G_{t:t+1} \...
- 301
4
votes
1
answer
121
views
In TD(0) with linear function approximation, why is the gradient of $\hat v(S^{\prime}, \mathbf w)$ wrt parameters $\mathbf w$ not considered?
I am reading these slides. On page 38, the update for the parameters for the linear function approximation of TD(0) is given. I have a doubt regarding this.
The cost function (RMSE) is given on page ...
- 43
2
votes
1
answer
361
views
How does this TD(0) off-policy value update formula work?
The update formula for the TD(0) off-policy learning algorithm is (taken from these slides by D. Silver for lecture 5 of his course)
$$ \underbrace{V(S_t)}_{\text{New value}} \leftarrow \underbrace{V(...
- 133
1
vote
1
answer
299
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 ...
- 11
2
votes
2
answers
654
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
2
votes
0
answers
179
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
2
votes
1
answer
421
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
0
votes
1
answer
125
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 ...
- 359
0
votes
0
answers
23
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 ...
- 359
0
votes
0
answers
68
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 ...
- 359
2
votes
1
answer
246
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: ...
- 359
0
votes
0
answers
118
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,581
1
vote
0
answers
34
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 ...
0
votes
0
answers
176
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 ...
- 3
1
vote
1
answer
246
views
What would be the importance sampling ratio for off-policy TD learning control using Q values?
The off-policy TD learning control using state value function from page 34 of David Silver's RL lecture is:
$$ V(S_t) \leftarrow V(S_t) + \alpha \left( \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)} (R_{t+1} + \...
- 113
4
votes
1
answer
174
views
How should I implement the state transition when it is a Gaussian distribution?
I am reading this paper Anxiety, Avoidance and Sequential Evaluation and is confused about the implementation of a specific lab study. Namely, the authors model what is called the Balloon task using a ...
- 182
0
votes
1
answer
403
views
When calculating the cost in deep Q-learning, do we use both the input and target states?
I just finished Andrew Ngs's deep learning specialization, but RL was not covered, so I don't know the basics of RL. So, I have been having trouble understanding the cost function in deep Q-learning. ...
- 323
3
votes
1
answer
194
views
Is the expected value we sample in TD-learning action-value Q or state-value V?
Both MC and TD are model-free and they both follow a sample trajectory (in the case of TD, the trajectory is cut-short) to estimate the return (we basically are sampling Q values). Other than that, ...
- 155
3
votes
1
answer
1k
views
How to determine if Q-learning has converged in practice？
I am using Q-learning and SARSA to solve a problem. The agent learns to go from the start to the goal without falling in the holes.
At each state, I can choose the action corresponding to the maximum ...
- 31
4
votes
2
answers
300
views
Why is the target called "target" in Monte Carlo and TD learning if it is not the true target?
I was going through Sutton's book and, using sample-based learning for estimating the expectations, we have this formula
$$
\text{new estimate} = \text{old estimate} + \alpha(\text{target} - \text{old ...
- 125
1
vote
0
answers
89
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_{...
- 673
5
votes
1
answer
400
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,121
1
vote
1
answer
45
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,215
2
votes
1
answer
109
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
0
answers
100
views
Why do bootstrapping methods produce nonstationary targets more than non-bootstrapping methods?
The following quote is taken from the beginning of the chapter on "Approximate Solution Methods" (p. 198) in "Reinforcement Learning" by Sutton & Barto (2018):
reinforcement ...
- 121
2
votes
1
answer
82
views
Why isn't it wise for us to completely erase our old Q value and replace it with the calculated Q value?
Why isn't it wise for us to completely erase our old Q value and replace it with the calculated Q value? Why can't we forget the learning rate and temporal difference?
Here's the update formula.
- 349
2
votes
1
answer
1k
views
What is the bias-variance trade-off in reinforcement learning?
I am watching DeepMind's video lecture series on reinforcement learning, and when I was watching the video of model-free RL, the instructor said the Monte Carlo methods have less bias than temporal-...
- 33
1
vote
0
answers
72
views
Why does the n-step return being zero result in high variance in off policy n-step TD?
In the paragraph given between eq 7.12 and 7.13 in Sutton & Barto's book:
$G_{t:h} = R_{t+1} + G_{t+1:h} , t < h < T$
where $G_{h:h} = V_{h-1}(S_h)$. (Recall that this return is used at ...
- 147
0
votes
0
answers
109
views
Problem in understanding equation given for convergence of TD(n) algorithm
Given equation 7.3 of Sutton and Barto's book for convergence of TD(n):
$\max_s|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi(s)| \leqslant \gamma^n \max_s|V_{t+n-1}(s) - v_\pi(s)|$
$\textbf{PROBLEM ...
- 147
2
votes
1
answer
176
views
How is $\Delta$ updated in true online TD($\lambda$)?
In the RL textbook by Sutton & Barto section 7.4, the author talked about the "True online TD($\lambda$)". The figure (7.10 in the book) below shows the algorithm.
At the end of each step, $V_{...
- 53
0
votes
1
answer
55
views
What is correct update when the some indexes are not available?
To update the Q table Q-learning takes the arg max of the Q values - the state, value mappings.
For example, in tic tac toe the state XOX OXO -X- contains two ...
- 325
6
votes
1
answer
2k
views
What are the conditions of convergence of temporal-difference learning?
In reinforcement learning, temporal difference seem to update the value function in each new iteration of experience absorbed from the environment.
What would be the conditions for temporal-...
- 163