6

Let's start by looking at: $$\max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert.$$ We can rewrite this by plugging in the definition of $G_{t:t+n}$: \begin{aligned} & \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert \\ % =& \max_s \Bigl\lvert \mathbb{...


5

To rewrite $G_t^\lambda$ recursively, our goal is to define it in terms of $$G_{t+1}^\lambda = (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}G_{t+1:t+n+1}.\tag{0}$$ The $\lambda$-return is a weighted average of all $n$-step returns. We will split up the summation by pulling out the one-step return $G_{t:t+1}$ and the first step's reward $R_{t+1}$. $$ \begin{...


5

You're correct, when the target policy $\pi$ is deterministic, the importance sampling ratio will be $\geq 1$ along the trajectory where the behaviour policy $b$ happened to have taken the same actions that $\pi$ would have taken, and turns to $0$ as soon as $b$ makes one "mistake" (selects an action that $\pi$ would not have selected). Before importance ...


5

The discount factor does appear twice, and this is correct. This is because the function you are trying to maximise in REINFORCE for an episodic problem (by taking the gradient) is the expected return from a given (distribution of) start state: $$J(\theta) = \mathbb{E}_{\pi(\theta)}[G_t|S_t = s_0, t=0]$$ Therefore, during the episode, when you sample the ...


4

Neil's answer already provides some intuition as to why the pseudocode (with the extra $\gamma^t$ term) is correct. I'd just like to additionally clarify that you do not seem to be misunderstanding anything, Equation (13.6) in the book is indeed different from the pseudocode. Now, I don't have the edition of the book that you mentioned right here, but I ...


4

Classical reinforcement learning which was explained in the Arxiv-papers from 2000 to 2015 is equal to model-free learning. A problem was given, for example to solve a simple game, and the agent's policy gets learned in the q-matrix. Alternatively, a neural network was used to described the direct policy of the agent in the system. The so called state-action ...


3

The first part of this answer is a little background that might bolster your intuition for what's going on. The second part is the more practical and direct answer to your question. The gradient is just the generalization of the derivative to multivariable functions. The gradient of a function at a certain point is a vector that points in the direction of ...


3

What you could do is to trigger environment termination when rat either: steps into the trap picks both cheese pieces The problem with such setup is that, when the rat picks a single piece, it would move one step to the side, and then it would come back to the same cheese spot so it would keep exploiting the same spot indefinitely. The solution to ...


3

Advantage function: $A(s,a) = Q(s,a) - V(s)$ More interesting is the General Value Function (GVF), the expected sum of the (discounted) future values of some arbitrary signal, not necessarily reward. It is therefore a generalization of value function $V(s)$. The GVF is defined on page 459 of the 2nd edition of Sutton and Barto's RL book as $$v_{\pi,\gamma,C}...


3

Your table is almost correct. It is a minor difference, you should not have a $R_0$, the top row, leftmost column of numbers should be empty. That is because the first reward is $R_1$ (a result of taking action $A_0$ in state $S_0$). The alignment of the columns on the right hand side is correct though. It might help to add the time step number at the top. ...


3

It's a subtle issue. If you look at the A3C algorithm in the original paper (p.4 and appendix S3 for pseudo-code), their actor-critic algorithm (same algorithm both episodic and continuing problems) is off by a factor of gamma relative to the actor-critic pseudo-code for episodic problems in the Sutton and Barto book (p.332 of January 2019 edition of http://...


2

Your first option is correct: $$r(s,a) = \mathbb{E}\left[R_t|S_{t-1}=s,A_{t-1}=a\right]=\sum_{r\in \mathcal{R}}\left[r\sum_{s'\in \mathcal{S}}p(s',r|s,a)\right]$$ It's partly a matter of taste, but I prefer not moving the $r$ into the double sum, because its value does not change in the "inner loop". There is a small amount of intuition to be had that way ...


2

Is it just about final states? So for $s \in S$ when S is not final? You are thinking the right way, but to represent what you mean you don't need to write out "when $s$ is not final" - although that would be fine (and is used in some places), there is a more concise way of saying that given to you by the book. As this is a formal exercise from the book, ...


2

Why is the action selection random with Sarsa? A policy could be stochastic. In the case of SARSA, it is stochastic because of the use of $\epsilon$-greedy. Isn't it on-policy and therefore ϵ-greedy? I don't quite understand the question. SARSA is on-policy evaluation with $\epsilon$-greedy policy. Q-learning is off-policy evaluation with $\epsilon$-...


2

The left hand graphs are showing you the estimated value function from using Monte Carlo evaluation, after 10,000 episodes. They give a sense of what your value table will look like before convergence. In the case of upper "usable ace" chart, the estimates are still showing a lot of inaccuracy due to variance in the data. This is for two main reasons: The ...


2

You are missing that the expression $$\sum_{s'} \eta(s')$$ is already a count of the expected length of an episode, and is used in the denominator to scale $\mu(s)$ such that $\sum_{s} \mu(s) = 1$ So the length of the episode is taken into account in the formula. In practice you don't need to know $\mu(s)$, it can be left unresolved as a theoretical ...


2

Let's first assume that there is only one action so that $\pi(a|s) = 1$ for every state - action pair which simplifies the discussion. Now let's consider a case with 100 time steps, 10 states and uniform distribution for starting state $s_0$ with $h(s_0) = 1$. The result would be \begin{align} \eta(s_0) &= 1 + \sum_{i = 0}^9 \eta(s_i) \cdot p(s_0|s_i) =\\...


2

So, what is the purpose of the new index for $V$ in Chapter 7, and why is it more important at this particular chapter? My guess would be that your intuition is correct, and that it's mostly introduced just to clarify exactly which "version" of our value function approximator is going to be used in any particular equation. In previous chapters, which ...


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

Why don't they just update the value with a weight for the value from previous episodes $\alpha$ and a weight $1- \alpha$ for the new episode return as it is done in TD-Learning? In my opinion, this is a mistake in the book. I went back and checked that this is still the same in the finished second edition, and it is still there. Keeping all returns and ...


1

The true value $v_{\pi}(s)$ is a conceptual target for the $\overline{VE}$ in the book. You often do not know it in real problems. However, it is still used in two main ways in the book: Theoretically for analysis of different aprpoximation schemes, which can be shown to converge to minimise the $\overline{VE}$ objective, or a related one. In toy problems ...


1

Why are they comparing state value function to action value function? It is because $v_{\pi}(s)$ and $q_{\pi}(s,a)$ measure the same quantity at different stages of the trajectory. By comparing the values at the same $s$ and modifying how $a$ is selected, the proof makes assertions about how that choice impacts the value. It is important to recall that $v_{...


1

Good question. I think this part of the book is not well explained. Off-policy evaluation of V by itself doesn't make sense, IMO. I think there are two cases here - is if $\pi$ is deterministic, as we probably want in the case of "control", i.e. we will determine pi to be deterministic and in every state choose the action that most likely to maximize the ...


1

I think pseudocode was made for tabular case with an assumption of deterministic environment. $Model(s, a)$ would then be a table with information of the next state and reward after taking action $a$ from state $s$. The size of that table would be same as the size of Q table. Because the environment is deterministic you wouldn't take a random sample because ...


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