questions de processus de décision de Markov [fermé]

Question

texte alt http://img693.imageshack.us/img693/724/markov .png

Je suis un peu confus au sujet de certains points ici:

1. Qu'est-ce que ça veut dire qu'il sera couronné de succès 70% du temps, il tente une action donnée? Est-ce que cela veut dire que chaque fois qu'il tente d'effectuer une action A, elle 70% du temps faire que l'action A et l'autre 30% faire l'action qui conduit au même état, ou tout simplement qu'il est comme il le faisait toujours l'action A, mais seulement 30% du temps, il ne vient non? J'espère que je me fais bien comprendre: (
2. Comment est-il possible d'avoir plusieurs états consécutifs avec la même utilité? En théorie, l'utilitaire ne doit pas toujours diminuer, plus vous êtes des Etats avec une récompense?
3. Sachant que les informations que j'ai donné ci-dessus, est-il possible de déduire quelle est la facteur d'actualisation (gamma)? Si oui, comment?
4. Est-il possible de calculer la Récompense pour les États? Comment?

Answer 1

Il y a un modèle pour traiter la plupart des problèmes MDP, mais je pense que vous avez probablement omis certaines informations de la description du problème, le plus probable qu'il a à voir avec l'état que vous essayez d'atteindre, ou la façon dont un épisode extrémités (ce qui se passe si vous exécutez le bord de la grille). Je l'ai fait de mon mieux pour répondre à vos questions, mais je l'ai joint une amorce sur le processus que j'utilise pour traiter ces types de problèmes.

Tout d'abord l'utilité est une mesure assez abstraite de combien vous voulez être dans un état donné. Il est certainement possible d'avoir deux états avec utilité égale, même lorsque l'on mesure l'utilité avec des heuristiques simples (euclidiennes ou à distance Manhattan). Dans ce cas, je suppose que la valeur d'utilité et de récompense sont interchangeables.

À long terme, l'objectif de ces types de problèmes tend à être, Comment maximiser votre attendu (long terme) récompense? Le taux d'apprentissage, gamma, contrôle le niveau de l'accent que vous placez sur l'état actuel par rapport à l'endroit où vous souhaitez finir - efficace que vous pouvez penser gamma un spectre allant de « faire la bonne chose les avantages m'a le plus dans ce timestep » à l'autre extrême < em> « explorer toutes mes options, et revenir au meilleur » . Sutton et Barto là-bas livre sur ont une certaine vraiment sympa href="http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node30.html" de la façon dont cela fonctionne.

---

Avant de commencer, revenir par la question et assurez-vous que vous pouvez en toute confiance répondre aux questions suivantes.

1. Qu'est-ce qu'un Etat? Combien d'états sont là?
2. Qu'est-ce qu'une action? Combien d'actions sont là?
3. Si vous commencez à l'état u, et que vous appliquez une action a, quelle est la probabilité d'atteindre un nouvel état v?

Ainsi, les réponses aux questions?

1. Un état est un vecteur (x, y). La grille est de 5 par 5, de sorte qu'il y a 25 états.
2. Il y a quatre actions possibles, {E, N, S, W}
3. La probabilité d'atteindre avec succès un état adjacent après l'application d'une action appropriée est de 0,7, la probabilité de ne pas se déplacer (en restant dans le même état est de 0,3). Si l'on suppose (0,0) est la cellule supérieure gauche et (4,4) est la cellule en bas à droite, le tableau suivant présente un petit sous-ensemble de toutes les transitions possibles.

Start State Action           Final State    Probability
---------------------------------------------------
(0,0)           E               (0,0)          0.3
(0,0)           E               (1,0)          0.7
(0,0)           E               (2,0)          0
...
(0,0)           E               (0,1)          0
... 
(0,0)           E               (4,4)          0
(0,0)           N               (0,0)          0.3
...
(4,4)           W               (3,4)          0.7
(4,4)           W               (4,4)          0.3

Comment peut-on vérifier que cela a un sens pour ce problème?

1. Vérifiez que la table a un nombre approprié d'entrées. Sur un 5 par 5 grille il y a 25 états et 4 actions, de sorte que le tableau doit avoir 100 entrées.
2. Vérifier pour vous assurer que pour un état de démarrage / d'action paire, deux entrées ont non nulle probabilité de se produisant.

---

Modifier. répondre à la demande pour les probabilités de transition à l'état cible. La notation ci-dessous suppose

• v est l'état final
• u est l'état de la source
• a est l'action, où il n'est pas mentionné, il est sous-entendu que l'action appliquée n'est pas pertinente.

P( v=(3,3) | u =(2,3), a=E ) = 0.7
P( v=(3,3) | u =(4,3), a=W ) = 0.7
P( v=(3,3) | u =(3,2), a=N ) = 0.7
P( v=(3,3) | u =(3,4), a=S ) = 0.7
P( v=(3,3) | u =(3,3) ) = 0.3

Answer 2

ad.1) probablement il n'est pas ce robot doit toujours se déplacer - à savoir les 30% sont « ah, maintenant je reste un peu » ou « il n'y avait pas le pouvoir de bouger ».

Answer 3

Je l'ai formulé ce problème comme la décision-Horizon de Markov Finite processus et résolu via Policy Iteration. A droite de chaque itération, il y a une représentation de grille code couleur des actions recommandées pour chaque état, ainsi que la grille / matrice de récompense originale.

Revoir la politique finale / stratégie à l'étape 4. Est-il d'accord avec votre intuition?