9 votes
Accepted

Why does the discount rate in the REINFORCE algorithm appear twice?

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 ...
user avatar
  • 23.1k
9 votes

How do we prove the n-step return error reduction property?

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}$: \...
user avatar
  • 9,316
7 votes
Accepted

How is the policy gradient calculated in REINFORCE?

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 ...
user avatar
6 votes

Why does the discount rate in the REINFORCE algorithm appear twice?

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 ...
user avatar
  • 9,316
6 votes

What is the difference between reinforcement learning and optimal control?

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 ...
user avatar
  • 961
6 votes
Accepted

Why does the definition of the reward function $r(s, a, s')$ involve the term $p(s' \mid s, a)$?

Expectation of reward after taking action $a$ in state $s$ and ending up in state $s'$ would simply be \begin{equation} r(s, a, s') = \sum_{r \in R} r \cdot p(r|s, a, s') \end{equation} The problem ...
user avatar
  • 2,216
5 votes
Accepted

How can the importance sampling ratio be different than zero when the target policy is deterministic?

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 ...
user avatar
  • 9,316
5 votes
Accepted

How can the $\lambda$-return be defined recursively?

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 ...
user avatar
5 votes
Accepted

If $\gamma \in (0,1)$, what is the on-policy state distribution for episodic tasks?

This question is really getting at the meaning of the discount factor in Markov decision processes. There are actually two, equivalent ways of interpreting the discount factor. The first is probably ...
user avatar
  • 746
4 votes
Accepted

Expected SARSA vs SARSA in "RL: An Introduction"

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 ϵ-...
user avatar
  • 490
4 votes
Accepted

What knowledge is required for understanding the AlphaZero paper?

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 ...
user avatar
4 votes

Counterexamples to the reward hypothesis

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. ...
user avatar
  • 141
4 votes
Accepted

How to express $v_\pi(s)$ in terms of $q_\pi(s,a)$?

isn't then $v_\pi(s)$ just the expected action value function at $s$ over all actions $a$ that are given by the policy $\pi$, namely $v_\pi(s) = E_{a \sim \pi}[q_\pi(s,a) | S_t = s, A_t = a] = \sum_{...
user avatar
  • 23.1k
3 votes
Accepted

Understanding the n-step off-policy SARSA update

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 ...
user avatar
3 votes
Accepted

How do I apply the value iteration algorithm when there are two goal states?

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 ...
user avatar
  • 2,216
3 votes

Is my interpretation of the return correct?

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 ...
user avatar
  • 23.1k
3 votes

Why does the discount rate in the REINFORCE algorithm appear twice?

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) ...
user avatar
  • 131
3 votes

How do compute the table for $p(s',r|s,a)$ (exercise 3.5 in Sutton & Barto's book)?

The function $r(s,a,s')$ gives the expected reward in each scenario, but not the distribution of rewards that lead to values $r_{search}$ and $r_{wait}$ The text explains that reward is $+1$ for ...
user avatar
  • 23.1k
3 votes
Accepted

On-policy state distribution for episodic tasks on Sutton & Barto, page 199

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 ...
user avatar
  • 2,216
3 votes
Accepted

If the current state is $S_t$ and the actions are chosen according to $\pi$, what is the expectation of $R_{t+1}$ in terms of $\pi$ and $p$?

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 ...
user avatar
3 votes
Accepted

Why is there an inconsistency between my calculations of Policy Iteration and this Sutton & Barto's diagram?

Your calculations are correct, but you have misinterpreted the equations and the diagram. The index $k$ in $v_k$ for the diagram refers to the policy evaluation update iteration only, and is not ...
user avatar
  • 23.1k
3 votes
Accepted

How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling", in the proof of the policy gradient theorem?

The unrolling step is due to the fact you end up with an equation that you can keep expanding indefinitely. Note that we start with calculating $\nabla v_\pi(s)$ and arrive at $$\nabla v_\pi(s) = \...
user avatar
3 votes
Accepted

Value Iteration failing to converge to optimal value function in Sutton-Barto's Gambler problem

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 ...
user avatar
  • 436
3 votes
Accepted

What is wrong with equation 7.3 in Sutton & Barto's book?

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 ...
user avatar
3 votes
Accepted

Why do all states appear identical under the function approximation in the Short Corridor task?

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 ...
user avatar
3 votes
Accepted

How do we derive the expression for average reward setting in continuing tasks?

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 ...
user avatar
3 votes
Accepted

Is the existence and uniqueness of the state-value function for $\gamma < 1$ theoretical?

In essence, your question is about convergence of infinite series. The mathematical discipline that studies such series is hundreds (if not thousands) years old an has nothing to do with "...
user avatar
  • 1,763
2 votes
Accepted

Where are the parentheses in the definition of $r(s,a)$?

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 ...
user avatar
  • 23.1k
2 votes

How can the Cart Pole problem be a continuing task?

It's a continuing task in that, after failure, the agent always gets a reward of $0$ at each time-step ad infinitum. From the book: we could treat pole-balancing as a continuing task, using ...
user avatar
2 votes

How do compute the table for $p(s',r|s,a)$ (exercise 3.5 in Sutton & Barto's book)?

At first, like Neil Slater says, I thought this could only be solved using the expected rewards instead of actual rewards, or else there wasn't enough information to solve it. But now I think there ...
user avatar
  • 171

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