The Exploration and Exploitation Trade-Off

In the previous two lessons the policy was written by hand. The rule knew from the start what to do, no number was learned from data, and so learning had no cost. When the policy starts to be learned, a constraint counted in the first lesson of the course turns directly into a conflict: in one step the agent sees only the outcome of the action it chose and hears nothing about the five it did not choose. The only way to learn how good an action is is to try it, and every trial is deducted from that period’s return.

Exploitation is choosing the action with the highest estimate; it turns current knowledge into money. Exploration is choosing an action whose estimate is low or missing; it turns today’s return into information. This lesson turns the conflict into a knob, sweeps the knob and counts both directions: how many steps are lost for how many steps gained.

• RL18. The setup, horizon, discount factor and seed continue unchanged from 01–02. Five subscribers, one crew, the same deterioration probabilities, 243 states, 6 actions, an episode of 30 periods.
• RL19. In this lesson the estimate is the mean of the immediate reward. For each state-action pair the mean of the rewards seen in that pair is kept; the return and the temporal difference are left to the next lesson.
• RL20. The form of exploration is a single rate. With probability $\varepsilon$ the action is chosen without discrimination, and in the remaining cases the one with the highest estimate is chosen; ties are broken by the smallest number.
• RL21. Regret is the immediate cost of exploration steps: at every step, the difference between the reward the greedy action would have given at that step and the reward actually received is accumulated. In exploitation steps this difference is exactly zero, while in exploration steps it can also come out negative.
• RL22. The initial value of the estimates is a choice, and this lesson measures it too. The pessimistic initial value is $-5.0$ and is below all possible rewards; the optimistic initial value is $0.0$ and is above $-2$, the reward of a wasted visit.
• RL23. Training is 300 episodes, that is 9,000 steps. Then the table is frozen and the learned greedy policy is measured on the same 300 episode seeds as in 01; the numbers are on the same scale as 10.432 and 20.621.
• RL24. The swept exploration rates are seven candidates: 0.00, 0.02, 0.05, 0.10, 0.20, 0.40 and 1.00.
• RL25. The measure is a triple and is always printed side by side: the return of the frozen policy, the accumulated regret and the number of actions never tried. When a state never seen in training is met, all estimates are equal and the action with the smallest number is chosen.

The Always-Exploiting Agent

# environment.py — FICTIONAL. Field visit planning continues unchanged from the previous two
# lessons: five subscribers, one crew each period, seed 20260218.
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)
LABELS = ("A1", "A2", "A3", "A4", "A5", "idle")
ACTIONS, HORIZON, DISCOUNT = SUBSCRIBERS + 1, 30, 0.9


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:
    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 run(policy, n=300):
    G = []
    for k in range(n):
        env = Environment(SEED + 1000 * k)
        s, g, c = env.state(), 0.0, 1.0
        for _ in range(HORIZON):
            s, r = env.step(policy(s, env))
            g, c = g + c * r, c * DISCOUNT
        G.append(g)
    return G


def train(explore, initial, n_episodes=300, seed=SEED + 11):
    """For each state-action pair the mean of the IMMEDIATE reward is kept."""
    draw = rng(seed)
    Q, N, regret, explore_steps = {}, {}, 0.0, 0
    for k in range(n_episodes):
        env = Environment(SEED + 1000 * k)
        s = env.state()
        for _ in range(HORIZON):
            q = Q.setdefault(s, [initial] * ACTIONS)
            n = N.setdefault(s, [0] * ACTIONS)
            greedy = max(range(ACTIONS), key=lambda i: q[i])
            a = int(draw() * ACTIONS) if draw() < explore else greedy
            expected = PAYOFF[env.level[greedy]] - COST if greedy < SUBSCRIBERS else 0.0
            s2, reward = env.step(a)
            regret += expected - reward
            explore_steps += (a != greedy)
            n[a] += 1
            q[a] += (reward - q[a]) / n[a]
            s = s2
    return Q, N, regret, explore_steps


def freeze(Q, initial):
    """Learning ends, the table freezes; the policy is now greedy."""
    def pol(s, env):
        q = Q.get(s, [initial] * ACTIONS)
        return max(range(ACTIONS), key=lambda i: q[i])
    return pol


INITIAL = -5.0
Q0, N0, regret0, explore0 = train(0.00, INITIAL)
tried = [sum(N0[s][a] for s in N0) for a in range(ACTIONS)]
print(f"exploration rate 0.00, initial value of estimates {INITIAL}")
print(f"  return of the learned policy {statistics.mean(run(freeze(Q0, INITIAL))):.3f}")
print(f"  accumulated regret {regret0:.1f}; exploration steps {explore0}")
print(f"  states seen {len(N0)}/243; state-action pairs tried "
      f"{sum(1 for v in N0.values() for x in v if x > 0)}/1458")
print("  trials per action: "
      + ", ".join(f"{LABELS[a]}={tried[a]}" for a in range(ACTIONS)))

exploration rate 0.00, initial value of estimates -5.0
  return of the learned policy -16.492
  accumulated regret 0.0; exploration steps 0
  states seen 95/243; state-action pairs tried 95/1458
  trials per action: A1=9000, A2=0, A3=0, A4=0, A5=0, idle=0

The agent that never explores spends all 9,000 of its steps on a single action. The reason can be read in one line: at the start all estimates are $-5.0$, ties are broken by the smallest number, the first action is A1, and whatever A1’s real reward comes out as, it is above $-5.0$. The estimate rises, A1 is now alone at the top and nothing can ever overtake it, because the estimates of the other five actions stay at $-5.0$ since they were never tried. A2, A3, A4, A5 and the option of not dispatching the crew are never tried: five of the six actions.

The result shows in the return. The policy gets $-16.492$; far below the 0.000 of never dispatching the crew and the 10.432 of random action. The agent goes to A1 every period, A1 is mostly found clean because it was repaired a period earlier, and every visit writes down 2 units. The number confirms this: the discounted total of getting $-2$ without a break for thirty periods is $-19.152$, and the measured $-16.492$ owes the difference to A1 occasionally deteriorating and giving 1 or 7. The collected data narrows as well: 95 of the 243 states are seen, and of the 1,458 pairs only 95 are tried. These 95 pairs mean a single action in each of 95 states — always the same action.

Regret, meanwhile, is exactly 0.0. This is not an achievement, it is the definition of the measure: regret counts the immediate cost of exploration steps, and there are no exploration steps. That a system’s regret is zero does not say the system is good, it says it learned nothing. The two numbers carry meaning only side by side.

Sweeping the Exploration Rate

# sweep.py — Seven exploration rates, the same budget (300 episodes, 9,000 steps), the same
# horizon, the same pessimistic initial value. The learned policy is then frozen and measured.
print(f"{'rate':>6}{'return':>9}{'regret':>10}{'explore steps':>15}"
      f"{'states':>8}{'pairs':>7}{'actions never tried':>22}")
for explore in (0.00, 0.02, 0.05, 0.10, 0.20, 0.40, 1.00):
    Q, N, regret, steps = train(explore, INITIAL)
    count = [sum(N[s][a] for s in N) for a in range(ACTIONS)]
    never = [LABELS[a] for a in range(ACTIONS) if count[a] == 0]
    pairs = sum(1 for v in N.values() for x in v if x > 0)
    print(f"{explore:>6.2f}{statistics.mean(run(freeze(Q, INITIAL))):>9.3f}{regret:>10.1f}"
          f"{steps:>15}{len(N):>8}{pairs:>7}{(','.join(never) if never else '-'):>22}")

  rate   return    regret  explore steps  states  pairs   actions never tried
  0.00  -16.492       0.0              0      95     95      A2,A3,A4,A5,idle
  0.02   16.716     -76.0            150     127    237                     -
  0.05   22.210     402.0            364     143    335                     -
  0.10   23.606    1210.0            748     176    472                     -
  0.20   25.659    3545.0           1500     185    578                     -
  0.40   25.997    8358.0           2945     217    839                     -
  1.00   23.000   33811.0           7494     235   1237                     -

The return column draws a single-peaked curve. At zero exploration $-16.492$, at 0.40 the highest value 25.997, at 1.00 again 23.000. The two ends are bad for two different reasons. On the left the agent does not learn, because it does not try. On the right the agent chooses every step without discrimination, so the data it collects is good but its behavior is bad; even so the frozen table gives 23.000, that is, good data can be collected with bad behavior — the basic tension of the next course sits here in seed form.

The real reading is between two columns. A rate of 0.20 gives a return of 25.659 at a cost of 3,545 regret. A rate of 0.40 gives only 0.338 more return but costs 8,358, more than double. The return bought with exploration rises with diminishing increments; each additional exploration step brings less information than the one before, yet its cost stays the same. Going to 1.00, a regret of 33,811 is paid and the return drops.

The minus sign in the 0.02 row is not an error, it is the measure itself. The total cost of the 150 exploration steps is $-76.0$: on average the exploration steps brought better rewards than the greedy action. The reason is that the greedy action was locked onto A1 at that stage; while going to A1 mostly writes $-2$, the action chosen without discrimination has often found something better. While a bad policy is being exploited, the cost of exploration falls below zero. The cost turns positive only when the exploited policy is actually good, and the rise in the table follows exactly this.

The pairs-tried column carries a warning too. Even at the most generous exploration, 1,237 of the 1,458 pairs are tried, so 221 are never tried and the states seen stay at 235. If the frozen policy meets the remaining 8 states it finds all estimates equal and chooses the action with the smallest number. This also defines where the learned number holds: as far as the region where the table is full.

The two columns on the right carry the third number of the course. As the exploration rate grows, the states seen rise from 95 to 235, and the pairs tried from 95 to 1,237. Exploration is not merely paying a cost; it widens the data it collects and the widening data ensures that more cells of the frozen table hold a number. The hyperparameter search lies outside this measure and is not repeated: in the candidate sweep built in the model evaluation topic of the Supervised Learning course, what was paid when the number of candidates was increased was the computation budget; the data stood fixed from start to finish and no loss remained after the search ended. Here what is paid is the return itself: every exploration step is a period that was actually lived, cannot be taken back, and also permanently changes the data collected in that period.

Exploration Does Not Have to Come from Randomness

# initial.py — The same sweep, two different initial values. A pessimistic initial value
# makes an untried action look bad; an optimistic initial value makes it look worth trying.
print(f"{'initial value':>14}{'rate':>7}{'return':>9}{'regret':>10}{'pairs':>7}")
for initial in (-5.0, 0.0):
    for explore in (0.00, 0.05, 0.20):
        Q, N, regret, steps = train(explore, initial)
        pairs = sum(1 for v in N.values() for x in v if x > 0)
        print(f"{initial:>14.1f}{explore:>7.2f}"
              f"{statistics.mean(run(freeze(Q, initial))):>9.3f}{regret:>10.1f}{pairs:>7}")

 initial value   rate   return    regret  pairs
          -5.0   0.00  -16.492       0.0     95
          -5.0   0.05   22.210     402.0    335
          -5.0   0.20   25.659    3545.0    578
           0.0   0.00   26.212       0.0    356
           0.0   0.05   26.155     772.0    496
           0.0   0.20   26.378    4147.0    636

The bottom three rows make the whole table above be read again. With the exploration rate again 0.00, the return is not $-16.492$ but 26.212, the regret is again exactly 0.0, and the pairs tried are not 95 but 356. Exploration happened without a single random step being taken.

The reason is in the initial value. The estimate of an untried action is $0.0$; the real reward of a wasted visit is $-2$. When the agent tries an action and gets $-2$, that action’s estimate falls below those of the untried actions and the greedy choice shifts by itself to the next one. As long as the estimates start above the truth, greediness itself produces exploration; disappointment brings the next action onto the agenda. With a pessimistic initial value the opposite happens: whatever the first tried action gives, it rises above the untried ones and the door closes.

This is an exploration mechanism that keeps regret at zero, but it is not free. The initial value has to be above the real rewards, which requires prior knowledge about the scale of the rewards; that 0.0 works in the setup is because we know a wasted visit writes $-2$. Its effect is also temporary: once each cell has been tried one time the optimism is spent, and if the environment changes over time exploration is needed again. Exploration done by rate is permanent and is paid at every step. The difference between 4,147 and 0.0 in the table puts the cost of these two mechanisms side by side in the same unit.

Summary

• Exploitation chooses the action with the highest estimate, exploration tries the uncertain one; since the agent sees the outcome of only the action it chose in a step, the two cannot be done at the same time.
• The agent that never explores, with a pessimistic initial value, spends all 9,000 steps on A1, never tries five of the six actions, sees 95 of the 243 states and gets a return of $-16.492$.
• A regret of 0.0 is not a good sign: because there are no exploration steps it is zero by definition, and it says nothing unless read side by side with the return.
• When the exploration rate is swept from 0.00 to 1.00 the return rises from $-16.492$ to 25.997 and falls to 23.000; the cost climbs from 0.0 to 33,811.0. A rate of 0.20 stays 0.338 below the best return while paying only 0.424 of the cost.
• At a low exploration rate regret can fall below zero ($-76.0$), because the exploited policy is bad at that stage and the action chosen without discrimination turns out on average better than it.
• The initial value of the estimates is also an exploration mechanism: with an optimistic start, without a single random step, the return rises to 26.212, the pairs tried from 95 to 356, and regret stays at 0.0.

Next Step

The number kept in this lesson was the mean of the immediate reward: what an action in a state brought in that period. In the first lesson, however, the return was defined as the discounted total of thirty periods, and the real effect of a visit does not end in that period — the repaired subscriber stays clean for a few more periods, the neglected subscriber costs more a few periods later. An estimate that looks at the immediate reward never sees this chain, which is why it gets stuck at 26.378. The next lesson turns the number kept in the table from the immediate reward into the return: the value of a state is the sum of the discounted rewards that can be collected from there on, and this number can be learned step by step from the difference between two successive estimates. The measure will again be read from the collected data: how many cells of the table remain never updated at the end of 9,000 steps.