liveBook · Manning

Policy evaluation

As explained in Applied Reinforcement Learning

Policy evaluation is the process of estimating the value of states or state-action pairs under a fixed policy.

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

How Applied Reinforcement Learning covers it

How deep it goes
Works through iterative Bellman expectation updates, convergence, and policy improvement, with a Python implementation.
Examples
Uses inventory ordering calculations and a project resource allocation problem to illustrate evaluation.
What you can do after
Build it from scratch in Python for a resource allocation model using iterative value updates.
How it connects
Connects policy evaluation to value functions, Bellman equations, policy improvement, and generalized policy 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.