---
kind: concept
slug: value-iteration
title: Value iteration
summary: >-
  Filling a table of the best expected return for each number of steps left and budget left, working back from the end, then reading a decision rule off the table. Exact cost grows as T times B. Large problems need an approximation: a small network for value differences, or backups only at sampled beliefs for partly observed problems.
tags: [reinforcement-learning, dynamic-programming, planning]
papers: ["1701.02490", "2107.07599", "2610.17391"]
related: [model-based-reinforcement-learning, multi-layer-perceptron, partially-observable-markov-decision-process, monte-carlo-tree-search]
status: draft
updated_at: 2026-10-19
---

## Overview

Value iteration fills a table V(t, b): the best expected return when t steps
are left and b units of a budget remain. It starts from V(0, ·) = 0, fills
t = 1, 2, ..., T, and takes the best action in each cell from the cell one step
earlier [arxiv:1701.02490 §4, alg. 1]. In the one card that uses the table, a
step is one ad auction, the budget is money, the action is an integer bid, and
the return is the predicted click value of a won impression
[arxiv:1701.02490 §3.1, §3.2].

Every variant uses the same kind of backup: a maximum over actions of the
immediate reward plus the value of the successor state. The variants differ in
the discount factor and in what a state is. The table card uses discount 1, so
the value is the total expected clicks over the campaign [arxiv:1701.02490
§3.2]. The POMDP review uses γ in (0, 1) and works on beliefs, which are
probability distributions over hidden states [arxiv:2107.07599 §2]. Its
optimal value is the best action value over beliefs, combining the expected
reward with the discounted value of successor beliefs [arxiv:2107.07599 §2,
eq. 1].

The bid rule in the table card is a threshold on the table: pay a price while
the click value of the request is at least the value lost from the budget
[arxiv:1701.02490 §4].

A textbook card lists Bellman recursion among the solution methods for
reinforcement learning [arxiv:2610.17391 §3]. It gives no value-iteration
algorithm, so this page takes none from it.

## Variants

### Exact table over the full grid

The table covers every t from 1 to T and every budget from 0 to B. Time and
memory are O(TB) [arxiv:1701.02490 §4.1]. The market-price distribution is
estimated by counting, and the average click-through rate comes from historical
data [arxiv:1701.02490 §2, §4]. The author-reported small-scale result is a
click improvement over the Lin baseline between +22.39% and +6.58% on iPinYou,
depending on the budget ratio [arxiv:1701.02490 tab. 2]. Card:
[Real-Time Bidding by Reinforcement Learning in Display Advertising](/papers/1701.02490).

### Network approximation of value differences

A small network with two tanh hidden layers of 30 and 15 units takes (t, b) as
input and predicts the difference D(t, b) = V(t, b+1) − V(t, b)
[arxiv:1701.02490 §4.1, §6.2]. The paper predicts the difference, not V,
because V is much larger than the click rate while the difference is on the
click scale [arxiv:1701.02490 §4.1]. Inside the trained box, the reported
root-mean-square error is about 10^-3 of the average click rate on iPinYou
[arxiv:1701.02490 tab. 4]. The paper states that generalisation is
satisfactory only at small scales [arxiv:1701.02490 §6.2].

### Scaling by reusing a small table

For episodes much longer than the trained horizon T0, the paper proposes three
ways to reuse the small table or network [arxiv:1701.02490 §4.1, §5.3]:

- *Segmentation*: split the episode into segments of length T0 and give each
  segment a share of the remaining budget.
- *State mapping of D*: for t above T0, read D at a rescaled budget, D(T0,
  b/t × T0).
- *State mapping of the action*: for t above T0, read the action from the
  table at the rescaled state.

The paper reports large-scale results (T = 100,000) only as figures, and the
text gives no values for them [arxiv:1701.02490 §6.2]. Card:
[Real-Time Bidding by Reinforcement Learning in Display Advertising](/papers/1701.02490).

### Exact recursion over beliefs, approximated by sampling

When the state is hidden, the value is a function of beliefs. The review states
that exact solution is intractable, PSPACE-hard in general
[arxiv:2107.07599 §3]. Its sampling-based solvers back up values only at a
sampled set of beliefs, and they do not produce optimal policies
[arxiv:2107.07599 §1, §3].

- *PBVI* keeps one alpha-vector per sampled belief and does point-based
  backups only [arxiv:2107.07599 §3.1].
- *HSVI2* keeps lower and upper bounds. Its upper bound starts from the value
  of the fully observable (MDP) version of the problem [arxiv:2107.07599 §3.1].
- *SARSOP* samples beliefs close to those reachable under an optimal policy and
  prunes provably suboptimal branches [arxiv:2107.07599 §3.1].

The review quotes the reported costs from the original papers, and does not
run them itself. On the Tag problem (870 states), PBVI takes about 50 hours
and SARSOP reaches a better policy than HSVI2 in 6 seconds
[arxiv:2107.07599 §3.1]. Card:
[POMDPs and Robotics](/papers/2107.07599).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Small grid, so that T × B table entries fit in memory | Exact table | Exact values for the modelled problem, and the small-scale results are the paper's strongest [arxiv:1701.02490 §6.1, tab. 2] |
| T and B too large for the table | Network on D | Removes the table. The paper does not state the training cost [arxiv:1701.02490 §6.2] |
| Need values outside the trained budget and horizon | Check first | Error is reported only inside the trained box, and generalisation is stated as limited [arxiv:1701.02490 tab. 4, §6.2] |
| Long episode, small table available | Segmentation or state mapping | Reuses a table of size T0 × B0 [arxiv:1701.02490 §4.1]. The paper gives no text values for the large-scale gains |
| Market price depends on request features | Plain table is a poor fit | The table assumes the price distribution ignores features. The paper relaxes this only by splitting the feature space into segments [arxiv:1701.02490 §4] |
| Hidden state, model small enough for exact backups | Exact recursion over beliefs | Gives the optimal value for the model. Exact solution is intractable in general [arxiv:2107.07599 §2, §3] |
| Hidden state, model too large for exact backups | Sampled-belief solver (PBVI, HSVI2, SARSOP) | Keeps the work to sampled beliefs. The policy is approximate [arxiv:2107.07599 §3.1] |
| Decisions needed under a time limit, with a simulator | Sampled tree search (MCTS with UCT, or POMCP over histories) | Examines only part of the tree rather than sweeping every state [arxiv:2610.17391 §5.2]. POMCP is the belief-space form of this [arxiv:2107.07599 §3.1] |

## Implementation sketch

Build the table once per campaign, then bid per request. The core is a
maximum over integer actions for each cell.

```pseudocode
# Build the value table: V[t][b] is the best expected return  [§4] [alg. 1]
# m[d]: estimated probability that the market price equals d  [§2]
# theta: average click-through rate, a constant  [§4]
def build_table(m, theta, T, B, d_max):
    # With no steps left the return is zero  [§4]
    V = zeros((T + 1, B + 1))
    for t in range(1, T + 1):
        for b in range(B + 1):
            # Try every integer bid a and keep the best  [alg. 1]
            V[t][b] = max(
                expected(V, m, theta, t, b, a)
                for a in range(min(d_max, b) + 1)
            )
    return V

# Expected return from state (t, b) when bidding a  [§4]
def expected(V, m, theta, t, b, a):
    total = 0
    for d in range(len(m)):
        if d <= a:
            # Won at price d: one click, budget falls by d  [§4]
            total += m[d] * (theta + V[t - 1][b - d])
        else:
            # Lost: budget is kept and nothing is earned  [§4]
            total += m[d] * V[t - 1][b]
    return total

# Bid for one request with predicted click value theta_x  [§4] [alg. 1]
def bid(V, t, b, theta_x, d_max):
    best = 0
    for d in range(min(d_max, b) + 1):
        # Gain from paying d instead of keeping the budget  [§4]
        gain = theta_x + V[t - 1][b - d] - V[t - 1][b]
        if gain >= 0:
            best = d
    return best
```

For large T and B, replace the table lookup V[t][b] with a network that
predicts the difference D(t, b), and use the difference form of the gain
[arxiv:1701.02490 §4.1]. For partly observed problems, the same maximum runs
over sampled beliefs instead of a grid [arxiv:2107.07599 §3].

## Contradictions

None known between papers. The cards solve different problems: a campaign
with discount 1 [arxiv:1701.02490 §3.2], and a POMDP with γ in (0, 1)
[arxiv:2107.07599 §2]. Their numbers are not comparable, and the textbook card
gives no value-iteration numbers to compare.

The table card's "Paper vs code" section lists differences between the paper
text and the released code, not between papers. They include how the average
click rate is computed, the smoothing of the price counts, and a clamp on the
network output [arxiv:1701.02490 §2, §4, §4.1]. Read that section before
reimplementing from the code.

## Papers

- [Real-Time Bidding by Reinforcement Learning in Display Advertising](/papers/1701.02490): exact value iteration for impression bidding on a small grid, and a network that approximates value differences for large budgets.
- [POMDPs and Robotics](/papers/2107.07599): review of the exact belief-space recursion and the sampling-based solvers that approximate it.
- [Learning to Play: Reinforcement Learning and Games](/papers/2610.17391): textbook that lists Bellman recursion among RL methods, and covers sampled tree search (MCTS).