2
$\begingroup$

I'm training a reinforcement model playing a game with self-learning. For each state, the agent can select one or several simultaneous actions from a list of possible actions. One possible action is a binary choice that can make other actions irrelevant (not illegal, just irrelevant). Some actions do however become "illegal" for certain states. And some combinations of actions are illegal.

My plan is to produce a fixed-length vector of binary values indicating the agent's choice of actions given a state. I have two questions:

Question 1: In the tutorials I've done the algorithm typically selects ONE action from a list of possible actions using something like $\text{argmax}_{a \in > \mathcal{A}} \hat q(s,a)$. I want to instead predict an action vector, not just an action index. What is the best way to do this? The number of possible action vectors is huge, so I'm worried the task becomes very hard...

My second question is how to handle the legality of various combinations. Assuming there is a good way to predict a vector of actions per Question 1 (i.e. the agents act method outputs a vector [0,0,0,1,1,0,1] where each value indicates if action with index n is taken or not) I need to decide how to handle illegal combinations of actions.

The response to this question "How to handle a changing action space in Reinforcement Learning" claims that

You don't need to do anything special to handle [illegal actions]. 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)$.

Question 2: Am I correct to just run the prediction step as if all actions can be selected together, and then remove all vectors of illegal actions from the predictions before selecting which one to take? What if the network only produces illegal vectors? It feels like this might get very sparse...

$\endgroup$

1 Answer 1

0
$\begingroup$

The number of possible action vectors is huge, so I'm worried the task becomes very hard.

If each component of the action vector is "independent", then you could just parameterize a bunch of univariate distributions for each component, and sample them independently.

Of course, this only works when the components are really independent -- for example, if your game is actually the "product" of two MDPs, where you're trying to train your agent to multi-task by playing two games simultaneously, then game 1 action components and game 2 action components are independent. On the other hand, if the game is a flight simulator, and one action component is yaw and another is roll, and another is pitch, these are quite dependent on each other.*

In the case where components of an action vector are dependent, you can model the distribution auto-regressively: $\pi(x,y,z;s) = \pi(z|x,y;s)\pi(y|x;s)\pi(x;s)$, using a neural network to parameterize each factor. This is fairly easy to sample from, and lets you model complicated joint distributions.

What if the network only produces illegal vectors?

This shouldn't be possible, since at least one action must be legal in every non-terminal state of an MDP. In particular, for a factored distribution like $\pi(z|x,y;s)\pi(y|x;s)\pi(x;s)$, you would

  1. first sample from $\pi(x;s)$, masking out all $x$ which are illegal.
  2. This guarantees that $\pi(y|x;z)$ contains some $y$ for which the combination $(x,y)$ is legal. Mask out the other y's which are illegal and sample.
  3. Repeat in the same manner for $z$.

*Most situations probably fall somewhere in between these two examples in terms of action independence, and you just have to use judgement to trade-off between more expressive policies, and easier to work with policies.

$\endgroup$
1
  • $\begingroup$ thank you! I will study your answer. $\endgroup$
    – langkilde
    Aug 8, 2021 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.