78 - Q-Learning: imparare la politica ottima senza conoscere il modello

Negli articoli precedenti abbiamo calcolato la politica ottima con la value iteration, ma a una condizione pesante: conoscere l'ambiente, cioè avere in mano la tabella P(s′|s,a). Nei problemi veri non ce l'abbiamo: un robot non sa in anticipo che cosa farà il pavimento sotto le ruote, un giocatore non conosce le mosse dell'avversario. Ciò che abbiamo è esperienza: possiamo provare un'azione e vedere che cosa succede. Il Q-Learning (Watkins, 1989) è l'algoritmo che trasforma l'equazione di Bellman di ottimalità in una regola di apprendimento da esperienza: dopo ogni passo l'agente corregge un po' la sua stima del valore di quell'azione, e dopo abbastanza passi la tabella converge al valore ottimo, senza che il modello sia mai stato scritto. Qui ricavi la regola passo per passo, la implementi in venti righe, la verifichi contro la soluzione esatta (errore 0.000), vedi l'effetto di α ed ε e scopri la differenza fra imparare «il meglio possibile» e imparare «il meglio dato che sto ancora esplorando», con il confronto fra Q-Learning e SARSA sulla scogliera.

Il vocabolario che serve

La tabella Q è una matrice con una riga per stato e una colonna per azione: la cella Q[s, a] è la stima corrente di q(s, a), il ritorno atteso facendo a in s e poi comportandosi in modo ottimo. Un'esperienza (o transizione) è la quaterna (s, a, r, s′): ero in s, ho fatto a, ho ricevuto r, sono finito in s′. L'apprendimento a differenza temporale (TD learning) aggiorna una stima usando la differenza fra ciò che ci si aspettava e ciò che si è osservato un passo dopo, senza aspettare la fine dell'episodio; il bootstrapping è l'uso, nel bersaglio, della propria stima dello stato successivo invece di un risultato finale reale. L'errore TD δ è la differenza fra bersaglio e stima corrente (se positivo, l'esito è andato meglio del previsto) e il tasso di apprendimento α (0 < α ≤ 1) è la parte dell'errore che si corregge a ogni aggiornamento.

La politica ε-greedy sceglie con probabilità ε un'azione a caso, altrimenti quella col Q più alto, come nel banditore a 10 bracci. Infine la politica di comportamento è quella che genera l'esperienza (qui ε-greedy) e la politica bersaglio è quella che si sta imparando a valutare. Un algoritmo è off-policy se impara una politica bersaglio diversa da quella di comportamento (il Q-Learning impara la politica avida mentre si comporta ε-greedy), on-policy se valuta la stessa che segue (SARSA).

L'analogia: il navigatore che si corregge mentre guida

Ricordi il navigatore dell'articolo su Bellman: stimava il tempo rimasto come «tempo al prossimo incrocio più tempo rimasto da lì». Ora immagina che il navigatore non conosca la mappa: ha solo delle stime iniziali (magari tutte uguali a zero) e le corregge viaggiando. A ogni incrocio si chiede: «mi aspettavo che da qui mancassero 20 minuti; ho impiegato 3 minuti per arrivare all'incrocio e da lì la mia stima dice 15: totale 18. Ho sbagliato di 2 minuti, correggo la mia stima di un po' verso 18». Dopo migliaia di viaggi le stime coincidono con i tempi veri. Non gli è mai servita la mappa: gli sono bastati i viaggi.

Dalla Bellman di ottimalità alla regola di aggiornamento

Dall'articolo su Bellman sappiamo che il valore ottimo dell'azione soddisfa:

q*(s, a) = Σ_{s′} P(s′|s,a) · [ R(s,a,s′) + γ · max_{a′} q*(s′, a′) ]
         = E[ R + γ · max_{a′} q*(S′, a′) | S = s, A = a ]

Il secondo rigo è la stessa formula letta come valore atteso: il valore di (s, a) è la media, su tutte le possibili risposte del mondo, della quantità R + γ max q*(S′, ·). Ora applichiamo l'idea dell'articolo sul banditore: una media si stima con l'aggiornamento incrementale, Q ← Q + α (campione − Q), dove il «campione» è un singolo esito della quantità di cui si vuole la media. Un singolo esperimento ci dà un campione di quella quantità: r + γ max_{a′} q*(s′, a′), con r e s′ osservati. Il problema è che q* non lo conosciamo: lo sostituiamo con la nostra stima corrente Q (bootstrapping). Il risultato è la regola del Q-Learning:

Q(s, a) ← Q(s, a) + α · [ r + γ · max_{a′} Q(s′, a′) − Q(s, a) ]
                          └────────── bersaglio ───────┘   └ stima ┘
                          └───────────── errore TD  δ ───────────────┘

Se s′ è terminale non c'è futuro e il bersaglio è semplicemente r. Tre cose da notare. Nessuna P compare: l'agente non ha bisogno di sapere con che probabilità le cose succedono, perché le probabilità sono incorporate nella frequenza con cui le osserva e nella media che l'aggiornamento costruisce nel tempo. È l'esatto analogo dell'aggiornamento del bandit, con la differenza che il bersaglio contiene la stima di un altro stato. Il max, infine, è la differenza con SARSA: il bersaglio assume che da s′ in poi si faccia l'azione migliore, qualunque cosa l'agente faccia davvero.

Il disegno percorre l'aggiornamento con numeri illustrativi. L'agente era nella cella 5, si è mosso a destra, ha ricevuto −1 ed è finito nella cella 6. Guarda la riga di 6 nella tabella: il valore migliore è −2. Il bersaglio è quindi −1 + 1·(−2) = −3. La sua stima attuale di Q(5, destra) era −4: l'errore TD è −3 − (−4) = +1 (è andata meglio del previsto). Con α = 0.5 la stima passa a −4 + 0.5·1 = −3.5: si sposta a metà strada verso il bersaglio.

Il codice: venti righe

Per rendere eseguibile questo articolo da solo, riporto in forma compatta la GridWorld 4×4 dell'articolo sull'MDP (16 stati, terminali agli angoli, ricompensa −1 a ogni passo, P[s][a] come lista di tuple). Con slip=0.0 ogni azione ha un solo esito; con slip > 0 l'azione devia di lato. Il dizionario MOVES servirà anche alla scogliera.

import numpy as np

# Actions: 0=up, 1=right, 2=down, 3=left
MOVES = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}

class GridWorld:
    """A small MDP written out explicitly: P[s][a] = list of (probability, next_state, reward, done)."""
    def __init__(self, n=4, terminals=(0, 15), step_reward=-1.0, slip=0.0):
        self.n, self.terminals, self.n_states, self.n_actions = n, set(terminals), n * n, 4
        self.P = {s: {a: self._transitions(s, a, step_reward, slip) for a in range(4)} for s in range(self.n_states)}

    def _move(self, s, a):
        r, c = divmod(s, self.n)
        dr, dc = MOVES[a]
        r2, c2 = r + dr, c + dc
        if not (0 <= r2 < self.n and 0 <= c2 < self.n):       # bumping into a wall: stay where you are
            r2, c2 = r, c
        return r2 * self.n + c2

    def _transitions(self, s, a, step_reward, slip):
        if s in self.terminals:                                # terminal states: absorbing, no reward
            return [(1.0, s, 0.0, True)]
        outcomes = {}                                          # next_state -> probability
        for a2, p in [(a, 1.0 - slip), ((a + 1) % 4, slip / 2), ((a - 1) % 4, slip / 2)]:   # intended, or slip to a side
            if p > 0:
                s2 = self._move(s, a2)
                outcomes[s2] = outcomes.get(s2, 0.0) + p
        return [(p, s2, step_reward, s2 in self.terminals) for s2, p in outcomes.items()]

La classe SampledEnv serve a una cosa sola: nascondere il modello all'agente. Riceve la tabella P e offre solo reset() e step(a), come un vero ambiente (la stessa idea di Gymnasium, con firme più semplici delle sue). L'agente può solo provare e osservare.

import numpy as np

class SampledEnv:
    """Wraps a model P[s][a] so that the AGENT can only call reset() and step(a): it never sees the probabilities."""
    def __init__(self, model, start_states, rng):
        self.model, self.start_states, self.rng, self.state = model, start_states, rng, None
    def reset(self):
        self.state = int(self.rng.choice(self.start_states))
        return self.state
    def step(self, a):
        outcomes = self.model.P[self.state][a]
        p, s2, r, done = outcomes[self.rng.choice(len(outcomes), p=[o[0] for o in outcomes])]
        self.state = s2
        return s2, r, done

def q_learning(env, n_states, n_actions, episodes, alpha=0.5, gamma=1.0, epsilon=0.1, seed=0, max_steps=500, log_at=()):
    rng = np.random.default_rng(seed)
    Q = np.zeros((n_states, n_actions))
    snapshots = {}
    for ep in range(1, episodes + 1):
        s = env.reset()
        for _ in range(max_steps):
            if rng.random() < epsilon:
                a = int(rng.integers(n_actions))                      # explore
            else:
                best = np.flatnonzero(Q[s] == Q[s].max())             # exploit, breaking ties at random
                a = int(rng.choice(best))
            s2, r, done = env.step(a)
            target = r if done else r + gamma * Q[s2].max()           # no bootstrapping after a terminal step
            Q[s, a] += alpha * (target - Q[s, a])                     # THE Q-learning update
            s = s2
            if done:
                break
        if ep in log_at:
            snapshots[ep] = Q.copy()
    return Q, snapshots

In step l'ambiente estrae un esito secondo le sue probabilità (rng.choice con p=…) e lo restituisce come (stato successivo, ricompensa, fine): l'agente non vede le probabilità. In q_learning la tabella Q parte a zero. Per ogni episodio: reset, poi, a ogni passo, la scelta ε-greedy dell'azione (rng.random() < epsilon → a caso; altrimenti l'azione col Q massimo, con i pareggi risolti a caso, perché all'inizio sono tutti zero e scegliere sempre la prima biaserebbe l'esplorazione); poi env.step(a); poi il bersaglio target = r if done else r + gamma * Q[s2].max(), dove la clausola if done gestisce il caso terminale; infine l'aggiornamento Q[s, a] += alpha * (target − Q[s, a]). Il parametro log_at salva fotografie della tabella a certi episodi, per vedere la convergenza; max_steps evita un episodio infinito se l'agente non arriva mai al traguardo.

Verifica: ritrova la soluzione esatta?

Usiamo la griglia 4×4, ma questa volta l'agente non vede P. Calcoliamo a parte, con la value iteration, la tabella esatta q* e misuriamo quanto la tabella imparata se ne discosta (errore massimo sulle celle non terminali). Tutti i generatori hanno un seme fisso, quindi due esecuzioni danno la stessa uscita.

# Learn the 4x4 grid WITHOUT being told the model, and compare with the exact answer from value iteration (lesson 76)
model = GridWorld()
env = SampledEnv(model, start_states=[s for s in range(16) if s not in model.terminals], rng=np.random.default_rng(1))

# exact q*, computed with the model (for checking only)
V_star = np.zeros(16)
for _ in range(100):
    for s in range(16):
        V_star[s] = max(sum(p * (r + V_star[s2] * (not d)) for p, s2, r, d in model.P[s][a]) for a in range(4))
Q_star = np.array([[sum(p * (r + V_star[s2] * (not d)) for p, s2, r, d in model.P[s][a]) for a in range(4)] for s in range(16)])

Q, snaps = q_learning(env, 16, 4, episodes=5000, alpha=0.5, gamma=1.0, epsilon=0.2, log_at=(10, 50, 200, 1000, 5000))
nt = [s for s in range(16) if s not in model.terminals]
for ep, Qe in snaps.items():
    err = np.abs(Qe[nt] - Q_star[nt]).max()
    print(f"after {ep:5d} episodes: max |Q - q*| = {err:6.3f}")
print("learned state values max_a Q(s,a):")
print(np.round(Q.max(axis=1).reshape(4, 4), 1))

# Output (due esecuzioni consecutive, stessa uscita):
# after    10 episodes: max |Q - q*| =  3.500
# after    50 episodes: max |Q - q*| =  2.094
# after   200 episodes: max |Q - q*| =  1.891
# after  1000 episodes: max |Q - q*| =  0.125
# after  5000 episodes: max |Q - q*| =  0.000
# learned state values max_a Q(s,a):
# [[ 0. -1. -2. -3.]
#  [-1. -2. -3. -2.]
#  [-2. -3. -2. -1.]
#  [-3. -2. -1.  0.]]

Il codice calcola V_star e Q_star con la value iteration (solo per controllo: l'agente non li vede), poi addestra con ε = 0.2 e α = 0.5 e confronta a cinque istanti. L'errore scende da 3.5 dopo 10 episodi a 1.9 dopo 200, 0.125 dopo 1000 e 0.000 dopo 5000: la tabella imparata è q* (all'arrotondamento a tre decimali). La stampa finale dei valori massimi per stato è esattamente il v* dell'articolo su Bellman (−1, −2, −3 …, la distanza dal traguardo). Un algoritmo che impara solo da esperienza ha ritrovato il risultato di quello che conosceva il modello. Nota che l'errore a 200 episodi (1.891) è quasi quello a 50 (2.094): la convergenza non è regolare, perché dipende da quando l'agente visita per la prima volta le coppie lontane dal traguardo.

Per la teoria, Sutton e Barto riportano che il Q-Learning converge a q* con probabilità 1 purché tutte le coppie stato-azione continuino a essere aggiornate e valga una variante delle condizioni usuali di approssimazione stocastica sui passi α (la somma dei passi diverge e la somma dei loro quadrati converge). La dimostrazione originale è attribuita a Watkins e Dayan (1992), che non ho consultato. Due conseguenze pratiche: serve esplorazione per sempre, o almeno finché non si è visto tutto, e un α costante è un compromesso, non una garanzia.

Che cosa fanno α ed ε (misurato)

La funzione final_error ripete l'addestramento con dieci semi e media l'errore finale: prima varia α con ε = 0.2, poi varia ε con α = 0.5. Il listato impiega qualche minuto in Python puro (circa 3 minuti sull'intera sequenza di questo articolo su questa macchina, una prova).

# How much do the learning rate alpha and the exploration rate epsilon matter?  (4x4 grid, error against the exact q*, mean of 10 seeds)
def final_error(alpha, epsilon, episodes, seeds=10):
    errs = []
    for seed in range(seeds):
        e = SampledEnv(model, start_states=nt, rng=np.random.default_rng(100 + seed))
        Q, _ = q_learning(e, 16, 4, episodes=episodes, alpha=alpha, epsilon=epsilon, seed=seed)
        errs.append(np.abs(Q[nt] - Q_star[nt]).max())
    return np.mean(errs)

print("error after 1000 episodes, epsilon=0.2:")
for alpha in (0.01, 0.1, 0.5, 1.0):
    print(f"  alpha={alpha:4.2f}  max|Q-q*| = {final_error(alpha, 0.2, 1000):6.3f}")
print("error after 1000 episodes, alpha=0.5:")
for epsilon in (0.0, 0.05, 0.2, 0.5):
    print(f"  epsilon={epsilon:4.2f}  max|Q-q*| = {final_error(0.5, epsilon, 1000):6.3f}")

# Output (due esecuzioni consecutive, stessa uscita):
# error after 1000 episodes, epsilon=0.2:
#   alpha=0.01  max|Q-q*| =  2.716
#   alpha=0.10  max|Q-q*| =  1.667
#   alpha=0.50  max|Q-q*| =  0.327
#   alpha=1.00  max|Q-q*| =  0.000
# error after 1000 episodes, alpha=0.5:
#   epsilon=0.00  max|Q-q*| =  1.944
#   epsilon=0.05  max|Q-q*| =  1.794
#   epsilon=0.20  max|Q-q*| =  0.327
#   epsilon=0.50  max|Q-q*| =  0.000

Sul tasso di apprendimento: con α = 0.01 l'agente ha imparato poco in 1000 episodi (errore 2.7), con 0.5 molto di più (0.33), con α = 1 l'errore è addirittura zero. Quest'ultimo risultato non è generalizzabile: la griglia è deterministica, e con α = 1 si sovrascrive il vecchio valore con il nuovo bersaglio, che in un mondo senza rumore è sempre quello giusto. Sull'esplorazione: con ε = 0 l'errore resta alto (1.94) perché l'agente non visita tutte le coppie stato-azione, e alzando ε l'errore scende fino a zero a 0.5 in 1000 episodi. Qui un'esplorazione abbondante conviene perché il problema è minuscolo e non c'è nulla da perdere nell'esplorare; in problemi con penalità forti (la scogliera, più sotto) l'esplorazione ha un costo.

Con il rumore, α = 1 è un disastro

Rendiamo il mondo scivoloso: il 30% delle mosse devia di lato. Calcoliamo il q* esatto del mondo scivoloso e rifacciamo il confronto sul tasso di apprendimento (3000 episodi, 10 semi).

# The same question when the world is NOISY: a slippery grid (30% of the moves slip sideways), exact q* computed with the model
slippery = GridWorld(slip=0.3)
Vs = np.zeros(16)
for _ in range(500):
    for s in range(16):
        Vs[s] = max(sum(p * (r + Vs[s2] * (not d)) for p, s2, r, d in slippery.P[s][a]) for a in range(4))
Qs = np.array([[sum(p * (r + Vs[s2] * (not d)) for p, s2, r, d in slippery.P[s][a]) for a in range(4)] for s in range(16)])

def error_slippery(alpha, episodes=3000, seeds=10):
    errs = []
    for seed in range(seeds):
        e = SampledEnv(slippery, start_states=nt, rng=np.random.default_rng(200 + seed))
        Q, _ = q_learning(e, 16, 4, episodes=episodes, alpha=alpha, epsilon=0.2, seed=seed)
        errs.append(np.abs(Q[nt] - Qs[nt]).max())
    return np.mean(errs)

for alpha in (0.02, 0.1, 0.3, 1.0):
    print(f"slippery world, alpha={alpha:4.2f}: max|Q-q*| after 3000 episodes = {error_slippery(alpha):6.3f}")

# Output (due esecuzioni consecutive, stessa uscita):
# slippery world, alpha=0.02: max|Q-q*| after 3000 episodes =  1.769
# slippery world, alpha=0.10: max|Q-q*| after 3000 episodes =  0.597
# slippery world, alpha=0.30: max|Q-q*| after 3000 episodes =  1.158
# slippery world, alpha=1.00: max|Q-q*| after 3000 episodes =  5.338

Ora il quadro si capovolge: α = 1.0 dà l'errore peggiore (5.34), perché ogni aggiornamento butta via il passato e insegue l'ultimo campione rumoroso: se l'ultima mossa è scivolata di lato, la stima si adegua a quell'esito. α = 0.02 è troppo lento (1.77 dopo 3000 episodi), α = 0.1 è il migliore fra i quattro (0.60), 0.3 è intermedio (1.16). È il classico compromesso: α piccolo è una media su molti campioni (stima stabile ma lenta a imparare), α grande è reattivo ma rumoroso. Con rumore nell'ambiente, α dovrebbe essere piccolo oppure decrescere nel tempo: con α = 1/n si ritrova la media campionaria del banditore.

La scogliera: on-policy contro off-policy

Finora il Q-Learning ha imparato la politica ottima, ma lo fa mentre si comporta in modo diverso (ε-greedy, quindi con mosse a caso). Che cosa succede se le mosse a caso sono pericolose? È il problema del Cliff Walking di Sutton e Barto (esempio 6.6 del loro testo): una griglia 4×12; si parte in basso a sinistra, il traguardo è in basso a destra; fra i due c'è una scogliera (la riga di celle in basso): metterci il piede costa −100 e riporta all'inizio. Ogni altro passo costa −1.

Confrontiamo due algoritmi. Il Q-Learning usa il bersaglio con il max: valuta la politica avida (la migliore), a prescindere da ciò che farà davvero. SARSA (il nome sono le cinque lettere della quintupla S, A, R, S′, A′) usa nel bersaglio l'azione a′ che sceglierà davvero al passo dopo, comprese le mosse a caso:

Q-Learning:  Q(s,a) ← Q(s,a) + α [ r + γ · max_{a′} Q(s′,a′)  − Q(s,a) ]     (off-policy)
SARSA:       Q(s,a) ← Q(s,a) + α [ r + γ · Q(s′, a′)            − Q(s,a) ]     (on-policy, a′ scelta con ε-greedy)

La differenza è una riga di codice, ma cambia ciò che si impara. Il listato implementa l'ambiente, i due algoritmi con lo stesso ciclo (solo il bersaglio differisce) e li misura con ε = 0.1 mantenuto per tutto l'addestramento.

class CliffWalking:
    """Sutton & Barto's cliff: a 4x12 grid. Start bottom-left, goal bottom-right, the cells between them are a cliff.
    Every step costs -1; stepping into the cliff costs -100 and sends the agent back to the start (the episode goes on)."""
    ROWS, COLS = 4, 12
    def __init__(self):
        self.start, self.goal = 3 * 12, 3 * 12 + 11
        self.cliff = {3 * 12 + c for c in range(1, 11)}
        self.n_states, self.n_actions = 48, 4
    def reset(self):
        self.s = self.start
        return self.s
    def step(self, a):
        r, c = divmod(self.s, self.COLS)
        dr, dc = MOVES[a]
        r, c = min(max(r + dr, 0), self.ROWS - 1), min(max(c + dc, 0), self.COLS - 1)
        s2 = r * self.COLS + c
        if s2 in self.cliff:
            self.s = self.start
            return self.s, -100.0, False
        self.s = s2
        return s2, -1.0, s2 == self.goal

def run_td(env, episodes, algorithm, alpha=0.5, gamma=1.0, epsilon=0.1, seed=0, max_steps=1000):
    """algorithm = 'q-learning' (off-policy) or 'sarsa' (on-policy). Returns Q and the reward collected in each episode."""
    rng = np.random.default_rng(seed)
    Q = np.zeros((env.n_states, env.n_actions))
    def act(s):
        if rng.random() < epsilon:
            return int(rng.integers(env.n_actions))
        return int(rng.choice(np.flatnonzero(Q[s] == Q[s].max())))
    returns = []
    for ep in range(episodes):
        s = env.reset(); a = act(s); total = 0.0
        for _ in range(max_steps):
            s2, r, done = env.step(a)
            total += r
            a2 = act(s2)                                              # the action it WILL take next (with exploration)
            if algorithm == "q-learning":
                bootstrap = Q[s2].max()                               # value of the BEST next action
            else:
                bootstrap = Q[s2, a2]                                 # value of the action it will ACTUALLY take
            target = r if done else r + gamma * bootstrap
            Q[s, a] += alpha * (target - Q[s, a])
            s, a = s2, a2
            if done:
                break
        returns.append(total)
    return Q, np.array(returns)

def greedy_path(env, Q, max_steps=60):
    s, path = env.reset(), []
    for _ in range(max_steps):
        a = int(np.argmax(Q[s])); path.append("^>v<"[a])
        s, r, done = env.step(a)
        if done or r == -100.0:
            return "".join(path) + ("  (fell off the cliff!)" if r == -100.0 else "")
    return "".join(path)

cliff = CliffWalking()
for algo in ("q-learning", "sarsa"):
    all_returns = np.array([run_td(cliff, 500, algo, seed=s)[1] for s in range(100)])
    Q, _ = run_td(cliff, 500, algo, seed=0)
    print(f"{algo:10s} mean reward per episode while learning (episodes 100-500, 100 runs): {all_returns[:, 100:].mean():7.1f}")
    print(f"           greedy path of the final policy: {greedy_path(CliffWalking(), Q)}")

# Output (due esecuzioni consecutive, stessa uscita):
# q-learning mean reward per episode while learning (episodes 100-500, 100 runs):   -49.1
#            greedy path of the final policy: ^>>>>>>>>>>>v
# sarsa      mean reward per episode while learning (episodes 100-500, 100 runs):   -28.0
#            greedy path of the final policy: ^^^>>>>>>>>>>v>vv

CliffWalking.step implementa le regole: griglia 4×12, la cella «scogliera» riporta all'inizio con −100 e l'episodio continua; il traguardo termina l'episodio. run_td esegue Q-Learning o SARSA: la sola differenza è la riga bootstrap = Q[s2].max() contro bootstrap = Q[s2, a2], dove a2 è l'azione che l'agente eseguirà (estratta con ε-greedy prima di aggiornare). greedy_path segue la politica finale senza esplorare e stampa le frecce. I numeri sono medie su 100 esecuzioni indipendenti, sugli episodi dal 100° al 500°; il percorso mostrato è quello del seme 0.

Il Q-Learning impara il percorso più breve, di 13 passi (^ su, undici >, v giù): rasente la scogliera, perché secondo il suo bersaglio (che assume di non esplorare più) quello è il percorso migliore. Ma durante l'addestramento si comporta ε-greedy: ogni tanto, lungo il bordo, una mossa a caso lo fa cadere (−100), e il suo guadagno medio per episodio è −49.1. SARSA impara un percorso più lungo, che sale fino alla riga alta e scende solo alla fine, lontano dal bordo: il suo bersaglio include le mosse a caso che farà davvero, e sa che camminare vicino alla scogliera con ε = 0.1 è pericoloso. Il suo guadagno medio durante l'addestramento è −28.0, molto meglio.

Non c'è un vincitore assoluto: dipende da ciò che si vuole. Se alla fine si smetterà di esplorare (ε = 0) e si userà la politica avida, quella di Q-Learning è migliore (13 passi, cioè −13, contro −17 per il percorso di SARSA, che ne fa 17). Se invece l'agente continuerà a esplorare anche in produzione, oppure se le sue prestazioni durante l'apprendimento contano (un robot vero che cade dalla scogliera si rompe), SARSA è la scelta più sicura. In sintesi: Q-Learning impara «cosa farei se agissi al meglio», SARSA impara «cosa conviene fare dato che a volte sbaglio».

I compromessi

La tabella Q richiede una cella per ogni coppia stato-azione: perfetta per 16 o 48 stati, impossibile per un'immagine. È il limite che affrontano l'articolo su Gymnasium, con ambienti più grandi, e quello sulla Deep Q-Learning. Off-policy riusa meglio l'esperienza (può imparare da dati raccolti da qualunque politica) ma può essere instabile con approssimatori; on-policy è più prudente. Quanto a α ed ε, costanti sono semplici ma lasciano rumore residuo e un costo permanente di esplorazione, decrescenti sono più precisi ma richiedono di scegliere il programma di decadimento.

Trappole reali

1. Dimenticare il caso terminale. Se bootstrappi anche dopo la fine dell'episodio, Q include «futuro» che non esiste e i valori sono gonfiati.
2. Scegliere sempre la prima azione fra i pareggi. All'inizio tutti i Q sono 0: argmax restituisce sempre la prima azione e l'esplorazione è distorta. Spezza i pareggi a caso (come nel codice).
3. Valutare con ε > 0. Durante la valutazione della politica imparata si spegne l'esplorazione (ε = 0), altrimenti si misura una politica rumorosa diversa da quella appresa. Il confronto «−49.1 contro −28.0» è durante l'apprendimento, un'altra misura.
4. α = 1 in ambienti rumorosi. Come visto: errore 5.34 contro 0.60 con α = 0.1.
5. Confondere on-policy e off-policy. Il Q-Learning non valuta la politica che segue. Se la politica di comportamento è pericolosa, la politica che impara non ne tiene conto (Cliff Walking).
6. Un solo seme. Le medie sulla scogliera sono su 100 esecuzioni; con una sola sarebbero molto rumorose (cadere o no è questione di fortuna).

Le prime due trappole sono errori di implementazione che si vedono guardando il codice; le ultime tre sono errori di misura e di interpretazione che nessun test automatico segnala, perché i numeri escono comunque. Se devi controllare un Q-Learning scritto da altri, parti dal caso terminale e dal modo di risolvere i pareggi, poi chiedi con quale ε e su quanti semi sono state fatte le misure.

Un esempio svolto a mano: due episodi di Q-Learning su una catena di tre stati

Un corridoio di tre celle: s0 (partenza), s1 e il traguardo G (terminale). Azioni: destra (R) e sinistra (L). Ogni passo costa −1; γ = 1, α = 0.5; tutta la tabella parte a 0.

Episodio 1. Da s0 si fa R e si arriva in s1 con ricompensa −1. Bersaglio: −1 + max Q(s1, ·) = −1 + 0 = −1. Aggiornamento: Q(s0, R) = 0 + 0.5·(−1 − 0) = −0.5. Da s1 si fa R e si arriva in G (terminale) con ricompensa −1. Bersaglio: −1 (nessun futuro). Q(s1, R) = 0 + 0.5·(−1 − 0) = −0.5.

Episodio 2. Da s0 di nuovo R verso s1 (ricompensa −1). Ora la riga di s1 è [Q(L) = 0, Q(R) = −0.5], quindi max = 0. Bersaglio: −1 + 0 = −1. Q(s0, R) = −0.5 + 0.5·(−1 + 0.5) = −0.75. In s1, questa volta si esplora (ε) e si fa L, tornando in s0 con ricompensa −1: bersaglio −1 + max Q(s0, ·) = −1 + max(Q(L) = 0, Q(R) = −0.75) = −1. Q(s1, L) = 0 + 0.5·(−1 − 0) = −0.5.

Fermiamoci a guardare ciò che è successo. I valori delle azioni provate sono scesi sotto zero (−0.75, −0.5, −0.5) perché tutte le ricompense sono negative; le azioni non provate (Q(s0, L)) restano a 0, che sembra meglio di qualunque azione provata: l'agente è «ottimista» verso ciò che non conosce, e questo spinge a esplorare. Il bersaglio di Q(s0, R) nell'episodio 2 usa il valore 0 di un'azione mai provata in s1: il bootstrapping usa le stime come sono, anche immature, ed è per questo che servono molti episodi perché l'informazione si propaghi (il valore vero di Q(s0, R) è −2: due passi da pagare). L'ordine di aggiornamento conta, infine: aggiornare dal traguardo all'inizio propaga l'informazione in un colpo solo.

Esercizi con soluzione

1. Q(s, a) = 2, r = 1, γ = 0.9, max Q(s′, ·) = 4, α = 0.5. Quanto vale il nuovo Q(s, a)?
   Soluzione: bersaglio 1 + 0.9·4 = 4.6; errore 4.6 − 2 = 2.6; nuovo 2 + 0.5·2.6 = 3.3.
2. Che differenza c'è, nell'aggiornamento, fra Q-Learning e SARSA?
   Soluzione: Q-Learning usa il valore dell'azione migliore in s′ (max); SARSA usa il valore dell'azione a′ che sceglierà davvero (inclusa l'eventuale mossa a caso).
3. Perché la tabella Q non richiede di conoscere P?
   Soluzione: perché le probabilità di transizione sono incorporate nella frequenza con cui i vari esiti si presentano: l'aggiornamento incrementale costruisce, nel tempo, la media pesata che nell'equazione di Bellman si calcolava con P.
4. L'agente ha ε = 0 e tutti i Q a zero all'inizio, con ricompense negative. Che comportamento ti aspetti?
   Soluzione: le azioni provate diventano negative e quelle mai provate restano a zero (sembrano migliori): per un po' l'agente prova tutte le azioni, in una sorta di esplorazione «ottimistica» involontaria; ma senza esplorazione esplicita può comunque restare bloccato su una scelta sub-ottima.

Il primo esercizio è aritmetica di aggiornamento, il secondo e il terzo fissano le due idee che separano il Q-Learning dalla programmazione dinamica (il max e l'assenza di P). Il quarto è il più utile in pratica, perché collega l'inizializzazione della tabella al comportamento esplorativo.

Domande frequenti

Perché si dice che il Q-Learning «converge» se i valori oscillano?

Con α costante le stime oscillano attorno al valore vero, come la media mobile di un segnale rumoroso. La convergenza esatta richiede α decrescente; nella pratica si accetta una piccola oscillazione.

Il Q-Learning funziona senza una politica ε-greedy?

Qualunque politica che visiti tutte le coppie stato-azione va bene, perché l'algoritmo è off-policy: può imparare da dati raccolti in modo diverso (da un altro agente, da un esperto, da un registro). Questa flessibilità è il suo punto di forza.

E se lo spazio degli stati è enorme?

La tabella non regge e si passa all'approssimazione con reti neurali, come nella Deep Q-Learning, con nuovi problemi di stabilità.

Perché α = 0.5 negli esempi e non 0.01?

Per rendere visibili gli aggiornamenti con pochi passi. In problemi veri, e in particolare con rumore, valori come 0.01-0.1 sono più tipici; la tabella delle misure sopra mostra il perché (0.10 era il migliore nel mondo scivoloso).

Come si sceglie γ per il Q-Learning?

Come per Bellman: è parte del problema, come mostra l'articolo sulle ricompense ritardate. Con episodi brevi e finiti si può usare anche 1, come qui.

Si può imparare Q direttamente da dati già raccolti, senza interagire?

È l'apprendimento per rinforzo offline: possibile, ma delicato, perché l'agente può sopravvalutare azioni mai viste nei dati. Non lo abbiamo trattato e non ne ho misurato nulla qui.

Che cosa sai fare adesso

Sai scrivere il Q-Learning, Q(s,a) ← Q(s,a) + α [ r + γ max Q(s′,·) − Q(s,a) ], e dire che cosa sono l'errore TD, il bootstrapping e perché nessuna probabilità di transizione compare. Nella griglia l'hai visto ritrovare q* con errore 0.000 dopo 5000 episodi senza vedere P. Sai che con il rumore α = 1 è disastroso (5.34 contro 0.60 con α = 0.1), e sai scegliere fra Q-Learning e SARSA: sulla scogliera il primo impara il percorso più breve ma lo paga durante l'addestramento (−49.1), il secondo un percorso più prudente (−28.0). Il limite resta la tabella: nel prossimo articolo usiamo la libreria Gymnasium per ambienti più grandi (Taxi e FrozenLake), con protocolli di valutazione seri.