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).

Filter by
Sorted by
Tagged with
1 vote
2 answers
48 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$ ...
user avatar
  • 163
1 vote
1 answer
44 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 ...
user avatar
0 votes
0 answers
12 views

TD(0) update with negative rewards

So I'm trying to figure out the update for TD learning and I'm curious about something. Below is the paper I'm reading and it's very good These make a lot of sense. Moving a --> b, the new value ...
user avatar
  • 1
0 votes
1 answer
57 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 ...
user avatar
1 vote
0 answers
27 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 ...
user avatar
  • 175
0 votes
1 answer
36 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). ...
user avatar
2 votes
1 answer
48 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} \...
user avatar
4 votes
1 answer
56 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 ...
user avatar
2 votes
1 answer
76 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(...
user avatar
  • 133
1 vote
1 answer
108 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 ...
user avatar
2 votes
2 answers
187 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 ...
user avatar
  • 43
2 votes
0 answers
71 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 ...
user avatar
  • 43
2 votes
1 answer
106 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. ...
user avatar
0 votes
1 answer
62 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 ...
user avatar
0 votes
0 answers
17 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 ...
user avatar
0 votes
0 answers
48 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 ...
user avatar
2 votes
1 answer
35 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: ...
user avatar
0 votes
0 answers
42 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 ...
user avatar
  • 2,975
1 vote
0 answers
20 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 ...
user avatar
0 votes
0 answers
44 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 ...
user avatar
1 vote
1 answer
79 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} + \...
user avatar
  • 113
4 votes
1 answer
84 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 ...
user avatar
0 votes
1 answer
186 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. ...
user avatar
  • 323
3 votes
1 answer
128 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, ...
user avatar
3 votes
1 answer
684 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 ...
user avatar
3 votes
2 answers
223 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 ...
user avatar
1 vote
0 answers
41 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_{...
user avatar
5 votes
1 answer
163 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 ...
user avatar
1 vote
1 answer
41 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 ...
user avatar
2 votes
1 answer
99 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 ...
user avatar
1 vote
0 answers
63 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 ...
user avatar
  • 121
2 votes
1 answer
69 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.
user avatar
  • 239
2 votes
1 answer
730 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-...
user avatar
1 vote
0 answers
59 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 ...
user avatar
0 votes
0 answers
96 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 ...
user avatar
2 votes
1 answer
103 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_{...
user avatar
  • 53
0 votes
1 answer
50 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 ...
user avatar
  • 295
5 votes
1 answer
908 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-...
user avatar
  • 153
2 votes
1 answer
227 views

In what RL algorithm category is MiniMax?

Q-learning is a temporal-difference method and Monte Carlo tree search is a Monte Carlo method. In what category is MiniMax?
user avatar
  • 573
2 votes
1 answer
297 views

What are episodic and non-episodic domains in reinforcement learning?

I was reading about the temporal difference (TD) learning and I read that: TD handles continuing, non-episodic domains Assuming that continuing means non-terminating, what does non-episodic or ...
user avatar
  • 512
2 votes
1 answer
43 views

Equivalence between expected parameter increments in "Off-Policy Temporal-Difference Learning with Function Approximation"

I am having a hard time understanding the proof of theorem 1 presented in the "Off-Policy Temporal-Difference Learning with Function Approximation" paper. Let $\Delta \theta$ and $\Delta \...
user avatar
1 vote
0 answers
58 views

Is the TD-residual defined for timesteps $t$ past the length of the episode?

Let $\mathcal{S}$ be the state-space in a reinforcement learning problem where rewards are in $\mathbb{R}$, and let $V:\mathcal{S} \to \mathbb{R}$ be an approximate value function. Following the GAE ...
user avatar
  • 133
1 vote
1 answer
58 views

Are there known error bounds for TD(0) with a constant learning rate?

Is there any known error bounds for the TD(0) algorithm for the value function after a finite number of iterations? $$ \Delta_t=\max_{s \in \mathcal{S}}|v_t(s)-v_\pi(s)|$$ $$v_{t+1}(s_t)=v_t(s_t)+\...
user avatar
  • 309
1 vote
0 answers
89 views

Does SARSA(0) converge to the optimal policy in expectation if the Robbins-Monro conditions are removed?

The conditions of convergence of SARSA(0) to the optimal policy are : The Robbins-Monro conditions above hold for $α_t$. Every state-action pair is visited infinitely often The policy is greedy with ...
user avatar
  • 309
1 vote
1 answer
294 views

Does TD(0) prediction require Robbins-Monro conditions to converge to the value function?

Does the learning rate parameter $\alpha$ require the Robbins-Monro conditions below for the TD(0) algorithm to converge to the true value function of a policy? $$\sum \alpha_t =\infty \quad \text{...
user avatar
  • 309
3 votes
1 answer
1k views

Is there a simple proof of the convergence of TD(0)?

Does anybody know a simple proof of the convergence of the TD(0) value function prediction algorithm?
user avatar
  • 309
5 votes
1 answer
455 views

Why not more TD(𝜆) in actor-critic algorithms?

Is there either an empirical or theoretical reason that actor-critic algorithms with eligibility traces have not been more fully explored? I was hoping to find a paper or implementation or both for ...
user avatar
  • 115
3 votes
1 answer
405 views

How does Monte Carlo have high variance?

I was going through David Silver's lecture on reinforcement learning (lecture 4). At 51:22 he says that Monte Carlo (MC) methods have high variance and zero bias. I understand the zero bias part. It ...
user avatar
6 votes
2 answers
2k views

What is the intuition behind TD($\lambda$)?

I'd like to better understand temporal-difference learning. In particular, I'm wondering if it is prudent to think about TD($\lambda$) as a type of "truncated" Monte Carlo learning?
user avatar
  • 115
4 votes
1 answer
179 views

What is the intuition behind the TD(0) equation with average reward, and how is it derived?

In chapter 10 of Sutton and Barto's book (2nd edition) is given the equation for TD(0) error with average reward (equation 10.10): $$\delta_t = R_{t+1} - \bar{R} + \hat{v}(S_{t+1}, \mathbf{w}) - \hat{...
user avatar