Struttura dati per processo decisionale Markov

Question

Ho implementato l'algoritmo di iterazione del valore per il processo decisionale Markov semplice Wikipedia in Python. Al fine di mantenere la struttura (stati, azioni, transizioni, premi) del particolare processo di Markov e scorrere su di esso ho usato le seguenti strutture di dati:

1. dizionario per gli stati e le azioni che sono disponibili per coloro afferma:

   SA = { 'state A': {' action 1', 'action 2', ..}, ...}

2. dizionario per probabilità di transizione:

   T = {('state A', 'action 1'): {'state B': probability}, ...}

3. dizionario per i premi:

   R = {('state A', 'action 1'): {'state B': reward}, ...}.

La mia domanda è: è questo l'approccio giusto? Quali sono le strutture dati più adatte (in Python) per MDP?

Answer 1

Se una struttura dati è adatta o meno dipende principalmente da ciò che si fa con i dati. Si dice che si desidera ripetere il processo, quindi ottimizzare la struttura dei dati per questo scopo.

Le transizioni nei processi Markov sono spesso modellate da moltiplicazioni di matrice. Le probabilità di transizione Pa(s1,s2) e i premi Ra(s1,s2) potrebbero essere descritti da matrici (potenzialmente sparse) Pa e Ra indicizzate dagli stati. Penso che questo avrebbe alcuni vantaggi:

• Se si utilizzano array numpy per questo, l'indicizzazione sarà probabilmente più veloce che con i dizionari.
• Anche le transizioni di stato potrebbero quindi essere semplicemente descritte mediante moltiplicazione di matrice.
• La simulazione del processo con la selezione della ruota della roulette, ad esempio, sarà più veloce e più chiaramente implementata, poiché è sufficiente selezionare la corrispondente colonna della matrice di transizione.

Answer 2

ho implementato Markov Decision Processes in Python prima e trovato il seguente codice utile.

http://aima.cs.berkeley.edu/python/mdp.html

Questo codice è tratto dal Intelligenza Artificiale: un approccio moderno da Stuart Russell e Peter Norvig.

Answer 3

Esiste un'implementazione di MDP con python chiamato pymdptoolbox. È sviluppato in base all'implementazione con Matlab chiamato MDPToolbox. Entrambi sono degni di nota.

Fondamentalmente, la matrice di transizione probabilità viene rappresentato come (A × S × S) matrice e ricompense come (S × A) matrice, dove S e A rappresentano il numero di stati e il numero di azioni. Il pacchetto ha anche un trattamento speciale per la matrice sparsa.