Bellman value iteration for stock control

Last updated: 5 Oct 20265 min read

tutorial

Value iteration repeatedly updates each state with the best expected immediate reward plus discounted next-state value when a transition model is known.

Define the finite process first

A low-stock bin may replenish at a labor cost or wait and risk shortage. A ready bin may dispatch for service value or hold and incur storage cost. The code uses deterministic transitions to make every calculation visible; a real transition model can distribute probability across several next states. The state contract defines actions, reward units and terminal behavior before any Bellman update.

Apply synchronous updates

At each sweep, compute every new value from the previous sweep, not partially updated values. For each action, add immediate reward to gamma times the previous next-state value, then choose the best eligible action. The terminal value stays zero. With gamma below one and bounded rewards, this finite discounted update converges under the stated model; the stopping tolerance controls numerical approximation, not model truth.

Extract policy after convergence

A state value estimates the best discounted return from that state. The policy selects the action achieving the best one-step reward plus continued value. The code finds replenishment and dispatch preferable in its invented process. Those actions are consequences of its stated rewards and transitions, not general advice for a warehouse. Q-learning addresses the case where transitions are sampled rather than supplied.

Challenge the model, not just the solver

A perfect value-iteration implementation can optimize a wrong simulator. Check transition frequencies on held-out operational data, especially low-frequency shortages and changes caused by the candidate action. If capacity or lead time is omitted from state, planning may assume replenishment is instant. Simulator risk limits offline claims.

Report cost and horizon

The discount factor describes how later rewards enter this mathematical objective; it should not hide long-term harms merely to make computation easy. Report gamma, reward scale, termination rule, convergence tolerance and sensitivity to alternative transition estimates. The release review requires those artifacts.

Implementation

discount = 0.80
model = {
    "low-stock": {
        "replenish": [(-2.0, "ready-stock", 1.0)],
        "wait": [(-7.0, "closed", 1.0)],
    },
    "ready-stock": {
        "dispatch": [(5.0, "low-stock", 1.0)],
        "hold": [(-1.0, "ready-stock", 1.0)],
    },
    "closed": {},
}

def action_value(outcomes, state_values, gamma):
    if abs(sum(probability for _, _, probability in outcomes) - 1) > 1e-9:
        raise ValueError("transition probabilities do not sum to one")
    return sum(probability * (reward + gamma * state_values[next_state])
               for reward, next_state, probability in outcomes)

values = {state: 0.0 for state in model}
for sweep in range(180):
    updated = {state: (max(action_value(outcomes, values, discount)
                           for outcomes in actions.values()) if actions else 0.0)
               for state, actions in model.items()}
    change = max(abs(updated[state] - values[state]) for state in model)
    values = updated
    if change < 1e-9:
        break
policy = {state: max(actions, key=lambda action:
                     action_value(actions[action], values, discount))
          for state, actions in model.items() if actions}
assert policy == {"low-stock": "replenish", "ready-stock": "dispatch"}
assert abs(values["low-stock"] - 5.5555555556) < 1e-5

Performance and operating cost

For S states, at most A actions per state, O possible next-state outcomes per action and K sweeps, direct value iteration costs O(KSAO) time and O(S) working values, excluding model storage. Large or continuous state spaces need approximation and additional validation. Exact convergence of a small model does not establish operational accuracy.

Common Mistakes

Do not use newly updated state values in some states and old values in others while claiming a synchronous sweep.
Do not bootstrap value from a true terminal state.
Do not treat an optimal policy for an estimated model as proven optimal in operations.