Questions tagged [temporal-difference]

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
1answer
22 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
votes
1answer
63 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 ...
1
vote
0answers
16 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 ...
2
votes
1answer
31 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.
2
votes
1answer
39 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-...
1
vote
0answers
32 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 ...
0
votes
0answers
38 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 ...
2
votes
1answer
55 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_{...
0
votes
1answer
38 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 ...
3
votes
1answer
71 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-...
2
votes
1answer
53 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?
1
vote
1answer
27 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 ...
2
votes
1answer
22 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 \...
1
vote
0answers
18 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 ...
1
vote
1answer
30 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)+\...
1
vote
0answers
22 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 ...
1
vote
1answer
62 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{...
1
vote
1answer
166 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?
4
votes
1answer
81 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 ...
3
votes
1answer
87 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 ...
1
vote
2answers
156 views

Understanding the loss function in deep Q-learning

I am trying to understand how deep Q learning (DQN) works. To my current understanding, each $Q(s, a)$ functions is estimated to be a function of a feature vector of its state $\phi$(s) and the weight ...
5
votes
1answer
119 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?
4
votes
1answer
71 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{...
1
vote
0answers
23 views

N-tuple based tic tac toe diverges in temporal difference learning

I have n-tuple based tic tac toe. I already have perfect minimax player and perfectly trained table-based player. My n-tuple network consists of 8 different rows of 3 of the board as triplets having ...
0
votes
0answers
29 views

How is the general return-based off-policy equation derived?

I'm wondering how is the general return-based off-policy equation in Safe and efficient off-policy reinforcement learning derived $$\mathcal{R} Q(x, a):=Q(x, a)+\mathbb{E}_{\mu}\left[\sum_{t \geq 0} \...
4
votes
1answer
87 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 (...
3
votes
1answer
44 views

Confusion about temporal difference learning

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(...
3
votes
1answer
221 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?
1
vote
1answer
142 views

Understanding TD(0) algorithm implementation

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 $...
1
vote
0answers
40 views

How do I know if the assumption of a static environment is made?

An important property of a reinforcement learning problem is whether the environment of the agent is static, which means that nothing changes if the agent remains inactive. Different learning methods ...
5
votes
1answer
314 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+...
2
votes
0answers
75 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 ...
5
votes
2answers
417 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 ...
1
vote
0answers
23 views

Why should we use TD prediction as opposed to TD control algorithms?

Consider a problem where we have a finite number of states and actions. Given a state and an action, we can easily know the reward and the next state (deterministic). The state space is really large ...
2
votes
1answer
112 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 ...
3
votes
1answer
383 views

How fast does Monte Carlo tree search converge?

How fast does Monte Carlo Tree Search converge? Is there proof that it does converge? How does it compare to Temporal Difference learning in terms of convergence speed (assuming the evaluation step ...
3
votes
1answer
130 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 $...
1
vote
1answer
58 views

On-policy distribution for Emphatic TD

The book by Sutton and Barto discussed in section 11.8 that the convergence of off-policy TD function approximation can be improved by correcting for distribution of states encountered. The section ...
4
votes
1answer
99 views

What are temporal-difference and Monte Carlo methods intuitively?

Intuitively, how do temporal-difference and Monte Carlo methods work in reinforcement learning? How can they be used to solve the reinforcement learning problem?
4
votes
1answer
1k 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 ...