75 - Processo decisionale di Markov: il linguaggio in cui si scrive ogni problema di RL

Nell'articolo precedente il banditore aveva un solo «stato»: ogni scelta era indipendente dalle altre. I problemi interessanti non sono così: muoversi in un labirinto, giocare a scacchi, guidare un'auto cambiano la situazione, e ciò che fai ora determina che cosa potrai fare dopo. Il linguaggio matematico che descrive questi problemi si chiama processo decisionale di Markov (Markov Decision Process, MDP). Non è un algoritmo: è una cornice. Ma tutto il resto del modulo (l'equazione di Bellman, il Q-Learning, la Deep Q-Learning) è scritto in questa cornice, e se la cornice non è chiara non lo è nemmeno il resto. Qui andiamo quindi lentamente: definiamo ogni elemento, verifichiamo con un esperimento il punto più sottile (la proprietà di Markov), scriviamo un piccolo MDP come tabella di numeri e lo facciamo giocare.

Il vocabolario di un MDP

Uno stato s è tutto ciò che serve sapere della situazione per decidere che cosa fare; l'insieme degli stati è S. Un'azione a è ciò che l'agente può fare in uno stato; l'insieme delle azioni è A. La transizione P(s′ | s, a) è la probabilità di finire nello stato s′ facendo l'azione a nello stato s: se tutte le probabilità sono 0 o 1 l'ambiente è deterministico, altrimenti stocastico. La ricompensa R(s, a, s′) è il numero ricevuto in quella transizione. Il fattore di sconto γ (gamma), con 0 ≤ γ ≤ 1, dice quanto vale una ricompensa futura rispetto a una immediata; qui lo definiamo, e perché serve lo ricavi nella derivazione dell'equazione di Bellman.

La politica π(a | s) è la regola dell'agente, cioè con che probabilità sceglie ogni azione in ogni stato; una politica deterministica è una tabella «stato → azione». Uno stato terminale è uno stato in cui l'episodio finisce: da lì non si esce e non si guadagna più nulla. Un episodio è una traiettoria completa dallo stato iniziale a uno terminale; un problema «episodico» ha episodi finiti (una partita), uno «continuo» non finisce mai (il controllo di un termostato). Infine le funzioni valore v_π(s) e q_π(s, a) sono il ritorno medio che ci si può aspettare partendo da s (e facendo a) e poi seguendo la politica π: servono per valutare quanto è «buono» uno stato o un'azione. Le definiamo qui e le stimiamo in due modi, uno lento in questa pagina e uno esatto nella prossima.

L'analogia: il navigatore che non ricorda da dove sei arrivato

Un navigatore satellitare, per dirti dove girare, ha bisogno di sapere dove sei adesso e dove vuoi andare. Non gli serve sapere da quale strada sei arrivato, né a che ora sei partito: la posizione attuale contiene tutto ciò che conta per il futuro. Questa è l'idea della proprietà di Markov: il futuro dipende dal passato solo attraverso il presente. Un buon «stato» è quello che riassume abbastanza del passato da rendere superfluo il resto. Se invece il navigatore sapesse solo «sei in un incrocio» senza dire quale, non potrebbe decidere: quello stato non è abbastanza ricco. Capire se lo stato che stai dando all'agente è davvero «di Markov» è una delle decisioni di progetto più importanti e più sottovalutate dell'RL.

Le cinque cose di un MDP

Un MDP è definito da cinque cose: (S, A, P, R, γ). Nel disegno c'è un esempio concreto: una griglia 4×4 con 16 stati (numerati da 0 a 15), 4 azioni (su, destra, giù, sinistra), due stati terminali (gli angoli 0 e 15, «obiettivo») e una ricompensa di −1 a ogni passo, finché non si arriva a un angolo. Quest'ultima scelta è importante: con −1 a ogni passo, per accumulare meno penalità possibile l'agente deve raggiungere un angolo il più in fretta possibile. L'obiettivo «sbrigati» è tutto nella ricompensa; non l'abbiamo detto all'agente. Muoversi contro una parete lascia nello stesso stato; e se il pavimento è «scivoloso» l'azione riesce con probabilità 0.8 e devia di lato con probabilità 0.1 + 0.1 (è l'esempio nel disegno). Sutton e Barto definiscono l'MDP finito nel capitolo 3 del loro testo e dicono una cosa che vale la pena tenere a mente: la proprietà di Markov è una restrizione non sul processo decisionale ma sullo stato, che deve includere ciò che del passato fa differenza per il futuro.

La proprietà di Markov, verificata

La definizione dice: la probabilità del prossimo stato e della ricompensa dipende solo da s e a, non dalla storia. Verifichiamola su un esempio dove possiamo vederla fallire. Una pallina rimbalza fra le posizioni 0 e 9 spostandosi di una cella a ogni passo, invertendo la direzione ai bordi. Se «lo stato» è soltanto la posizione, possiamo prevedere la posizione successiva? Il listato usa un generatore con seme fisso (default_rng(0)), quindi la traiettoria e l'uscita sono le stesse a ogni esecuzione.

# Is "the position" a Markov state? A ball bounces between 0 and 9 moving one cell per step.
import numpy as np
from collections import Counter, defaultdict

def ball_trajectory(steps, rng):
    pos, vel = int(rng.integers(0, 10)), int(rng.choice([-1, 1]))
    traj = [pos]
    for _ in range(steps):
        if not (0 <= pos + vel <= 9):
            vel = -vel                                # bounce
        pos += vel
        traj.append(pos)
    return traj

rng = np.random.default_rng(0)
traj = ball_trajectory(20000, rng)

def best_possible_accuracy(feature):
    """Largest accuracy any predictor can reach if it can only look at `feature(t)` to guess position t+1."""
    table = defaultdict(Counter)
    for t in range(1, len(traj) - 1):
        table[feature(t)][traj[t + 1]] += 1
    hits = sum(c.most_common(1)[0][1] for c in table.values())
    return hits / (len(traj) - 2)

print("state = position only          :", round(best_possible_accuracy(lambda t: traj[t]), 3))
print("state = (previous, current)    :", round(best_possible_accuracy(lambda t: (traj[t - 1], traj[t])), 3))

# Output (due esecuzioni consecutive, stessa uscita):
# state = position only          : 0.556
# state = (previous, current)    : 1.0

ball_trajectory genera 20.000 passi della pallina. best_possible_accuracy(feature) costruisce, per ogni valore della «descrizione dello stato» (feature), una tabella che conta quale posizione successiva è comparsa più spesso; la frazione di casi in cui la scelta più frequente è corretta è la massima accuratezza possibile per qualunque previsore che veda solo quella descrizione, perché l'informazione per fare meglio non c'è. Con la sola posizione il massimo è 55.6%: nelle celle intermedie la pallina può andare sia a destra sia a sinistra, e la posizione sola non dice quale. Con la coppia (posizione precedente, posizione corrente) è 100%: la differenza fra le due rivela la direzione. Conclusione: «solo la posizione» non è uno stato di Markov per questo sistema, «posizione e posizione precedente» lo è.

Quando l'osservazione non basta, si aggiunge la storia necessaria (la velocità, per esempio) o si usa una memoria ricorrente, come nelle reti del modulo sulle sequenze (vedi LSTM e adding problem). Nei videogiochi per Atari, ad esempio, l'articolo di Mnih e colleghi su DQN applica la rete agli ultimi 4 fotogrammi impilati: un solo fotogramma non dice se la palla sta salendo o scendendo. Il limite del nostro esperimento è che 55.6% vale per questa pallina e questa lunghezza di traiettoria: la cifra mostra il meccanismo, non è una proprietà generale.

Scrivere un MDP come tabella

Per un MDP piccolo si può scrivere P come una vera tabella: per ogni stato e per ogni azione, la lista delle possibili conseguenze, ciascuna con probabilità, stato successivo, ricompensa e un indicatore «episodio finito». Gli ambienti tabulari di Gymnasium espongono la stessa struttura nell'attributo unwrapped.P, come vedi in Gymnasium in pratica. Il codice qui sotto costruisce la nostra griglia 4×4.

import numpy as np

# Actions: 0=up, 1=right, 2=down, 3=left
MOVES = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}

class GridWorld:
    """A small MDP written out explicitly: P[s][a] = list of (probability, next_state, reward, done)."""
    def __init__(self, n=4, terminals=(0, 15), step_reward=-1.0, slip=0.0):
        self.n, self.terminals, self.n_states, self.n_actions = n, set(terminals), n * n, 4
        self.P = {s: {a: self._transitions(s, a, step_reward, slip) for a in range(4)} for s in range(self.n_states)}

    def _move(self, s, a):
        r, c = divmod(s, self.n)
        dr, dc = MOVES[a]
        r2, c2 = r + dr, c + dc
        if not (0 <= r2 < self.n and 0 <= c2 < self.n):       # bumping into a wall: stay where you are
            r2, c2 = r, c
        return r2 * self.n + c2

    def _transitions(self, s, a, step_reward, slip):
        if s in self.terminals:                                # terminal states: absorbing, no reward
            return [(1.0, s, 0.0, True)]
        outcomes = {}                                          # next_state -> probability
        for a2, p in [(a, 1.0 - slip), ((a + 1) % 4, slip / 2), ((a - 1) % 4, slip / 2)]:   # intended, or slip to a side
            if p > 0:
                s2 = self._move(s, a2)
                outcomes[s2] = outcomes.get(s2, 0.0) + p
        return [(p, s2, step_reward, s2 in self.terminals) for s2, p in outcomes.items()]

env = GridWorld()
print("from state 1, action 'left' (towards the terminal state 0):", env.P[1][3])
print("from state 5, action 'up':", env.P[5][0])
print("from state 0 (terminal):", env.P[0][2])
slippery = GridWorld(slip=0.2)
print("slippery, state 5, action 'right':", [(round(p, 2), s2) for p, s2, r, d in slippery.P[5][1]])

# Output (due esecuzioni consecutive, stessa uscita):
# from state 1, action 'left' (towards the terminal state 0): [(1.0, 0, -1.0, True)]
# from state 5, action 'up': [(1.0, 1, -1.0, False)]
# from state 0 (terminal): [(1.0, 0, 0.0, True)]
# slippery, state 5, action 'right': [(0.8, 6), (0.1, 9), (0.1, 1)]

La classe GridWorld costruisce il dizionario self.P, tale che P[s][a] sia la lista delle conseguenze. _move calcola dove si finisce muovendosi nella direzione a, restando fermi se si urta il bordo. _transitions distingue due casi: se s è terminale, la transizione è «assorbente» (si resta lì, ricompensa 0, done=True); altrimenti, con probabilità 1 − slip l'azione riesce, e con probabilità slip/2 a testa viene eseguita l'azione «ruotata» a destra o a sinistra ((a + 1) % 4 e (a − 1) % 4). Se due esiti portano allo stesso stato (accade vicino ai muri), le probabilità si sommano nel dizionario outcomes: senza questo accorpamento la lista conterrebbe due voci per lo stesso stato di arrivo.

Le quattro righe stampate lo confermano: da 1 con «sinistra» si va al terminale 0 con probabilità 1, ricompensa −1 e done=True; da 5 con «su» si va a 1 senza finire; lo stato terminale 0 è assorbente; con pavimento scivoloso (slip=0.2), da 5 con «destra» si va a 6 con 0.8, a 9 con 0.1 e a 1 con 0.1, gli stessi numeri del disegno.

Far giocare l'agente: politica casuale contro politica sensata

Una politica è soltanto una funzione dallo stato all'azione. Scriviamo la funzione che simula un episodio e proviamo due politiche: una che sceglie a caso e una che va dritta verso l'angolo più vicino. Le simulazioni usano rng.choice(len(probs), p=probs) per estrarre l'esito secondo le probabilità di P[s][a]; nella griglia deterministica c'è una sola voce con probabilità 1, ma il codice funziona anche con slip > 0.

def run_episode(env, policy, rng, start, max_steps=10_000, gamma=1.0):
    """Follow `policy` (a function state -> action) from `start`. Returns (return, number_of_steps)."""
    s, G, discount = start, 0.0, 1.0
    for t in range(max_steps):
        a = policy(s)
        probs = [p for p, _, _, _ in env.P[s][a]]
        p, s2, r, done = env.P[s][a][rng.choice(len(probs), p=probs)]
        G += discount * r
        discount *= gamma
        s = s2
        if done:
            return G, t + 1
    return G, max_steps

rng = np.random.default_rng(0)
random_policy = lambda s: int(rng.integers(4))
non_terminal = [s for s in range(env.n_states) if s not in env.terminals]
results = [run_episode(env, random_policy, rng, start=s) for s in non_terminal for _ in range(2000)]
G = np.array([g for g, _ in results]); L = np.array([l for _, l in results])
print(f"random policy: mean return {G.mean():.1f}, mean episode length {L.mean():.1f}, longest {L.max()}")
# A hand-written policy: head for the NEAREST terminal state (state 0 or state 15)
def towards_nearest_corner(s):
    r, c = divmod(s, 4)
    dist0, dist15 = r + c, (3 - r) + (3 - c)
    if dist0 <= dist15:
        return 0 if r > 0 else 3                 # up while possible, then left
    return 2 if r < 3 else 1                     # down while possible, then right

results = [run_episode(env, towards_nearest_corner, rng, start=s) for s in non_terminal]
print(f"shortest-path policy: mean return {np.mean([g for g, _ in results]):.2f}, longest episode {max(l for _, l in results)} steps")

# Output (due esecuzioni consecutive, stessa uscita):
# random policy: mean return -18.2, mean episode length 18.2, longest 213
# shortest-path policy: mean return -2.00, longest episode 3 steps

run_episode parte da start e, a ogni passo, chiede l'azione alla politica, estrae un esito, accumula la ricompensa (scontata se gamma < 1) e si ferma quando done è vero. Con la politica casuale, partendo da ognuno dei 14 stati non terminali per 2000 volte, il ritorno medio è −18.2 e l'episodio dura in media 18.2 passi (ogni passo vale −1, quindi ritorno = −lunghezza); il più lungo ha 213 passi, perché una camminata casuale può vagare a lungo. La politica «verso l'angolo più vicino» fa in media −2.00, al massimo 3 passi: stesso ambiente, due politiche, un ritorno circa nove volte migliore. È questo che vuol dire «imparare»: l'RL cerca la politica che massimizza il ritorno atteso. Attenzione al parametro max_steps=10_000: protegge da una politica che non arriva mai a un terminale, ma se scatta il ritorno restituito è parziale, e in quel caso l'episodio va segnalato, non mediato in silenzio.

Il ritorno scontato

Finora il ritorno era la somma semplice delle ricompense. Per problemi lunghi o senza fine si usa il ritorno scontato: ogni ricompensa viene moltiplicata per una potenza di γ crescente con la distanza nel tempo:

G_t = R_{t+1} + γ R_{t+2} + γ² R_{t+3} + γ³ R_{t+4} + …  =  Σ_{k=0..∞} γ^k R_{t+k+1}

Un'osservazione algebrica, che userai continuamente, è che il ritorno si può scrivere in modo ricorsivo: raccogliendo γ dal secondo termine in poi,

G_t = R_{t+1} + γ ( R_{t+2} + γ R_{t+3} + γ² R_{t+4} + … ) = R_{t+1} + γ G_{t+1}

«Il ritorno di adesso è la ricompensa immediata più γ volte il ritorno da domani». Questa ricorsione è il seme dell'equazione di Bellman. Vediamo i numeri con un episodio di quattro passi: tre passi con ricompensa −1 e poi l'arrivo con +10.

def discounted_return(rewards, gamma):
    """G_0 = R_1 + gamma R_2 + gamma^2 R_3 + ...   (computed from the end, which is how it is done in practice)"""
    G = 0.0
    for r in reversed(rewards):
        G = r + gamma * G                              # G_t = R_{t+1} + gamma * G_{t+1}
    return G

rewards = [-1, -1, -1, 10]                             # three steps of cost, then the goal
for gamma in (1.0, 0.9, 0.5):
    print(f"gamma={gamma}:  G_0 = {discounted_return(rewards, gamma):.3f}")
print("by hand, gamma=0.9:", -1 - 0.9 - 0.81 + 0.729 * 10)

# Output (due esecuzioni consecutive, stessa uscita):
# gamma=1.0:  G_0 = 7.000
# gamma=0.9:  G_0 = 4.580
# gamma=0.5:  G_0 = -0.500
# by hand, gamma=0.9: 4.58

La funzione discounted_return calcola il ritorno da destra a sinistra, applicando la ricorsione G = r + γ·G, che evita di calcolare le potenze di γ una per una. Con γ = 1 (nessuno sconto) il ritorno è la somma semplice, −1 −1 −1 + 10 = 7. Con γ = 0.9 il premio di +10, che arriva dopo tre passi, vale solo 0.9³ · 10 = 7.29 e il ritorno è −1 − 0.9 − 0.81 + 7.29 = 4.58, come conferma la riga calcolata a mano. Con γ = 0.5 il premio vale 0.125 · 10 = 1.25 e il ritorno diventa negativo (−0.5): un agente così «miope» considererebbe quell'episodio un cattivo affare. Il valore di γ non è un dettaglio: cambia ciò che l'agente considera ottimale, e ne parliamo a fondo nell'articolo su Bellman.

Che cosa significa «valore»: la stima più lenta possibile

La funzione valore v_π(s) è il ritorno atteso partendo da s e seguendo la politica π. Possiamo stimarla senza nessuna teoria, solo simulando: per ogni stato facciamo molti episodi con la politica casuale e ne mediamo i ritorni (metodo Monte Carlo).

# Estimating the VALUE of each state under the random policy, the slow way: average the returns of many simulated episodes
rng = np.random.default_rng(1)
random_policy = lambda s: int(rng.integers(4))
V_mc = np.zeros(env.n_states)
for s in range(env.n_states):
    if s in env.terminals:
        continue
    V_mc[s] = np.mean([run_episode(env, random_policy, rng, start=s)[0] for _ in range(4000)])
print(np.round(V_mc.reshape(4, 4), 1))

# Output (due esecuzioni consecutive, stessa uscita):
# [[  0.  -13.8 -19.6 -21.7]
#  [-14.  -18.4 -19.8 -20.4]
#  [-19.9 -19.9 -18.4 -14.1]
#  [-22.1 -20.3 -14.2   0. ]]

Il codice esegue, per ognuno dei 14 stati non terminali, 4000 episodi con la politica casuale e ne media il ritorno. Il risultato è una mappa dei valori: vicino agli angoli terminali il valore è «meno brutto» (circa −14), lontano dagli angoli è peggiore (circa −22). Ha senso: partire da uno stato lontano dal traguardo significa, per una camminata casuale, aspettarsi più passi e quindi più −1. Quanto fidarsi di ogni cella? Rieseguendo la stessa procedura con altri semi su tre stati (1, 5 e 10), la deviazione standard dei ritorni è 17-18 e l'errore standard della media su 4000 episodi risulta 0.27-0.28: ogni cella è affidabile a circa ±0.3, non alla prima cifra decimale. Ricorda questa tabella: nell'articolo sull'equazione di Bellman la si calcola senza simulare niente, e la distanza fra le due è proprio quel rumore di campionamento.

Dal MDP alla domanda centrale

Con queste definizioni, il problema dell'RL si enuncia in una riga: dato un MDP (spesso senza conoscere P e R), trovare la politica π che massimizza il ritorno atteso da ogni stato. Due situazioni sono molto diverse. Se si conosce l'MDP (la tabella P), si può pianificare, cioè calcolare il valore con la programmazione dinamica; se non lo si conosce, si deve imparare dall'esperienza, ed è il caso del Q-Learning e della Deep Q-Learning. La differenza fra le due è la spina dorsale del modulo. Per un MDP finito esiste sempre almeno una politica ottima, e ogni politica greedy rispetto al valore ottimo lo è (Sutton e Barto, sezione 3.6): per questo si può cercare una politica deterministica senza perdere nulla.

I compromessi di modellazione

Il primo compromesso riguarda quanto includere nello stato: poco, e l'agente non vede ciò che serve (la pallina senza direzione); troppo, e gli stati diventano tanti e l'apprendimento rallenta. Il secondo è fra ambiente deterministico e stocastico: il modello stocastico è più realistico ma obbliga a ragionare in media, con i valori attesi. Il terzo riguarda la densità della ricompensa: una ricompensa a ogni passo (−1 qui) guida l'agente, mentre una ricompensa solo alla fine rende l'apprendimento molto più difficile, tema di Ricompense ritardate, reward shaping e reward hacking. Il quarto è fra episodico e continuo: con episodi finiti γ = 1 è lecito, per problemi senza fine serve γ < 1 perché la somma resti finita.

Trappole reali

1. Stato non markoviano. L'errore più comune: dare all'agente un'osservazione che non contiene ciò che serve (qui, la pallina senza direzione). Ogni algoritmo funziona male e non sai perché.
2. Ricompensa che non descrive l'obiettivo. L'agente massimizza quel numero, non la tua intenzione. Con −1 a passo ottiene «sbrigati»; con una ricompensa mal scritta ottiene un comportamento inatteso.
3. Confondere reward e return. La ricompensa è il numero di un passo, il ritorno è la somma di tutti quelli futuri (scontata).
4. Dimenticare i terminali. Uno stato terminale deve essere assorbente con ricompensa zero dopo l'arrivo; se gli lasci uscire ricompensa, l'agente può imparare a «oscillare» lì.
5. Misurare una politica con un solo episodio. L'ambiente può essere stocastico: serve la media su molti episodi (qui 2000 per stato nel confronto fra politiche, 4000 per la stima di valore).

Le prime due trappole sono errori di progetto e nessuna misura le segnala: l'algoritmo gira, i numeri escono, e il comportamento è sbagliato per ragioni che stanno nella definizione dello stato o della ricompensa. Le ultime tre sono errori di implementazione o di valutazione e si trovano con un test: uno stato terminale si controlla guardando P[s][a] (come nella terza riga di uscita sopra), una media su molti episodi si controlla con l'errore standard.

Un esempio svolto a mano: il valore di una catena di due stati

Un MDP minuscolo che anticipa Bellman. Due stati, A e B, più un terminale. Con la politica che stiamo valutando: da A si va sempre in B (ricompensa −1); da B si va nel terminale con probabilità ½ oppure si torna in A con probabilità ½ (ricompensa −1 in entrambi i casi). Qual è il valore, cioè il ritorno atteso (senza sconto), di A e di B?

Ragioniamo con la ricorsione del ritorno. Da B: si paga −1 e poi, con probabilità ½ si finisce (valore 0), con probabilità ½ si ricomincia da A: v(B) = −1 + ½·0 + ½·v(A). Da A: si paga −1 e si va in B: v(A) = −1 + v(B). Sostituendo: v(A) = −1 − 1 + ½·v(A), quindi ½·v(A) = −2 e v(A) = −4, v(B) = −3. Verifica indipendente: il numero atteso di passi E per uscire da B soddisfa E = 1 + ½·(1 + E) (un passo; con probabilità ½ si torna in A, si fa un altro passo verso B e si ricomincia). Risolvendo, ½·E = 1.5, cioè E = 3 passi attesi, e poiché ogni passo costa −1 il ritorno è −3, che coincide con v(B). Ho ricontrollato anche il sistema lineare con numpy.linalg.solve: restituisce (−4, −3).

Le due equazioni scritte sopra sono equazioni di Bellman, che ricaviamo in generale nell'articolo successivo: abbiamo scritto il valore di uno stato in funzione dei valori degli stati successivi e le abbiamo risolte come un sistema lineare. Con 16 stati nella griglia 4×4 il sistema ha 16 equazioni; è ciò che farà il computer.

Domande frequenti

Qual è la differenza fra «stato» e «osservazione»?

Lo stato è la descrizione completa della situazione; l'osservazione è ciò che l'agente riceve, che può essere parziale (un solo fotogramma di un videogioco). Quando l'osservazione non è markoviana, si aggiunge storia o memoria.

Una politica deve essere deterministica?

No: può assegnare probabilità alle azioni, e la politica casuale della griglia è un caso particolare. Per un MDP finito esiste comunque una politica ottima deterministica (vedi sopra, sezione 3.6 del libro).

Perché la ricompensa può dipendere da s′?

Per generalità: la ricompensa può dipendere da che cosa succede dopo l'azione (ad esempio «cadi in un buco»). Spesso si scrive R(s, a) perché è la media su s′.

Che cosa significa che un MDP è «finito»?

Che l'insieme di stati e azioni è finito, come nella nostra griglia; è il caso in cui tabelle e programmazione dinamica funzionano. Con stati continui (CartPole) servono approssimatori.

Il ritorno può essere calcolato prima della fine dell'episodio?

Non esattamente: dipende da ricompense future ancora ignote. È per questo che si stima il valore (Monte Carlo a fine episodio, oppure Bellman e TD senza aspettare).

Gli stati terminali devono avere valore zero?

Per convenzione sì: dopo la fine non si accumula altro. Dimenticarsene (aggiungendo valore dopo un terminale) gonfia le stime.

Esercizi con soluzione

Prima di andare avanti, prova a risolvere questi esercizi con carta e matita; la soluzione è subito sotto ciascuno.

1. Calcola G_0 per le ricompense 2, 0, 4 con γ = 0.5.
   Soluzione: 2 + 0.5·0 + 0.25·4 = 3. Con la ricorsione da destra: G = 4; G = 0 + 0.5·4 = 2; G = 2 + 0.5·2 = 3.
2. Calcola G_0 per le ricompense 1, 2, 3 con γ = 0.5.
   Soluzione: 1 + 0.5·2 + 0.25·3 = 2.75; da destra: G = 3; G = 2 + 0.5·3 = 3.5; G = 1 + 0.5·3.5 = 2.75.
3. Una griglia 5×5 con 4 azioni: quante voci ha la tabella P (stato, azione)?
   Soluzione: 25·4 = 100. Per la griglia 4×4 dell'articolo sono 16·4 = 64 voci, ciascuna con un solo esito se non c'è scivolamento.
4. Perché «posizione» non basta come stato per la pallina che rimbalza?
   Soluzione: perché la direzione non è determinata dalla sola posizione: nelle celle intermedie la pallina può andare da entrambe le parti (accuratezza massima 55.6%).
5. Nella catena A, B, terminale (B torna in A con probabilità ½), se la ricompensa per passo fosse −2, quanto varrebbe v(A)?
   Soluzione: i valori scalano linearmente: v(A) = −8, il doppio di −4 (ricontrollato con numpy.linalg.solve: −8 e −6).

I primi tre esercizi sono aritmetica: servono a fissare la ricorsione G = r + γ·G e il conteggio delle voci di P. Gli ultimi due sono di interpretazione, e sono quelli che separano chi ha capito la proprietà di Markov dalla ricorsione di Bellman da chi ha solo imparato le formule: se rispondi senza rileggere il testo, puoi passare avanti.

Che cosa sai fare adesso

Sai scrivere un MDP come (S, A, P, R, γ), sai dire se uno stato è markoviano e hai visto come si misura (accuratezza massima 55.6% con la sola posizione, 100% con posizione e posizione precedente). Sai costruire la tabella P di un piccolo ambiente, simulare una politica e confrontarne il ritorno: nella griglia, la politica casuale vale −18.2 e quella sensata −2. Sai calcolare il ritorno scontato G_t = R_{t+1} + γ G_{t+1} e stimare il valore di uno stato con Monte Carlo (da circa −14 a circa −22 nella griglia, con errore standard intorno a 0.3). Il passo successivo è l'equazione di Bellman derivata per intero, che trasforma la ricorsione del ritorno in un calcolo esatto senza simulare.