State space · reinforcement learning

On this page 7

In reinforcement learning, the state space is the set of all possible states an environment can be in, where each state is a description of the situation that the agent uses to choose its next action. Formally, it is the set S in the tuple that defines a Markov decision process, alongside the action space, transition dynamics, reward function and discount factor.

The design and size of the state space decide which algorithms are feasible, how much data training needs and whether the learned policy can generalize. Within artificial intelligence, many practical failures of reinforcement learning agents trace back not to the learning algorithm but to a poorly chosen state representation.

What a state must contain in reinforcement learning

A good state contains all information relevant to predicting the future, so that the next state and reward depend only on the current state and action. This requirement is the Markov property, and it allows value functions and the Bellman equation to be defined over states rather than over entire histories.

The distinction between the environment state and the agent observation matters. In a fully observable task, the observation equals the state. In a partially observable task, such as a robot with a limited camera view, the agent sees only part of the state and must build a belief state or use memory, which turns the problem into a partially observable Markov decision process.

The table below separates the related notions that are often blurred together in practice.

ConceptDefinitionWho sees it
Environment stateComplete internal situation of the worldSimulator or designer
ObservationSignal the agent actually receivesAgent
Belief stateProbability distribution over hidden statesAgent with a model
Feature vectorEngineered or learned encoding of the stateFunction approximator
HistorySequence of past observations and actionsRecurrent or memory-based agent
State, observation and related concepts

Discrete and continuous state spaces

State spaces are classified mainly by whether they are discrete or continuous, and by how large they are. A grid world with 100 cells has a small discrete state space, while a humanoid robot described by joint angles and velocities has a continuous, high-dimensional one with infinitely many states.

TypeExample environmentApproximate sizeUsual approach
Small discreteGrid world, simple board puzzleTens to thousandsTabular Q-learning, value iteration
Large discreteChess, GoAbout 10^44 to 10^170Search plus neural networks
Continuous low-dimensionalCart-pole, pendulum4 to 10 variablesLinear or small neural approximators
Continuous high-dimensionalRobot locomotionDozens to hundreds of variablesDeep actor-critic methods
Pixel-basedAtari games84 x 84 x 4 input framesConvolutional deep Q-networks
Types of state spaces with typical examples

In small discrete spaces, an agent can store a value for every individual state in a lookup table. Once states number in the millions or are continuous, this becomes impossible, and the agent must use function approximation to generalize from visited states to similar unvisited ones.

Why state space size drives difficulty

The number of states grows exponentially with the number of state variables, a consequence of the curse of dimensionality. Ten binary variables yield 1,024 states, while 50 binary variables yield more than 10^15 states, far more than any agent can visit even once.

Larger state spaces raise three costs at once. Exploration becomes harder because rewarding states are rarer, sample complexity increases because more experience is needed per decision, and credit assignment suffers because long chains of states separate actions from their consequences.

The table below shows how the state space interacts with neighboring elements of the problem definition.

ElementWhat it describesRelationship to the state space
Action spaceChoices available to the agentActions may depend on the current state
Transition functionProbability of the next stateDefined over state and action pairs
Reward functionImmediate feedback signalUsually a function of state and action
PolicyMapping from state to actionIts input domain is the state space
Value functionExpected cumulative rewardAssigns a number to each state
State space compared with related elements of a Markov decision process

Designing a practical state representation

Designing the state is an engineering decision that balances completeness against compactness. Including too little information breaks the Markov property, while including irrelevant variables inflates the space and slows learning.

SituationRecommended choiceReason
Velocity matters but only positions are observedStack recent framesRestores the Markov property
Variables differ greatly in scaleNormalize each featureStabilizes gradient-based learning
Agent sees only part of the worldAdd a recurrent memorySummarizes the relevant history
Continuous space with few variablesTile coding or radial basisEnables linear value approximation
Raw sensor data with structureLearn an encoderExtracts compact latent features
Design decisions for state representations

Modern deep reinforcement learning often lets a neural network learn the representation from raw input. Auxiliary objectives, such as predicting the next observation, can help the encoder capture features that matter for control rather than for visual detail alone.

Common mistakes with state spaces

Most state space errors are invisible during training and appear as unstable or brittle policies at evaluation time. Experienced practitioners check the representation before tuning any algorithm hyperparameters.

  • Leaking privileged information: giving the agent simulator-only variables produces policies that fail on real hardware.
  • Omitting time or velocity: a single snapshot can make two different situations look identical to the agent.
  • Unbounded features: raw counters or timestamps grow without limit and destabilize value estimates.
  • Confusing state with observation: assuming full observability hides the need for memory.
  • Ignoring terminal states: failing to mark episode ends corrupts bootstrapped value targets.

The idea in brief

The state space is the list of every situation a learning agent could find itself in. Think of a board game: each possible arrangement of pieces is one state, and the state space is every arrangement that could ever occur.

The agent looks at its current state to decide what to do next. If the description of the state leaves out something important, such as which direction a ball is moving, the agent cannot make good choices. If the description includes too many details, learning becomes slow. A well-chosen state space makes learning faster and decisions more reliable.

A practical scenario

An engineering team trains an agent to control the heating and cooling of a 12-floor office building to reduce energy use while keeping rooms comfortable. Their first state contains only the current indoor temperature for each floor, which gives 12 variables. The resulting policy oscillates, overheating rooms in the morning and reacting too late to sunshine.

The team redesigns the state space. They add outdoor temperature, solar radiation, time of day encoded as sine and cosine values, occupancy estimates and the temperatures from the previous 30 minutes. The state grows to 64 normalized variables, and the team trains a soft actor-critic agent in a calibrated building simulator.

After deployment, the agent anticipates warm afternoons and pre-cools floors during cheaper off-peak hours. Over one summer, the building records about 15 percent lower HVAC energy use with no increase in comfort complaints, an improvement the team credits mainly to the richer state representation.