Answers.Body: <blockquote>
  <p>All store and access operations (for S(t), A(t), and R(t)) can take their index mod n + 1</p>
  </blockquote>
  <p>This is referencing a possible storage space optimisation, which is not really necessary on any modern PC, but might be of interest in embedded systems, or perhaps as a convenience on continuing systems where you may process millions of time steps in the same trajectory.</p>
  <p>The n-step TD algorithm makes an update to state/action pairs <span class="math-container">$n$</span> steps in the past, and needs the whole trajectory in-between, but never needs any earlier or different data (unlike an experience replay table).</p>
  <p>This means you can store everything you need for the calculations in 3 arrays of size <span class="math-container">$n+1$</span>.</p>
  <p>One way to do that might be to push and unshift the arrays once they have reached the max length, and work everything relatively from the current time step. However, most array implementations won't do the unshift efficiently, so it's not a great solution - plus all the relative indexing might be confusing.</p>
  <p>The pseudocode is suggesting that you create 3 arrays of length <span class="math-container">$n+1$</span> and use modular arithmetic when referencing the timestep indices. This is a neat way of using the minimum required space.</p>
  <p>In Python, you would use the modulus operator <code>%</code> to do this, wherever you reference a list used to store states, actions or rewards.</p>
  <p>So for example, if you have the code <code>states[t] = current_state</code> to store the current state in a longer array, you would instead use <code>states[t % store_size] = current_state</code>, where <code>store_size = n + 1</code>.</p>
  <p>The same applies to any other index references. If they are calculated inside the indexing you need parens, e.g. <code>g += rewards[(t - i) % store_size]</code>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-06T16:48:28.147Z
Answers.LastActivityDate: 2022-07-06T19:25:51.037Z
Answers.LastEditDate: 2022-07-06T19:25:51.037Z
Answers.UserDisplayName: Neil Slater
Body: <p>It's from the book Introduction to Reinforcement Learning. Second edition, chapter7: n-step Bootstrapping, page 147, n-step Sarsa.</p>
  <p>I made the algo work, but I still don't understand the phrase.</p>
  <p>Preferably explained in Python terms. The introductory part for the algo:</p>
  <blockquote>
  <p>Initialize Q(s, a) arbitrarily, for all s <span class="math-container">$\in$</span> S, a <span class="math-container">$\in$</span> A</p>
  </blockquote>
  <blockquote>
  <p>Initialize <span class="math-container">$\pi$</span> to be <span class="math-container">$\epsilon$</span>-greedy with respect to Q, or to a fixed given policy</p>
  </blockquote>
  <blockquote>
  <p>Algorithm parameters: step size <span class="math-container">$\alpha$</span> <span class="math-container">$\in$</span> (0, 1], small  <span class="math-container">$\epsilon$</span> &gt; 0, a positive integer n</p>
  </blockquote>
  <blockquote>
  <p>All store and access operations (for S(t), A(t), and R(t)) can take their index mod n + 1</p>
  </blockquote>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-06T16:09:18.370Z
Comments.Text: I know what this is, but please [edit] and add some context from the book. The page reference is useful, but some context would be useful, and preferred on this site. E.g. chapter subject matter, section heading, name of the algorithm and  and maybe a pull quote of the surrounding pseudo-code. Text please, not screenshots
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-06T16:20:24.890Z
Comments.Text: @NeilSlater, transferring all the mathematical symbols from the page would be unreasonably painful.
Comments.UserDisplayName: asdfasdfsdf
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-06T16:24:03.643Z
Comments.Text: the site supports math symbols using LaTex notation between `$$` e.g. `$S_{t+1}$` shows as $S_{t+1}$. I am sure most of the context doesn't require them, just some of the pseudocode.
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><machine-learning><sutton-barto>
Title: What does "All store and access operations (for S(t) , A(t), and R(t)) can take their index mod n + 1" mean?
UserDisplayName: asdfasdfsdf
ThreadText: # What does "All store and access operations (for S(t) , A(t), and R(t)) can take their index mod n + 1" mean?
  
  (Asked by: username_0 on 2022-07-06)
  
  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.
  
  Preferably explained in Python terms. The introductory part for the algo:
  
  > Initialize Q(s, a) arbitrarily, for all s $\in$ S, a $\in$ A
  
  > Initialize $\pi$ to be $\epsilon$-greedy with respect to Q, or to a fixed given policy
  
  > Algorithm parameters: step size $\alpha$ $\in$ (0, 1], small $\epsilon$ > 0, a positive integer n
  
  > All store and access operations (for S(t), A(t), and R(t)) can take their index mod n + 1
  
  **Tags:** reinforcement-learning, machine-learning, sutton-barto
  > **Comments:**
  > **username_1**: I know what this is, but please [edit] and add some context from the book. The page reference is useful, but some context would be useful, and preferred on this site. E.g. chapter subject matter, section heading, name of the algorithm and  and maybe a pull quote of the surrounding pseudo-code. Text please, not screenshots  
  > **username_0**: @NeilSlater, transferring all the mathematical symbols from the page would be unreasonably painful.  
  > **username_1**: the site supports math symbols using LaTex notation between `$$` e.g. `$S_{t+1}$` shows as $S_{t+1}$. I am sure most of the context doesn't require them, just some of the pseudocode.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-07-06. Score: 0
  
  > All store and access operations (for S(t), A(t), and R(t)) can take their index mod n + 1
  
  This is referencing a possible storage space optimisation, which is not really necessary on any modern PC, but might be of interest in embedded systems, or perhaps as a convenience on continuing systems where you may process millions of time steps in the same trajectory.
  
  The n-step TD algorithm makes an update to state/action pairs $n$ steps in the past, and needs the whole trajectory in-between, but never needs any earlier or different data (unlike an experience replay table).
  
  This means you can store everything you need for the calculations in 3 arrays of size $n+1$.
  
  One way to do that might be to push and unshift the arrays once they have reached the max length, and work everything relatively from the current time step. However, most array implementations won't do the unshift efficiently, so it's not a great solution - plus all the relative indexing might be confusing.
  
  The pseudocode is suggesting that you create 3 arrays of length $n+1$ and use modular arithmetic when referencing the timestep indices. This is a neat way of using the minimum required space.
  
  In Python, you would use the modulus operator `%` to do this, wherever you reference a list used to store states, actions or rewards.
  
  So for example, if you have the code `states[t] = current_state` to store the current state in a longer array, you would instead use `states[t % store_size] = current_state`, where `store_size = n + 1`.
  
  The same applies to any other index references. If they are calculated inside the indexing you need parens, e.g. `g += rewards[(t - i) % store_size]`.
  
  
  ---
  
  