A business may have a rule for replenishing inventory or allocating a budget, but how good is that rule over time? Policy evaluation estimates the value of each state, or state-action pair, assuming the current policy remains fixed. It measures the plan before changing it. section 4.3 section 4.4
A state’s value combines the reward expected now with the discounted value of what may happen next. When several next states are possible, their contributions are weighted by their transition probabilities. The discount factor controls how much future value contributes to the estimate. section 4.4 section 4.6
To evaluate a fixed policy with a known model:
- Start with a value estimate for every state, often zero. section 4.4
- For each state, follow the policy’s prescribed action and average the reward plus discounted next-state value over possible outcomes. section 4.4
- Repeat the updates until value changes are negligible. The resulting estimates describe the current policy, not a newly chosen one. section 4.4
Evaluating an inventory rule
Suppose the current rule orders one unit in every inventory state, the discount factor is 0.9, and all initial values are zero. In the zero-inventory state, the first update is −$50: $0 in sales, a $20 ordering cost, and a $30 stockout penalty. The discounted next-state estimate contributes zero on this first pass. Further updates incorporate future values. section 4.3
Table 4.3 First iteration of policy evaluation calculations.
|
State
|
Action (π
0)
|
Immediate Reward
|
γV
0(next)
|
V
1(s)
|
|
0
|
Order 1
|
Sales: $0 + Order: -$20 + Stockout: -$30 = -$50
|
+0.9×$0
|
-$50
|
|
1
|
Order 1
|
Sales: $100 + Order: -$20 + Holding: -$5 = $75
|
+0.9×$0
|
$75
|
|
2
|
Order 1
|
Sales: $100 + Order: -$20 + Holding: -$10 = $70
|
+0.9×$0
|
$70
|
|
+3
|
Order 1
|
Sales: $100 + Order: -$20 + Holding: -$15 = $65
|
+0.9×$0
|
$65
|
Compare the first value update across inventory states under the same ordering rule. section 4.3
Evaluation and improvement play different roles. Policy improvement uses the estimated values to choose better actions; evaluation then assesses the revised policy. Generalized policy iteration repeats this interaction, and can use partial evaluation rather than waiting for the values to settle completely on every pass. section 4.3 section 4.6
Listing 4.6 Policy Evaluation Function
def policy_evaluation(mdp: ResourceAllocationMDP,
states: list[tuple],
policy: dict[tuple, tuple],
value_function: dict[tuple, float],
theta: float = 1e-6) -> dict[tuple, float]:
actions = create_action_space(mdp)
iteration = 0
while True:
delta = 0.0
new_value_function = value_function.copy()
for state in states:
old_value = value_function[state]
action = policy.get(state, (-1, 0)) #A
expected_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)
expected_value += trans_prob * (reward + mdp.discount_factor * value_function[next_state]) #B
new_value_function[state] = expected_value
delta = max(delta, abs(old_value - expected_value)) #C
value_function = new_value_function #D
iteration += 1
if delta < theta: #E
break
print(f"Policy evaluation converged in {iteration} iterations")
return value_function
Inspect an iterative Python policy-evaluation function for a resource allocation problem. section 4.4
This dynamic programming approach relies on known transition probabilities and rewards. Large state spaces can make evaluation costly in computation and memory, while accurate models may be unavailable in practice. section 4.6
