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 ...
- 33.3k
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}$:
\...
- 10.5k
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 ...
- 41.4k
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 ...
- 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 ...
- 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 ...
- 10.5k
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 ...
- 2,064
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 ...
- 2,064
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') | ...
- 5,030
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, ...
- 33.3k
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: \...
- 41.4k
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 ...
- 10.5k
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 ...
- 5,030
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_{...
- 33.3k
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 ...
- 1,301
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 ϵ-...
- 520
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 ...
- 9,392
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. ...
- 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 ...
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 ...
- 1,703
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 ...
- 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. ...
- 33.3k
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 ...
- 5,422
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$ ...
- 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 ...
- 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 ...
- 131
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 ...
- 33.3k
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) ...
- 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 ...
- 33.3k
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 ...
- 171
Only top scored, non community-wiki answers of a minimum length are eligible