7
$\begingroup$

This question is regarding Reinforcement Learning and different/inconsistent action space for every/some states.

What do I mean by inconsistent action space?

Let 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 "inconsistent 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 do not have the same action set. In the figures (1, 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

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 seam 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. E.i, 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 cannot find papers directly regarding this matter. My questions are therefore

  1. Does anyone know any paper regarding this subject?
  2. Is the terminology wrong? "Inconsistant", "Irregular", "Different"... ?
  3. Anyone having another approach worth digging into?
$\endgroup$
5
$\begingroup$
  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 every 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.

  1. Is the terminology wrong? "Inconsistant", "Irregular", "Different"... ?

I wouldn't use inconsistent, because that word can be interpreted as implying that something would be "wrong" or "ill-defined". I would say that you have a variable action set (the action set varies per state). When I search for that, there aren't a lot of results either though... but I think that term would be more promising.

  1. Anyone having another approach worth digging into?

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Rikard Olsson Dec 17 '18 at 7:41
0
$\begingroup$

The misconception is to ignore the game tree. A Reinforcement Learning robot doesn't life outside of any rules, but he acts within the given game. Before an artificial Intelligence algorithm can be constructed, the game has to be formalized. A game like chees has a different kind of action space, than a grasping robot. Formalizing the game rules is not an reinforcement learning problem, except the aim is to reverse engineering an existing game. That means, use an existing game log for game-rule induction.

If the aim is only to construct a game-playing agent, the possible action space of the robot is the obeys to the game tree. The question is not how to solve a markov decision problem, the question is which kind of game is available. From the terminology it make sense to search for games which have an Irregular, discrete or continuous action space. The action space of TicTacToe for example is limited to a 9x9 matrix, while the action space of a car's wheel is from -180 degree to +180 degree.

$\endgroup$
  • $\begingroup$ I'm not sure if I'm clear enough, but the answer you're giving is obvious. This is not a question on how to construct a game-playing agent. Nor how to solve some MDP in this matter (since it can be done with any of the three approaches given), but rather exploring what is an (or what is the most) efficient way in a "inconsistent action space"-environment. $\endgroup$ – Rikard Olsson Dec 12 '18 at 15:04
  • $\begingroup$ @RikardOlsson The environment for deep reinforcement learning agents is a game, for example “Cart-pole”, or “Puddle World”. If the question is not how to explore a game by an agent, we have to ask under which conditions games are created. The “cart-pole” game was created according to a real-life model, it's a balancing task for a non-linear system which is hard to solve by ordinary differential equations. $\endgroup$ – Manuel Rodriguez Dec 12 '18 at 16:19
  • $\begingroup$ Yes, I could add more information of the environment. Still, the question is not how to solve (or construct a perticular model for) a specific game. This is a research question. Take one of the papers I included. They’re using an actor-critic model. For each state, they approximate an action set (with the actor network) and does not include the whole action space. But Ill update the question to make it clearer $\endgroup$ – Rikard Olsson Dec 12 '18 at 17:58

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.