0
$\begingroup$

To update the Q table Q-learning takes the arg max of the Q values - the state, value mappings.

For example, in tic tac toe the state XOX OXO -X- contains two available positions, each marked by the - character. In order to evaluate the arg max should temporal difference calculate the arg max of just the available positions?

For the state XOX OXO -X- the arg max should be taken at index 6 and 8 ? (assuming zero indexing) If not then how should the arg max indexes be updated? The indexes 0,1,2 3,4,5 7 can be used as they are already been taken by X or O so should not be evaluated for their value ? This also means that indexes which are not available will not have their Q value updated, will this break the Q-learning procedure ?

$\endgroup$
3
$\begingroup$

What you are referring to as the situation where

some indexes are not available

is simply the situation where some actions are not available/valid in some state. So, yes, the ${\arg \max }$ will be calculated based only on the available actions in that state. More formally, $$\underset{a \in \mathcal{A}(s)}{\arg \max } \, Q(s, a)$$

where $Q(s,a)$ has been initialized for all $s \in \mathcal{S}^{+}$ and $a \in \mathcal{A}(s)$ and $\mathcal{A}(s)$ is defined as the set of all actions available in state $s$. See Sutton and Barto's Intro to RL book, chapter 6 (the part on Q-learning).

In the same book (chapter 3), the authors state that:

To simplify notation, we sometimes assume the special case in which the action set is the same in all states and write it simply as $\mathcal{A}$.

Therefore, in many sources, you may see the $\arg \max$ expressed as $\underset{a \in \mathcal{A}} {\arg \max}$ or even $\underset{a} {\arg \max}$. It's implicit that it is taken with respect to the set of actions $\mathcal{A}(s)$ available in state $s$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.