Must the space be a list?

No. Rules and variable domains can define it implicitly, and continuous spaces cannot be enumerated as finite lists.

Are all possible states reachable?

Not necessarily. Reachability depends on the initial state and transition rules.

Does a complete state make the future certain?

No. A stochastic model can specify a distribution over future states even when the current state is known.

AI Glossary / Time series and signal processing / Advanced

State space

Definition

A state space is the set of possible states used to represent a system. Each state records information relevant to describing the system now and predicting its evolution under the chosen model. The space may be finite, countably infinite or continuous. Defining it is a modeling decision: the representation must retain information needed for the task while avoiding unnecessary detail.

What it means

A state is one possible configuration; the state space contains all configurations the model allows. For an inventory system, a state might include stock on hand and stock already ordered. For a moving object, it might include position and velocity. Two situations that look identical through one measurement can still be different states if they can evolve differently under the same action.

How it works

Choose state variables and their allowed values, then apply constraints to exclude invalid combinations. Specify how actions or system dynamics move between states. A transition may be deterministic or probabilistic. An initial state and transition rules determine which allowed states are reachable in a particular problem.
In search, states can be represented as graph nodes and actions as directed edges. A search tree can contain several nodes corresponding to the same state because different action sequences reach it. In a partially observed system, the true state need not be directly known; a distribution over possible states can represent the agent's uncertainty.

Three practical examples

A warehouse planner represents both available stock and outstanding deliveries. Ignoring outstanding deliveries could make two situations appear identical even though their replenishment options differ.
A navigation model tracks location and remaining battery. The same location with a full battery and an empty battery may permit different actions, so location alone may be an inadequate state.
A time-series model represents an underlying level and trend as a state vector while observed sales provide noisy measurements. The state space describes allowable vector values; the observation series is not itself the full set of possible states.

Think of it this way

A state space is like a catalog of all valid positions in a board game, together with a separate rulebook explaining legal moves. One position is a state, a sequence of moves is a path, and the catalog is the space.

Worked example

Construct a toy inventory system whose state is (h, o), where h is units on hand and o is units outstanding. Let h range from zero to three and o from zero to two. The unconstrained product contains 4 times 3 = 12 pairs. Impose a commitment limit h + o ≤ 3.
When o = 0, four h values are allowed. When o = 1, only h = 0, 1 or 2 is allowed. When o = 2, only h = 0 or 1 is allowed. The constrained state space therefore contains 4 + 3 + 2 = nine states. Counting the full product would include three invalid combinations: (2,2), (3,1) and (3,2).
Define three deterministic actions. Order increases o by one if o < 2 and h + o < 3. Receive changes (h,o) to (h+1,o-1) when o > 0. Sell reduces h by one when h > 0. These rules preserve the constraints. Starting from (0,0), all nine states are reachable: to reach any allowed pair, first order and receive h units one at a time, then place o outstanding orders.
Suppose the goal is (3,0). One valid plan is order, receive, order, receive, order, receive. It uses six actions. Any plan must receive at least three units, each requiring an order, so no plan can use fewer than six actions under these rules. Selling cannot shorten that requirement.
Now suppose a display reports only h = 1. Three states remain possible: (1,0), (1,1) and (1,2). Receiving is impossible in the first but possible in the other two. An order is allowed in the first two but not the third. The same visible stock count therefore does not identify the complete state needed for this decision model.

Illustrative case study

Fictional Cedar Supplies uses the nine-state construction to review an automated replenishment prototype. Its first design stores only stock on hand. During a simulated test, it tries to place another order despite two outstanding units already filling the remaining commitment allowance.
The team adds outstanding orders to the state and checks every allowed transition against the capacity rule. It keeps the toy model separate from production requirements: actual deliveries can be delayed, partial or canceled, and those features may require additional variables or stochastic transitions. The nine-state count does not describe a real warehouse's complete complexity.

Common misconceptions and mistakes

A state space is not the same as the states already observed in a dataset. Nor does a Cartesian-product count automatically respect feasibility constraints. A state's probability and its membership in the space are different questions. Do not confuse a state with an action, a model parameter or an entire history. Omitting relevant history is safe only when the retained representation adequately supports the transition assumptions being made.

Business use

Define state variables jointly with the people who understand operational rules. Check whether situations sharing the same representation really permit the same decisions and predicted outcomes. Estimate how the number of configurations grows before committing to exhaustive search. For uncertain systems, specify what the decision maker observes and how uncertainty is represented. A compact state model can simplify planning, but excessive simplification can make a fast policy systematically wrong.

Check your understanding

Why are (1,0) and (1,2) different states even though both have one unit available?

Answer: Their outstanding commitments differ. The allowed receive and order actions differ under the toy rules, so collapsing them would lose information relevant to planning.

Related terms

State
Action space
Markov property
Belief state
state transition
search graph
state-space model
partial observability

Learn next

Increase the commitment limit and maximum on-hand stock to four while keeping at most two outstanding units. The allowed count becomes 5 + 4 + 3 = 12 states. Reaching (4,0) from (0,0) requires at least eight actions: four orders and four receives.

Sources

Aalto Dictionary of Machine Learning, state and state space: https://aaltodictionaryofml.github.io/ADictML_Main.pdf UC Berkeley CS188, State Spaces and Search Problems: https://inst.eecs.berkeley.edu/~cs188/textbook/search/state.html (primary textbook search text consulted). The inventory rules, state counts, plans and Cedar Supplies scenario are original teaching constructions.

Previous: State observer Next: State space graph