In traditional reinforcement learning (RL), an agent interacts with its environment by selecting from a fixed, discrete set of actions. In an Atari game, this might be a dozen button combinations; in chess, a few legal moves.
But when an environment is mediated entirely through natural language—such as in interactive fiction or text-adventure games—the action space becomes unbounded. Instead of pressing a button, the agent must generate a text command like "open the wooden chest with the rusty key".
If an agent's vocabulary contains just 1,000 words, generating a short 4-word command yields a search space of $1,000^4 = 1$ trillion possible actions at every single step. As highlighted by Hausknecht et al., the overwhelming majority of these combinations are syntactically or semantically meaningless gibberish. The environment's parser will simply reject them, resulting in extremely sparse feedback. This is the combinatorial action space explosion, and it renders standard random exploration strategies completely intractable.
To make learning possible, researchers have developed architectures that prune, structure, and decompose this infinite space into a manageable set of choices.
Action Elimination: Learning What Not to Do
The most direct way to handle an astronomical action space is to filter out invalid moves before the agent's core policy network even evaluates them.
[ Raw Text State ] ───> [ Action Elimination Network ] ───> [ Valid Action Mask ]
│
[ Raw Text State ] ───> [ Core Policy Network (DQN) ] ─────────────┴─> [ Optimized Action Selection ]
To implement this intuition, Haroush et al. introduced the Action Elimination Deep Q-Network (AE-DQN). This architecture utilizes a dedicated auxiliary network trained to predict whether an action is valid or invalid given the current text state. By masking out the invalid actions, the RL agent can focus its exploration entirely on contextually viable moves.
A similar pruning strategy applies to open-ended text generation. Instead of filtering full sentences, Martin et al. proposed an approach called TrufLL, which uses a task-agnostic language model to dynamically prune the vocabulary token-by-token during training. This prevents the agent from generating incoherent sequences during its initial exploration phase, allowing it to learn language generation tasks from scratch without task-specific demonstrations.
Grounding Actions with Knowledge Graphs
Pure text descriptions are inherently unstructured, making it difficult for an agent to deduce which actions are physically possible. To bridge this gap, researchers introduce structural priors that map text into explicit world models.
Ammanabrolu et al. (2019) introduced KG-DQN, an architecture that dynamically constructs a Knowledge Graph (KG) of the game world from raw text descriptions. The graph tracks the agent's location, inventory, and discovered objects as nodes and edges (e.g., [Player] -> carries -> [Key]). By framing action selection as a question-answering task over this graph, the agent naturally prunes contextually irrelevant commands.
Building on this concept, Prithviraj Ammanabrolu and Matthew J. Hausknecht developed KG-A2C. This model uses the knowledge graph to generate a strict action mask. If the graph indicates that a room is dark and the agent does not possess a flashlight, any action involving "examine painting" is masked out entirely.
Transforming an unconstrained text generation problem into a constrained graph-traversal problem reduces the branching factor from billions of arbitrary word strings to a handful of structurally grounded choices.
Leveraging Linguistic Priors and LLMs
Humans playing a text game do not randomly combine words; we use common sense. We know instinctively that we can "eat the apple" or "open the door", but we cannot "eat the door".
To inject this baseline world knowledge into RL agents, Singh et al. demonstrated the efficacy of embedding pre-trained language models (like DistilBERT) directly into the agent's architecture. The language model acts as a semantic prior, scoring potential word combinations based on how closely they align with human language patterns and steering exploration toward logical actions.
With the advent of Large Language Models (LLMs), this paradigm has evolved into a clean decoupling of action generation and strategic selection.
[ Text State ] ───> [ Large Language Model ] ───> [ Small Set of Plausible Candidates ]
│
[ Reinforcement Learning Policy ]
│
▼
[ Strategically Optimal Move ]
As shown by Xu et al., an LLM can be leveraged as a candidate generator to propose a small, high-quality set of plausible actions from an infinite space. A specialized RL policy then evaluates these candidates to select the move that maximizes long-term strategic rewards. This architecture exploits the LLM's capacity to handle natural language syntax while preserving the RL policy's ability to optimize for complex, multi-step goals.
Action Decomposition and Skill Abstraction
Another powerful lever for taming combinatorial spaces is altering the granularity of the actions themselves. Rather than treating an entire sentence or sequence as a single monolithic choice, models can break the problem down hierarchically.
The authors of POAD (Wen et al.) introduced Policy Optimization with Action Decomposition. Instead of evaluating a full sentence action as a single choice, POAD optimizes the policy at the individual token level while mathematically preserving the sentence-level objective. This allows the agent to receive precise, word-by-word credit assignment, drastically accelerating learning in unconstrained environments.
Alternatively, the action space can be compressed by grouping low-level commands into high-level behaviors. Zhu et al. proposed a skill-centric framework that uses the Information Bottleneck principle to autonomously abstract sequences of individual text commands into reusable "skills" or macro-actions.
By learning to navigate a compressed space of high-level skills rather than individual words, the agent effectively flattens the infinite branching factor of natural language into a highly efficient decision tree.