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
11 votes
3 answers
1k views

What algorithms are considered reinforcement learning algorithms?

What are the areas/algorithms that belong to reinforcement learning? TD(0), Q-Learning and SARSA are all temporal-difference algorithms, which belong to the reinforcement learning area, but is there ...
Miguel Saraiva's user avatar
9 votes
2 answers
6k 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?
Nick Kunz's user avatar
  • 145
6 votes
1 answer
1k views

How to show temporal difference methods converge to MLE?

In chapter 6 of Sutton and Barto (p. 128), they claim temporal difference converges to the maximum likelihood estimate (MLE). How can this be shown formally?
fool's user avatar
  • 203
6 votes
1 answer
3k views

Can TD($\lambda$) be used with deep reinforcement learning?

TD lambda is a way to interpolate between TD(0) - bootstrapping over a single step, and, TD(max), bootstrapping over the entire episode length, or, Monte Carlo. Reading the link above, I see that an ...
Gulzar's user avatar
  • 749
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-...
MJeremy's user avatar
  • 163
6 votes
1 answer
754 views

Convergence of semi-gradient TD(0) with non-linear function approximation

I am looking for a result that shows the convergence of semi-gradient TD(0) algorithm with non-linear function approximation for on-policy prediction. Specifically, the update equation is given by (...
srinivas tunuguntla's user avatar
6 votes
2 answers
548 views

Understanding the n-step off-policy SARSA update

In Sutton & Barto's book (2nd ed) page 149, there is the equation 7.11 I am having a hard time understanding this equation. I would have thought that we should be moving $Q$ towards $G$, where $...
Antoine Savine's user avatar
5 votes
1 answer
447 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 ...
stoic-santiago's user avatar
5 votes
1 answer
575 views

Understanding the equation of TD(0) in the paper "Learning to predict by the methods of temporal differences"

In the paper Learning to predict by the methods of temporal differences (p. 15), the weights in the temporal difference learning are updated as given by the equation $$ \Delta w_t = \alpha \left(P_{t+...
Amanda's user avatar
  • 205
5 votes
2 answers
1k views

Why am I getting the incorrect value of lambda?

I am trying to solve for $\lambda$ using temporal-difference learning. More specifically, I am trying to figure out what $\lambda$ I need, such that $\text{TD}(\lambda)=\text{TD}(1)$, after one ...
Amanda's user avatar
  • 205
5 votes
1 answer
168 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 ...
A Yoghes's user avatar
5 votes
1 answer
950 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 ...
Nick Kunz's user avatar
  • 145
4 votes
2 answers
312 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 ...
Chukwudi Ogbonna's user avatar
4 votes
1 answer
176 views

How do temporal-difference and Monte Carlo methods work, if they do not have access to model?

In value iteration, we have a model of the environment's dynamics, i.e $p(s', r \mid s, a)$, which we use to update an estimate of the value function. In the case of temporal-difference and Monte ...
strongguy122's user avatar
4 votes
1 answer
313 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{...
Maverick Meerkat's user avatar
4 votes
1 answer
999 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 ...
Bhuwan Bhatt's user avatar
4 votes
1 answer
192 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 ...
dezdichado's user avatar
3 votes
1 answer
2k 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 ...
WANGWANGZI's user avatar
3 votes
1 answer
197 views

Confusion about temporal difference learning [closed]

I have a couple of small questions about the David Silver lecture about reinforcement learning, lecture slides (slides 23, 24). More specifically it is about the temporal difference algorithm: $$V(...
Sebastian's user avatar
  • 165
3 votes
1 answer
2k views

How fast does Monte Carlo tree search converge?

How fast does Monte Carlo Tree Search converge? Is there a proof that it converges? How does it compare to temporal-difference learning in terms of convergence speed (assuming the evaluation step is a ...
ATidedHumour's user avatar
3 votes
1 answer
208 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, ...
Aung Khant's user avatar
3 votes
1 answer
1k 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?
mason7663's user avatar
  • 613
3 votes
1 answer
2k 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?
KaneM's user avatar
  • 309
3 votes
1 answer
147 views

Convergence of epsilon greedy policy (with no epsilon decay) using TD Learning?

If I create a policy using the q-values of an epsilon greedy policy using the Sarsa algorithm (not changing the epsilon with each episode), will it converge to the optimal solution to the MDP? I am ...
Prabhjot Singh Rai's user avatar
2 votes
1 answer
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 ...
jackless's user avatar
2 votes
1 answer
189 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_{...
roy's user avatar
  • 53
2 votes
2 answers
760 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 ...
XXX's user avatar
  • 143
2 votes
1 answer
86 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.
Chukwudi's user avatar
  • 359
2 votes
1 answer
2k 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-...
Aman Savaria's user avatar
2 votes
1 answer
912 views

What is the relation between Monte Carlo and model-free algorithms?

Monte Carlo (MC) methods are methods that use some form of randomness or sampling. For example, we can use an MC method to approximate the area of a circle inside a square: we generate random 2D ...
nbro's user avatar
  • 40.2k
2 votes
1 answer
445 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(...
KoKlA's user avatar
  • 133
2 votes
1 answer
309 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: ...
user529295's user avatar
2 votes
1 answer
771 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 ...
devidduma's user avatar
  • 552
2 votes
1 answer
96 views

Why is $M_t$ (the emphasis) helping in correcting for the state distribution in the Emphatic TD algorithm?

The book by Sutton and Barto discusses in section 11.8 that the convergence of off-policy TD function approximation can be improved by correcting for the distribution of states encountered. The ...
pg2455's user avatar
  • 221
2 votes
1 answer
71 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} \...
DSPinfinity's user avatar
2 votes
1 answer
511 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. ...
John Rothman's user avatar
2 votes
1 answer
51 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 \...
A M's user avatar
  • 23
2 votes
0 answers
254 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 ...
XXX's user avatar
  • 143
2 votes
1 answer
57 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 ...
Prakash Gawas's user avatar
2 votes
0 answers
169 views

Infinite horizon in Reinforcement Learning

I read this article: "Towards Autonomous Data Ferry Route Design through Reinforcement Learning" by Daniel Henkel and Timothy X Brown. It specifies an infinite horizon problem where they use as a ...
Miguel Saraiva's user avatar
1 vote
2 answers
63 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$ ...
Onil90's user avatar
  • 183
1 vote
1 answer
220 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-...
Multihunter's user avatar
1 vote
1 answer
346 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 ...
heiyezhu6324's user avatar
1 vote
1 answer
276 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} + \...
Cauchy's user avatar
  • 113
1 vote
1 answer
828 views

By learning from incomplete episodes, does David Silver mean learning of $V(s)$ even when the episode is not completed?

I came across the $TD(0)$ algorithm from Sutton and Barto: Clearly, the only difference of TD methods with the MC methods is that TD method is not waiting till the end of the episode to update the $...
user avatar
1 vote
1 answer
74 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) ...
FluidMechanics Potential Flows's user avatar
1 vote
1 answer
345 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 ...
Kareit's user avatar
  • 19
1 vote
1 answer
108 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 ...
user3489173's user avatar
1 vote
1 answer
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 ...
chessprogrammer's user avatar
1 vote
1 answer
79 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)+\...
KaneM's user avatar
  • 309