Introduzione al Q-Learning: un tutorial per principianti

Il reinforcement learning (RL) è l’area del machine learning in cui l’agente impara interagendo con l’ambiente per ottenere la strategia ottimale per raggiungere gli obiettivi. È piuttosto diverso dagli algoritmi di machine learning supervisionato, dove dobbiamo ingerire ed elaborare i dati. Il reinforcement learning non richiede dati a priori: impara invece dall’ambiente e dal sistema di ricompense per prendere decisioni migliori.

Per esempio, nel videogioco di Mario, se un personaggio compie un’azione casuale (ad es. si muove a sinistra), in base a quell’azione può ricevere una ricompensa. Dopo aver agito, l’agente (Mario) si trova in un nuovo stato e il processo si ripete finché il personaggio non raggiunge la fine del livello o muore. 

Questo episodio si ripeterà più volte finché Mario non imparerà a muoversi nell’ambiente massimizzando le ricompense. 

Immagine dell’autore

Possiamo scomporre il reinforcement learning in cinque semplici passaggi:

1. L’agente si trova nello stato zero in un ambiente.
2. Compie un’azione in base a una strategia specifica.
3. Riceve una ricompensa o una penalità in base a quell’azione.
4. Impara dalle mosse precedenti e ottimizza la strategia. 
5. Il processo si ripete finché non si trova una strategia ottimale. 

Approfondisci leggendo il nostro tutorial, un’Introduzione al Reinforcement Learning. Esplorerai in dettaglio come funziona il reinforcement learning con esempi di codice. 

In questo tutorial impareremo il Q-learning e capiremo perché abbiamo bisogno del Deep Q-learning. Inoltre, vedremo come creare e addestrare algoritmi di Q-learning da zero usando Numpy e OpenAI Gym.

Nota: se sei alle prime armi con il machine learning, ti consigliamo il nostro percorso di carriera Machine Learning Scientist with Python per comprendere meglio Reinforcement Learning e Q-Learning. 

Che cos’è il Q-Learning?

Il Q-learning è un algoritmo model-free, value-based, off-policy che trova la migliore sequenza di azioni in base allo stato corrente dell’agente. La “Q” sta per quality, ovvero qualità. La qualità rappresenta quanto sia utile un’azione nel massimizzare le ricompense future.  

Gli algoritmi model-based usano funzioni di transizione e di ricompensa per stimare la politica ottimale e creare il modello. Al contrario, gli algoritmi model-free imparano le conseguenze delle proprie azioni tramite l’esperienza, senza funzioni di transizione e ricompensa. 

Il metodo value-based addestra la funzione di valore per apprendere quali stati sono più vantaggiosi e agire di conseguenza. I metodi policy-based, invece, addestrano direttamente la politica per imparare quale azione intraprendere in un determinato stato.

Nell’off-policy, l’algoritmo valuta e aggiorna una politica diversa da quella usata per agire. Al contrario, l’algoritmo on-policy valuta e migliora la stessa politica usata per agire.  

Terminologia chiave nel Q-learning

Prima di vedere come funziona il Q-learning, dobbiamo imparare alcune terminologie utili per capirne le basi. 

• Stati (s): la posizione corrente dell’agente nell’ambiente. 
• Azione (a): un passo compiuto dall’agente in un determinato stato. 
• Ricompense: per ogni azione, l’agente riceve una ricompensa o una penalità. 
• Episodi: la fine del livello, quando l’agente non può più agire. Succede quando l’agente ha raggiunto l’obiettivo o ha fallito. 
• Q(S_t+1, a): valore Q ottimale atteso dell’esecuzione dell’azione in un determinato stato. 
• Q(S_t, A_t): la stima corrente di Q(S_t+1, a).
• Q-Table: la tabella che l’agente mantiene con insiemi di stati e azioni.
• Temporal Differences (TD): usate per stimare il valore atteso di Q(S_t+1, a) impiegando stato e azione correnti e precedenti. 

Come funziona il Q-Learning?

Vedremo in dettaglio come funziona il Q-learning usando l’esempio di un lago ghiacciato. In questo ambiente, l’agente deve attraversare il lago congelato dall’inizio al traguardo, senza cadere nelle buche. La strategia migliore è raggiungere l’obiettivo seguendo il percorso più breve. 

Gif dell’autore

Q-Table

L’agente userà una Q-table per scegliere l’azione migliore possibile in base alla ricompensa attesa per ciascuno stato dell’ambiente. In parole semplici, una Q-table è una struttura dati con insiemi di azioni e stati, e usiamo l’algoritmo di Q-learning per aggiornare i valori nella tabella. 

Q-Function

La Q-function usa l’equazione di Bellman e prende in input stato (s) e azione (a). L’equazione semplifica il calcolo dei valori di stato e dei valori stato-azione. 

Immagine da freecodecamp.org

Algoritmo di Q-learning

Immagine dell’autore

Inizializzare la Q-Table

Per prima cosa inizializzeremo la Q-table. Costruiremo la tabella con colonne in base al numero di azioni e righe in base al numero di stati.

Nel nostro esempio, il personaggio può muoversi su, giù, sinistra e destra. Abbiamo quattro azioni possibili e quattro stati (inizio, inattivo, percorso sbagliato e fine). Puoi anche considerare il percorso sbagliato come la caduta in una buca. Inizializzeremo la Q-Table con valori pari a 0. 

Immagine dell’autore

Scegliere un’azione

Il secondo passaggio è piuttosto semplice. All’inizio, l’agente sceglierà un’azione casuale (giù o destra) e, alla seconda esecuzione, userà una Q-Table aggiornata per selezionare l’azione. 

Eseguire un’azione

Scegliere ed eseguire un’azione si ripeterà più volte finché l’anello di training non si interrompe. La prima azione e il primo stato sono selezionati usando la Q-Table. Nel nostro caso, tutti i valori della Q-Table sono zero. 

Quindi, l’agente si muoverà verso il basso e aggiornerà la Q-Table usando l’equazione di Bellman. A ogni mossa aggiorneremo i valori nella Q-Table e la useremo anche per determinare la migliore linea d’azione. 

Inizialmente, l’agente è in modalità esplorazione e sceglie un’azione casuale per esplorare l’ambiente. La strategia Epsilon-Greedy è un metodo semplice per bilanciare esplorazione e sfruttamento. Epsilon indica la probabilità di scegliere l’esplorazione e, quando è bassa, di privilegiare lo sfruttamento. 

All’inizio, il tasso di epsilon è più alto, il che significa che l’agente esplora. Man mano che esplora l’ambiente, l’epsilon diminuisce e l’agente inizia a sfruttarlo. Durante l’esplorazione, a ogni iterazione l’agente diventa più sicuro nel stimare i valori Q.

Immagine dell’autore

Nell’esempio del lago ghiacciato, l’agente non conosce l’ambiente, quindi all’inizio compie un’azione casuale (muoversi in basso). Come si vede nell’immagine sopra, la Q-Table viene aggiornata usando l’equazione di Bellman.

Misurare le ricompense

Dopo aver eseguito l’azione, misureremo l’esito e la ricompensa. 

• La ricompensa per raggiungere l’obiettivo è +1
• La ricompensa per prendere il percorso sbagliato (cadere nella buca) è 0
• La ricompensa per essere inattivo o muoversi sul lago ghiacciato è anch’essa 0. 

Aggiornare la Q-Table

Aggiorneremo la funzione Q(S_t, A_t) usando l’equazione. Utilizza le stime dei valori Q dell’episodio precedente, il learning rate e l’errore di Temporal Differences. L’errore di Temporal Differences si calcola usando la ricompensa immediata, la massima ricompensa futura attesa scontata e la stima precedente del valore Q. 

Il processo si ripete più volte finché la Q-Table non è aggiornata e la funzione di valore Q è massimizzata. 

Immagine dell’autore | Visualizzazione dell’equazione di Thomas Simonini

All’inizio, l’agente esplora l’ambiente per aggiornare la Q-table. Quando la Q-Table è pronta, l’agente inizia a sfruttarla e a prendere decisioni migliori. 

Immagine dell’autore

Nel caso del lago ghiacciato, l’agente imparerà a seguire il percorso più breve per raggiungere l’obiettivo ed evitare di saltare nelle buche. 

Tutorial Python sul Q-Learning 

In questa sezione costruiremo il nostro modello di Q-learning da zero usando l’ambiente Gym, Pygame e Numpy. Il tutorial Python è una versione modificata del Notebook di Thomas Simonini. Include l’inizializzazione dell’ambiente e della Q-Table, la definizione della politica greedy, l’impostazione degli iperparametri, la creazione ed esecuzione del ciclo di training e della valutazione, e la visualizzazione dei risultati.   

Se riscontri problemi nel creare ed eseguire il tuo ciclo di training, puoi consultare il codice sorgente con l’output.   

Configurazione

Impostare un display virtuale

Per prima cosa installeremo tutte le dipendenze per generare un video di replay (Gif). Avremo bisogno di uno schermo virtuale (pyvirtualdisplay) per renderizzare l’ambiente e registrare i frame. 

Nota: usando %%capture sopprimiamo l’output della cella Jupyter. 

%%capture
!pip install pyglet==1.5.1
!apt install python-opengl
!apt install ffmpeg
!apt install xvfb
!pip3 install pyvirtualdisplay

# Virtual display
from pyvirtualdisplay import Display

virtual_display = Display(visible=0, size=(1400, 900))
virtual_display.start()

Installare le dipendenze

Ora installeremo le dipendenze che ci aiuteranno a creare, eseguire e valutare il ciclo di training. 

• gym: usato per inizializzare l’ambiente FrozenLake-v1.
• pygame: usato per l’interfaccia di FrozenLake-v1.
• numPy: usato per creare e gestire la Q-table.

%%capture
!pip install gym==0.24
!pip install pygame
!pip install numpy

!pip install imageio imageio_ffmpeg

Importare i pacchetti

Ora importeremo le librerie necessarie. 

• Imageio è usata per creare l’animazione. 
• tqdm è usata per le barre di avanzamento. 

import numpy as np
import gym
import random
import imageio
from tqdm.notebook import trange

Ambiente Gym Frozen Lake 

Creeremo un ambiente 4x4 non scivoloso usando la libreria Gym Frozen Lake. 

• Ci sono due versioni della griglia, “4x4” e “8x8”.
• Se is_slippery=True, l’agente potrebbe non muoversi nella direzione prevista a causa della natura scivolosa del lago ghiacciato. 

Dopo aver inizializzato l’ambiente, faremo un’analisi dell’ambiente. 

env = gym.make("FrozenLake-v1",map_name="4x4",is_slippery=False)

print("Observation Space", env.observation_space)
print("Sample observation", env.observation_space.sample()) # display a random observation

Ci sono 16 spazi unici nell’ambiente mostrati in posizioni casuali. 

Observation Space Discrete(16)
Sample observation 15

Scopriamo il numero di azioni e mostriamo un’azione casuale. 

Spazio delle azioni:

• 0: muoversi a sinistra
• 1: muoversi in basso
• 2: muoversi a destra
• 3: muoversi in alto

Funzione di ricompensa:

• Raggiungere l’obiettivo: +1
• Cadere nella buca: 0
• Restare sul lago ghiacciato: 0

print("Action Space Shape", env.action_space.n)
print("Action Space Sample", env.action_space.sample())

Action Space Shape 4
Action Space Sample 1

Creare e inizializzare la Q-table

La Q-Table ha come colonne le azioni e come righe gli stati. Possiamo usare OpenAI Gym per trovare lo spazio delle azioni e quello degli stati. Useremo poi queste informazioni per creare la Q-Table. 

state_space = env.observation_space.n
print("There are ", state_space, " possible states")

action_space = env.action_space.n
print("There are ", action_space, " possible actions")

There are  16  possible states
There are  4  possible actions

Per inizializzare la Q-Table, creeremo un array Numpy di state_space e action_space. Creeremo un array 16 x 4. 

def initialize_q_table(state_space, action_space):
  Qtable = np.zeros((state_space, action_space))
  return Qtable

Qtable_frozenlake = initialize_q_table(state_space, action_space)

Politica epsilon-greedy

Nella sezione precedente abbiamo visto la strategia epsilon-greedy che gestisce il compromesso tra esplorazione e sfruttamento. Con probabilità 1 - ɛ, sfruttiamo; con probabilità ɛ, esploriamo. 

Nella epsilon_greedy_policy faremo:

1. Generare un numero casuale tra 0 e 1.
2. Se il numero casuale è maggiore di epsilon, sfrutteremo: l’agente sceglie l’azione con il valore più alto dato uno stato.
3. Altrimenti, esploreremo (azione casuale). 

def epsilon_greedy_policy(Qtable, state, epsilon):
  random_int = random.uniform(0,1)
  if random_int > epsilon:
    action = np.argmax(Qtable[state])
  else:
    action = env.action_space.sample()
  return action

Definire la politica greedy

Ora sappiamo che il Q-learning è un algoritmo off-policy, il che significa che la politica per agire e quella per l’aggiornamento sono diverse. 

In questo esempio, la politica Epsilon-Greedy è la politica di azione, e la politica Greedy è quella di aggiornamento. 

La politica Greedy sarà anche la politica finale quando l’agente è addestrato. Viene usata per selezionare dalla Q-Table il valore stato-azione più alto.

def greedy_policy(Qtable, state):
  action = np.argmax(Qtable[state])
  return action

Iperparametri del modello

Questi iperparametri sono usati nel ciclo di training e, calibtrandoli, otterrai risultati migliori. 

L’agente deve esplorare a sufficienza lo spazio degli stati per apprendere una buona approssimazione dei valori; è quindi necessario un decadimento progressivo di epsilon. Se il tasso di decadimento è alto, l’agente potrebbe bloccarsi perché non ha esplorato abbastanza lo spazio degli stati.

• Ci sono 10.000 episodi di training e 100 di valutazione.
• Il learning rate è 0,7.
• Usiamo "FrozenLake-v1" come ambiente con 99 passi massimi per episodio.
• Il gamma (tasso di sconto) è 0,95.
• eval_seed: seed di valutazione per l’ambiente.
• La probabilità epsilon di esplorazione all’inizio è 1,0 e la probabilità minima sarà 0,05.
• Il tasso di decadimento esponenziale per epsilon è 0,0005.

# Training parameters
n_training_episodes = 10000
learning_rate = 0.7        

# Evaluation parameters
n_eval_episodes = 100      

# Environment parameters
env_id = "FrozenLake-v1"   
max_steps = 99             
gamma = 0.95               
eval_seed = []             

# Exploration parameters
max_epsilon = 1.0           
min_epsilon = 0.05           
decay_rate = 0.0005           

Training del modello 

Nel ciclo di training faremo:

1. Creare un ciclo per gli episodi di training.
2. Per prima cosa ridurremo epsilon. A ogni episodio serve meno esplorazione e più sfruttamento. 
3. Resettare l’ambiente.
4. Creare un ciclo annidato per i passi massimi.
5. Scegliere l’azione usando la politica epsilon-greedy. 
6. Compiere l’azione (A_t) e osservare la ricompensa attesa (R_t+1) e lo stato (S_t+1).
7. Compiere l’azione (a) e osservare il nuovo stato (s') e la ricompensa (r).
8. Aggiornare la Q-function usando la formula. 
9. Se done= True, concludere l’episodio e interrompere il ciclo.
10. Infine, passare dallo stato corrente al nuovo stato. 
11. Al termine di tutti gli episodi di training, la funzione restituirà la Q-Table aggiornata. 

def train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable):
  for episode in trange(n_training_episodes):
 
    epsilon = min_epsilon + (max_epsilon - min_epsilon)*np.exp(-decay_rate*episode)
    # Reset the environment
    state = env.reset()
    step = 0
    done = False

    # repeat
    for step in range(max_steps):
   
      action = epsilon_greedy_policy(Qtable, state, epsilon)

   
      new_state, reward, done, info = env.step(action)

   
      Qtable[state][action] = Qtable[state][action] + learning_rate * (reward + gamma * np.max(Qtable[new_state]) - Qtable[state][action])

      # If done, finish the episode
      if done:
        break
     
      # Our state is the new state
      state = new_state
  return Qtable

Abbiamo impiegato 3 secondi per completare 10.000 episodi di training. 

Qtable_frozenlake = train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable_frozenlake)

Come si vede, la Q-Table addestrata ha dei valori e l’agente ora userà questi valori per navigare nell’ambiente e raggiungere l’obiettivo.  
Qtable_frozenlake
array([[0.73509189, 0.77378094, 0.77378094, 0.73509189],
      [0.73509189, 0.        , 0.81450625, 0.77378094],
      [0.77378094, 0.857375  , 0.77378094, 0.81450625],
      [0.81450625, 0.        , 0.77378094, 0.77378094],
      [0.77378094, 0.81450625, 0.        , 0.73509189],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.        , 0.81450625],
      [0.        , 0.        , 0.        , 0.        ],
      [0.81450625, 0.        , 0.857375  , 0.77378094],
      [0.81450625, 0.9025    , 0.9025    , 0.        ],
      [0.857375  , 0.95      , 0.        , 0.857375  ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.95      , 0.857375  ],
      [0.9025    , 0.95      , 1.        , 0.9025    ],
      [0.        , 0.        , 0.        , 0.        ]])
Valutazione
La funzione evaluate_agent esegue n_eval_episodes episodi e restituisce media e deviazione standard della ricompensa. 

Nel ciclo, controlleremo per prima cosa se è presente un seed di valutazione. In caso contrario, resetteremo l’ambiente senza seed. 
Il ciclo annidato verrà eseguito fino a max_steps.
L’agente compirà l’azione che ha la massima ricompensa futura attesa in un dato stato usando la Q-Table. 
Calcolare la ricompensa.
Cambiare lo stato.
Se done (l’agente cade nella buca o l’obiettivo è raggiunto), interrompere il ciclo.
Accodare i risultati.
Alla fine useremo questi risultati per calcolare media e deviazione standard. 

def evaluate_agent(env, max_steps, n_eval_episodes, Q, seed):

  episode_rewards = []
  for episode in range(n_eval_episodes):
    if seed:
      state = env.reset(seed=seed[episode])
    else:
      state = env.reset()
    step = 0
    done = False
    total_rewards_ep = 0
   
    for step in range(max_steps):
      # Take the action (index) that have the maximum reward
      action = np.argmax(Q[state][:])
      new_state, reward, done, info = env.step(action)
      total_rewards_ep += reward
       
      if done:
        break
      state = new_state
    episode_rewards.append(total_rewards_ep)
  mean_reward = np.mean(episode_rewards)
  std_reward = np.std(episode_rewards)

  return mean_reward, std_reward
Come puoi vedere, abbiamo ottenuto il punteggio perfetto con deviazione standard pari a zero. Significa che il nostro agente ha raggiunto l’obiettivo in tutti i 100 episodi. 
# Evaluate our Agent
mean_reward, std_reward = evaluate_agent(env, max_steps, n_eval_episodes, Qtable_frozenlake, eval_seed)
print(f"Mean_reward={mean_reward:.2f} +/- {std_reward:.2f}")
Mean_reward=1.00 +/- 0.00
Visualizzare il risultato
Finora abbiamo lavorato con i numeri e, per la demo, dobbiamo creare una Gif animata dell’agente dall’inizio fino al raggiungimento dell’obiettivo. 

Per prima cosa creeremo lo stato resettando l’ambiente con un intero casuale tra 0 e 500. 
Renderizzeremo l’ambiente usando rdb_array per creare un array di immagini. 
Poi aggiungeremo l’img all’array images. 
Nel ciclo, faremo lo step usando la Q-Table e renderizzeremo l’immagine a ogni passo. 
Infine, useremo questo array e imageio per creare una Gif di un fotogramma al secondo. 

def record_video(env, Qtable, out_directory, fps=1):
  images = [] 
  done = False
  state = env.reset(seed=random.randint(0,500))
  img = env.render(mode='rgb_array')
  images.append(img)
  while not done:
    # Take the action (index) that have the maximum expected future reward given that state
    action = np.argmax(Qtable[state][:])
    state, reward, done, info = env.step(action) # We directly put next_state = state for recording logic
    img = env.render(mode='rgb_array')
    images.append(img)
  imageio.mimsave(out_directory, [np.array(img) for i, img in enumerate(images)], fps=fps)
Se sei in un notebook Jupyter, puoi visualizzare la Gif usando la funzione Image di IPython.display. 
video_path="/content/replay.gif"
video_fps=1
record_video(env, Qtable_frozenlake, video_path, video_fps)

from IPython.display import Image
Image('./replay.gif')
Ora puoi condividere questi risultati con colleghi e compagni di corso oppure pubblicarli sui social.