Answers.Body: <p>Usually softmax methods in policy gradient methods using linear function approximation use the following formula to calculate the probability of choosing action <span class="math-container">$a$</span>. Here, weights are <span class="math-container">$\theta$</span>, and the features <span class="math-container">$\phi$</span> is a function of the current state <span class="math-container">$s$</span> and an action from the set of actions <span class="math-container">$A$</span>. </p>
  
  <p><span class="math-container">$$
  \pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum_{b \in A} e^{\theta \phi(s, b)}}
  $$</span></p>
  
  <p>To eliminate illegal moves, one would limit the set of actions to only those that were legal, hence <span class="math-container">$Legal(A)$</span>.</p>
  
  <p><span class="math-container">$$
  \pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum_{b \in Legal(A)} e^{\theta \phi(s, b)}}, \, a \in Legal(A)
  $$</span></p>
  
  <p>In pseudocode the formula may look like this:</p>
  
  <pre><code>action_probs = Agent.getActionProbs(state)
  legal_actions = filterLegalActions(state, action_probs)
  best_legal_action = softmax(legal_actions)
  </code></pre>
  
  <p>Whether using linear or non-linear function approximation (your neural network), the idea is to only use the legal moves when computing your softmax. This method means that only valid moves will be given by the agent, which is good if you wanted to change your game later on, and that the difference in value between the limited choice in actions will be easier to discriminate by the agent. It will also be faster as the number of possible actions decreases.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-11T13:04:39.267Z
Answers.Text: @brianberns Did you manage to find an answer? It seems like that would be the case to me but somehow in my toy example I'm only getting the right answer when using the log probabilities of the unfilitered softmax...
Answers.UserDisplayName: tryingtolearn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-02T10:16:16.440Z
Answers.Text: @tryingtolearn You could try to ask that as a separate question on our site (if it has not been asked before: I don't know).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-14T16:09:24.477Z
Answers.Text: The maths and pseudocode do not match here. Softmax over the legal move probabilities will adjust the relative probabilities. E.g. (0.3, 0.4, 0.2, 0.1) filtered with first and third item removed would be (0.0, 0.8, 0.0, 0.2) with your formula, but would be (0.0, 0.57, 0.0, 0.42) using the pseudocode. The pseudocode needs to take the logits, prior  to action probability calculations.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-22T14:26:08.337Z
Answers.Text: How does one compute the gradient of the filtered version of Softmax? Seems like this would be necessary for backpropagation to work successfuly, yes?
Answers.UserDisplayName: Brian Berns
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-03-15T06:21:41.317Z
Answers.LastActivityDate: 2018-11-14T13:58:07.037Z
Answers.LastEditDate: 2018-11-14T13:58:07.037Z
Answers.UserDisplayName: Jaden Travnik
Answers.Body: <p>I faced a similar issue recently with Minesweeper.</p>
  
  <p>The way I solved it was by ignoring the illegal/invalid moves entirely.</p>
  
  <ol>
  <li>Use the Q-network to predict the Q-values for all of your actions (valid and invalid)</li>
  <li>Pre-process the Q-values by setting all of the invalid moves to a Q-value of zero/negative number (depends on your scenario)</li>
  <li>Use a policy of your choice to select an action from the refined
  Q-values (i.e. greedy or Boltzmann)</li>
  <li>Execute the selected action and resume your DQN logic</li>
  </ol>
  
  <p>Hope this helps.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-07T07:21:06.197Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/105285/discussion-on-answer-by-sanavesa-how-to-handle-invalid-moves-in-reinforcement-le).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-17T19:09:20.057Z
Answers.LastActivityDate: 2018-12-04T21:20:06.213Z
Answers.LastEditDate: 2018-12-04T21:20:06.213Z
Answers.UserDisplayName: Sanavesa
Answers.Body: <p>IMHO the idea of invalid moves is itself invalid. Imagine placing an "X" at coordinates <code>(9, 9)</code>. You could consider it to be an invalid move and give it a negative reward. Absurd? Sure!</p>
  
  <p>But in fact your invalid moves are just <em>a relic of the representation</em> (which itself is straightforward and fine). The best treatment of them is to exclude them completely from any computation.</p>
  
  <p>This gets more apparent in chess:</p>
  
  <ul>
  <li><p>In a positional representation, you might consider the move <code>a1-a8</code>, which only belongs in the game if there's a Rook or a Queen at <code>a1</code> (and some other conditions hold).</p></li>
  <li><p>In a different representation, you might consider the move <code>Qb2</code>. Again, this may or may not belong to the game. When the current player has no Queen, then it surely does not.</p></li>
  </ul>
  
  <p>As the invalid moves are related to the representation rather than to the game, they should not be considered at all.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-12T18:08:33.343Z
Answers.Text: Great point.  In [M] games, which are played on Sudoku, the constraints make many positions (coordinates+value) illegal after the first placement.  There is no value in considering these illegal positions from the standpoint of placement, *but*, an important strategic layer is recognizing which placements minimize value of remaining, unplayed positions. (i.e. if I place an 8 here, it blocks my opponent from placing an 8 in that row, column or region.  Essentially, "how many strategic positions does this placement remove from the gameboard?")
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-12T03:49:42.523Z
Answers.LastActivityDate: 2018-01-12T03:49:42.523Z
Answers.UserDisplayName: maaartinus
Answers.Body: <p>An experimental paper exist in <a href="https://arxiv.org/abs/2006.14171" rel="nofollow noreferrer">arxiv</a> about the effect of whether to mask or to give negative rewards to invalid actions. There are some references in this paper which also discuss the effects and the mechanism to handle invalid actions. However, those main references are still only pre-prints in the arxiv (not published and presumably not peer-reviewed yet).</p>
  <p>On a way to handle that situation, other answers have given good practical methods to ignore the invalid actions. I just want to add one more trick to do that. You can pre-compute a binary vector as the mask for the actions, and add the log of the mask before the softmax operation. The log of 0 is -inf and exp(-inf) is 0 in Pytorch (I don't know if the same applies in Tensorflow).</p>
  <blockquote>
  <p><span class="math-container">$P(a_i| A'_t, X_t) = \text{softmax}(u_i+\log{m^t_i}), \forall i \in
   \{1,\dots,|A|\}$</span> and <span class="math-container">$m^t_i \in \{0,1\}$</span></p>
  </blockquote>
  <p>with <span class="math-container">$P(a_i| A'_t, X_t)$</span> is the probability to take action <span class="math-container">$a_i$</span> given  the action history <span class="math-container">$A'_t$</span> up to the <span class="math-container">$t$</span>-th step and the current environment's features <span class="math-container">$X_t$</span>, <span class="math-container">$u$</span> is the output of the last layer of the model, <span class="math-container">$A$</span> is the action space <span class="math-container">$m^t_i$</span> is the feasibility mask of action <span class="math-container">$a_i$</span> for the current step.
  Therefore,
  the probability of the invalid action is 0 after the softmax operation.   That way, you can treat the mask as the part of the state as the input to your model. This is actually more handy for algorithm which employs experience memory because the mask then can be saved in the experience memory too.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-11T17:07:33.693Z
Answers.LastActivityDate: 2021-07-13T09:47:02.280Z
Answers.LastEditDate: 2021-07-13T09:47:02.280Z
Answers.UserDisplayName: Sanyou
Answers.Body: <p>Just ignore the invalid moves.</p>
  <p>For exploration, it is likely that you won't just execute the move with the highest probability, but instead choose moves randomly based on the outputted probability. If you only punish illegal moves they will still retain some probability (however small) and therefore will be executed from time to time (however seldom). So you will always retain an agent which occasionally makes illegal moves.</p>
  <p>To me, it makes more sense to just set the probabilities of all illegal moves to zero and renormalise the output vector before you choose your move.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-16T19:04:51.383Z
Answers.Text: Do you think we need to take the invalid move with negative rewards for sample to train?
Answers.UserDisplayName: shtse8
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-18T08:12:53.837Z
Answers.Text: Maybe if there is consistently a lot of probability mass on illegal moves. Otherwise probably not.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-03-14T15:37:23.737Z
Answers.LastActivityDate: 2022-01-10T07:52:58.523Z
Answers.LastEditDate: 2022-01-10T07:52:58.523Z
Answers.UserDisplayName: BlindKungFuMaster
Body: <p>I want to create an AI which can play five-in-a-row/Gomoku. I want to use reinforcement learning for this.</p>
  <p>I use the <em>policy gradient</em> method, namely REINFORCE, with baseline. For the value and policy function approximation, I use a <em>neural network</em>. It has convolutional and fully connected layers. All of the layers, except for the output, are shared. The policy's output layer has <span class="math-container">$8 \times 8=64$</span> (the size of the board) output unit and <em>softmax</em> on them. So it is stochastic.</p>
  <p>But what if the network produces a very high probability for an invalid action? An invalid action is when the agent wants to check a square that has one <code>X</code> or <code>O</code> in it. I think it can be stuck in that game state.</p>
  <p>How should I handle this situation?</p>
  <p>My guess is to use the <em>actor-critic</em> method. For an invalid action, we should give a negative reward and pass the turn to the opponent.</p>
  
Tags: <reinforcement-learning><policy-gradients><actor-critic-methods><reinforce><reward-design>
Title: How should I handle invalid actions (when using REINFORCE)?
UserDisplayName: Molnár István
ThreadText: # How should I handle invalid actions (when using REINFORCE)?
  
  (Asked by: username_0 on 2017-03-14)
  
  I want to create an AI which can play five-in-a-row/Gomoku. I want to use reinforcement learning for this.
  
  I use the *policy gradient* method, namely REINFORCE, with baseline. For the value and policy function approximation, I use a *neural network*. It has convolutional and fully connected layers. All of the layers, except for the output, are shared. The policy's output layer has $8 \times 8=64$ (the size of the board) output unit and *softmax* on them. So it is stochastic.
  
  But what if the network produces a very high probability for an invalid action? An invalid action is when the agent wants to check a square that has one `X` or `O` in it. I think it can be stuck in that game state.
  
  How should I handle this situation?
  
  My guess is to use the *actor-critic* method. For an invalid action, we should give a negative reward and pass the turn to the opponent.
  
  **Tags:** reinforcement-learning, policy-gradients, actor-critic-methods, reinforce, reward-design
  
  
  ---
  
  ## 5 answers
  
  ### Answer by username_10 on 2017-03-14. Score: 22 | Accepted answer
  
  Just ignore the invalid moves.
  
  For exploration, it is likely that you won't just execute the move with the highest probability, but instead choose moves randomly based on the outputted probability. If you only punish illegal moves they will still retain some probability (however small) and therefore will be executed from time to time (however seldom). So you will always retain an agent which occasionally makes illegal moves.
  
  To me, it makes more sense to just set the probabilities of all illegal moves to zero and renormalise the output vector before you choose your move.
  
  > **Comments:**
  > **username_11**: Do you think we need to take the invalid move with negative rewards for sample to train?  
  > **username_10**: Maybe if there is consistently a lot of probability mass on illegal moves. Otherwise probably not.  
  
  ---
  
  ### Answer by username_1 on 2017-03-15. Score: 14
  
  Usually softmax methods in policy gradient methods using linear function approximation use the following formula to calculate the probability of choosing action $a$. Here, weights are $\theta$, and the features $\phi$ is a function of the current state $s$ and an action from the set of actions $A$.
  
  $$
  \pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum\_{b \in A} e^{\theta \phi(s, b)}}
  $$
  
  To eliminate illegal moves, one would limit the set of actions to only those that were legal, hence $Legal(A)$.
  
  $$
  \pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum\_{b \in Legal(A)} e^{\theta \phi(s, b)}}, \, a \in Legal(A)
  $$
  
  In pseudocode the formula may look like this:
  
  ```
  action_probs = Agent.getActionProbs(state)
  legal_actions = filterLegalActions(state, action_probs)
  best_legal_action = softmax(legal_actions)
  
  ```
  
  Whether using linear or non-linear function approximation (your neural network), the idea is to only use the legal moves when computing your softmax. This method means that only valid moves will be given by the agent, which is good if you wanted to change your game later on, and that the difference in value between the limited choice in actions will be easier to discriminate by the agent. It will also be faster as the number of possible actions decreases.
  
  > **Comments:**
  > **username_4**: The maths and pseudocode do not match here. Softmax over the legal move probabilities will adjust the relative probabilities. E.g. (0.3, 0.4, 0.2, 0.1) filtered with first and third item removed would be (0.0, 0.8, 0.0, 0.2) with your formula, but would be (0.0, 0.57, 0.0, 0.42) using the pseudocode. The pseudocode needs to take the logits, prior  to action probability calculations.  
  > **username_5**: How does one compute the gradient of the filtered version of Softmax? Seems like this would be necessary for backpropagation to work successfuly, yes?  
  > **username_2**: @username_5 Did you manage to find an answer? It seems like that would be the case to me but somehow in my toy example I'm only getting the right answer when using the log probabilities of the unfilitered softmax...  
  > **username_3**: @username_2 You could try to ask that as a separate question on our site (if it has not been asked before: I don't know).  
  
  ---
  
  ### Answer by username_6 on 2018-11-17. Score: 7
  
  I faced a similar issue recently with Minesweeper.
  
  The way I solved it was by ignoring the illegal/invalid moves entirely.
  
  1. Use the Q-network to predict the Q-values for all of your actions (valid and invalid)
  2. Pre-process the Q-values by setting all of the invalid moves to a Q-value of zero/negative number (depends on your scenario)
  3. Use a policy of your choice to select an action from the refined
     Q-values (i.e. greedy or Boltzmann)
  4. Execute the selected action and resume your DQN logic
  
  Hope this helps.
  
  > **Comments:**
  > **username_3**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/105285/discussion-on-answer-by-username_6-how-to-handle-invalid-moves-in-reinforcement-le).  
  
  ---
  
  ### Answer by username_7 on 2018-01-12. Score: 6
  
  IMHO the idea of invalid moves is itself invalid. Imagine placing an "X" at coordinates `(9, 9)`. You could consider it to be an invalid move and give it a negative reward. Absurd? Sure!
  
  But in fact your invalid moves are just *a relic of the representation* (which itself is straightforward and fine). The best treatment of them is to exclude them completely from any computation.
  
  This gets more apparent in chess:
  
  * In a positional representation, you might consider the move `a1-a8`, which only belongs in the game if there's a Rook or a Queen at `a1` (and some other conditions hold).
  * In a different representation, you might consider the move `Qb2`. Again, this may or may not belong to the game. When the current player has no Queen, then it surely does not.
  
  As the invalid moves are related to the representation rather than to the game, they should not be considered at all.
  
  > **Comments:**
  > **username_8**: Great point.  In [M] games, which are played on Sudoku, the constraints make many positions (coordinates+value) illegal after the first placement.  There is no value in considering these illegal positions from the standpoint of placement, *but*, an important strategic layer is recognizing which placements minimize value of remaining, unplayed positions. (i.e. if I place an 8 here, it blocks my opponent from placing an 8 in that row, column or region.  Essentially, "how many strategic positions does this placement remove from the gameboard?")  
  
  ---
  
  ### Answer by username_9 on 2021-07-11. Score: 2
  
  An experimental paper exist in [arxiv](https://arxiv.org/abs/2006.14171) about the effect of whether to mask or to give negative rewards to invalid actions. There are some references in this paper which also discuss the effects and the mechanism to handle invalid actions. However, those main references are still only pre-prints in the arxiv (not published and presumably not peer-reviewed yet).
  
  On a way to handle that situation, other answers have given good practical methods to ignore the invalid actions. I just want to add one more trick to do that. You can pre-compute a binary vector as the mask for the actions, and add the log of the mask before the softmax operation. The log of 0 is -inf and exp(-inf) is 0 in Pytorch (I don't know if the same applies in Tensorflow).
  
  > $P(a\_i| A'\_t, X\_t) = \text{softmax}(u\_i+\log{m^t\_i}), \forall i \in
  > \{1,\dots,|A|\}$ and $m^t\_i \in \{0,1\}$
  
  with $P(a\_i| A'\_t, X\_t)$ is the probability to take action $a\_i$ given the action history $A'\_t$ up to the $t$-th step and the current environment's features $X\_t$, $u$ is the output of the last layer of the model, $A$ is the action space $m^t\_i$ is the feasibility mask of action $a\_i$ for the current step.
  Therefore,
  the probability of the invalid action is 0 after the softmax operation. That way, you can treat the mask as the part of the state as the input to your model. This is actually more handy for algorithm which employs experience memory because the mask then can be saved in the experience memory too.
  
  
  ---
  
  