Action Space

An action space is classified as discrete when it contains a finite or countably infinite set of distinct actions, such as {move_north, move_east, pick_up, drop}. It is continuous when actions are defined by real-valued vectors within a bounded region, such as [torque ∈ (-1, 1), steering_angle ∈ (-30°, 30°)]. Discrete spaces are typical in symbolic planning (e.g., STRIPS), while continuous spaces are common in control and robotics, requiring different algorithmic approaches like gradient-based optimization.

The dimensionality of an action space refers to the number of independent parameters required to specify an action. A single discrete choice is one-dimensional, while a continuous robotic arm command with 7 joint angles is 7-dimensional. High-dimensional action spaces suffer from the curse of dimensionality, where the volume of the space grows exponentially, making exhaustive search or uniform sampling computationally intractable. This necessitates the use of function approximation (e.g., neural network policies) and sophisticated exploration strategies.

In a deterministic action space, executing an action in a given state always leads to a single, predictable successor state (e.g., a chess move). In a stochastic action space, an action leads to one of several possible successor states according to a probability distribution, modeling uncertainty in the environment (e.g., a robot gripper might slip). This distinction is critical: deterministic planning can use classical search algorithms, while stochastic planning requires frameworks like Markov Decision Processes (MDPs) or Partially Observable MDPs (POMDPs) to reason about expected outcomes.

In symbolic planning formalisms like STRIPS and PDDL, each action has associated preconditions—logical propositions that must be true in the current state for the action to be legally applicable. For example, the action Unlock(Door) may have the precondition Has(Key). The effective, or relevant, action space at any given state is therefore a subset of the full action space, filtered by these preconditions. Efficient planners exploit this structure to prune the search tree.

A hierarchical action space allows high-level, abstract actions to be decomposed into sequences of lower-level primitive actions. This is the core of Hierarchical Task Network (HTN) planning. For instance, the abstract action NavigateTo(Office) can be decomposed into primitives like Open(Door), Move(Hallway), Turn. This abstraction dramatically reduces the branching factor for search, enabling the solution of complex, long-horizon problems that would be infeasible with a flat primitive action space.

Actions are often defined schematically with variables, known as operator schemas. For example, a Move(x, y) schema has parameters for the start and end locations. Grounding is the process of instantiating these schemas with all valid combinations of concrete objects from the problem domain to produce the set of ground actions. A domain with 10 locations yields 90 possible Move actions (10*9). The size of the grounded action space is a key driver of planning complexity, and lifted planning algorithms work directly with the schemas to avoid explicit grounding.

The state space is the set of all possible configurations or situations the world can be in. It is defined by the values of all relevant state variables. The action space provides the operators that create transitions between states.

• Relationship to Action Space: The action space defines the legal transitions between states. Each action maps a subset of the state space (where its preconditions hold) to a new subset (its effects).
• Example: In a navigation problem, the state space is all possible (x, y) coordinates. The action space {North, South, East, West} defines how the agent moves between those coordinates.

A Markov Decision Process is a mathematical framework for modeling sequential decision-making under uncertainty. It formally defines the tuple (S, A, P, R, γ), where:

• S is the state space.
• A is the action space (the set of all available actions).
• P defines transition probabilities: P(s' | s, a).
• R is a reward function: R(s, a, s').
• γ is a discount factor.

The MDP framework explicitly models the action space A as a core component for which an optimal policy π(a|s) must be derived.

A precondition is a logical condition that must be true in the current state for an action to be legally applicable. It acts as a filter on the action space, determining which actions are valid from any given state.

• Role in Planning: In formalisms like STRIPS, each action in the action space is defined with a precondition list. The planner can only apply an action if its preconditions are a subset of the current state's propositions.
• Example: For an action PickUp(block), a precondition might be clear(block) and handEmpty. If these aren't true, PickUp is not part of the currently applicable action space.

An effect specifies the changes an action makes to the state when executed. It defines the outcome of applying an action from the action space. Effects are typically divided into add lists (propositions made true) and delete lists (propositions made false).

• Deterministic vs. Probabilistic: In classical planning, effects are deterministic. In MDPs or contingent planning, actions can have probabilistic effects, leading to different successor states.
• Example: The action Move(A, B) might have the effect Add: at(A, B), Delete: at(A, previous_location).

A policy is a mapping from states to actions. It is a strategy that defines which action from the action space the agent should execute in any given state (or belief state in POMDPs).

• In Reinforcement Learning: The goal is to learn an optimal policy π* that maximizes expected cumulative reward. The policy operates over the entire defined action space.
• Types: Policies can be deterministic (π(s) = a) or stochastic (π(a|s) = probability). In planning, a plan is a sequential, deterministic policy from the initial state.

A hierarchical action space structures primitive actions into higher-level macro-actions or skills. This abstraction reduces the branching factor for planners and enables reasoning over longer time horizons.

• Used in Hierarchical Task Networks (HTN): HTN planning decomposes high-level tasks (like BuildHouse) into networks of subtasks, ultimately refining them into primitive actions from the base action space.
• Benefits: Dramatically improves search efficiency. An agent can choose a high-level action NavigateToCity instead of millions of individual Move steps.