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

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


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

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


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

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


4

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


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

The more you read, the more deeply you can understand any paper, but given your stated background, reading the Monte-Carlo Tree Search chapter of Barto & Sutton, plus Gerald Tesauro's TD-Gammon paper (which is pretty accessible, and which is the basis for the other technique used in AlphaZero) should be enough to get a pretty good idea of what they did.


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

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

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

First note that $\mathbb{E}[R_{t+1} |S_t=s] = \sum_{s',r}rm(s',r|s)$ where $m(\cdot)$ is the mass function for the joint distribution of $S_{t+1},R_{t+1}$. If you are currently in state $S_t$ and we condition on taking action $a$ then the expected reward at time $t+1$ is given as follows: \begin{align} \mathbb{E}[R_{t+1} | S_t = s, A_t=a] & = \sum_{s',...


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

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

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

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

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


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

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

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

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


2

In the PDF of the original paper for UCB1 you linked, in page 242-243 the authors proves why non-optimal machines get played much less (in fact, logarithmically less) than the optimal ones. $c$ decides whether they indeed would, and $c=\sqrt{2}$ is the minimum choice of $c$. We want to show that the number of runs for non-optimal machines ($n_i$, for non-...


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