Policy Gradient

In the previous five lessons the policy was always built indirectly: a value was estimated for each action and the largest was chosen. In this arrangement the policy is a by-product of the value estimate — if the estimated values of two actions are close to each other, a small drift in the estimate turns the choice completely around. The choice is also sharp: the action with the largest value is always chosen, the second best action never.

This lesson takes another path. The policy is parameterized directly: each action is given a weight row, a probability distribution is produced from the state, and the weights are shifted in the direction that will increase the return. The direction is no longer read from a table; it is estimated from sampled episodes — and what this lesson measures is how much that estimate wobbles.

• RL49. The environment is the setup built in 01 and continues as it was: five subscribers, one crew per period, horizon 30, discount factor 0.9. The measurement is on the same 300 episodes as in 01.
• RL50. The features of the policy are the five delay classes and a constant, that is, six numbers. The weight array is $6 \times 6 = 36$ numbers; throughout the lesson “direction” describes a shift of these 36 numbers.
• RL51. The action probabilities come from the exponential normalization of the weighted sums. When all weights are zero the distribution is equiprobable; this is the policy at which the measurement starts, and it is the same as the random action baseline of 01.
• RL52. The direction read from one episode is, at every step, the product of the return after that step and the shift that increases the probability of the chosen action. The discount factor is not applied separately as a step weight; the return itself is already discounted.
• RL53. The variability is written with two numbers: the mean pairwise angle between the estimates and the agreement ratio — the length of the mean estimate divided by the mean length of the individual estimates. If the agreement is near 1 the estimates point to the same place, if it is near 0 they cancel one another. Both measures are independent of the number of estimates.
• RL54. The baseline is the step-by-step mean return read from separate 200 episodes of the same policy. It has to be read from separate episodes; if the own return of the measured episode is subtracted, the direction is by definition zeroed.
• RL55. The baseline is independent of the action, so it does not shift the place the estimate is going to: when the probability shifts of all the actions in a state are summed the result is zero, and therefore the multiplier of a constant number is zero as well. The only thing that changes is the wobble of the estimate.
• RL56. In training the budget is 240 episodes and the learning step is held constant at 0.01; the only things that change are the batch size and whether baseline subtraction is used.

Writing the Policy Directly

The block below rebuilds the environment, defines the policy and computes the direction read from one episode. The logic of the direction is one sentence: if the return that comes after an action is chosen is large, the probability of that action is increased, if it is small it is decreased.

# policy.py — FICTIONAL. The same setup: five subscribers, one crew, horizon 30, discount 0.9.
import math
import statistics

SEED, M32 = 20260218, 0xFFFFFFFF
SUBSCRIBERS, PAYOFF, COST = 5, (0, 3, 9), 2
DETERIORATION = (0.30, 0.05, 0.60, 0.15, 0.45)
ACTIONS, HORIZON, DISCOUNT = SUBSCRIBERS + 1, 30, 0.9
FEATURES = SUBSCRIBERS + 1                  # number of features: five delay classes + a constant


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


class Environment:
    """The deterioration level is hidden; the state the agent sees is the delay class."""

    def __init__(self, seed):
        self.draw = rng(seed)
        self.level, self.delay = [0] * SUBSCRIBERS, [0] * SUBSCRIBERS
        for i in range(SUBSCRIBERS):
            self.delay[i] = int(self.draw() * 6)
            for _ in range(self.delay[i]):
                if self.level[i] < 2 and self.draw() < DETERIORATION[i]:
                    self.level[i] += 1

    def state(self):
        return tuple(min(2, x // 3) for x in self.delay)

    def step(self, a):
        reward = 0.0
        if a < SUBSCRIBERS:
            reward = PAYOFF[self.level[a]] - COST
            self.level[a] = 0
            self.delay[a] = 0
        for i in range(SUBSCRIBERS):
            if i != a:
                self.delay[i] += 1
                if self.level[i] < 2 and self.draw() < DETERIORATION[i]:
                    self.level[i] += 1
        return self.state(), reward


def probabilities(th, s):                   # exponential normalization; th[a] is the weight row of the action
    x = [v / 2.0 for v in s] + [1.0]
    z = [sum(t * v for t, v in zip(th[a], x)) for a in range(ACTIONS)]
    e = [math.exp(v - max(z)) for v in z]
    total = sum(e)
    return [v / total for v in e], x


def choose(th, s, r):
    p, _ = probabilities(th, s)
    u, t = r(), 0.0
    for a in range(ACTIONS):
        t += p[a]
        if u < t:
            return a
    return ACTIONS - 1


def run(policy, n=300):                     # the same 300 episodes as in 01
    returns = []
    for k in range(n):
        env, r = Environment(SEED + 1000 * k), rng(SEED + 90000 + k)
        s, total, factor = env.state(), 0.0, 1.0
        for _ in range(HORIZON):
            s2, reward = env.step(policy(s, r))
            total, factor, s = total + factor * reward, factor * DISCOUNT, s2
        returns.append(total)
    return statistics.mean(returns)


def episode_trace(th, seed):
    env, r = Environment(seed), rng(seed + 5)
    s, trace = env.state(), []
    for _ in range(HORIZON):
        a = choose(th, s, r)
        s2, reward = env.step(a)
        trace.append((s, a, reward))
        s = s2
    return trace


def returns_to_go(trace):                   # the discounted return after each step
    G, g = [0.0] * len(trace), 0.0
    for t in range(len(trace) - 1, -1, -1):
        g = trace[t][2] + DISCOUNT * g
        G[t] = g
    return G


def episode_gradient(th, trace, G, baseline=None):     # the update direction read from a single episode
    e = [0.0] * (ACTIONS * FEATURES)
    for t, (s, a, _) in enumerate(trace):
        p, x = probabilities(th, s)
        w = G[t] - (baseline[t] if baseline else 0.0)
        for b in range(ACTIONS):
            k = w * ((1.0 if b == a else 0.0) - p[b])
            for j in range(FEATURES):
                e[b * FEATURES + j] += k * x[j]
    return e


def value_baseline(th, seeds):              # the step-by-step mean return, from SEPARATE episodes
    total = [0.0] * HORIZON
    for sd in seeds:
        G = returns_to_go(episode_trace(th, sd))
        for t in range(HORIZON):
            total[t] += G[t] / len(seeds)
    return total


def angle(u, v):
    nu = math.sqrt(sum(x * x for x in u))
    nv = math.sqrt(sum(x * x for x in v))
    c = sum(a * b for a, b in zip(u, v)) / (nu * nv)
    return math.degrees(math.acos(max(-1.0, min(1.0, c))))


def measure(estimates):
    n = len(estimates)
    mean = [sum(v[j] for v in estimates) / n for j in range(len(estimates[0]))]
    length = statistics.mean(math.sqrt(sum(x * x for x in v)) for v in estimates)
    return (statistics.mean(angle(estimates[i], estimates[j])
                            for i in range(n) for j in range(i + 1, n)),
            math.sqrt(sum(x * x for x in mean)) / length)


TH = [[0.0] * FEATURES for _ in range(ACTIONS)]    # all weights zero: equal-probability policy
rp = rng(SEED + 7)
print(f"{'baseline: no dispatch':<30}{run(lambda s, r: SUBSCRIBERS):8.3f}")
print(f"{'baseline: random action':<30}{run(lambda s, r: int(rp() * ACTIONS)):8.3f}")
print(f"{'measured policy (weights 0)':<30}{run(lambda s, r: choose(TH, s, r)):8.3f}")

BUDGET = 120
BASELINE = value_baseline(TH, [SEED + 700000 + i for i in range(200)])
RAW, BASELINED = [], []
for i in range(BUDGET):
    trace = episode_trace(TH, SEED + 200000 + i)
    G = returns_to_go(trace)
    RAW.append(episode_gradient(TH, trace, G))
    BASELINED.append(episode_gradient(TH, trace, G, BASELINE))


def group_mean(items, B):
    return [[sum(v[j] for v in items[i * B:(i + 1) * B]) / B for j in range(ACTIONS * FEATURES)]
            for i in range(len(items) // B)]


print(f"\nbaseline: first step {BASELINE[0]:.2f}, tenth {BASELINE[9]:.2f}, last {BASELINE[-1]:.2f}")
print(f"{'episodes/estimate':>17}{'estimates':>10}{'angle':>8}{'agreement':>11}"
      f"{'angle (baseline)':>18}{'agreement (baseline)':>22}")
for B in (1, 2, 4, 10, 20):
    h, t = measure(group_mean(RAW, B)), measure(group_mean(BASELINED, B))
    print(f"{B:>17}{BUDGET // B:>10}{h[0]:>8.1f}{h[1]:>11.3f}{t[0]:>18.1f}{t[1]:>22.3f}")

baseline: no dispatch            0.000
baseline: random action         10.432
measured policy (weights 0)     10.177

baseline: first step 9.88, tenth 11.18, last 1.63
episodes/estimate estimates   angle  agreement  angle (baseline)  agreement (baseline)
                1       120    86.1      0.290              81.2                 0.389
                2        60    83.1      0.386              74.8                 0.511
                4        30    77.9      0.508              67.0                 0.636
               10        12    62.4      0.736              53.1                 0.790
               20         6    44.0      0.878              39.8                 0.892

The third row gives the measure of the policy: the policy with zero weights returns 10.177, that is, it is at the same place as the 10.432 of the random action. This is what is expected — equiprobable choice is random choice and the 0.255 difference between the two numbers is only a sampling detail.

The first row of the table is the number of the lesson. When the budget of 120 episodes is used one by one, 120 distinct update directions come out and these directions make a mean angle of 86.1 degrees: they are almost perpendicular to one another. The agreement ratio is 0.290, that is, seven tenths of the directions cancel one another when summed. Shifting the weights by looking at a direction read from a single episode is writing noise into the policy.

When the budget is not divided, the table smooths out: six estimates of twenty episodes each give 44.0 degrees and 0.878 agreement. But this has a cost — the same budget falls to six updates. This is the tension measured throughout the lesson: the more reliable the direction is wanted, the fewer updates can be made.

Subtracting the Baseline

The baseline row shows the source of the problem: in this environment the returns are between 9.88 and 11.18 in the first steps and 1.63 at the last step. Nearly all of them are positive. When the return is used directly as the multiplier, the probability of every chosen action is increased; the distinction between actions comes only from the size of the increase. A bad action, too, since the return that follows it is positive, ends up increasing its probability.

Baseline subtraction corrects this. The mean return of each step is subtracted from the return of that step; an action that stays above the mean is increased, one that stays below it is decreased. The number is in the right half of the table: for a single episode 86.1 degrees becomes 81.2 degrees, and the agreement rises from 0.290 to 0.389. A more readable form is this — two episodes with baseline subtraction give 0.511 agreement, four raw episodes 0.508. The same agreement is obtained with half the budget.

The effect shrinks as the budget grows: with twenty episodes 44.0 degrees falls to 39.8 degrees, and the agreement rises from 0.878 to 0.892. If the estimate is already sampled enough, baseline subtraction has little left to correct.

The Same Budget, Four Setups

The variability measure gains meaning only when it is turned into learning. The block below spends the same budget of 240 episodes in four ways: a batch of two or ten episodes, with baseline subtraction or with raw return.

def train(seed, baselined, batch, budget=240, rate=0.01):
    th = [[0.0] * FEATURES for _ in range(ACTIONS)]
    baseline = [0.0] * HORIZON
    for t in range(budget // batch):
        direction, mean_G = [0.0] * (ACTIONS * FEATURES), [0.0] * HORIZON
        for i in range(batch):
            trace = episode_trace(th, seed + 1000 * t + i)
            G = returns_to_go(trace)
            e = episode_gradient(th, trace, G, baseline if baselined else None)
            for j in range(ACTIONS * FEATURES):
                direction[j] += e[j] / batch
            for u in range(HORIZON):
                mean_G[u] += G[u] / batch
        if baselined:
            baseline = mean_G               # the baseline comes from the previous batch
        for b in range(ACTIONS):
            for j in range(FEATURES):
                th[b][j] += rate * direction[b * FEATURES + j]
    return th


print(f"{'setup':<28}{'updates':>11}{'run 1':>9}{'run 2':>9}{'band':>7}")
FINAL = {}
for batch in (2, 10):
    for baselined in (False, True):
        name = f"{batch} episodes, {'with baseline' if baselined else 'raw return'}"
        g = [run(lambda s, r, th=train(SEED + 300000 + k * 7919, baselined, batch): choose(th, s, r))
             for k in (1, 2)]
        FINAL[(batch, baselined)] = g
        print(f"{name:<28}{240 // batch:>11}{g[0]:>9.3f}{g[1]:>9.3f}{max(g) - min(g):>7.3f}")

h2, t2 = FINAL[(2, False)], FINAL[(2, True)]
print(f"\nbaseline subtraction at a two-episode estimate: {min(h2):.3f} -> {min(t2):.3f} and "
      f"{max(h2):.3f} -> {max(t2):.3f}, band {max(h2) - min(h2):.3f} -> {max(t2) - min(t2):.3f}")

setup                           updates    run 1    run 2   band
2 episodes, raw return              120   15.840   19.962  4.122
2 episodes, with baseline           120   22.866   22.190  0.675
10 episodes, raw return              24   17.121   17.853  0.732
10 episodes, with baseline           24   16.808   16.900  0.093

baseline subtraction at a two-episode estimate: 15.840 -> 22.190 and 19.962 -> 22.866, band 4.122 -> 0.675

The four rows confirm how the table is read. The two-episode estimate gives 15.840 and 19.962 with raw return; both exceed the 10.432 of the random action but the run band is 4.122 — a number that moves by more than four units only because the starting episodes change. When the baseline is subtracted in the same setup, 22.866 and 22.190 come out and the band falls to 0.675. Here baseline subtraction both raises the level and brings stability, because a two-episode estimate is too wobbly to be used without a baseline.

With the ten-episode estimate the table turns around: 16.808 and 16.900 against 17.121 and 17.853. Baseline subtraction brings no gain here. The reason is in the table — at ten episodes the agreement is already 0.736 and baseline subtraction carries it to 0.790; this improvement does not make up for the number of updates, which falls to a tenth of the budget. The best number comes from where many updates and an agreeing direction meet.

No setup of this lesson approaches the 26.233 of the previous lesson. Here the policy gradient is weaker than the action value, and this needs to be written down: a linear policy of 36 numbers learns as much as it can by weighting the delay classes and choosing; the action value built by the network also carries the nonlinear distinctions between states.

Summary

• Parameterizing the policy directly removes the action value from the middle: each action is given a weight row, the probabilities are produced by exponential normalization, the weights are shifted in the direction that will increase the return.
• The direction is now estimated from sampled episodes and it wobbles: when the budget of 120 episodes is used one by one, 120 distinct directions come out, the mean angle between them is 86.1 degrees and the agreement ratio 0.290.
• One way to bring the estimate into agreement is not to divide the budget — with twenty episodes the angle comes to 44.0 degrees and the agreement to 0.878 — but then the same budget falls to six updates.
• Because the baseline is independent of the action, it does not shift the place the estimate is going to, it only lowers its wobble: two episodes with baseline subtraction give 0.511 agreement, four raw episodes 0.508.
• In the same budget of 240 episodes the two-episode estimate gives 15.840 and 19.962 with raw return and 22.866 and 22.190 with baseline subtraction; the band falls from 4.122 to 0.675. With the ten-episode estimate the gain of baseline subtraction disappears.

Next Step

In this lesson the baseline remained a fixed list: the step-by-step mean return read from separate episodes of the same policy. It does not use the state at all — it gives the same number for every state at the thirtieth step, although some states are clearly better than others. The next lesson replaces the fixed baseline with a learned value function and trains two components together: the side that chooses the action and the side that evaluates it. Two things will be measured — the gain brought by the difference read against the value of the state itself, and the situation in which the two components spoil each other: where the choosing side goes when the evaluating side gives a wrong number.