How to handle invalid actions for next state in Q-learning loss

Question

I am implementing an RL application in an environment with illegal moves. For handling the illegal moves, I am currently just picking an action as the maximum Q-value from the set of legal Q-values.

So, it is clear that when deciding on actions we only pick from a subset of valid Q-values, but, when using the Q-learning algorithm, do we also want to consider the subset of invalid actions for the $\max\limits_{a}Q(s_{t+1},a)$?

My gut tells me that we consider all actions for the max function, purely based on the lack of documentation on the subject, but only considering the subset of legal actions makes more sense to me. I'm having a hard time finding any reliable sources addressing this topic. Any advice/direction would be greatly appreciated.

Answer 1

do we also want to consider the subset of invalid actions for the $\max\limits_{a}Q(s_{t+1},a)$

No.

Doing so would go against the theory behind the Bellman equation from which the update derives. The value of $r_{t+1} + \gamma \max\limits_{a'}Q(s_{t+1},a')$ needs to match to a realisable trajectory, otherwise the eventual expected values may be estimates for a different MDP than the one being learned.

For intuition, you can construct a valid MDP which would clearly give the wrong update if the update maximised over non-valid actions. For instance, in a maze game where as well as the classic N,E,S,W moves, the agent can see and pick up treasure in each location. The "pick up" (P) action is only allowed in a location that has treasure and scores $+10$ reward when successfully used, all other outcomes grant $-1$ reward to encourage the agent to act efficiently and escape the maze.

It is worth considering two broad types of Q-learning here - an approximate learner that uses a neural network (e.g. DQN), and a tabular learner that stores action values in a table.

• The approximate learner will associate successful uses of the P action with a higher expected return, and generalise this to other states. If the P action is included in updates where there is no treature to pick up in state $s_{t+1}$, it will incorrectly increase the expected return from all actions. Actions that move away from treasure would score similarly as actions that move towards it.

• The tabular learner's behaviour will depend on how Q values are initialised. The table entries for non-valid actions would never be updated, so they would remain at the initialised value. If that was e.g. $0$, then it may sometimes be better than valid actions that lead to longer stretches without treasure. Which in turn means that in some locations, multiple valid actions going in different directions would look the same to the agent - future expected returns would be capped at minimum $-1$ (the immediate reward) irrespective of whether they go towards the exit or not. Some actions, that head towards real treasure, may score higher. However, when there is no treasure or exit nearby, all actions would seem the same.

In both cases, the behaviour of the agent will be compromised. It may ignore nearby treasure, or travel into a dead end or loop.

I have deliberately constructed an MDP where maximising over all actions including non-valid ones will cause a problem. Some MDPs will not cause a problem - for instance the same maze MDP with one difference, where the P action is allowed even when there is no treasure, and scores -1 reward for wasting time. However, having a valid environment where the agent fails, demonstrates that an agent built to maximise over non-valid actions will not be reliable in all MDPs, it would have a designed in "bug" and fail for some use cases.