Questions tagged [sutton-barto]

For questions related to the book "Reinforcement Learning: An Introduction" (by Andrew Barto and Richard S. Sutton).

Filter by
Sorted by
Tagged with
16
votes
3answers
1k 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 ...
13
votes
2answers
7k 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 ...
11
votes
2answers
1k views

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

In section 7.1 (about the n-step bootstrapping) of the book Reinforcement Learning: An Introduction (2nd edition), by Andrew Barto and Richard S. Sutton, the authors write about what they call the "n-...
11
votes
4answers
1k 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 ...
7
votes
1answer
673 views

How is the policy gradient calculated in REINFORCE?

Reading Sutton and Barto, I see the following in describing policy gradients: How is the gradient calculated with respect to an action (taken at time t)? I've read implementations of the algorithm, ...
5
votes
2answers
291 views

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

In the book Reinforcement Learning: An Introduction (2nd edition) Sutton and Barto define at page 104 (p. 126 of the pdf), equation (5.3), the importance sampling ratio, $\rho _{t:T-1}$, as follows: $$...
5
votes
1answer
3k views

Expected SARSA vs SARSA in "RL: An Introduction"

Sutton and Barto state in the 2018-version of "Reinforcement Learning: An Introduction" in the context of Expected SARSA (p. 133) the following sentences: Expected SARSA is more complex ...
4
votes
2answers
88 views

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

This is the Short Corridor problem taken from the Sutton & Barto book. Here it's written: The problem is difficult because all the states appear identical under the function approximation But ...
4
votes
1answer
220 views

Understanding the n-step off-policy SARSA update

In Sutton & Barto's book (2nd ed) page 149, there is the equation 7.11 I am having a hard time understanding this equation. I would have thought that we should be moving $Q$ towards $G$, where $...
3
votes
2answers
141 views

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

In Sutton & Barto's "Reinforcement Learning: An Introduction", 2nd edition, page 199, they describe the on-policy distribution for episodic tasks in the following box: I don't understand how this ...
3
votes
1answer
114 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 ...
3
votes
1answer
106 views

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

Equation 7.3 of Sutton Barto book: $$\text{Equation: } max_s|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi| \le \gamma^nmax_s|V_{t+n-1}(s) - v_\pi(s)| $$ $$\text{where }G_{t:t+n} = R_{t+1} + \gamma R_{t+2}...
3
votes
1answer
72 views

Is my interpretation of the return correct?

Sutton and Barto 2018 define the discounted return $G_t$ the following way (p 55): Is my interpretation correct? Or should all "1" be in the same column?
3
votes
1answer
133 views

Why do we have two similar action selection strategies for UCB1?

In the literature, there are at least two action selection strategies associated with the UCB1's action selection strategy/policy. For example, in the paper Algorithms for the multi-armed bandit ...
3
votes
1answer
79 views

Sutton & Barto's notation $V_{t+n}$ in Chapter 7: $n$-step Bootstrapping

Until Chapter 6 of Sutton & Barto's book on Reinforcement Learning, the authors use $V$ for the current estimate of a state value. Equation (6.1), for example, shows: $$ V(S_t) \leftarrow V(S_t) +...
3
votes
2answers
522 views

Difference in continuing and episodic cases in Sutton and Barto - Introduction to RL, exercise 3.5

Excercise 3.5 The equastions in Section 3.1 are for the continuing case and need to be modified (very slightly) to apply to episodic tasks. Show that you know the modifications needed by giving ...
3
votes
1answer
129 views

Why is an average of all returns used to update the value in the first-visit MC control?

In Sutton & Barto's Reinforcement Learning: An Introduction, in page 83 (101 of the pdf), there is a description of first-visit MC control. In the phase where they update $Q(s, a)$, they do an ...
3
votes
1answer
531 views

When does backward propagation occur in n-step SARSA?

I am trying to understand the algorithm for n-step SARSA from Sutton and Barto (2nd Edition). As I understand it, this algorithm should update n state-action values, but I cannot see where it is ...
3
votes
0answers
165 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 ...
2
votes
1answer
48 views

Why is the fraction of time spent in state $s$, $\mu(s)$, not in the update rule of the parameters?

I am reading "Reinforcement Learning: An Introduction (2nd edition)" authored by Sutton and Barto. In Section 9, On-policy prediction with approximation, it first gives the mean squared ...
2
votes
1answer
58 views

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

In the average reward setting we have: $$r(\pi)\doteq \lim_{h\rightarrow\infty}\frac{1}{h}\sum_{t=1}^{h}\mathbb{E}[R_{t}|S_0,A_{0:t-1}\sim\pi]$$ $$r(\pi)\doteq \lim_{t\rightarrow\infty}\mathbb{E}[R_{t}...
2
votes
1answer
82 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 ...
2
votes
1answer
127 views

What does the figure "Blackjack Value Function..." from Sutton represent?

I came across this graph in David Silver's youtube lecture and Sutton's book on reinforcement learning. Can anyone help me understand the graph? From the graph, for 10000 episodes what i see is ...
2
votes
1answer
136 views

Understanding the notation in the definition of the expected reward

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 ...
2
votes
1answer
31 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 ...
2
votes
1answer
58 views

In off-policy MC control algorithm by Sutton & Barto, why do we perform a last update when sample action is inconsistent with target policy?

I have a question about the $W$ term in the off-policy MC control algorithm on Page 111 of Sutton & Barto. I have also included it in the figure below. My question: shouldn't the check $A_{t} = \...
2
votes
2answers
98 views

How do we get the true value in the prediction objective in reinforcement learning?

In the book "Reinforcement Learning: An Introduction" (2018) Sutton and Barto define the prediction objective ($\overline{VE}$) as follows (page 199): $$\overline{VE}\doteq\sum_{s\epsilon S} \mu(s)[v_{...
2
votes
1answer
72 views

Possible inconsistency in the Policy Improvement equation

I came across this formula in Sutton And Barto: RL an Intro (2nd Edition) equation number 4.7 (page number 78). If $\pi$ and $\pi'$ are deterministic policies and $q_\pi(s, \pi'(s)) \geq v_\pi(s)$ ...
2
votes
1answer
92 views

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

I'm reading the book "Reinforcement Learning: An Introduction" (by Andrew Barto and Richard S. Sutton). The authors provide the pseudocode of the prioritized sweeping algorithm, but I do not know ...
1
vote
1answer
585 views

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

The $\lambda$-return is defined as $$G_t^\lambda = (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}G_{t:t+n}$$ where $$G_{t:t+n} = R_{t+1}+\gamma R_{t+2}+\dots +\gamma^{n-1}R_{t+n} + \gamma^n\hat{v}(S_{t+n})...
1
vote
1answer
210 views

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

In Example 4.3:Gambler's Problem of Sutton and Barto's book whose code is given here. In this code the value function array is initialized as np.zeros(states) where ...
1
vote
1answer
261 views

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

I am working through the famous RL textbook by Sutton & Barto. Currently, I am on the value iteration chapter. To gain better understanding, I coded up a small example, inspired by this article. ...
1
vote
1answer
46 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? ...
0
votes
1answer
31 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_\...
0
votes
1answer
94 views

How to simplify policy gradient theoram 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) \...
0
votes
0answers
16 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 ...
0
votes
0answers
15 views

Why has PILCO not been included in Sutton & Barto?

PILCO is a model-based Reinforcement Learning method introduced in 2011 by Deisenroth and Rasmussen. As far as I know, it is still considered one of the most important RL method, especially for its ...
0
votes
0answers
34 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 ...