# Tag Info

12

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 Introduction by Barto and Sutton) because they are very related to reinforcement learning algorithms, like $Q$-learning. They are all based on the assumption that ...

7

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 ...

7

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 + \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 &...

6

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 $p(r,s'|s,a)$ is consistent. The current state $s$ is a key argument of that function. There is no adjustment for history of previous states, actions or ...

5

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 ...

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$...

5

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 moving away from a more wrong value. Of course, it is all base on random trials, so saying anything definite (such as: "we are guaranteed to improve at each ...

4

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 ...

4

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 learning, like many topics whose names end with “ing,” such as machine learning and mountaineering, is simultaneously a problem, a class of solution methods that ...

4

This is simply from definition of return in average reward setting (look at equation $10.9$). The "standard" TD error is defined as $$TD_{\text{error}} = R_{t+1} + V(S_{t+1}) - V(S_t)$$ In average reward setting, average reward $r(\pi)$ is subtracted from reward at $t$, $R_t$, so TD error in this case is TD_{\text{...

4

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 ...

4

$TD(\lambda)$ return has the following form: $$G_t^\lambda = (1 - \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n}$$ 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

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

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_{... 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'... 4 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 solution has not changed (much) with respect to the previous one. In your case, the solutions are value functions, so you could check if your algorithm 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 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 (given that e.g. Q-learning can be viewed as a stochastic process) and the work by Robbins and Monro (in fact, the Robbins-Monro conditions are usually assumed in ... 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 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 ... 3 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 ... 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 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 gained in later time steps. It does not matter what kind of value estimate is being associated across time, because all value functions are expressing the same ... 3 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 provided with some data$\{(\textbf{x}_i, y_i)\}_{i=1}^n$where$\textbf{x}_i$are the features for data point$i$and$y_i$is its true label. Now, the aim of ... 3 It should be noted that the selection of$\alphais a classic problem in stochastic approximation, rather than a specific problem in RL. Once you know this it will be clear. What is stochastic approximation? As its name suggests, it is a method that uses data to approximate (typically) expectations. For example, suppose \begin{align*} w=\mathbb{E}[X] \end{... 2 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 ... 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 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 ... 2 TheTD(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

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 ...

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