1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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 $\endgroup$ Jul 6, 2022 at 16:09
  • $\begingroup$ @NeilSlater, transferring all the mathematical symbols from the page would be unreasonably painful. $\endgroup$
    – Melanol
    Jul 6, 2022 at 16:20
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 6, 2022 at 16:24
  • 1
    $\begingroup$ Thanks for the update $\endgroup$ Jul 6, 2022 at 16:33

1 Answer 1

0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .