5 REINFORCEMENT LEARNING

5

REINFORCEMENT LEARNING

Il presente capitolo serve a chiarire alcuni concetti necessari ad una migliore comprensione del capitolo 6 che descrive la realizzazione del progetto. A questo scopo, verranno introdotti i principali concetti del “reinforcement learning”.

Dopo aver spiegato il significato del termine saranno individuati gli elementi di cui esso si compone e chiariti gli obiettivi che esso si propone di raggiungere. Inoltre sarà spiegato brevemente il problema del bandito ad n braccia che richiama concetti del reinforcement learning e sarà fornita una panoramica dei metodi utilizzati per la selezione delle azioni con particolare riferimento al metodo softmax. Infine verrà data una breve spiegazione delle principali classi di metodi utilizzati per la risoluzione di problemi di reinforcement learning e, con riferimento ai metodi di apprendimento delle differenze temporali sarà posta l’attenzione su un algoritmo in particolare: Q-learning.

5.1

Introduzione al Reinforcement Learning

Il reinforcement learning è un metodo di apprendimento per automi appartenente alla categoria dei metodi di apprendimento non supervisionato1 e dell’area dell’intelligenza artificiale. Esso si distingue dagli altri approcci computazionali per l’enfasi che attribuisce all’apprendimento di un learner agent o agente [Sutton 98].

Il learner agent letteralmente è colui che agisce ed impara interagendo con il suo ambiente. Durante queste interazioni, seleziona le azioni da compiere e ottiene delle risposte dall’ambiente. L’ambiente infatti, oltre a presentare nuove situazioni, fornisce anche delle ricompense o rewards, che rappresentano il guadagno ottenuto dal learner agent per aver compiuto una particolare azione. Scegliere le azioni giuste è fondamentale, ogni azione infatti, contribuisce alla realizzazione dell’obiettivo di massimizzazione del reward.

Di seguito è presentato uno schema del reinforcement learning, il cui obiettivo è quello di massimizzare il reward.

1

Non deve essere detto all’agente quali azioni compiere; l’agente deve interagire liberamente con il proprio ambiente e scoprire quali sono le migliori azioni da compiere facendo prove e valutazioni.

Figura 1 – Schema del reinforcement learning

Il learner agent ha un comportamento non passivo, nel senso che modifica l’ambiente in cui agisce, ne valuta lo stato e reagisce appropriatamente. Il reinforcement learning usa una struttura formale per definire l’interazione tra il learner agent e il suo ambiente in termini di stati, azioni e rewards come mostrato di seguito:

Figura 2 - Interazione dell'agente con l'ambiente

La figura mostra che l’agente e l’ambiente interagiscono con una sequenza di passi, t = 1, 2, 3,….. Ad ogni passo, l’agente riceve una rappresentazione dello stato dell’ambiente,

s

t

∈

S

, dove

S

è l’insieme dei possibili stati e su queste basi

seleziona un’azione,

a

t

∈

A

(

s

t

)

, dove

A

(

S

t

)

è l’insieme delle azioni disponibili nello

stato

s

_t. Dopo il primo passo l’agente riceve un reward numerico,

r

_t+1

∈

R

, e si ritrova in un nuovo stato,

s

_t+1.

Agente

Ambiente

Reward rt st+1 rt+1 Stato st Azione at

L’agente quindi può essere descritto da un insieme di possibili stati a cui è associata un’azione ed ognuna di esse restituisce un premio o reward.

Figura 3 - Funzionamento agente

La struttura presentata rappresenta in modo semplice le caratteristiche essenziali di un problema di intelligenza artificiale, caratteristiche che contengono relazioni di causa-effetto, incertezza, non determinismo e l’esistenza di un obiettivo esplicito.

Per capire meglio il concetto è possibile considerare un esempio in cui un agente mobile è in grado di compiere quattro azioni e deve raggiungere due possibili obiettivi. Il reward in questo caso è definito in ogni stato con il valore penalizzante -1 eccetto che per il target dove vale 0, in questo modo viene premiato il più veloce raggiungimento dell’obiettivo.

Figura 4 - Processo con 16 stati e 4 azioni

Le due seguenti figure illustrano il processo di decisione dove gli obiettivi sono colorati in grigio. Nella prima figura sono indicati i valori di ogni stato nel caso che la strategia adottata (o policy) sia casuale (può essere scelta a caso una qualsiasi delle 4 azioni). Mentre nella seconda figura sono indicati i valori nel caso della migliore strategia possibile.

s0 a0 s1 a1 s2 a2

…

Figura 5 - Valorizzazione degli stati

Gli stati più lontani dai target saranno penalizzati perché il punteggio finale (fitness) ottenibile a partire da questi stati è la somma di molte ricompense (reward) negativi. Il valore degli stati nel primo caso, comportamento casuale, è un valore medio molto basso perché si attraversano molti stati inutilmente, mentre nel caso di comportamento ottimale (rappresentato dalle frecce) è il massimo possibile che si possa ottenere perché rappresenta le traiettorie più brevi. La valorizzazione degli stati, in termini di reward totale ottenibile, viene effettuata mediante esperienza. Partendo da una strategia, si fa vivere l’agente sulla scacchiera più volte e in questo modo vengono contabilizzati i rinforzi totali medi accumulati a partire dallo stato su cui l’agente passa, fino al raggiungimento del target.

Il reinforcement learning, consente quindi all’agente di imparare a collegare determinate azioni da intraprendere e non si caratterizza come un “algoritmo” di apprendimento bensì come un “problema” di apprendimento, ciò vuol dire che dato un problema di reinforcement learning deve essere definito un algoritmo di reinforcement learning per la risoluzione del problema. Gli algoritmi di reinforcement learning tentano di cogliere un’informazione di feedback ad ogni istante della vita, modificando di conseguenza il comportamento, per questo motivo l’elaborazione deve essere iterativa e il comportamento deve essere sequenzialmente aggiornato.

Il raggiungimento dell’obiettivo di massimizzazione del reward da parte del learner agent dipende dalla capacità del learner di stabilire le giuste percentuali di sfruttamento ed esplorazione, a tale scopo esso deve essere in grado di:

Sfruttare (exploit) le azioni di cui conosce già il reward

Esplorare (explore) o provare a compiere nuove azioni per selezionarne migliori in futuro.

Il bilanciamento di esplorazione e sfruttamento può essere fatto utilizzando alcuni metodi, quali metodi ∈-greedy e metodi Softmax che saranno analizzati più in dettaglio nei prossimi paragrafi.

Un sistema basato sul reinforcement learning quindi, è costituito da quattro sottoelementi:

Strategia (policy)

Funzione di rinforzo (Reward function)
Funzione del valore (Value function)
Modello dell’ambiente (Model)

La strategia rappresenta il modo in cui il learner agent si comporta in un determinato istante e da sola è sufficiente a determinarne il comportamento. E’ possibile vedere la strategia come una mappa di stati percepiti dall’ambiente e di azioni da intraprendere in quegli stati, essa può essere rappresentata da una semplice funzione o da una semplice tabella. Per comprenderne meglio il significato è possibile considerare un’analogia con la psicologia, in cui la strategia corrisponderebbe all’insieme delle regole o delle associazioni stimolo-risposta.

Nei paragrafi che seguono, sarà fatto spesso riferimento alla strategia con il simbolo

π

_t.

La funzione di rinforzo, mette in relazione le coppie stato-azione con un valore numerico detto reward (desiderabilità dello stato) e definisce l’obiettivo, di massimizzazione del reward nel lungo periodo, del problema di reinforcement learning,.

La funzione di rinforzo è la base per il cambiamento della strategia, ad esempio se un’azione selezionata con una determinata strategia è seguita da un basso reward, la strategia può essere cambiata selezionando una nuova azione in futuro.

Generalmente la funzione di rinforzo indica la desiderabilità degli stati nell’immediato mentre la funzione del valore indica la desiderabilità degli stati nel lungo periodo e valuta gli stati che potrebbero seguire e i rewards ottenibili in tali stati. La funzione del valore specifica il reward totale che un agente può prevedere di accumulare nel tempo, partendo dallo stato in cui si trova. I reward quindi sono valori di primaria importanza mentre i valori, intesi come predizione di rewards, sono di secondaria importanza, in quanto se non ci fossero i rewards non ci sarebbero nemmeno i valori che vengono determinati solo allo scopo di massimizzare il reward.

La concentrazione è riservata alle azioni che portano a stati con più alti valori e non a quelle con più alti reward, perché sono le azioni con più alti valori che ottengono il più alto reward nel tempo.

I rewards in genere vengono assegnati dall’ambiente, mentre i valori devono essere stimati e ristimati a partire dalla sequenza delle osservazioni che l’agente fa lungo il corso della sua vita. Per questo motivo per gli algoritmi di reinforcement learning è fondamentale un metodo per stimare questi valori efficientemente.

Il quarto e ultimo elemento che caratterizza il reinforcement learning è il modello dell’ambiente, un modello che simula il comportamento dell’ambiente, cioè dato uno stato ed un’azione, predice il prossimo stato e il reward risultante.

Generalmente il modello è utile in fase di pianificazione per decidere tra le azioni, esso infatti permette di considerare probabili situazioni future prima che effettivamente si verifichino.

5.2

L’obiettivo dell’agente

Come precedentemente esposto, l’obiettivo dell’agente è quello di massimizzare i rewards ricevuti durante le lunghe elaborazioni. Se la sequenza dei rewards è identificata con

r

_t+1

,

r

_t+2

,...,

allora ciò che deve essere massimizzato sono i ritorni attesi , e il ritorno Rt, è definito come una specifica funzione della sequenza

dei reward, in pratica il valore di Rt è dato da:

T t

t

t

r

r

r

R

=

₊1

+

₊2

+

...

+

Dove T è il passo finale. Ma c’è un altro fattore che deve essere considerato e cioè, il fattore di sconto. Secondo questo approccio, l’agente prova a selezionare le azioni in modo che la somma dei rewards scontati che riceve nel tempo sia massimizzata. In particolare sceglie l’azione

a

_t per massimizzare il ritorno atteso scontato: 1 0 3 2 2 1

...

+ + ∞ = + + +

+

+

+

=

∑

=

t k k k t t t t

r

r

r

r

R

γ

γ

γ

Dove

γ

è un parametro,

0

<=

γ

<=

1

, chiamato tasso di sconto. Il tasso di sconto determina il valore presente dei rewards futuri, se

γ

=0 sarà considerato

solo il reward immediato, se invece

γ

=1, sarà data più enfasi ai rewards futuri rispetto al reward immediato. La sequenza dei rewards

r

_t+i è generata partendo

dallo stato

s

_te usando ripetutamente la politica

π

per selezionare le azioni. L’obiettivo è fare in modo che l’agente impari una politica

π

in grado di massimizzare

R

_t. Lo stesso valore di

R

_t può essere indicato anche con

V

π

(

s

_t

)

, cioè il valore ottenuto dall’uso della strategia

π

partendo dallo stato

s

_t, per ogni stato

s

. Questa strategia ottimale viene indicata con

π

*:

)

(

),

(

max

arg

*

s

s

V

∀

≡

π π

π

Con

V

*

(

s

)

sarà indicato il massimo reward cumulativo scontato che l’agente può ottenere partendo dallo stato

s

.

V

*

(

s

)

è ottenuto partendo dallo stato

s

e seguendo la strategia ottimale,

π

*.

L’illustrazione di questo concetto è riportata in figura [Mitchell 97]:

Figura 6 - Rewards immediati

r

( a

s

,

)

Ogni cella della griglia rappresenta uno stato distinto e ogni freccia rappresenta un’azione.

Il sesto quadrato della griglia rappresenta la posizione attuale dell’agente, ogni freccia rappresenta l’azione possibile che l’agente può fare da uno stato all’altro. Il numero associato ad ogni freccia è il reward immediato

r

( a

s

,

)

che l’agente riceve se esegue la corrispondente transizione stato-azione. In questo particolare ambiente il reward è 0 per tutte le transizioni tranne che per quella nello stato etichettato con G. G è lo stato goal, il solo modo con cui l’agente può ricevere un reward è quello di entrare nello stato G, in questo caso l’unico modo che l’agente ha per entrare all’interno di questo stato, è quello di entrare e rimanerci, in quanto G è uno stato assorbente. Una volta che lo stato, l’azione e i rewards sono

stati definiti e una volta scelto un valore per il fattore di sconto

γ

, possiamo determinare la politica ottimale

π

* e il valore della sua funzione

V

π

(s

)

. La strategia ottimale guiderà l’agente lungo il cammino più breve per raggiungere lo stato G.

Di seguito è mostrato un esempio che spiega in che modo è possibile trovare la strategia ottimale a partire dai seguenti valori di

Q

( a

s

,

)

(valore della transizione stato-azione), di *

(

)

s

V

(valore dello stato) che provengono da

r

( a

s

,

)

e dal fattore di sconto

γ

= 0.9.

Figura 7 - Valori per Q( as, ) e

_V

*

(

_s

)

In questo caso, il valore

V

*dello stato in basso a destra è 100, la politica ottimale in questo stato seleziona l’azione “vai su” che riceve un reward immediato di 100, a questo punto l’agente rimane nello stato assorbente e continua a ricevere rewards. Una cosa simile succede nello stato centrale in basso con valore 90. La politica ottimale farà muovere l’agente da questo stato verso destra, generando un reward immediato di 0, poi su , generando un reward immediato di 100. Il reward futuro scontato dallo stato centrale in basso è

0 +

γ

100

+

γ

2

0

+

γ

3

0

+

...

=

90

La strategia ottimale corrispondente alle azioni con i massimi valori di Q è la seguente:

Figura 8 - Strategia ottimale con i massimi valori di Q( as, )

*

V

è la somma dei rewards futuri scontati fino all’infinito. In questo particolare ambiente, una volta che l’agente entra nello stato assorbente G il suo futuro consiste nel rimanere in questo stato e ricevere rewards 0.

5.3

Il problema del bandito ad n braccia

La caratteristica più importante che distingue il reinforcement learning dagli altri tipi di apprendimento è il fatto che esso usa informazioni di training per valutare le azioni piuttosto che fornire direttamente le azioni corrette. Per poter generare il giusto comportamento ricercando l’azione mediante prove (trial and error search) è necessario attivare l’esplorazione.

I feedback per i metodi di apprendimento non supervisionato dipendono dalle azioni, sono detti valutativi, e si distinguono dai feedback istruttivi, utilizzati per i metodi di apprendimento supervisionato (classificazioni, reti neurali…) che invece dipendono interamente dalle azioni considerate. I feedback valutativi indicano se l’azione è buona ma non se è la migliore o la peggiore possibile

Nel presente paragrafo la trattazione è riservata, in modo semplificato, all’aspetto valutativo del reinforcement learning. In particolare l’attenzione è concentrata su una semplice versione del problema del bandito ad n braccia che prende il nome dall’analogia con la slot machine o “bandito ad un braccio” ma si distingue perché possiede n leve e non una.

Consideriamo il caso di dover essere ripetutamente di fronte ad n scelte. Dopo ogni scelta si riceve un reward numerico scelto tra distribuzioni di probabilità stazionarie che dipendono dalle azioni che vengono selezionate. L’obiettivo è massimizzare il reward totale atteso nel tempo. Mantenendo l’analogia con la slot machine, è possibile immaginare che ogni azione selezionata equivalga

all’attivazione della leva della slot machine e che il reward sia il pagamento del jackpot. Attraverso la ripetizione del gioco è possibile massimizzare le vincite concentrando il gioco sulle migliori leve.

In questo problema ogni azione ha un reward atteso che non è altro che il valore dell’azione, conoscendo il valore di ogni azione è possibile provare a risolvere il problema del bandito ad n-braccia: selezionando sempre l’azione con il più alto valore. Se non si conosce il valore dell’azione è necessario stimarlo.

Se la stima dei valori delle azioni viene mantenuta, in ogni momento esiste almeno un’azione il cui valore stimato è più grande, quest’azione è detta greedy. La selezione di un’azione greedy consente di sfruttare la conoscenza dei valori delle azioni, mentre la selezione di azioni non greedy, consente di esplorare allo scopo di migliorare la stima dei valori delle azioni non greedy.

Per la massimizzazione del reward atteso in un gioco, lo sfruttamento, è la miglior cosa da fare, tuttavia l’esplorazione può contribuire alla produzione di un reward totale più grande in lunghe elaborazioni.

Ad esempio supponiamo di conoscere con certezza i valori delle azioni greedy, e di avere altre azioni con valori stimati vicini a quello ma con una sostanziale incertezza. L’incertezza è tale per cui almeno una di queste altre azioni probabilmente è realmente migliore delle azioni greedy, ma non sappiamo quale. Se abbiamo qualche mossa ancora da fare, potrebbe essere meglio esplorare le azioni non greedy e scoprire quali di queste sono migliori delle azioni greedy. Il reward è più basso nelle piccole elaborazioni, (durante l’esplorazione) ma più alto nelle lunghe elaborazioni perché si possono scoprire migliori azioni e sfruttare quelle. Poiché non è possibile esplorare e sfruttare insieme con una singola azione selezionata, nascono spesso conflitti nella scelta tra esplorazione e sfruttamento.

La scelta tra esplorazione e sfruttamento dipende dal valore preciso delle stime, dall’incertezza (ad esempio, si stima che un certo numero di azioni abbia un valore quasi pari a quello dell’azione greedy ma non lo si sa con certezza ed è il caso di esplorarle) e dal numero delle mosse rimanenti.

Esistono diversi metodi per bilanciare esplorazione e sfruttamento per diverse formulazioni matematiche del problema del bandito ad n braccia. Alcuni di questi metodi fanno forti assunzioni sulla stazionarietà e sulla conoscenza a priori che in genere sono impossibili da verificare nelle applicazioni.

5.4

Metodi per la selezione delle azioni

In questo paragrafo viene presentato qualche metodo utilizzato per stimare i valori delle azioni e l’uso di questi valori per selezionare le azioni stesse.

Indichiamo con

a

l’azione, con

Q

* a

(

)

il valore effettivo di

a

e con

Q

t

(a

)

il

valore stimato della t-esima mossa. Il valore effettivo dell’azione

a

è il reward ricevuto nel momento in cui l’azione è stata selezionata. La stima del valore di

a

dopo t mosse è data dalla media dei reward realmente ricevuti quando l’azione è stata selezionata. In altre parole se alla t-esima mossa è stata scelta

k

_a(cioè la

k

-esima azione), allora il valore stimato per

k

_a alla t-esima mossa è:

=

)

(a

Q

t a k

k

r

r

r

a

+

+

+

₂

...

1

Se

k

a

=

0

allora

Q

0

(

a

)

=

0

, se il

k

a

→

∞

per la legge dei grandi numeri

)

(a

Q

t converge a

Q

* a

(

)

. Questo è detto metodo della media del campione per la

stima dei valori delle azioni in quanto ogni stima è data dalla media semplice dei rewards del campione. Naturalmente questo metodo serve a stimare i valori delle azioni e non a scegliere l’azione migliore. La regola più semplice per selezionare l’azione migliore è quella di selezionare quella con il più alto valore stimato, ossia selezionare una delle azioni greedy

a

*

alla t-esima mossa, quindi

)

(

max

*)

(

a

Q

a

Q

_t

=

_{a t} . Questo metodo sfrutta in ogni momento la conoscenza che si ha allo scopo di massimizzare il reward immediato e non spreca tempo per vedere se tutte le azioni che apparentemente avevano un reward inferiore a quello dell’azione greedy potevano essere migliori.

Metodi alternativi sono i metodi ∈-greedy che si comportano come i metodi azione-valore visti fin’ora ma ogni tanto, con probabilità ∈, selezionano un’azione in modo casuale, indipendentemente dalla stima del valore dell’azione. Il vantaggio di questi metodi è che, man mano che il numero delle mosse aumenta, ogni azione è campionata un infinito numero di volte, e questo garantisce che quando

k

_a

→

∞

)

(

a

Q

_t converge a

Q

*

(

a

)

(valore effettivo). Questo implica che la probabilità di selezionare l’azione ottimale converge a 1-∈.

Nonostante la selezione delle azioni ∈-greedy sia un metodo popolare per bilanciare esplorazione e sfruttamento nel reinforcement learning, esso presenta lo svantaggio che nell’esplorazione sceglie equamente tra le azioni. Questo significa che la migliore e la peggiore azione possono essere scelte con la stessa probabilità e nei casi in cui le peggiori azioni sono molto dannose questo può essere insoddisfacente. La soluzione ovvia è variare le probabilità di scelta delle azioni con una funzione graduata della stima del loro action value. In questo caso l’azione greedy ha ancora la più alta probabilità di essere scelta, mentre la probabilità delle altre è pesata in accordo alla stima del loro valore. Il metodo softmax più comune usa la distribuzione di Gibbs, o di Boltzmann. L’azione

a

nella t-esima mossa è scelta con probabilità:

∑

n₌ b b Q a Q t t

e

e

1 / ) ( / ) ( τ τ

Dove

τ

è un parametro positivo che indica la temperatura. Un’alta temperatura fa si che tutte le azioni abbiano la stessa probabilità di essere scelte. Basse temperature provocano una grande differenza nella probabilità di selezione delle azioni che differiscono per i loro valori stimati. Quando

τ

→

0

, la selezione delle azioni con softmax diventa la stessa della selezione greedy. Naturalmente gli effetti di softmax possono essere prodotti in diversi modi oltre che con la distribuzione di Gibbs.

Capire chi è il migliore tra softmax e ∈-greedy non è facile, dipende dal compito e da fattori umani. Alcuni trovano più facile impostare il parametro ∈ mentre l’impostazione di

τ

richiede conoscenze sui valori delle azioni e sul potere di

e

.

5.5

Implementazione in ambienti statici e dinamici

I metodi azione-valore discussi stimano i valori delle azioni come media del campione dei rewards osservati. L’implementazione ovvia è mantenere, per ogni azione

a

, un record di tutti i rewards che seguono la selezione dell’azione. Una volta che il valore stimato dell’azione

a

è necessario al tempo t, esso può essere computato secondo la seguente formula:

=

)

(

a

Q

t a k

k

r

r

r

a

+

+

+

₂

...

1 a k

r

r ,...,

1 sono i rewards ricevuti in seguito alle selezioni dell’azione

a

prima della

mossa t. Questa implementazione presenta problemi di memorizzazione, infatti ogni reward successivo alla selezione dell’azione

a

richiede memoria per essere immagazzinato, deve essere determinata una formula che calcoli la media in modo da processare ogni nuovo reward. Per ogni azione

Q

_k(da non confondere con

)

(

a

Q

k la media per l’azione

a

alla mossa

k

), rappresenta la media dei primi

k

reward. Data questa media e il

(

k

+

1

)

-esimo reward,

rk

+

1

, la media dei

k

+

1

rewards può essere calcolata nel seguente modo:

]

[

1

1

1

1

1 1 1 1 k k k i k i k

r

Q

k

Q

r

k

Q

−

+

+

=

+

=

+ ₊ = +

∑

Esprimibile come:

∑

=

=

k i i t

r

Q

1

che per valori di

k

=

0

ottiene

Q

₁

=

r

₁ per

Q

₀ arbitrari. Questa implementazione richiede la memorizzazione dei soli valori di

Q

_ke

k

, e solo un piccolo calcolo per ogni nuovo reward. In pratica:

nuova stima = vecchia stima + StepSize [Target – vecchia stima]

L’espressione tra parentesi quadre indica l’errore nella stima. Il target indica la direzione desiderata in cui muoversi, nel caso sopra il target è il

k

+

1

–esimo reward.

Il parametro StepSize descrive i cambiamenti passo per passo. Processando il k-esimo reward per l’azione

a

, il metodo usa uno StepSize di

k

1

. Lo StepSize

d’ora in poi sarà indicato con

α

, più generalmente con

a k

k

a

)

1

(

=

α

.

Il metodo della media descritto sopra è molto indicato nei casi in cui l’ambiente sia statico, ma non in presenza di un ambiente dinamico, ad esempio nel caso in cui il bandito cambi nel tempo. In molte situazioni ha senso pesare i rewards in modo sempre più incisivo con il passare del tempo. Uno dei metodi più comuni per fare questo è quello di usare un parametro costante per lo Step-Size.

Si potrebbero memorizzare solo la vecchia stima del valore dell’azione, l’istante

k

e il reward a tale istante:

]

[

1 1 k k k

k

Q

r

Q

Q

₊

=

+

α

₊

−

dove il parametro Step-size ,

α

,

0

<=

α

<=

1

è costante.

Q

_k è una media pesata dei rewards passati con stima iniziale

Q

₀ quindi risulta:

i i k k i k k k k k

Q

r

Q

Q

r

Q

− = − −

+

−

=

−

+

∑

−

=

1 0 1 1

α

[

]

(

1

α

)

α

(

1

α

)

Chiamiamo questa formula media pesata in quanto la somma dei pesi è

1

)

1

(

)

1

(

1 0

+

−

=

−

− =

∑

i i k k i k

r

Q

α

α

α

. E’ possibile notare che il peso,

α

(

1

−

α

)

k−i dato al reward

r

_i, dipende da quanti reward,

k

−

i

sono stati osservati. La quantità

1

−

α

è inferiore ad 1 e il peso dato a

r

_i decresce all’aumentare del numero dei rewards. Infatti il peso decade esponenzialmente secondo l’esponente

1

−

α

.

5.6

I processi decisionali Markoviani

Nella struttura del reinforcement learning, l’agente prende le proprie decisioni in funzione dei segnali provenienti dall’ambiente, più comunemente chiamati, stati dell’ambiente. In questo paragrafo verrà chiarito che cosa è richiesto allo stato e che tipo di informazione esso dovrebbe fornire. In particolare viene definita una proprietà degli ambienti e degli stati, detta proprietà di Markov.

Lo stato contiene le informazioni a disposizione dell’agente, assumiamo che esso sia dato da un sistema di preprocessing che fa parte dell’ambiente. Abbiamo bisogno di uno stato che sia in grado di mantenere, in modo compatto, le sensazioni passate o le informazioni ritenute rilevanti. Uno stato che riesce a

trattenere le informazioni rilevanti è detto Markoviano, o avente la proprietà di Markov.

In riferimento al problema del reinforcement learning, la proprietà di Markov, può essere definita nel seguente modo: assumendo che ci siano un numero di stati e di reward finiti, la risposta dell’ambiente al tempo t+1 ad un’azione eseguita al tempo t potrebbe dipendere da quello che è successo in passato. In questo caso la dinamica può essere definita solo specificando la distribuzione completa delle probabilità:

{

1

'

,

1

|

,

,

,

1

,

1

,....,

1

,

0

,

0

}

Pr

s

_t+

=

s

r

_t+

=

r

s

_t

a

_t

r

_t

s

_t−

a

_t−

r

s

a

Lo stato

s

'

è detto stato sensoriale e rappresenta lo stato al tempo t+1 mentre

r

rappresenta il reward al tempo t+1. Per tutti gli stati

s

'

,

r

, e tutti i possibili valori degli eventi passati:

s

_t

,

a

_t

,

r

_t

,....,

r

₁

,

s

₀

,

a

₀, se lo stato sensoriale ha la proprietà di Markov allora la risposta dell’ambiente al tempo t+1 dipende solo dalle rappresentazioni dello stato e dell’azione al tempo t, in questo caso le dinamiche dell’ambiente possono essere definite specificando solo:

{

s

t

s

'

,

r

t

r

|

s

t

,

a

t

}

Pr

+1

=

+1

=

∀

s

'

,

r

,

s

t,

a

t

In altre parole, uno stato sensoriale avente la proprietà di Markov è uno stato Markoviano se e solo se le due espressioni sopra riportate sono uguali per tutti gli

,

,

' r

s

e per i valori storici

s

_t

,

a

_t

,

r

_t

,...,

r

₁

,

s

₀

,

a

₀, in questo caso anche l’ambiente ha la proprietà di Markov.

Un ambiente che ha la proprietà di Markov è detto one-step dynamics e permette di predire il prossimo stato e il prossimo reward atteso dati lo stato e l’azione corrente. E’ possibile dimostrare che iterando l’equazione e conoscendo lo stato corrente e la storia completa fino allo stato attuale, è possibile predire tutti gli stati futuri e i rewards attesi. Inoltre gli stati Markoviani forniscono le migliori basi per la scelta dell’azione e per la definizione della migliore strategia.

La proprietà di Markov è importante nel reinforcement learning perché permette di prendere le decisioni e di definire i valori solo in funzione dello stato corrente.

Una piena comprensione della teoria dei casi di Markov è essenziale anche per essere estesa a casi più complessi e non markoviani. Le teorie sviluppate per i

casi Markoviani aiutano a capire il comportamento degli algoritmi e gli algoritmi possono essere applicati anche a casi che non sono propriamente Markoviani.

Infine, l’importanza delle rappresentazioni degli stati di Markov è dimostrata anche dall’uso, oltre che nel reinforcement learning, in altri approcci all’intelligenza artificiale.

Un task di reinforcement learning che soddisfa la proprietà di Markov è detto processo decisionale Markoviano (MDP), se lo stato e gli spazi delle azioni sono finiti, allora è detto processo decisionale markoviano finito (finite MDP). Gli MDP finiti sono particolarmente importanti per la teoria del reinforcement learning. Con il processo decisionale Markoviano la vita dell’agente è scomposta in una sequenza di stati sensoriali e ad ogni stato corrisponde una gamma di azioni possibili che devono essere valutate, solo se la funzione di transizione di stato (la regola che lega l’azione allo stato successivo), è fissa e indipendente dalla storia passata, cioè solo se è funzione dello stato corrente siamo in un processo decisionale markoviano.

La figura mostra un esempio di catena markoviana degli stati:

Figura 9 - Catena markoviana degli stati

Un particolare MDP finito è definito dal suo stato e dalla sua azione,

s

e

a

, e dalla probabilità di ogni possibile stato successivo s’:

{

s

_t

s

s

_t

s

a

_t

a

}

a

ss

=

=

=

=

Ρ

_'

Pr

₊₁

|'

,

Queste quantità sono chiamate probabilità di transizione. In modo simile dato uno stato corrente e un’azione,

s

e

a

, con uno stato s’, il valore atteso del prossimo reward sarà:

{

1

|

,

,

1

'

}

'

E

r

s

s

a

a

s

s

R

t t t t a ss

=

+

=

=

+

=

Queste quantità,

P

_ssa'e q ss

R

', specificano completamente i più importanti aspetti

delle dinamiche degli MDP finiti.

5.7

Ottimizzazione della funzione valore

La maggior parte degli algoritmi di reinforcement learning si occupa di calcolare una stima della funzione valore (o value function). La funzione valore assegna ad ogni stato, o coppia stato-azione, il ritorno atteso (o reward futuro) dallo stato o dalla coppia, tenendo conto della strategia utilizzata dall’agente. Come già detto in precedenza la strategia, può essere identificata con

π

. Informalmente il valore dello stato

s

sotto la strategia

π

, indicato con

V

π

(s

)

, è il ritorno atteso ottenuto partendo dallo stato s ed eseguendo la strategia

π

.

Definiamo

V

π

(s

)

come:

{

}













=

=

=

=

_∑

∞ =0 + + 1

|

|

)

(

k t k t k t t

s

s

E

r

s

s

R

E

s

V

π _{π π}

γ

{ }

π

E

indica il valore atteso dato dall’agente che segue la strategia

π

. La funzione

π

V

è detta funzione stato-valore per la strategia

π

.

In modo simile il valore associato al fatto di prendere l’azione

a

nello stato

s

con una strategia

π

è

Q

π

( a

s

,

)

esso rappresenta il ritorno atteso che si ottiene partendo dallo stato

s

, prendendo l’azione

a

e seguendo la strategia

π

:

{

}













=

=

+

+

=

=

=

=

∑

∞ =

a

a

s

s

k

r

E

a

a

s

s

R

E

a

s

Q

_{t t} k t k t t t

|

,

1

|

,

)

,

(

0

γ

π π π π

Q

è la funzione azione-valore per la strategia

π

. Il valore delle funzioni

V

πe

π

Q

può essere stimato in base all’esperienza. Per esempio, se un agente segue la strategia

π

e mantiene una media, per ogni stato incontrato, dei ritorni attuali derivanti da ognuno di essi, allora la media convergerà al valore dello stato,

V

π

(s

)

. Se le medie vengono prese separatamente per ogni azione eseguita in uno stato,

allora convergeranno in modo simile ai valori dell’azione

Q

π

( a

s

,

)

. I metodi di stima di questo tipo vengono chiamati metodi Monte Carlo perché coinvolgono le medie di campioni random dei ritorni attuali. Naturalmente se ci fossero molti più stati,non sarebbe possibile considerare le medie in modo separato per ciascuno stato, in tal caso l’agente deve mantenere

V

πe

Q

πcome funzioni parametrizzate e di volta in volta, aggiustare i parametri nel migliore dei modi in base ai ritorni osservati.

Una proprietà fondamentale dei valori delle funzioni usate nel reinforcement learning e nella programmazione dinamica è il soddisfacimento di particolari relazioni ricorsive. Per una strategia

π

e uno stato

s

, la condizione di consistenza seguenti stanno tra i valori di

s

e il valore del suo prossimo successore:

{

=

}

=

∑

∑

+

=

a s a ss a ss t t

s

s

s

a

P

R

V

s

R

E

s

V

' ' '

[

(

'

)]

)

,

(

|

)

(

_π π π

_π

_γ

L’equazione sopra mostrata è l’equazione di Bellman per

V

π. Essa esprime la relazione tra il valore di uno stato e il valore dei suoi stati successivi. Nella figura sottostante sono rappresentati con il cerchio vuoto lo stato e con il cerchio pieno la coppia stato-azione.

Figura 10 - Rappresentazione stato-azione

Partendo dallo stato

s

, il nodo radice in alto, l’agente potrebbe prendere alcune delle azioni appartenenti all’insieme delle azioni sottostanti e ottenere, per ognuna di esse, una risposta dall’ambiente in termini di stati successivi s’ e un rewards r. L’equazione di Bellman calcola la media di tutte le possibilità, pesando ognuna di esse con la sua probabilità di occorrenza

Risolvere un problema di reinforcement learning vuol dire trovare una strategia che ottiene molti reward durante l’elaborazione. Le funzioni del valore ottimale assegnano ad ogni stato, o coppia stato-azione, il più alto ritorno atteso ottenibile da una strategia.

s

a

r

'

Per MDP finiti , può essere definita una strategia ottimale dato che il valore delle funzioni definisce un ordinamento parziale delle strategia. Una strategia

π

è definita migliore di, o uguale ad una strategia

π

'

se il suo ritorno atteso è più grande di, o uguale a

π

'

per tutti gli stati. In altre parole

π

≥

π

'

se e solo se

)

(

)

(

s

V

'

s

V

π

≥

π per tutti gli stati

s

∈

S

. Esiste sempre, almeno una strategia che è migliore o uguale a tutte le altre. Questa è detta strategia ottimale (optimal strategia). Dato che ce ne possono essere più di una, indichiamo le strategie ottimali con

π

*. Queste condividono la stessa funzione stato-valore, chiamata funzione ottimale stato-valore, indicata con

V

* e definita come:

)

(

max

)

(

*

s

V

s

V

a π

=

per ogni stato

s

∈

S

Le strategie ottimali condividono anche la funzione ottimale stato-valore, indicata con

Q

*e definita come:

)

,

(

max

)

,

(

*

a

s

Q

a

s

Q

a π

=

per ogni stato

s

∈

S

e

a

∈

A

(s

)

Per la coppia stato-azione

( a

s

,

)

, questa funzione fornisce il ritorno atteso dall’esecuzione dell’azione

a

nello stato

s

e seguendo una strategia ottimale. A questo punto possiamo scrivere

Q

*in termini di

V

*come segue:

{

r

V

s

s

s

a

a

}

E

a

s

Q

(

,

)

=

t+

+

(

t+1

)

|

t

=

,

t

=

* 1 *

γ

5.1

Esempio griglia del mondo

Supponiamo di voler risolvere l’equazione di ottimalità di Bellman per

V

*per la griglia mostrata in figura:

Figura 11- Griglia del mondo

Lo stato A è seguito da un reward di +10 e la transizione è nello stato A’, mentre lo stato B è seguito da un reward +5 e la transizione è nello stato B’.

La figura sottostante mostra i valori della funzione ottimale e le corrispondenti strategie ottimali. La figura delle strategie ottimali è costituita da molte frecce ognuna corrispondente alle azioni ottimali.

Figura 12 - V* e

π

*: Soluzioni ottimali per la griglia del mondo

La risoluzione dell’equazione di Bellman fornisce un percorso per trovare la strategia ottimale, per la risoluzione dei problemi di reinforcement learning. Tuttavia, la considerazione di tutte le possibilità, il calcolo della loro probabilità di occorrenza e la loro desiderabilità in termini di reward attesi rendono questa soluzione raramente utilizzabile. Infatti, questa soluzione si basa su tre assunzioni:

1) la conoscenza della dinamicità dell’ambiente, 2) Il possesso di un buon numero di risorse computazionali per il calcolo della soluzione, 3) la proprietà di Markov.

Un agente in grado di imparare bene una strategia ottimale è difficile da trovare. Un modello dell’ambiente dinamico, non sempre rende possibile calcolare una strategia ottimale con la risoluzione dell’equazione di Bellman. I computer, per esempio, non sempre sono in grado di calcolare le mosse ottimali per tabelle dei giochi come gli scacchi anche se esse rappresentano una piccola frazione dell’esperienza umana.

5.2

Metodi di risoluzione

Per risolvere i problemi di reinforcement learning esistono tre classi di metodi:

- Programmazione dinamica

- Metodi Monte Carlo

- Temporal-difference learning

Il termine “programmazione dinamica” (DP) si riferisce ad un insieme di algoritmi che possono essere utilizzati per calcolare le strategie ottimali dato un modello perfetto dell’ambiente come il processo di decisione Markoviano (MDP). A causa di queste assunzioni, l’uso di questi modelli è limitato nel reinforcement learning essi risultano molto importanti dal punto di vista teorico.

Assumiamo ancora che il mondo sia MDP, che gli stati e le azioni,

S

e

A

(s

)

, siano finiti e che le dinamiche dell’ambiente siano date da un insieme di probabilità di transizione,

Pss

'

=

Pr

{

s

t+1

=

s

|'

s

t

=

s

,

a

t

=

a

}

, e di rewards attesi,

{

₁

|

,

,

₁

'

}

'

E

r

a

a

s

s

s

s

R

_ssa

=

_{t+ t}

=

_t

=

_t+

=

per ogni stato

s

∈

S

,

a

∈

A

. La programmazione dinamica, attribuisce un valore ai singoli stati V(s), successivamente la scelta del comportamento migliore (o strategia migliore) viene fatta utilizzando questi valori in modo da determinare le singole azioni in base allo stato migliore raggiungibile.

I metodi Monte Carlo usati per la risoluzione di problemi di reinforcement learning si basano sulle medie dei ritorni del campione, essi richiedono soltanto esperienza e campioni delle sequenze di stati, azioni e rewards provenienti da interazioni on-line o da simulazioni con l’ambiente. L’apprendimento dall’esperienza on-line non richiede una conoscenza a priori delle dinamiche dell’ambiente, tuttavia anche l’apprendimento dalle esperienze simulate risulta molto potente. In entrambe i casi è necessario un modello che sia in grado di generare transizioni, non

distribuzioni complete di probabilità delle possibili transizioni che sono richieste dai metodi di programmazione dinamica.

I metodi Monte Carlo si basano sull’esperienza simulata, sono definiti solo per compiti episodici, in cui si assume che l’esperienza sia divisa in episodi e nel caso in cui gli episodi siano in numero finito, solo il completamento dell’episodio stima il valore e cambia la strategia. Più sono numerosi gli episodi più la media approssima l’effettivo valore dello stato.

Per chiarire, i metodi sequenziali di Monte Carlo necessitano di un’organizzazione ad episodi mentre i metodi paralleli della programmazione dinamica necessitano della completa conoscenza del modello degli stati. Tuttavia è possibile pensare ad un metodo tipo quello di Monte Carlo che non necessita di un numero di stati finiti. I modelli di “temporal difference learning” (TD), sono una combinazione di idee dei metodi Monte Carlo e dei metodi di programmazione dinamica. Infatti come i metodi Monte Carlo, possono apprendere direttamente dall’esperienza senza avere un modello delle dinamiche dell’ambiente e come i metodi di programmazione dinamica, modificano le stime basandosi su altre stime apprese.

5.3

Metodo Q-learning

Uno dei migliori successi ottenuti nel reinforcement learning è stato lo sviluppo dell’algoritmo Q-learning appartenente alla TD. Esso cerca la diretta valorizzazione delle associazioni stato-azione

V

( a

s

,

)

. Q sta ad indicare la valorizzazione delle coppie s,a la cui funzione è rappresentata con il simbolo

Q

( a

s

,

)

piuttosto che con

V

( a

s

,

)

. In ogni caso si tratta di ricostruire per ogni stato s, o per ogni coppia,

s,

a

un valore che sia direttamente correlato al reward totale che si può ottenere a partire da quello stato e per il fatto di essere arrivati in quello stato, si tratta quindi di determinare la funzione azione-valore.

Nella forma più semplice un one-step Q-learning è definito come:

)])

,

(

)

,

(

max

[

)

,

(

)

,

(

1 t 1 t 1 t t a t t t t t

a

Q

s

a

r

Q

s

a

Q

s

a

s

Q

←

+

α

₊

+

γ

_{+ +}

−

In questo caso, la funzione azione-valore,

Q

, è approssimata a

Q

*, la funzione azione-valore ottimale. Questa semplifica le analisi dell’algoritmo e attiva delle prove di convergenza. La strategia ha ancora effetto in tutto questo, nel senso

che determina la coppia stato-azione visitata e la modifica. Quello che è richiesto per la convergenza è che tutte le coppie continue siano modificate.

Di seguito è presentato lo pseudo-codice dell’algoritmo Q-learning :

Figura 13 - Algoritmo Q-learning

Le tecniche TD permettono di stimare i valori degli stati o delle coppie

)

,

( a

s

mentre si attraversano gli stati, ovvero mentre si fa vivere l’agente. Per ogni stato o per ogni coppia stato-azione attraversata, si considera lo stato successivo di arrivo e l’azione, che il comportamento impostato sceglierà. Con questo valore e con il reward immediato, si provvederà ad aggiornare la stima del valore medio della coppia

( a

s

,

)

attraversata. Ma se invece di considerare l’azione decisa dal comportamento impostato si considerasse quella con valore

Q

più elevato, la velocità di convergenza migliore non potrebbe che aumentare. Questa è la sostanza del metodo più utilizzato per le applicazioni del reward: Q-learning, esso permette di modificare il comportamento e di aggiornare nel contempo i valori di

Q

passo per passo mentre percorre gli stati, cioè mentre agisce nell’ambiente, come mostra la seguente figura:

Figura 14 - Agente che utilizza il metodo Q-learning

Il Q-learning è un metodo di tipo “Off-policy”, con questo termine si intende un metodo che non aggiorna la valorizzazione degli stati o delle coppie stato-azione in base alla strategia effettivamente seguita, ma in base alla migliore possibilità;

infatti l’aggiornamento del valore

Q

( a

s

,

)

è fatto sulla base della migliore opzione del passo successivo, che non è quella necessariamente utilizzata.

5.4

Esempio del funzionamento del Q-learning

Per illustrare l’operazione dell’algoritmo di Q-learning, si può considerare una singola azione eseguita dall’agente e il corrispondente raffinamento mostrato in figura mostrato nella seguente figura:

Figura 15 – Esempio Q-learning

La figura a sinistra mostra lo stato iniziale s1 del robot R e i valori di

Q

dell’ipotesi iniziale. Per esempio, il valore Q(s₁,a_destra)=72,

a

_destrasi riferisce all’azione che fa muovere il robot verso destra. Quando il robot esegue l’azione

a

_destra, riceve il reward immediato

r

=

0

e si sposta nello stato

s

₂. Dopo di che modifica la sua stima Q(s₁,a_destra) in base alla stima di

Q

per il nuovo stato

s

₂.

) ' , ( max ) , (s1 a r _' Q s2 a Q a destra ← +γ

{

63,81,100

}

max 9 , 0 0+ ← 90 ←

In questo esempio, l’agente si muove nella cella di destra nella sua griglia del mondo ricevendo un reward immediato pari a zero per la transizione. Successivamente applica la seguente regola per ridefinire la stima di Q per la transizione stato-azione appena eseguita:

) ' , ' ( max ) , ( ' Q s a r a s Q a

γ

+ ← destra

a

Secondo questa regola, la nuova stima di Q per la transizione è data dalla somma del reward ricevuto che è pari a zero, e del più alto valore di

Q

associato allo stato risultante che in questo caso è 100, scontato di

γ

pari a 0,9.

Ogni volta che l’agente si muove dal vecchio al nuovo stato, l’algoritmo del Q learning, propaga la stima di

Q

all’indietro dal nuovo al vecchio stato. Allo stesso tempo, il reward immediato ricevuto dall’agente per la transizione viene utilizzato per aumentare questi valori propagati di

Q

.

5.5

Considerazioni conclusive

Nel capitolo sono stati chiariti i principali concetti alla base del reinforcement learning, un agente o un robot deve formulare la migliore strategia, quella che gli consente di ottenere un più alto guadagno, scegliendo ad ogni passo la migliore coppia azione-stato e tenendo conto anche dei pagamenti ricevuti in passato, solo così è possibile realizzare un apprendimento con rinforzo.

Nel prossimo capitolo sarà presentato un progetto basato proprio sui principi di reinforcement learning.