• 🏡 Home
  • 🚨 GDPR Compliant
  • ⚡️ Data Science
  • 📌 Machine Learning
  • 🔒 Privacy Preserving
  • 🏡 Home
  • 🚨 GDPR Compliant
  • ⚡️ Data Science
  • 📌 Machine Learning
  • 🔒 Privacy Preserving
machine-learning

Tutto sul Markov Decision Process (MDP) | Reinforcement Learning

Tutto sul Markov Decision Process (MDP) | Reinforcement Learning

Il Markov Decision Process (MDP) o processo decisionale di Markov è un modello di gestione dello stato di transizione di un agente in un ambiente dinamico e casuale, dunque non deterministico.

Fornisce un modello matematico per modellare un processo decisionale in quelle situazioni in cui il risultato è parzialmente casuale (random), e in parte sotto controllo di un decisore (decision maker).

Una definizione molto comoda per compiacere il nostro interlocutore, ma poco utile per comprendere a fondo il significato di questo concetto.

Dobbiamo scendere più a fondo.

I mariani hanno ricevuto ordini.

Cambusa riempita e vele spiegate: siamo pronti per questo nuovo viaggio!

Scopriamo insieme in cosa consiste il Markov Decision Process, e sopratutto perché sia importante.

Markov Decision Process

Per capire a fondo cosa sia un processo decisionale di markov dobbiamo fare chiarezza su almeno due conceti:

  • La catena di Markov, o Markov chain
  • La proprietà di Markov o Markov property

Iniziamo dal primo.

Markov Chain

Nei primi anni del secolo scorso, il matematico russo Andrej Markov studiò i processi stocastici, che involvono un elemento di casualità, senza memoria, chiamati catene di Markov o Markov Chains.

Un tale processo ha un numero fisso di stati, ed evolve in modo casuale da uno stato all’altro, a ogni step.

La probabilità che l’evoluzione avvenga dallo stato s a quello s’ è fissa e dipende unicamente dalla coppia (s, s’) e non dagli stati passati, ergo per cui definiamo il sistema come privo di memoria.

Privo di memoria?

No, non ha bevuto la sera prima e dimenticato la festa in spiaggia tornando a casa con un male alla testa da Guiness World Record.

Possiamo però fare chiarezza sull’argomento.

Markov Property

Tecnicamente, l’indipendenza dagli stati passati in un processo stocastico è definita in Teoria della Probabilità come Markov property, trovi un approfondimento qui.

La Markov Property è il discriminante per distinguere i Markov Process.

Diciamo infatti che un processo stocastico si definisce Markov Process se e solo se risulti caratterizzato dalla Markov Property, e quindi se la distribuzione di probabilità condizionata dei futuri stati del processo (condizionata su entrambi gli insiemi di stati futuri e passati) dipende unicamente dallo stato presente e non dalla sequenza di eventi precedenti.

Devi sapere anche un’altra cosa fondamentale.

Da un punto di vista matematico, un processo stocastico altro non è che una famiglia di variabili casuali (i.e. Il cui valore dipende da un fenomeno aleatorio, cioè casuale) indicizzate da un parametro temporale.

Distinguiamo allora un processo stocastico tempo-discreto (o tempo-continuo) a seconda che lo spazio della variabile tempo sia discreto (o continuo).

Ora hai tutti gli strumenti per capire cosa sia davvero una Markov chain: un processo stocastico tempo-discreto (i.e. Discreto nel tempo) che soddisfa la Markov property.

Le Markov chains sono utilizzate in molte aree, tra cui termodinamica, chimica, statistica e altre.

Vediamo ora cosa sia un Markov decision process.

Markov Decision Processes

Fu Richard Bellman a descrivere per la prima volta i Markov Decision Processes in una celebre pubblicazione degli anni ’50.

I Markov Decision Processes sono allora un’estensione delle Markov Chains, con due aggiunte:

  • Azioni, actions (i.e. Permettono una scelta)
  • Ricompense, rewards (i.e. Motivano l’agente)

Quando esiste una sola azione per ogni step, e tutte le ricompense sono uguali, il processo decisionale di Markov (Markov decision process) si riduce a una catena di Markov (Markov chain).

Osserviamo allora un esempio di Markov decision process.

Hands-On Machine Learning with Tensorflow

Il MDP in figura ha 3 stati e al massimo 3 azioni per ogni step.

Iniziando allo stato s0 l’agente può scegliere una delle 3 azioni a0,a1,a2.

Se scegliesse l’azione a1 rimarrebbe nello stato s0 con certezza (probabilità 1.0) senza ottenere alcuna ricompensa.

Se scegliesse l’azione a0, avrebbe il 70% di probabilità di guadagnare una ricompensa di 10 punti e rimanere nello stato s0. In questo caso l’agente potrebbe optare per la medesima scelta ottenendo quante più ricompense possibili, benché a un certo punto raggiungerà lo stato s1.

Nello stato s1 le azioni sono 2: a0 e a2.

L’agente può ora scegliere di stare ripetutamente nello stato optando per l’azione a0. L’azione a2 permetterebbe invece all’agente di raggiungere lo stato s2 seppur con una ricompensa negativa di 50 punti.

Dallo stato s2 la sola azione concessa è l’a0 che riporterebbe l’agente allo stato iniziale con una ricompensa di 40 punti.

Bellman individuò un modo per stimare un parametro, l’optimal state value di qualunque stato s, espresso come V*(s) inteso come somma di tutte le future ricompense scontate (i.e. Con applicato il discount rate, spiegato in questo post) che l’agente può potenzialmente ricevere in media dopo aver raggiunto lo stato s, assumendo che agisca in modo ottimale.

Bellman dimostrò che quando l’agente agisce in modo ottimale, la Bellman Optimality Equation può essere applicata.

Si tratta di un’equazione ricorsiva che, assumendo che l’agente agisca in modo ottimale, permette il calcolo dell’optimal state value, dello stato corrente come la somma delle ricompense che potrebbe ottenere in media optando per l’azione ottimale e la stima dell’optimal state value di tutti i possibili stati a cui l’azione designata porterebbe.

Questa equazione conduce a un algoritmo in grado di stimare precisamente l’optimal state value di ogni possibile stato: inizializzando ogni parametro a zero, e aggiornandoli iterativamente usando il Value Iteration Algorithm.

Il punto di forza di questo metodo è la garanzia che i valori stimati convergano all’optimal state values di ogni stato, costituendo dunque la policy ottimale.

Per il momento è tutto.

Per aspera, ad astra.

Un caldo abbraccio, Andrea.

Written by Andrea Provino - Agosto 9, 2020
Tags | machine learning, reinforcement learning, teoria

You Might Also Like

privacy-preserving-tracking-app-immuni-italia-bending-spoons-guida-italia-machine-learning-data-science-blog

Privacy Preserving Tracing App: cosa significa davvero?

Aprile 24, 2020

Guida segmentazione semantica | Tensorflow, machine learning e computer vision

Dicembre 26, 2018
k-means-clustering-data-science-machine-learning-blog-teoria-unsupervised-clustering-algorithm-scaled

k-means Clustering

Novembre 15, 2019
Next Post
Previous Post

Una pubblicità che non vedi se usi AdBlock

EXPAND YOUR KNOWLEDGE

  • Blockchain Developer

    Circuito aritmetico

    Novembre 1, 2022
  • machine-learning

    Un nuovo inizio

    Settembre 4, 2021
  • Zero Knwoledge Proof Article Privacy Preserving

    Zero Knowledge Proof: zk-SNARK e zk-STARK | Prova a conoscenza zero

    Luglio 8, 2021
  • oblivious-transfer-spiegazione-italiano-ot-explanation Privacy Preserving

    Oblivious Transfer (OT)

    Luglio 6, 2021
  • Aleo Studio Website Preview machine-learning

    Aleo Studio: un IDE per Zero-Knowledge Proofs Applications

    Luglio 1, 2021
  • privacy-enhancing-technologies-data-machine-learning-data-science Privacy Preserving

    Perché il Privacy Tech è un vantaggio competitivo micidiale

    Giugno 17, 2021
  • bloom-filter-spiegazione-italian Privacy Preserving

    Bloom Filter

    Giugno 3, 2021
  • trusted-execution-environment-tee-data-science-come-fuziona Data Science, Privacy Preserving

    Trusted Execution Environment | Cos’è un TEE?

    Giugno 2, 2021
  • Crypto Custody services machine-learning

    Crypto Custody: Guida alla custodia delle criptomonete

    Maggio 26, 2021
  • deep-q-learning-q-learning-reinforcement-learning machine-learning

    Deep Q-Learning

    Aprile 27, 2021

Quello che Google pensa ti possa piacere

Prodotti che i Cookie dicono potresti trovare interessanti

AI Blog - © 2019-2021 Andrea Provino