All Questions
Tagged with barto-sutton or sutton-barto
121 questions
4
votes
0
answers
64
views
Does everyone still use discount rates?
In Section 10.4 of Sutton and Barto's RL book, they argue that the discount rate $\gamma$ has no effect in continuing settings. They show (at least for one objective function) that the average of the ...
- 41.4k
3
votes
2
answers
419
views
How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling", in the proof of the policy gradient theorem?
In the proof of the policy gradient theorem in the RL book of Sutton and Barto (that I shamelessly paste here):
there is the "unrolling" step that is supposed to be immediately clear
With ...
- 5,030
1
vote
1
answer
246
views
In off-policy MC learning, why is the probability of sampling a trajectory the same as having a return?
In Sutton and Barto's RL book, in the section for off-policy learning, we would like to find the expected value of the random variable $G_t$, given $S_t = s$ under our target policy: $$\mathbb{E}_{\pi}...
- 41.4k
3
votes
1
answer
308
views
Sutton & Barto: what are parametrized functions?
From "Reinforcement Learning: An introduction (2nd ed.)" by Richard S. Sutton and Andrew G. Barto, on page 59
Instead, the agent would have to maintain $v_\pi$ and $q_\pi$ as parameterized ...
- 41.4k
1
vote
1
answer
56
views
Why will every action be sampled an infinite number of times?
I am reading the book Reinforcement Learning: An Introduction. Second edition (Richard S. Sutton and Andrew G. Barto). In the k-armed bandit problem using $\varepsilon$-greedy selection method, the ...
- 41.4k
3
votes
1
answer
157
views
Why does REINFORCE perform badly at first in Sutton and Barto Figure 13.1?
In Sutton and Barto (PDF, page 265), 2nd edition, Figure 13.1 applies REINFORCE to the "short corridor with switched actions" environment from Example 13.1. The figure looks like this:
My ...
- 632
2
votes
1
answer
45
views
What does it mean for an episode to start in a state-action pair?
In Sutton and Barto on chapter 5 (p.96), they talk about estimating state-action values with Monte Carlo:
For policy evaluation to work for action
values, we must assure continual exploration. One ...
- 5,030
2
votes
1
answer
813
views
Why would SARSA diverge (but not Expected SARSA or Q-learning)?
In figure 6.3 (shown below) from Reinforcement Learning: An Introduction (second edition) by Sutton and Barto, SARSA is shown to perform worse asymptotically (after 100k episodes) than in the interim (...
CommunityBot
- 1
0
votes
1
answer
269
views
Is my derivation of the Bellman equation for $q_{\pi}$ in terms of $p(s'|s,a)$ and $r(s,a)$ correct?
I have done exercise 3.29 from Sutton and Barto and I'd like to check if it's correct. Here's the exercise:
Rewrite the Bellman equation for the function $q_{\pi}$ in terms of the three argument ...
- 1,301
18
votes
4
answers
2k
views
Why does the discount rate in the REINFORCE algorithm appear twice?
I was reading the book Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto (complete draft, November 5, 2017).
On page 271, the pseudo-code for the episodic Monte-Carlo ...
- 41
0
votes
1
answer
404
views
What is the equation for $\pi_*$ in terms of $q_*(s,a)$?
I am trying to solve the following exercise from Sutton and Barto:
Sutton and Barto Exercise 3.27 Give an equation for $\pi_*$ in terms of $q_*(s,a)$
However, I am struggling to do so. I know that $\...
- 41.4k
4
votes
1
answer
1k
views
How do we express $q_\pi(s,a)$ as a function of $p(s',r|s,a)$ and $v_\pi(s)$?
The task (exercise 3.13 in the RL book by Sutton and Barto) is to express $q_\pi(s,a)$ as a function of $p(s',r|s,a)$ and $v_\pi(s)$.
$q_\pi(s,a)$ is the action-value function, that states how good ...
- 145
7
votes
2
answers
2k
views
In Value Iteration, why can we initialize the value function arbitrarily?
I have not been able to find a good explanation of this, other than statements that the algorithm is guaranteed to converge with arbitrary choices for initial values in each state. Is this something ...
- 1,703
3
votes
1
answer
415
views
Why does the average-reward estimator for continuing tasks use the TD error?
In Sutton and Barto's RL book, section 10.3 describes how to use average reward $r(\pi)$ to define the quality of a policy, re-defining action-value function $q_\pi(s,a)$ and value function $v_\pi(s)$ ...
- 106
0
votes
1
answer
428
views
How to perform the back propagation step in Semi-gradient SARSA using a deep neural network?
For the back weight update step, I need to calculate $\nabla\hat{q}(S,A,w)$. My neural network takes in the state vector $S$ and gives out the action values for state $S$ and each action in the action ...
- 41.4k
5
votes
1
answer
1k
views
Should the policy parameters be updated at each time step or at the end of the episode in REINFORCE?
REINFORCE is a Monte Carlo policy gradient algorithm, which updates weights (parameters) of policy network by generating episodes. Here's a pseudo-code from Sutton's book (which is same as the ...
- 41.4k
4
votes
1
answer
676
views
What should the discount factor for the non-slippery version of the FrozenLake environment be?
I was working with FrozenLake 4x4 from open AI gym. In the slippery case, using a discounting factor of 1, my value iteration implementation was giving a success rate of around 75 percent. It was much ...
- 33.3k
2
votes
1
answer
245
views
Gradient bandit algorithm: is $\bar{R}_t$ average of all rewards or average of rewards corresponding to $A_t$?
Sutton-Barto (Section 2.8-Gradient Bandit Algorithms, page 37):
Question: is $\bar{R}_t$ average of all rewards or average of rewards corresponding to $A_t$?
- 33.3k
3
votes
4
answers
2k
views
How can the Cart Pole problem be a continuing task?
In Introduction to Reinforcement Learning (2nd edition) by Sutton and Barto, there is an example of the Pole-Balancing problem (Example 3.4).
In this example, they write that this problem can be ...
- 33.3k
1
vote
0
answers
62
views
Knowing the futility of discounting in continuing problems, how can we say discounting has no role in control problems with function approximation?
Sutton-Barto (Section 10.4, page 254):
Based on the futility of discounting in continuing problems, how can we conclude that discounting has no role to play in control problems with function ...
- 41.4k
6
votes
5
answers
1k
views
How do compute the table for $p(s',r|s,a)$ (exercise 3.5 in Sutton & Barto's book)?
I am trying to study the book Reinforcement Learning: An Introduction (Sutton & Barto, 2018). In chapter 3.1 the authors state the following exercise
Exercise 3.5 Give a table analogous to that ...
- 41.4k
2
votes
1
answer
183
views
Where are the parentheses in the definition of $r(s,a)$?
I am new to RL and I am trying to work through the book Reinforcement Learning: An Introduction I (Sutton & Barto, 2018). In chapter 3 on Finite Markov Decision Processes, the authors write the ...
- 41.4k
5
votes
2
answers
1k
views
Why does the definition of the reward function $r(s, a, s')$ involve the term $p(s' \mid s, a)$?
Sutton and Barto define the state–action–next-state reward function, $r(s, a, s')$, as follows (equation 3.6, p. 49)
$$
r(s, a, s^{\prime}) \doteq \mathbb{E}\left[R_{t} \mid S_{t-1}=s, A_{t-1}=a, S_{t}...
- 41.4k
6
votes
1
answer
334
views
If $\gamma \in (0,1)$, what is the on-policy state distribution for episodic tasks?
In Reinforcement Learning: An Introduction, section 9.2 (page 199), Sutton and Barto describe the on-policy distribution in episodic tasks, with $\gamma =1$, as being
\begin{equation}
\mu(s) = \frac{\...
- 41.4k
2
votes
1
answer
128
views
Is the existence and uniqueness of the state-value function for $\gamma < 1$ theoretical?
Consider the following statement from 4.1 Policy Evaluation of the first edition of Sutton and Barto's book.
The existence and uniqueness of $V^{\pi}$ are guaranteed as long as
either $\gamma < 1$...
- 41.4k
2
votes
1
answer
160
views
Why is there an inconsistency between my calculations of Policy Iteration and this Sutton & Barto's diagram?
In equation 4.9 of Sutton and Barto's book on page 79, we have (for the policy iteration algorithm):
$$\pi'(s) = arg \max_{a}\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]$$
where $\pi$ is the previous ...
- 41.4k
1
vote
0
answers
43
views
Why is the step-size $\alpha_t = 1/t$ not appropriate for non-stationary function approximation?
Sutton-Barto (Section: Selecting Step-Size Parameters Manually, page: 222)
The classical choice $\alpha_t = 1/t$, which produces sample averages in tabular MC methods, is not appropriate for TD ...
- 41.4k
3
votes
1
answer
224
views
Given these two reward functions, what can we say about the optimal Q-values, in self-play tic-tac-toe?
This corresponds to Exercise 1.1 of Sutton & Barto's book (2nd edition), and a discussion followed from this answer.
Consider the following two reward functions
Win = +1, Draw = 0, Loss = -1
Win =...
- 41.4k
1
vote
1
answer
66
views
Unclear paragraph in Sutton-Barto on "Tile Coding"
Sutton-Barto (Tile Coding, page 218):
For example, choosing $\alpha = 1/n$, where n is the number
of tilings, results in exact one-trial learning. If the example $s\to v$ is trained on, then
whatever ...
- 33.3k
0
votes
1
answer
85
views
How state 1 has a 0.5 chance of terminating on the left, and state 950 has a 0.25 chance of terminating on the right?
Sutton-Barto's RL book (page 203)
Example 9.1: State Aggregation on the 1000-state Random Walk: Consider a
1000-state version of the random walk task (Examples 6.2 and 7.1 on pages 125 and
144). The ...
- 5,417
0
votes
1
answer
353
views
How is state aggregation defined mathematically here? [duplicate]
Sutton-Barto's RL book (page 203):
State aggregation is a simple form of generalizing function approximation in which
states are grouped together, with one estimated value (one component of the ...
- 33.3k
1
vote
1
answer
68
views
Without planning, why does each episode only add one additional step to the policy?
In Sutton & Barto's RL book at page 165 for Example 8.1, they say:
Figure 8.3 shows why the planning agents found the solution so much faster than the nonplanning agent. Shown are the policies ...
- 33.3k
1
vote
0
answers
105
views
Why does importance sampling ratio start and end one step later in off-policy SARSA given in Sutton-Barto's RL book?
In Sutton & Barto's RL book (page 149) they say:
Sarsa update can be completely replaced by a simple off-policy form
$Q_{t+n}(S_t,A_t)=Q_{t+n−1}(S_t,A_t) + \rho_{t+1:t+n} [G_{t:t+n} − Q_{t+n−1}(...
- 41.4k
0
votes
1
answer
256
views
Why $ t=τ+n-1$ instead of $t=τ+n$ in n-step TD?
If $\tau$ is the time, whose state’s estimate is being updated, and $t$ is the current time, then, in n-step TD method, we have $t=\tau+n$ (because we have to wait n-steps, before we can update). ...
- 41.4k
2
votes
1
answer
92
views
Why do we have $t$ as subscript in $V$ instead of $t+1$ in the expression of $G_{t:t+1}$?
In one-step TD updates, the target is the first reward plus the discounted estimated value of the next state, which we call the one-step return (page 143 of Sutton & Barto):
$$
G_{t:t+1} \...
- 927
3
votes
1
answer
263
views
Doubt regarding the proof of convergence of $\epsilon$ soft policies without exploring starts
In page 125 of Sutton and Barto (second last paragraph) the proof for equality of $v_{\pi}$ and $v_*$ for $\epsilon$ soft policies is given. But I could not understand the statement explaining the ...
- 10.5k
0
votes
1
answer
257
views
How to simplify policy gradient theorem to $E_{\pi}[G_t \frac{\nabla_{\theta}\pi(a|S_t,\theta)}{\pi(a|S_t,\theta)}]$?
In "Introduction to Reinforcement Learning" (Richard Sutton) section 13.3(Reinforce algorithm) they have the following equation:
\begin{align}
\nabla_{\theta}J &\propto \sum_s \mu(s) \...
- 41.4k
2
votes
0
answers
122
views
In Policy Gradient methods, why are actions always chosen from a Gaussian in the literature?
In Sutton's 2020 Reinforcement Learning text (in chapter 13.7 Policy Parameterization for Continuous Actions) it's stated
actions [may be] chosen from a normal (Gaussian) distribution.
However, I ...
- 41.4k
3
votes
1
answer
1k
views
How to express $v_\pi(s)$ in terms of $q_\pi(s,a)$?
This is exercise 3.18 in Sutton and Barto's book.
The task is to express $v_\pi(s)$ using $q_\pi(s,a)$.
Looking at the diagram above, the value of $q_\pi(s,a)$ at $s$ for each $a \in A$ we take gives ...
- 41.4k
2
votes
1
answer
96
views
Why is $M_t$ (the emphasis) helping in correcting for the state distribution in the Emphatic TD algorithm?
The book by Sutton and Barto discusses in section 11.8 that the convergence of off-policy TD function approximation can be improved by correcting for the distribution of states encountered. The ...
- 41.4k
6
votes
1
answer
1k
views
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$?
I'm trying to solve exercise 3.11 from the book Sutton and Barto's book (2nd edition)
Exercise 3.11 If the current state is $S_t$ , and actions are selected according to a stochastic policy $\pi$, ...
- 41.4k
4
votes
1
answer
174
views
What knowledge is required for understanding the AlphaZero paper?
My goal is to understand AlphaZero paper published by deepmind. I'm beginning my journey trying to get the basic intuition of reinforcement learning from the book by Barto and Sutton.
As per my ...
- 137
2
votes
1
answer
65
views
How to prove importance sampling ratio is uncorrelated with action-value (or state-value) estimate?
In Sutton & Barto (2nd edition), the following is mentioned on page 150 (p. 172 of the pdf), section 7.4:
the importance sampling ratio has expected value one (Section 5.9) and is uncorrelated ...
- 348
0
votes
1
answer
165
views
Policies for which the policy improvement theorem holds
According to Reinforcement Learning (2nd Edition) by Sutton and Barto, the policy improvement theorem states that for any pair of deterministic policies $\pi'$ and $\pi$, if $q_\pi(s,\pi'(s)) \geq v_\...
CommunityBot
- 1
0
votes
0
answers
29
views
Why does one-step TD strengthen only the last action of the sequence of actions that led to the high reward, while n-step TD the last n actions?
In the caption of figure 7.4 (p. 147) of Sutton & Barto's book (2nd edition), it's written
The one-step method strengthens only the last action of the sequence of actions that led to the high ...
- 41.4k
23
votes
2
answers
15k
views
What is the difference between reinforcement learning and optimal control?
Coming from a process (optimal) control background, I have begun studying the field of deep reinforcement learning.
Sutton & Barto (2015) state that
particularly important (to the writing of the ...
- 41.4k
1
vote
1
answer
95
views
Why is the update in-place faster than the out-of-place one in dynamic programming?
In Barto and Sutton's book, it's written that we have two types of updates in dynamic programming
Update out-of-place
Update in-place
The update in-place is the faster one. Why is that the case?
...
- 41.4k
4
votes
0
answers
376
views
When using hashing in tile coding, why are memory requirements reduced and there is only a little loss of performance?
In the book "Reinforcement Learning: An Introduction" (2018) Sutton and Barto explain, on page 221, a form of tile coding using hashing, to reduce memory consumption.
I have two questions ...
- 41.4k
12
votes
4
answers
2k
views
Counterexamples to the reward hypothesis
On Sutton and Barto's RL book, the reward hypothesis is stated as
that all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative ...
- 131
0
votes
0
answers
552
views
Suppose every-visit MC was used instead of first-visit MC on blackjack. Would you expect the results to be different?
This is a question from page 94 of Sutton and Barto's RL book 2020.
I read in someone's compiled GitHub answers to this book's exercises their answer was: "No because each state in an episode of ...
- 41.4k