ד.6 — מונטה קרלו — למידה מהתנסות

המצגת: מונטה קרלו (עותק מקומי)

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

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

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

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

דוגמים אפיזודה מלאה

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

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

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

כדי לחשב את כל התשואות ביעילות, אפשר לעבור על האפיזודה מהסוף להתחלה. מתחילים ב־G=0, ובכל צעד מחשבים G = reward + gamma * G. כך כל תגמול עתידי מקבל את ההיוון המתאים בלי לסכום את שאר האפיזודה מחדש.

אותה פעולה, תוצאות שונות

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

נתחיל בשאלה הראשונה. ערך בסביבה אקראית מבטא תוחלת — Expected Value, כלומר ממוצע משוקלל של התוצאות האפשריות, שבו כל תוצאה נשקלת לפי ההסתברות שלה. זו ה־E שהופיעה בהגדרת V ו־Q בפרק המודל. אם פעולה נותנת בדוגמה ערך ‎−0.4 בהסתברות 0.8 וערך 0.7 בהסתברות 0.2, התוחלת היא:

אבל כאן טמונה הנקודה: את ההסתברויות 0.8 ו־0.2 איננו יודעים — הן חלק מהמודל שאין לנו. כאשר ההסתברויות אינן נתונות לנו, נלמד מדגימות חוזרות. לדוגמה, במדגם של 100 ניסיונות ייתכן שנקבל 80 תוצאות מן הסוג הראשון ו־20 מן הסוג השני. הממוצע שלהן יהיה ‎−0.18 — אותה תוחלת, שהתקבלה בלי לדעת את ההסתברויות. מדגם אחר עשוי לתת יחס מעט שונה; זו הסיבה שאין להסתמך על משחק יחיד. ככל שנשחק יותר, הממוצע יתקרב לתוחלת האמיתית.

ממוצע שמתעדכן אחרי כל דגימה

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

אם הממוצע של שלוש דגימות הוא 0.2, והדגימה הרביעית נותנת 1, נקבל 0.2+(1−0.2)/4=0.4. הנוסחה מזיזה את הממוצע לכיוון התוצאה החדשה במידה התלויה במספר הדגימות שכבר נאספו.

אפשר להחליף את ‎1/n במקדם קבוע, מקדם הלמידה — α (אלפא), ולא להחזיק מונה לכל מצב. זהו אותו רעיון של קצב הלמידה שהכרנו ב־Gradient Descent בחלק ג — מספר קטן שקובע את גודל הצעד לכיוון המידע החדש:

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

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

Q-Table — בוחרים פעולה גם בלי מודל

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

לכן נשמור את התשואה המשוערת עבור זוג של מצב ופעולה, בטבלה שנקראת Q-Table. לכל פעולה חוקית במצב הנוכחי נוכל לקרוא ערך ישירות מהטבלה, בלי לשאול "לאן הפעולה תוביל". בקוד תהיה זו פשוט מילון שהמפתח שלו הוא הזוג (מצב, פעולה). ההגדרה של ערך מצב–פעולה נמצאת ב־פרק המודל; כעת אנחנו לומדים אותו מתוך דגימות.

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

אין להוסיף כאן שוב את התגמול המיידי: הוא כבר נכלל בתשואה שעל פיה Q נלמד. הבחירה מוגבלת לפעולות חוקיות; תא שכבר תפוס באיקס עיגול אינו מועמד.

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

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

חקירה וניצול

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

זה המתח בין Exploration — חקירה, לבין Exploitation — ניצול הידע הקיים. הוא מוכר גם מחוץ למשחקים: מי שתמיד מזמין במסעדה את המנה שהוא כבר אוהב לא יגלה לעולם מנה טובה יותר, ומי שתמיד מנסה משהו חדש לא נהנה ממה שכבר יודע שטוב. פתרון פשוט הוא ε-greedy (אפסילון־חמדני): בהסתברות ε (אפסילון, מספר קטן בין 0 ל־1) בוחרים פעולה חוקית אקראית, וביתר המקרים בוחרים פעולה בעלת Q מרבי.

import random

def choose_action(state, actions, Q, epsilon):
    if random.random() < epsilon:
        return random.choice(actions)
    return max(actions, key=lambda a: Q.get((state, a), 0.0))

random.random() מגרילה מספר בין 0 ל־1, ולכן התנאי מתקיים בהסתברות ε. Q.get מחזירה 0 אם עדיין אין בטבלה ערך לזוג הזה, וכך אין צורך למלא את הטבלה מראש. אם ε=0.1, ב־10% מהבחירות בממוצע תתבצע הגרלה. גם בהגרלה אפשר לבחור במקרה את הפעולה בעלת הערך המרבי.

מקטינים את החקירה במהלך האימון

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

import math

def epsilon_at(epoch, start=1.0, final=0.01, decay=100000):
    return final + (start - final) * math.exp(-epoch / decay)

הפרמטר epoch הוא כאן מספר האפיזודה (המשחק) הנוכחית. באפיזודה 0 נקבל ε=1, כלומר משחק אקראי לחלוטין. אחרי 100,000 אפיזודות נקבל בערך 0.374, ואחרי 200,000 בערך 0.144. decay קובע את קצב הירידה; הוא אינו מספר האפיזודה שבה נגיע בדיוק ל־final. הערך מתקרב בהדרגה ל־0.01.

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

יש לנו עכשיו את כל החלקים: חישוב תשואה מהסוף להתחלה, עדכון ממוצע עם α, טבלת Q ובחירה ב־ε-greedy. נחבר את בחירת הפעולות, איסוף האפיזודה ועדכון הערכים לתהליך אימון אחד, לפי סדר ביצועם:

Initialize Q and choose alpha, gamma
For each episode:
    Compute epsilon for this episode
    Play until termination using epsilon-greedy
    Store each (state, action, reward)
    G = 0
    For each stored step, from last to first:
        G = reward + gamma * G
        Q(state, action) += alpha * (G - Q(state, action))

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

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