Skip to main content
10 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 ...
Neil Slater's user avatar
  • 32.7k
10 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}$: \...
Dennis Soemers's user avatar
  • 10.4k
10 votes
Accepted

What is the difference between reinforcement learning and optimal control?

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 ...
nbro's user avatar
  • 41k
9 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 ...
harwiltz's user avatar
  • 1,136
8 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 ...
Brale's user avatar
  • 2,406
7 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 ...
Dennis Soemers's user avatar
  • 10.4k
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 ...
Philip Raeisghasem's user avatar
7 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 ...
Philip Raeisghasem's user avatar
6 votes
Accepted

How do we express $q_\pi(s,a)$ as a function of $p(s',r|s,a)$ and $v_\pi(s)$?

Not quite. You are missing the reward at time step $t+1$. The definition you are looking for is (leaving out the $\pi$ subscripts for ease of notation) $$q(s,a) = \mathbb{E}[R_{t+1} + \gamma v(s') | ...
David's user avatar
  • 4,930
6 votes

In Value Iteration, why can we initialize the value function arbitrarily?

Is this something to do with the Bellman optimality constraint itself? That is part of it, and important for episodic problems without discounting. The Bellman equations link between time steps, ...
Neil Slater's user avatar
  • 32.7k
6 votes
Accepted

Sutton & Barto: what are parametrized functions?

A parameterized function is a function that is defined by a set of parameters. If you change the parameters, you also change the actual function. For example, let's define this linear function $$f: \...
nbro's user avatar
  • 41k
5 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 ...
David's user avatar
  • 4,930
5 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_{...
Neil Slater's user avatar
  • 32.7k
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 ...
Taw's user avatar
  • 1,291
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 ϵ-...
Phizaz's user avatar
  • 510
4 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 ...
Dennis Soemers's user avatar
  • 10.4k
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 ...
John Doucette's 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. ...
Kumar's user avatar
  • 141
4 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 ...
Robby Goetschalckx's user avatar
4 votes
Accepted

In Value Iteration, why can we initialize the value function arbitrarily?

If the value function of a state $v(s)$ is relatively high, then you are absolutely correct in saying that a greedy policy may choose to visit $s$, since the high $v(s)$ makes it very promising. The ...
DeepQZero's user avatar
  • 1,494
4 votes
Accepted

Why does REINFORCE perform badly at first in Sutton and Barto Figure 13.1?

I'm actually working on this example too, implemented the REINFORCE algorithm, and got the same result as you. My only guess is that the authors chose a different initial $\theta$ value to show the ...
gwtw14's user avatar
  • 156
4 votes
Accepted

Unclear paragraph in Sutton-Barto on exploration/exploitation relating to bandit like decision tasks

The quoted text is from the end of a paragraph that is explaining some aspects of bandit algorithms, and looking forward to how knowledge of them is applicable in a reinforcement learning context. ...
Neil Slater's user avatar
  • 32.7k
4 votes
Accepted

Where does the TD formula for tic-tac-toe in Sutton & Barto come from?

The equation (1) you mentioned is a simplified form of the temporal difference TD(0) update rule, specifically for the case of episodic tasks where there's no discounting $\gamma$ and the only reward ...
cinch's user avatar
  • 2,517
3 votes

What is the meaning of Model(s, a) in the prioritized sweeping algorithm?

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$ ...
Brale's user avatar
  • 2,406
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 ...
Brale's user avatar
  • 2,406
3 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 ...
Bijay Gurung's user avatar
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 ...
Neil Slater's user avatar
  • 32.7k
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) ...
toto2's 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 ...
Neil Slater's user avatar
  • 32.7k
3 votes
Accepted

Should the policy parameters be updated at each time step or at the end of the episode in REINFORCE?

The essence of your observation is that Sutton's version of REINFORCE is taking into consideration all of the trajectory to compute the returns, while in the pytorch version only the future is taken ...
Dimitris Monroe's user avatar

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