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

תהליך החלטה מרקובי (באנגלית: 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 ^{t}R(s_{t},\pi (s_{t}))$ עבור $s_{t}\in S$ יהיה גבוה ככל שניתן. כדי לגבש מדיניות בחירת פעולות מתאימה תחת מודל זה, נעזרים באלגוריתמים מתחומי למידת חיזוק ובקרה אופטימלית. כמו כן קיימות גרסאות של המודל עבור מרחבי מצבים שניתנים לצפייה חלקית (Partially Observable MDP או POMDP) ועבור תהליכי החלטה לזמן רציף כשהקריטריון למיקסום הוא אינטגרל.

התהליך משמש במדעי המחשב בתחום של Reinforcement Learning לשם יצירת תוכניות הלומדות לבד לפתור מערכת ולהגיע לאופטימיזציה בתהליכים בה[1].

אלגוריתמים

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

בגישה של פתרון באמצעות תכנון דינמי מגדירים לרוב שני מערכים: אחד המגדיר את ערכי התגמול הממוצעים לכל מצב ( $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 - בגרסה זו מחשבים את המדיניות פעם אחת, ולאחר מכן מחשבים את התגמול שוב ושוב עד להתכנסות. כאשר שלב חישוב התגמול מתכנס, מחשבים מחדש את המדיניות.