2022 Developer Survey is open! Take survey.
12 votes
Accepted

What algorithms are considered reinforcement learning algorithms?

The dynamic programming algorithms (like policy iteration and value iteration) are often presented in the context of reinforcement learning (in particular, in the book Reinforcement Learning: An ...
user avatar
  • 33.1k
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 ...
user avatar
  • 33.1k
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 ...
user avatar
  • 33.1k
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 ...
user avatar
  • 23.3k
5 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 ...
user avatar
  • 33.1k
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 ...
user avatar
  • 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 ...
user avatar
  • 9,326
5 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 ...
user avatar
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 ...
user avatar
  • 23.3k
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 ...
user avatar
  • 23.3k
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) \...
user avatar
  • 2,226
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, ...
user avatar
  • 9,326
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} ...
user avatar
  • 2,226
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(...
user avatar
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 ...
user avatar
  • 961
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 ...
user avatar
  • 33.1k
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 ...
user avatar
  • 961
3 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 ...
user avatar
  • 33.1k
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 ...
user avatar
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 ...
user avatar
  • 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 (...
user avatar
  • 33.1k
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 ...
user avatar
  • 23.3k
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 ...
user avatar
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 ...
user avatar
  • 776
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 ...
user avatar
  • 23.3k
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 33.1k

Only top scored, non community-wiki answers of a minimum length are eligible