A state space is the set of possible states of an environment. In a delivery problem, a state might describe the driver’s location, remaining deliveries, time left in the shift, and traffic. Together, these details give an agent a picture of the situation in which it must choose its next action. section 3.1
A useful state includes the information needed for future decisions. It should satisfy the Markov property: the current state contains the relevant information without requiring the agent to reconstruct how it arrived there. The state space works alongside the action space, reward function, and transition logic, which respectively describe choices, goals, and how the environment changes. section 3.1 section 4.4
Warehouse order picking
A warehouse robot’s state records its position, which items it has picked, and whether it has collected everything and should return to the depot. Resetting the environment puts the robot at the depot, marks all items uncollected, and starts a new episode. section 3.2
Listing 3.3 State Representation and Reset Logic
def _get_state(self): #A
return { #A
"robot_pos": tuple(self.robot_pos), #A
"items_picked": tuple(self.items_picked_status), #A
"all_items_collected_phase": self.all_items_collected_phase
} #A
def reset(self): #B
self.robot_pos = np.array(self.depot_pos) #C
self.items_picked_status = [False] * self.num_items #D
self.all_items_collected_phase = False #E
self.current_step = 0 #F
return self._get_state() #G
See how the warehouse state is returned and reset in Python. section 3.2
Allocating a budget
For resource allocation, a state pairs the remaining budget with a status for each project: 0 for unattempted, 1 for successful, and −1 for failed. For example, (6, (1, 0, −1, 0)) means six budget units remain, the first project succeeded, and the third failed. These values capture the information needed for the next allocation decision. section 4.4
Listing 4.2 Defining State Space
def create_state_space(mdp: ResourceAllocationMDP) -> list[tuple]:
states = []
# Generate all possible combinations of remaining budget and project outcomes
for budget in range(mdp.max_budget + 1): #A
for proj_state in range(3**mdp.n_projects): #B
proj_outcomes = []
temp = proj_state
for _ in range(mdp.n_projects):
proj_outcomes.append(temp % 3 - 1) #C
temp //= 3
states.append((budget, tuple(proj_outcomes)))
return states
Explore how the budget and project-status combinations are enumerated. section 4.4
State-space size matters when choosing a solution method. With a maximum budget of 12 and four projects, the allocation representation has 13 × 3⁴ = 1,053 combinations. Raising the maximum budget to 100 and the project count to ten produces nearly six million. Dynamic programming iterates over states, so this growth can make storing values and calculating a policy impractical. section 4.5



