מבוא לבינה מלאכותית - פרק 10: תהליכי החלטה מרקוביים (MDP)

יחידת לימוד 10.1 • תשתית תיאורטית ומתמטית

המסגרת הפורמלית של תהליכי החלטה מרקוביים (MDP)

מידול קבלת החלטות בסביבות סטוכסטיות, תכונת מרקוב (Markov Property), פונקציית התגמול, והתמודדות עם אופק אינסופי באמצעות פקטור היוון מהוון ($\gamma$).

👋

להבין את האינטואיציה שמאחורי הקלעים: המעבר מחיפוש עיוור לקבלת החלטות תחת אי-ודאות סטוכסטית

ברוכים הבאים לפרק 10! עד כה בקורס פגשנו שתי משפחות של בעיות: בעולם החיפוש הקלאסי (פרקים 2–4), הסביבה הייתה דטרמיניסטית לחלוטין — פקודת "סע ישר" הבטיחה הגעה מדויקת ליעד, והפתרון היה רצף פעולות קשיח. בפרקים 8–9 למדנו לכמת אי-ודאות באמצעות רשתות בייסיאניות, אך הסוכן שם היה צופה פסיבי שרק עדכן את אמונותיו. בפרק 10 מתרחשת המהפכה האמיתית: אנו מחברים בין יכולת הפעולה לבין אי-הוודאות הסטוכסטית! הסוכן פועל בעולם שבו פעולותיו עלולות להיכשל (החלקה, רוח, תקלות), ולכן פתרון הבעיה איננו מסלול פעולות חד-פעמי, אלא מדיניות כוללת ($\pi$) — ספר חוקים שלם המגדיר לסוכן מה לעשות בכל מצב ומצב בעולם, גם אם הוא נזרק למקום בלתי צפוי.

💡 אינטואיציה בגובה העיניים: נהיגה בכביש מכוסה קרח תחת רוח סערה

דמיינו שאתם נוהגים ברכב על כביש חלקלק ומכוסה קרח. אם תתכננו מראש בבית: "אסע 100 מטר ישר, אפנה 90 מעלות ימינה ואז אאיץ", תמצאו את עצמכם בתעלה כבר בפנייה הראשונה! מדוע? כי הגלגלים יחליקו והרוח תסחוף אתכם. במקום תוכנית עיוורת, נהג מיומן מחזיק בראש מדיניות (Policy): "אם אני מרגיש שהרכב סוטה ימינה — אפנה את ההגה שמאלה; אם הגלגלים ננעלים — אשחרר את הבלם". תהליך החלטה מרקובי (MDP) פועל בדיוק כך: הוא בונה לסוכן מפת תגובות אופטימלית לכל משבצת בעולם, תוך שקלול הסיכויים להחלקה והתגמולים לאורך הדרך.

📊 תרשים 10.1: האנטומיה המבנית של מעגל קבלת החלטות מרקובי (MDP Cycle)

זרימת המידע, מודל המעברים הסטוכסטי $T(s,a,s')$, פונקציית התגמול $R$ ומנגנון ההיוון $\gamma$

מודל פורמלי

🎯

1. המעבר מעולם דטרמיניסטי לעולם של אי-ודאות סטוכסטית

מדוע אלגוריתמי חיפוש קלאסיים (כמו *A) אינם מספיקים כאן?

בעולם החיפוש הקלאסי (פרקים 2–3), הנחנו עולם דטרמיניסטי: כאשר סוכן בחר לבצע את הפעולה "קדימה", הוא עבר בוודאות של $100\%$ למשבצת שמלפניו. במצב כזה, פתרון הבעיה היה פשוט סדרה קבועה של פעולות (מסלול מנקודה A לנקודה B).

אולם בעולם האמיתי (ובפרט ברובוטיקה, רכבים אוטונומיים ומערכות בקרה), הסביבה היא סטוכסטית (Stochastic): פעולות אינן מובטחות להצליח. רובוט המנסה לנסוע ישר עלול להחליק על קרח, גלגל עלול להסתבך בחול, ומשב רוח עז עלול לסטות רחפן ממסלולו. בסביבה כזו, תכנון מסלול סטטי נידון לכישלון מוחלט עם הסטייה הראשונה!

תהליכי החלטה מרקוביים (Markov Decision Processes – MDP) מספקים את המסגרת המתמטית השלמה לקבלת החלטות בסביבות שבהן:

👁️ נצפות מלאה (Fully Observable)

הסוכן תמיד יודע בוודאות מוחלטת באיזה מצב הוא נמצא ברגע נתון. אין ערפל או תצפית חסרה (בשונה מ-POMDP שיידון ביחידה 10.5).

🎲 פעולות סטוכסטיות (Non-Deterministic Actions)

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

📐

2. המבנה הפורמלי של MDP: הרביעייה $\langle S, A, P, R \rangle$

ההגדרה המתמטית המחייבת והרחבתה עם מקדם ההיוון $\gamma$

מודל MDP מוגדר באופן קנוני כרביעייה מתמטית $\langle S, A, P, R \rangle$, ולרוב כחמישייה $\langle S, A, P, R, \gamma \rangle$:

רכיב במודל	סימון מתמטי	הגדרה ומשמעות תיאורטית	תפקיד בקבלת החלטות
מרחב המצבים	$S = \{s_1, s_2, \dots, s_n\}$	קבוצה סופית (או בת-מנייה) של כל התצורות האפשריות של הסביבה שבהן הסוכן יכול להימצא.	מגדיר היכן הסוכן נמצא בכל רגע נתון.
מרחב הפעולות	$A = \{a_1, a_2, \dots, a_m\}$	ארסנל כל הפעולות הזמינות לסוכן (לעיתים תלוי מצב: $A(s)$).	ההחלטות שהסוכן יכול להפעיל כדי להשפיע על הסביבה.
מודל המעברים	$P(s' \mid s, a)$ או $M_{ij}^a$	הסתברות המעבר למצב יעד $s'$ בהינתן שהסוכן ביצע פעולה $a$ במצב $s$. סכום ההסתברויות לכל פעולה הוא בדיוק 1: $\sum_{s'} P(s' \mid s,a) = 1$.	מכמת את הדינמיקה ואי-הוודאות של הסביבה ("הפיזיקה" של העולם).
פונקציית התגמול	$R(s)$ או $R(s, a, s')$	ערך מספרי (חיובי כפרס או שלילי כקנס) הניתן לסוכן. לרוב משויך לעצם השהייה במצב: $R(s)$.	מגדיר את מטרת הסוכן: למקסם את סך התגמול המצטבר לאורך זמן.
מקדם היוון	$0 \le \gamma \le 1$	פקטור הקובע את משקלם של תגמולים עתידיים ביחס לתגמולי הווה מיידיים.	מבטיח התכנסות מתמטית של טורים אינסופיים ומכייל את סבלנות הסוכן.

🧠

3. תכונת מרקוב (Markov Property) ומשמעותה העמוקה

חוסר זיכרון היסטורי והשלכותיו על סקלביליות חישובית

בלב המודל ניצבת תכונת מרקוב. תכונה זו קובעת כי העתיד בלתי-תלוי בעבר בהינתן ההווה:

$$P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots, s_0, a_0) = P(s_{t+1} \mid s_t, a_t)$$

במילים פשוטות: ההסתברות לעבור למצב הבא $s_{t+1}$ תלויה אך ורק במצב הנוכחי שבו הסוכן נמצא ברגע זה ($s_t$) ובפעולה שהוא מבצע כעת ($a_t$). אין שום משמעות לשאלה כיצד הגיע הסוכן למצב זה, באילו מצבים ביקר קודם לכן, או כמה זמן הוא משוטט במערכת!

⚠️ מה קורה אם בעיה מהחיים האמיתיים אינה מרקובית?

אם בעיה מסוימת תלויה בהיסטוריה (למשל: מהירות הרובוט תלויה במיקומו בשני הצעדים הקודמים), ניתן להחזיר אותה למסגרת מרקובית על ידי הרחבת הגדרת המצב. במקום שהמצב יהיה רק מיקום $x$, המצב יוגדר כצמד $\langle x, v \rangle$ הכולל מיקום ומהירות. המחיר החישובי: התפוצצות ממדית של מרחב המצבים $S$.

♾️

4. אופק אינסופי וההכרח המתמטי בפקטור ההיוון ($\gamma$)

מדוע סכום פשוט קורס, וכיצד טור הנדסי מהוון מבטיח התכנסות?

כאשר סוכן פועל לאורך זמן, עליו למקסם את התגמול המצטבר. בסביבות בעלות אופק סופי קיים מצב טרמינלי (Terminal State) המסמן את סיום הריצה, וניתן לסכום את התגמולים ישירות: $U = \sum_{t=0}^T R(s_t)$.

אולם ברוב היישומים (רובוט תעשייתי, רשת חשמל או מערכת בקרה פיננסית), המערכת פועלת באופק אינסופי (Infinite Horizon). אם היינו סוכמים תגמולים רגילים, היינו מקבלים טור אינסופי שמתבדר: $$\sum_{t=0}^\infty R(s_t) = \pm \infty$$ במצב כזה, אי-אפשר להשוות מתמטית בין שתי אסטרטגיות שונות ששתיהן מניבות אינסוף!

הפתרון המתמטי האלגנטי הוא שימוש בתגמולים מהוונים (Discounted Rewards) באמצעות מקדם חיסכון $0 < \gamma < 1$:

$$U(s_0, s_1, s_2, \dots) = R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \dots = \sum_{t=0}^\infty \gamma^t R(s_t)$$

🔬 הוכחת החסימות וההתכנסות של סכום התועלות המהוון:

נניח כי התגמול המקסימלי האפשרי במערכת חסום על ידי ערך קבוע $R_{\max} < \infty$. אז עבור כל סדרת מצבים אינסופית:

$$U = \sum_{t=0}^\infty \gamma^t R(s_t) \le \sum_{t=0}^\infty \gamma^t R_{\max} = R_{\max} \sum_{t=0}^\infty \gamma^t = R_{\max} \cdot \frac{1}{1 - \gamma} = \frac{R_{\max}}{1 - \gamma}$$

מאחר ש-$0 < \gamma < 1$, הטור ההנדסי מתכנס תמיד למספר סופי קבוע! תוצאה זו מבטיחה שהתועלת של כל מצב תהיה חסומה תמיד, מה שמאפשר השוואה אלגברית חד-חד-ערכית בין כל שתי מדיניות פעולה.

סוכן קצר רואי קיצוני ($\gamma = 0$):

הסוכן מתעלם לחלוטין מכל מה שעתיד לקרות מעבר לרגע הנוכחי ($U = R(s_0)$). הוא יבחר פעולה שתיתן לו $+1$ עכשיו, אפילו אם היא מובילה אותו ישירות לבור של $-1000$ בצעד הבא!

סוכן רואה למרחקים ($\gamma \to 1$):

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

🧪

התנסות מעשית: מעבדת האקראיות של מרקוב וטווח ההיוון

חיבור החומר התיאורטי לסימולציה האינטראקטיבית

בסימולציה שלפניכם נבחן בפועל סביבת MDP בת 16 מצבים ($4 \times 4$). נבדוק כיצד הסתברויות המעבר מפעילות תנועה סטוכסטית וכיצד שינוי מקדם החיסכון $\gamma$ משנה את "טווח הראייה" של הסוכן.

איך משתמשים בסימולציה?

חצי התנועה (▲ ◀ ▼ ▶): נסו להזיז את הסוכן. שימו לב שבכל לחיצה מופיעות "חלליות רפאים" הממחישות את הפיצול ההסתברותי של $P(s' \mid s, a)$!
סליידר מדד האקראיות: כוונו ל-$100\%$ לקבלת עולם דטרמיניסטי מלא, או הורידו ל-$60\%$ לצפייה בהחלקות מרובות לצדדים.
סליידר מקדם ההיוון ($\gamma$): הורידו את $\gamma$ ל-$0.0$ וראו כיצד תאי המטרה הרחוקים מוחשכים (קוצר רואי). העלו אותו ל-$0.95$ וראו את הארת המסלול העתידי!
כפתור "סיור אוטומטי מודרך": צפו ברצף מהלכים אוטומטי המדגים את התכנסות התועלת לאורך מסלול.

יחידת לימוד 10.3 • אלגוריתמי אופטימיזציה דינמית

אלגוריתמים מרכזיים: איטרציית ערך (VI) מול איטרציית מדיניות (PI)

הוכחת העתקת הכיווץ (Contraction Mapping) בנורמת $L_\infty$, משפט נקודת השבת של בנך, סף העצירה $\epsilon \frac{1-\gamma}{\gamma}$, סיבוכיות פולינומית חזקה, ו-Modified Policy Iteration.

👋

להבין את האינטואיציה שמאחורי הקלעים: הקרב הקלאסי בין איטרציית ערך (VI) לאיטרציית מדיניות (PI)

לאחר שניסחנו את משוואות בלמן, אנו נתקלים בבעיה חישובית: בנוכחות אופרטור ה-$\max$, משוואות בלמן האופטימליות אינן ליניאריות, ולכן לא ניתן לפתור אותן באמצעות אלגברה ליניארית פשוטה. כאן נכנסים שני האלגוריתמים המרכזיים של תכנון דינמי: איטרציית ערך (Value Iteration) הפועלת על המספרים ומעדכנת את הערכים צעד אחר צעד עד שהם מתכנסים מתמטית בזכות עקרון ההעתקה המכווצת (Contraction Mapping); ואיטרציית מדיניות (Policy Iteration) הפועלת ישירות במרחב המדיניות, מעריכה מדיניות קבועה בעזרת מערכת משוואות ליניאריות, ומשפרת אותה בצעדי ענק. ביחידה זו ננתח את ההוכחות הפורמליות, תנאי העצירה והפשרות ההנדסיות ביניהם.

💡 אינטואיציה בגובה העיניים: גילוף פסל עץ מול החלפת הרכב ואסטרטגיה שלמה

דמיינו שני אמנים: הראשון (Value Iteration) מגלף פסל עץ בעדינות אין-קץ. בכל סיבוב הוא משייף מילימטר מכל צד. הוא מתקרב לפסל המושלם באופן רציף ואיטי, ולעולם אינו קופץ בבת אחת. האמן השני (Policy Iteration) הוא מאמן כדורגל: במקום להתלבט על כל מסירה, הוא מגבש מערך טקטי שלם (מדיניות). הוא בוחן את ביצועי המערך (Evaluation), מזהה את השחקן החלש, ומחליף מערך שלם (Improvement). מכיוון שיש רק מספר סופי של מערכים אפשריים ($|A|^{|S|}$) וכל מערך חדש טוב מקודמו, המאמן מגיע לאסטרטגיה המנצחת תוך 3 עד 5 משחקים בלבד!

📊 תרשים 10.3: השוואת זרימת העבודה – איטרציית ערך (VI) מול איטרציית מדיניות (PI)

התכנסות רציפה במרחב הערכים מול מחזור הערכה ושיפור במרחב המדיניות הדיסקרטי

השוואת אלגוריתמים

🌊

1. אלגוריתם איטרציית ערך (Value Iteration)

עדכון אסימפטוטי של תועלות באמצעות אופרטור בלמן

אלגוריתם איטרציית ערך (Value Iteration) הוא שיטה איטרטיבית המחשבת את ערכי התועלת האופטימליים $U^*(s)$ על ידי הפעלה חוזרת של משוואת האופטימליות של בלמן.

מהלך האלגוריתם: 1. מאתחלים את וקטור התועלות לערכים שרירותיים (לרוב אפסים: $U_0(s) = 0$ או לתגמול המיידי $U_0(s) = R(s)$).
2. בכל איטרציה $k+1$, מעדכנים את התועלת של כל מצב $s \in S$ על בסיס התועלות מהאיטרציה הקודמת:

$$U_{k+1}(s) \leftarrow R(s) + \gamma \max_{a \in A} \sum_{s'} P(s' \mid s, a) U_k(s')$$

3. התהליך מבוצע במקביל לכל המצבים עד שמתקיים תנאי עצירה מסוים.

🔬 מדוע האלגוריתם מובטח להתכנס תמיד? (העתקת כיווץ ומשפט בנך)

נגדיר את אופרטור בלמן $\mathcal{T}$ כפעולת העדכון שלעיל: $U_{k+1} = \mathcal{T}(U_k)$.
במרחב הווקטורי של התועלות המצויד בנורמת המקסימום ($L_\infty$, המודדת את הפער המקסימלי במצב הבודד שבו ההפרש הגדול ביותר): $$||U - V||_\infty = \max_{s \in S} |U(s) - V(s)|$$ הוכח מתמטית כי אופרטור בלמן מקיים את תכונת העתקת הכיווץ (Contraction Mapping):

$$||\mathcal{T}(U) - \mathcal{T}(V)||_\infty \le \gamma ||U - V||_\infty$$

משפט נקודת השבת של בנך (Banach Fixed-Point Theorem): מאחר שמרחב התועלות הוא מרחב מטרי שלם, ומאחר ש-$0 < \gamma < 1$, הפעלה חוזרת של העתקת כיווץ מתכנסת תמיד לנקודת שבת יחידה בודדת ($U^*$). התכנסות זו מובטחת לכל נקודת אתחול $U_0$ ובקצב הנדסי!

⏱️ תנאי העצירה המדויק לסף שגיאה $\epsilon$:

מאחר שההתכנסות היא אסימפטוטית, יש לקבוע מתי לעצור את האלגוריתם כך שהשגיאה ביחס לערך האמיתי $U^*$ לא תעלה על סף נתון $\epsilon$. המשפט המתמטי קובע כי אם השינוי בין שתי איטרציות עוקבות מקיים:

$$||U_{k+1} - U_k||_\infty < \epsilon \cdot \frac{1 - \gamma}{\gamma}$$

אז מובטח כי המרחק בין התועלת שחושבה $U_{k+1}$ לתועלת האופטימלית האמיתית $U^*$ קטן מ-$\epsilon$: $$||U_{k+1} - U^*||_\infty < \epsilon$$ שימו לב לפקטור $\frac{1-\gamma}{\gamma}$: כאשר $\gamma$ קרוב מאוד ל-1 (למשל 0.99), סף העצירה נהיה מחמיר וקטן ביותר, מה שדורש איטרציות רבות יותר להשגת דיוק זהה.

🎯

2. אלגוריתם איטרציית מדיניות (Policy Iteration)

חיפוש ישיר במרחב המדיניות והתכנסות בסופיות מוחלטת

בעוד ש-Value Iteration פועל במרחב התועלות הרציף (שבו התכנסות מושלמת דורשת אינסוף צעדים), אלגוריתם Policy Iteration מתמקד ישירות בחיפוש במרחב הסופי של המדיניות האפשריות ($|A|^{|S|}$).

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

שלב 1: הערכת מדיניות (Policy Evaluation)

בהינתן המדיניות הנוכחית $\pi_k$, מחשבים את ערכי התועלת המדויקים שלה $U_k$ על ידי פתרון מערכת של $|S|$ משוואות ליניאריות: $$U_k(s) = R(s) + \gamma \sum_{s'} P(s' \mid s, \pi_k(s)) U_k(s')$$ שלב זה דורש היפוך מטריצה וסיבוכיותו היא $O(|S|^3)$.

שלב 2: שיפור מדיניות (Policy Improvement)

מעדכנים את המדיניות לכל מצב על ידי ביצוע בחירה חמדנית (Greedy) לפי ה-$\arg\max$ על ערכי התועלת $U_k$ שחושבו: $$\pi_{k+1}(s) \leftarrow \operatorname{argmax}_{a \in A} \sum_{s'} P(s' \mid s, a) U_k(s')$$

תנאי העצירה והוכחת אי-מעגליות:

האלגוריתם עוצר ברגע שבו המדיניות אינה משתנה בין שתי איטרציות עוקבות: $$\pi_{k+1} = \pi_k$$ האם ייתכן שהאלגוריתם ייכנס ללולאה אינסופית? לא! על פי משפט שיפור המדיניות (Policy Improvement Theorem), בכל איטרציה התועלת המופקת מהמדיניות החדשה עדיפה מובהקת על הקודמת: $U^{\pi_{k+1}}(s) \ge U^{\pi_k}(s)$ לכל מצב $s$. מאחר שמספר המדיניות האפשריות הוא סופי ($|A|^{|S|}$) והתועלת היא מונוטונית עולה, האלגוריתם חייב לעצור בתוך מספר סופי של איטרציות (בדרך כלל 3–5 איטרציות בלבד!).

גרסה מתקדמת: Modified Policy Iteration

שלב הערכת המדיניות המדויק ($O(|S|^3)$) יקר מאוד בעולמות גדולים. ב-Modified Policy Iteration, במקום לפתור את מערכת המשוואות במדויק, מבצעים רק מספר קטן של איטרציות עוקבות של Value Iteration (למשל 10 צעדים), ואז קופצים מיד לשלב שיפור המדיניות. שיטה זו נהנית מהמהירות של PI ומהעלות הזולה של VI.

📊

3. טבלת השוואה מקיפה: Value Iteration מול Policy Iteration

הכרעת ה-Trade-offs ההנדסיים בבחירת אלגוריתם

מאפיין הנדסי	Value Iteration (VI)	Policy Iteration (PI)
מוקד העדכון המרכזי	ערכי התועלת של המצבים: $U(s)$	המדיניות עצמה: פונקציית הפעולה $\pi(s)$
עלות חישוב לאיטרציה בודדת	$O(\|S\|^2 \cdot \|A\|)$ - זולה ומהירה במיוחד	$O(\|S\|^3 + \|S\|^2 \cdot \|A\|)$ - יקרה בשל היפוך מטריצה
מספר איטרציות ממוצע להתכנסות	גבוה מאוד (עשרות עד מאות, תלוי ב-$\gamma$ וב-$\epsilon$)	נמוך מאוד (לרוב 2 עד 5 איטרציות בלבד!)
תנאי עצירה	סף שגיאה מספרי: $\|\|U_{k+1}-U_k\|\|_\infty < \epsilon \frac{1-\gamma}{\gamma}$	מדויק ומוחלט: המדיניות אינה משתנה ($\pi_{k+1} = \pi_k$)
הוכחת סיבוכיות תיאורטית	התכנסות ליניארית (הנדסית) של העתקת כיווץ	פולינומית חזקה (Strongly Polynomial - משפט Ye 2011) ל-$\gamma$ קבוע

🏁

התנסות מעשית: מרוץ האלגוריתמים (VI מול PI)

השוואה חזותית בזמן אמת של התכנסות מפת חום מול חיצי מדיניות

בסימולציה שלפניכם מוצג אותו עולם מבוך $3 \times 3$ במקביל לשני האלגוריתמים. צד שמאל מריץ Value Iteration (מפת חום), וצד ימין מריץ Policy Iteration (חיצי כיוון).

איך משתמשים בסימולציה?

כפתור "צעד איטרציה יחיד": לחצו פעם אחת לצפייה בשלב בודד בשני האלגוריתמים. שימו לב: ב-PI החצים מתיישרים ומתייצבים כבר אחרי 2–3 קליקים!
כפתור "הרץ מרוץ מלא": צפו במרוץ סימולטני. שימו לב כיצד מדד נורמת המקסימום $|| \Delta U ||$ דועך לאט ב-VI, בעוד PI מסיים בהרבה לפניו.
סליידר מקדם ההיוון ($\gamma$): בדקו כיצד הגדלת $\gamma$ מאיטה עוד יותר את התכנסות ה-VI אך כמעט ואינה משפיעה על מהירות ה-PI.

יחידת לימוד 10.4 • ניתוח תרגילים מודרך

ניתוח עומק של מקרי הבוחן ותרגילי המפתח

פתרון שלם, מודרך ומפורט של 5 תרגילי הדגל: פקמן ב-Grid 3x3, גרף 4 המצבים, סוכן הביטים, מערכת 3 המצבים והלולאות ללא היוון, ועולם ה-101 עם סף השוויון הקריטי.

👋

להבין את האינטואיציה שמאחורי הקלעים: מהלכה למעשה – עולם הרשת, מלכודות חישוב ושאלות מבחן

תיאוריה ללא תרגול מעשי היא עיוורת! במבחנים האקדמיים בנושא MDP, שאלות החישוב מתמקדות כמעט תמיד בתרחישים קונקרטיים: עולם הרשת (Gridworld) המפורסם של Russell & Norvig, מערכות מצבים דיסקרטיות עם פעולות מתחלפות (כמו סוכן הביטים Flip/Swap), ובחינת נקודות שוויון תחת פקטורי היוון משתנים ($\gamma$). ביחידה זו נפרק שלב-אחר-שלב 5 תרגילי מבחן מרכזיים, נחשב איטרציות ידניות במדויק, ונפתח את החוש ההנדסי לזיהוי מהיר של מלכודות חישוביות נפוצות (כגון התנגשות בקירות, בלבול בין ערך טרמינלי לערך מתמשך, והתנהגות תחת קנס צעד).

💡 אינטואיציה בגובה העיניים: פקמן בסמטה צרה מעל בור אש – קנס צעד כ"מס נשימה"

תארו לעצמכם את פקמן הולך בסמטה: מימינו מונח יהלום ענק ($+1$), משמאלו בור לבה רותחת ($-1$), ובכל צעד יש רוח שעלולה להעיף אותו לבור בסיכוי $20\%$. אם כל צעד עולה לו קנס קטנטן של $-0.01$ ("מס נשימה"), פקמן יעדיף ללכת לאט ובזהירות, לעקוף את הבור מרחוק ולא להסתכן. אבל מה יקרה אם נעלה את קנס הצעד ל-$-2.0$? עכשיו כל שנייה של המתנה שורפת לו את כל התקציב! פקמן ירוץ בריצת אמוק ישר קדימה ליד הבור, ואפילו יקפוץ לתהום רק כדי לסיים את המשחק ולעצור את הדימום של הקנסות. פונקציית התגמול היא השפה שבה אנו מכתיבים לסוכן את אופיו!

📊 תרשים 10.4: עולם הרשת 3x3 – הסתברויות מעבר, קירות, תגמולים ומדיניות אופטימלית

הדגמת מודל הרעש הסטוכסטי (80% ישר, 10% לכל צד), התנגשות בקיר, ומדיניות הפקמן

תרגול Gridworld

הסתברות 80% (0.8): הסוכן מצליח ונע קדימה צפונה לתא היעד. • הסתברות 10% (0.1): הסוכן מחליק 90° שמאלה (מערב). • הסתברות 10% (0.1): הסוכן מחליק 90° ימינה (מזרח). ⚠️ כלל התנגשות בקיר: אם תא היעד הוא קיר או מחוץ ללוח, הסוכן נשאר במקומו! ⚙️ השפעת קנס הצעד R(s) על אופי המדיניות (Policy Persona): 1. R(s) = -0.04 (קנס מתון): סוכן זהיר — עוקף את הבור בבטחה מסביב ומגיע ל-+1. 2. R(s) = -0.40 (קנס בינוני): סוכן נועז — לוקח סיכון של החלקה לבור כדי לקצר דרך. 3. R(s) = -2.00 (קנס חריף): סוכן אובדני — קופץ מיד לבור -1 כדי לסיים את סבל הקנסות! 4. R(s) > 0 (בונוס על כל צעד): סוכן עצלן — מסתובב לנצח במעגלים ולעולם לא יסיים. מסקנה: פונקציית התגמול אינה רק ציון, אלא המצפן המכוון את אסטרטגיית הסוכן.

🟡

תרגיל מודרך 1: בעיית פקמן ב-Grid World בגודל 3x3

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

סביבת ה-Grid מוגדרת על לוח של $3 \times 3$ (קואורדינטות $(x,y)$ כאשר $x$ עמודה ו-$y$ שורה מלמטה למעלה):

מצבים טרמינליים (סופיים): $(1,1) = +25$, $(2,1) = -100$, $(3,1) = +80$, $(3,2) = -80$, $(3,3) = +100$.
מצב התחלה של פקמן: $(1,3)$ (הפינה השמאלית העליונה).
מצבי ביניים ריקים: $(1,2)$, $(2,2)$, $(2,3)$.
מקדם היוון: $\gamma = 0.5$.

א. המקרה הדטרמיניסטי (הצלחה ב-100%):

נחשב את התועלות תחת המדיניות האופטימלית עבור המצבים $U(3,1)$, $U(1,3)$, ו-$U(2,2)$:

1. חישוב $U(3,1)$ : מאחר ש-$(3,1)$ הוא מצב טרמינלי, אין עתיד מהוון, ולכן תועלתו שווה ישירות לתגמולו המיידי: $$U(3,1) = 80$$

2. חישוב $U(1,3)$ : מפינה זו ישנם שני מסלולים מתחרים:

מסלול דרומה: תנועה DOWN אל $(1,2)$ ואז DOWN אל המטרה $(1,1) = +25$ (2 צעדים). התועלת: $\gamma^2 \times 25 = 0.5^2 \times 25 = 6.25$.
מסלול ימינה: תנועה מזרחה לעבר הפרס הגדול $+100$ ב-$(3,3)$ דרך $(2,3) \to (3,3)$ (4 צעדים בסך הכל). התועלת: $\gamma^4 \times 100 = 0.5^4 \times 100 = \frac{1}{16} \times 100 = 6.25$.

שני המסלולים מעניקים בדיוק את אותה התועלת האופטימלית, ולכן: $$U(1,3) = 6.25$$

3. חישוב $U(2,2)$ : המסלול האופטימלי מ-$(2,2)$ הוא ללכת ימינה (RIGHT) אל $(3,2)$ (שהוא בור!) ולכן אסור ללכת ימינה; הנתיב הבטוח והרווחי הוא למעלה (UP) אל $(2,3)$ ואז ימינה (RIGHT) אל $(3,3) = +100$ (2 צעדים): $$U(2,2) = 0.5^2 \times 100 = 25.0$$

ב. המקרה הסטוכסטי (0.8 הצלחה, 0.1 החלקה לכל אלכסון):

נחשב 2 איטרציות של Value Iteration (התחלה מ-0 לכל המצבים הלא-סופיים):

איטרציה 1: כל המצבים הלא-סופיים מאותחלים ב-0. המצבים הטרמינליים מקבלים את תגמולם המיידי.

איטרציה 2:

U₂(1,2) [עם פעולה DOWN]: מעבר מביא ל-(1,1)[+25] ב-0.8, מחליק ימינה ל-(2,1)[-100] ב-0.1, ומחליק שמאלה לקיר ב-0.1:

U₂(1,2) = 0.5 × [0.8 × 25 + 0.1 × (-100) + 0.1 × 0] = 0.5 × (20 - 10) = 5.00

U₂(3,2) [עם פעולה UP]: מעבר מביא ל-(3,3)[+100] ב-0.8, ומחליק ל-(2,2)[0] ב-0.1 ולבור ב-0.1:

U₂(3,2) = 0.5 × [0.8 × 100 + 0.1 × (-80) + 0.1 × 0] = 0.5 × (80 - 8) = 36.00

🔢

תרגיל מודרך 2: הרצת Value Iteration על 4 מצבים ($S_0$ עד $S_3$)

חישוב שתי איטרציות ופיתוח אנליטי של גבולות ההתכנסות

נתון גרף MDP בעל 4 מצבים עם התגמולים: $R(S_0)=1, R(S_1)=2, R(S_2)=3, R(S_3)=10$, פקטור היוון $\gamma = 0.9$. הסתברויות המעבר: $S_0 \to S_1 (0.5), S_2 (0.5)$ | $S_1 \to S_1 (0.5), S_3 (0.5)$ | $S_2 \to S_0 (1.0)$ | $S_3 \to S_3 (1.0)$ (לולאה עצמית במטרה).

איטרציה 1 (תגמול מיידי):

U₁(S₀) = 1.00

U₁(S₁) = 2.00

U₁(S₂) = 3.00

U₁(S₃) = 10.00

איטרציה 2 (עדכון בלמן):

U₂(S₀) = 1 + 0.9(0.5×2 + 0.5×3) = 3.25

U₂(S₁) = 2 + 0.9(0.5×2 + 0.5×10) = 7.40

U₂(S₂) = 3 + 0.9(1.0×1) = 3.90

U₂(S₃) = 10 + 0.9(1.0×10) = 19.00

🔬 פיתוח אנליטי מדויק של ערכי התועלת הסופיים $U^*$:

עבור מצב $S_3$: $$U^*(S_3) = 10 + 0.9 U^*(S_3) \implies 0.1 U^*(S_3) = 10 \implies U^*(S_3) = \mathbf{100.0}$$

עבור מצב $S_1$: $$U^*(S_1) = 2 + 0.9 \cdot [0.5 U^*(S_1) + 0.5 U^*(S_3)]$$ $$U^*(S_1) = 2 + 0.45 U^*(S_1) + 0.45 \times 100 = 47 + 0.45 U^*(S_1)$$ $$0.55 U^*(S_1) = 47 \implies U^*(S_1) = \frac{47}{0.55} \approx \mathbf{85.45}$$

💡 הערה פדגוגית לפתרון: ברישומים ידניים של סטודנטים נפלה לעיתים טעות חישוב ונכתב 87.45. הפתרון המתמטי האנליטי המדויק והנכון לחלוטין הוא 85.45.

🔲

תרגיל מודרך 3: בעיית MDP בלוח ביטים (Flip and Swap)

מידול מצבים דיסקרטיים של מחשב, משוואות בלמן והתייצבות במצב 11

הבעיה מוגדרת על זוג ביטים. ישנם 4 מצבים: $S = \{00, 01, 10, 11\}$.
התגמול שווה למספר ה-1-ים: $R(00)=0, R(01)=1, R(10)=1, R(11)=2$. מקדם היוון $\gamma = 0.8$.
שתי פעולות זמינות: Flip ($F$): הופכת את הביט השמאלי בהסתברות 0.9 (משאירה אותו ללא שינוי ב-0.1).
Swap ($S$): מחליפה דטרמיניסטית בין הביט הימני לשמאלי (01 הופך ל-10, 10 הופך ל-01; 00 ו-11 נשארים במקומם).

מערכת משוואות בלמן האופטימליות למודל הביטים:

U(00) = 0 + 0.8 · max[ 0.9 U(10) + 0.1 U(00), U(00) ]

U(01) = 1 + 0.8 · max[ 0.9 U(11) + 0.1 U(01), U(10) ]

U(10) = 1 + 0.8 · max[ 0.9 U(00) + 0.1 U(10), U(01) ]

U(11) = 2 + 0.8 · max[ 0.9 U(01) + 0.1 U(11), U(11) ]

תוצאות 3 איטרציות ראשונות של Value Iteration (התחלה מ-0):

איטרציה 1: U₁(00)=0, U₁(01)=1, U₁(10)=1, U₁(11)=2
איטרציה 2: U₂(00)=0.72, U₂(01)=2.52, U₂(10)=1.80, U₂(11)=3.60
איטרציה 3: U₃(00)≈1.35, U₃(01)≈3.79, U₃(10)≈3.02, U₃(11)=4.88

גבול התועלת האופטימלי במצב 11:

במצב 11, הפעולה האופטימלית היא לבצע Swap השומרת על הסוכן ב-11 בהסתברות 1.0 (בניגוד ל-Flip שמסכן ביט בהסתברות 0.9). תחת פעולה זו מתקבל טור הנדסי פשוט: $$U^*(11) = 2 + 0.8 U^*(11) \implies 0.2 U^*(11) = 2 \implies U^*(11) = \frac{2}{1 - 0.8} = \mathbf{10.0}$$

🔄

תרגיל מודרך 4: הרצת Policy Iteration ופרדוקס הלולאה ללא היוון

מערכת 3 המצבים, התכנסות בשני צעדים, ופתרון משבר המטריצה הסינגולרית

נתונה מערכת בעלת 3 מצבים $\{1, 2, 3\}$ ותגמולים: $R(1)=-1, R(2)=-2, R(3)=0$ (מצב 3 טרמינלי).
במצבים 1 ו-2 קיימות שתי פעולות: פעולה $a$: מעבירה למצב השני בהסתברות 0.8 ונשארת במקום ב-0.2.
פעולה $b$: מנסה לברוח למצב הטרמינלי 3 בהסתברות 0.1 ונשארת במקום ב-0.9.
החיפוש המקורי מבוצע ללא היוון ($\gamma = 1$).

הרצת אלגוריתם Policy Iteration (ממדיניות התחלתית $\pi_0 = \{b, b\}$):

איטרציה 1:
1. הערכת מדיניות: תחת פעולה $b$, הסוכן נשאר במקום ב-0.9 ועובר ל-3 (שערכו 0) ב-0.1: $$U_1(1) = -1 + 0.1(0) + 0.9 U_1(1) \implies 0.1 U_1(1) = -1 \implies U_1(1) = -10$$ $$U_1(2) = -2 + 0.1(0) + 0.9 U_1(2) \implies 0.1 U_1(2) = -2 \implies U_1(2) = -20$$ 2. שיפור מדיניות:
- במצב 1: פעולה $a$ נותנת $0.8(-20) + 0.2(-10) = -18$; פעולה $b$ נותנת $0.9(-10) = -9$. נבחרת $b$.
- במצב 2: פעולה $a$ נותנת $0.8(-10) + 0.2(-20) = -12$; פעולה $b$ נותנת $0.9(-20) = -18$. נבחרת $a$ (כי $-12 > -18$)!
המדיניות החדשה: $\pi_1 = \{b, a\}$.

איטרציה 2:
1. הערכת מדיניות: $$U_2(1) = -10$$ $$U_2(2) = -2 + 0.8 U_2(1) + 0.2 U_2(2) \implies 0.8 U_2(2) = -2 + 0.8(-10) = -10 \implies U_2(2) = -12.5$$ 2. שיפור מדיניות: חישוב התוחלות מאשר שוב את הבחירה $\{b, a\}$.
המדיניות לא השתנתה ($\pi_2 = \pi_1$). האלגוריתם התכנס בהצלחה תוך 2 איטרציות!

⚠️ פרדוקס הלולאה ללא היוון ($\gamma = 1$):

מה היה קורה אילו בחרנו מדיניות שבה שני המצבים בוחרים בפעולה $a$ ($\pi = \{a, a\}$)?
במקרה זה, הסוכן מסתחרר בלולאה אינסופית בין מצב 1 למצב 2, וצובר קנסות של $-1$ ו-$-2$ לנצח מבלי להגיע למצב 3 הטרמינלי. מאחר שאין פקטור היוון ($\gamma = 1$), סכום התועלות צולל ל-$\mathbf{-\infty}$.
מערכת המשוואות הליניארית הופכת למטריצה סינגולרית ללא פתרון!
הפתרון המתמטי: הכנסת פקטור היוון $\gamma = 0.5$. ההיוון מבטיח העתקת כיווץ ומייצב את מערכת המשוואות, מה שהפיק את הערכים האנליטיים המדויקים: $U(1) = -220/65$ ו-$U(2) = -170/65$.

📏

תרגיל מודרך 5: בעיית העולם בגודל 101x3 (תרגיל 17.9) וסף השוויון

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

הסוכן מתחיל במצב השמאלי המרכזי. יש לו בחירה דטרמיניסטית יחידה בתחילת הדרך: ללכת למעלה (UP) או למטה (DOWN). מכל שאר המצבים יש רק פעולה אחת: ימינה (RIGHT) לאורך 100 תאים עוקבים.

מסלול למעלה (UP): תגמול מיידי של $+50$, אך לאחריו 100 תאים של עונש קבוע $-1$.
מסלול למטה (DOWN): עונש מיידי של $-50$, אך לאחריו 100 תאים של רווח קבוע $+1$.

נוסחאות התועלת כסדרות הנדסיות סופיות:

U(UP) = 50γ - ∑_{t=2}^{101} γ^t = 50γ - γ² · (1 - γ¹⁰⁰) / (1 - γ)

U(DOWN) = -50γ + ∑_{t=2}^{101} γ^t = -50γ + γ² · (1 - γ¹⁰⁰) / (1 - γ)

נקודת השוויון הקריטית: $\gamma \approx 0.9844$

כאשר משווים את שני הביטויים: $U(\text{UP}) = U(\text{DOWN})$, מקבלים את הפתרון המספרי: $$\gamma \approx 0.9844$$

אם $\gamma < 0.9844$:
הסוכן בוחר למעלה (UP). הוא "קצר רואי" מספיק כדי להעדיף את הרווח המיידי $+50$, שכן 100 הקנסות הבאים ממותנים מאוד על ידי הדיסקאונט.

אם $\gamma > 0.9844$:
הסוכן בוחר למטה (DOWN). הוא "רואה למרחק" ומבין שהצטברות ה-$+1$ לאורך 100 צעדים תניב רווח ענק שיכסה לחלוטין על עונש ה-$-50$ הראשוני!

🎯

תרגיל מודרך 6: מערכת 4 המצבים הסטוכסטית ($A, B, C, D$) – משוואות בלמן והרצת Value Iteration

שאלת דגל ממבחני הקורס – בחירת פעולות תחת מקסימום, מקדם היוון $\gamma=0.8$, טבלת איטרציות מלאה והתכנסות אנליטית

נתונה מערכת תהליכי החלטה מרקוביים (MDP) בעלת 4 מצבים בדידים: $S = \{A, B, C, D\}$.
מקדם ההיוון הוא $\mathbf{\gamma = 0.8}$.
במערכת זו קיימים תגמולים מיידיים (Rewards) בעת קבלת החלטה או הגעה למצב: $$R(A) = 0, \quad R(B) = 10, \quad R(C) = 15, \quad R(D) = 20$$

תרשים גרף המעברים וההסתברויות של מערכת 4 המצבים:

מערכת 4 משוואות בלמן האופטימליות למודל:

מצב A (מעבר פסיבי יחיד):
$$V(A) = 0 + 0.8 \cdot \big[ 0.7 V(A) + 0.3 V(B) \big] = 0.56 V(A) + 0.24 V(B)$$

מצב B (החלטה: חזרה ל-A או המשך סטוכסטי):
$$V(B) = \max \Big\{ \underbrace{10 + 0.8 V(A)}_{\text{חזרה ל-A עם תגמול 10}}, \; \underbrace{0 + 0.8 \cdot [0.8 V(B) + 0.2 V(C)]}_{\text{המשך שהייה ב-B והתקדמות ל-C}} \Big\}$$

מצב C (החלטה: חזרה ל-A או המשך סטוכסטי):
$$V(C) = \max \Big\{ \underbrace{15 + 0.8 V(A)}_{\text{חזרה ל-A עם תגמול 15}}, \; \underbrace{0 + 0.8 \cdot [0.9 V(C) + 0.1 V(D)]}_{\text{המשך שהייה ב-C והתקדמות ל-D}} \Big\}$$

מצב D (חזרה דטרמיניסטית ל-A):
$$V(D) = 20 + 0.8 V(A)$$

טבלת מעקב צעד-אחר-צעד: הרצת Value Iteration החל מ-$V_0 = (0, 0, 0, 0)$:

איטרציה $k$	$V_k(A)$	$V_k(B)$ והחלטה	$V_k(C)$ והחלטה	$V_k(D)$	הערות ומשמעות
$k=0$ (אתחול)	0.000	0.000	0.000	0.000	אתחול כל התועלות באפס
$k=1$	0.000	10.000 (A)	15.000 (A)	20.000	התגמולים המיידיים מתגלים: ב-B עדיף $\max(10, 0)=10$, ב-C עדיף $\max(15, 0)=15$
$k=2$	2.400	10.000 (A)	15.000 (A)	20.000	$V_2(A) = 0.24 \times 10 = 2.4$. ב-B: $\max(10, 0.64(10)+0.16(15)=8.8)=10$. ב-C: $\max(15, 12.4)=15$
$k=3$	3.744	11.920 (A)	16.920 (A)	21.920	עליית $V(A)$ מקפיצה את שווי החזרה ל-A: $10+0.8(2.4)=11.92 > 8.8$. החלטה יציבה: חזרה ל-A
$k=4$	4.957	12.995 (A)	17.995 (A)	22.995	התקדמות מונוטונית יציבה לעבר נקודת השבת האופטימלית
$k \to \infty$ ($V^*$)	9.677	17.742 (A)	22.742 (A)	27.742	התכנסות אנליטית שלמה: $\pi^* = \{\text{Advance}, \text{Go to A}, \text{Go to A}, \text{Go to A}\}$

🔬 פיתוח הפתרון האנליטי המדויק (Exact Closed-Form Solution):

מכיוון שבכל האיטרציות החל מ-$k=1$ הפעולה האופטימלית ב-$B$ וב-$C$ היא חזרה ל-$A$ (גריפת הפרס המיידי), המדיניות האופטימלית היא דטרמיניסטית ואינה משתנה: $\pi^*(B) = A, \pi^*(C) = A, \pi^*(D) = A$.

תחת מדיניות זו, מערכת משוואות בלמן הופכת למערכת ליניארית פשוטה של משתנה בודד: $$V^*(B) = 10 + 0.8 V^*(A)$$ נציב במשוואה של $V^*(A)$: $$V^*(A) = 0.56 V^*(A) + 0.24 \cdot \big[ 10 + 0.8 V^*(A) \big]$$ $$V^*(A) = 0.56 V^*(A) + 2.4 + 0.192 V^*(A) = 0.752 V^*(A) + 2.4$$ $$(1 - 0.752) V^*(A) = 2.4 \implies 0.248 V^*(A) = 2.4 \implies V^*(A) = \frac{2.4}{0.248} = \frac{2400}{248} \approx \mathbf{9.677}$$

V*(A): 9.68

V*(B): 17.74

V*(C): 22.74

V*(D): 27.74

💡 בדיקת נאותות: האם היה משתלם ל-C להמשיך ל-D במקום לחזור ל-A?
תועלת המשך מ-C ל-D: $0.8 \cdot [0.9(22.742) + 0.1(27.742)] = 0.8 \cdot [20.468 + 2.774] = 0.8 \cdot 23.242 = \mathbf{18.59}$.
תועלת חזרה ל-A עם תגמול 15: $15 + 0.8(9.677) = \mathbf{22.742}$.
מאחר ש-$22.742 > 18.59$, החלטת החזרה ל-$A$ מנצחת בהפרש ניכר, והמדיניות אופטימלית באופן מוחלט!

🧪

התנסות מעשית: זירת המעבדה המפוצלת

מעבדה חיה המאפשרת לחקור אינטראקטיבית את 4 מקרי הבוחן שלמעלה

עברו בין הלשוניות השונות של הסימולציה ובחנו בפועל: את גרף עולם ה-101 ונקודת המפגש, את פקמן החומק ממלכודת הקרח, את איטרציות 4 המצבים, ואת התייצבות סוכן הביטים.

איך משתמשים בסימולציה?

בלשונית עולם ה-101: גררו את סליידר $\gamma$ וחפשו את נקודת המפגש $0.9844$. ראו כיצד תיבת ההחלטה הופכת מכחול (UP) לירוק (DOWN)!
בלשונית פקמן קרח: שנו את אחוז ההחלקה. צפו כיצד מסלול פקמן סוטה מהקיר המסוכן ברגע שההחלקה חוצה $8\%$.
בלשונית 4 המצבים: לחצו על איטרציה 1, 2 וגבול $U^*$ לצפייה בערכים האופטימליים ($85.45$ ו-$100$).

יחידת לימוד 10.6 • סיכום מאסטר וצ'יט-שיט לבחינה

צ'יט-שיט מאסטר וסיכום מקיף לבחינה: תהליכי החלטה מרקוביים (MDP)

ריכוז כל משוואות בלמן, תנאי עצירה והיוון, מטריצת השוואת אלגוריתמי פתרון (VI מול PI מול LP), ריכוז תוצאות תרגילי המפתח, 10 מלכודות בחינה קריטיות, מילון מונחים מקצועי וגשר פדגוגי לפרק 11.

📋

נוסחאות מפתח וקשרי חישוב יסודיים ב-MDP

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

Bellman Core

הגדרת MDP, תוחלת והיוון

חמישיית ה-MDP: $(S, A, T, R, \gamma)$ כאשר $S$ מרחב המצבים, $A$ הפעולות, $T(s,a,s')=P(s'|s,a)$, $R(s,a,s')$ התגמול, ו-$\gamma \in [0, 1)$ פקטור ההיוון.
סכום תגמולים מהוון: $U([s_0, s_1, \dots]) = \sum_{t=0}^\infty \gamma^t R(s_t, a_t, s_{t+1}) \le \frac{R_{\max}}{1-\gamma}$ (חסום תמיד לטור גיאומטרי).
חובת סכימת הסתברויות: לכל מצב $s$ ופעולה $a$: $\sum_{s' \in S} T(s, a, s') = 1.0$. במצב טרמינלי אין מעברים ($V(s_{term}) = R(s_{term})$).
תכונת מרקוב: $P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots) = P(s_{t+1} \mid s_t, a_t)$. העתיד בלתי-תלוי בעבר בהינתן ההווה.
אינווריאנטיות לטרנספורמציה: הכפלה בסקלר חיובי $R' = c R + d$ (כאשר $c > 0$) שומרת על אותה מדיניות אופטימלית $\pi^*$.

משוואות בלמן ואלגוריתמי פתרון

משוואת בלמן למדיניות נתונה π: $V^\pi(s) = R(s, \pi(s)) + \gamma \sum_{s'} T(s, \pi(s), s') V^\pi(s')$.
מטריציונית: $V^\pi = (I - \gamma T^\pi)^{-1} R^\pi$.
משוואת בלמן האופטימלית: $V^*(s) = \max_{a \in A} \left[ R(s,a) + \gamma \sum_{s'} T(s,a,s') V^*(s') \right]$.
קשר לערך Q: $Q^*(s, a) = R(s,a) + \gamma \sum_{s'} T(s,a,s') V^*(s')$ ומתקיים $V^*(s) = \max_a Q^*(s, a)$.
תנאי עצירה ב-Value Iteration: אם $\|V_{k+1} - V_k\|_\infty < \epsilon \frac{1-\gamma}{\gamma}$, אזי מובטח כי $\|V_{k+1} - V^*\|_\infty < \epsilon$.
עיצוב תגמולים (Reward Shaping): $F(s, a, s') = \gamma \Phi(s') - \Phi(s)$. התגמול $R' = R + F$ שומר על אותה $\pi^*$ הודות לביטול טלסקופי.

⚖️

מטריצת השוואה הנדסית של אלגוריתמי פתרון ב-MDP

שיקולי בחירה, סיבוכיות זמן וזיכרון, יתרונות ומגבלות של כל גישה

אלגוריתם	מרחב החיפוש	סיבוכיות לאיטרציה	מספר איטרציות	תנאי עצירה	מתי לבחור?
Value Iteration (VI)	וקטור ערכים רציף $\mathbb{R}^{\|S\|}$	$O(\|S\|^2 \cdot \|A\|)$	גבוה (רציף לפי $\gamma$ ו-$\epsilon$)	$\\|V_{k+1}-V_k\\|_\infty < \epsilon \frac{1-\gamma}{\gamma}$	מרחבי מצבים ענקיים ($\|S\| > 10,000$) בהם היפוך מטריצה אינו אפשרי.
Policy Iteration (PI)	מרחב מדיניות דיסקרטי $\|A\|^{\|S\|}$	$O(\|S\|^3 + \|S\|^2 \|A\|)$	קטן מאוד (3 עד 5 סיבובים)	$\pi_{k+1}(s) = \pi_k(s) \quad \forall s$	מרחבי מצבים קטנים-בינוניים ($\|S\| < 1,000$) וכאשר $\gamma$ קרוב ל-1.
Modified Policy Iteration	משלב ערכים ומדיניות	$O(m \cdot \|S\|^2 + \|S\|^2 \|A\|)$	בינוני (מתכנס מהר מ-VI)	יציבות מדיניות או שגיאת ערך	הפתרון המעשי הנפוץ ביותר בתעשייה המשלב את יתרונות שני האלגוריתמים.
Linear Programming (LP)	אופטימיזציה מוגבלת	פולינומי (Simplex/Interior Point)	פתרון במכה אחת (Solver)	הגעה לנקודת אופטימום ב-LP	כאשר יש אילוצים קשיחים (Constrained MDP) כגון בטיחות או תקציב.

🎯

ריכוז תוצאות 5 תרגילי המפתח (עוגני בדיקה עצמית לבחינה)

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

תרגיל מפתח	פרמטרים מרכזיים	ערכים סופיים ותובנה מסכמת לבחינה
1. פקמן ב-Grid 3x3	γ = 0.5, הצלחה 0.8 / החלקה 0.1	דטרמיניסטי: $U(1,3)=6.25$, $U(2,2)=25$, $U(3,1)=80$. סטוכסטי (איטרציה 2): $U_2(1,2)=5.00$, $U_2(3,2)=36.00$. התנגשות בקיר משאירה את הסוכן במקומו!
2. מודל 4 המצבים	γ = 0.9, R=[1, 2, 3, 10]	איטרציה 2: $U_2 = [3.25, 7.40, 3.90, 19.00]$. גבולות אנליטיים: $U^(S_3)=100.0$, $U^(S_1) \approx \mathbf{85.45}$ (נפתר דרך $0.55 U^*(S_1)=47$).
3. סוכן הביטים (Flip/Swap)	γ = 0.8, S={00, 01, 10, 11}	איטרציה 2: $U_2 = [0.72, 2.52, 1.80, 3.60]$. גבול אופטימלי במצב 11: $U^*(11) = \frac{2}{1-0.8} = \mathbf{10.0}$.
4. מערכת 3 המצבים ללא היוון	γ = 1, R=[-1, -2, 0]	התכנסות PI תוך 2 איטרציות למדיניות $\pi^* = \{b, a\}$. לולאה מעגלית תחת $\gamma=1$ מייצרת מטריצה סינגולרית (מתוקן ע"י $\gamma=0.5$).
5. עולם ה-101x3	100 צעדים, UP מול DOWN	נקודת שוויון קריטית ב-$\gamma \approx 0.9844$. אם $\gamma < 0.9844$: UP (הווה עדיף); אם $\gamma > 0.9844$: DOWN (עתיד עדיף).

⚠️

10 מלכודות הבחינה הקריטיות ביותר ב-MDP (צ'ק-ליסט להצלחה בטוחה)

טעויות נפוצות של סטודנטים בחישובי איטרציות, משוואות בלמן ומודלי מעבר

1. שכחת התנגשות בקיר (Bumping into walls):

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

2. שימוש שגוי ב-max בשלב Policy Evaluation:

בשלב הערכת המדיניות של Policy Iteration, המדיניות קבועה מראש ($\pi$). אסור להפעיל $\max_a$; יש להשתמש אך ורק בפעולה $a=\pi(s)$ המוגדרת באותה איטרציה!

3. בלבול בין מצב טרמינלי למצב רגיל:

מצב טרמינלי מחזיר אך ורק את התגמול המיידי שלו ($V(s_{term}) = R(s_{term})$). אין לו מעברים עתידיים ואין להוסיף עבורו איבר היוון $\gamma V(s')$.

4. טעות חישוב נפוצה: 87.45 מול 85.45:

במערכת 4 המצבים, המשוואה היא $0.55 U^*(S_1) = 47$. החלוקה $47 / 0.55$ מניבה $85.4545\dots$ בדיוק ולא $87.45$! שימו לב לדיוק האלגברי במחשבון.

5. שכחת פקטור המתיחה בתנאי העצירה של VI:

התנאי לעצירת איטרציית ערך אינו סתם $\|V_{k+1}-V_k\| < \epsilon$, אלא כולל את פקטור ההיוון: $\|V_{k+1}-V_k\|_\infty < \epsilon \frac{1-\gamma}{\gamma}$. ללא הפקטור, השגיאה האמיתית תהיה גדולה בהרבה מ-$\epsilon$!

6. מעגלים אינסופיים ללא היוון (γ = 1):

כאשר $\gamma = 1$, אם יש מעגל שבו סכום התגמולים אינו אפס, ערך המצבים מתבדר לאינסוף ומערכת המשוואות $(I - T^\pi)$ הופכת לסינגולרית ללא פתרון יחיד!

7. הוספת תגמול קבוע בסביבות בעלות אורך משתנה:

הוספת קבוע $c > 0$ לכל הצעדים מעודדת את הסוכן להאריך את המשחק ולסרב להגיע ליעד; הוספת קבוע שלילי מעודדת "התאבדות" מהירה כדי לעצור את הקנסות.

8. בלבול בין V(s) ל-Q(s, a):

$V(s)$ הוא ערך המצב (סקלאר לכל מצב). $Q(s,a)$ הוא ערך הצמד מצב-פעולה (מטריצה בגודל $|S| \times |A|$). $V$ נגזר מ-$Q$ ע"י מקסימום: $V(s) = \max_a Q(s,a)$.

9. שגיאת סימון בהחלקה סטוכסטית:

בעת פקודת "צפון", החלקה של 10% שמאלה פירושה מעבר מערבה (ולא דרומה!); החלקה של 10% ימינה פירושה מעבר מזרחה. בדקו תמיד את וקטור הכיוונים.

10. סדר פעולות ב-Reward Shaping:

הפוטנציאל מחייב צורה מדויקת של $F = \gamma \Phi(s') - \Phi(s)$. החלפת סימנים או שכחת $\gamma$ תהרוס את הביטול הטלסקופי ותעוות לחלוטין את המדיניות האופטימלית $\pi^*$!

📖

מילון מונחים מקצועי: תהליכי החלטה מרקוביים (MDP)

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

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

תכונת מרקוב (Markov Property)

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

פקטור היוון (Discount Factor - γ)

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

מדיניות סטציונרית (Stationary Policy - π)

פונקציה הממפה כל מצב לפעולה ($\pi: S \to A$) ללא תלות בזמן שחלף מתחילת התהליך.

משוואות בלמן (Bellman Equations)

קשרי שיווי-משקל רקורסיביים הקושרים את ערך המצב לתגמול המיידי ולתוחלת הערך המהוון של המצבים הבאים.

העתקה מכווצת (Contraction Mapping)

תכונה של אופרטור בלמן המקטינה את המרחק בין כל שני וקטורי ערך בפקטור $\gamma$ בנורמת המקסימום ($L_\infty$).

איטרציית ערך (Value Iteration)

אלגוריתם תכנון דינמי המעדכן את פונקציית הערך עד להתכנסות לפי חסם $\epsilon$, ורק אז גוזר את המדיניות.

איטרציית מדיניות (Policy Iteration)

אלגוריתם המתחלף בין הערכה מדויקת של מדיניות נתונה ($V^\pi$) לבין שיפור חמדני שלה, ומתכנס במספר סופי של צעדים.

עיצוב תגמולים (Reward Shaping)

הוספת פונקציית עזר $F = \gamma \Phi(s') - \Phi(s)$ המאיצה את למידת הסוכן מבלי לשנות את המדיניות האופטימלית.

POMDP

הרחבה של MDP שבה המצב אינו נצפה ישירות, והסוכן פועל במרחב אמונות רציף (Belief State) המבוסס על תצפיות רועשות.

🚀

גשר פדגוגי לפרק 11: מתכנון מבוסס מודל (Model-Based) ללמידת חיזוק (Model-Free RL)

כיצד תשתית ה-MDP שלמדנו מובילה ישירות לאלגוריתמי Q-Learning ורשתות עצביות עמוקות

בפרק 10 הנחנו הנחה משמעותית ביותר: המודל ידוע במלואו לסוכן! הסוכן החזיק בראש את טבלאות המעברים $T(s, a, s')$ ואת פונקציית התגמול $R(s,a)$, ולכן כל מה שנדרש היה לבצע חישוב פנימי (Planning) באמצעות משוואות בלמן. אולם מה קורה כאשר הסוכן מושלך לסביבה חדשה שבה חוקי הפיזיקה והתגמולים אינם ידועים לו מראש? (רובוט המהלך על אדמת מאדים, סוכן המשחק במשחק מחשב לא מוכר, או מערכת מסחר בבורסה). במצב כזה הסוכן חייב ללמוד מתוך ניסיון וטעייה (Trial & Error)! בפרק 11 ניקח את פונקציית ה-$Q(s,a)$ שלמדנו כאן, נשחרר את הצורך בטבלת $T$, ונפתח את אלגוריתמי Q-Learning ו-SARSA המהווים את היסודות של למידת חיזוק מודרנית (Reinforcement Learning) ורשתות DQN עמוקות.

המשיכו לפרק 11: למידה מונחית ועצי החלטה / למידת חיזוק ←

לפרק הבא (פרק 11: למידה מונחית ועצי החלטה) ←

המסגרת הפורמלית של תהליכי החלטה מרקוביים (MDP)

להבין את האינטואיציה שמאחורי הקלעים: המעבר מחיפוש עיוור לקבלת החלטות תחת אי-ודאות סטוכסטית

💡 אינטואיציה בגובה העיניים: נהיגה בכביש מכוסה קרח תחת רוח סערה

📊 תרשים 10.1: האנטומיה המבנית של מעגל קבלת החלטות מרקובי (MDP Cycle)

1. המעבר מעולם דטרמיניסטי לעולם של אי-ודאות סטוכסטית

2. המבנה הפורמלי של MDP: הרביעייה $\langle S, A, P, R \rangle$

3. תכונת מרקוב (Markov Property) ומשמעותה העמוקה

4. אופק אינסופי וההכרח המתמטי בפקטור ההיוון ($\gamma$)

התנסות מעשית: מעבדת האקראיות של מרקוב וטווח ההיוון

מדיניות, פונקציית תועלת ומשוואות בלמן

להבין את האינטואיציה שמאחורי הקלעים: הקסם הרקורסיבי של משוואות בלמן

💡 אינטואיציה בגובה העיניים: שמאי הנדל"ן וערך הבתים בשכונה

📊 תרשים 10.2: עץ הגיבוי של בלמן (Bellman Backup Tree) – פירוק ערכי V ו-Q

1. מהי מדיניות ($\pi$) ומדוע היא מוגדרת על כל המצבים?

2. ההבדל הקריטי: תגמול מיידי ($R$) מול פונקציית תועלת ($U$)

3. משוואות בלמן: תוחלת (Expectation) מול אופטימליות (Optimality)

4. חילוץ המדיניות האופטימלית ($\pi^*$) מתוך ערכי התועלת

התנסות מעשית: רשת המים הרקורסיבית של בלמן

אלגוריתמים מרכזיים: איטרציית ערך (VI) מול איטרציית מדיניות (PI)

להבין את האינטואיציה שמאחורי הקלעים: הקרב הקלאסי בין איטרציית ערך (VI) לאיטרציית מדיניות (PI)

💡 אינטואיציה בגובה העיניים: גילוף פסל עץ מול החלפת הרכב ואסטרטגיה שלמה

📊 תרשים 10.3: השוואת זרימת העבודה – איטרציית ערך (VI) מול איטרציית מדיניות (PI)

1. אלגוריתם איטרציית ערך (Value Iteration)

2. אלגוריתם איטרציית מדיניות (Policy Iteration)

3. טבלת השוואה מקיפה: Value Iteration מול Policy Iteration

התנסות מעשית: מרוץ האלגוריתמים (VI מול PI)

ניתוח עומק של מקרי הבוחן ותרגילי המפתח

להבין את האינטואיציה שמאחורי הקלעים: מהלכה למעשה – עולם הרשת, מלכודות חישוב ושאלות מבחן

💡 אינטואיציה בגובה העיניים: פקמן בסמטה צרה מעל בור אש – קנס צעד כ"מס נשימה"

📊 תרשים 10.4: עולם הרשת 3x3 – הסתברויות מעבר, קירות, תגמולים ומדיניות אופטימלית

תרגיל מודרך 1: בעיית פקמן ב-Grid World בגודל 3x3

תרגיל מודרך 2: הרצת Value Iteration על 4 מצבים ($S_0$ עד $S_3$)

תרגיל מודרך 3: בעיית MDP בלוח ביטים (Flip and Swap)

תרגיל מודרך 4: הרצת Policy Iteration ופרדוקס הלולאה ללא היוון

תרגיל מודרך 5: בעיית העולם בגודל 101x3 (תרגיל 17.9) וסף השוויון

תרגיל מודרך 6: מערכת 4 המצבים הסטוכסטית ($A, B, C, D$) – משוואות בלמן והרצת Value Iteration

התנסות מעשית: זירת המעבדה המפוצלת

הרחבות מתקדמות: תכנות ליניארי, POMDP ו-Reward Shaping

להבין את האינטואיציה שמאחורי הקלעים: חזית המחקר – תכנות ליניארי, תצפית חלקית (POMDP) ועיצוב תגמולים

💡 אינטואיציה בגובה העיניים: ניווט צוללת בערפל ומאלף הכלבים המעניק חטיפי ביניים

📊 תרשים 10.5: הרחבות מתקדמות – תכנות ליניארי (LP), מרחב אמונות (POMDP) ו-Reward Shaping

1. ניסוח MDP כבעיית תכנות ליניארי (Linear Programming - LP)

2. תהליכי החלטה מרקוביים עם תצפיות חלקיות (POMDP)

3. עיצוב תגמולים מבוסס פוטנציאל (Potential-Based Reward Shaping)

4. תכנון פעולות קלאסי (Classical Planning), שפת PDDL וגרפי תכנון (Planning Graphs)

התנסות מעשית: מגרש המשחקים של השייפינג ו-POMDP

צ'יט-שיט מאסטר וסיכום מקיף לבחינה: תהליכי החלטה מרקוביים (MDP)

נוסחאות מפתח וקשרי חישוב יסודיים ב-MDP

מטריצת השוואה הנדסית של אלגוריתמי פתרון ב-MDP

ריכוז תוצאות 5 תרגילי המפתח (עוגני בדיקה עצמית לבחינה)

10 מלכודות הבחינה הקריטיות ביותר ב-MDP (צ'ק-ליסט להצלחה בטוחה)

מילון מונחים מקצועי: תהליכי החלטה מרקוביים (MDP)

גשר פדגוגי לפרק 11: מתכנון מבוסס מודל (Model-Based) ללמידת חיזוק (Model-Free RL)

שאלות מנחות ותרגול יחידה