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


5

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


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


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

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


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

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

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


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

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


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


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


1

It would be heplful for me if you specify the section and page number of the Sutton's book. But as far as I understand your question I will try explain this. Think of TD update. The sample contains $(s_t,a_t,r_{t+1},s_{t+1})$. Using incremental update we can write: $$ v_{t}(s) = \frac{1}{t} \sum_{j=1}^{t}(r_{t+1} + \gamma v_{s_{t+1}})$$ $$ v_{t}(s) = v_{t-1}(...


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

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 "Bias-Variance" Error Bounds for Temporal Difference Updates (2000) by M. Kearns and S. Singh provides error bounds for temporal-difference algorithms, i.e. TD($k$) and TD($\lambda$) (see theorem 1 and theorem 2, respectively). Note that both TD($k$) and TD($\lambda$) include TD($0$) as a special case.


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

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


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

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

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


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