Reinforcement Learning: imparare per tentativi#
Nessuno insegna a un bambino a camminare elencandogli la sequenza esatta di contrazioni muscolari. Il bambino ci prova, oscilla, cade, si rialza, fa un passo e cade di nuovo. Ogni tentativo il mondo gli restituisce un giudizio implicito (un tonfo doloroso oppure un metro guadagnato verso il divano) e settimana dopo settimana quel giudizio scolpisce un modo di muoversi che nessun manuale ha mai descritto. Questo è, in una frase, il reinforcement learning (apprendimento per rinforzo, spesso abbreviato in RL): imparare a comportarsi non da esempi già etichettati, ma dalle conseguenze delle proprie azioni.
Agente, ambiente, ricompensa#
Tre ingredienti bastano, e non ne servono altri. C’è un agente, cioè chi decide (il bambino, un robot, un programma che gioca a scacchi). C’è un ambiente, cioè tutto il resto: il mondo che l’agente non controlla ma con cui interagisce. E c’è una ricompensa, un numero che l’ambiente restituisce per dire «bene» o «male». L’agente guarda la situazione in cui si trova (lo stato: tutto ciò che in questo istante vede del mondo), sceglie un’azione, l’ambiente passa a un nuovo stato e gli consegna una ricompensa; poi il ciclo ricomincia (Fig. 10.1). Quello che l’agente cerca di rendere più grande possibile non è la ricompensa di adesso, ma la somma di tutte quelle che verranno da qui alla fine: quella somma ha un nome, ritorno (in inglese return), e da qui in avanti la useremo continuamente.
Nella somma c’è però una regola di impazienza, perché dieci euro oggi valgono più di dieci euro l’anno prossimo: un premio lontano entra ridotto. Il taglio è sempre lo stesso a ogni passo di attesa. Se per esempio ogni attesa lascia in piedi nove decimi, un premio di dieci punti che arriva una mossa più tardi ne vale nove, due mosse più tardi otto e un decimo, e così via.
Serve anche a una cosa pratica, e questa vale la pena vederla coi numeri. Immagina una partita che non finisce mai e che paga dieci punti a ogni mossa, per sempre. Senza il taglio la somma cresce all’infinito e non vuol dire più niente. Con il taglio la somma è \(10 + 9 + 8{,}1 + 7{,}29 + \ldots\), e per quanto si vada avanti non arriva mai a \(100\): ogni pezzo nuovo è nove decimi del precedente, e quello che resta da aggiungere si assottiglia più in fretta di quanto la somma cresca. Un totale infinito diventa così un numero maneggiabile. La sezione sulle funzioni valore lo scrive per bene.
Fig. 10.1 Il ciclo di interazione del reinforcement learning: l’agente compie un’azione, l’ambiente risponde con un nuovo stato e una ricompensa, e l’anello si richiude. Accanto a ogni etichetta il disegno mette una lettera con un numeretto in basso: la lettera è l’iniziale (\(a\) per azione, \(s\) per stato, \(r\) per ricompensa) e il numeretto è il conto dei passi. L’azione la si compie al passo \(t\), lo stato nuovo e la ricompensa arrivano subito dopo, al passo \(t+1\).#
Una domanda viene prima di ogni algoritmo, e conviene togliersela subito: chi decide la ricompensa? Non l’agente, e nemmeno il mondo: la scrive chi imposta il problema. In un videogioco il punteggio esiste già e si prende quello; per un robot che deve imparare a camminare qualcuno deve stabilire che cadere vale \(-5\) e che un metro guadagnato vale \(+1\). È una scelta di progetto, ed è una scelta seria, perché un agente ottimizza esattamente i numeri che gli sono stati dati e non le intenzioni di chi glieli ha dati: premiato per la velocità, può imparare a buttarsi in avanti e cadere in fretta. Chi imposta il problema può anche aggiungere premi intermedi, per guidare l’agente invece di lasciarlo cercare a vuoto: si chiama reward shaping, «dare forma alla ricompensa». È un’arma a doppio taglio. Esiste un modo di aggiungerli che è dimostrato non cambiare quale sia la strategia migliore, e l’idea in una riga è questa: si attacca un punteggio a ogni situazione e si premia solo la differenza fra il punteggio di dove si arriva e quello di dove si era, così che un giro che torna al punto di partenza non frutti niente e nessuno possa guadagnare andando avanti e indietro. Tutti gli altri modi, che sono la maggior parte, la strategia migliore la spostano senza dirlo. Il capitolo di deep reinforcement learning ci torna per esteso, nella sezione su esplorazione e ricompensa.
La regola con cui l’agente sceglie, situazione per situazione, si chiama politica, all’inglese policy. Le due parole indicano la stessa cosa e in questo capitolo si alternano: è la sola cosa che l’agente cerca di migliorare.
Immagina un videogioco. A ogni istante vedi lo schermo (lo stato), premi un tasto (l’azione) e il gioco reagisce: nuova schermata e magari qualche punto in più o in meno (la ricompensa). L’obiettivo non è indovinare il tasto «giusto» in questo istante, ma accumulare più punti possibile fino alla fine della partita: quel totale è il ritorno, ed è il numero da cui si giudica tutto. La politica, cioè la tua abitudine di gioco («in questa schermata salto sempre»), è quello che con l’esperienza migliora.
Formalmente l’interazione è un processo decisionale di Markov (Markov Decision Process, MDP). A ogni passo \(t\) l’agente osserva lo stato \(S_t\), sceglie un’azione \(A_t\) secondo la sua politica \(\pi(a \mid s)\), e l’ambiente transita in \(S_{t+1}\) restituendo una ricompensa scalare \(R_{t+1}\) (maiuscole per le variabili aleatorie, minuscole \(s\), \(a\), \(r\) per i valori che assumono). L’obiettivo è massimizzare non la ricompensa immediata ma il ritorno (return) scontato:
Qui \(\gamma\) è il fattore di sconto: vicino a \(1\) l’agente è lungimirante e dà peso al futuro lontano; vicino a \(0\) è miope e insegue solo il premio immediato. \(\gamma < 1\) è obbligatorio nei compiti continui, che non terminano mai, perché senza sconto quella somma infinita non converge; nei compiti episodici, che finiscono da soli, la somma ha un numero finito di termini e \(\gamma = 1\) è ammesso e usatissimo. Cercare la politica ottima \(\pi^{*}\) significa massimizzare \(\mathbb{E}_\pi[G_t]\), e quasi tutti gli algoritmi lo fanno stimando funzioni di valore come \(Q^\pi(s,a) = \mathbb{E}_\pi[G_t \mid S_t=s,\, A_t=a]\), il ritorno atteso partendo da \(s\), giocando \(a\) e poi seguendo \(\pi\).
Cosa lo distingue dall’apprendimento supervisionato#
Nell’apprendimento supervisionato ogni esempio arriva con la sua risposta corretta, la sua etichetta: questa foto è un gatto, quella casa vale 300 000 euro. Il programma deve solo imparare a imitare quelle risposte. Nel reinforcement learning le risposte corrette non esistono: nessuno le conosce.
Nessuno dice mai all’agente «la mossa giusta era questa». Riceve solo una ricompensa che dice quanto è andata bene, non cosa avrebbe dovuto fare. E il punto più difficile è che la ricompensa spesso arriva tardi: negli scacchi capisci di aver sbagliato solo trenta mosse dopo, quando perdi. Quale mossa ringraziare per la vittoria? Quale incolpare per la sconfitta? Questo si chiama problema dell’assegnazione del merito (credit assignment), ed è il cuore di tutta la difficoltà.
La differenza è strutturale. Nel supervisionato i dati \((x, y)\) sono indipendenti e l’etichetta \(y\) è il segnale di errore diretto. Nel RL il segnale è una ricompensa scalare, potenzialmente ritardata e sparsa, e i dati non sono indipendenti: l’azione di adesso determina lo stato successivo, quindi la distribuzione degli esempi dipende dalla politica stessa. L’assegnazione del merito temporale si affronta con i metodi a differenza temporale (temporal-difference, TD) e con l’equazione di Bellman, che spezza il ritorno in premio immediato più valore scontato dello stato futuro:
Aggiornare \(Q\) verso il lato destro di questa uguaglianza è, in sostanza, ciò che fanno Q-learning e le sue versioni profonde.
Il dilemma esplorazione–sfruttamento#
C’è una tensione che nessun agente può ignorare, e che riconosciamo tutti.
Hai un ristorante preferito che non delude mai. Provi quello nuovo appena aperto o resti sul sicuro? Se scegli sempre il noto (sfruttamento), non scoprirai mai un posto migliore. Se provi sempre cose nuove (esplorazione), sprechi serate in locali mediocri. Un buon agente fa entrambe le cose: sfrutta ciò che sa quasi sempre, ma ogni tanto azzarda, perché solo azzardando può scoprire ricompense che non sospettava.
Questa ricetta ha un nome che ritornerà in ogni sezione del capitolo: \(\varepsilon\)-greedy, che si legge «epsilon-greedy». Greedy è l’inglese per «avido», cioè chi prende sempre quello che al momento sembra il meglio; ed \(\varepsilon\) (epsilon) è la piccola probabilità con cui invece si azzarda, per esempio una volta su dieci.
Il compromesso si formalizza con strategie come \(\varepsilon\)-greedy: con probabilità \(1-\varepsilon\) l’agente sceglie l’azione stimata migliore, con probabilità \(\varepsilon\) ne prende una a caso.
In pratica \(\varepsilon\) parte alto e decresce nel tempo: si esplora molto all’inizio, quando le stime di \(Q\) sono grezze, e si sfrutta sempre di più man mano che diventano affidabili. Approcci più raffinati (softmax, Upper Confidence Bound, bonus di curiosità) dosano l’esplorazione in base all’incertezza invece che a caso.
Tre tappe che hanno fatto la storia#
Il RL non è un’idea nuova, ma ha avuto pochi momenti che ne hanno mostrato la potenza. Nei primi anni Novanta, all’IBM, Gerald Tesauro costruì TD-Gammon, un programma che imparò a giocare a backgammon (il gioco da tavolo con le pedine e i dadi) quasi al livello dei campioni umani. Il metodo con cui imparava è quello che l’ultima sezione di questo capitolo racconta per esteso: a ogni mossa il programma si fa un’idea di come andrà a finire, e alla mossa dopo corregge un poco l’idea di prima. Le partite se le giocò da solo, oltre un milione, muovendo da tutte e due le parti: nessuno gli diceva quale fosse la mossa buona, ma alla fine uno dei due lati aveva vinto, e quel giudizio bastava per capire quali idee erano da rivedere. Ne uscirono aperture che i maestri poi adottarono.
Nel 2015 DeepMind, un laboratorio londinese, pubblicò su Nature, una delle riviste scientifiche più importanti che esistano, il DQN. Era un agente che imparava a giocare a decine di videogiochi della vecchia console Atari partendo dai soli pixel dello schermo e dal punteggio, senza sapere nulla delle regole. Le tre lettere del nome stanno per Deep Q-Network: la Q è il voto che l’agente dà a ogni mossa, ed è il filo di tutto questo capitolo; network è la rete neurale che quel voto lo indovina; deep, «profonda», è come si chiamano le reti a molti strati dei capitoli precedenti. Il capitolo prossimo lo smonta pezzo per pezzo. E nel marzo 2016 AlphaGo batté 4-1 il campione Lee Sedol al Go, il gioco orientale in cui si posano pietre bianche e nere sugli incroci di una griglia: era considerato fuori portata per le macchine perché le posizioni possibili sono troppe per elencarle (quante di preciso lo dice la sezione sulle funzioni valore), e molti davano quel risultato lontano un decennio.
Come è organizzato questo capitolo#
Cominciamo da una versione del problema spogliata di tutto tranne il dilemma appena descritto: i bandit a più braccia, dove la situazione non cambia mai e l’unica domanda è quale leva tirare. Poi rimettiamo al suo posto la situazione che cambia, e con essa la domanda che tiene insieme tutto il resto: quanto vale trovarsi in un certo punto, cioè quanti punti ci si può aspettare di raccogliere da lì in avanti.
Dopo i bandit restano tre sezioni, e sono tre risposte a quella domanda, in ordine di quanto pretendono di sapere. La prima pretende la mappa del mondo, e con la mappa in mano calcola quei valori senza giocare nemmeno una partita. La seconda non pretende niente: gioca partite intere e fa la media di com’è andata. La terza non aspetta nemmeno la fine della partita e corregge a ogni mossa, ed è la strada dell’algoritmo più famoso del campo, il Q-learning. Tutte e tre riempiono la stessa cosa: una grande tabella con una casella per ogni situazione.
Il passo verso il deep reinforcement learning, dove reti neurali stimano quei valori o direttamente la politica, non è un ampliamento facoltativo: è una necessità, perché la tabella smette di stare in piedi appena le situazioni possibili sono tante, e va sostituita da qualcosa che sappia indovinare il valore di situazioni mai viste prima. Lo affrontiamo nel capitolo successivo, ricostruendo proprio il tipo di agente che ha imparato a giocare a partire dai pixel. L’obiettivo non è collezionare sigle, ma capire un’unica idea da tutte le angolazioni: come si impara a decidere quando l’unico maestro è l’esperienza.
Da ricordare
Servono tre cose e basta: qualcuno che decide (l’agente), un mondo che risponde (l’ambiente) e un punteggio che dice se è andata bene o male (la ricompensa). Si agisce, il mondo cambia e paga, si ricomincia.
Nessuno dice mai qual era la mossa giusta: il punteggio dice quanto è andata bene, non cosa si doveva fare. E spesso arriva tardi, molte mosse dopo quella che lo ha meritato: capire chi ringraziare è la difficoltà centrale.
Quel che si vuole rendere grande non è il punteggio del momento ma il totale da qui alla fine (il ritorno), con una regola di impazienza: un premio lontano conta meno di uno vicino.
Chi decide i punti è chi imposta il problema, non il mondo: numeri scelti male insegnano il comportamento sbagliato.
Bisogna sempre scegliere fra tornare dove si sa che si sta bene e provare qualcosa di nuovo (il dilemma del ristorante): quasi sempre il noto, ogni tanto una prova a caso.
Tre risultati che hanno fatto la storia: TD-Gammon a backgammon, DQN sui vecchi videogiochi Atari, AlphaGo al Go nel 2016.
Da ricordare
Il RL si regge su tre elementi: un agente che decide, un ambiente che risponde, una ricompensa che valuta. Il ciclo azione → nuovo stato + ricompensa si ripete.
A differenza del supervisionato non ci sono etichette, ma un segnale scalare spesso ritardato: da qui il problema dell’assegnazione del merito.
L’obiettivo è massimizzare il ritorno scontato \(G_t\), non la ricompensa immediata; il fattore \(\gamma\) regola quanto conta il futuro ed è obbligatoriamente \(<1\) solo nei compiti continui.
Ogni agente deve bilanciare esplorazione e sfruttamento (per esempio con \(\varepsilon\)-greedy).
La funzione di ricompensa è una scelta di progetto, non un dato dell’ambiente: l’agente ottimizza ciò che è scritto, non ciò che si intendeva.
Tappe simbolo: TD-Gammon (backgammon), DQN sui giochi Atari, AlphaGo (Go, 2016).