9

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


8

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


6

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


5

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


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


4

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


4

As a supplement to nbro's nice answer, I think a major difference between RL and optimal control lies in the motivation behind the problem you're solving. As has been pointed out by comments and answers here (as well as the OP), the line between RL and optimal control can be quite blurry. Consider the Linear-Quadratic-Gaussian (LQG) algorithm, which is ...


4

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


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

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) =\\...


3

In general, $\mathbb{E}_\pi[G_{t:t+n}|S_t = s] \neq v_\pi(s)$. $v_\pi(s)$ is defined as $\mathbb{E}_\pi[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s]$, so you should be able to see why the two are not equal when the LHS is an expectation of the $n$th step return. They would only be equal as $n \rightarrow \infty$.


3

So, naturally, if you've observed something that contradicts the theoretical properties of Value Iteration, something's wrong, right? Well, the code you've linked, as it is, is fine. It works as intended when all the values are initialized to zero. HOWEVER, my guess is that you're the one introducing an (admittedly very subtle) error. I think you're changing ...


3

What if a scalar reward is insufficient, or its unclear on how to collapse a multi-dimensional reward to a single dimension. Example, for someone eating a burger, both taste and cost are important. Agents may prioritize taste and cost differently, so its not clear on how to aggregate the two. It is also not clear on how a subjective categorical taste value ...


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

You can choose those states, but is the agent aware of the state it is in? From the text, it seems that the agent cannot distinguish between the three states. Its observation function is completely uninformative. This is why a stochastic policy is what is needed. This is common for POMDPs, whereas for regular MDPs we can always find a deterministic policy ...


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

The same book Reinforcement learning: an introduction (2nd edition, 2018) by Sutton and Barto has a section, 1.7 Early History of Reinforcement Learning, that describes what optimal control is and how it is related to reinforcement learning. I will quote the most relevant part to answer your question, but you should read all that section to have a full ...


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

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


2

Let's first clarify a couple of details: The policy $\pi$ we're talking about is an $\epsilon$-soft policy (defined to mean that $\pi(a \vert s) \geq \frac{\epsilon}{\vert \mathcal{A}(s) \vert}$ for all states and all actions). We're not trying to prove equality of $v_{\pi}$ and $v_*$, but of $v_{\pi}$ and $\tilde{v}_*$, where $\tilde{v}_*$ denotes the ...


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

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


2

We assume that our MDP is ergodic. Loosely speaking, this means that wherever the MDP starts (i.e. no matter which state we start in) or any actions the agent takes early on can only have a limited effect on the MDP and in the limit (as $t \rightarrow \infty$) the expectation of being in a given state depends only on the policy $\pi$ and the transition ...


2

$\mu(s)$ is not in equation (9.4) because we are assuming that the examples by which we update our parameter $w$, i.e. the frequency of which we will observe the states during online training, is the same. That is, it is a constant with respect to $w$ and since we are differentiating it can be somewhat disregarded as a constant of proportionality -- it ...


1

I believe that there is no clear answer to your question. It essentially boils down to whether you are a reductionist – whether you believe that quantitative measurements can truly give justice to the complexity of the real world, and that a framework such as expectation maximization can losslessly capture what we care about as humans in the performing of ...


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


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