# How to implement a constrained action space in reinforcement learning?

I'm coding a reinforcement learning model with a PPO agent thanks to the very good Tensorforce library, built on top of Tensorflow.

The first version was very simple and I'm now diving into a more complex environment where all the actions are not available at each step.

Let's say there are 5 actions and their availability depends on an internal state (which is defined by the previous action and/or the new state/observation space) :

• 2 actions (0 and 1) are always available
• 2 actions (2 and 3) are only available when the internal_state == 0
• 1 action (4) is only available when the internal_state == 1

Hence, there is 4 actions available when internal_state == 0 and 3 actions available when internal_state == 1.

I'm thinking of a few possibilities to implement that :

1. Change the action space at each step, depending on the internal_state. I assume this is nonsense.
2. Do nothing : let the model understand that choosing an unavailable action has no impact.
3. Do -almost- nothing : impact slightly negatively the reward when the model chooses an unavailable action.
4. Help the model : by incorporating an integer into the state/observation space that informs the model what's the internal_state value + bullet point 2 or 3

Is there other ways to implement this ? From your experience, which one would be the best ?

The most straightforward solution is to simply make every action "legal", but implementing a consistent, deterministic mapping from potentially illegal actions to different legal actions. Whenever the PPO implementation you are using selects an illegal action, you simply replace it with the legal action that it maps to. Your PPO algorithm can then still update itself as if the illegal action were selected (the illegal action simply becomes like... a "nickname" for the legal action instead).

For example, in the situation you describe:

• 2 actions (0 and 1) are always available
• 2 actions (2 and 3) are only available when the internal_state == 0
• 1 action (4) is only available when the internal_state == 1

In cases where internal_state == 0, if action 4 was selected (an illegal action), you can always swap it out for one of the other actions and play that one instead. It doesn't really matter (theoretically) which one you pick, as long as you're consistent about it. The algorithm doesn't have to know that it picked an illegal action, whenever it picks that same illegal action in the future again in similar states it will consistently get mapped to the same legal action instead, so you just reinforce according to that behaviour.

The solution described above is very straightforward, probably the most simple to implement, but of course it... "smells" a bit "hacky". A cleaner solution would involve a step in the Network that sets the probability outputs of illegal actions to $$0$$, and re-normalizes the rest to sum up to $$1$$ again. This requires much more care to make sure that your learning updates are still performed correctly though, and is likely a lot more complex to implement on top of an existing framework like Tensorforce (if not already somehow supported in there out of the box).

For the first "solution", I wrote above that it does not matter "theoretically" how you choose you mapping. I absolutely do expect your choices here will have an impact on learning speed in practice though. This is because, in the initial stages of your learning process, you'll likely have close-to-random action selection. If some actions "appear multiple times" in the outputs, they will have a greater probability of being selected with the initial close-tor-andom action selection. So, there will be an impact on your initial behaviour, which has an impact on the experience that you collect, which in turn also has an impact on what you learn.

I certainly expect it will be beneficial for performance if you can include input feature(s) for the internal_state variable.

If some legal actions can be identified that are somehow "semantically close" to certain illegal actions, it could also be beneficial for performance to specifically connect those "similar" actions in the "mapping" from illegal to legal actions if you choose to go with that solution. For example, if you have a "jump forwards" action that becomes illegal in states where the ceiling is very low (because you'd bump your head), it may be better to map that action to a "move forwards" action (which is still kind of similar, they're both going forwards), than it would be to map it to a "move backwards" action. This idea of "similar" actions will only be applicable to certain domains though, in some domains there may be no such similarities between actions.

The objective is to design a proximal policy optimization component that has specific constraints on the action space dependent upon state driven rules, using a framework like Tensorforce.

Design Options Listed in the Question

These options are listed here for quick reference when reading the initial analysis below.

• Change the action space at each step, depending on the internal_state. I assume this is nonsense.
• Do nothing : let the model understand that choosing an unavailable action has no impact.
• Do -almost- nothing : impact slightly negatively the reward when the model chooses an unavailable action.
• Help the model : by incorporating an integer into the state/observation space that informs the model what's the internal_state value + bullet point 2 or 3

Initial Analysis

It is indeed sensible to change the action space for each move. That is, in fact, a proper representation for the problem as stated and the normal way humans play games and the way computers beat humans in Chess and Go.

The apparent senselessness of this idea is merely an artifact of the progress along the Tensorforce project road map and the progress along reinforcement theory, both young in the bigger picture. Reading the Tensorforce documentation and FAQ, it does not appear that the framework is designed to plug in a rules engine to determine the action space. This is not a shortcoming of the open source. There do not appear to be any papers providing theory or proposing algorithms for rule-conditioned Markov chain decisioning.

The do-nothing option is the one that fits into the current available strategies represented in the literature. The do-almost-nothing is probably the approach that will produce more reliable and perhaps more immediate desirable behavior.

The problem with the concept of helping the model is that it is not as strong an idea than extending the model. In open source, this would be done by extending the classes that represent the model, which would require some theoretical work prior to coding to

    a. Represent rule-conditioned learning in nomenclature
b. Represent convergence mathematically using the new nomenclature
c. Determining a method of convergence
d. Proving convergence
e. Rechecking
f. Defining a smooth and efficient algorithm
g. Providing PAC learning information for planning
f. Peer review
g. Extending the classes of the library
h. Proof of concept with the current problem above
i. Additional cases and metrics comparing the approach with the others
j. Extending the library flexibility to support more such dev


The extension of learning systems to cover the rule-constrained case is a great idea for a PhD thesis and might fly in research laboratories as a project proposal with many possible applications. Don't let all the steps dissuade the researcher. They're essentially a list of steps for any PhD thesis or funded AI laboratory project.

For a short term solution, helping the model might work, but it is not a sound strategy for furthering the ideas of AI along the reinforcement learning path. As a short term solution for a particular problem it may work fine. The do-almost-nothing idea may be more sound, since it fits within the convergence proofs that led to the particular implementation Tensorforce is likely to be using.

Renaming it from do-almost-nothing to assist-convergence may help develop the right perspective before giving it a try. You may find that you have to attenuate the assist as you approach convergence to avoid overshoot just as with a learning rate.

• What typically happens, in e.g. AlphaGo, is that the low-level representation in the Neural Network represents a very large action space, most of which is impossible in the current state (it does this due to limitations of simple NNs which output fixed size vectors). Then another part of code applies a filter to select and normalise probabilities for only allowed moves. The combined NN and filter are part of the agent. So it is fair to say that the agent as a whole will "change the action space for each move" - I don't know how that might be achieved inside the Tensorforce library though. – Neil Slater Oct 21 '18 at 19:06

Normally, the set of actions that the agent can execute does not change over time, but some actions can become impossible in different states (for example, not every move is possible in any position of the TicTacToe game).

Take a look as example at pice of code https://github.com/haje01/gym-tictactoe/blob/master/examples/base_agent.py :

ava_actions = env.available_actions()
action = agent.act(state, ava_actions)
state, reward, done, info = env.step(action)