ד.10 — למידת חיזוק עמוקה

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

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

טבלת Q התאימה לאיקס עיגול, שבו מספר המצבים קטן. במשחק גדול יותר מספר זוגות המצב–פעולה עלול להיות עצום, ובסביבה עם מדידות רציפות אי אפשר לשמור רשומה נפרדת לכל מצב אפשרי. Deep Q-Network — DQN משתמש ברשת נוירונים כדי לאמוד ערכי Q. במקום לשמור כל ערך בתא נפרד, נלמד פונקציה שמחשבת אותו.

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

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

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

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

הקשר ללמידה מפוקחת

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

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

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

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

יעד האימון ופונקציית הטעות

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

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

התחזית Q(S,A;w) מתייחסת לפעולה שנדגמה. היעד y משלב את התגמול ואת ההמשך החמדני במצב הבא. בזמן צעד האימון נתייחס ליעד כקבוע ולא נעביר דרכו גרדיאנט. הגרדיאנט יחושב דרך התחזית שאנחנו מנסים לקרב אליו. אם לא נעשה זאת, ה־backpropagation "ימשוך" גם את היעד לכיוון התחזית, במקום להזיז רק את התחזית לכיוון היעד.

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

האלגוריתם הראשוני ומצב סופי

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

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

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

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

Replay Buffer — לומדים ממאגר מעברים

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

הפתרון הוא לא לזרוק את המעברים אחרי שימוש יחיד. נשמור מעברים במאגר בשם Replay Buffer. כל רשומה מכילה (state, action, reward, next_state, done). לאחר איסוף מעברים נדגום מהם אצווה אקראית ונאמן עליה את הרשת. כאן נכנס לתמונה היתרון של Q-learning כאלגוריתם off-policy: המעברים במאגר נאספו כשהרשת הייתה במצב אחר, ואולי גם עם ε אחר, ובכל זאת מותר ללמוד מהם, כי היעד משתמש בפעולה הטובה ביותר במצב הבא ולא בפעולה שנבחרה אז בפועל.

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

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

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

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

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

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

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

ההבדל היחיד מהנוסחה הקודמת הוא ה־w⁻ במקום w: ערכי ההמשך מגיעים מרשת המטרה. ב־DQN רגיל רשת המטרה גם קובעת איזו פעולת המשך היא הטובה ביותר וגם נותנת את הערך שלה. בחירת פעולת ההתנסות במשחק ממשיכה להיעשות ברשת הראשית עם ε-greedy. לעובדה שרשת אחת גם בוחרת וגם מעריכה נחזור בפרק על DDQN.

DQN — מחברים את הרכיבים

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

Initialize main network Q
Copy its weights to target network
Create a replay buffer
For each episode:
    Initialize the game state
    Until termination:
        Choose a legal action using main Q and epsilon-greedy
        Observe next_state, reward, done
        Store the transition in the replay buffer
        If enough transitions exist:
            Sample a random batch
            Compute predictions using main Q
            Compute targets using target Q, without gradients
            Compute MSE and update main Q
        Advance the live game to next_state
    Every C completed episodes: copy main weights to target

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

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