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 riuscisse, cioè che le carte andassero tutte a posto. Provò a calcolarla con la combinatoria, contando tutti i modi in cui le carte si possono disporre, 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 si è fermata la sezione sugli MDP. 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’è, c’è 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 sugli MDP: 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 è un’attesa, il ritorno medio partendo da lì, e un’attesa si stima con la media campionaria: tanti casi indipendenti, e la loro media. Qui i casi sono i ritorni osservati nelle 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. È il conteggio che nel capitolo sulla ricerca prendeva il posto del giudizio sulle posizioni del Go; là le mosse si tiravano a caso, qui le gioca l’agente con le sue abitudini, e la media dice quanto vale la posizione per lui.

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, perché l’oscillazione cala come la radice quadrata del numero di partite, e la radice di quattro è due. Con cento partite il numero balla ancora parecchio, e per farlo ballare la metà ce ne vogliono quattrocento, non duecento.

Nessuna riga del quaderno si appoggia a un’altra stima: ognuna è 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). Come sui bandit, la media si tiene in forma incrementale, e con un passo costante \(\alpha\) al posto di \(1/n\) diventa \(V(S_t) \leftarrow V(S_t) + \alpha\,[\,G_t - V(S_t)\,]\), applicata a fine episodio per ogni visita contata: è il constant-α MC, cioè la stessa forma dell’aggiornamento TD con il ritorno intero \(G_t\) come bersaglio.

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 sugli MDP (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 farà da nome collettivo per le 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 partita realmente giocata, 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 varianza, cioè in quanto i ritorni si sparpagliano attorno alla loro media: il ritorno di una partita è la somma di molte ricompense, ognuna con la sua parte di caso, e due partite dalla stessa situazione danno ritorni diversi.

Da questa differenza discendono tre conseguenze pratiche.

Monte Carlo funziona anche quando l’ambiente è una scatola nera, di cui si vede che cosa entra e che cosa esce ma non come funziona dentro, 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. 13.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 . \]

Gli stessi identici dati danno due numeri diversi per ogni casella. 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, le partite non si influenzano fra loro, e la media di numeri indipendenti presi tutti dalla stessa distribuzione si avvicina al valore vero quante più partite si giocano. 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. 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 sugli MDP 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 il valore vero di una strategia qualsiasi non supera mai quello della migliore. Le medie su tre partite, invece, possono sbagliare in tutti e due i versi, anche verso l’alto: si assestano sul valore vero quando i casi mediati sono tanti, e tre non lo sono.

gamma = 0.9

# Ogni episodio è 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))
print(monte_carlo(episodi, prima_visita=False))

{'s0': 7.496666666666667, 's1': 9.033333333333333}
{'s0': 8.098, 's1': 9.275}

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

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 policy iteration della sezione sugli MDP: si valuta, poi in ogni situazione si tiene la mossa che secondo quelle valutazioni 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. Senza la mappa, però, cambiano due cose. I valori delle caselle non bastano più a scegliere: per confrontare le mosse bisognerebbe sapere dove porta ciascuna, cioè proprio la mappa che manca, e allora si stimano direttamente i valori delle mosse, la \(Q^\pi(s,a)\) della sezione sugli MDP. E il valore di una mossa si stima soltanto se quella mossa viene giocata.

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 (si chiamano inizi esplorativi): 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. E anche dove si può, la teoria è meno solida di quanto sembri. Che l’alternanza valuta-migliora, fatta episodio per episodio, non possa fermarsi su una policy subottima si vede in una riga: se si fermasse, i valori tenderebbero a quelli di quella policy, e il miglioramento la cambierebbe. Ma può non fermarsi affatto. Sutton e Barto indicano la convergenza come una delle questioni teoriche aperte più importanti della materia [SB18], e la risposta dipende da come si sorteggiano gli inizi: se li si sceglie in modo arbitrario, purché ogni coppia torni infinite volte, esiste un controesempio in cui l’alternanza non converge [BT96]; con il ritorno scontato e ogni coppia che apre gli episodi con la stessa frequenza, la convergenza all’ottimo è dimostrata [Tsi02], e fuori da questi casi resta una domanda.

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 davanti a due mosse buone tira una monetina. Vuoi sapere come se la caverebbe un altro giocatore, uno deciso che sa sempre quale mossa vuole e che lì non ha mai giocato: in quell’archivio le partite che lui avrebbe giocato sono poche, e la media dei cento fogli dà il voto al socio della monetina, non a lui.

Allora si va foglio per foglio, scrivendo accanto a ognuno quanto conta. Vale molto la partita che il giocatore deciso avrebbe giocato spesso e il socio di rado, rara e istruttiva; vale poco o niente quella tipica del socio, che l’altro non giocherebbe 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 socio 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 socio sceglieva fra due mosse tirando la monetina, il giocatore deciso 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 socio 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 il giocatore deciso non farebbe mai, da lì in poi la partita non è più una delle sue. Le righe scritte prima di quella mossa si buttano: ciascuna conta i punti fino alla fine, compresi quelli venuti dopo la mossa storta, che lui non avrebbe mai incassato. Le righe scritte dopo invece si salvano, perché cominciano quando la mossa storta è già alle spalle, e da lì in avanti la partita può essere ancora una delle sue. 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. Sotto una policy, la probabilità della traiettoria \(A_t, S_{t+1}, \dots, S_T\) (dove \(T\) è l’istante in cui finisce l’episodio che contiene \(t\)) è 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.

Il peso fa un cambio di misura. Dette \(P_b(\tau)\) e \(P_\pi(\tau)\) le probabilità di una traiettoria \(\tau\) da \(S_t = s\) in poi sotto le due policy, per come è fatto il rapporto vale \(P_\pi(\tau) = \rho(\tau)\, P_b(\tau)\), e quindi

\[ \mathbb{E}_b\big[\rho_{t:T-1}\,G_t \mid S_t = s\big] = \sum_\tau P_b(\tau)\,\rho(\tau)\,G(\tau) = \sum_\tau P_\pi(\tau)\,G(\tau) = V^\pi(s). \]

La copertura serve proprio qui: se \(\pi\) desse probabilità a traiettorie che \(b\) non genera mai, la seconda somma ne perderebbe un pezzo. E il pedice dell’attesa conta, perché l’attesa è sulle traiettorie generate da \(b\), ed è tutto il punto. Su questa identità 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, e si pone a zero quando i pesi sono tutti nulli:

\[ 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, come hanno mostrato Precup, Sutton e Dasgupta [PSD01]. 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, costruito nella sezione sul gradiente di policy, 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 disegna attorno una fascia, e quando il peso ne esce dalla parte che spingerebbe troppo l’aggiornamento non conta più del bordo (lo si «tosa», in inglese 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, e la tengono a bada lo stesso rapporto e una regola in più: al programma vengono tolti punti quanto più le sue risposte si allontanano da quelle del programma di partenza, così che non possa cambiare troppo in fretta. La racconta la sezione sul post-training.

Il ponte verso le differenze temporali#

Restano due difetti, e sono quelli che le differenze temporali vengono 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. La varianza, insomma, è alta.

L’idea che li risolve entrambi è usare, al posto del ritorno vero, la ricompensa del passo successivo più la stima già disponibile del valore 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 tiranti degli stivali», l’immagine già incontrata con il bootstrap della statistica, cioè cavarsela da soli dove servirebbe un aiuto. 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 confrontano allora su tre domande:

	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 \(n\) passi, due, o tre, o dieci. Al crescere di \(n\) si va dalle differenze temporali pure al Monte Carlo puro, e la sezione sulle differenze temporali tratta questa famiglia con i ritorni a \(n\) passi e le tracce di eleggibilità.

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 alla programmazione dinamica della sezione sugli MDP cambia che cosa bisogna sapere: quella 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, pesandole: 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 è 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). Sulle partite corte il metodo funziona bene, su quelle lunghe traballa.

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, si stimano i valori delle azioni \(Q^\pi(s,a)\), da cui la policy greedy si legge senza il modello, e 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.