Value Iteration

Ecco un esempio di applicato a una griglia (4X 4) (un ambiente comune nei problemi di Reinforcement Learning).
Le azioni disponibili sono su, giù, sinistra, destra.
Utilizziamo la funzione di Bellman per calcolare i valori ottimali degli stati e derivare la politica ottimale.

import numpy as np

# Parametri della griglia
rows, cols = 4, 4  # Griglia 4x4
gamma = 0.9        # Fattore di sconto
theta = 1e-4       # Soglia di convergenza

# Azioni possibili
actions = {
    'up': (-1, 0),
    'down': (1, 0),
    'left': (0, -1),
    'right': (0, 1)
}

# Funzione per verificare se uno stato è valido nella griglia
def is_valid_state(state):
    r, c = state
    return 0 <= r < rows and 0 <= c < cols

# Funzione di transizione (stato successivo e probabilità)
def transition(state, action):
    r, c = state
    dr, dc = actions[action]
    next_state = (r + dr, c + dc) if is_valid_state((r + dr, c + dc)) else state
    return next_state

# Inizializzazione della funzione di valore
V = np.zeros((rows, cols))

# Ricompense: obiettivo a (3, 3), buca a (1, 1)
rewards = np.zeros((rows, cols))
rewards[3, 3] = 1    # Obiettivo
rewards[1, 1] = -1   # Buca

# Value Iteration
while True:
    delta = 0
    new_V = V.copy()
    for r in range(rows):
        for c in range(cols):
            state = (r, c)
            if state in [(3, 3), (1, 1)]:  # Stati terminali
                continue
            # Calcola il valore massimo usando la funzione di Bellman
            action_values = []
            for action in actions:
                next_state = transition(state, action)
                prob = 1.0  # Azioni deterministiche
                reward = rewards[next_state]
                action_values.append(prob * (reward + gamma * V[next_state]))
            new_V[state] = max(action_values)
            delta = max(delta, abs(new_V[state] - V[state]))
    V = new_V
    if delta < theta:
        break

# Derivare la politica ottimale
policy = np.full((rows, cols), '', dtype=object)
for r in range(rows):
    for c in range(cols):
        state = (r, c)
        if state in [(3, 3), (1, 1)]:  # Stati terminali
            policy[state] = 'TERMINAL'
            continue
        action_values = {}
        for action in actions:
            next_state = transition(state, action)
            prob = 1.0  # Azioni deterministiche
            reward = rewards[next_state]
            action_values[action] = prob * (reward + gamma * V[next_state])
        best_action = max(action_values, key=action_values.get)
        policy[state] = best_action

# Stampa i risultati
print("Funzione di valore ottimale:")
print(np.round(V, 2))

print("\nPolitica ottimale:")
for row in policy:
    print(row)

Spiegazione del codice

1. Parametri della griglia:
- La griglia è (4 X 4) con stati rappresentati come coordinate ((r, c)).
- Azioni: Su ((-1, 0)), giù ((+1, 0)), sinistra ((0, -1)), destra ((0, +1)).

2. Funzione di transizione:
- La funzione `transition(state, action)` restituisce lo stato successivo dato lo stato attuale e l'azione.
Se l'azione porta fuori dalla griglia, si rimane nello stato corrente.

3. Funzione di valore:
- La funzione di valore ( V(s)) viene inizializzata a zero per tutti gli stati.
- Gli stati terminali (((3, 3)) e ((1, 1))) non vengono aggiornati.

4. Value Iteration:
- Per ogni stato, si calcolano i valori attesi delle azioni utilizzando l'equazione di Bellman: \[ V(s) = \max_{a} \sum_{s'} P(s'|s, a) \cdot \left[ R(s, a) + \gamma V(s') \right] \]
- In questo caso, le azioni sono deterministiche, quindi ( P(s'|s, a) = 1 ).
5. Politica ottimale:
- Dopo la convergenza di ( V(s) ), si calcola la politica ottimale ( pi(s) ) scegliendo l'azione che massimizza il valore atteso.

6. Risultati:
- La funzione di valore ( V(s) ) e la politica ottimale ( pi(s) ) vengono stampate.

Esempio di output

Funzione di valore ottimale:
[[0.53 0.59 0.66 0.73]
 [0.48 0.   0.73 0.81]
 [0.43 0.53 0.66 0.9 ]
 [0.39 0.48 0.59 1.  ]]

Politica ottimale:
['right' 'right' 'right' 'down']
['up' 'TERMINAL' 'right' 'down']
['up' 'right' 'right' 'down']
['up' 'up' 'up' 'TERMINAL']

Conclusioni

- La funzione di valore mostra i valori ottimali ( V^*(s) ) per ogni stato.
- La politica ottimale indica l'azione migliore da intraprendere in ogni stato per raggiungere l'obiettivo massimizzando la ricompensa.
- Questo approccio può essere esteso a griglie più grandi o ambienti più complessi.