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
3 votes
1 answer
167 views

$\gamma^t$ in REINFORCE update (Sutton-Barto RL book Exercise 13.2)

I've struggled with solving exercise 13.2 from Reinforcement Learning: An Introduction Second Edition : Generalize the box on page 199, the policy gradient theorem (13.5), the proof of the policy ...
cfml's user avatar
  • 53
4 votes
1 answer
54 views

Could you explain these 2 steps of the derivation of the Bellman equation as a recursive equation in Sutton & Barto?

I am reading the Sutton & Barto (2018) RL textbook. On page 59, it derives the recursive property of the state-value function as below. Could you explain the steps of third and fourth equality? ...
tesio's user avatar
  • 195
0 votes
0 answers
58 views

Understanding SARSA with binary features and function approximation

I'm reading the Sutton and Barto Book on Reinforcement Learning (for oral exam preparation). However, I'm stuck on the algorithm for SARSA($\lambda$) with binary features and linear function ...
Mika2019's user avatar
1 vote
1 answer
133 views

Where is the problem: in batch TD(0) algorithm or in the code to solve AB problem in Sutton-Barto RL book?

Here is the batch TD(0) algorithm: Here is the AB example I want to solve using batch TD(0): And finally here is my Matlab code: % eps1: A 0 B 0 % eps2: B 1 % eps3: B 1 % eps4: B 1 % eps5: B 1 % ...
DSPinfinity's user avatar
1 vote
1 answer
172 views

How does off-policy Monte Carlo weighted importance sampling bias converge to zero (Sutton & Barto Section 5.5)

On Section 5.5 (page 105) of Sutton & Barto's "Reinforcement Learning: An Introduction", they discuss the off-policy Monte Carlo method for learning the value function of a target policy ...
user118967's user avatar
5 votes
2 answers
154 views

Why is $\sum_{s} \eta(s)$ a constant of proportionality in the proof of the policy gradient theorem?

In Sutton and Barto's book (http://incompleteideas.net/book/bookdraft2017nov5.pdf), a proof of the policy gradient theorem is provided on pg. 269 for an episodic case and a start state policy ...
jwl17's user avatar
  • 59
3 votes
1 answer
272 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 ...
SomeoneUnknown's user avatar
1 vote
1 answer
55 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 ...
k2pctdn's user avatar
  • 55
1 vote
1 answer
187 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}...
ArminAshrafi's user avatar
3 votes
0 answers
60 views

How does off-policy monte carlo explore and converge? [duplicate]

Premises to question: Behavior Policy: e-greedy (stochastic) Target Policy: greedy (deterministic) Importance Sampling Included In off-policy Monte-Carlo control, the behavior policy chooses actions ...
Jonah Kim's user avatar
2 votes
1 answer
37 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 ...
user's user avatar
  • 145
3 votes
1 answer
127 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 ...
LarrySnyder610's user avatar
1 vote
1 answer
79 views

What does "All store and access operations (for S(t) , A(t), and R(t)) can take their index mod n + 1" mean?

It's from the book Introduction to Reinforcement Learning. Second edition, chapter7: n-step Bootstrapping, page 147, n-step Sarsa. I made the algo work, but I still don't understand the phrase. ...
Melanol's user avatar
  • 93
0 votes
1 answer
154 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 ...
user's user avatar
  • 145
0 votes
0 answers
30 views

Rewrite the four Bellman equations for the four value functions $(v_{\pi},v_*,q_{\pi},q_*)$ in terms of $p$ (3.4) and $r$ (3.5) [duplicate]

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 four Bellman equations for the four value functions $(v_{\pi},v_*,q_{\pi},q_*)$ ...
user's user avatar
  • 145
0 votes
1 answer
230 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 $\...
user's user avatar
  • 145
4 votes
1 answer
151 views

$E_{\pi}[R_{t+1}|S_t=s,A_t=a] = E[R_{t+1}|S_t=s,A_t=a]$?

I would like to solve the first question of Exercise 3.19 from Sutton and Barto: Exercise 3.19 The value of an action, $q_{\pi}(s, a)$, depends on the expected next reward and the expected sum of the ...
user's user avatar
  • 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 ...
Arham's user avatar
  • 73
0 votes
1 answer
313 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 ...
ketan dhanuka's user avatar
3 votes
1 answer
323 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)$ ...
kmf's user avatar
  • 106
4 votes
1 answer
496 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 ...
ketan dhanuka's user avatar
1 vote
1 answer
38 views

If the probabilities with which each task is selected for you do not change over time, why would it appear as a single stationary k-armed bandit task?

Sutton-Barto (Section 2.9-Associative Search (Contextual Bandits), page 41): As an example, suppose there are several different k-armed bandit tasks, and that on each step you confront one of these ...
user3489173's user avatar
1 vote
1 answer
178 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$?
user3489173's user avatar
1 vote
0 answers
35 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 ...
user3489173's user avatar
1 vote
0 answers
36 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 ...
user3489173's user avatar
0 votes
1 answer
53 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 ...
DSPinfinity's user avatar
0 votes
1 answer
61 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 ...
DSPinfinity's user avatar
0 votes
1 answer
206 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 ...
DSPinfinity's user avatar
1 vote
1 answer
55 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 ...
DSPinfinity's user avatar
1 vote
0 answers
73 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}(...
DSPinfinity's user avatar
0 votes
1 answer
186 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). ...
DSPinfinity's user avatar
2 votes
1 answer
68 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} \...
DSPinfinity's user avatar
1 vote
1 answer
224 views

Unclear step in off-policy (every-visit) MC Control: why do we need the line: $A_t \neq \pi(S_t)$ then exit inner loop?

Could please some expert on reinforcement learning explain the red-box part in the following off-policy MC control? I mean I did not understand what (and why) is done in the step shown as a red-box. I ...
user3489173's user avatar
0 votes
2 answers
366 views

Why does OpenAI's PPO algorithm not follow the discounting method used in Sutton & Barto?

As discussed in this question, the policy gradient algorithms given in Reinforcement Learning: An Introduction use the gradient \begin{align*} \gamma^t \hat A_t \nabla_{\theta} \log \pi(a_t \, | \, ...
Taw's user avatar
  • 1,201
2 votes
0 answers
105 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 ...
Bennet Leff's user avatar
4 votes
1 answer
491 views

What is the difference between an on-policy distribution and state visitation frequency?

On-policy distribution is defined as follows in Sutton and Barto: On the other hand, state visitation frequency is defined as follows in Trust Region Policy Optimization: $$\rho_{\pi}(s) = \sum_{t=0}^...
user529295's user avatar
2 votes
1 answer
597 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 (...
Quantum Sphinx's user avatar
0 votes
1 answer
93 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_\...
bonzo_pippinpaddle's user avatar
2 votes
1 answer
54 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 ...
user529295's user avatar
0 votes
0 answers
24 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 ...
user529295's user avatar
2 votes
1 answer
221 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} = \...
Curious2learn's user avatar
6 votes
1 answer
269 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{\...
Felipe Costa's user avatar
2 votes
1 answer
122 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$...
hanugm's user avatar
  • 3,612
0 votes
1 answer
209 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) \...
Swakshar Deb's user avatar
1 vote
1 answer
82 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? ...
VanasisB's user avatar
0 votes
0 answers
439 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 ...
user8714896's user avatar
4 votes
1 answer
441 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 ...
nbro's user avatar
  • 39.6k
2 votes
1 answer
72 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 ...
JYY's user avatar
  • 123
3 votes
1 answer
146 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}...
ZERO NULLS's user avatar
4 votes
2 answers
142 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 ...
ZERO NULLS's user avatar