Flerarmade banditer

Du har k spelautomater («armar») med okända vinstchanser. Varje drag: dra en arm, se belöning. Mål: maximera total belöning. Problemet: för att veta vilken som är bäst måste du utforska dåliga armar; för att tjäna måste du utnyttja den bästa.

• ε-greedy: med sannolikhet ε dra slumpmässig arm, annars den med högst skattat medel. Enkelt; utforskar för evigt lika mycket.
• Thompson sampling: håll en sannolikhetsfördelning (Beta) över varje arms chans; dra ett stickprov per arm, välj högsta. Utforskar automatiskt mer där osäkerheten är stor. Nära optimal i praktiken.
• UCB: välj arm med högst medel + bonus för osäkerhet.

Regret = vad du förlorade mot att alltid ha dragit bästa armen. Bra algoritmer har regret som växer som log(t).

AI-grafen använder detta för att välja vilken förklaringstyp som fungerar bäst för en användare: varje förklaringsdjup är en arm, «användaren klarade övningen» är belöningen.

import numpy as np
rng = np.random.default_rng(0)
p_sann = np.array([0.30, 0.45, 0.60, 0.40])          # okända för agenten

def kor(valj, T=5000):
    n = np.zeros(4); s = np.zeros(4); regret = 0.0
    for t in range(T):
        a = valj(n, s, t)
        r = rng.random() < p_sann[a]
        n[a] += 1; s[a] += r; regret += p_sann.max() - p_sann[a]
    return regret

def eps_greedy(eps=0.1):
    def f(n, s, t):
        if rng.random() < eps or n.min() == 0: return rng.integers(4)
        return int(np.argmax(s / n))
    return f

def thompson(n, s, t):
    return int(np.argmax(rng.beta(s + 1, n - s + 1)))

print("eps-greedy", round(kor(eps_greedy()), 1))     # ≈ 90
print("thompson  ", round(kor(thompson), 1))         # ≈ 25