Processi Decisionali di Markov Flashcards
Cosa sono i processi decisionali di Markov?
Un Processo Decisionale di Markov (MDP, Markov Decision Process) è un modello matematico usato per rappresentare situazioni che coinvolgono una scelta in un ambiente incerto.
Formalmente, un MDP è definito dai seguenti elementi:
Insieme degli Stati (S): Questo rappresenta l’insieme di tutti gli stati possibili in cui un agente può trovarsi durante l’interazione con l’ambiente. Gli stati possono essere discreti o continui e definiscono il contesto in cui l’agente prende decisioni.
Insieme delle Azioni (A): Questo rappresenta l’insieme di tutte le possibili azioni che l’agente può intraprendere in ogni stato. Le azioni possono variare da uno stato all’altro.
Funzione di Transizione di Stato (T o P): Questa funzione descrive le probabilità di transizione tra gli stati quando vengono intraprese determinate azioni. In altre parole, stabilisce come l’ambiente risponde alle azioni dell’agente. È spesso rappresentata come una matrice di transizione.
Funzione di Ricompensa (R): Questa funzione definisce le ricompense o penalizzazioni associate a ciascuna transizione stato-azione. La funzione di ricompensa assegna un valore numerico a ciascuna coppia stato-azione e misura quanto è desiderabile o indesiderabile uno stato o un’azione.
e fattoredi sconto
Cosa dice la proprietà di Markov?
La proprietà di Markov si riferisce all’indipendenza condizionale di un evento futuro rispetto a tutto il passato, dato il presente.
In altre parole, un processo con la proprietà di Markov è caratterizzato dal fatto che la probabilità di transizione tra gli stati futuri dipende solo dallo stato presente e non dai dettagli dell’intera storia passata. Questo significa che l’evoluzione del processo dipende solo dallo stato corrente e dalle azioni intraprese in quel momento, rendendo il processo “senza memoria” rispetto al passato oltre allo stato corrente.
In un contesto di catene di Markov, la proprietà di Markov è definita in termini di probabilità condizionali. Formalmente, un processo (o catena) stocastico soddisfa la proprietà di Markov se:
P(X_n+1 | X_0, X_1, …, X_n) = P(X_n+1 | X_n)
Dove X_n rappresenta lo stato al tempo n. Questo significa che la probabilità di transizione tra due stati successivi è determinata solo dallo stato attuale e non da tutti i passi intermedi.
Cos’è la matrice di transizione di stato?
Rappresenta le probabilità di transizione tra gli stati in un sistema stocastico, cioè le probabilità di passare da uno stato a un altro al passaggio di ciascun passo temporale.
La matrice di transizione di stato è solitamente denotata con diverse notazioni, tra cui P, T, o A, ed è definita come segue:
Supponiamo di avere N stati nell’ambiente o nel sistema che stiamo modellando. La matrice di transizione P (o T o A) è una matrice quadrata di dimensioni N x N, in cui ogni elemento P(i, j) rappresenta la probabilità di transizione dallo stato i allo stato j in un passo temporale. Queste probabilità di transizione soddisfano alcune regole, tra cui:
Ogni elemento della matrice è non negativo: 0 <= P(i, j) <= 1.
Per ciascuna riga della matrice, la somma di tutte le probabilità di transizione deve essere uguale a 1. Questo perché, dato uno stato, l’agente deve andare in uno dei possibili stati successivi.
Nel contesto dei MDP, la matrice di transizione di stato è utilizzata per definire come l’ambiente risponde alle azioni intraprese dall’agente in ciascuno stato. In altre parole, specifica le probabilità di andare da uno stato all’altro quando l’agente intraprende un’azione specifica.
Cos’è un processo di Markov?
Un processo di Markov è un processo casuale senza memoria, cioè una sequenza di stati casuali S_1, S_2, … caratterizzati dalla proprietà di Markov
Un processo di Markov (o catena di Markov) è una tupla <S, P>
-S è un insieme (finito) di stati
-P è una matrice di probabilità di transizione di stato
P_ss’=P[S_t+1=s’ | S_t=s]
Cos’è un processo di ricompensa di Markov?
Un processo di ricompensa di Markov è una tupla <S, P, R, γ>
-S è un insieme (finito) di stati
-P è una matrice di probabilità di transizione di stato
P_ss’=P[S_t+1=s’ | S_t=s]
-R è una funzione di ricompensa,
R_s=E[R_t+1 | S_t=s]
-γ è un fattore di sconto, γ ∈ [0,1]
Perchè i processi decisionali e di ricompensa di Markov sono scontati?
I Processi Decisionali di Markov (MDP) e i Processi di Ricompensa di Markov (MRP) sono spesso modellati con sconto per una serie di ragioni, tra cui la gestione del futuro incerto
Questo sconto è noto come il “fattore di sconto” e rappresenta la preferenza dell’agente per le ricompense immediate rispetto a quelle future. Ecco alcune ragioni per cui il sconto è incorporato in questi modelli:
Gestione dell’incertezza: Nell’ambito dei MDP e dei MRP, l’agente deve prendere decisioni in ambienti incerti, dove le ricompense future possono essere soggette a variabilità o incertezza. L’introduzione del sconto permette di attribuire un valore maggiore alle ricompense immediate rispetto a quelle future, riflettendo la preferenza dell’agente per la certezza a breve termine.
Cos’è la Bellman Equation per MRP?
la Bellman Equation viene utilizzata per esprimere il valore di uno stato in termini del suo valore atteso e dei valori degli stati successivi.
Nel contesto dei MRP, stiamo cercando di determinare il valore di uno stato, che rappresenta l’aspettativa cumulativa delle ricompense future a partire da quel particolare stato. La Bellman Equation per i MRP è espressa come segue per uno stato s:
La Bellman Equation per uno stato s:
Formula
Dove:
V(s) rappresenta il valore dello stato s, ovvero l’aspettativa cumulativa delle ricompense future partendo dallo stato s.
R(s) è la ricompensa immediata ottenuta nello stato s.
γ è il fattore di sconto che rappresenta la preferenza dell’agente per le ricompense immediate rispetto a quelle future. È un valore compreso tra 0 e 1.
Σ_s’ indica una somma su tutti gli stati successivi s’ che possono essere raggiunti dallo stato s.
P(s’ | s) rappresenta la probabilità di transizione dallo stato s allo stato successivo s’.
L’equazione esprime il valore di uno stato come la somma della ricompensa immediata nello stato s e del valore scontato atteso di tutti gli stati successivi s’, pesati dalle probabilità di transizione P(s’ | s).
+ Matrice + Soluzione
Cos’è la state-value function? e la action-value function?
State-Value Function (Vπ o V(s)):
La state-value function per una politica specifica π è una funzione che assegna a ciascuno stato s l’aspettativa del valore cumulativo ottenuto partendo da quel determinato stato e seguendo la politica π. In altre parole, Vπ(s) rappresenta il valore atteso delle ricompense cumulative ottenute a partire da s e seguendo la politica π.
Formalmente, la state-value function è definita come: Vπ(s) = Eπ[∑(t=0 to ∞) γ^t * R_t+1 | S_0 = s], dove Eπ indica l’aspettativa sotto la politica π, γ è il fattore di sconto, R_t+1 è la ricompensa ottenuta al passo temporale t+1 e S_0 è lo stato iniziale.
Action-Value Function (Qπ o Q(s, a)):
La action-value function per una politica specifica π (denotata come Qπ) è una funzione che assegna a ciascuna coppia stato-azione (s, a) l’aspettativa del valore cumulativo ottenuto partendo da s, intraprendendo l’azione a e seguendo la politica π. In altre parole, Qπ(s, a) rappresenta il valore atteso delle ricompense cumulative ottenute a partire da s, intraprendendo l’azione a e seguendo la politica π.
Formalmente, la action-value function è definita come: Qπ(s, a) = Eπ[∑(t=0 to ∞) γ^t * R_t+1 | S_0 = s, A_0 = a], dove Eπ indica l’aspettativa sotto la politica π, γ è il fattore di sconto, R_t+1 è la ricompensa ottenuta al passo temporale t+1, S_0 è lo stato iniziale e A_0 è l’azione iniziale.
Cos’è la optimal state-value-function e la optimal action-value function?
Queste funzioni rappresentano il valore ottimale di uno stato o di una coppia stato-azione sotto la migliore politica possibile, ovvero la politica che massimizza le ricompense cumulative nel lungo termine. Le notazioni tipiche per queste funzioni sono V* per la funzione di valore di stato ottimale e Q* per la funzione di valore di azione ottimale.
Ecco come sono formalmente definite:
*Optimal State-Value Function (V)**:
La funzione di valore di stato ottimale, denotata come V, rappresenta il valore ottimale di uno stato s. Questo valore è l’aspettativa del valore cumulativo ottimale ottenuto partendo da s e seguendo la politica ottimale.
Formalmente, la funzione di valore di stato ottimale è definita come: V(s) = max_π Vπ(s), dove max_π indica la politica che massimizza il valore atteso tra tutte le possibili politiche π.
*Optimal Action-Value Function (Q)**:
La funzione di valore di azione ottimale, denotata come Q, rappresenta il valore ottimale di una coppia stato-azione (s, a). Questo valore è l’aspettativa del valore cumulativo ottimale ottenuto partendo da s, intraprendendo l’azione a e seguendo la politica ottimale.
Formalmente, la funzione di valore di azione ottimale è definita come: Q(s, a) = max_π Qπ(s, a), dove max_π indica la politica che massimizza il valore atteso tra tutte le possibili politiche π.
Cos’è la policy ottimale?
La “policy ottimale” (politica ottimale) in un Processo Decisionale di Markov (MDP) è la politica che massimizza il valore atteso delle ricompense cumulative nel lungo termine. La policy ottimale è la scelta delle azioni in ciascuno stato che permette all’agente di ottenere la massima ricompensa complessiva nel corso del tempo.
Formalmente, la policy ottimale è denotata come π* e può essere definita come segue:
Data un MDP con insiemi di stati (S), azioni (A), funzioni di transizione (T o P), funzioni di ricompensa (R), e un fattore di sconto (γ), la policy ottimale π* è la politica che massimizza il valore atteso del valore di stato ottimale V*(s) in ciascuno stato s. Questo può essere espresso come:
π* = argmax_π Eπ [Σ_t=0 to ∞ γ^t * R_t+1 | S_0 = s]
Dove:
π* è la policy ottimale.
Eπ indica l’aspettativa sotto la politica π.
Σ_t rappresenta la somma su tutti i passi temporali t.
γ è il fattore di sconto.
R_t+1 è la ricompensa ottenuta al passo temporale t+1.
S_0 è lo stato iniziale.
La policy ottimale è quella che massimizza il valore cumulativo aspettato nel corso del tempo e, di conseguenza, fornisce al sistema la migliore sequenza di azioni da intraprendere in ciascuno stato per raggiungere l’obiettivo desiderato.
Teorema:
Per ogni processo decisionale di Markov Esiste una policy ottimale π∗ che è migliore o uguale a tutte le altre policy, π∗ ≥ π, ∀π
Tutte le policy ottimali condividono la stessa optimal statevalue function, vπ∗ (s) = v∗(s)
Tutte le policy ottimali condividono la stessa optimal actionvalue function, qπ∗ (s, a) = q∗(s, a)
Come individuare una policy ottimale se conosciamo un action value function ottimale?
Una policy ottimale può essere individuata massimizzando q∗(s,a),
π∗(a|s) = { 1 se a=argmax q∗(s,a) , 0 altrimenti
Esiste sempre una policy ottimale deterministica per ogni mdp se q∗(s,a) è noto, si ottiene immediatamente la policy ottimale
Cos’è il guadagno?
A partire dalle ricompense ci possiamo calcolare il guadagno Gt che è il guadagno atteso all’istante t, nello specifico sarebbe la ricompensa totale ed è dato dalla somma di tutte le ricompense che otterrò dall’istante t+1 in poi
G_t=R_(t+1) + γR_(t+2)+…=Sum(k=0 -> infinito) di γ^k R_(t+k+1)
La gamma mi dice il valore attuale delle ricompense e deve sommare 1.
per dare più importanza alle ricompense attuali diamo gamma = 1 ad esse mentre a quelle successive attribuiamo un valore minore di 1 perchè quelle future di solito sono incerte.
