14
votes
Accepted
What algorithms are considered reinforcement learning algorithms?
The dynamic programming (DP) algorithms like policy iteration (PI) and value iteration (VI) are often presented in the context of reinforcement learning (in particular, in the book Reinforcement ...
- 39.7k
8
votes
Accepted
How to show temporal difference methods converge to MLE?
The convergence and optimality proofs of (linear) temporal-difference methods (under batch training, so not online learning) can be found in the paper Learning to predict by the methods of temporal ...
- 39.7k
7
votes
Accepted
Can TD($\lambda$) be used with deep reinforcement learning?
Eligibility traces is a method of weighting between temporal-difference "targets" and Monte-Carlo "returns". In practice, for example, instead of using the one-step TD target, $r_t ...
- 39.7k
6
votes
Accepted
What are the conditions of convergence of temporal-difference learning?
There are different TD algorithms, e.g. Q-learning and SARSA, whose convergence properties have been studied separately (in many cases).
In some convergence proofs, e.g. in the paper Convergence of ...
- 39.7k
6
votes
Accepted
Why does TD Learning require Markovian domains?
The Markov assumption is used when deriving the Bellman equation for state values:
$$v(s) = \sum_a \pi(a|s)\sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$
One requirement for this equation to hold is that ...
- 30.4k
6
votes
Why is the target called "target" in Monte Carlo and TD learning if it is not the true target?
It is our "current" target. We assume that the value we get now is at least a closer approximation to the "true" target.
We're not so much moving towards a wrong value as we are ...
5
votes
How do temporal-difference and Monte Carlo methods work, if they do not have access to model?
The main idea is that you can estimate $V^\pi(s)$, the value of a state $s$ under a given policy $\pi$, even if you don't have a model of the environment, by visiting that state $s$ and following the ...
- 202
5
votes
Accepted
Understanding the equation of TD(0) in the paper "Learning to predict by the methods of temporal differences"
When lambda = 0 as in TD(0), how does the method learn? As it appears, with lambda = 0, there will never be a change in weight and hence no learning.
I think the detail that you're missing is that ...
- 10.1k
5
votes
Accepted
What is the intuition behind TD($\lambda$)?
TD($\lambda$) can be thought of as a combination of TD and MC learning, so as to avoid to choose one method or the other and to take advantage of both approaches.
More precisely, TD($\lambda$) is ...
- 39.7k
4
votes
Accepted
Confusion about temporal difference learning
My first question is whether the following "implementation" of the 𝑇𝐷(0) algorithm for the first two of the above observed trajectories correct?
$V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad ...
- 30.4k
4
votes
What algorithms are considered reinforcement learning algorithms?
In Reinforcement Learning: An Introduction the authors suggest that the topic of reinforcement learning covers analysis and solutions to problems that can be framed in this way:
Reinforcement ...
- 30.4k
4
votes
Accepted
What is the intuition behind the TD(0) equation with average reward, and how is it derived?
This is simply from definition of return in average reward setting (look at equation $10.9$). The "standard" TD error is defined as
\begin{equation}
TD_{\text{error}} = R_{t+1} + V(S_{t+1}) - V(S_t)
\...
- 2,336
4
votes
Accepted
How fast does Monte Carlo tree search converge?
Yes, Monte Carlo tree search (MCTS) has been proven to converge to optimal solutions, under assumptions of infinite memory and computation time. That is, at least for the case of perfect-information, ...
- 10.1k
4
votes
Accepted
Why am I getting the incorrect value of lambda?
$TD(\lambda)$ return has the following form:
\begin{equation}
G_t^\lambda = (1 - \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n}
\end{equation}
For you MDP $TD(1)$ looks like this:
\begin{align}
...
- 2,336
4
votes
Accepted
How is $\Delta$ updated in true online TD($\lambda$)?
Let us denote the state we are in at time $t$ by $S_t$. Then at iteration $t$ we create a placeholder $V_{old} = V(S_{t+1})$ for the state we will transition into. We then update the value function $V(...
- 4,685
4
votes
Accepted
Into which subcategories can reinforcement learning be divided?
Your two suggestions are not mutually exclusive. If you go by this process, you'll have to do a "Cartesian product" of a bunch of different RL categorizations which would get out of hand. I ...
- 1,126
4
votes
How to determine if Q-learning has converged in practice？
A typical and practical way to measure the convergence to some solution (so not necessarily the optimal one!) of any numerical iterative algorithm (such as RL algorithms) is to check if the current ...
- 39.7k
3
votes
Accepted
What is the bias-variance trade-off in reinforcement learning?
The bias-variance trade-off that you're referring to has to do with the return estimator. Any RL algorithm you choose needs some estimate of the cumulative return, which is a random variable with many ...
- 1,126
3
votes
Accepted
What is correct update when the some indexes are not available?
What you are referring to as the situation where
some indexes are not available
is simply the situation where some actions are not available/valid in some state. So, yes, the ${\arg \max }$ will ...
- 722
3
votes
In what RL algorithm category is MiniMax?
I think you are looking at it from the wrong direction, min-max is just a planning algorithm, decision strategy, in the sense that you are describing other algorithms/methods it does not have a ...
- 77
3
votes
Is there a simple proof of the convergence of TD(0)?
As far as I know, there is no very simple proof of the convergence of temporal-difference algorithms. The proofs of convergence of TD algorithms are often based on stochastic approximation theory (...
- 39.7k
3
votes
What is the relation between Monte Carlo and model-free algorithms?
In Reinforcement Learning (RL), the use of the term Monte Carlo has been slightly adjusted by convention to refer to only a few specific things.
The more general use of "Monte Carlo" is for ...
- 30.4k
3
votes
Accepted
Understanding the n-step off-policy SARSA update
Multiplying the entire update by $\rho$ has the desirable property that experience affects $Q$ less when the behavior policy is unrelated to the target policy. In the extreme, if the trajectory taken ...
- 2,038
3
votes
Accepted
Why isn't it wise for us to completely erase our old Q value and replace it with the calculated Q value?
Removing the learning rate will likely yield poor convergence to the optimal policy and optimal Q-values. Note that the current policy is completely dependent on the Q-values, as we take the action ...
- 1,332
3
votes
Accepted
Is the expected value we sample in TD-learning action-value Q or state-value V?
However, from the blogs and texts I read, the equations are expressed in terms of V and NOT Q. Why is that?
MC and TD are methods for associating value estimates to time step based on experienced ...
- 30.4k
3
votes
Accepted
When calculating the cost in deep Q-learning, do we use both the input and target states?
I will first explain briefly to you the difference between supervised learning and reinforcement learning to make sure that you don't have any misunderstandings. In supervised learning you are ...
- 4,685
2
votes
Why is $M_t$ (the emphasis) helping in correcting for the state distribution in the Emphatic TD algorithm?
I don't think the section was written in haste. I think they just didn't have space to include the whole proof. It's a bit involved, so they just gave concepts.
An Emphatic Approach to the Problem
...
- 2,038
2
votes
Convergence of semi-gradient TD(0) with non-linear function approximation
Apparently there is an example of non-convergence for semi-gradient sarsa, according to Rich Sutton (check slide 35). I guess TD(0) is not so different. So, probably your approximator will need to ...
- 395
2
votes
Accepted
By learning from incomplete episodes, does David Silver mean learning of $V(s)$ even when the episode is not completed?
The $TD(0)$ algorithm learns from incomplete episodes, but in the earlier algorithm we can see that the loop repeats until $s$ is terminal which mean completion of episode.
In the pseudocode, you ...
- 39.7k
Only top scored, non community-wiki answers of a minimum length are eligible