Value iteration

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 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 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 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 1701.02490 §4.

A textbook card lists Bellman recursion among the solution methods for reinforcement learning 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) 1701.02490 §4.1. The market-price distribution is estimated by counting, and the average click-through rate comes from historical data 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 1701.02490 tab. 2. Card: Real-Time Bidding by Reinforcement Learning in Display Advertising.

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) 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 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 1701.02490 tab. 4. The paper states that generalisation is satisfactory only at small scales 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 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 1701.02490 §6.2. Card: Real-Time Bidding by Reinforcement Learning in Display Advertising.

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 2107.07599 §3. Its sampling-based solvers back up values only at a sampled set of beliefs, and they do not produce optimal policies 2107.07599 §1, §3.

• PBVI keeps one alpha-vector per sampled belief and does point-based backups only 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 2107.07599 §3.1.
• SARSOP samples beliefs close to those reachable under an optimal policy and prunes provably suboptimal branches 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 2107.07599 §3.1. Card: POMDPs and Robotics.

When to use which

Implementation sketch

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

# 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 1701.02490 §4.1. For partly observed problems, the same maximum runs over sampled beliefs instead of a grid 2107.07599 §3.

Contradictions

None known between papers. The cards solve different problems: a campaign with discount 1 1701.02490 §3.2, and a POMDP with γ in (0, 1) 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 1701.02490 §2, §4, §4.1. Read that section before reimplementing from the code.

Papers

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