כשמתפרסם מאמר ב Science בתחום שלי (Machine Leaning) זה משהו מיוחד כי זה לא קורה כל יום.
אתם מוזמנים לקרוא על איך OpenAI מביאים מודל לשחק את המשחק הרב משתתפים “תפוס את הדגל” ברמת מיומנות אנושית ואולי יותר מעניין מזה איך מאמנים מודל לגרום לסוכנים שמשחקים מחבואים לשתף בינהם פעולה באופן יצירתי:
בימים אלו אני בונה קורס חדש (Reinforcement Learning), והחלטתי גם לסדר את החומרים לפוסט שיאמלק לכם את הבסיס האלגוריתמי לחידושים אלו.
לא הצלחתי למצוא תירגום טוב למונח: גראדיאנטים של מדיניות (אשמח לעזרה…)
אבל Policy Gradient הינה גישה אלגוריתמית לפתירת בעיות Reinforcement Learning שנגזרו ממנה אלגוריתמים רבים כגון: Actor Critic, A2C, A3C, TRPO, PPO, SAC ועוד ועוד…
אם עלי לתת את התורה כולה על רגל אחת אסכם זאת במשפט הבא: ניתן לסוכן לשחק לאורך זמן ואז נעדכן את המודל באופן כזה שיחזק (ויחזור) על אותם ההחלטות שהביאו לתגמולים חיוביים ונחליש את ההחלטות שהביאו לתגמולים שליליים.
רקע קצר על למידה באמצעות חיזוקים (Reinforcement Learning)
יש סוכן (Agent) שחי בסביבה דינאמית (Environment) ויש לו סט של פעולות (Actions) שהוא יכול לעשות בסביבה. הפעולות שלו עשויות לשנות את המצב (State) של הסביבה, ועל כל פעולה שלו הוא עשוי לקבל פידבק מהסביבה שנקרא תגמול (Reward) שיכול להיות חיובי או שלילי. מטרתינו למצוא את המדיניות (Policy) שהינו אלגוריתם שמחליט בעבור הסוכן איך לפעול בסביבה (איזו פעולה לבחור בכל רגע) באופן כזה שיביא למקסימום ההחזר (Return) שזה סך כל התגמולים שמקבל הסוכן.
השפה המתמטית לתיאור בעיה זו היא תהליך החלטות מרקובי MDP=Markov Decision Process:
כפי שניתן לראות בתמונה יש גרף שקודקודיו הינם ה states בו יכול להימצא הסוכן, ולכל קשת (כיוונית) בין קודקודים יש ערך מספרי שמתאר את ההסתברות מעבר מקודקוד לקודקוד. ולעיתים מתקבל תגמול במהלך הדרך (החיצים המסולסלים הצהובים).
עידן הלמידה העמוקה חולל מהפיכה גם בתחום ה Reinforcement Learning במובן הזה שרשת נוירונים עמוקה מהווה את המדיניות (Policy), ז”א מקבל כקלט את ה State ומחזירה את הפעולה (Action) הרצוייה.
כעת חלק הכיפי,
פורמליזם מתמטי לתיאור הבעיה
בכל נקודת זמן t יש לנו מצב, פעולה ותגמול:
ומאחורי הקלעים קיימת פונקציית הסתברות המעברים בין המצבים:
שמשמעותה: מה ההסתברות שאם התחלנו במצב St והסוכן בחר לבצע פעולה At הסביבה עברה למצב St+1.
למשל אם הסוכן שלנו הוא רכב, המצב שלנו הוא מיקומו במרחב (x,y) והפעולה היא לקחת הגה ימינה, מה ההסתברות שהרכב יעבור למצב (x+5,y). אז בהסתברות גבוהה זה יקרה. אבל לא תמיד זה יקרה כי אולי יש שמן על הכביש והפעולה הביאה את הרכב למצב אחר (x+500,y).
המדיניות (אופן הפעולה של הסוכן) יכולה להיות פונקציה דטרמיניסטית שמקבלת מצב St ומחזירה פעולה At. אבל כשמרחב הפעולות האפשרי רציף ולא בדיד ויש אינסוף פעולות אפשריות נעדיף לעבוד עם מדיניות סטוכסטית, ז”א מגרילה כל פעם פעולה לפי ההתפלגות . (ליתר דיוק מה שיקרה בפועל זה שנגריל את הפעולה הבאה מתוך התפלגות גאוסית לפי וקטור תוחלות אותו תחזיר לנו הרשת נוירונים שתקבל את המצב הנוכחי)
מסלול (Trajectory) סופי הינו וקטור של השלשות הבאות:
והוא מתאר שרשרת מצבים, או אם תרצו קטע מהקלטה של משחק בו הסוכן פועל בסביבה.
כל אחד מהאלמנטים במסלול 𝜏 הינו וקטור אקראי, וההסתברות לקבל מסלול שלם הינה:
ההסתברות לקבל מסלול 𝜏 היא מכפלת ההסתברות להיות במצב הראשון S1 כפול
ההסתברות לבחור פעולה A1 כפול ההסתברות לעבור למצב S2 כפול ההסתברות לבחור פעולה A2 וכו’…
נשים לב שמופיעות שתי פונקציות התפלגות שונות, האחת P אותה הזכרתי קודם קשורה לסביבה ואין לנו שליטה עליה והשניה 
(המדיניות) שתלויה בפרמטרים θ שהם למעשה הפרמטרים או המשקלים של הרשת נוירונים אותה נאמן.
פונקציית המטרה שלנו J שאותה נאפטם (ז”א נשאף למצוא לה מקסימום) הינה התוחלת של סכום התגמולים:
כזכור תוחלת של פונקציה של מ”א היא סכום (או אינטגרל במשתנים אקראיים רציפים) של הפונקציה של המשתנה האקראי כפול ההסתברות שלו. במקרה שלנו המשתנה האקראי הינו 𝜏 והפונקציה הינה 
שמהווה את התגמול המצטבר שמקבל הסוכן כשנע במסלול 𝜏:
אם כן, מטרתינו לאמן רשת נוירונים (שמשקליה θ) שבהינתן מצב state תחזיר פילוג ממנו נגריל פעולה אופטימלית בעבור הסוכן. פעולה אופטימלית במובן הזה שכשישחק לפיה יקבל בתוחלת סכום תגמולים מירבי:
נשים לב ש 
כולל בתוכו למעשה גם את 
על אף שהסימון אינו מייצג זאת.
מדוע לא פשוט לאמן מודל עם פונקציית מטרה?
התחום Reinforcement Learning אומנם יושב תחת המטריה הרחבה של עולם ה Machine Learning אבל הוא אינו Supervised Learning וגם אינו Unsupervised Learning כי זה לא שיש לנו Ground Truth של אילו החלטות היה הסוכן אמור לבחור בכל צעד שלו, אבל מצד שני גם לא יהיה נכון לומר שלא קיים ברשותינו מידע לגבי מה נכון ומה לא כי יש לנו את התגמולים. ולכן זה מן תחום כלאיים בין Supervised לבין Unsupervised.
אם באימון של מודלי Machine Learning אחרים נזין בכל איטרציית אימון סט של דוגמאות (וב Supervised גם סט תואם של Labels) בבעיות Reinforcement Learning ניתן לסוכן לפעול (בין אם באופן אקראי בהתחלה ובין אם בדרך אחרת) ונשמור בזכרון מסלולים (Trajectories) שעשה. באמצעות כל מסלול (הכולל סדרה של מצב, פעולה, תגמול) נוכל לבצע איטרציית אימון למודל רשת נוירונים שלנו, כזה שימקסם את פונקציית המטרה שהגדרנו.
ברמה האינטואטיבית ניתן להבין שבהינתן מסלולים עליהם רץ הסוכן, לא באמת נוכל לחפש במרחב ה-θ מודל משופר שהיה מביא לסכום תגמולים גדול יותר על המסלולים האלו, כיוון שאילו המודל היה שונה אזי המסלולים היו שונים. אבל המסלולים שהקלטנו זה מה שיש לנו – וזה מקשה על האופטימיזציה…
כידוע בלמידה עמוקה משתמשים ב Gradient Descent (או בשיכלולים שלו) כדי לאמן את המודל:
אם כן ננסה לגזור את פונקציית המטרה שהגדרנו מקודם לפי משקלי המודל:
הגראדיאנט נכנס לאינטגרל אבל הגזירה של 
לא פשוטה כי היא נגזרת של מכפלות של הרבה פונקציות הסתברות (בכל צעד במסלול) ולכאורה תלויה בפונקציות שאין ברשותינו (הסתברויות המעבר בין המצבים).
אז מה עושים בכל זאת ?
מכיוון שלכל f(x) מתקיים:
נוכל להשתמש בזה לטובתינו:
ולקבל:
מעבר ראשון הינו הגדרת התוחלת כפי שראינו למעלה והכנסת הגראדיאנט לתוך האינטגרל, מעבר שני בשימוש בזהות ומעבר שלישי הוא שוב לפי הגדרת התוחלת.
נשים לב שההסתברות לקבלת מסלול
תלויה ב θ אבל סך התגמולים 
אינו תלוי ב θ עבור מסלול מסויים 𝜏.
הטריק הזה שהוסיף לנו log עזר לנו להמנע מנגזרת של מכפלות.
נזכור שההסתברות לקבל מסלול היא מכפלת ההסתברויות של המעברים בתוך המסלול:
וכשמפעילים על מכפלות אלו לוג זה הופך לסכומי הסתברויות:
ואז הגרדיאנט שלנו לפי θ נהיה פשוט יותר כי כל מה שלא תלוי בו מתאפס:
הלוג היפריד לנו בין הצימוד הבעייתי שהיה לנו ובזכותו נפטרנו מגורמים שממילא לא הייתה לנו דרך לחשב, לסיכום מקבלים:
בחיים האמיתיים נחשב את התוחלת הזו (של ההחזר כפול הגראדיאנט של הלוג של המדיניות) ע”י מיצוע על פני הרבה מסלולים שהסוכן שלנו ישחק, וכך נעדכן את משקולות הרשת בכל איטרציית אימון:
כאשר i רץ על פני כל ה trajectories שהקלטנו ו t הוא האינדקס בכל trajectory.
פירוש לתוצאה:
המרכיב השמאלי בביטוי הוא ה Maximum Likelihood של ההסתברות
ז”א הוא מבטא איך לעדכן את המשקולות כדי שבסבירות גבוהה יותר הסוכן יעבור את המסלולים שאגרנו.
הביטוי כולו מבטא איך לעדכן את משקולות הרשת כך שתגדיל את ההסתברות לקבל את המסלולים שאגרנו שהיו להם תגמולים מצטברים גבוהים ותקטין את ההסתברות לקבל את מסלולים להם היו תגמולים מצטברים נמוכים.
צעד אחרון לפני מימוש
אז אפילו שיש נוסחה שימושית מפורשת לקח לי לא מעט זמן להבין קודים לדוגמא המממשים Vanilla Policy Gradient (אלגוריתם Reinforce), ורק בזכות הקורס של ברקלי הבנתי שאם מניחים התפלגות נורמלית למדיניות ומשתמשים בפרדיקציה של הרשת fלהיות וקטור התוחלות:
אז עידכון המשקולות נהיה בפועל:
הלוג ביטל את האקספוננט של הגאוסיאן ונשארים עם הביטוי לטובת עידכון המשקולות של הרשת:
לשם הפשטות נתעלם ממטריצת הקוואריאנס ומהחצי המופיע בביטוי. (נניח שמטריצת הקוואריאנס הינה מטריצת היחידה וממילא החצי נבלע ב Learning Rate):
בכל איטרצית אימון נשנה את המשקלים לפי הפער של של מה שאומרת הרשת לעשות לבין מה שעשינו כשהסוכן שיחק כפול ההחזר שאומר לנו אם כדאי לחזור על הפעולות שבוצעו או לא.
וכעת כשמסתכלים על מימושים הכל נראה ברור יותר… לא כך ?
מקורות
