Actor–Critic Methods

The previous lesson measured that baseline subtraction brings the gradient estimate into agreement, but the baseline that was subtracted was a crude list: the step-by-step mean return read from separate episodes of the same policy. It did not use the state at all. A state in which all five subscribers are waiting at the thirtieth step and a state in which all are freshly visited were compared with the same number, although the two are clearly different places.

This lesson replaces the fixed baseline with a learned state value. A two-component arrangement emerges: the actor that chooses the action and the critic that says how valuable the current state is. The update of the actor is now scaled not by the return itself but by the advantage — by how much better the action turned out than what was expected in that state. Two things will be measured: the difference the advantage estimate makes, and the situation in which the two components spoil each other.

• RL57. The environment is the setup built in 01: five subscribers, one crew per period, horizon 30, discount factor 0.9. The weight array of the actor is 36 numbers as in 06, and the measurement is on the same 300 episodes.
• RL58. The critic uses the same six features as the actor and is a single weight row — six numbers. It is kept linear because what this lesson measures is not the capacity of the critic but the interaction of the two components.
• RL59. The advantage is one-step: the reward received, plus the discounted value of the next state, minus the value of the current state. At the last step of the episode the value of the next state is taken as zero.
• RL60. The critic is updated in the temporal difference form and the same advantage is used in the update; that is, the actor and the critic share a single number. This sharing is also the reason the two can spoil each other.
• RL61. Three methods are compared under the same budget: 240 episodes, a batch of two episodes, 120 updates. The only thing that changes is the number that scales the update of the actor — the raw return, the return with a fixed baseline subtracted, or the advantage.
• RL62. The comparison is made at two learning steps: 0.01 and 0.06. Measuring at a single step is misleading, because the real difference between the methods is which step they can carry.
• RL63. The own learning step of the critic is a separate hyperparameter and is swept; the number of candidates tried is four.
• RL64. Every measure is printed with two runs; between the runs only the seed of the training episodes changes. The evaluation episodes are the same in every run.

The Difference the Advantage Makes

The block below rebuilds the environment and the policy, gathers the three methods in a single training procedure and measures at two learning steps. The three methods differ only in the number A.

# actor_critic.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):                   # ACTOR: exponential normalization, the policy of 06
    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 state_value(w, s):                      # CRITIC: the value of the state, a row of six numbers
    return sum(a * b for a, b in zip(w, [v / 2.0 for v in s] + [1.0]))


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):
    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 train(seed, mode, rate, beta=0.05, budget=240, batch=2):
    th, w, baseline = [[0.0] * FEATURES for _ in range(ACTIONS)], [0.0] * FEATURES, [0.0] * HORIZON
    for t in range(budget // batch):
        grad_th, grad_w, mean_G = [0.0] * (ACTIONS * FEATURES), [0.0] * FEATURES, [0.0] * HORIZON
        for i in range(batch):
            trace = episode_trace(th, seed + 1000 * t + i)
            G = returns_to_go(trace)
            for u, (s, a, reward) in enumerate(trace):
                p, x = probabilities(th, s)
                if mode == "raw return":
                    A = G[u]
                elif mode == "fixed baseline":
                    A = G[u] - baseline[u]
                else:                       # learned critic: one-step advantage
                    v2 = 0.0 if u == HORIZON - 1 else state_value(w, trace[u + 1][0])
                    A = reward + DISCOUNT * v2 - state_value(w, s)
                    for j in range(FEATURES):
                        grad_w[j] += A * x[j] / batch
                for b in range(ACTIONS):
                    k = A * ((1.0 if b == a else 0.0) - p[b])
                    for j in range(FEATURES):
                        grad_th[b * FEATURES + j] += k * x[j] / batch
            for u in range(HORIZON):
                mean_G[u] += G[u] / batch
        baseline = mean_G
        for b in range(ACTIONS):
            for j in range(FEATURES):
                th[b][j] += rate * grad_th[b * FEATURES + j]
        for j in range(FEATURES):
            w[j] += beta * grad_w[j]
    return th, w


print(f"{'method':<22}{'step 0.01':>20}{'step 0.06':>20}")
FINAL = {}
for mode in ("raw return", "fixed baseline", "learned critic"):
    row = ""
    for rate in (0.01, 0.06):
        g = [run(lambda s, r, th=train(SEED + 300000 + k * 7919, mode, rate)[0]: choose(th, s, r))
             for k in (1, 2)]
        FINAL[(mode, rate)] = g
        row += f"{g[0]:>10.3f}{g[1]:>10.3f}"
    print(f"{mode:<22}{row}")
for rate in (0.01, 0.06):
    h, u = FINAL[("raw return", rate)], FINAL[("learned critic", rate)]
    c = FINAL[("fixed baseline", rate)]
    print(f"step {rate}: gain of the advantage over the raw return {min(u) - min(h):+.3f} / "
          f"{max(u) - max(h):+.3f}; band raw {max(h) - min(h):.3f}, "
          f"baseline {max(c) - min(c):.3f}, advantage {max(u) - min(u):.3f}")

method                           step 0.01           step 0.06
raw return                15.840    19.962    14.207    17.218
fixed baseline            22.866    22.190     0.029    15.982
learned critic            21.154    21.100    23.401    23.755
step 0.01: gain of the advantage over the raw return +5.260 / +1.192; band raw 4.122, baseline 0.675, advantage 0.053
step 0.06: gain of the advantage over the raw return +9.194 / +6.537; band raw 3.011, baseline 15.953, advantage 0.354

Reading the table by looking at a single column is misleading. At the small step (0.01) the best number is given by the fixed baseline: 22.866 and 22.190. The learned critic stays below it with 21.154 and 21.100, and the finding of 06 is not broken — a crude baseline does its job in this environment too. The difference the advantage makes over the raw return is still marked: +5.260 and +1.192.

The distinction appears at the large step. When the learning step is raised to 0.06, both methods that rely on the full return break down: the raw return falls to 14.207 and 17.218, one run of the fixed baseline gives 0.029 — that is, almost nothing above the never-dispatch baseline — and its band rises to 15.953. The advantage estimate gives 23.401 and 23.755 at the same step and its band stays at 0.354.

This is what the advantage really brings. It does not raise the level a little, it lowers the wobble; because the wobble falls, a larger learning step can be carried; and the large step extracts more progress from the same budget. The full return is the sum of thirty steps and carries the noise of thirty steps; the one-step advantage carries only one reward and two value estimates.

This trade is not free. The full return, however much it wobbles, is an outcome that was actually lived. The one-step advantage hands twenty-nine of the thirty steps over to the estimate of the critic. If the critic is wrong, the advantage is not only wobbly but systematically wrong, and the error looks in the same direction in every run. This is not visible in the table above, because the critic works. The next block makes it stop working.

When the Critic Breaks

The two components share a single number: the same advantage updates both the actor and the critic. When the critic gives a wrong value, the actor shifts in the wrong direction; when the actor shifts, the distribution the critic is trying to learn changes as well. The block below sweeps the learning step of the critic and counts where this loop breaks.

LABELS = ("A1", "A2", "A3", "A4", "A5", "idle")
ALL_STATES = [(a, b, c, e, f) for a in range(3) for b in range(3) for c in range(3)
              for e in range(3) for f in range(3)]


def action_distribution(th, n=300):
    counts = [0] * ACTIONS
    for k in range(n):
        env, r = Environment(SEED + 1000 * k), rng(SEED + 90000 + k)
        s = env.state()
        for _ in range(HORIZON):
            a = choose(th, s, r)
            counts[a] += 1
            s = env.step(a)[0]
    return counts


print(f"{'critic step':>17}{'run 1':>9}{'run 2':>9}{'mean |V|':>14}"
      f"{'most chosen':>16}{'never visited':>15}")
for beta in (0.00, 0.05, 0.50, 2.00):
    g = []
    for k in (1, 2):
        th, w = train(SEED + 300000 + k * 7919, "learned critic", 0.06, beta)
        g.append(run(lambda s, r: choose(th, s, r)))
        if k == 1:
            d = action_distribution(th)
            mean_v = statistics.mean(abs(state_value(w, s)) for s in ALL_STATES)
    total, top = sum(d), d.index(max(d))
    print(f"{beta:>17.2f}{g[0]:>9.3f}{g[1]:>9.3f}{mean_v:>14.3g}"
          f"{LABELS[top] + ' ' + format(max(d) / total, '.3f'):>16}"
          f"{sum(x == 0 for x in d[:SUBSCRIBERS]):>15}")

      critic step    run 1    run 2      mean |V|     most chosen  never visited
             0.00   22.506   22.620             0        A3 0.305              0
             0.05   23.401   23.755          22.2        A3 0.258              0
             0.50  -16.492  -18.772      2.6e+102        A1 1.000              4
             2.00  -15.332  -14.622     5.84e+180        A5 1.000              4

The first row is the form without a critic: because the step is zero the values stay at zero and the advantage reduces to the one-step reward. The result is 22.506 and 22.620 — not bad, because in this environment the reward mostly comes immediately. When the critic works (0.05) the number rises to 23.401 and 23.755; the mean value the critic produces is 22.2, that is, on the order of the measured return. What the critic gains is about one unit, and it should not be written down without being measured.

The last two rows show the break. When the step of the critic is raised to 0.50 the values diverge to the order of $10^{102}$. The advantage no longer carries the reward but the own error of the critic; its sign becomes fixed independently of the state and all the probability of the actor shifts onto a single action: the share of A1 is 1.000. Four of the five subscribers are never visited. The return is −18.772 — not only bad, but also below the 0.000 of never dispatching a crew, because every period the crew cost is paid and almost nothing is received in return. At step 2.00 the same collapse happens to another subscriber, A5; which action it piles onto is not even a result, it is an accident.

This is the sharpest form of the rule of the course. Someone looking at the return column sees that both runs are bad but cannot know why. The fourth column — the number of subscribers never visited — states the reason directly: the policy collects its own data, and once it piles onto a single action nothing more is learned about four subscribers, and the critic can never estimate the states of those four subscribers correctly. A system that does not write down the collected data counts as unmeasured.

Summary

• In the actor–critic arrangement the actor chooses the action, the critic says the value of the state, and the update of the actor is scaled not by the return but by the advantage: the reward plus the discounted next state value minus the current state value.
• Under the same budget of 240 episodes, with a step of 0.01 the raw return gives 15.840 and 19.962, the fixed baseline 22.866 and 22.190, the advantage 21.154 and 21.100. A crude baseline does not fall behind the learned critic at this step.
• The distinction shows when the learning step is raised to 0.06: one run of the fixed baseline falls to the never-dispatch baseline with 0.029 and its band becomes 15.953, while the advantage gives 23.401 and 23.755 and keeps the band at 0.354. What the advantage brings is not level but stability, and stability makes the larger step carryable.
• The own learning step of the critic is a hyperparameter: four candidates were tried, 0.05 gave the best and brought about one unit over the form without a critic.
• When the step of the critic is raised to 0.50 the values diverge to the order of $10^{102}$, all the probability of the actor piles onto a single action, four of the five subscribers are never visited and the return falls below inaction with −18.772.

Next Step

In seven lessons the agent chose its own action and learned its result directly from the environment: a reward came from the subscriber to whom it sent the crew, and the subscribers it did not send to kept deteriorating. The response came at every step, right after the choice, and the choice changed the next state. The numbers were written above the same two baselines — never dispatching a crew 0.000 and a random action 10.432 — and the 20.621 of the rule policy was the threshold to be passed: the table of 05 24.495, the replay-buffer network of the same lesson 26.233, the actor with the advantage estimate of this lesson 23.755. The third number of the measure was always in the same form — which states were never seen, which action was never tried.

The next topic breaks the same loop at one point. The action is no longer something the agent does, it is an option offered to a person: which service item to recommend to a subscriber. The recommendation is shown, but its result is seen only if that person chooses it — an item that is not shown is never scored, and an item that is not scored is never shown again. The collected data is no longer the states the agent has wandered through but the items it showed, and the items never learned because they were never shown. The next lesson builds the baseline of this arrangement and measures the surprisingly high baseline of the field: recommending the most used item to everyone.