5

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 one of the terms in the sum (the final "iteration" of the sum, the case where $k = t$) has $\lambda$ raised to the power $0$, and anything raised to the power $0$...


4

$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} G &= 0.64 (r_0 + r_2 + r_4 + r_5 + r_6) + 0.36(r_1 + r_3 + r_4 + r_5 + r_6)\\ G &\approx 6.164 \end{align} $TD(\lambda)$ looks like this: \begin{...


4

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 policy $\pi$ after that state. If you repeat this process many times, you'll get many samples of trajectories starting at $s$ with some total return associated ...


4

Eligibility traces is a method of weighting between temporal-difference "targets" and Monte-Carlo "returns. In practice, e.g., instead of using the one-step TD target, $r_t + \gamma V (s_{t+1})$, as in the temporal difference update $V (s_t) \leftarrow V (s_t) + \alpha (r_t + \gamma V (s_{t+1}) − V (s_t))$, you use the so-called "lambda" ($\lambda$) target, ...


4

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 differences (1988) by Richard Sutton, specifically section 4 (p. 23). In this paper, Sutton uses a different notation than the notation used in the famous book ...


4

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(s) \; \forall s \in \mathcal{S}$ - i.e. we update the value function for all states in our state space. Let us denote this updated value function by $V'(S)$. ...


4

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 recommend, if you can, to describe some sort of "RL taxonomy" instead. By this I mean describing different RL characterizations without assuming they'...


3

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 V(b)\leftarrow0+0.1(1+0-0)=0.1$ $V(b)\leftarrow0.1+(0.1)(1+0-0.1)= 0.19$ Your calculations for the first trajectory $(A,1,B,0)$ is incorrect for either TD or ...


3

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 with highest Q-value in a given state (with a few other considerations such as exploration, etc.). If we were to remove the learning rate, then we are making a ...


3

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 be calculated based only on the available actions in that state. More formally, $$\underset{a \in \mathcal{A}(s)}{\arg \max } \, Q(s, a)$$ where $Q(s,a)$ has ...


3

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 category. For example, you have negamax algorithm which is in a sense the same thing the Monte Carlo Search Tree is to Monte Carlo. Min-max category is game theory ...


3

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) \end{equation} In average reward setting, average reward $r(\pi)$ is subtracted from reward at $t$, $R_t$, so TD error in this case is \begin{equation} TD_{\text{...


3

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, deterministic games / MDPs. Maybe some other problems were covered too by some proofs (I could intuitively imagine the proofs holding up for non-deterministic ...


2

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 simulation methods that use random numbers to sample - often as a replacement for an otherwise difficult analysis or exhaustive search. In RL, Monte Carlo methods are ...


2

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 have two loops: one for each episode and one (nested) for each step of the episode. The until $S$ is terminal means that you perform the updates until you end the ...


2

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 Q-learning: A Simple Proof (by Francisco S. Melo), the required conditions for Q-learning to converge (in probability) are the Robbins-Monro conditions $\sum_{...


2

When using terms like "high" for high variance, this is in comparison to other methods, mainly in comparison to TD learning, which bootstraps between single time steps. It is worth spelling out what the variance applies to and where it comes from: Namely the Monte Carlo return $G_t$ distribution, which can be calculated as follows: $$G_t = \sum_{k=0}^{T-t-...


2

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 sources of randomness, such as stochastic transitions or rewards. Monte Carlo RL algorithms estimate returns by running full trajectories and literally ...


1

A full Bellman update can be intractable. For instance, if your state space or action space are continuous, the full Bellman update is intractable. You can try to solve this by discretizing, but if your state space is large this will also be intractable.


1

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 temporal-difference learning with a $\lambda$-return, which is defined as an average of all $n$-step returns, for all $n$, where an $n$-step return is the target ...


1

Assuming that continuing means non terminating, what does non-episodic or episodic domain mean ? Non-episodic means the same as continuing. The quote you found is not listing two separate domains, the word "continuing" is slightly redundant. I expect the author put it in there to emphasise the meaning, or to cover two common ways of describing such ...


1

First part is correct \begin{align} &\sum_{n=1}^{\infty} \alpha(1-\lambda)\lambda^{n-1} (\bar R_t^{(n)} - \theta^T \phi_t)\\ =& \alpha[\sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \bar R_t^{(n)} - \sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \theta^T \phi_t] \end{align} $\sum_{n=1}^{\infty} (1-\lambda)\lambda^{(n-1)}$ sums to $1$ so we have \begin{...


1

The paper Convergence of Q-learning: A Simple Proof (by Francisco S. Melo) shows (theorem 1) that Q-learning, a TD(0) algorithm, converges with probability 1 to the optimal Q-function as long as the Robbins-Monro conditions, for all combinations of states and actions, are satisfied. In other words, the Robbins-Monro conditions are sufficient for Q-learning ...


1

Theoretically, nothing precludes the use of $\lambda$-returns in actor-critic methods. The $\lambda$-return is an unbiased estimator of the Monte Carlo (MC) return, which means they are essentially interchangeable. In fact, as discussed in High-Dimensional Continuous Control Using Generalized Advantage Estimation, using the $\lambda$-return instead of the MC ...


1

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 satisfy certain conditions to proof convergence. Maybe this paper will be useful for you. It seems that they show that constraining your network to have relu ...


1

The previous answer from Brale is mostly correct but is missing a large detail to get the precise answer. Given this is a question from a GT course homework, I only want to leave pointers so those seeking help can understand the required concept. 𝑇𝐷(𝜆) equation is a summation over infinite K-steps (𝐺0:1 -> 𝐺0:∞) and should be included in our equation ...


1

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 has zero probability under the target policy, then $Q$ isn't updated at all, which is good. Alternatively, if only $G$ is scaled by $\rho$, taking zero ...


1

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 of Off-policy Temporal-Difference Learning gives a proof of stability. At least parts of it should seem familiar if you've read Sutton and Barto's proof of the ...


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