5
$\begingroup$

I'm training a Reinforcement Model playing a game with self learning.(A second instance is its opponent). An agent has a set of possible action to choose from in each state. Those actions usually remain the same. Q-Learning tries than to map best actions to highest rewards. DQN tries to estimate Q values for unseen states.

I have now an example, where at some time some actions can not be taken. In fact the remaining possible actions get fewer and fewer leading finally to only one possible action before the game ends. How do I handle that? Do I simply give a huge negativ reward when an action is chosen which can not be taken and let it choose again? In this way the model has to learn that those actions can not be taken in certain situations.

Is there maybe a different approach which would neglect learning this?

$\endgroup$
6
$\begingroup$

You don't need to do anything special to handle this. The only thing you need to change is to not take any illegal actions.

The typical Q-learning greedy policy is $\pi(s) = \text{argmax}_{a \in \mathcal{A}} \hat q(s,a)$ and the epsilon-greedy rollout policy is very similar. Simply replace the action space $\mathcal{A}$ with just the legal actions $\mathcal{A}_\text{legal}(s)$.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure if understand this right. When imagining Q-learning quite simple as dictionary mapping states to best actions, then you suggest just picking the legal action with the highest reward is the best way? In DQN the network responds to the state vector with its fixed length output vector. So again just pick the highest rated legal action? I find this a bit strange, because I assume my network will often rate illegal actions quite high and I just don't pick them. Not picking them somehow doesn't contribute to the learning. Wouldn't the network then never learn that such boarders exists? $\endgroup$ – Mr.Sh4nnon Nov 20 '18 at 21:53
  • 2
    $\begingroup$ The network doesn't need to learn what's legal and what's not legal, because your move validity checking code can take care of it. $\endgroup$ – shimao Nov 20 '18 at 21:56
  • 2
    $\begingroup$ It's typical to have a rule-checking part to the program outside of the RL component. This is the case in AlphaGo, for example. stats.stackexchange.com/questions/328835/… $\endgroup$ – Sycorax says Reinstate Monica Nov 20 '18 at 22:01
  • $\begingroup$ @shimao and sycorax thank you! Those are very convincing arguments. One further question. Do I assume correctly that the reward will be connected in the back propagation with the legal action I forced it to take? I first believed the network will be encouraged to take the illegal action later again. But updating the network with the legal action it actually took and the reward will hinder illegal actions in future anyway. $\endgroup$ – Mr.Sh4nnon Nov 20 '18 at 22:21
  • 1
    $\begingroup$ @Mr.Sh4nnon Yes; you update the Q function for the legal action you decided to take. $\endgroup$ – BigBadMe Nov 21 '18 at 17: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.