תהליך החלטה מרקובי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

תהליך החלטה מרקוביאנגלית: Markov Decision Process או MDP) הוא מודל מתמטי לתהליכי החלטה שבה פונקציית המעברים של המערכת מקיימת את תכונת מרקוב, קרי ההסתברות להגיע למצב כלשהו תלויה אך ורק במצב ופעולה נבחרת קודמת. המודל קרוי על שמו של אנדריי מרקוב והוא הרחבה של המודל של שרשרת מרקוב שנעשתה עם פיתוחו של ענף התכנון הדינאמי על ידי ריצ'רד בלמן בשנות ה-50 של המאה העשרים.

בצורתו הבסיסית מוגדר תהליך החלטה מרקובי באמצעות הפרמטרים (S,A,P_\cdot(\cdot,\cdot),R_\cdot(\cdot,\cdot),\gamma) כך ש:

  • S הוא מרחב המצבים של המערכת.
  • A הוא מרחב הפעולות.
  • P היא פונקציית הסתברות למעבר בין מצבים מתוך S בהינתן ביצוע פעולה מתוך A המוגדרת  P: S {\times} S {\times} A \to [0,1]
  • R היא פונקציית התגמול המתאימה ערך מספרי לכל מצב (או לחלופין לכל צירוף של מצב ופעולה).
  • \gamma הוא פקטור בתחום (0,1) שתפקידו לקבוע עד כמה מדיניות הפעולה לגיבוש תהיה מושפעת מתגמולים שהתקבלו באינטראקציות מאוחרות בזמן.

במסגרת מודל זה, יש למצוא מדיניות פעולה \pi:S\to A כך שהתגמול הכולל לאורך זמן הניסוי \sum_{t=0}^{\infty}\gamma^tR(s_t,\pi(s_t)) עבור s_t \in S יהיה גבוה ככל שניתן. כדי לגבש מדיניות בחירת פעולות מתאימה תחת מודל זה, נעזרים באלגוריתמים מתחומי למידת חיזוק ובקרה אופטימלית. כמו כן קיימות גרסאות של המודל עבור מרחבי מצבים שניתנים לצפיה חלקית (Partially Observable MDP או POMDP) ועבור תהליכי החלטה לזמן רציף כשהקריטריון למיקסום הוא אינטגרל.

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.