DQN (רשת Q עמוקה)

מהרשימה הקבועה לרשת שלומדת בעצמה

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

2013: הניסוי הראשון, שבעה משחקי אטארי

ב-19 בדצמבר 2013 פרסמו חוקרי ⁦DeepMind Technologies⁩ — ⁦Volodymyr Mnih⁩ ועוד שישה חוקרים — מאמר בשם ⁦Playing Atari with Deep Reinforcement Learning⁩. הם בחנו את השיטה על שבעה משחקי ⁦Atari 2600⁩ בלבד: ⁦Beam Rider⁩, ⁦Breakout⁩, ⁦Enduro⁩, ⁦Pong⁩, ⁦Q*bert⁩, ⁦Seaquest⁩ ו-⁦Space Invaders⁩. התמונה הגולמית עברה עיבוד: הומרה לגווני-אפור, הוקטנה, ונחתך ממנה אזור המשחק בגודל 84 על 84 פיקסלים; ארבעת הפריימים האחרונים הוערמו יחד כקלט אחד, כדי שהרשת תוכל להסיק גם כיוון-תנועה. הרשת עצמה כללה שתי שכבות קונבולוציה ושכבה מחוברת-במלואה אחת, ופלט הערכה לכל פעולה חוקית במשחק (בין ארבע ל-18 פעולות, לפי המשחק). לפי המאמר, השיטה עקפה את כל הגישות הקודמות בשישה מתוך שבעת המשחקים, ועלתה על שחקן אנושי מקצועי בשלושה מהם: ⁦Breakout⁩, ⁦Enduro⁩ ו-⁦Pong⁩.

הזיכרון שמונע משכחה: experience replay

חידוש מרכזי של ⁦DQN⁩ הוא "זיכרון-חזרות" (⁦experience replay⁩): במקום ללמוד מכל צעד ואז לשכוח אותו, הרשת שומרת מאגר של עד מיליון צעדים אחרונים (מצב, פעולה, תגמול ומצב-הבא), ובכל סבב-אימון היא דוגמת ממנו קבוצה אקראית. למאגר הזה שלושה יתרונות, לפי המאמר המקורי: הוא מאפשר להשתמש בכל צעד כמה פעמים בעדכוני-משקל שונים, הוא שובר את הקשר החזק בין צעדים עקביים ברצף (קשר שמגדיל את השונות של עדכוני-האימון), והוא מחליק את ההתפלגות של הנתונים, מה שמסייע למנוע תנודות והתבדרות באימון. בגרסה הזו מ-2013 עדיין לא הייתה "רשת-מטרה" נפרדת — תוספת שהגיעה רק בגרסה המאוחרת יותר.

2015: Nature, 49 משחקים ורשת-המטרה

ב-25 בפברואר 2015 (בגיליון של 26 בפברואר) התפרסם בכתב-העת ⁦Nature⁩ מאמר המשך, ⁦Human-level control through deep reinforcement learning⁩, של קבוצה רחבה יותר של חוקרים ב-⁦Google DeepMind⁩ בלונדון, ובראשם שוב ⁦Volodymyr Mnih⁩. הגרסה הזו הוסיפה רכיב-יציבות חדש: "רשת-מטרה" (⁦target network⁩), עותק נפרד של הרשת שמתעדכן רק אחת לכמה זמן, כדי שההערכה שאליה הרשת מתכנסת לא תרדוף אחרי עצמה כל צעד. הפעם המערכת נבחנה על 49 משחקי ⁦Atari⁩, לא שבעה, עם אותו אלגוריתם, אותה ארכיטקטורה ואותם היפר-פרמטרים בכל המשחקים — בלי שום התאמה-ידנית למשחק הבודד. גם הרשת עצמה גדלה: במקום שתי שכבות-קונבולוציה ושכבה מחוברת-במלואה אחת כמו ב-2013, לגרסת ⁦Nature⁩ היו שלוש שכבות-קונבולוציה (32, 64 ו-64 מסננים) ושכבה מחוברת-במלואה אחת עם 512 יחידות. לפי המאמר, ⁦DQN⁩ עקף שיטות-למידת-מכונה קודמות ב-43 מתוך 49 המשחקים, והגיע ליותר מ-75% מהניקוד של בוחן-משחקים אנושי מקצועי ביותר ממחצית מהם — 29 מתוך 49. הציון המנורמל חושב כ-100 כפול ((ניקוד ⁦DQN⁩ מינוס ניקוד משחק-אקראי) חלקי (ניקוד השחקן האנושי מינוס ניקוד משחק-אקראי)), כך ש-0% מייצג משחק אקראי ו-100% מייצג את רמת הבוחן האנושי. גם לגרסה הזו היה פגם ידוע: ⁦Q-learning⁩ נוטה להעריך ביתר את ערכי הפעולות, כי אותה רשת גם בוחרת את הפעולה הטובה ביותר וגם מעריכה את ערכה. ב-2015 פרסמו ⁦van Hasselt⁩,‏ ⁦Guez⁩ ו-⁦Silver⁩ שיפור בשם ⁦Double DQN⁩, שמפריד בין שתי המשימות האלה ומקטין את ההטיה.

איפה DQN נכשל: משחקים שדורשים תכנון ארוך-טווח

לא כל המשחקים הצליחו באותה מידה. לפי סיקור שפורסם בשבוע הפרסום של מאמר ה-⁦Nature⁩, ⁦DQN⁩ "התקשה במשחקים כמו ⁦Montezuma's Revenge⁩, שדורשים אסטרטגיית-תכנון לטווח-ארוך" — משחק שבו התגמול מגיע רק אחרי רצף ארוך של פעולות נכונות, ולא אחרי כל צעד בנפרד. השיטה שהצליחה היטב במשחקים עם תגמול תכוף וברור, כמו ⁦Breakout⁩ ו-⁦Video Pinball⁩, נתקלה בקושי כשהתגמול דליל ומרוחק. המגבלה הזו — יעילות נמוכה כשצריך לתכנן קדימה בלי משוב תכוף — נשארה אתגר מרכזי בלמידת חיזוק הרבה אחרי ⁦DQN⁩.

ההשפעה: מאטארי ל-AlphaGo ומעבר

⁦DQN⁩ היה ההדגמה הראשונה שרשת עצבית אחת, בלי שום ידע מוקדם על חוקי המשחק, יכולה ללמוד לשחק משחקים שונים לגמרי זה מזה ישירות מהפיקסלים על המסך. העבודה הזו נעשתה ב-⁦DeepMind⁩ עוד לפני ש-⁦AlphaGo⁩ הפך את החברה לשם מוכר בכל העולם, ב-2016. השיטות ששימשו את ⁦DQN⁩ — רשת עצבית קונבולוציונית שמחליפה טבלה, וזיכרון-חזרות שמייצב את האימון — הפכו לאבני-בניין סטנדרטיות בהמשך פיתוח למידת חיזוק עמוקה, ושינויים עליהן, כמו ⁦Double DQN⁩, פורסמו כבר ב-2015 כדי לתקן הטיות בהערכות. התוצאה המעשית: אלגוריתם אחד, עם אותה ארכיטקטורה ואותן הגדרות, שאומן בנפרד על כל משחק והגיע ליותר מ-75% מרמת בוחן-המשחקים האנושי ב-29 מתוך 49 משחקים, בלי שמתכנת הסביר לו מה המטרה או מה עושה כל כפתור.