Know Your Action Set: Learning Action Relations for Reinforcement Learning

Ayush Jain, Norio Kosaka, Kyung-Min Kim, Joseph J. LimICLR 2022 · OpenReview

Standard reinforcement learning (RL) typically assumes an agent chooses from a static, fixed "menu" of independent actions. However, real-world applications—such as a robot selecting tools from a changing toolbox or a recommender system suggesting items from a daily-updated catalog—often feature a varying action space.

Existing methods for handling varying action spaces generally treat actions as independent entities. This paper argues that this is a fundamental flaw: the optimality of an action often depends heavily on what other actions are currently available. For example, in a repair task, picking up a nail is only a viable strategy if a hammer is also in the toolbox. If the hammer is missing, the agent must pivot to a different strategy, such as using a hook and adhesive tape.

Action interdependence in varying action sets.

To tackle the challenge of learning these complex "action-action" and "state-action-action" relationships, the authors introduce AGILE, a novel policy architecture that leverages Graph Attention Networks (GATs) to model interdependence between actions.

The AGILE Architecture

The core innovation of AGILE (Action Graph for Interdependence Learning) is treating the available action set as a fully connected graph rather than a simple list.

The AGILE architecture.

The architecture operates through four main steps:

  1. Action Graph Construction: At every timestep, AGILE builds a graph where each node represents an available action. Node features are initialized using a combination of the current environment state and the specific action's representation (e.g., a text embedding or behavioral vector).
  2. Graph Attention Network (GAT): The graph is processed by a GAT, allowing each action to "attend" to every other available action. Through message passing, the model computes relational action representations that encode how useful an action is given the presence of others.
  3. Action Set Summary: The model mean-pools these relational features to create a global "summary" of the agent's current capabilities, which is fed back into the decision-making process.
  4. Utility Network: A shared utility network computes a score (Q-value or probability) for each action in parallel, utilizing its specific relational features, the global state, and the action set summary.

AGILE is highly flexible and can be integrated into both policy-gradient methods (like PPO) and value-based methods (like DQN).

Experimental Setup

The authors benchmarked AGILE across four diverse environments designed to test action interdependence:

  • Dig Lava Grid Navigation: A 2D maze where the agent receives a random subset of "skills." Some skills allow for shortcuts through lava, but only if the agent knows it has the complementary skill before taking the risk.
  • CREATE (Chain Reaction Tool Environment): A physics-based puzzle requiring the agent to place tools to move a ball to a goal. The environment features "activator" tools (e.g., fire, electricity) that "general" tools (e.g., cannon, fan) require to function.
  • RecSim: A simulated recommender system where the goal is to recommend a list of items that are diverse yet coherent.
  • Real-Data Recommender System: A dataset of four weeks of interaction data from an online campaign, rewarding actual user clicks and list-wise coherence.

Key Insights and Results

AGILE consistently outperformed baseline models—which either ignored action sets or treated actions independently—across all four environments.

  • Significant Performance Gains: In the complex CREATE tool-use environment, AGILE demonstrated a 30-50% improvement over ablations that lacked relational action features.
  • Attention Reveals Reasoning: Visualizing the GAT's attention weights showed that the model actively "reasons" about dependencies. For instance, in CREATE, when considering placing a trampoline, the model exhibited high attention toward the "spring" tool (its activator), effectively verifying if the sequence was viable.
  • Zero-Shot Generalization: Because AGILE relies on action representations rather than fixed IDs, it successfully generalized to unseen actions during testing in both the CREATE and RecSim environments.
  • Context-Aware Risk Taking: In the Grid World task, AGILE was the only model that consistently learned to take risky shortcuts, as it could reliably verify it possessed the necessary digging tools to survive the path.
  • Beyond Global Summaries: The experiments proved that simply providing a global "summary" of available actions (e.g., via a Deep Set or LSTM) is insufficient for complex tasks. Agents require per-action relational features to understand exactly how specific tools interact.

Limitations and Future Directions

While highly effective, AGILE's fully connected graph approach results in $O(N^2)$ computational complexity relative to the number of actions ($N$). While manageable for the paper's experiments (up to 250 actions), this could become a bottleneck for systems with thousands of actions. The authors suggest that incorporating domain knowledge to pre-define certain edges (creating a sparse graph) or exploring hierarchical graph structures could handle much larger action spaces more efficiently. Additionally, the model's success relies heavily on high-quality action representations, and learning these embeddings end-to-end alongside the policy remains an ongoing challenge for real-world deployment.

Summary updated

Abstract

Intelligent agents can solve tasks in various ways depending on their available set of actions. However, conventional reinforcement learning (RL) assumes a fixed action set. This work asserts that tasks with varying action sets require reasoning of the relations between the available actions. For instance, taking a nail-action in a repair task is meaningful only if a hammer-action is also available. To learn and utilize such action relations, we propose a novel policy architecture consisting of a graph attention network over the available actions. We show that our model makes informed action decisions by correctly attending to other related actions in both value-based and policy-based RL. Consequently, it outperforms non-relational architectures on applications where the action space often varies, such as recommender systems and physical reasoning with tools and skills. Results and code at https://sites.google.com/view/varyingaction .
BibTeX
@inproceedings{jain2022know,
  author = {Ayush Jain and Norio Kosaka and Kyung-Min Kim and Joseph J. Lim},
  title = {{Know Your Action Set: Learning Action Relations for Reinforcement Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=_a4BOayCY4},
}
Figure