liveBook · Manning

Value iteration

As explained in Applied Reinforcement Learning

Value iteration is a dynamic-programming algorithm that repeatedly applies a Bellman optimality update to approximate optimal state values and derive an optimal policy.

A manager allocating a limited budget must weigh immediate returns against what each decision leaves available for later. Value iteration tackles this trade-off when the possible outcomes, their probabilities, and rewards are known. It repeatedly updates estimates of long-term state values and uses them to choose better actions. section 4.4 section 4.1

The central idea is to compare actions by their expected immediate reward plus the discounted value of their possible successor states. A Bellman optimality update assigns a state the value of its best available action. Repeating these updates lets information about future outcomes flow backward through the states. section 4.6 section 4.3

An evaluate-and-improve implementation works as follows:

  • Initialize state values, for example to zero, and choose an initial policy. section 4.4
  • Sweep through the states once, updating each value using the current policy and the model’s rewards and transitions. section 4.4
  • Improve the policy by choosing the action with the highest expected immediate reward plus discounted successor value at each state. section 4.3
  • Repeat the sweep and improvement, tracking value changes and policy changes. Continuing to check value convergence matters: a policy can appear stable before its value estimates have settled. section 4.4 section 4.6

Allocating a project budget

A resource-allocation model tracks remaining budget and project outcomes as its state. An action either allocates money to a project or does nothing. Success probabilities and rewards describe the possible consequences; valid actions must fit the remaining budget and project status. The resulting strategy is conservative with low budgets, balanced with medium budgets, and opportunistic with high budgets. section 4.4 section 4.6

Listing 4.8 Generalized Policy iteration Function
def generalized_policy_iteration(mdp: ResourceAllocationMDP, 
                               max_iterations: int = 100) -> tuple[dict, dict, list]:
        
    states = create_state_space(mdp)
    actions = create_action_space(mdp)
    print(f"State space size: {len(states)}")
    
    value_function = {state: 0.0 for state in states} #A
    policy = {state: (-1, 0) for state in states}  #A
    
    convergence_history = []
    
    for iteration in range(max_iterations):
        print(f"\nIteration {iteration + 1}:")
        print("-" * 30)
        
 
        old_value_function = value_function.copy()
        delta = 0.0
        
        for state in states: #B
         
            action = policy.get(state, (-1, 0)) #B
            
            expected_value = 0.0 #C
            for next_state in states:
                trans_prob = transition_probability(mdp, state, action, next_state) #C
                if trans_prob > 0:
                    reward = reward_function(mdp, state, action, next_state)
                    expected_value += trans_prob * (reward + mdp.discount_factor * old_value_function[next_state]) #D
            
            value_function[state] = expected_value
            delta = max(delta, abs(old_value_function[state] - value_function[state])) #E
            
        print(f"Policy evaluation sweep complete. Max value change: {delta:.6f}")
 
        policy_stable = True #F
        old_policy = policy.copy() #F
 
        for state in states:
            budget, proj_outcomes = state
            
            valid_actions = [] #G
            for action in actions: #G
                project_id, allocation = action #G
                if project_id == -1:  
                    valid_actions.append(action) #G
                elif (allocation <= budget and  #G
                      project_id < mdp.n_projects and  
                      proj_outcomes[project_id] == 0): #G
                    valid_actions.append(action)
            
            best_action = None
            best_value = float('-inf')
            
            for action in valid_actions: #H
         
                action_value = 0.0
                for next_state in states:
                    trans_prob = transition_probability(mdp, state, action, next_state)
                    if trans_prob > 0:
                        reward = reward_function(mdp, state, action, next_state)
                        action_value += trans_prob * (reward + mdp.discount_factor * value_function[next_state]) #I
                
                if action_value > best_value:
                    best_value = action_value
                    best_action = action
            
            policy[state] = best_action if best_action else (-1, 0)
            
            if old_policy.get(state) != policy[state]: #J
                policy_stable = False
        
        policy_changed = sum(1 for s in states if old_policy.get(s) != policy.get(s))
        print(f"Policy improvement sweep complete. Policy changes: {policy_changed}")
 
        convergence_history.append({ #K
            'iteration': iteration + 1,
            'policy_changes': policy_changed,
            'max_value_change': delta
        })
        
       
        if policy_stable: #L
            print(f"\nPolicy converged after {iteration + 1} iterations!")
            break
            
    return policy, value_function, convergence_history

The implementation starts with zero values and a passive policy, then alternates value sweeps with policy improvement. section 4.4

Value iteration is most useful when a reliable model is available and the state space is manageable. A large state space can make computation and storage impractical, while inaccurate or unavailable transition probabilities and rewards undermine the model-based approach. section 4.6

How Applied Reinforcement Learning covers it

How deep it goes
Explains single-sweep evaluation and greedy improvement, then implements the loop and tracks convergence.
Examples
Works through project-budget allocation in code and a simplified weekly inventory-ordering problem.
What you can do after
Builds it from scratch for a modeled resource-allocation problem and interprets the resulting policy.
How it connects
Connects value iteration to Bellman equations, dynamic programming, generalized policy iteration, policy evaluation, and policy improvement.

Also explained in

Compare how 2 books explain value iteration →

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.