ד.12 — DDQN — ההבדל מ־DQN

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

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

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

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

מי בוחר ומי מעריך?

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

בשורת DDQN, ‏argmax מחזיר את הפעולה בעלת הערך הגבוה ביותר לפי הרשת הראשית (ולא את הערך עצמו), ואת הפעולה הזאת, a*, מעבירים לרשת המטרה כדי לקבל את הערך שייכנס ליעד. בכל בחירה בוחנים רק פעולות חוקיות. במעבר סופי היעד בשתי השיטות הוא R בלבד. שתי רשתות ומאגר דגימות כבר קיימים ב־DQN; הם אינם החידוש של DDQN. השם "Double" מתייחס להפרדת התפקידים, לא למספר הרשתות.

דוגמה מספרית וקוד השינוי

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

עבור R=0 ו־γ=0.9, ‏DQN משתמש במקסימום של רשת המטרה: הערך הגבוה ביותר בעמודת המטרה הוא 0.9 (פעולה B), ולכן היעד הוא 0.9×0.9=0.81. ‏DDQN בוחר A בעזרת הראשית, כי בעמודת הראשית 0.8 גדול מ־0.6, אך מעריך אותה בעזרת המטרה: 0.9×0.4=0.36. שימו לב ששתי הרשתות חלוקות ביניהן איזו פעולה עדיפה, וזה בדיוק המצב שבו ההפרדה משנה את היעד. המספרים הומצאו להמחשת ההבדל; אין כאן ידיעה מהו הערך האמיתי או הוכחה שהיעד הנמוך תמיד נכון יותר.

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

def compute_targets(reward, done, main_values, target_values, gamma=0.9):
    if done:
        return reward, reward
    dqn_target = reward + gamma * max(target_values)
    best_index = max(range(len(main_values)), key=main_values.__getitem__)
    ddqn_target = reward + gamma * target_values[best_index]
    return dqn_target, ddqn_target

dqn, ddqn = compute_targets(0, False, [0.8, 0.6], [0.4, 0.9])
print(f'DQN: {dqn:.2f}, DDQN: {ddqn:.2f}')

פלט

DQN: 0.81, DDQN: 0.36

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

במימוש רשתות מחשבים את שני היעדים ללא גרדיאנט; רק הרשת הראשית מתעדכנת כדי להתקרב ליעד שנבחר. יתר לולאת DQN נשארת באותו מבנה: אותו מאגר, אותו סנכרון של רשת המטרה, אותו צעד אימון. במימוש איקס עיגול מהפרק הקודם, השינוי נמצא בפונקציה לחישוב ערכי ההמשך של האצווה: במקום target(states, actions).max(), הראשית תבחר פעולה חוקית, והמטרה תעריך אותה.

בכך מסתיים חלק למידת החיזוק. עברנו מתכנון עם מודל מלא של הסביבה (Policy Iteration ו־Value Iteration), דרך למידה מדגימות בטבלאות (מונטה קרלו, SARSA ו־Q-learning), ועד להחלפת הטבלה ברשת נוירונים שיודעת להכליל (DQN ו־DDQN). אותם רעיונות, עם רשתות גדולות יותר ומשחקים מורכבים יותר, עומדים בבסיס הסוכנים שלומדים לשחק במשחקי מחשב ובמשחקי לוח ברמה גבוהה.