Reinforcement Learning: Afterstate and Afterstate value functions

Question

While reading the book: Reinforcement Learning, An Introduction by Rich Sutton, I came across a doubt regarding afterstates and afterstates value functions and I am afraid I don't understand the concept well.

A conventional state-value function evaluates states in which the agent has the option of selecting an action, but the state-value function used in tic-tac-toe evaluates board positions after the agent has made its move. Let us call these afterstates, and value functions over these, afterstate value functions.

Now, I understand what afterstates are, but I am unable to understand, how to use these afterstate value functions to learn the action values?

A conventional action-value function would have to separately assess both pairs, whereas an afterstate value function would immediately assess both equally. Any learning about the position–move pair on the left would immediately transfer to the pair on the right.

How do we make sure that the learning is transferred from one state-action pair to the other provided both the state-action pair results in the same afterstate?

Answer 1

I am unable to understand, how to use these afterstate value functions to learn the action values?

If you use afterstates, you don't learn action values. You learn afterstate values.

It might help to think of it like this:

• $v_{\pi}(s)$ state value of being in state $s$ and following policy $\pi$

• $q_{\pi}(s,a)$ action value of being in state $s$, taking action $a$ and thereafter following policy $\pi$

• $w_{\pi}(s')$ afterstate value of changing to state $s'$ (regardless of current state) and thereafter following policy $\pi$

Sorry to use the letter $w$ - that's because $a$ already taken - but I want to make it clear that this is a different, but related function. Most of the literature appears to use $v$ or $q$ with some annotation to explain that it is an afterstate value function.

How do we make sure that the learning is transferred from one state-action pair to the other provided both the state-action pair results in the same afterstate?

With afterstate values, it is impossible to not do this. There is nowhere else for any new value estimate to go, but to the value of the (shared) afterstate.

What you are possibly missing is that you need to use the environment model to look up either:

• Which actions lead to which afterstates. In which case you might use same notation as action value $Q(s,a)$ but use $(s,a)$ to look up $s'$ and store a table (or approximate a function) of estimated values indexed by $s'$.

OR

• Which afterstates are possible/valid given the current state. In which case you might use the same notation as state value $V(s)$ but actually use $s'$ in place of $s$ and remember to include immediate reward for arriving in the state in the value.

Both of these effectively define action selection (your "action" is to select a desired afterstate), and this is something you must do in order to use afterstate representation.

One other possible "gotcha" for using afterstates: In general as I've used $s'$ above, $s' \neq s_{t+1}$ for afterstates. That is, the agent may select a state $s'$, then the environment (or other player) could alter the state further resulting in the next state $s_{t+1}$ seen by the agent.