Giocare fino in fondo: i metodi Monte Carlo

Contenuti

Giocare fino in fondo: i metodi Monte Carlo#

Nel 1946, a Los Alamos, Stanisław Ulam era in convalescenza e passava le giornate a fare solitari. A un certo punto si chiese quale fosse la probabilità che un solitario venisse. Provò a calcolarla con la combinatoria, si arenò, e gli venne l’idea che avrebbe cambiato mezzo secolo di scienza applicata: invece di calcolare la probabilità, giocare cento partite e contare quante finiscono bene. Ne parlò con John von Neumann, e Nicholas Metropolis propose per il metodo un nome preso dal casinò dove uno zio di Ulam andava a perdere i soldi presi in prestito dai parenti [Met87].

L’idea è tutta lì, e serve esattamente al punto in cui la sezione precedente si è fermata. Il metodo di là, quello che riscriveva i numeri delle caselle finché non si assestavano (l’iterazione dei valori, in inglese value iteration), sa calcolare i valori ma pretende la mappa: per ogni mossa, dove si finisce e quanto si incassa. Se la mappa non c’è, resta una via che non chiede nulla a nessuno: far vivere all’agente molte partite intere, guardare come sono andate, e fare la media.

Giocare, e poi fare la media#

Il ritorno è quello definito nella sezione precedente: quanto si raccoglie in tutto da un certo istante fino alla fine della partita, contando meno ciò che arriva tardi. Il valore di una situazione è il ritorno medio partendo da lì, e una media si stima nel modo più ovvio che ci sia: si prendono tanti casi e si fa la loro media. Qui i casi sono le partite giocate.

Elementare

Vuoi sapere quanto vale, negli scacchi, una certa posizione. Un modo c’è, e non richiede di capire niente di scacchi: da quella posizione gioca mille partite fino allo scacco matto, e segnati com’è finita ogni volta, un punto se hai vinto e zero se hai perso. La media di quei mille numeri è la percentuale di vittorie, e se è alta la posizione è buona.

I metodi Monte Carlo fanno questo, e la parola difficile non nasconde niente di più. L’agente gioca una partita dall’inizio alla fine, poi torna indietro con la matita e, per ogni situazione attraversata, si annota quanto ha raccolto da lì in avanti. Ripetuto molte volte, quel quaderno di annotazioni diventa la stima del valore di ogni situazione: si fa la media delle righe che parlano della stessa casella.

Una partita però può ripassare due volte per la stessa casella, e allora lascia due righe. Si tengono tutte e due, o si tiene solo la prima? Tenerle tutte sfrutta ogni riga scritta. In cambio le partite che girano in tondo lasciano molte righe a testa, e proprio per questo finiscono per pesare più delle altre: finché le partite sono poche, i due conti non danno lo stesso numero.

Quanto ci si può fidare di una media dipende da quante partite ci sono dietro, e il conto è meno generoso di quanto si spererebbe: per dimezzare l’oscillazione servono quattro volte le partite. Con cento partite il numero balla ancora parecchio, e per farlo ballare la metà ce ne vogliono quattrocento, non duecento.

Sul quaderno non finisce mai una stima: ogni riga è il conto dei punti che quella partita ha davvero portato a casa. Nessuna mappa, nessuna formula sull’ambiente: solo partite giocate e una media. Il prezzo è dichiarato subito: bisogna arrivare alla fine della partita prima di poter scrivere qualsiasi cosa.

Superiore

Ogni volta che un episodio attraversa lo stato \(s\) si parla di visita a \(s\). Il metodo a prima visita stima \(V^\pi(s)\) come la media dei ritorni che seguono la prima visita a \(s\) in ciascun episodio; quello a ogni visita media i ritorni che seguono tutte le visite:

\[ V(s) \;=\; \frac{1}{|\mathcal{T}(s)|} \sum_{t \in \mathcal{T}(s)} G_t , \]

dove \(\mathcal{T}(s)\) è l’insieme degli istanti in cui \(s\) è stato visitato (solo le prime visite, nella variante a prima visita).

La versione a prima visita ha una giustificazione immediata: i ritorni raccolti sono variabili aleatorie indipendenti e identicamente distribuite con media \(V^\pi(s)\) e varianza finita, quindi per la legge dei grandi numeri la media converge al valore vero, e l’errore standard cala come \(1/\sqrt{n}\) con \(n\) ritorni mediati. Ogni stima è non distorta.

La variante a ogni visita è invece distorta per \(n\) finito, e la spiegazione naturale della distorsione è sbagliata. Non viene dal fatto che i ritorni di uno stesso episodio siano correlati: una media di variabili correlate, in numero fissato e con la stessa media marginale, resta non distorta, e la correlazione muove la varianza, non il valore atteso. Viene dal fatto che il denominatore è aleatorio. Il numero di visite non è deciso in anticipo ed è correlato con il numeratore, perché un episodio che passa molte volte per lo stesso stato contribuisce molte righe, e quelle righe non sono un campione qualunque dei ritorni possibili. È il classico stimatore-rapporto, dove l’attesa del rapporto non è il rapporto delle attese. Di quanto e in che verso sbagli dipende dal problema: il conto sulle tre partite, dove la variante a ogni visita dà un numero più alto dell’altra, ne è un esempio e non una regola. La distorsione svanisce al crescere degli episodi, e la variante si estende meglio a quando il quaderno diventa una rete neurale [SB18].

Il punto strutturale: qui non c’è bootstrapping. Il bersaglio è il ritorno osservato, non una stima costruita a partire da altre stime. Ogni stato si stima per conto proprio, e la stima di uno stato non dipende dalla stima degli altri.

Che cosa cambia rispetto alla programmazione dinamica#

Programmazione dinamica è il nome che Bellman diede al modo di procedere della sezione precedente (con lo scrivere programmi per il computer non c’entra niente: «programmazione», per lui, voleva dire pianificazione), quello che trova i valori girando e rigirando su tutte le caselle con la mappa in mano: da qui in avanti lo useremo come nome collettivo delle sue due ricette, l’iterazione dei valori e quella della pagella (value iteration e policy iteration). Conviene metterlo accanto a Monte Carlo, perché la differenza fra i due non è di efficienza ma di che cosa serve sapere.

La programmazione dinamica guarda un passo in avanti ma in tutte le direzioni: per calcolare il valore di una casella tiene conto di tutte le caselle in cui quella mossa potrebbe far finire, dando a ciascuna un peso pari alla sua probabilità. Quei pesi le servono, e quindi le serve conoscere le probabilità; in cambio non le deve stimare.

Monte Carlo guarda in una direzione sola ma fino in fondo: segue la traiettoria realmente accaduta, dall’inizio alla fine dell’episodio, e ignora le strade non prese. Non ha bisogno di sapere nulla dell’ambiente, e in cambio paga in rumore: è la parola che si usa per il fatto che una misura, ripetuta, non dà mai due volte lo stesso numero.

Da questa differenza discendono tre conseguenze pratiche.

Monte Carlo funziona anche quando l’ambiente è una scatola nera o un simulatore: basta saperci giocare, non saperlo descrivere. Scrivere un programma che simula un gioco è spesso molto più facile che compilare l’elenco, mossa per mossa e con tutte le probabilità, di dove quel gioco può portare.
Il costo di stimare un singolo stato non dipende dal numero di stati. Se interessa il valore di una manciata di posizioni, si giocano partite da quelle e basta, senza passare in rassegna tutte le altre come fa la programmazione dinamica.
Gli errori non si propagano. Il voto di una casella esce solo da quello che è successo davvero nelle partite, e nessun’altra casella se ne serve per calcolare il proprio: un voto sbagliato resta sbagliato dov’è, e non contagia i vicini.

Tre partite, coi numeri#

Riprendiamo il mondo a tre caselle della Fig. 12.2, quello in cui salire non costa nulla, restare fermi o tornare indietro costano \(1\), e arrivare all’obiettivo paga \(10\). Vale lo stesso sconto di prima, \(0{,}9\): un premio che arriva una mossa più tardi conta nove decimi. Stavolta però fingiamo di non conoscere dove porta ogni mossa. L’agente si limita a giocare, seguendo una strategia che di norma sale verso l’obiettivo ma ogni tanto tentenna, ed ecco tre sue partite, con le ricompense incassate lungo la strada.

\(s_0 \xrightarrow{\,0\,} s_1 \xrightarrow{\,+10\,} s_2\)
\(s_0 \xrightarrow{\,-1\,} s_0 \xrightarrow{\,0\,} s_1 \xrightarrow{\,+10\,} s_2\)
\(s_0 \xrightarrow{\,0\,} s_1 \xrightarrow{\,-1\,} s_0 \xrightarrow{\,0\,} s_1 \xrightarrow{\,+10\,} s_2\)

Ogni riga si legge da sinistra a destra, e il numero sopra la freccia è quello che si incassa facendo quel passo, col suo segno: \(+10\) vuol dire dieci punti guadagnati, \(-1\) un punto perso. Nella prima partita, da \(s_0\) si sale a \(s_1\) senza incassare nulla, e da \(s_1\) si arriva all’obiettivo incassando \(+10\).

Elementare

I punti raccolti si contano all’indietro, ed è il modo comodo di farlo: si parte dalla fine, dove il totale è \(0\) perché dopo l’arrivo non c’è più niente da raccogliere, e a ogni passo indietro si moltiplica per \(0{,}9\) il totale che si aveva e ci si aggiunge la ricompensa di quel passo.

La prima partita è la più corta e serve a scaldarsi. Da \(s_1\) si arriva all’obiettivo incassando \(10\), e l’obiettivo vale \(0\): quindi da \(s_1\) in avanti si sono raccolti \(10 + 0{,}9 \times 0 = 10\). Da \(s_0\), un passo prima, non si incassa nulla e si finisce in un posto che vale \(10\): quindi \(0 + 0{,}9 \times 10 = 9\).

Prendiamo adesso la seconda partita. Dall’ultimo \(s_1\) mancava solo il premio, quindi \(10\). Dal \(s_0\) che veniva subito prima: quel passo non paga nulla e porta in un posto che vale \(10\), quindi \(0 + 0{,}9 \times 10 = 9\). Dal primo \(s_0\): quel passo costa \(1\) e porta in un posto che vale \(9\), quindi \(-1 + 0{,}9 \times 9 = 7{,}1\).

La terza partita è più lunga e si fa allo stesso modo, sempre partendo dalla fine: l’ultimo \(s_1\) vale \(10\); il \(s_0\) prima di lui \(0 + 0{,}9 \times 10 = 9\); il \(s_1\) prima ancora costa \(1\) e porta in un posto che vale \(9\), quindi \(-1 + 0{,}9 \times 9 = 7{,}1\); e il primo \(s_0\) di tutti non paga nulla e porta in un posto che vale \(7{,}1\), quindi \(0 + 0{,}9 \times 7{,}1 = 6{,}39\).

partita	raccolto da \(s_0\) in avanti	raccolto da \(s_1\) in avanti
1	\(9\)	\(10\)
2	\(7{,}1\) la prima volta, \(9\) la seconda	\(10\)
3	\(6{,}39\) la prima volta, \(9\) la seconda	\(7{,}1\) la prima volta, \(10\) la seconda

Adesso la media, e ci sono due modi di farla. Il primo conta una riga per partita, quella della prima volta che si è passati di lì, e si chiama a prima visita: per \(s_0\) si mediano \(9\), \(7{,}1\) e \(6{,}39\), cioè \(22{,}49 : 3 = 7{,}4966\ldots\); per \(s_1\) si mediano \(10\), \(10\) e \(7{,}1\), cioè \(27{,}1 : 3 = 9{,}0333\ldots\). Il secondo conta tutte le righe, ripassaggi compresi, e si chiama a ogni visita: per \(s_0\) i numeri diventano cinque (\(9 + 7{,}1 + 9 + 6{,}39 + 9 = 40{,}49\), diviso \(5\) fa \(8{,}098\)) e per \(s_1\) quattro (\(10 + 10 + 7{,}1 + 10 = 37{,}1\), diviso \(4\) fa \(9{,}275\)). Da qui in avanti li scriveremo arrotondati alla seconda cifra, \(7{,}50\) e \(9{,}03\) da una parte, \(8{,}10\) e \(9{,}28\) dall’altra, ma i numeri veri sono questi.

Superiore

I ritorni si calcolano all’indietro, che è il modo economico di farlo: partendo dalla fine, \(G \leftarrow r + \gamma\,G\) a ogni passo indietro. Nel secondo episodio, per esempio: dall’ultimo \(s_1\) il ritorno è \(10\); dal secondo \(s_0\) è \(0 + 0{,}9 \times 10 = 9\); dal primo \(s_0\) è \(-1 + 0{,}9 \times 9 = 7{,}1\).

episodio	ritorni osservati
1	\(G(s_0) = 9\); \(G(s_1) = 10\)
2	\(G(s_0) = 7{,}1\), poi \(G(s_0) = 9\); \(G(s_1) = 10\)
3	\(G(s_0) = 6{,}39\), poi \(G(s_0) = 9\); \(G(s_1) = 7{,}1\), poi \(G(s_1) = 10\)

Adesso la media. A prima visita si conta una riga per episodio:

\[ V(s_0) = \frac{9 + 7{,}1 + 6{,}39}{3} = \frac{22{,}49}{3} \simeq 7{,}50, \qquad V(s_1) = \frac{10 + 10 + 7{,}1}{3} = \frac{27{,}1}{3} \simeq 9{,}03 . \]

A ogni visita entrano tutte le righe, cinque per \(s_0\) e quattro per \(s_1\):

\[ V(s_0) = \frac{9 + 7{,}1 + 9 + 6{,}39 + 9}{5} = 8{,}098, \qquad V(s_1) = \frac{10 + 10 + 7{,}1 + 10}{4} = 9{,}275 . \]

Per ogni casella sono usciti due numeri diversi dagli stessi identici dati, ed entrambi sono legittimi: sono due modi di stimare la stessa cosa, e nella pratica si usano tutti e due. Quello a prima visita è il più facile da giustificare: ogni partita porta un numero solo, e numeri che vengono da partite diverse non si influenzano a vicenda, che è esattamente la condizione in cui fare una media è la cosa giusta da fare. Quello a ogni visita conta anche i ripassaggi, quindi butta via meno dati, e non obbliga a tenere il conto di dove si è già passati; e si estende meglio a quando il quaderno viene sostituito da una rete neurale, che è la situazione del capitolo successivo. Con tante partite la scelta non cambia il risultato, perché tutti e due finiscono sul valore vero.

Tutti e quattro i numeri, però, restano sotto quelli che la sezione precedente aveva calcolato sullo stesso mondo, che erano \(9\) per \(s_0\) e \(10\) per \(s_1\): là si calcolava il valore della strategia migliore possibile, qui si misura quello della strategia che ha giocato davvero, tentennamenti compresi. Sono due domande diverse, e la seconda non può avere una risposta più alta della prima: i valori veri, però, non le medie su tre partite, che possono anche sballare per eccesso. Una media si assesta sul valore vero quando i casi mediati sono tanti, e tre non lo sono.

gamma = 0.9

# Ogni episodio e' una lista di (stato, ricompensa incassata subito dopo).
episodi = [
    [("s0", 0.0), ("s1", 10.0)],
    [("s0", -1.0), ("s0", 0.0), ("s1", 10.0)],
    [("s0", 0.0), ("s1", -1.0), ("s0", 0.0), ("s1", 10.0)],
]

def ritorni(episodio):
    """Ritorni G_t, calcolati all'indietro: G <- r + gamma * G."""
    G, fuori = 0.0, []
    for stato, r in reversed(episodio):
        G = r + gamma * G
        fuori.append((stato, G))
    return list(reversed(fuori))

def monte_carlo(episodi, prima_visita=True):
    somma, conteggio = {}, {}
    for episodio in episodi:
        visti = set()
        for stato, G in ritorni(episodio):
            if prima_visita and stato in visti:
                continue           # a prima visita: le repliche non contano
            visti.add(stato)
            somma[stato] = somma.get(stato, 0.0) + G
            conteggio[stato] = conteggio.get(stato, 0) + 1
    return {s: somma[s] / conteggio[s] for s in somma}

print(monte_carlo(episodi, prima_visita=True))
# {'s0': 7.496666666666667, 's1': 9.033333333333333}
print(monte_carlo(episodi, prima_visita=False))
# {'s0': 8.098, 's1': 9.275}

Nulla nel codice conosce l’ambiente: legge una lista di partite già giocate. È tutta la differenza con la sezione precedente.

Dalla valutazione al controllo#

Misurare quanto vale una strategia è metà del lavoro; l’altra metà si chiama controllo, ed è trovarne una migliore. Si riusa lo schema della pagella della sezione precedente: si misura, poi in ogni situazione si tiene la mossa che secondo quelle misure rende di più (si dice che la strategia si rende greedy, cioè avida: prende sempre quello che al momento sembra il meglio), e si ricomincia da capo con la strategia nuova. Con una differenza che sembra un dettaglio tecnico e invece è il tema di tutto il capitolo.

Elementare

C’è una trappola. Se l’agente, dopo aver imparato che una certa mossa è buona, la gioca sempre, le altre mosse non le prova più. E se non le prova più, non scoprirà mai che una di quelle era migliore: il suo voto resterà per sempre quello sbagliato del primo tentativo. Il quaderno delle medie ha una colonna che non si aggiorna più.

Per questo un agente Monte Carlo che vuole migliorare (e non solo misurare) deve continuare a fare mosse che non crede ottime. È lo stesso dilemma fra esplorare e sfruttare che la sezione sulle leve aveva isolato in apertura di capitolo, e qui si presenta nella forma più cruda: senza esplorazione, il metodo semplicemente non vede i dati che gli servirebbero.

Ci sono due modi di tenere aperte le altre mosse. Uno è cominciare ogni partita da una situazione e da una mossa sorteggiate, così che prima o poi tocchi a tutte le combinazioni: negli scacchi si può fare, basta disporre i pezzi come si vuole, mentre su un’automobile o su un impianto no, perché la giornata comincia dove comincia e non la si può apparecchiare. L’altro funziona dappertutto: tenere da parte una quota di mosse tirate a sorte, nove volte su dieci la mossa che il quaderno dice migliore e una volta su dieci una qualunque, anche quella che sembra sciocca.

Quella quota si paga. Un giocatore che una mossa su dieci la tira a sorte non giocherà mai la partita perfetta: arriva al meglio fra i giocatori che ogni tanto tirano a sorte, e quel meglio sta sotto al meglio in assoluto. Smettere di sorteggiare per giocare perfetto lo riporterebbe al punto di partenza, cieco su tutto quello che non prova. Una via d’uscita c’è: farsi portare le partite da qualcuno che tira a sorte, e usarle per giudicare un giocatore che invece non tira mai.

Superiore

Il problema è che \(Q^\pi(s,a)\) si può stimare solo per le coppie \((s,a)\) che compaiono nei dati, e una policy deterministica ne genera una sola per stato. Ci sono due rimedi classici.

Il primo è l’ipotesi degli inizi esplorativi: ogni episodio comincia da una coppia \((s,a)\) estratta a caso, con probabilità non nulla per tutte. È comoda nella teoria e quasi sempre inapplicabile, perché richiede di poter piazzare l’agente dove si vuole.

Il secondo, praticabile, è restare su policy \(\varepsilon\)-soft, cioè con \(\pi(a\mid s) \ge \varepsilon/|\mathcal{A}|\) per ogni azione: la \(\varepsilon\)-greedy già vista sui bandit è il caso tipico. Il policy improvement theorem continua a valere ristretto a questa classe, quindi l’alternanza valuta-migliora converge, ma converge alla migliore policy \(\varepsilon\)-soft, non alla migliore in assoluto [SB18].

La rinuncia è reale, e la via d’uscita è separare la policy che genera i dati da quella che si sta valutando.

Imparare da una policy e giudicarne un’altra#

Ci sono due strategie in gioco: quella che vogliamo giudicare e quella che ha davvero giocato le partite che abbiamo in mano. Se sono la stessa, cioè se si impara giocando in proprio, si dice che si sta lavorando on-policy, ed è il caso di tutto quello che abbiamo visto finora. Se sono diverse si è off-policy, «fuori dalla propria strategia», ed è la situazione interessante: imparare da un archivio di partite giocate da altri, da un programma di controllo che c’era già, da un esperto umano, oppure da una versione precedente di sé stessi.

Elementare

Cento fogli di partita su uno scaffale, tutti dello stesso socio del circolo, uno che non rischia mai. Vuoi sapere come se la caverebbe uno spericolato, che lì non ha mai giocato: in quell’archivio le partite che lui avrebbe giocato sono pochissime, e la media dei cento fogli dà il voto al prudente.

Allora si va foglio per foglio, scrivendo accanto a ognuno quanto conta. Vale molto la partita che lo spericolato avrebbe giocato spesso e il prudente quasi mai, rara e istruttiva; vale poco o niente quella tipica del prudente, che l’altro non farebbe mai. Quel numero è il peso, il rapporto fra quanto era probabile quella sequenza di mosse per l’uno e per l’altro (in inglese importance sampling: si campiona tenendo conto di quanto ogni caso conta). Una mossa che il prudente non ha mai provato non lascia fogli, e nessun peso li inventa.

Sul foglio non c’è solo quello che i giocatori decidono: il dado che rotola, la carta che esce, l’avversario che sbaglia sono capitati una volta sola, identici per tutti e due, e nella frazione stanno sopra e sotto e si cancellano. Nel peso resta la sola parte scelta, e per questo non serve sapere niente di come funziona il gioco.

Prendi un foglio di tre mosse. Il prudente sceglieva fra due mosse tirando una monetina, lo spericolato sa sempre quale vuole, e la monetina ha indovinato la sua tutte e tre le volte. Lui quella partita l’avrebbe giocata sempre, una volta su una; il prudente ci è arrivato per fortuna, una volta su due a ogni mossa, cioè \(\frac12 \times \frac12 \times \frac12 = \frac18\), una volta su otto. Il peso è \(1\) diviso \(\frac18\), cioè \(8\): quel foglio conta otto volte tanto.

Se a metà foglio la monetina ha scelto una mossa che lo spericolato non farebbe mai, il peso va a zero, e a perderci è il pezzo scritto prima: quelle righe contano anche i punti presi dopo la mossa storta, che lui non avrebbe mai visto. Il seguito si salva: la mossa storta è alle spalle, e da lì si riprende a contare. Bastano poche mosse perché i pesi diventino minuscoli o enormi, ed è il guaio del metodo: sui fogli corti riesce, su quelli lunghi traballa.

I pesi ballano, e allora conta anche come fai la media. Su dieci fogli uno pesa otto e nove pesano zero. Somma i punti pesati e dividi per dieci, cioè per i fogli che hai in mano: il voto esce tutto da quell’unico foglio, e col peso a mille invece che a otto verrebbe cento volte i punti di quella partita. Dividi per la somma dei pesi, otto in tutto, e il voto cade per forza fra il punteggio peggiore e il migliore che hai letto. Il primo modo azzecca in media il valore giusto già con pochi fogli, ma quell”«in media» può nascondere oscillazioni enormi; il secondo lo sbaglia un po’ e non impazzisce mai, ed è quello che si sceglie quasi sempre.

Superiore

Nelle formule la policy da valutare si chiama \(\pi\) (target) e quella che ha generato i dati \(b\) (behavior, di comportamento).

La condizione di buon senso si chiama copertura: \(\pi(a\mid s) > 0\) deve implicare \(b(a\mid s) > 0\). Ne segue che \(b\) deve essere stocastica dove differisce da \(\pi\), mentre \(\pi\) può tranquillamente essere deterministica (ed è il caso che interessa nel controllo, dove \(\pi\) è la greedy).

Il peso è il rapporto di importance sampling. La probabilità della traiettoria \(A_t, S_{t+1}, \dots, S_T\) sotto una policy è il prodotto dei termini \(\pi(A_k\mid S_k)\,P(S_{k+1}\mid S_k, A_k)\), e nel rapporto fra le due policy accade la cosa che rende il metodo praticabile:

\[ \rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k\mid S_k)\,P(S_{k+1}\mid S_k,A_k)} {b(A_k\mid S_k)\,P(S_{k+1}\mid S_k,A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k\mid S_k)}{b(A_k\mid S_k)} . \]

Le probabilità di transizione si cancellano, identiche a numeratore e denominatore. Il correttore non dipende dall’MDP, che infatti non conosciamo: dipende solo dalle due policy e dalle azioni osservate. È il motivo per cui l’off-policy è possibile senza modello.

Poiché \(\mathbb{E}_b\big[\rho_{t:T-1}\,G_t \mid S_t = s\big] = V^\pi(s)\) (il pedice non è pignoleria: l’attesa è sulle traiettorie generate da \(b\), ed è tutto il punto), si può stimare in due modi. L’importance sampling ordinario fa la media semplice dei ritorni pesati; quello pesato normalizza per la somma dei pesi:

\[ V_{\text{ord}}(s) = \frac{\sum_{t\in\mathcal{T}(s)} \rho_{t:T-1}\,G_t}{|\mathcal{T}(s)|}, \qquad V_{\text{pes}}(s) = \frac{\sum_{t\in\mathcal{T}(s)} \rho_{t:T-1}\,G_t} {\sum_{t\in\mathcal{T}(s)} \rho_{t:T-1}} . \]

Il compromesso fra i due è una lezione statistica che vale oltre il RL, e si enuncia a prima visita. L’ordinario è non distorto ma la sua varianza può essere illimitata, perché un rapporto può valere dieci o mille e moltiplicare un singolo ritorno per quella cifra. Il pesato è distorto (la distorsione svanisce al crescere dei campioni) ma il peso di un singolo ritorno non supera mai \(1\) e, purché i ritorni siano limitati, la sua varianza converge a zero anche quando quella dei rapporti è infinita: un risultato del 2001 di Precup, Sutton e Dasgupta. A ogni visita sono distorti tutti e due, e per la ragione già vista, il denominatore aleatorio. In pratica si preferisce quasi sempre il pesato [SB18].

Un esempio piccolo rende concreto il numero. Supponiamo che \(b\) scelga fra due azioni tirando una moneta (\(b(a\mid s) = 0{,}5\) per entrambe) e che \(\pi\) sia deterministica. Una partita di tre mosse in cui \(b\) ha per caso scelto ogni volta l’azione che anche \(\pi\) avrebbe scelto ha peso

\[ \rho = \frac{1}{0{,}5}\cdot\frac{1}{0{,}5}\cdot\frac{1}{0{,}5} = 8 . \]

Per \(\pi\) quella traiettoria è otto volte più probabile che per \(b\), e quindi conta otto volte tanto. Se invece a un certo punto \(b\) ha scelto un’azione che \(\pi\) non sceglierebbe mai, ogni prodotto che contiene quella mossa vale \(0\): escono dal conto le visite che la precedono, mentre quelle successive continuano a pesare, perché il loro prodotto comincia più tardi. Si vede subito anche il difetto: bastano poche mosse perché i pesi diventino minuscoli o enormi, ed è il motivo per cui l’off-policy su traiettorie lunghe è fragile.

Pesare così le partite di un altro è uno degli attrezzi più riusati del reinforcement learning, e ricompare in tre punti.

Dove ritorna

Nel PPO (Proximal Policy Optimization), uno degli algoritmi più usati del capitolo successivo, il peso è il rapporto fra quanto la strategia nuova e quella che ha raccolto i dati avrebbero giocato la stessa mossa: lo stesso oggetto di qui, calcolato su una mossa sola invece che su tutta la partita. E siccome un peso che esplode è il difetto appena visto, PPO gli mette attorno una fascia, sopra e sotto, oltre la quale il peso viene tosato (clipping).
Nell’offline RL, cioè imparare da un archivio di partite senza poterne giocare altre, quell’archivio è tutto ciò che c’è: la condizione appena vista (deve contenere tutto quello che la strategia da giudicare potrebbe fare) diventa il problema centrale della sezione sull’offline RL.
Nell’RLHF (Reinforcement Learning from Human Feedback), il modo in cui gli assistenti conversazionali imparano dai giudizi delle persone su quale di due risposte sia migliore, il programma che si sta migliorando si allontana passo dopo passo da quello che aveva prodotto le risposte giudicate: è la stessa deriva fra chi ha giocato e chi si giudica, tenuta a bada dallo stesso rapporto e da una regola in più: al programma che si sta migliorando vengono tolti punti quanto più le sue risposte si allontanano da quelle del programma di partenza, così che non possa cambiare troppo in fretta.

Il ponte verso le differenze temporali#

Restano due difetti, e sono quelli che la prossima sezione viene a risolvere.

Il primo è che bisogna arrivare alla fine. Un metodo Monte Carlo non aggiorna niente finché l’episodio non termina, il che lo esclude dai compiti continui (un impianto che non si spegne mai, un agente che non muore) e lo rende lento quando gli episodi sono lunghi.

Il secondo è che i numeri ballano. Il ritorno di una singola partita è la somma di molte ricompense, ognuna con la sua dose di caso: in media è giusto, ma preso una volta sola può capitare lontanissimo dal vero, e servono molti episodi perché la media si assesti. Quanto ballano lo misura la varianza, cioè quanto i valori si sparpagliano attorno alla loro media.

L’idea che li risolve entrambi è di una semplicità irritante: invece di aspettare il ritorno vero, usare la ricompensa del prossimo passo più la stima già disponibile della situazione in cui si finisce. Si aggiorna subito, e si sostituisce una somma rumorosa di molti termini con un termine osservato e una stima sola. Usare una propria stima per aggiornarne un’altra ha un nome, bootstrapping (alla lettera «tirarsi su per i lacci delle scarpe»), e ha un costo: la stima presa come bersaglio può essere sbagliata, e allora la correzione tira nella direzione sbagliata. E non tira a caso, tira sempre dalla stessa parte, almeno finché le stime non si assestano: nel labirinto tutte le caselle partono da zero, che è meno del loro valore vero, quindi ogni bersaglio costruito su di esse è più basso del vero, e ogni correzione tira più in basso di quanto dovrebbe. Un errore che ha un verso non si cancella facendo la media di tante correzioni, e per questo ha un nome suo, la distorsione; è il prezzo di non aspettare la fine: numeri molto più stabili, appoggiati però a un bersaglio che potrebbe non essere quello giusto. Nasce così l’apprendimento per differenze temporali, in inglese temporal-difference, che tutti abbreviano in TD.

Le tre famiglie si dispongono allora su due assi, ed è la mappa da tenere a mente per tutto il resto del capitolo:

	quanto guarda avanti	serve la mappa dell’ambiente?	si corregge appoggiandosi alle proprie stime (bootstrapping)
Programmazione dinamica	un passo, su tutte le caselle in cui si può finire	sì	sì
Monte Carlo	fino alla fine, su una partita sola	no	no
Differenze temporali	un passo, su una partita sola	no	sì

In quella tabella manca una riga, ed è quella in mezzo: guardare avanti non un passo solo e nemmeno fino alla fine, ma due passi, o tre, o dieci. È una manopola vera e non una possibilità teorica, che va con continuità dalle differenze temporali pure al Monte Carlo puro; la fine della prossima sezione è dedicata a lei.

Elementare

Da ricordare

Un metodo Monte Carlo stima quanto vale una situazione nel modo più diretto che ci sia: si giocano molte partite intere, e per ogni situazione attraversata ci si segna sul quaderno quanto si è raccolto da lì in avanti. Il valore è la media di quelle righe. Nessuna mappa dell’ambiente, solo partite giocate fino in fondo.
Rispetto al metodo della sezione precedente cambia che cosa bisogna sapere: quello guarda un passo avanti in tutte le direzioni possibili e pretende la mappa dell’ambiente, Monte Carlo guarda in una direzione sola ma fino in fondo e non pretende niente. Basta saper giocare, non saper descrivere il gioco. E se interessano poche situazioni, si giocano partite solo da quelle, senza passare in rassegna tutte le altre.
Le medie si possono fare in due modi, contando una riga per partita (la prima volta che si è passati di lì) oppure contandole tutte, ripassaggi compresi. Danno numeri un po’ diversi, sono tutti e due legittimi, e con tante partite finiscono nello stesso posto.
Ogni situazione si giudica per conto suo, su quello che è successo davvero: un voto sbagliato non contagia le caselle vicine, perché nessuno lo usa per calcolare il proprio. Il prezzo sono i due difetti dichiarati fin dall’inizio: i numeri ballano parecchio (una partita sola è una somma di tanti colpi di fortuna) e non si scrive niente finché la partita non è finita.
Per migliorare la strategia, e non solo misurarla, l’agente deve continuare a giocare mosse che non crede le migliori: se non le prova più, quella colonna del quaderno resta per sempre al voto sbagliato del primo tentativo. E si paga: chi tira a sorte una mossa su dieci arriva al meglio fra i giocatori che tirano a sorte, che sta sotto al meglio in assoluto.
Si può giudicare una strategia con partite giocate da un’altra, purché le si pesi invece di contarle tutte uguali: una partita che la strategia da giudicare avrebbe giocato spesso e l’altra di rado conta molto, una che la prima non farebbe mai non conta niente. Il peso è solo il rapporto fra quanto erano probabili quelle mosse per l’una e per l’altra, e per questo non serve sapere nulla dell’ambiente. Serve però che l’archivio contenga tutto ciò che la strategia da giudicare potrebbe fare.
I pesi però sono fragili: bastano poche mosse perché diventino minuscoli o enormi (tre mosse tirate a sorte e indovinate pesano già otto volte tanto, e una sola mossa che la strategia da giudicare non farebbe mai cancella dal conto tutto il tratto di partita che la precede). Giudicare le partite di un altro funziona bene sulle partite corte, e diventa traballante su quelle lunghe.

Superiore

Da ricordare

Un metodo Monte Carlo stima il valore di uno stato come media dei ritorni osservati partendo da lì: nessun modello dell’ambiente, solo episodi giocati fino in fondo.
A prima visita conta un ritorno per episodio, è non distorto e il suo errore cala come \(1/\sqrt{n}\); a ogni visita li conta tutti ed è distorto per \(n\) finito. Convergono tutti e due.
Non c’è bootstrapping: il bersaglio è il ritorno vero, quindi le stime non si contaminano fra loro, ma hanno varianza alta e arrivano solo a episodio finito.
Per migliorare una policy, e non solo misurarla, serve esplorazione: inizi esplorativi (teorici) o policy \(\varepsilon\)-soft (pratiche), che però fanno convergere alla migliore policy \(\varepsilon\)-soft, non alla migliore in assoluto.
L’importance sampling permette di valutare una policy \(\pi\) con dati generati da un’altra policy \(b\), pesando le traiettorie con \(\rho = \prod \pi(a_k\mid s_k)/b(a_k\mid s_k)\). Le probabilità di transizione si cancellano, quindi non serve il modello. Serve la copertura.
La variante pesata dell’importance sampling è distorta ma molto più stabile di quella ordinaria, e in pratica si preferisce.