liveBook · Manning

Generalized policy iteration

As explained in Applied Reinforcement Learning

Generalized policy iteration is a reinforcement-learning framework that alternates policy evaluation with policy improvement until the policy stabilizes or reaches an optimum.

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

How Applied Reinforcement Learning covers it

How deep it goes
Works through evaluation and greedy improvement, including a single-sweep implementation and practical model and state-space limitations.
Examples
Works through inventory ordering calculations and a budget-constrained project resource allocation solver.
What it assumes
Builds on an understanding of Bellman equations and policy evaluation before developing the improvement loop.
What you can do after
Build a resource allocation solver from scratch using evaluation sweeps and greedy policy improvement.
How it connects
Connects policy evaluation and policy improvement with Bellman equations, value functions, dynamic programming, and 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.