Sessione 3 (Metodo Montecarlo)

Il Metodo Montecarlo (MC) migliora la policy iteragendo con l'ambiente e ottenendo dei ritorni (scantati da gamma) di cui viene calcolata la media. Per la legge dei grandi numeri più osservazioni (e quindi ritorni) otteniamo più ci avviciniamo al valore ottimale atteso Vπ(S).

Dalla formula si evince che il limite per n che tende a infinto dove n è il numero di misurazioni, genera una stima dei valori degli stati con probabilià 100% di essere ottimale.

Il MC ha dei vantaggi rispetto al DP (dynamic programmig spiegata nella sessione 2):

la stima dei valori degli stati non dipende dagli altri
il costo per stimare il valore di uno stato è indipendente dal numero toale degli stati

Nel caso del DP l'algoritmo bootstrappa il valore degli altri stati in modo da utilizzare una stima per produrne un'altra. Per questo la complessità di un algoritmo cresce esponenzialmente con il numero di stati.

Cosa molto importante MD non necessita del modello, la dinamica dell'ambiete sarà implicita nella nostra stima.

Per risolvere l'algorimo del MC verrà utilizzato il metodo, visto in precedenza anche con il DP detto "Generalized Policy Iteration".

Generalized Policy Iteration

La GPI si basa sulla valutazione della policy (partendo da una che può essere randomica o arbitraria) per poi migliorarla e looppando fino a quando non si arriva a quella ottiamale.

MC si elabora generando un episodio la cui traiettoria parte dallo stato iniziale sino allo stato finale durante il qualche vengono raccolte e sommate tutte le ricompense scontate gamma, per ogni stato dell'enviroment.

Bisogna quindi trovare la policy che sceglie l'azione con il Q-Value più alto, nella pratica dovremo tenere traccia nella tabella dei valori, non più i valori degli stati V(s) come nel DP, ma salveremo i valori delle azioni Q(s,a), ovvero dell'azione che massimizza il valore.

Il processo per MC diventerà quindi:

Dove la policy calcola i Q-Value che viene a sua volta utilizzato per migliorare la policy in un ciclo continuo fino ai valori ottimali Q* e π*.

Exploration

Quindi la policy migliora sulla base dell'esperienza che agente effettua mentre interagisce con l'ambiente. L'esperienza che l'agente raccoglie dipende dalle azioni che l'agente effettua, e le azioni dipendono dalla policy che l'agente utilizza in quel momento. Per questo motivo avremo una policy π' che seleziona l'azione sulla base delle stime Q(s,a). E queste stime saranno sempre più accurate soprattutto mentre ci avviciniamo alle fasi finali dell'apprendimento. (a differenza delle fase iniziale dove invece sono inaccurate)

Immaginiamo il caso in cui l'azione è ottimale ma la sua stima Q(s,a) è pessima, allora la policy non la sceglierà in quanto la stima del valore è molto bassa. Si rende quindi necessario che tutte le azioni vengano scelte ogni tanto in maniera casuale per "esplorare" l'ambiente con scelte che normalmente non verrebbero effettuate, ma che possono migliorare la policy anche se apparentemente non nell'immediato. Tutto questo per scoprire eventuali azioni ottimali non considerate dalla policy in uso.

Quindi come mantenere l'esplorazione?

Beh, nella pratica abbiamo due opzioni:

La prima si chiama "exploring starts" e prevede che l'agente inizi la sua esplorazione in uno stato casuale dell'ambiente ed effettui un'azione iniziale casuale. Purtroppo non è una modalità molto realistica in quanto ci sono molti task che semplicamente non hanno questa possibilità. (soprattutto se parliamo del mondo reale)
La seconda si chiama "stocastic policies" ovvero vengono considerate le azioni che hanno una probabilità maggiore di zero, in questo modo ogni tanto vengono prese delle azioni "a caso" che potrebbero aiutare la policy a migliorare grazie al caso. (una sorta di evoluzione naturale della specie :) ) Queta seconda ipotesti è più realista e più facilmente implementabil.

Le policy stocastiche si suddivino in due tipologie:

On-policy learning strategies: la quale genera l'esperienza basandosi nulla stessa policy che stiamo ottimizzando
Off-policy learning strategies: la quale utilizza due policy distinte, una per esplorare l'ambiente e un'altra da ottimizzare

On-policy

Questo metodo segue una strategia che ogni tanto (randomicamente) effettua un'azione a caso, questa policy è chiamata epsiolon-greedy. (ϵ-greedy)

In questa policy ogni azione ha la probabilità di essere eseguita maggiore di zero, ogni volta che bisogna scegliere un'azione ne scegliamo una casuale tra quelle disponibili nello stato con probabilità ϵ (che quindi deve essere abbastanza bassa) mentre nelle restanti probabilità 1-ϵ andiamo a scegliere l'azione con probabilità più alta, ovvero:

come si può vedere dalla formula la probabilità di scegliere l'azione ottimale a* (quindi con la stima q-value più alta) è 1-ϵ sommato alla probabilità di scegliere un'azione casualmente, mentre, per contro, abbiamo la probabilità ϵ di sceglire una azione che potrebbe non essere ottiamale. ϵr rappresenta la probabilità di scegliare un'azione tra tutte le azioeni A disponibili.

Facciamo un esempio:

Abbiamo 4 possibili azioni e un ϵ del 20%, come sotto riportato:

La probabilità di sceglire l'azione con il valore Q(s,a) più alto è 80%.

Quando scegliamo un'azione a caso ϵr, la probabilità di scegliare questa azione è del 0,2/4 che sono le azioni possibili, ovvero del 5%. (o 0,05)

Per questo la probabilità di scegliere un'azione ottimale è del 0,85 (85%) perchè tra le 4 azioni c'è quella migliore (delle 4) che comunque va sommata a 1-ϵ.

Di seguito il pseudo codice che descrive l'alagoritmo:

In input viene passato epsilon e gamma (che ricordo rappresentare il fattore di sconto)

Vediamolo in codice Python.

L'esempio di utilizzo è il classico labirinto 5x5, dove l'agente inizia nell'angolo in alto a sx e finisce il suo percorso in basso a dx.

Per prima inizializziamo la matrice che contiene le azioni effettuabili nello stato con valori zero il cui shape è 5x5x4 dove 5x5 sono gli stati mentre 4 sono le azioni effettuabili in ciascun stato. Il valore per inizializzare scelto è zero ma avrebbe potuto essere un qualsiasi valore arbitrario che il processo di apprendimento avrebbe comunque ottimizzato.

e ora plottiamo la rappresentazione dei Q-values associati a ciascuno stato:

Si possomo vedere i valori per 4 movimenti effettuabili in ciascono.

Creiamo una policy che scelga una azione dato uno stato e la probabilità di scegliere un'azione casuale. (ϵ)

La funzione che sceglie la policy, effettua un'azione a caso tra le 4 disponibili se un numero compreso tra zero e uno, generato randomicamente, è inferiore al epsilon. (prima riga della funzione)

Nel caso invece nel quale si effettui l'azione migliore (1-ϵ) allora vengono in prima battuta estratti i 4 valori Q(s,a) associati allo stato passato in input. Di questi 4 valori viene scelto quello con il Q(s,a) più alto e, nel caso i valori più alti siano indentici tra loro, allora viene effettuata una scelta random tra questi. (vedi ultima riga della funzione)

NOTA: la funzione np.flatnonzero ritorna gli indici di un array che possiedono un valore diverso da zero.

giusto per cuiosità ho estrapolato la parte di codice che esegue l'azione con il Q-value più alto per far vedere come vengono gesiti i casi particolari come più valori identici massimi:

action_values = np.zeros((5,5,4))

def policy(state, epsilon=0.01):
    av= action_values[state]
    print (av.max())
    print (av == av.max())
    print ( np.flatnonzero(av == av.max()))
    return np.random.choice(np.flatnonzero(av == av.max()))


print (policy((0,0)))

0.0
[ True  True  True  True]
[0 1 2 3]
3

Visualizziamo la policy con i valori inizializzati, ovviamente essendo inizializzati l'azione di default è univoca per tutti gli stati.

ora definiamo l'algoritmo principale

def on_policy_mc_control(policy, action_values, episodes, gamma=0.99)
"""
Algoritmo di Montecarlo nella modalità on-policy
policy: funzione policy che scaglie le azioni, spiegata prima e che 
        attinge dalla tabella degli stati (action_values)
action_values: tabella contente tutte le azioni effettuali per tuti gli 
               stati dell'env
episodes: numero di episodi utili per far si che la policy migliori
gamma: fattore di sconto
"""

  # dizionario dove verranno salvati i valori associati alle coppie stato-azione
  sa_return={}

  # main loop
  for episode in range (1, episodes +1)

    # ricavo lo stato iniziale
    state = env.reset()
    
    # flag che determina la fine dell'episodio
    done = False
    
    # lista alla quale appendere i valori ritornanti dall'ambiente a fronte in una zione
    transtions = []

    # loop che gira finchè l'agente trova l'uscita e quindi termoina il task
    while not done:
      
      # effettuo l'azione utilizzando la policy che abbiamo definito (cone random actions)
      action = policy(state, epsilon)

      # salvo le risposte dell'ambiente
      next_state, reward, done, _ = env.step(action)

      # salvo lo stao-azione e la reward ottenuta
      transtions.append ([state,action,reward])

      # salvo il prossimo stato da eseguire
      state = next_state
      
    # inizializzo il rtorno
    G = 0
    
    # calcolo il ritorno in modalità "backword" ovvero dall'ultimo al primo
    for state_t, action_t, reward_t in reverse(transtions)
      G = reward_t + gamma*G

      # se l'elemento non esiste nel dictionary allora lo creo con per la coppia stato-azione
      if not (state_t, action_t) in sa_retutns:        
        sa_returns[(state_t, action_r)] = []

      # aggiungo il ritorno 
      sa_returns[(state_t, action_r)].append(G)

      # salvo nella stato/azione la media dei ritorni per lo stato-azione
      action_vales[state][action] = np.mean (sa_returns[(state_t, action_t)])
      
        
    
# test
on_policy_mc_control(policy, action_values, episodes = 10000)

di seguito la tabella delle azioni ottimali negli stati:

capitolo 46

di seguito la mappa delle azioni migliori che portano alla fine del tastk

capitolo 46

Oltre al set delle azioni migliore si vede come negli stati non ottimali (in alto a dx) le azioni non sono ottimali in quanto, non essendo gli stati azioni ottimali, l'agente le evita tranne per il fatto che ogni le esplora casualmente.

Ottimizzazione On-Policy

capitolo 48