A retailer deciding how much inventory to order must balance immediate costs against future sales and stockouts. Generalized policy iteration (GPI) addresses decisions like this by repeatedly assessing a policy—the action chosen in each state—and improving it using the resulting value estimates. section 4.3
The loop has two interacting steps:
- Policy evaluation estimates the long-term value of states or state-action pairs under the current policy. section 4.3
- Policy improvement compares available actions using those estimates and selects better actions. The revised policy is then evaluated again. section 4.3 section 4.4
Evaluation and improvement need not wait for one another to finish completely. One implementation performs a single sweep of value updates before improving the policy again, while tracking both changes in values and changes in actions. A stable policy is a useful stopping signal, but with partial evaluation, stability alone does not necessarily establish optimality. section 4.4 section 4.6
Inventory ordering
Suppose weekly profit is sales revenue minus ordering, holding, and stockout costs. Starting with a policy that orders one unit in every inventory state, an evaluation sweep estimates each state's value. An improvement sweep then compares ordering zero, one, or two units: it chooses two at zero inventory, one at inventory of one, and zero at inventory of two or three-plus. A second improvement sweep leaves those choices unchanged in the worked example. section 4.3
Table 4.4 First iteration of policy improvement (with round up values)
|
State
|
Order 0
|
Order 1
|
Order 2
|
Best Action
|
New Policy π
1
|
|
0
|
$0-$0-$30 + 0.9×(-$50) = -$75
|
$0-$20-$30 + 0.9×$75 = $18
|
$0-$40-$0 + 0.9×$70 = $23
|
Order 2
|
π
1(0) = 2
|
|
1
|
$100-$0-$0 + 0.9×(-$50) = $55
|
$100-$20-$5 + 0.9×$75 = $143
|
$100-$40-$5 + 0.9×$70 = $118
|
Order 1
|
π
1(1) = 1
|
|
2
|
$100-$0-$5 + 0.9×$75 = $163
|
$100-$20-$10 + 0.9×$70 = $133
|
$100-$40-$10 + 0.9×$65 = $109
|
Order 0
|
π
1(2) = 0
|
|
+3
|
$100-$0-$10 + 0.9×$70 = $153
|
$100-$20-$15 + 0.9×$65 = $124
|
$100-$40-$15 + 0.9×$65 = $104
|
Order 0
|
π
1(+3) = 0
|
Compare the candidate order quantities and resulting policy in the first improvement sweep. section 4.3
Resource allocation
A resource allocation solver starts with zero values and a do-nothing policy. States track remaining budget and project outcomes; valid actions allocate budget to an eligible project or do nothing. Each improvement step uses a one-step lookahead to choose the action with the highest expected value. section 4.4
In the dynamic programming setting, evaluation relies on a known model of transition probabilities and rewards. Large state spaces can make the approach expensive in computation and memory, while an accurate model may not be available. section 4.6
