Processo decisionale di Markov: cos’è e come funziona nel reinforcement learning

Ogni volta che un’intelligenza artificiale sceglie una mossa in una partita, un robot decide dove appoggiare il piede successivo o un sistema di raccomandazione ti propone il prossimo video da guardare, dietro le quinte c’è quasi sempre lo stesso schema concettuale. Quello schema si chiama processo decisionale di Markov, in inglese Markov Decision Process, spesso abbreviato in MDP. È il modo formale con cui descriviamo un agente che prende decisioni una dopo l’altra all’interno di un ambiente incerto, cercando di ottenere il miglior risultato possibile nel corso del tempo.

Capire il processo decisionale di Markov significa mettere le mani sulle fondamenta dell’apprendimento per rinforzo, la branca del machine learning in cui un sistema impara per tentativi ed errori invece di essere programmato passo per passo. Non si tratta di un dettaglio tecnico riservato ai ricercatori, ma del linguaggio con cui oggi si progettano gli agenti autonomi, dai robotaxi agli assistenti conversazionali.

In questa guida vedrai cos’è un MDP, di quali elementi è composto e come un agente lo usa per decidere. Lo faremo con parole semplici, senza però rinunciare al rigore.

Che cos’è un processo decisionale di Markov

Un processo decisionale di Markov è un modello matematico che descrive un problema di decisione sequenziale in condizioni di incertezza. La parola chiave qui è sequenziale: non parliamo di una scelta singola e isolata, ma di una catena di decisioni in cui ogni azione influenza la situazione successiva e, di conseguenza, tutte le scelte che verranno dopo. È esattamente la situazione in cui si trova chiunque debba pianificare, un giocatore di scacchi, un investitore, un robot che attraversa una stanza.

L’idea di fondo è semplice e potente. Immagina un agente, cioè chi prende le decisioni, immerso in un ambiente. A ogni istante l’agente osserva lo stato dell’ambiente, sceglie un’azione, e in risposta l’ambiente cambia stato e restituisce un segnale numerico chiamato ricompensa. L’obiettivo dell’agente non è massimizzare la ricompensa immediata, ma la somma delle ricompense che riuscirà a raccogliere lungo tutto il percorso.

Questo ciclo di osservazione, azione e ricompensa si ripete di continuo. Un passo dopo l’altro, si costruisce quella che chiamiamo una traiettoria.

Il nome rende onore al matematico russo Andrej Markov, che a inizio Novecento studiò i processi in cui il futuro dipende solo dal presente. Il processo decisionale di Markov aggiunge a quell’intuizione due ingredienti che Markov non aveva considerato: la possibilità di compiere azioni e la presenza di ricompense. Da un modello puramente descrittivo si passa così a un modello adatto a prendere decisioni.

La proprietà di Markov: perché conta solo il presente

Il cuore concettuale del modello è la cosiddetta proprietà di Markov, detta anche assenza di memoria. Afferma che lo stato attuale contiene tutte le informazioni necessarie per decidere il futuro, rendendo irrilevante la storia passata. In altre parole, se conosci lo stato presente, sapere come ci sei arrivato non aggiunge nulla di utile per prevedere cosa accadrà dopo.

Prendi una partita a dama. Per scegliere la mossa migliore ti basta guardare la disposizione attuale delle pedine sulla scacchiera. Non ti serve ricordare l’ordine esatto delle mosse che hanno portato a quella configurazione, perché la posizione presente riassume già tutto.

Questa proprietà non è un tecnicismo fine a se stesso. È ciò che rende il problema trattabile.

Senza la proprietà di Markov l’agente dovrebbe tenere conto dell’intera cronologia di ogni interazione, un compito che diventa rapidamente impossibile. Grazie a essa, invece, tutto si riduce a una domanda ben definita: dato lo stato in cui mi trovo adesso, qual è l’azione migliore? Quando un problema reale non soddisfa questa condizione, spesso lo si riformula arricchendo la definizione di stato, in modo da inglobare le informazioni del passato che contano davvero.

Dai processi di Markov ai processi decisionali

Vale la pena chiarire una piccola gerarchia di concetti, perché aiuta a orientarsi. Il punto di partenza è la catena di Markov, un sistema che salta da uno stato all’altro seguendo semplici probabilità, senza che nessuno intervenga. Pensa all’evoluzione del meteo modellata in modo elementare, con probabilità fisse di passare da sereno a nuvoloso.

Se a quel sistema aggiungi delle ricompense associate agli stati, ottieni un processo di ricompensa di Markov. E se, oltre alle ricompense, introduci la possibilità di scegliere tra diverse azioni, allora arrivi finalmente al processo decisionale di Markov. È l’azione a fare la differenza, perché trasforma uno spettatore passivo in un agente capace di influenzare il proprio destino.

I cinque elementi che definiscono un MDP

Un processo decisionale di Markov si descrive in modo compatto attraverso un insieme di componenti. Tradizionalmente sono cinque: l’insieme degli stati, l’insieme delle azioni, la funzione di transizione, la funzione di ricompensa e il fattore di sconto. Conoscerli bene significa avere in mano tutto ciò che serve per formalizzare quasi qualunque problema di decisione sequenziale.

Vediamoli uno alla volta, con calma.

Stati e azioni

Lo stato è la fotografia della situazione in un dato momento. In un videogioco potrebbe essere la posizione del personaggio e dei nemici, in un magazzino automatizzato la collocazione degli scaffali e dei robot, in un problema finanziario il valore corrente di un portafoglio. L’insieme di tutti gli stati possibili prende il nome di spazio degli stati e può essere piccolo e numerabile oppure enorme, addirittura continuo.

L’azione è invece la leva che l’agente può muovere. Andare a destra o a sinistra, comprare o vendere, accelerare o frenare. In alcuni stati non tutte le azioni sono disponibili, e questo fa parte della definizione del problema.

La ricchezza di un MDP nasce proprio dalla combinazione di questi due insiemi. Ogni coppia formata da uno stato e da un’azione apre uno scenario diverso, e il compito dell’agente è capire quali scenari conviene davvero perseguire.

La funzione di transizione e il ruolo del caso

Qui entra in gioco l’incertezza, che è l’aspetto più interessante del modello. Quando l’agente compie un’azione in un certo stato, non sempre il risultato è garantito. La funzione di transizione descrive con quale probabilità si finisce in ciascuno degli stati possibili, data la coppia di partenza formata da stato e azione.

Un esempio chiarisce subito il concetto. Un robot riceve il comando di avanzare di una casella, ma il pavimento è scivoloso: nel novanta per cento dei casi si sposta come previsto, mentre nel restante dieci per cento slitta di lato. Questa aleatorietà, ovvero la presenza del caso, è ciò che distingue un MDP da un problema di pianificazione deterministico.

La transizione incarna la proprietà di Markov in forma matematica, perché dipende solo dallo stato e dall’azione correnti, mai dal percorso seguito in precedenza. Ecco perché si dice che un MDP è un processo di controllo stocastico a tempo discreto.

Quando gli stati e le azioni sono in numero finito si parla di MDP finito, il caso più studiato e quello su cui poggia gran parte della teoria dell’apprendimento per rinforzo.

La ricompensa e il fattore di sconto

La funzione di ricompensa assegna un valore numerico a ciò che accade. Può premiare il raggiungimento di un obiettivo, penalizzare un errore, o semplicemente misurare quanto è desiderabile una certa transizione. È attraverso la ricompensa che il progettista comunica all’agente cosa considera un buon comportamento, senza però dirgli come ottenerlo. Definire bene questa funzione è una delle parti più delicate di tutto il lavoro.

Resta un problema: se l’agente guarda a un futuro potenzialmente infinito, la somma delle ricompense potrebbe crescere senza limite e diventare impossibile da confrontare. Per questo si introduce il fattore di sconto, di solito indicato con la lettera greca gamma, un numero compreso tra zero e uno.

Il fattore di sconto riduce progressivamente il peso delle ricompense lontane nel tempo. Una ricompensa che arriva subito vale di più di una identica promessa fra molti passi, un po’ come accade con il valore del denaro, che oggi preferiamo averlo piuttosto che domani.

Regolare gamma cambia il carattere dell’agente. Un valore vicino a zero lo rende impaziente, concentrato sul guadagno immediato. Un valore vicino a uno lo rende lungimirante, disposto a rinunciare a qualcosa nel presente per un beneficio maggiore in seguito. È una sola manopola, ma il suo effetto sul comportamento è profondo.

La politica: come l’agente decide cosa fare

Fin qui abbiamo descritto il mondo in cui vive l’agente. Ma come decide, concretamente, quale azione compiere? La risposta sta in un concetto centrale: la politica, in inglese policy.

Una politica è una regola che associa a ogni stato l’azione da intraprendere, oppure una distribuzione di probabilità sulle azioni possibili. Nel primo caso si parla di politica deterministica, sempre la stessa mossa in una data situazione, nel secondo di politica stocastica, in cui l’agente sceglie con una certa probabilità. La politica è, in sostanza, il cervello dell’agente, la strategia che ne guida ogni mossa.

Risolvere un processo decisionale di Markov vuol dire trovare la politica ottimale, cioè quella che massimizza la ricompensa totale attesa a lungo termine. Non basta una politica qualsiasi che funzioni, si cerca la migliore in assoluto.

Ed è qui che il modello mostra tutta la sua eleganza. Sotto le condizioni tipiche di un MDP finito esiste sempre almeno una politica ottimale deterministica, e questo garantisce che la ricerca abbia un traguardo ben definito verso cui tendere.

Funzioni di valore ed equazioni di Bellman

Per confrontare le politiche tra loro serve un metro di giudizio. Questo strumento è la funzione di valore, uno dei contributi più importanti dell’intera teoria.

La funzione di valore di stato risponde a una domanda precisa: partendo da un certo stato e seguendo una data politica, quanta ricompensa complessiva posso aspettarmi di accumulare da qui in avanti? Assegna quindi a ogni stato un numero che ne esprime la desiderabilità, non nell’immediato, ma considerando tutto ciò che verrà.

Valore di stato e valore di azione

Accanto al valore di stato esiste una variante ancora più utile nella pratica, la funzione di valore di azione, spesso indicata con la lettera Q. Invece di valutare solo lo stato, valuta la coppia formata da stato e azione: quanto conviene, trovandomi qui, compiere proprio questa mossa e poi proseguire secondo la politica?

La differenza sembra sottile, ma è decisiva. Se conosci il valore Q di ogni azione in ogni stato, scegliere diventa immediato, ti basta prendere in ciascuna situazione l’azione con il valore più alto. Non a caso questa funzione dà il nome a uno degli algoritmi più celebri del settore, il Q-learning, che impara proprio a stimare questi valori attraverso l’esperienza.

L’equazione di Bellman

Come si calcolano questi valori? La chiave è un’idea ricorsiva formulata dal matematico Richard Bellman, e che porta il suo nome. L’equazione di Bellman esprime una relazione tanto semplice quanto profonda: il valore di uno stato è pari alla ricompensa immediata più il valore scontato dello stato in cui ci si ritroverà dopo.

In pratica, il valore del presente si appoggia sul valore del futuro. Ogni stato eredita parte del proprio valore da quelli che lo seguono, in una catena che collega insieme l’intero problema.

Questa struttura ricorsiva è ciò che rende gli MDP risolvibili. Invece di considerare tutte le possibili sequenze di azioni, un numero astronomico, l’equazione di Bellman spezza il problema in sottoproblemi più piccoli, legati tra loro. È il principio su cui si fonda la programmazione dinamica, e rappresenta il ponte teorico che collega la definizione di un MDP agli algoritmi capaci di risolverlo.

Come si risolve un processo decisionale di Markov

Arriviamo alla domanda operativa: dato un MDP, come si trova la politica ottimale? Le strade sono due, e la scelta dipende da quanto conosciamo dell’ambiente.

Quando il modello è noto: la programmazione dinamica

Nel caso più fortunato conosciamo in anticipo tutti gli ingredienti del problema, comprese le probabilità di transizione e le ricompense. In questo scenario possiamo calcolare la soluzione a tavolino, con metodi di programmazione dinamica come l’iterazione di valore e l’iterazione di politica.

L’iterazione di valore parte da stime approssimative e le raffina di continuo, applicando l’equazione di Bellman finché i numeri smettono di cambiare in modo significativo. L’iterazione di politica alterna invece due fasi, la valutazione della politica attuale e il suo miglioramento, ripetendole fino a quando la strategia non può più essere perfezionata.

Entrambi gli approcci convergono verso la politica ottimale. Il limite è evidente, però: richiedono di conoscere in anticipo il funzionamento dell’ambiente, una condizione che nel mondo reale si verifica di rado.

Quando il modello è ignoto: entra in scena l’apprendimento per rinforzo

Molto più spesso l’agente non dispone di una mappa dell’ambiente. Non sa in anticipo quali ricompense otterrà, né dove lo porteranno le sue azioni. Deve scoprirlo agendo, osservando le conseguenze e imparando dall’esperienza.

È esattamente questo il terreno dell’apprendimento per rinforzo. L’agente interagisce ripetutamente con l’ambiente, raccoglie ricompense e aggiorna a poco a poco le proprie stime di valore, senza aver bisogno di conoscere in partenza le probabilità di transizione. Il processo decisionale di Markov fornisce l’impalcatura teorica, mentre l’apprendimento per rinforzo offre gli strumenti pratici per risolverlo quando il modello è nascosto.

Metodi come il già citato Q-learning appartengono a questa famiglia. Imparano una stima dei valori di azione basandosi solo sulle esperienze vissute, correggendo le proprie previsioni ogni volta che la realtà si discosta dalle attese.

Quando gli stati diventano troppi per essere elencati uno per uno, come accade con le immagini di un videogioco o con i sensori di un’automobile, entrano in gioco le reti neurali. Il connubio tra MDP, apprendimento per rinforzo e reti profonde prende il nome di deep reinforcement learning, ed è ciò che ha permesso all’AI di battere i campioni umani in giochi complessi come il Go.

Il dilemma tra esplorazione e sfruttamento

C’è una tensione che accompagna ogni agente alle prese con un MDP quando il modello non è noto, e merita un paragrafo tutto suo. Da un lato l’agente vorrebbe sfruttare ciò che ha già imparato, scegliendo le azioni che finora hanno dato i risultati migliori. Dall’altro sa che potrebbero esistere opzioni ancora inesplorate, capaci di rivelarsi superiori.

Questo conflitto è noto come dilemma tra esplorazione e sfruttamento, in inglese exploration versus exploitation.

Sfruttare troppo presto significa accontentarsi, rischiando di non scoprire mai la strategia davvero ottimale. Esplorare troppo a lungo significa invece sprecare occasioni, provando continuamente azioni mediocri. Il buon apprendimento nasce da un equilibrio tra i due atteggiamenti, un equilibrio che di solito si sposta nel tempo, con molta esplorazione all’inizio e uno sfruttamento crescente man mano che la conoscenza si consolida.

Una strategia semplice e diffusa consiste nello scegliere quasi sempre l’azione migliore conosciuta, riservando però una piccola probabilità a mosse casuali. Basta questa fessura aperta sull’ignoto per permettere all’agente di continuare a imparare.

Dove si usano i processi decisionali di Markov

La teoria è affascinante, ma è nelle applicazioni che il processo decisionale di Markov mostra il suo valore. Il modello è talmente generale da adattarsi a campi lontanissimi tra loro, ogni volta che c’è qualcuno che deve decidere in sequenza sotto incertezza.

Nella robotica gli MDP guidano il movimento e la manipolazione, aiutando una macchina a pianificare azioni in un ambiente fisico imprevedibile. Nei videogiochi e nei giochi da tavolo hanno permesso di costruire agenti capaci di prestazioni sovrumane, imparando strategie che nessuno aveva insegnato loro esplicitamente.

Il modello si ritrova anche nei sistemi di raccomandazione, dove ogni contenuto proposto è un’azione che modifica lo stato di attenzione dell’utente, e nella gestione di risorse, dai data center che regolano il consumo energetico alle reti di telecomunicazione che instradano il traffico.

C’è poi un ambito che negli ultimi tempi è tornato al centro della scena. Gli assistenti conversazionali più avanzati vengono perfezionati con tecniche di apprendimento per rinforzo che affondano le radici proprio nel formalismo degli MDP. È il caso dell’RLHF, la metodologia con cui si allineano i grandi modelli linguistici alle preferenze umane, considerando la generazione di una risposta come una sequenza di decisioni da ricompensare.

Questa parentela spiega perché il tema sia oggi così attuale. Gli agenti autonomi, capaci di svolgere compiti articolati muovendosi tra strumenti e ambienti digitali, sono una delle direzioni più promettenti dell’intelligenza artificiale, e il loro modo di ragionare si radica nel linguaggio dei processi decisionali di Markov.

Limiti del modello e le sue estensioni

Nessun modello è perfetto, e anche il processo decisionale di Markov ha i suoi confini. Il più evidente riguarda proprio l’ipotesi da cui prende il nome, l’idea che lo stato osservato racchiuda tutta l’informazione utile. Nel mondo reale l’agente raramente vede lo stato completo, e deve accontentarsi di osservazioni parziali e talvolta rumorose.

Per affrontare questa situazione è stata sviluppata un’estensione importante, il processo decisionale di Markov parzialmente osservabile, noto con la sigla POMDP. Qui l’agente non conosce con certezza lo stato in cui si trova, ma solo indizi da cui deve inferirlo, mantenendo una sorta di convinzione, in inglese belief, su dove potrebbe essere.

Un altro limite pratico è la cosiddetta maledizione della dimensionalità. Quando gli stati e le azioni si moltiplicano, calcolare i valori per ognuno diventa proibitivo, e le tabelle esplodono di dimensione.

Proprio da qui nasce l’incontro con le reti neurali, chiamate ad approssimare le funzioni di valore quando enumerarle non è più possibile. E resta aperta la sfida di definire ricompense che catturino davvero ciò che desideriamo, perché una funzione di ricompensa mal congegnata può spingere l’agente verso comportamenti astuti quanto indesiderati.

Conclusioni: perché vale la pena capire gli MDP

Il processo decisionale di Markov non è soltanto una formula da studiare, è un modo di pensare i problemi. Ci insegna a scomporre una decisione complessa in una catena di scelte più semplici, a mettere in conto l’incertezza invece di ignorarla, e a bilanciare il guadagno immediato con quello futuro. Sono principi che valgono ben oltre l’informatica.

Chi lavora con l’intelligenza artificiale trova negli MDP il vocabolario comune che unisce la teoria dell’apprendimento per rinforzo alle sue applicazioni più spettacolari. Stati, azioni, ricompense, politiche e funzioni di valore sono i mattoni con cui si costruiscono gli agenti che oggi giocano, guidano, raccomandano e conversano.

Se questa guida ti ha incuriosito, il passo naturale è approfondire gli algoritmi che danno vita a tutto questo. Parti dal Q-learning per capire come un agente impara dai valori, esplora il deep reinforcement learning per vedere cosa succede quando entrano in scena le reti neurali, e osserva nell’RLHF come questi principi plasmino gli assistenti che usi ogni giorno. La strada dell’apprendimento per rinforzo comincia sempre da qui, da un agente, un ambiente e la domanda più importante di tutte: qual è la scelta migliore da fare adesso?