1
$\begingroup$

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.

Q learning equation from https://en.wikipedia.org/wiki/Q-learning

$\endgroup$
2
  • 2
    $\begingroup$ you only choose the max over valid actions for that state. This is intuitive for the tabular case, there would only be the choice of valid actions as there would be no state-action tuple in the lookup table for invalid action choices. $\endgroup$ Sep 23 at 21:13
  • $\begingroup$ this might help : ai.stackexchange.com/search?q=mask+action $\endgroup$
    – Sanyou
    Sep 23 at 22:13
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ An excellent reply! Thank you for spending the time. In hindsight its kind of funny that I would even consider using infeasible actions. $\endgroup$ Sep 29 at 13:20

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.