L’apprendimento per rinforzo

s r Sistema di apprendimento Ambiente

una rete di trasporto astratta [A. T. Rocha e A. L. C. Bazzan, 2012], in cui l’algoritmo proposto si basa sul cosiddetto Q-learning, una tecnica di apprendimento per rinforzo.

2.2 L’apprendimento per rinforzo

L’apprendimento per rinforzo, RL (Reinforcement Learning), modella tipicamente il caso di un agente che percepisce ed agisce in un certo ambiente, con lo scopo di imparare a fare la scelta ottimale, o la scelta che lo avvicina di più al suo obiettivo. In altre parole, l’agente percepisce lo stato dell’ambiente, sceglie un’azione disponibile in tale stato e quindi riceve immediatamente un segnale di rinforzo dall’ambiente, legato al nuovo stato raggiunto. In figura 3.1 si illustra un problema di apprendimento per rinforzo modellato come un processo di decisione di Markov (MDP). In tale processo, un agente, che si muove in un ambiente (rappresentabile mediante un insieme discreto di stati S), è in grado di percepire un vettore di ingresso, o percezione, che lo informa dello stato s in cui si trova. L’esecuzione di un’azione a ∈ A (insieme discreto di azioni eseguibili dagli agenti) produce una transizione di stato T: S × A → Π (S)) (dove Π (S) è una distribuzione di probabilità su S) e una funzione di ricompensa R: S × A →

R

. Con T (s, a, s’) si intende la probabilità di passare dallo stato s allo stato s’ dopo aver eseguito un’azione a in s.

Per scegliere in ogni istante l’azione da eseguire, l’agente fa uso di una strategia, definita come π: S × A →

R

, che associa l’attuale stato s ad una azione a eseguita dall’agente. Tale politica è ottenuta sottoforma di tabella stati/azioni (Q-table). Per agire l’agente deve valutare in ogni stato, e per ogni azione intrapresa, il valore atteso della ricompensa futura. È proprio questa l’informazione che l’agente deve apprendere cioè: una value function V: S

_R

, oppure una value-action function Q: S × A →

R

. Il valore

ottimale di uno stato, V*(s), è la somma delle ricompense che l’agente guadagna a partire dallo stato s e seguendo l’orientamento ottimale. La politica ottimale π* rappresenta l’associazione degli stati alle azioni che massimizza la ricompensa futura [A. T. Rocha e A. L. C. Bazzan, 2012].

2.3 Il modello decisionale di scelta del percorso di J. L. Horowitz

J. L. Horowitz (1984) è stato uno dei primi studiosi ad indagare la stabilità dell’equilibrio stocastico in una rete di trasporto semplificata, concentrandosi sulla stima del costo di viaggio medio percepito attraverso una media pesata dei costi realizzati nei periodi precedenti (l’impatto delle informazioni di viaggio non è stato trattato). Nei modelli stocastici, i costi dei percorsi oggettivi e quelli percepiti dai viaggiatori differiscono di un residuo aleatorio, legato agli effetti degli errori di percezione nella stima dei costi. L’autore propone tre modelli per studiare il processo decisionale che porta alla scelta del percorso, e per ognuno indaga la stabilità dell’equilibrio. Nello specifico, se si assume che Vit sia il volume di traffico del link i nel periodo di tempo t (t = 1, 2, …) e che Vie sia l’unico volume di equilibrio dello stesso link i, l’equilibrio è stabile se per tutti i link:

ie it t V =V ∞ → lim (3. 1)

a prescindere dal volume iniziale dei link o dai costi di viaggio percepiti iniziali [J. L. Horowitz, 1984].

Il problema della stabilità dell’equilibrio nelle reti di trasporto è estremamente complesso in quanto legato alla varietà e alla complessità dei modi in cui le decisioni di viaggio possono dipendere dagli esiti delle esperienze passate. Pertanto, per una trattazione più semplice, nello studio di Horowitz sono state adottate le seguenti ipotesi:

la rete di trasporto è costituita da due soli link che collegano l’origine alla destinazione;

i viaggiatori si spostano dall’origine alla destinazione in una sequenza di periodi t = 1, 2, …;

i costi dei link sono dipendenti dai flussi, pertanto i costi reali non sono noti ai viaggiatori fin tanto che il viaggio non si verifica. Ciò comporta che le scelte di percorso devono essere basate sulle informazioni riguardanti i costi di viaggio dei periodi precedenti;

il flusso della domanda totale origine destinazione è noto e fissato.

Di seguito, si considera il primo modello che tiene conto della relazione tra i costi di viaggio con cui il viaggiatore si è confrontato nelle esperienze precedenti, e le scelte di percorso correnti. Il modello viene così formulato:

(

1

)

; 1,2 ˆ ¹ 1 = + − =

∑

⁻ = i C t w C _it t k ik k it ε (3. 2) dove:

Ĉit= costo di viaggio percepito del link i nel periodo t in cui il viaggiatore deve decidere quale percorso utilizzare;

Cik = costi di viaggio oggettivi del link i nei periodi k precedenti al momento della decisione;

εit = residuo aleatorio ;

w_k (t-1) = peso (non negativo)¹.

In parole: le decisioni di scelta di percorso si basano su una media pesata dei costi di viaggio misurati nei periodi di tempo precedenti il periodo in cui viene presa la decisione (cioè per t ≤ t-1). I pesi, attribuiti ai costi dei percorsi sperimentati in precedenza, descrivono l’influenza dei costi passati, lontani e recenti, sulla percezione corrente del viaggiatore. In particolare, se le percezioni dell’individuo al tempo t sono determinate principalmente dai costi recenti (con tendenza a dimenticare quelli più lontani), allora sarà lecito supporre che w1(t-1) < w2(t-1) < … < wt-1(t-1). Al contrario, se w1(t-1) > w2(t-1) > … > wt-1(t-1) allora ciò significa che il viaggiatore attribuisce un maggior peso alle esperienze più lontane nel tempo che hanno contribuito allo sviluppo di forti abitudini. Dal momento che l’abitudine è strettamente legata all’apprendimento

per rinforzo e alla memoria nella sua fase iniziale di formazione, una volta consolidata, la misura in cui il processo di apprendimento si verifica diminuisce. In questo caso la scelta di percorso sarà influenzata dall’inerzia, e non sarà facilmente condizionata dagli eventi recenti tanto più il viaggiatore è sfavorevole alla sperimentazione di nuove alternative.

Si è detto che la stabilità dell’equilibrio dipende dalla relazione tra i costi di viaggio oggettivi misurati nelle esperienze passate, e le scelte di percorso correnti dei viaggiatori. In questo modello, la stabilità dipende da come i viaggiatori assegnano i pesi ai costi passati (recenti e distanti). Se i pesi sono opportunamente bilanciati la stabilità è assicurata, altrimenti se troppo sbilanciati a favore delle esperienze recenti o di quelle passate, l’equilibrio non è stabile.

Per concludere, si propongono delle brevi considerazioni sul modello appena descritto. Il primo aspetto riguarda lo scarso approfondimento nella definizione dei pesi. L’autore accenna al fatto che i pesi devono essere valori positivi, senza precisare da cosa dipendono. Un altro aspetto è legato al parametro k, la cui variazione (k = 1, 2, …, t-1) fa presumere che l’autore assuma che il viaggiatore abbia una capacità illimitata nel ricordare gli eventi passati. Per quanto riguarda il primo aspetto, Horowitz assume una formulazione del tipo:

t

w₌ 1 _{, in cui tanto più l’evento appartiene a un passato lontano} tanto più il peso associato ad esso diminuirà. In altre parole, è più logico pensare che rinforzi lontani nel tempo pesino di meno di quelli più recenti. Altrimenti, i pesi possono derivare da un’analisi psicologica secondo il seguente concetto: se l’azione (in questo caso la scelta di percorso) comporta un premio (risultato positivo) allora il peso sarà alto in modo da indurre l’utente a compiere la medesima scelta. Altrimenti, in caso di "punizione" (risultato negativo), il peso sarà basso in modo da scoraggiare il viaggiatore. L’assunzione di memoria illimitata non è plausibile, in quanto la memoria di un evento decade nel tempo. Esistono modelli che includono il cosiddetto “parametro di recuperabilità” che rappresenta la facilità con cui la traccia dell’evento può essere recuperata dalla memoria. Quindi in una qualche misura la memoria limitata dei viaggiatori influenza i comportamenti di scelta del percorso.

2.4 Un esempio di modello di apprendimento con rinforzo per

Nel documento ANALISI DI ALCUNI ASPETTI PSICOLOGICI E COMPORTAMENTALI DELLE SCELTE INDIVIDUALI DI TRASPORTO (pagine 83-87)