ד.3 — מודל סביבה–סוכן ו־MDP

המצגות: מודל סביבה–סוכן (עותק מקומי) · מבוא ללמידת חיזוק (עותק מקומי)

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

כדי שתוכנה תלמד לשחק, לא מספיק שיהיה על המסך לוח יפה. היא צריכה לקבל תיאור של המצב, לבחור פעולה ולדעת מה השתנה בעקבותיה. לכן נבנה את המשחק לפי מודל סביבה–סוכן: מבנה המפריד בין העולם שבו משחקים לבין מי שבוחר את המהלכים. בהמשך נחליף סוכן אקראי בסוכן לומד, תוך שימוש באותם חוקי משחק ובאותו ממשק.

הפרק בנוי בשני רבדים. תחילה נגדיר את המושגים מצד התוכנה — סביבה, סוכן, מצב, פעולה והממשק ביניהם — כפי שנממש אותם ב־Pygame. אחר כך נעבור לרובד המתמטי: נראה שאותם מושגים בדיוק מרכיבים מודל שנקרא MDP, ונוסיף לו את המושגים שכל שאר הפרקים בחלק ד יישענו עליהם — תשואה, מדיניות, ערך של מצב וערך של פעולה. כדי שהמושגים לא יישארו מופשטים, נמחיש כל אחד מהם על לוח קטן של 4×4 משבצות.

הסביבה, המצב, הסוכן והפעולה

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

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

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

הממשק שהסוכן צריך

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

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

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

מן המשחק אל MDP

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

הסימן התחתון מציין את הזמן: s_t הוא המצב בצעד t, ו־a_t הפעולה שנבחרה בו. כאן נסמן את התגמול שמתקבל אחרי הפעולה בזמן t באמצעות r_t. רצף הצעדים ממשיך עד למצב סופי, אם קיים כזה במשימה. רצף שלם כזה — מהמצב ההתחלתי ועד הסיום — נקרא אפיזודה — Episode; משחק אחד של איקס־עיגול הוא אפיזודה אחת.

תגמול: המשוב מן הסביבה

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

באופן כללי התגמול עשוי להיות תלוי במצב, בפעולה ובמצב החדש:

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

מטרה ומדיניות

עכשיו, כשיש לנו תגמולים, אפשר לשאול מה בדיוק הסוכן מנסה להשיג. מטרת הסוכן היא להשיג תגמול מצטבר גבוה לאורך זמן, ולא רק ברגע הבא. פעולה שנותנת מעט עכשיו עשויה לפתוח דרך לניצחון בהמשך — כמו הקרבת כלי בשחמט כדי לזכות במט כמה מהלכים אחר כך; לכן אין די בבחירת התגמול המיידי הגדול ביותר. כדי לדבר על "סך התגמולים מכאן והלאה" נצטרך מושג משלו. אם משחק מסתיים בזמן T, נגדיר תחילה את התשואה — Return מן הזמן t כסכום התגמולים שיגיעו אחריו:

התשואה מודדת עד כמה הצליח משחק אחד. אבל מה שאנחנו רוצים לשפר אינו משחק בודד אלא דרך ההחלטה של הסוכן. מדיניות — Policy היא הדרך שבה הסוכן בוחר פעולה בכל מצב — למעשה "הכלל" או "הפונקציה" שמקבלת מצב ומחזירה פעולה. נסמן מדיניות באות π. במדיניות דטרמיניסטית הפעולה נקבעת ישירות מן המצב:

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

תכונת מרקוב

המדיניות שהגדרנו מסתכלת רק על המצב הנוכחי: a = π(s). זה מעלה שאלה — האם מותר לנו להתעלם מכל מה שקרה קודם? התשובה תלויה בשאלה כמה מידע המצב מכיל. כדי לבחור את ההמשך על סמך המצב הנוכחי, המצב צריך לכלול את המידע הדרוש לתיאור המעבר הבא. כאשר המצב מספיק לשם כך, אין צורך לדעת באיזה מסלול הגענו אליו. זו תכונת מרקוב: התפלגות המצב הבא והתגמול, בהינתן המצב הנוכחי והפעולה, אינה דורשת את ההיסטוריה הקודמת.

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

מדיניות מיטבית

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

Grid World: רואים מדיניות על לוח

איקס־עיגול הוא משחק קטן, אבל יש בו אלפי מצבים אפשריים — קשה לצייר אותם על דף. לכן נמחיש את המושגים על משחק פשוט עוד יותר, שכל מצביו נראים בבת אחת: Grid World, לוח משבצות שהסוכן נע בו. נשתמש בלוח 4×4. המצב הוא מיקום הסוכן, והפעולות הן למעלה, למטה, שמאלה וימינה. מתחילים בפינה השמאלית העליונה. כניסה ליעד הירוק נותנת 1, וכניסה לתא האדום נותנת ‎−1; שני המצבים האלה מסיימים את המשחק. בשאר המעברים התגמול 0. שורות ועמודות בקוד נספרות מאפס.

התחלה	0	0	0
0	0	−1	0
0	0	0	0
0	0	0	+1

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

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

V: ערך של מצב

ראינו שתי מדיניות על אותו לוח, ואחת נראית טובה מהאחרת. כדי להשוות מדיניות — ובהמשך כדי לשפר אותה — נצטרך דרך למדוד במספר עד כמה טוב להיות במצב מסוים. פונקציית ערך המצב — State Value, המסומנת V, שואלת: אם נתחיל במצב s ונמשיך לפי מדיניות π, מהי התשואה שנקבל? בסביבה דטרמיניסטית ובמדיניות קבועה אפשר לעקוב אחרי המסלול ולסכום את התגמולים. כאשר קיימת אקראיות, הערך הוא התשואה הצפויה — ממוצע על ההמשכים האפשריים.

במדיניות ״למעלה״ שתוארה, המצב שמתחת לתא האדום מוביל מיד להפסד, ולכן ערכו ‎−1. שני התאים הצמודים ליעד שהוגדרו כחריגים מובילים לניצחון, ולכן ערכם 1. תא סופי מקבל ערך 0: התגמול כבר התקבל בכניסה אליו, וממנו לא נותרו תגמולים עתידיים. כל שאר התאים מקבלים אף הם 0, אך מסיבה אחרת: המדיניות ״למעלה״ מובילה מהם אל השורה העליונה ושם הסוכן נתקע ואינו מגיע לעולם לא ליעד ולא לתא האדום, כך שסכום התגמולים בדרך הוא 0.

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

0	0	0	0
0	0	0	0
0	0	−1	1
0	0	1	0

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

Q: ערך של מצב ופעולה

V אומרת לנו כמה טוב מצב, אבל כשהסוכן עומד במצב ומתלבט, השאלה המעשית שלו היא אחרת: איזו פעולה לבחור עכשיו? כדי להשוות בין פעולות באותו מצב, נגדיר ערך מצב–פעולה — Action Value, Q. הפעם קובעים גם את הפעולה הראשונה: מתחילים ב־s, מבצעים a, ורק לאחר מכן ממשיכים לפי π.

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

γ: משקל התגמולים העתידיים

בהגדרת התשואה שנתנו, כל התגמולים נספרים באותו משקל: ניצחון בעוד צעד אחד וניצחון בעוד מאה צעדים שווים אותו דבר. אם שני מסלולים נותנים אותו תגמול, אך אחד מגיע אליו מהר יותר, נרצה לעיתים להעדיף אותו. גם בחיים "שקל היום שווה יותר משקל בעוד שנה". לשם כך נוסיף מקדם היוון — Discount Factor, γ (גמא), מספר בין 0 ל־1 המקטין את משקלם של תגמולים רחוקים:

כאשר γ=0 מתחשבים רק בתגמול המיידי. כש־γ קרוב ל־1, גם העתיד מקבל משקל רב. בדוגמה נבחר γ=0.9: תגמול 1 שמתקבל בצעד הקרוב שווה 1; אם לפניו יש צעד אחד עם תגמול 0, ערכו 0.9; ואם יש שניים, ערכו 0.81.

במדיניות שמביאה מכל מצב שאינו סופי ליעד בדרך קצרה, מתקבלת הטבלה הבאה. המספרים מעוגלים לשלוש ספרות אחרי הנקודה. שימו לב שהערך הולך וקטן ככל שמתרחקים מהיעד: כל צעד נוסף בדרך מכפיל את הערך ב־0.9. כך ההיוון נותן לנו בחינם מידע על המרחק — מצב "קרוב לניצחון" מקבל ערך גבוה יותר ממצב רחוק, גם כששניהם מובילים בסופו של דבר לאותו תגמול:

0.590	0.656	0.729	0.810
0.656	0.729	0	0.900
0.729	0.810	0.900	1
0.810	0.900	1	0

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

מודל ידוע ומודל לא ידוע

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

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

סביבה דטרמיניסטית וסביבה אקראית

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

ההבחנה הזאת מסדרת את הפרקים הבאים. נתחיל בתכנון בסביבה דטרמיניסטית שהמודל שלה ידוע: בפרקים ד.4 ו־ד.5 נראה איך, כשחוקי המשחק ידועים במלואם, אפשר לחשב את ערכי V ואת המדיניות המיטבית ישירות, בלי לשחק אפילו משחק אחד. בהמשך, החל מפרק ד.6, נלמד מתוך דגימות גם כאשר אי אפשר לחשב מראש את התגובה של הסביבה — הסוכן ישחק, יצבור ניסיון וילמד ממנו.

לצפייה במבנה משחק מוכן לפי המודל אפשר לעיין ב־GridWorld וב־חומרי הקורס. בהדגמות הספר נשתמש בלוח 4×4 שתואר כאן, ובסוף פרק ד.4 נראה את הסוכן פותר מבוך 5×5 מתוך אותו פרויקט.