J'ai mis en œuvre l'algorithme d'itération de la valeur pour le processus de décision de Markov simple Wikipedia en python. Afin de conserver la structure (états, actions, transitions, récompenses) du processus de Markov en particulier et que je les ai utilisés, j'ai utilisé les structures de données suivantes:
Dictionnaire des États et des actions disponibles pour ceux qui sont disponibles États:
Dictionnaire pour les probabilités de transition:
Dictionnaire pour les récompenses:
Ma question est la suivante: est-ce la bonne approche? Quelles sont les structures de données les plus appropriées (en python) pour le MDP? SA = {'State a': {'Action 1', 'Action 2', ..}, ...}, ...}
t = {('état a', 'action 1'): {'état b': probabilité}, ...}
r = {('State A', 'Action 1'): {'State B': récompense}, ...} .
3 Réponses :
Si une structure de données convient ou non sur ce que vous faites avec les données. Vous mentionnez que vous souhaitez itération sur le processus, optimisez donc votre structure de données à cet effet.
Les transitions dans les processus Markov sont souvent modélisées par les multiplications matricielles. Les probabilités de transition pa (s1, s2) et les récompenses ra (S1, S2) Pourraient être décrites par (potentiellement clairsemé) Matrices PA et ra indexé par les états. Je pense que cela aurait quelques avantages:
Merci beaucoup pour vos commentaires. Je vais envisager votre approche au moins en cas de résolution de MDPS plus complexes.
J'ai mis en œuvre les processus de décision de Markov dans Python avant et trouvé le code suivant utile.
http://aima.cs.berkeley.edu/python/mdp.html
Ce code est pris de intelligence artificielle: une approche moderne par Stuart Russell et Peter Norvig.
Tandis que cela peut théoriquement répondre à la question, Ce serait préférable d'inclure les parties essentielles de la réponse ici et de fournir le lien pour référence.
Il y a une implémentation de MDP avec python appelé pympdptoolbox . Il est développé sur la base de la mise en œuvre avec MATLAB appelée MDPoolbox . Les deux méritent de noter.
Fondamentalement, la matrice de transition de probabilité est représentée en tant que ( A × S) × ST s ) tableau et récompense en tant que ( S × une matrice ), où s et a représente le nombre d'états et de nombre d'actions. Le paquet a également un traitement spécial pour la matrice clairsemé.