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

