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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
דוגמה לתהליך החלטה מרקובי שבו שלושה מצבים (בירוק), שתי פעולות (באדום)

תהליך החלטה מרקוביאנגלית: 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) ועבור תהליכי החלטה לזמן רציף כשהקריטריון למיקסום הוא אינטגרל.

אלגוריתמים[עריכת קוד מקור | עריכה]

קיימים אלגוריתמים שונים לפתרון בעיות של תהליך החלטה מרקובי, אלגוריתמים אלו מבוססים בדרך כלל על תכנון דינמי או על תכנון לינארי.

בגישה של פתרון באמצעות תכנון דינמי מגדירים לרוב שני מערכים: אחד המגדיר את ערכי התגמול הממוצעים לכל מצב (V), ואחד המגדיר את המדיניות (\pi) לכל מצב. ניתן להשיג פתרון באמצעות חזרה על שני השלבים הבאים:

  • חישוב מדיניות:  \pi(s) := \arg \max_a \left\{ \sum_{s'} P_a(s,s') \left( R_a(s,s') + \gamma V(s') \right) \right\}
  • חישוב תגמול:  V(s) := \sum_{s'} P_{\pi(s)} (s,s') \left( R_{\pi(s)} (s,s') + \gamma V(s') \right)

קיימות גרסאות שונות לאלגוריתם, כאשר בחלקן עוברים על כל המצבים ובחלקן עוברים על כל מצב בנפרד, או עוברים בשכיחות שונה על המצבים. דוגמאות לגרסאות נפוצות לאלגוריתם זה הן

  • Value iteration - בה משלבים את חישוב המדיניות עם חישוב התגמול ומתקבל הכלל המאוחד:  V_{i+1}(s) := \max_a \left\{ \sum_{s'} P_a(s,s') \left( R_a(s,s') + \gamma V_i(s') \right) \right\},
  • Policy iteration - בגרסה זו מחשבים את המדיניות פעם אחת, ולאחר מכן מחשבים את התגמול שוב ושוב עד להתכנסות. כאשר שלב חישוב התגמול מתכנס, מחשבים מחדש את המדיניות.
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.