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.
| Concept | Definition | Who sees it |
|---|---|---|
| Environment state | Complete internal situation of the world | Simulator or designer |
| Observation | Signal the agent actually receives | Agent |
| Belief state | Probability distribution over hidden states | Agent with a model |
| Feature vector | Engineered or learned encoding of the state | Function approximator |
| History | Sequence of past observations and actions | Recurrent or memory-based agent |
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.
| Type | Example environment | Approximate size | Usual approach |
|---|---|---|---|
| Small discrete | Grid world, simple board puzzle | Tens to thousands | Tabular Q-learning, value iteration |
| Large discrete | Chess, Go | About 10^44 to 10^170 | Search plus neural networks |
| Continuous low-dimensional | Cart-pole, pendulum | 4 to 10 variables | Linear or small neural approximators |
| Continuous high-dimensional | Robot locomotion | Dozens to hundreds of variables | Deep actor-critic methods |
| Pixel-based | Atari games | 84 x 84 x 4 input frames | Convolutional deep Q-networks |
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.
| Element | What it describes | Relationship to the state space |
|---|---|---|
| Action space | Choices available to the agent | Actions may depend on the current state |
| Transition function | Probability of the next state | Defined over state and action pairs |
| Reward function | Immediate feedback signal | Usually a function of state and action |
| Policy | Mapping from state to action | Its input domain is the state space |
| Value function | Expected cumulative reward | Assigns a number to each state |
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.
| Situation | Recommended choice | Reason |
|---|---|---|
| Velocity matters but only positions are observed | Stack recent frames | Restores the Markov property |
| Variables differ greatly in scale | Normalize each feature | Stabilizes gradient-based learning |
| Agent sees only part of the world | Add a recurrent memory | Summarizes the relevant history |
| Continuous space with few variables | Tile coding or radial basis | Enables linear value approximation |
| Raw sensor data with structure | Learn an encoder | Extracts compact latent features |
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.