esercizi Reinforcement Learning Note: La maratona Definizione di stato

Reinforcement Learning

esercizi

Reinforcement Learning La maratona

Trovare affitto

Primo appuntamento TORCS

Washing machine

Note:

Dopo averne mostrato questi esercizi al Bonarini è emerso che

1)tutto è chiaramente più prolisso di quello che si riesce a fare in esame

2)le riflessioni sulla topologia del modello sono superflue anche se penso possano essere utili per ragionare in termini di MDP rispetto a che risultati ci si aspetta dall’ apprendimento

3) il docente ha avuto periodi molto creativi rispetto ai temi d’ esame

La maratona

Si progetti un sistema di apprendimento per rinforzo in grado di apprendere la strategia migliore per affrontare positivamente una maratona (circa 42 Km di corsa). Considerare le grandezze ritenute significative per un approccio semplificato. Modellare il problema, specificando gli stati, le azioni possibili (che saranno in grado di far passare l’agente da uno stato all’altro), e una funzione di rinforzo. Motivare la scelta di un opportuno algoritmo di distribuzione del rinforzo per questa applicazione, data la modellizzazione scelta.

Definizione di stato

si prenderà per stato la tupla <x,d> dove:

x è un intero associato alla posizione sul percorso con una granularità di 50 metri d in {no,poco,medio,molto} rappresenta il dolore e la stanchezza fisica percepiti dall attleta

La definizione di x è motivata dalla mia personale esperienza (pur non essendo un maratoneta) : correndo penso spesso a quanto manca alla fine del percorso con una granularità simile.

Azioni

a in {sosta,camminare,marciare,correre,scatto}

Topologia del modello

considerando l' ordinamento su A basato sulla velocità attesa sosta<camminare<marciare<correre<scatto

e un ordinamento su D

no<poco<medio<molto

il modello puo essere desciritto come segue:

un azione a conduce da uno stato <x,d> a uno stato <x',d'> con probabilità P( a(<x,d>,<x',d'>) );

possiamo imporre che il maratoneta non torni indietro a(<x,d>,<x',d'>) => x'>=x;

che verosimilmente correndo più veloce si percorra più strada per ogni <x0,d0>

P(x'>x|a(<x0,d0>,<x,>),a'(<x0,d0>,<x',>),a'>a) > 0.5;

ma ci si stanchi di più per ogni <x0,d0>

P(d'>d|a(<x0,d0>,<,d>),a'(<x0,d0>,<,d'>),a'>a) > 0.5;

Gli stati si possono rappresentare su una griglia ma si deve tener presente che l agente si muove sempre verso la meta ma non con continuità rispetto alla griglia( puo "saltare" se percorre piu di 50 metri in un "turno"). Il modello assomiglia per certi versi ad una versione semplificata del gioco formula dè

Ricompense

Ad ogni step un reward associa un vantaggio alla distanza percorsa e uno svantaggio se il livello di dolore è alto

r=|x'­x| ­ (d==molto)?penalità:0

Apprendimento

Il costo dell' apprendimento è molto "umano" e richiede di correre ripetutamente sul tracciato. Il modello è esteso (circa 3500 stati)  e non è noto negli effettivi valori delle probabilità di

transizione.

Per scegliere un algoritmo escludo subito DP : non ho il modello delle probabilità di transizione.

Valuto un aspetto umano : "affrontare positivamente una maratona" è molto simile e altrettanto desiderabile a "affrontare positivamente un allenamento per una maratona". Questo mi porta ad escludere monte carlo e q learning perchè l attleta non puo correre il rischio dovuto a policy casuali o esplorative . Se la policy serve anche a proteggere l attleta l' apprendimento deve essere on­policy. Scelgo quindi TD(lambda). La permanenza delle tracce di eligibilità deve

essere tale da associare la condizione di stanchezza o dolore ad uno sforzo precedente.

Trovare affitto

Si progetti un sistema di apprendimento per rinforzo in grado di apprendere la strategia migliore per trovare un appartamento da affittare a Milano. Considerare le grandezze ritenute significative per un approccio semplificato. Modellare il problema, specificando gli stati, le azioni possibili (che saranno in grado di far passare l’agente da uno stato all’altro), e una funzione di rinforzo.

Motivare la scelta di un opportuno algoritmo di distribuzione del rinforzo per questa applicazione, data la modellizzazione scelta.

Riflessioni preliminari

locazione n_stanze area trasporti servizi risorse:

denaro

tempo(per trovare casa)

chi è l agente? qual' è il rapporto tra il suo stato e le sue decisioni? qual' è l architettura informativa di una città?

L' apprendimento è un processo che si basa sull' esperienza. Considerato che la maggior parte delle persone affitta non più di 20 case nella sua vita (stima larga) il sistema di apprendimento deve per forza concertare l' esperienza di più persone. A questo punto il sistema prende (quasi necessariamente) la forma di un questionario, non sarà progettato come un sistema di

apprendimento automatico ma come un sistema che deve invogliare persone ad inserire dati significativi. Le informazioni raccolte saranno parziali perchè non si potrà chiedere molto tempo o sforzo all' utente. Il questionario definisce un numero di canali

*passaparola

*agenzia immobiliare

*bacheche

*annunci gratuiti online

*annunci a pagamento online

*girando per strada

per ciascun canale all' utente è chiesto se è stato usato nella ricerca dell’ ultima casa affittata.

Viene poi chiesto quale canale ha permesso di trovare l’ abitazione scelta alla fine del processo.

Il modello comprende un solo stato effettivo, ciascun canale è modellato come un azione e le transizioni sono banali. Per dovere di completezza si aggiunge uno stato pozzo con il significato di "ho trovato casa".

Il sistema assomiglia vagamente all' apprendimento per simulazioni di montecarlo se si assume

che gli intervistati seguono policy casuali o comunque non controllate. Il reward è distribuito una volta che la casa è stata scelta. Si potrebbe rilevare il gradimento dell' abitazione e assegnarlo come reward ma la percezione di qualità sarebbe molto soggettiva ed è quindi consigliabile assegnare un reward fisso al raggiungimento dello stato pozzo.

E' più difficile spiegare il sistema come reinforcement learning che implementarlo (questionario+foglio di calcolo).

Primo appuntamento

Si progetti un sistema di apprendimento per rinforzo in grado di apprendere la strategia migliore per affrontare il primo incontro con un potenziale partner.

Considerare le grandezze ritenute significative per un approccio semplificato. Modellare il

problema,specificando gli stati, le azioni possibili, e una funzione di rinforzo. Motivare la scelta di un opportuno algoritmo di distribuzione delrinforzo per questa applicazione, data la

modellizzazione scelta.

?? no dai...

TORCS

Si progetti un sistema di apprendimento per rinforzo in grado di apprendere il comportamento di un sistema automatico che possa giocare a un videogame guidando un’automobile da corsa simulata. Il sistema deve apprendere una strategia di gioco che si avvicini a quella di un utente il cui comportamento viene rilevato. Si considerino solo 1­2 situazioni semplici e stereotipate.

Considerare le grandezze ritenute significative e che possano essere rilevate in un sistema del genere. Modellare il problema, specificando gli stati, le azioni possibili (che saranno in grado di far passare l’agente da uno stato all’altro), e una funzione di rinforzo. Motivare la scelta di un opportuno algoritmo di distribuzione del rinforzo per questa applicazione, data lamodellizzazione scelta e le ipotesi fatte.

Azioni

sterzo s in {sx,no ,dx}

acceleratore a in {freno,stabile,sostenuto,massimo}

Stati

tuple <p,v,b,m,pn,d>

segmento attuale p in {retilineo,curva_dx,curva_sx}

velocità v in {fermo ...elevata}

distanza bordo b in {lontano, vicino , prossimo}x{bordoSx,BordoDx}

margine di cambio m in {lontano, vicino , prossimo}

prossimo segmento pn in{retilineo,curva_dx,curva_sx}

distanza dall' asse     d in {margine dx , dx , centro ,sx , margine sx}

problema : gli stati sono tanti…

[La semantica dello stato è esposta da un disegno a matita sul foglio, qui manca , scusate]

Rinforzi

penalità: si calcolino

p_tempo= differenza tra il tempo di percorrenza del segmento del giocatore e del bot p_traiettoria= area tra le traiettorie del bot e del giocatore

reward: alla fine di ogni scenario viene dato un reward r=exp(­ptempo ­alfa* p_traiettoria)

Modello e scelta algoritmo

il modello del mondo è noto: c' è un videogioco deterministico. Tuttavia il modello considerato è semplificato rispetto al motore fisico del gioco=> no markovianità.

il modello dell' obiettivo : è noto solo alcune specifiche "giocate"

algoritmo : montecarlo simulando sugli specifici scenari coperti dalle piste giocate

Washing machine

Design a Reinforcement learning system to learn the optimal policy of a washing machine to optimize energy and water use, by maintaining an acceptable washing quality. let us assume that the situation the washing machine can be in are fixed a priori, that they be in a finite number, and that they be defined by the state of the machine, (ectrovalve controlling the water input

open/close, slow handling (for washing and rinsing)), fast movement (for centrifuge)) and time spent in a given state (discretized with 1 minute granularity).

Possible actions are those allowing to pass from one state to another, and are

selected every minute; among them we have also the one doing nothing (NOP). Finally,

measures of water and energy use are available, as well as a 3­valued evaluation of the washing quality (good, acceptable, unacceptable)

Model the problem, specifying the states, the possible actions (that enable the agent to pass from one state to another), and a reinforcement function. Justify the choice of a reinforcement distribution algorithm for this application,on the basis of the selected model.

States

tuples <t,v,m> in S permanence int t

valve v in {open/closed}

movement m in {stop,slow,fast}

An additional state <wait> is added as both an initial and a final state to allow human operators to safely manipulate the machine.

A time independent state may be defined by the simple projection

<t,v,m> ­> <v,m>

<t,v,m> in S => <v,m> in Si

Actions and Model

An action is defined for each time independent state.

a(<v,m>)  for each <v,m> in Si

The outcome of an action is deterministic in the state/action model described and result in either 1. a transition from the original state to the time independent state that define the action with

t=0

2. an increment of t in case of a NOP a(<v,m>) : S­>S

for each <v0,m0,t0> in S

a(<v’,m’>) (<v0,m0,t0>)  = <0,v’,m’>  iff  <v’,m’>!=<v0,m0>

<t0+1,v0,m0> iff  <v’,m’>==<v0,m0>

a(<wait>)(<v0,m0,t0>)= <wait>;

a(<wait>)(<wait>)= <wait>;

Their outcome is deterministic as they control the operating state of the machine not the one of the clothes to be washed. There is a state (the one of the clothes) that is actually hidden until the inspection that will be at the end of the episode.

safety constraint for all policies :

p(<wait>)=a(<wait>) until the operator press the start button

Reinforcement

Given at the end of the washing episode, it s a sum of bonus 100 for acceptable quality

bonus 50 for good quality

a weighted penalty for Watt*hour used a weighted penalty for time spent a weighted penalty for water used to be given at the end of the wash but : no reward at all for unaceptable results!

want real weights? ask marketing . They will first say "give maximum priority to everything!" . Make them reason and plan a product differentiation strategy... one problem at a time...

Learning:

If we can build a computable model to simulate the outcomes(in terms of quality , energy and water) of a wash episode monte carlo may be an effective and low cost way to develop a policy (computer simulation is cheaper than setting up real world experiments).

If the computable model can provide an indicator of the outcomes at each step the model will allow to use dynamic programming.

Otherwise the cost of setting up experiments (washing machines, cost of human supervision) will drive the choice of a learning algorithm toward one that requires less trials. Q learning may be that algorithm. The explorative policy may be developed by adding probabilistic uncertainty to the firmware of a previous product and if possible should be short in time to distribute reward to selected state­action pairs and be quicker in time (saving on human supervision costs).