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

Question

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

Answer 1

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].