Answers.Body: <blockquote>
  <p>Does anyone know any paper regarding this subject?</p>
  </blockquote>
  <p>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).</p>
  <p>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.</p>
  <blockquote>
  <p>Are there other approaches to deal with variable action spaces?</p>
  </blockquote>
  <p>The problem you describe is mostly a problem in <strong>Reinforcement Learning with function approximation</strong>, 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 <span class="math-container">$Q(s, a)$</span> values as commonly used in the tabular, value-based algorithms does not need to contain entries for all possible <span class="math-container">$(s, a)$</span> pairs; it's fine if it only contains entries for <span class="math-container">$(s, a)$</span> pairs such that <span class="math-container">$a$</span> is legal in <span class="math-container">$s$</span>.</p>
  <p>Variable action spaces primarily turn into a problem in Deep RL approaches, <strong>because we normally work with a fixed neural network architecture</strong>. A DQN-style algorithm involves neural networks that take feature vectors describing states <span class="math-container">$s$</span> as inputs, and provide <span class="math-container">$Q(s, a)$</span> 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).</p>
  <p>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 <strong>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</strong>.</p>
  <p>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 <span class="math-container">$(s, a)$</span>. If you can do that, then you could, for example, build neural networks which:</p>
  <ul>
  <li>Take a feature vector <span class="math-container">$x(s, a)$</span> as input, which describes (hopefully in some meaningful way) the full pair of the state <span class="math-container">$s$</span> <strong>and</strong> the action <span class="math-container">$a$</span></li>
  <li>Produce a single <span class="math-container">$\hat{Q}(s, a)$</span> estimate as output, for the specific pair of state + action given as input, rather than producing multiple outputs.</li>
  </ul>
  <p>If you can do that, then in any given state <span class="math-container">$s$</span> you can simply loop through all the legal actions <span class="math-container">$A(s)$</span>, compute <span class="math-container">$\hat{Q}(s, a)$</span> estimates for them all (<strong>note</strong>: we now require <span class="math-container">$\lvert A(s) \rvert$</span> 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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T16:45:32.197Z
Answers.Text: I am trying to do this state-action representation and create a DQN-like network that would output the Q-value of the x(s,a), like a regression problem. Having read the tf_agents documentation, I do not think that I can model it with this. Is there a way to model it with tf_agents or should I do it from scratch ?
Answers.UserDisplayName: ddaedalus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T17:32:13.027Z
Answers.Text: @ddaedalus Hmmm I'm not sure, I'm not super familiar with tf_agents. I must say that I don't believe I've ever seen anyone in the literature actually doing this thing with state-action pairs being the inputs, rather than states inputs and actions outputs. Almost everyone in all the literature always seems to assume they can just predetermine the number of actions. So, since this is so rarely done in the literature, it would indeed be very well possible that it's not easily supported by such frameworks and requires more work from scratch
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T17:48:00.593Z
Answers.Text: In my case, every action is different from the other. If you choose an action, then it cannot be appeared again. Also from each state, you always have different actions or actions that you have seen again but not taken yet. Do you think that I could create an environment that inherits from gym environment? I doubt that because of what you said.
Answers.UserDisplayName: ddaedalus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T18:14:29.677Z
Answers.Text: @ddaedalus Again not 100% sure... I'm thinking that might be possible though. If I remember correctly, you do have to predefine your action space in advance, but it does not have to be discrete; you can specify continuous action spaces, which is used for all these continuous control envs (the ones where you have to make all sorts of robots learn how to walk etc.). I suppose that in your situation you'll also have to find some action representation (probably with binary or numeric features). If you have upper/lower bounds on your feature values, you can define your action space with that?
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T18:23:59.980Z
Answers.Text: @DennisSoemers Both my state and actions are texts so I have word embeddings with a mean pooling layer for each text and I concatenate state and action embeddings. So it's numeric features for x(s,a).
Answers.UserDisplayName: ddaedalus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-17T07:41:05.087Z
Answers.Text: This is great feedback and interesting thoughts, thanks for that. I find many papers regarding "large action space"'s, which is in pretty much the same issue. I think the paper "Discrete Sequential Prediction of continuous action for Deep RL" is very interesting since it predicts a sequence of actions using Recurrent Neural Networks instead, which solves the fixed network issue. We will do our master thesis in this subject and I hope we'll collect more information in this matter.
Answers.UserDisplayName: Rikard Olsson
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-13T17:07:53.980Z
Answers.LastActivityDate: 2021-12-29T15:28:24.103Z
Answers.LastEditDate: 2021-12-29T15:28:24.103Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <blockquote>
  <ol start="3">
  <li>Another approach that came across was to, assuming the number of different action set <span class="math-container">$n$</span> is quite small, have functions <span class="math-container">$f_{\theta_1}$</span>, <span class="math-container">$f_{\theta_2}$</span>, ..., <span class="math-container">$f_{\theta_n}$</span> that returns the action regarding that perticular state with <span class="math-container">$n$</span> valid actions. In other words, the performed action of a state <span class="math-container">$s$</span> with 3 number of actions will be predicted by <span class="math-container">$\underset{a}{\text{argmax}} \ f_{\theta_3}(s, a)$</span>.</li>
  </ol>
  </blockquote>
  <p>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 <span class="math-container">$7 \cdot 4 \cdot 2=56$</span> 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 <span class="math-container">$2^{56}$</span>, but also surely far too big for being practical.</p>
  <blockquote>
  <p>Are there other approaches to deal with variable action spaces?</p>
  </blockquote>
  <p>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 <em>legal</em> action returning the best award.</p>
  <hr />
  <p>Note that your expression</p>
  <p><span class="math-container">$$\forall s \in S: \exists s' \in S: A(s) \neq A(s') \wedge s \neq s'$$</span></p>
  <p>can be simplified to</p>
  <p><span class="math-container">$$\forall s \in S: \exists s' \in S: A(s) \neq A(s')$$</span></p>
  <p>or even</p>
  <p><span class="math-container">$$|A(s)|_{s \in S} &gt; 1$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-26T06:09:50.553Z
Answers.LastActivityDate: 2021-12-29T15:30:46.407Z
Answers.LastEditDate: 2021-12-29T15:30:46.407Z
Answers.UserDisplayName: maaartinus
Body: <p>This question is about <strong>Reinforcement Learning</strong> and <strong>variable action spaces for every/some states</strong>.</p>
  <h3>Variable action space</h3>
  <p>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 <span class="math-container">$$\forall s \in S: \exists s' \in S: A(s) \neq A(s') \wedge s \neq s'$$</span></p>
  <p>That is, for every state, there exists some other state which does not have the same action set.</p>
  <p>In figures 1 and 2, there's a relatively small amount of actions per state. Instead imagine states <span class="math-container">$s \in S$</span> with <span class="math-container">$m_s$</span> number of actions, where <span class="math-container">$1 \leq m_s \leq n$</span> and <span class="math-container">$n$</span> is a really large integer.</p>
  <p><a href="https://i.sstatic.net/q2Huu.png" rel="noreferrer"><img src="https://i.sstatic.net/q2Huu.png" alt="Some MDP's" /></a></p>
  <h3>Environment</h3>
  <p>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 <span class="math-container">$M : s \rightarrow A'$</span> that takes a state as input and returns a valid number of actions.</p>
  <h3>Approches</h3>
  <ol>
  <li><p>A naive approach to this problem (discussed <a href="https://ai.stackexchange.com/q/7755/2444">here</a> and <a href="https://ai.stackexchange.com/q/2219/2444">here</a>) is to define the action set equally for every state, return a negative reward whenever the performed action <span class="math-container">$a \notin A(s)$</span> and move the agent into the same state, thus letting the agent &quot;learn&quot; what actions are valid in each state. This approach has two obvious drawbacks:</p>
  <ul>
  <li><p>Learning <span class="math-container">$A$</span> takes time, especially when the Q-values are not updated until either termination or some statement is fulfilled (like in <a href="https://datascience.stackexchange.com/q/20535/10640">experience replay</a>)</p>
  </li>
  <li><p>We know <span class="math-container">$A$</span>, why learn it?</p>
  </li>
  </ul>
  </li>
  <li><p>Another approach (<a href="https://ai.stackexchange.com/a/8564/2444">first answer here</a>, also very much alike proposals from papers such as <a href="https://arxiv.org/pdf/1512.07679" rel="noreferrer">Deep Reinforcement Learning in Large Discrete Action Spaces</a> and <a href="https://arxiv.org/pdf/1705.05035" rel="noreferrer">Discrete Sequential Prediction of continuous action for Deep RL</a>) 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.</p>
  </li>
  <li><p>Another approach that came across was to, assuming the number of different action set <span class="math-container">$n$</span> is quite small, have functions <span class="math-container">$f_{\theta_1}$</span>, <span class="math-container">$f_{\theta_2}$</span>, ..., <span class="math-container">$f_{\theta_n}$</span> that returns the action regarding that perticular state with <span class="math-container">$n$</span> valid actions. In other words, the performed action of a state <span class="math-container">$s$</span> with 3 number of actions will be predicted by <span class="math-container">$\underset{a}{\text{argmax}} \ f_{\theta_3}(s, a)$</span>.</p>
  </li>
  </ol>
  <p>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.</p>
  <p><strong>Does anyone know any paper regarding this subject? Are there other approaches to deal with variable action spaces?</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-14T23:28:53.213Z
Comments.Text: Have a similar issue, and my immediate thoughts are to perform some transformation of the problem into a domain where the action space *is* fixed. For instance, if I am working in active learning, where the action is to select an example from a unlabelled training dataset (without replacement), then perhaps a different formulation where the action is to select a class, or point in data space might work as well (this will have a fixed/static action space)
Comments.UserDisplayName: information_interchange
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-23T09:17:34.173Z
Comments.Text: I have the same question. The best answer I have found is the following paper:
  [Learning Action Representation for Reinforcement Learning](https://arxiv.org/abs/1902.00183)
Comments.UserDisplayName: NameVergessen
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-11T19:40:30.300Z
Comments.Text: How about your master thesis? Have you figured out methods to solve your question or anything else you want to share? I found the most related works as listed below are large action spaces.
Comments.UserDisplayName: DongDong Chen
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-11T22:08:23.537Z
Comments.Text: @DongDongChen we used a modified version of the https://arxiv.org/pdf/1512.07679.pdf paper, along with an ILP solver, which worked ok for us in the thesis. However, I think our version was very specific to our instance of the problem and was hard to generalize.
Comments.UserDisplayName: Rikard Olsson
Tags: <reinforcement-learning><reference-request><deep-rl><function-approximation><action-spaces>
Title: Are there other approaches to deal with variable action spaces?
UserDisplayName: Rikard Olsson
ThreadText: # Are there other approaches to deal with variable action spaces?
  
  (Asked by: username_0 on 2018-12-12)
  
  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.
  
  [![Some MDP's](https://i.sstatic.net/q2Huu.png)](https://i.sstatic.net/q2Huu.png)
  
  ### 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](https://ai.stackexchange.com/q/7755/2444) and [here](https://ai.stackexchange.com/q/2219/2444)) 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](https://datascience.stackexchange.com/q/20535/10640))
     * We know $A$, why learn it?
  2. Another approach ([first answer here](https://ai.stackexchange.com/a/8564/2444), also very much alike proposals from papers such as [Deep Reinforcement Learning in Large Discrete Action Spaces](https://arxiv.org/pdf/1512.07679) and [Discrete Sequential Prediction of continuous action for Deep RL](https://arxiv.org/pdf/1705.05035)) 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?**
  
  **Tags:** reinforcement-learning, reference-request, deep-rl, function-approximation, action-spaces
  
  > **Comments:**
  > **username_1**: Have a similar issue, and my immediate thoughts are to perform some transformation of the problem into a domain where the action space *is* fixed. For instance, if I am working in active learning, where the action is to select an example from a unlabelled training dataset (without replacement), then perhaps a different formulation where the action is to select a class, or point in data space might work as well (this will have a fixed/static action space)  
  > **username_2**: I have the same question. The best answer I have found is the following paper: [Learning Action Representation for Reinforcement Learning](https://arxiv.org/abs/1902.00183)  
  > **username_3**: How about your master thesis? Have you figured out methods to solve your question or anything else you want to share? I found the most related works as listed below are large action spaces.  
  > **username_0**: @username_3 we used a modified version of the https://arxiv.org/pdf/1512.07679.pdf paper, along with an ILP solver, which worked ok for us in the thesis. However, I think our version was very specific to our instance of the problem and was hard to generalize.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2018-12-13. Score: 18
  
  > 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.
  
  > **Comments:**
  > **username_0**: This is great feedback and interesting thoughts, thanks for that. I find many papers regarding "large action space"'s, which is in pretty much the same issue. I think the paper "Discrete Sequential Prediction of continuous action for Deep RL" is very interesting since it predicts a sequence of actions using Recurrent Neural Networks instead, which solves the fixed network issue. We will do our master thesis in this subject and I hope we'll collect more information in this matter.  
  > **username_5**: I am trying to do this state-action representation and create a DQN-like network that would output the Q-value of the x(s,a), like a regression problem. Having read the tf_agents documentation, I do not think that I can model it with this. Is there a way to model it with tf_agents or should I do it from scratch ?  
  > **username_4**: @username_5 Hmmm I'm not sure, I'm not super familiar with tf_agents. I must say that I don't believe I've ever seen anyone in the literature actually doing this thing with state-action pairs being the inputs, rather than states inputs and actions outputs. Almost everyone in all the literature always seems to assume they can just predetermine the number of actions. So, since this is so rarely done in the literature, it would indeed be very well possible that it's not easily supported by such frameworks and requires more work from scratch  
  > **username_5**: In my case, every action is different from the other. If you choose an action, then it cannot be appeared again. Also from each state, you always have different actions or actions that you have seen again but not taken yet. Do you think that I could create an environment that inherits from gym environment? I doubt that because of what you said.  
  > **username_4**: @username_5 Again not 100% sure... I'm thinking that might be possible though. If I remember correctly, you do have to predefine your action space in advance, but it does not have to be discrete; you can specify continuous action spaces, which is used for all these continuous control envs (the ones where you have to make all sorts of robots learn how to walk etc.). I suppose that in your situation you'll also have to find some action representation (probably with binary or numeric features). If you have upper/lower bounds on your feature values, you can define your action space with that?  
  > **username_5**: @username_4 Both my state and actions are texts so I have word embeddings with a mean pooling layer for each text and I concatenate state and action embeddings. So it's numeric features for x(s,a).  
  
  ---
  
  ### Answer by username_6 on 2020-01-26. Score: 4
  
  > 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$$
  
  
  ---
  
  