Q-Learning: teoria

Il Q-Learning è un algoritmo utilizzato durante l’addestramento di reti neurali basati un reinforced learning. Infatti egli funziona attribuendo un “premio” in base all’azione eseguita, il premio sarà alto quando l’azione compiuta è “giusta” e il premio sarà basso quando l’azione compiuta è “sbagliata”. Possiamo assimilare una reward alta al piacere umano e una reward bassa al dolore umano.

In una prima matrice “R” viene salvata in modo binario, se è possibile eseguire una determinata azione prenderà come valore 1, altrimenti prenderà il valore 0.
La matrice prende una simile forma:

Dove su ogni riga viene rappresentata lo stato (per esempio la posizione) e su ogni colonna l’azione (per esempio andare avanti). E’ facilmente rappresentabile la matrice con un array di Numpy.

L’equazione di Bellman viene usata per calcolare quanto sia buono essere in un determinato stato. Essa viene rappresentata in questo modo:

Essa esprime che la nuova Q sarà espressa dalla precedente Q sommata alpha per la funzione di reward sommata a gamma per il massimo valore in un determinato stato sottratta alla Q precedente. I dati salvati vengono salvati in una matrice che rappresenta orizzontalmente lo stato e verticalmente l’azione, essa sarà simile alla seguente:

Quest’ultima tabella è la Q-table ed è la tabella che rappresenta, appunto, i risultati di ogni azione per stato.

Alpha e gamma sono rispettivamente il tasso di apprendimento e il fattore di sconto. Un tasso di apprendimento alto terrà conto solo delle nuove informazioni al contrario un tasso di apprendimento basso o peggio pari a zero impedirebbe all’agente di imparare. Invece un fattore di sconto basso farebbe in modo che l’agente sia troppo “opportunistico”, facendo si che consideri solo le ricompense recenti. Un fattore di sconto alto renderà l'agente attento anche alle ricompense che riceverà in un futuro a lungo termine.

Lo stato e l'azione durante il training possono essere scelte casualmente dal programma. La funzione di reward calcola i punti da dare ad una specifica azione e infine l’equazione di bellman calcolerà il valore da attribuire a Q. Questo procedimento viene ripetuto per un numero di volte, maggiore sarà in numero di volte che si ripete più il risultato ottenuto sarà ottimale.

Infine per predirre le azioni da eseguire dopo al training viene preso il valore maggiore partendo da un determinato stato. Per esempio se sono nello stato “A” l’algoritmo andrà a vedere nella riga corrispondente qual’è l’azione con il valore massimo.

Questo è un esempio di codice da un mio vecchio progetto:

import math
import numpy as np


class Space():
    def __init__(self, max_x, max_y, obstacle):
        self.moves = [Space.up, Space.down, Space.left, Space.right]
        self.x = 0
        self.y = 0
        self.max = [max_x, max_y]
        self.obstacle = obstacle
    def reset(self):
        self.x = 0
        self.y = 0

    # moves:
    def up(self):
        self.y += 1
        self.max_y()   
        return self.y   
    def down(self):
        self.y -= 1
        self.max_y()  
        return self.y          
    def left(self):
        self.x += 1
        self.max_x()  
        return self.x      
    def right(self):
        self.x -= 1
        self.max_x()  
        return self.x    

    def max_x(self):
        if self.x >= self.max[0] or self.x < 0:
            raise AttributeError()        
    def max_y(self):
        if self.y >= self.max[1] or self.y < 0:
            raise AttributeError()   

    # q-functions:
    def reward(self, s, a):
        x, y = s
        try:
            self.moves[a](self)
        except AttributeError:
            return -1
        a = math.sqrt((x - self.x) ** 2 + (y - self.y) ** 2)
        max = math.sqrt((self.max[0] - 1) ** 2 + (self.max[1] - 1) ** 2)
        return  (max - a) / max # atributing an value between 0 and 1
    def bellman(self, s, a, alpha, gamma, max, old):
        # Bellman function = Q(S, A)' = Q(S, A) + a[R(S, A) + g[Max Q(S)]] - Q(S, A)] =
        #                  = New_Q_value = Old_Q_value + learning_rate * [Reward_function(S, A) + discount_rate * max_value_for_state - Old_Q_value]
        return old + alpha * (self.reward(s, a) + gamma * max - old)

env = Space(4, 4, [[(1, 0), 0]]) # creating the envioment where the robot is going to move

def training(env: Space, EPOCHS, alpha, gamma):
    R = []
    sR = []
    for row in range(env.max[0]):
        for col in range(env.max[1]):
            r = []
            for move in env.moves:
                env.x = row
                env.y = col
                try:
                    x, y = env.x, env.y
                    move(env)
                    r.append(1) 
                except AttributeError: # if the robot goes out of space or touches an obstacle (to create code)
                    r.append(0)
                env.reset()
            sR.append([row, col])
            R.append(r)

    R = np.array(R, dtype=object) # the possible moves can do from an specific position => [(x, y)+list(moves)]
    for obstacle in env.obstacle:
        s = sR.index([obstacle[0][0], obstacle[0][1]])
        R[s, obstacle[1]] = 0
    env.reset() # resetting the enviroment

    Q = []
    states = []
    for row1 in range(env.max[0]):
        for col1 in range(env.max[1]):
            for row2 in range(env.max[0]):
                for col2 in range(env.max[1]):
                    states.append([row1, col1, row2, col2])
                    Q.append([0] * len(env.moves))

    # the q-table is going to be like this
    # Q = [
    #   [n_1, n_2, n_3, n_4] => this row defines the position where it starts and the position where it arrives (pos_1 => pos_2)
    # ]

    Q = np.array(Q)


    for _ in range(EPOCHS):
        for x1 in range(0, env.max[0]):
            for y1 in range(0, env.max[1]):
                for x2 in range(0, env.max[0]):
                    for y2 in range(0, env.max[1]):
                        if (x1, y1) != (x2, x1):
                            moves = []
                            s = states.index([x1, y1, x2, y2])
                            for i, m in enumerate(R[sR.index([x1, x2])]):
                                if m > 0:
                                    moves.append(i)
                            for move in moves:
                                env.x = x1
                                env.y = y1
                                max = Q[s, np.argmax(Q[s])]
                                bl = env.bellman([x2, y2], move, alpha, gamma, max, Q[s, move])
                                env.reset()
                                try:
                                    Q[s, move] = bl * 10 if Q[s, move] < 1 else bl
                                except OverflowError:
                                    break
    env.reset()
    return Q, states

Q, states = training(env, 500, 0.9, 0.7)

env.x = np.random.randint(0, env.max[0])
env.y = np.random.randint(0, env.max[1])
x2 = env.x
y2 = env.y
while x2 == env.x:
    x2 = np.random.randint(0, env.max[0]) 
while y2 == env.y:
    y2 = np.random.randint(0, env.max[1])  

moves = []

print("start:", env.x, env.y)
print("finish:", x2, y2)

i = 0
while (env.x, env.y) != (x2, y2):
    try:
        s = states.index([env.x, env.y, x2, y2])
        env.moves[np.argmax(Q[s])](env)
        moves.append(env.moves[np.argmax(Q[s])].__name__)
        i += 1
        if i == 20:
            Q, states = training(env, 500, 0.9, 0.7)
    except AttributeError:
        Q, states = training(env, 500, 0.9, 0.7)


print(moves)

Fonti:

wikipedia.org

Blog

eduardo-bolognini

Join Our Newsletter. No Spam, Only the good stuff.

Related