Are there other approaches to deal with variable action spaces?

Question

This question is about Reinforcement Learning and variable action spaces for every/some states.

Variable action space

Let's say you have an MDP, where the number of actions varies between states (for example like in Figure 1 or Figure 2). We can express a variable action space formally as $$\forall s \in S: \exists s' \in S: A(s) \neq A(s') \wedge s \neq s'$$

That is, for every state, there exists some other state which does not have the same action set.

In figures 1 and 2, there's a relatively small amount of actions per state. Instead imagine states $s \in S$ with $m_s$ number of actions, where $1 \leq m_s \leq n$ and $n$ is a really large integer.

Environment

To get a better grasp of the question, here's an environment example. Take Figure 1 and let it explode into a really large directed acyclic graph with a source node, huge action space and a target node. The goal is to traverse a path, starting at any start node, such that we'll maximize the reward which we'll only receive at the target node. At every state, we can call a function $M : s \rightarrow A'$ that takes a state as input and returns a valid number of actions.

Approches

1. A naive approach to this problem (discussed here and here) is to define the action set equally for every state, return a negative reward whenever the performed action $a \notin A(s)$ and move the agent into the same state, thus letting the agent "learn" what actions are valid in each state. This approach has two obvious drawbacks:

   • Learning $A$ takes time, especially when the Q-values are not updated until either termination or some statement is fulfilled (like in experience replay)

   • We know $A$, why learn it?

2. Another approach (first answer here, also very much alike proposals from papers such as Deep Reinforcement Learning in Large Discrete Action Spaces and Discrete Sequential Prediction of continuous action for Deep RL) is to instead predict some scalar in continuous space and, by some method, map it into a valid action. The papers are discussing how to deal with large discrete action spaces and the proposed models seem to be a somewhat solution for this problem as well.

3. Another approach that came across was to, assuming the number of different action set $n$ is quite small, have functions $f_{\theta_1}$, $f_{\theta_2}$, ..., $f_{\theta_n}$ that returns the action regarding that perticular state with $n$ valid actions. In other words, the performed action of a state $s$ with 3 number of actions will be predicted by $\underset{a}{\text{argmax}} \ f_{\theta_3}(s, a)$.

None of the approaches (1, 2 or 3) are found in papers, just pure speculations. I've searched a lot, but I cannot find papers directly regarding this matter.

Does anyone know any paper regarding this subject? Are there other approaches to deal with variable action spaces?

Answer 1

Does anyone know any paper regarding this subject?

I'm not familiar with any off the top of my head. I do know that the vast majority of Reinforcement Learning literature focuses on settings with a fixed action space (like robotics where your actions determine how you attempt to move/rotate a particular part of the robot, or simple games where you always have the same set of actions to move and maybe ''shoot'' or ''use'' etc.). Another common class of settings is where the action space can easily be treated as if it always were the same (by enumerating all actions that ever could be legal in some state), and filtering out illegal actions in some sort of post-processing steps (e.g. RL work in board games).

So, there might be something out there, but it's certainly not common. Most RL people like to involve as little domain knowledge as possible, and I suppose that a function that generates a legal set of actions given a particular state can very much be considered to be domain knowledge.

Are there other approaches to deal with variable action spaces?

The problem you describe is mostly a problem in Reinforcement Learning with function approximation, in particular, function approximation using Neural Networks. If you can get away with using tabular RL algorithms, the problem instantly disappears. For example, a table of $Q(s, a)$ values as commonly used in the tabular, value-based algorithms does not need to contain entries for all possible $(s, a)$ pairs; it's fine if it only contains entries for $(s, a)$ pairs such that $a$ is legal in $s$.

Variable action spaces primarily turn into a problem in Deep RL approaches, because we normally work with a fixed neural network architecture. A DQN-style algorithm involves neural networks that take feature vectors describing states $s$ as inputs, and provide $Q(s, a)$ estimates as outputs. This immediately implies that we need one output node for every action, which means you have to enumerate all the actions, which is where your problem comes in. Similarly, policy gradient methods traditionally also require one output node per action, which again means you have to be able to enumerate all the actions in advance (when determining the network architecture).

If you still want to use Neural Networks (or other kinds of function approximators with similar kinds of inputs and outputs), the key to addressing your problem (if none of the suggestions you've already listed in the question are to your liking) is to realize that you'll have to find a different way to formulate your inputs and outputs, such that you are no longer required to enumerate all actions in advance.

The only way I can think of doing that really is if you are able to compute meaningful input features for complete state-action pairs $(s, a)$. If you can do that, then you could, for example, build neural networks which:

• Take a feature vector $x(s, a)$ as input, which describes (hopefully in some meaningful way) the full pair of the state $s$ and the action $a$
• Produce a single $\hat{Q}(s, a)$ estimate as output, for the specific pair of state + action given as input, rather than producing multiple outputs.

If you can do that, then in any given state $s$ you can simply loop through all the legal actions $A(s)$, compute $\hat{Q}(s, a)$ estimates for them all (note: we now require $\lvert A(s) \rvert$ passes through the network rather than just a single pass as would normally be required in DQN-style algorithms), and otherwise proceed similarly to standard DQN-style algorithms.

Obviously, the requirement of having good input features for actions is not always going to be satisfied... but I doubt there are many good ways to get around that. It's very similar to the situation with states really. In tabular RL, we enumerate all states (and all actions). With function approximation, we usually still enumerate all actions, but avoid the enumeration of all states by replacing them with meaningful feature vectors (which enables generalization across states). If you want to avoid enumerating actions, you'll in a very similar way have to have some way of generalizing across actions, which again means you need features to describe actions.

Answer 2

3. Another approach that came across was to, assuming the number of different action set $n$ is quite small, have functions $f_{\theta_1}$, $f_{\theta_2}$, ..., $f_{\theta_n}$ that returns the action regarding that perticular state with $n$ valid actions. In other words, the performed action of a state $s$ with 3 number of actions will be predicted by $\underset{a}{\text{argmax}} \ f_{\theta_3}(s, a)$.

That sounds pretty complicated and the number of different action sets is usually very high, even for the simplest games. Imagine checkers, ignore promotions and jumping, for simplicity, and there are some $7 \cdot 4 \cdot 2=56$ possible actions (which is fine), but the number of different sets of these actions is much higher. It's actually difficult to compute how many such sets are possible in a real game - it's surely much less than $2^{56}$, but also surely far too big for being practical.

Are there other approaches to deal with variable action spaces?

Assuming the number of actions is not too big, you can simply ignore actions which don't apply in a given state. That's different from learning - you don't have to learn to return negative reward for illegal actions, you simply don't care and select the legal action returning the best award.

---

Note that your expression

$$\forall s \in S: \exists s' \in S: A(s) \neq A(s') \wedge s \neq s'$$

can be simplified to

$$\forall s \in S: \exists s' \in S: A(s) \neq A(s')$$

or even

$$|A(s)|_{s \in S} > 1$$