Reinforcement learning — only hit or miss

import random

BIAS = (-11.0, 7.0)
WOBBLE = 4.0
STEP = 0.15        # told a number
CAT_STEP = 0.6     # told a category
GOLD = 10.0        # inside this ring, the coach says 'hit'
NEAR = 2.5         # 'has learned it': aim this close to perfect
BUDGET = 4000      # arrows after which we stop waiting

IDEAL = (-BIAS[0], -BIAS[1])

def residual(aim):
    return ((aim[0] - IDEAL[0]) ** 2 + (aim[1] - IDEAL[1]) ** 2) ** 0.5

def sign(v):
    return 1.0 if v > 0 else (-1.0 if v < 0 else 0.0)

def fire(aim, rng):
    return (aim[0] + BIAS[0] + rng.gauss(0, WOBBLE),
            aim[1] + BIAS[1] + rng.gauss(0, WOBBLE))

def told(seed, kind, budget=400):
    """Told a number, or told a category. Both can correct; only the step differs."""
    rng = random.Random(seed)
    aim = [0.0, 0.0]
    for n in range(1, budget + 1):
        shot = fire(aim, rng)
        if kind == 'number':
            aim[0] -= STEP * shot[0]
            aim[1] -= STEP * shot[1]
        else:
            aim[0] -= CAT_STEP * sign(shot[0])
            aim[1] -= CAT_STEP * sign(shot[1])
        if residual(aim) < NEAR:
            return n
    return budget

record('near_cm', NEAR)
record('gold_cm', int(GOLD))

BATCH = 10         # arrows spent judging one setting
SIGMA = 4.0        # how far a guess strays from where it is now

def hit_or_miss(seed, gold=GOLD, budget=BUDGET):
    rng = random.Random(seed)
    aim = [0.0, 0.0]
    spent = 0

    def hit_rate(a):
        """Fire BATCH arrows at `a`. All the coach ever says is hit or miss."""
        nonlocal spent
        hits = 0
        for _ in range(BATCH):
            shot = fire(a, rng)
            spent += 1
            hits += 1 if (shot[0] ** 2 + shot[1] ** 2) ** 0.5 <= gold else 0
        return hits / BATCH

    while spent < budget:
        here = hit_rate(aim)                                  # re-measured, every round
        guess = [aim[0] + rng.gauss(0, SIGMA), aim[1] + rng.gauss(0, SIGMA)]
        there = hit_rate(guess)
        if there > here:
            aim = guess
        if residual(aim) < NEAR:
            return spent
    return budget

def average(f, trials=40, **kw):
    return round(sum(f(s, **kw) for s in range(trials)) / trials)

arrows = {
    'told a number': average(lambda s: told(s, 'number')),
    'told a category': average(lambda s: told(s, 'category')),
    'told hit or miss': average(hit_or_miss),
}
for label, n in arrows.items():
    print(f'{label:>18}: {n} arrows')

record('arrows_number', arrows['told a number'])
record('arrows_category', arrows['told a category'])
record('arrows_hitmiss', arrows['told hit or miss'])
record('times_more', round(arrows['told hit or miss'] / arrows['told a number']))

def plot_cost(ax):
    labels = list(arrows)
    values = list(arrows.values())
    bars = ax.bar(labels, values, color=['#9aa1ab', '#3b6fd4', '#ee785b'])
    for b, v in zip(bars, values):
        ax.text(b.get_x() + b.get_width() / 2, v + max(values) * 0.02, f'{v}',
                ha='center', fontsize=11)
    ax.set_ylabel('arrows until it has learned the habit')
    ax.set_ylim(0, max(values) * 1.16)
    ax.spines[['top', 'right']].set_visible(False)

save_fig('what-one-word-costs', plot_cost, figsize=(7.0, 3.8))

import matplotlib.pyplot as plt
import matplotlib.patches as patches

def plot_rings(ax):
    rng2 = random.Random(11)
    shots = [fire((11.0, -7.0), rng2) for _ in range(60)]      # a robot already aiming well
    ax.scatter([s[0] for s in shots], [s[1] for s in shots], s=22, color='#ee785b',
               alpha=0.7, zorder=1)
    for r, style in ((20, ':'), (6, '--'), (2, '-')):
        inside = sum(1 for s in shots if (s[0] ** 2 + s[1] ** 2) ** 0.5 <= r)
        ax.add_artist(patches.Circle((0, 0), r, facecolor='none', edgecolor='#3a3a3a',
                                     lw=1.4, ls=style, zorder=2))
        ax.annotate(f'{r} cm ring — {inside} of {len(shots)} arrows are a "hit"',
                    xy=(r * 0.71, r * 0.71), xytext=(26, r - 1), fontsize=9.5, color='#3a3a3a',
                    va='center', arrowprops=dict(arrowstyle='-', color='#b9b2aa', lw=1))
        record(f'hits_at_{r}', inside)
    ax.set_xlim(-24, 68); ax.set_ylim(-24, 24); ax.set_aspect('equal')
    ax.set_xticks([]); ax.set_yticks([]); ax.grid(False)
    for side in ('top', 'right', 'bottom', 'left'):
        ax.spines[side].set_visible(False)

save_fig('what-counts-as-a-hit', plot_rings, figsize=(7.4, 3.4))

golds = [2, 3, 6, 10, 14, 20]
costs = [average(hit_or_miss, trials=30, gold=float(g)) for g in golds]
for g, c in zip(golds, costs):
    cap = '  (never got there — stopped at the budget)' if c >= BUDGET * 0.95 else ''
    print(f'gold {g:>2} cm -> {c:>5} arrows{cap}')

record('budget', BUDGET)
record('cost_tiny', costs[0])
record('cost_best', min(costs))
record('best_gold', golds[costs.index(min(costs))])
record('cost_huge', costs[-1])

def plot_signal(ax):
    ax.plot(golds, costs, color='#ee785b', linewidth=2.4, marker='o', markersize=7)
    ax.axhline(BUDGET, color='#6b7280', linestyle=':', linewidth=1.2)
    ax.text(3, BUDGET * 0.93, 'gave up here', fontsize=9.5, color='#6b7280')
    ax.annotate('almost never hits\nevery word is "miss"', xy=(2, costs[0]),
                xytext=(2.6, costs[0] + BUDGET * 0.16), fontsize=9.5, color='#6b7280')
    ax.annotate('almost always hits\nevery word is "hit"', xy=(20, costs[-1]),
                xytext=(12.4, costs[-1] - BUDGET * 0.20), fontsize=9.5, color='#6b7280')
    ax.set_xlabel('how big the gold ring is (cm)')
    ax.set_ylabel('arrows until it has learned the habit')
    ax.set_ylim(0, BUDGET * 1.1)
    ax.spines[['top', 'right']].set_visible(False)

save_fig('a-word-that-never-changes', plot_signal, figsize=(7.2, 4.0))