08-Temporal Difference | למידת מכונה ולמידת חיזוק

ד.8 — Temporal Difference

שיטות במשפחת TD: SARSA ו־Q-learning

המצגת: Temporal Difference (עותק מקומי)

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

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

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

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

עדכון בלי להמתין לסוף האפיזודה

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

אחרי מעבר מ־S למצב S′ קיבלנו תגמול R. התגמולים הרחוקים עדיין אינם ידועים, אבל כבר יש לנו הערכה V(S′). לכן נבנה יעד המשלב מידע שנמדד עכשיו עם הערכה לעתיד:

target = R + γV(S′)
V(S) ← V(S) + α[target − V(S)]

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

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

לדוגמה, אם R=0, ‏γ=0.9 ו־V(S′)=0.8, היעד הוא 0.72. אם הערך הישן של S הוא 0.5 ו־α=0.1, נקבל ערך חדש 0.522. אפשר לבצע את העדכון מיד, גם אם המשחק נמשך עוד צעדים רבים. נשים לב שהערך זז רק מ־0.5 ל־0.522, אף שהיעד היה 0.72: זהו עדכון הדרגתי, ורק אחרי דגימות רבות הערך מתקרב ליעד.

TD Error ו־Bootstrapping

כדאי לתת שם לגודל שמניע את העדכון. הפער בין היעד לבין הערך הנוכחי נקרא שגיאת TD — TD Error, ומסמנים אותו באות היוונית δ (דלתא):

δ = R + γV(S′) − V(S)

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

מטבלת V לטבלת Q ולדגימת הסביבה

עד כאן דיברנו על ערכי מצבים. אבל כדי שהסוכן יבחר פעולה לפי V(S′) הוא צריך לדעת לאיזה מצב תוביל כל פעולה, כלומר מודל של הסביבה, ואת המודל הזה אין לנו. לכן, כדי לבחור פעולות ללא מודל נשתמש ב־Q, מהסיבה שהוסברה ב־מונטה קרלו: Q(S,A) אומר ישירות כמה שווה לבצע את הפעולה A במצב S, והסוכן בוחר את הפעולה בעלת הערך הגבוה. ביעד של TD מופיע כעת ערך Q של המצב הבא, אבל למצב הבא יש כמה פעולות אפשריות, ולכל אחת ערך Q משלה. צריך להחליט איזה מהם ייכנס ליעד. השאלה הזאת מובילה לשני האלגוריתמים הבאים.

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

SARSA — לומדים לפי הפעולה שנבחרה להמשך

האפשרות הראשונה היא הישירה ביותר: להשתמש בערך של הפעולה שהסוכן באמת עומד לבצע במצב הבא. השם SARSA מציין את חמשת הרכיבים של הדגימה: S, A, R, S′, A′. מתחילים במצב S, מבצעים A ומקבלים R ו־S′. אם המשחק נמשך, בוחרים גם את A′ לפי אותה מדיניות ε-greedy שבה הסוכן משתמש במשחק. ערך הפעולה הזאת יהיה חלק מהיעד:

Q(S,A) ← Q(S,A) + α[R + γQ(S′,A′) − Q(S,A)]

אחרי העדכון ממשיכים מ־S′ ומבצעים את אותה A′ שכבר נבחרה. אין להגריל מחדש פעולה מיד לאחר שהשתמשנו בה ביעד. בכך נשמר הקשר בין הפעולה שעל פיה עודכן הערך לבין המדיניות שמבוצעת בפועל.

הפסאודו־קוד מדגיש את הסדר:

Initialize Q
For each episode:
    Initialize S
    Choose A using epsilon-greedy
    Repeat:
        Perform A and observe R, S'
        If S' is terminal:
            target = R
        Else:
            Choose A' using epsilon-greedy
            target = R + gamma * Q(S', A')
        Q(S, A) += alpha * (target - Q(S, A))
        If S' is terminal: stop this episode
        S = S'
        A = A'

SARSA נקרא on-policy: הוא לומד את ערכי המדיניות שמייצרת את הפעולות, כולל בחירות החקירה שלה. במילים אחרות, ערכי Q שהוא מאמד עונים על השאלה "כמה שווה המצב הזה לסוכן שממשיך לחקור לפעמים באקראי", ולא לסוכן מושלם. בסיום לא בוחרים A′, כי אין פעולה נוספת; מעדכנים לפי התגמול האחרון בלבד.

Q-learning — לומדים לפי הערך המרבי להמשך

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

Q(S,A) ← Q(S,A) + α[R + γ max_{a′∈A(S′)} Q(S′,a′) − Q(S,A)]

זהו אלגוריתם off-policy: הדגימות יכולות להגיע ממדיניות חוקרת, בעוד היעד משתמש בבחירה חמדנית. כלומר, הסוכן משחק במדיניות אחת (עם חקירה) ולומד את ערכיה של מדיניות אחרת (החמדנית, ללא חקירה). התכונה הזאת היא שתאפשר בהמשך ללמוד גם מדגימות ישנות שנשמרו בזיכרון, ונחזור אליה בפרק על DQN. גם כאן, במצב סופי היעד הוא R בלבד.

Initialize Q
For each episode:
    Initialize S
    Repeat:
        Choose A using epsilon-greedy
        Perform A and observe R, S'
        If S' is terminal:
            target = R
        Else:
            target = R + gamma * max Q(S', legal action)
        Q(S, A) += alpha * (target - Q(S, A))
        S = S'
    Until S is terminal

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

ההבדל בין שני מסלולי העדכון

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

שלב	SARSA	Q-learning
בחירת הפעולה שמתבצעת	ε-greedy	ε-greedy
מידע שמתקבל מהסביבה	R ו־S′	R ו־S′
ההמשך שביעד	Q של A′ שנבחרה ב־ε-greedy	Q המרבי בין הפעולות החוקיות
הצעד הבא	מבצעים את A′ שכבר נבחרה	בוחרים פעולה מחדש באמצעות ε-greedy

נניח שבמצב הבא יש שתי פעולות בעלות ערכים 0.8 ו־0.2, והחקירה בחרה בפעולה השנייה. עבור R=0 ו־γ=0.9, יעד SARSA יהיה 0.18 (כי 0.9·0.2) ואילו יעד Q-learning יהיה 0.72 (כי 0.9·0.8). ההפרש נובע מבחירת ההמשך ביעד, אף שהמעבר שנדגם זהה. SARSA "מעניש" את המצב הנוכחי על כך שהחקירה עלולה לבחור בו פעולה גרועה; Q-learning מתעלם מהחקירה ומניח שבהמשך ייבחר הטוב ביותר.

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

n-step TD — כמה צעדים לפני האומדן

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

G_t⁽ⁿ⁾ = R_t + γR_t+1 + … + γⁿ⁻¹R_t+n−1 + γⁿV(S_t+n)

למשל, ב־2-step נשתמש בשני תגמולים ואז בערך המצב שאליו הגענו: R_t+γR_t+1+γ²V(S_t+2). את V(S_t) נעדכן לכיוון היעד הזה בעזרת α, באותו מבנה של עדכון הדרגתי.

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

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