Come applicare il Reinforcement Learning ai problemi di pianificazione della vita reale

Di recente, ho pubblicato alcuni esempi in cui ho creato modelli di apprendimento di rinforzo per alcuni problemi della vita reale. Ad esempio, utilizzando l'apprendimento per rinforzo per la pianificazione dei pasti basato su un budget impostato e preferenze personali.

L'apprendimento per rinforzo può essere utilizzato in questo modo per una varietà di problemi di pianificazione tra cui piani di viaggio, pianificazione del budget e strategia aziendale. I due vantaggi dell'utilizzo di RL è che tiene conto della probabilità dei risultati e ci consente di controllare parti dell'ambiente. Pertanto, ho deciso di scrivere un semplice esempio in modo che altri possano considerare come potrebbero iniziare a usarlo per risolvere alcuni dei loro problemi quotidiani o lavorativi.

Che cos'è l'apprendimento per rinforzo?

Il Reinforcement Learning (RL) è il processo di test delle azioni migliori per ogni stato di un ambiente essenzialmente attraverso tentativi ed errori. Il modello introduce una politica casuale per iniziare e ogni volta che viene intrapresa un'azione viene inviato al modello un importo iniziale (noto come ricompensa). Questo continua fino al raggiungimento di un obiettivo finale, ad es. vinci o perdi la partita, dove termina quella corsa (o episodio) e il gioco si ripristina.

Man mano che il modello subisce sempre più episodi, inizia a capire quali azioni hanno maggiori probabilità di portarci a un risultato positivo. Pertanto trova le azioni migliori in ogni dato stato, noto come politica ottimale.

Processo generale di apprendimento per rinforzo

Molte delle applicazioni RL addestrano i modelli online su un gioco o un ambiente virtuale in cui il modello è in grado di interagire ripetutamente con l'ambiente. Ad esempio, lasci che il modello esegua ripetutamente una simulazione di tic-tac-toe in modo da osservare il successo e il fallimento nel provare mosse diverse.

Nella vita reale, è probabile che non abbiamo accesso per formare il nostro modello in questo modo. Ad esempio, un sistema di consigli nello shopping online richiede il feedback di una persona per dirci se ha avuto successo o meno, e questo è limitato nella sua disponibilità in base al numero di utenti che interagiscono con il sito di shopping.

Potremmo invece disporre di dati di esempio che mostrano le tendenze degli acquisti in un periodo di tempo che possiamo utilizzare per creare probabilità stimate. Usando questi, possiamo creare quello che è noto come un processo decisionale Markov parzialmente osservato (POMDP) ​​come un modo per generalizzare la distribuzione di probabilità sottostante.

Processi decisionali di Markov parzialmente osservati (POMDP)

I processi decisionali di Markov (MDP) forniscono un quadro per modellare il processo decisionale in situazioni in cui i risultati sono in parte casuali e in parte sotto il controllo di un decisore. La caratteristica principale degli MDP è che seguono la proprietà Markov; tutti gli stati futuri sono indipendenti dal passato dato il presente. In altre parole, la probabilità di passare allo stato successivo dipende solo dallo stato corrente.

I POMDP funzionano in modo simile, tranne per il fatto che si tratta di una generalizzazione degli MDP. In breve, ciò significa che il modello non può semplicemente interagire con l'ambiente ma viene invece data una distribuzione di probabilità impostata in base a ciò che abbiamo osservato. Maggiori informazioni possono essere trovate qui. Potremmo utilizzare metodi di iterazione di valore sul nostro POMDP, ma invece ho deciso di utilizzare Monte Carlo Learning in questo esempio.

Esempio di ambiente

Immagina di essere tornato a scuola (o forse lo è ancora) e di essere in un'aula, l'insegnante ha una rigida politica in materia di spreco di carta e richiede che gli eventuali pezzi di carta di scarto debbano essere passati a lui nella parte anteriore dell'aula e posizionerà i rifiuti nel cestino (cestino).

Tuttavia, alcuni studenti della classe si preoccupano poco delle regole dell'insegnante e preferiscono risparmiarsi il disturbo di passare il foglio in classe. Invece, questi individui problematici possono scegliere di gettare la carta straccia nel cestino da una distanza. Ora questo fa arrabbiare l'insegnante e coloro che lo fanno vengono puniti.

Questo introduce un concetto di ricompensa di azione molto semplice e abbiamo un esempio di ambiente di classe come mostrato nel diagramma seguente.

Il nostro obiettivo è quello di trovare le migliori istruzioni per ogni persona in modo che il foglio raggiunga l'insegnante e venga inserito nel cestino ed eviti di essere gettato nel cestino.

Stati e azioni

Nel nostro ambiente, ogni persona può essere considerata uno stato e ha una varietà di azioni che può intraprendere con la carta straccia. Possono scegliere di passarlo a un compagno di classe adiacente, trattenerlo o alcuni possono scegliere di gettarlo nel cestino. Possiamo quindi mappare il nostro ambiente su un layout di griglia più standard come mostrato di seguito.

Questo è appositamente progettato in modo tale che ogni persona, o stato, compia quattro azioni: su, giù, sinistra o destra e ognuna avrà un risultato "vita reale" varia in base a chi ha intrapreso l'azione. Un'azione che mette la persona in un muro (incluso il blocco nero al centro) indica che la persona si tiene sulla carta. In alcuni casi, questa azione è duplicata, ma non è un problema nel nostro esempio.

Ad esempio, le azioni della persona A comportano:

  • Su = Lancia nel cestino
  • Giù = trattenere sulla carta
  • Sinistra = Passa alla persona B
  • Destra = Mantieni sulla carta

Ambiente probabilistico

Per ora, il decisore che controlla in parte l'ambiente siamo noi. Diremo a ogni persona quale azione dovrebbero intraprendere. Questa è nota come politica.

La prima sfida che devo affrontare nel mio apprendimento è capire che l'ambiente è probabilmente probabilistico e cosa significa. Un ambiente probabilistico è quando istruiamo uno stato a intraprendere un'azione ai sensi della nostra politica, c'è una probabilità associata se questo è seguito con successo. In altre parole, se diciamo alla persona A di passare la carta alla persona B, possono decidere di non seguire l'azione indicata nella nostra politica e invece gettare la carta straccia nel cestino.

Un altro esempio è se stiamo raccomandando prodotti per lo shopping online non vi è alcuna garanzia che la persona visualizzerà ciascuno di essi.

Probabilità di transizione osservate

Per trovare le probabilità di transizione osservate, dobbiamo raccogliere alcuni dati di esempio su come agisce l'ambiente. Prima di raccogliere informazioni, introduciamo una politica iniziale. Per iniziare il processo, ne ho scelto uno a caso che sembra portare a un risultato positivo.

Ora osserviamo le azioni intraprese da ciascuna persona data questa politica. In altre parole, supponiamo che ci siamo seduti sul retro della classe e abbiamo semplicemente osservato la classe e osservato i seguenti risultati per la persona A:

Azioni osservate della persona A.

Vediamo che un documento ha attraversato questa persona 20 volte; 6 volte l'hanno tenuto fermo, 8 volte lo hanno passato alla persona B e altre 6 volte l'hanno buttato nella spazzatura. Ciò significa che secondo la nostra politica iniziale, la probabilità di trattenerla o gettarla nella spazzatura per questa persona è 6/20 = 0,3 e allo stesso modo 8/20 = 0,4 per passare alla persona B. Possiamo osservare il resto della classe per raccogliere i seguenti dati di esempio:

Esito della vita reale osservato

Allo stesso modo, calcoliamo quindi le probabilità di essere la seguente matrice e potremmo usarla per simulare l'esperienza. L'accuratezza di questo modello dipenderà in larga misura dal fatto che le probabilità siano rappresentazioni vere dell'intero ambiente. In altre parole, dobbiamo assicurarci di avere un campione che sia grande e abbastanza ricco di dati.

Funzione di probabilità di transizione osservata

Banditi multi-armati, episodi, premi, ritorno e tasso di sconto

Quindi abbiamo le nostre probabilità di transizione stimate dai dati campione sotto un POMDP. Il prossimo passo, prima di introdurre qualsiasi modello, è introdurre i premi. Finora abbiamo discusso solo del risultato del passaggio finale; o il foglio viene messo nel cestino dall'insegnante e guadagna una ricompensa positiva o viene lanciato da A o M e guadagna ricompense negative. Questo premio finale che termina l'episodio è noto come Terminal Reward.

Ma c'è anche un terzo risultato che è tutt'altro che ideale; la carta viene continuamente passata in giro e non arriva mai (o impiega molto più tempo di quanto vorremmo) al cestino. Pertanto, in sintesi, abbiamo tre risultati finali

  • La carta viene messa nel cestino dall'insegnante e guadagna una ricompensa terminale positiva
  • La carta viene gettata nel cestino da uno studente e guadagna una ricompensa terminale negativa
  • La carta viene continuamente passata per la stanza o rimane bloccata sugli studenti per un periodo di tempo più lungo di quanto vorremmo

Per evitare che la carta venga gettata nel cestino, forniamo una grande ricompensa negativa, diciamo -1, e poiché l'insegnante è contento che venga messa nel cestino, si ottiene una grande ricompensa positiva, +1. Per evitare il risultato in cui viene continuamente passato nella stanza, impostiamo la ricompensa per tutte le altre azioni su un valore piccolo e negativo, diciamo -0.04.

Se lo impostiamo come un numero positivo o nullo, il modello potrebbe lasciare che la carta giri e giri poiché sarebbe meglio ottenere piccoli positivi piuttosto che rischiare di avvicinarsi al risultato negativo. Questo numero è anche molto piccolo in quanto raccoglierà un solo premio terminale ma potrebbero essere necessari molti passaggi per terminare l'episodio e dobbiamo assicurarci che, se il foglio viene inserito nel cestino, il risultato positivo non viene annullato.

Nota: le ricompense sono sempre relative l'una all'altra e ho scelto cifre arbitrarie, ma queste possono essere modificate se i risultati non sono quelli desiderati.

Sebbene nell'esempio abbiamo discusso inavvertitamente degli episodi, dobbiamo ancora definirlo formalmente. Un episodio è semplicemente le azioni che ogni documento intraprende attraverso l'aula raggiungendo il cestino, che è lo stato terminale e termina l'episodio. In altri esempi, come giocare a tic-tac-toe, questa sarebbe la fine di una partita in cui vinci o perdi.

Il documento potrebbe in teoria iniziare in qualsiasi stato e questo introduce il motivo per cui abbiamo bisogno di episodi sufficienti per garantire che ogni stato e azione siano testati abbastanza in modo che il nostro risultato non sia guidato da risultati non validi. Tuttavia, il rovescio della medaglia, più episodi introduciamo, più lungo sarà il tempo di calcolo e, a seconda della scala dell'ambiente, potremmo non avere una quantità illimitata di risorse per farlo.

Questo è noto come problema Multi-Armed Bandit; con tempo limitato (o altre risorse), dobbiamo assicurarci di testare ogni coppia stato-azione abbastanza che le azioni selezionate nella nostra politica siano, di fatto, quelle ottimali. In altre parole, dobbiamo convalidare che le azioni che ci hanno portato a buoni risultati in passato non sono per pura fortuna ma sono in effetti nella scelta corretta, e allo stesso modo per le azioni che sembrano scarse. Nel nostro esempio questo può sembrare semplice con il numero di stati che abbiamo, ma immagina se aumentiamo la scala e come questo diventi sempre più un problema.

L'obiettivo generale del nostro modello RL è selezionare le azioni che massimizzano i premi cumulativi previsti, noti come rendimento. In altre parole, il Ritorno è semplicemente la ricompensa totale ottenuta per l'episodio. Un modo semplice per calcolare questo sarebbe quello di sommare tutti i premi, incluso il premio terminale, in ogni episodio.

Un approccio più rigoroso è considerare i primi passi più importanti di quelli successivi nell'episodio applicando un fattore di sconto, gamma, nella seguente formula:

In altre parole, sommiamo tutte le ricompense ma appesantiamo i passaggi successivi di un fattore di gamma in base alla potenza di quanti passi ha impiegato per raggiungerli.

Se pensiamo al nostro esempio, l'utilizzo di un rendimento scontato diventa ancora più chiaro da immaginare poiché l'insegnante ricompenserà (o punirà di conseguenza) chiunque sia stato coinvolto nell'episodio ma ridimensionerebbe questo in base alla distanza dal risultato finale.

Ad esempio, se il documento è passato da A a B a M che lo ha lanciato nel cestino, M dovrebbe essere punito di più, quindi B per averlo passato a lui e infine alla persona A che è ancora coinvolta nel risultato finale, ma meno di M oppure B. Ciò sottolinea anche che quanto più tempo impiega (in base al numero di passaggi) per iniziare in uno stato e raggiungere il cestino, tanto meno verrà premiato o punito, ma accumulerà ricompense negative per compiere più passaggi.

Applicazione di un modello al nostro esempio

Poiché l'ambiente di esempio è piccolo, possiamo applicare ciascuno di essi e mostrare alcuni dei calcoli eseguiti manualmente e illustrare l'impatto della modifica dei parametri.

Per qualsiasi algoritmo, dobbiamo prima inizializzare la funzione del valore di stato, V (s), e abbiamo deciso di impostare ciascuno di questi su 0 come mostrato di seguito.

Successivamente, lasciamo che il modello simuli l'esperienza sull'ambiente in base alla nostra distribuzione di probabilità osservata. Il modello inizia un pezzo di carta in stati casuali e i risultati di ogni azione nell'ambito della nostra politica si basano sulle nostre probabilità osservate. Ad esempio, supponiamo che i primi tre episodi simulati siano i seguenti:

Con questi episodi possiamo calcolare i nostri primi aggiornamenti alla nostra funzione di valore di stato usando ciascuno dei tre modelli indicati. Per ora, scegliamo valori alfa e gamma arbitrari su 0,5 per semplificare i nostri calcoli con le mani. Mostreremo in seguito l'impatto che questa variabile ha sui risultati.

Innanzitutto, applichiamo la differenza temporale 0, il più semplice dei nostri modelli e i primi tre aggiornamenti di valore sono i seguenti:

Quindi, come sono stati calcolati? Bene perché il nostro esempio è piccolo, possiamo mostrare i calcoli a mano.

Quindi cosa possiamo osservare in questa fase iniziale? In primo luogo, l'uso di TD (0) appare ingiusto in alcuni stati, ad esempio la persona D, che, in questa fase, non ha guadagnato nulla dalla carta che ha raggiunto il cestino due volte su tre. Il loro aggiornamento è stato influenzato solo dal valore della fase successiva, ma questo sottolinea come le ricompense positive e negative si propagano verso l'esterno dall'angolo verso gli stati.

Man mano che prendiamo più episodi, le ricompense terminali positive e negative si spargeranno sempre più in tutti gli stati. Ciò è mostrato approssimativamente nel diagramma qui sotto dove possiamo vedere che i due episodi hanno provocato un risultato positivo influenzano il valore degli stati Insegnante e G mentre il singolo episodio negativo ha punito la persona M.

Per dimostrarlo, possiamo provare più episodi. Se ripetiamo gli stessi tre percorsi già indicati produciamo la seguente funzione del valore di stato:

(Si noti che abbiamo ripetuto questi tre episodi per semplicità in questo esempio, ma il modello reale avrebbe episodi in cui i risultati si basano sulla funzione di probabilità di transizione osservata.)

Il diagramma sopra mostra i premi del terminale che si propagano verso l'esterno dall'angolo in alto a destra verso gli stati. Da questo, potremmo decidere di aggiornare la nostra politica in quanto è chiaro che la ricompensa terminale negativa passa attraverso la persona M e quindi B e C sono influenzati negativamente. Pertanto, in base alla V27, per ogni stato potremmo decidere di aggiornare la nostra politica selezionando il miglior valore di stato successivo per ciascuno stato, come mostrato nella figura seguente

Esistono due cause di preoccupazione in questo esempio: la prima è che la migliore azione di quella persona A è quella di gettarla nel cestino e ottenere una ricompensa negativa. Questo perché nessuno degli episodi ha visitato questa persona e sottolinea il problema del multi bandito armato. In questo piccolo esempio ci sono pochissimi stati, quindi occorrerebbero molti episodi per visitarli tutti, ma dobbiamo assicurarci che ciò avvenga.

Il motivo per cui questa azione è migliore per questa persona è perché nessuno degli stati terminali ha un valore, ma piuttosto i risultati positivi e negativi sono nelle ricompense terminali. Potremmo quindi, se la nostra situazione lo richiedesse, inizializzare V0 con cifre per gli stati terminali in base ai risultati.

In secondo luogo, il valore dello stato della persona M si sposta avanti e indietro tra -0,03 e -0,51 (circa) dopo gli episodi e dobbiamo affrontare il motivo per cui ciò sta accadendo. Ciò è causato dal nostro tasso di apprendimento, alfa. Per ora, abbiamo introdotto solo i nostri parametri (il tasso di apprendimento alfa e il tasso di sconto gamma) ma non abbiamo spiegato in dettaglio come avranno un impatto sui risultati.

Un alto tasso di apprendimento può far oscillare i risultati, ma viceversa non dovrebbe essere così piccolo che ci vuole un'eternità per convergere. Questo è mostrato ulteriormente nella figura seguente che mostra le V totali per ogni episodio e possiamo vedere chiaramente come, sebbene ci sia una tendenza generale in aumento, si sta differenziando avanti e indietro tra gli episodi. Un'altra buona spiegazione per il tasso di apprendimento è la seguente:

“Nel gioco del golf quando la palla è lontana dalla buca, il giocatore colpisce molto forte per avvicinarsi il più possibile alla buca. Più tardi, quando raggiunge l'area contrassegnata, sceglie un bastoncino diverso per ottenere un tiro corto preciso.

Quindi non è che non sarà in grado di mettere la palla nella buca senza scegliere il bastoncino, ma può mandare la palla davanti al bersaglio due o tre volte. Ma sarebbe meglio se gioca in modo ottimale e usa la giusta quantità di potenza per raggiungere il buco. ”

Episodio

Esistono alcuni metodi complessi per stabilire la velocità di apprendimento ottimale per un problema ma, come con qualsiasi algoritmo di apprendimento automatico, se l'ambiente è abbastanza semplice si scorre su valori diversi fino a raggiungere la convergenza. Questo è anche noto come gradiente stocastico decente. In un recente progetto RL, ho dimostrato l'impatto della riduzione dell'alfa usando un visual animato e questo è mostrato di seguito. Ciò dimostra l'oscillazione quando l'alfa è grande e come questo viene smussato quando l'alfa viene ridotta.

Allo stesso modo, dobbiamo anche avere il nostro tasso di sconto per essere un numero compreso tra 0 e 1, spesso questo è considerato vicino allo 0,9. Il fattore di sconto ci dice quanto siano importanti i premi in futuro; un numero elevato indica che saranno considerati importanti, mentre spostarlo verso 0 farà sì che il modello consideri sempre meno i passi futuri.

Tenendo conto di entrambi, possiamo cambiare sia l'alfa da 0,5 a 0,2 che la gamma da 0,5 a 0,9 e otteniamo i seguenti risultati:

Poiché il nostro tasso di apprendimento è ora molto più piccolo, il modello richiede più tempo per l'apprendimento e i valori sono generalmente più piccoli. Il più evidente è per l'insegnante che è chiaramente lo stato migliore. Tuttavia, questo compromesso per un maggiore tempo di calcolo significa che il nostro valore per M non oscilla più al livello in cui erano prima. Ora possiamo vederlo nel diagramma seguente per la somma di V (s) seguendo i nostri parametri aggiornati. Sebbene non sia perfettamente uniforme, le V totali aumentano lentamente a una velocità molto più uniforme rispetto a prima e sembrano convergere come vorremmo, ma richiedono circa 75 episodi per farlo.

Modifica del risultato dell'obiettivo

Un altro vantaggio cruciale di RL che non abbiamo menzionato in modo troppo dettagliato è che abbiamo un certo controllo sull'ambiente. Attualmente, i premi si basano su ciò che abbiamo deciso sarebbe meglio per ottenere il modello per raggiungere il risultato positivo nel minor numero di passaggi possibile.

Tuttavia, supponiamo che l'insegnante sia cambiato e al nuovo non importava che gli studenti gettassero il foglio nel cestino fintanto che lo raggiungeva. Quindi possiamo cambiare la nostra ricompensa negativa su questo e la politica ottimale cambierà.

Ciò è particolarmente utile per le soluzioni aziendali. Ad esempio, supponiamo che tu stia pianificando una strategia e sappia che alcune transizioni sono meno desiderate di altre, quindi questo può essere preso in considerazione e modificato a piacimento.

Conclusione

Ora abbiamo creato un semplice modello di apprendimento di rinforzo dai dati osservati. Ci sono molte cose che potrebbero essere migliorate o portate avanti, incluso l'uso di un modello più complesso, ma questa dovrebbe essere una buona introduzione per coloro che desiderano provare ad applicare ai propri problemi della vita reale.

Spero che ti sia piaciuto leggere questo articolo, se hai qualche domanda non esitare a commentare qui sotto.

Grazie

Sterlina