liveBook · Manning

State space

As explained in Applied Reinforcement Learning

A state space is the set of possible states of an environment in a decision process.

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

How Applied Reinforcement Learning covers it

How deep it goes
Develops Markov state representations and implements reset and state enumeration, then examines the computational cost of larger spaces.
Examples
Illustrates states through delivery routing, warehouse order picking, and budget allocation across projects.
What you can do after
Build state representations from scratch for custom environments and enumerate combinations for a resource-allocation problem.
How it connects
Connects state space to the Markov property, action space, transition dynamics, reward functions, and dynamic programming.

Also explained in

Compare how 4 books explain state space →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.