מבוא לשודדים רב-זרועיים

זכויות יוצרים 2021 מחברי TF-Agents.

מבוא

Multi-Armed Bandit (MAB) היא מסגרת למידת מכונה שבה סוכן צריך לבחור פעולות (זרועות) על מנת למקסם את התגמול המצטבר שלו בטווח הארוך. בכל סיבוב, הסוכן מקבל מידע על המצב הנוכחי (הקשר), ואז הוא בוחר פעולה על סמך מידע זה והניסיון שנאסף בסבבים קודמים. בסוף כל סבב, הסוכן מקבל את התגמול הקשור לפעולה שנבחרה.

אולי דוגמא הכי הטהורה היא הבעיה כי השאיל את שמה MAB: לדמיין שאנחנו מתמודדים עם k מכונה הימורים (בנדיטים בעלי יד אחת), ואנחנו צריכים להבין איזה מהם יש את התשלום הטוב ביותר מבלי לאבד יותר מדי כסף.

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

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

שודדים רב-זרועיים ולמידת תגבור

מדוע ישנה חבילת MAB בספריית TF-Agents? מה הקשר בין RL ל-MAB? ניתן להתייחס לשודדים מרובי זרועות כמקרה מיוחד של למידת חיזוק. אם לצטט מבוא RL :

בכל שלב בזמן, הסוכן נוקט פעולה הסביבה המבוססת על מדיניותו \(\pi(a_t|s_t)\), שבו \(s_t\) היא התצפית הנוכחית מהסביבה, ומקבל גמול \(r_{t+1}\) ואת התצפית הבאה \(s_{t+1}\) מהסביבה . המטרה היא לשפר את הפוליסה כדי למקסם את סכום התגמולים (החזר).

במקרה RL הכללי, התצפית הבאה \(s_{t+1}\) תלוי במצב הקודם \(s_t\) ופעולת \(a_t\) שנקטה המדיניות. החלק האחרון הזה הוא מה שמפריד בין MAB ל-RL: ב-MAB, המצב הבא, שהוא התצפית, אינו תלוי בפעולה שבחר הסוכן.

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

• סביבת פלטי תצפיות, ומגיב פעולות עם תגמולים.
• מדיניות פלטי פעולה המבוססת על תצפית, ו
• סוכן שוב ושוב מעדכן את המדיניות המבוססת על tuples תצפית-פעולה-בתגמול קודם.

סביבת הפטריות

למטרות המחשה, אנו משתמשים בדוגמה של צעצוע בשם "סביבת הפטריות". מערך הנתונים של פטריות ( Schlimmer, 1981 ) כוללת דוגמאות שכותרתו של פטריות מאכל רעילים. התכונות כוללות צורות, צבעים, גדלים של חלקים שונים של הפטרייה, כמו גם ריח ועוד רבים נוספים.

ניתן להפוך את מערך הנתונים של הפטריות, בדיוק כמו כל מערכי הלמידה המפוקחים, לבעיית MAB הקשרית. אנו משתמשים בשיטה גם בשימוש על ידי ריקלמה ואח. (2018) . בהמרה זו, הסוכן מקבל תכונות של פטריה, מחליט לאכול אותה או לא. אכילת פטריית מאכל מביאה לתגמול של +5, בעוד שאכילת פטרייה רעילה תיתן או +5 או -35 בהסתברות שווה. אי אכילת הפטרייה מביאה ל-0 פרס, ללא תלות בסוג הפטרייה. הטבלה הבאה מסכמת את מטלות התגמול:

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

סוכן LinUCB

ביצועים טובים בסביבת שודדים קונטקסטואלית דורשת הערכה טובה של פונקציית התגמול של כל פעולה, בהתחשב בתצפית. אפשרות אחת היא להעריך את פונקציית התגמול עם פונקציות ליניאריות. כלומר, לכל פעולה \(i\), אנו מנסים למצוא את הפרמטר \(\theta_i\in\mathbb R^d\) עבורו האומדנים

\(r_{t, i} \sim \langle v_t, \theta_i\rangle\)

קרובים ככל האפשר למציאות. הנה \(v_t\in\mathbb R^d\) הוא בהקשר המתקבל בזמן צעד \(t\). ואז, אם הסוכן הוא מאוד בטוח הערכותיה, הוא יכול לבחור \(\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle\) כדי לקבל את הפרס צפוי ביותר.

כפי שהוסבר לעיל, עצם בחירת הזרוע עם התגמול המשוער הטוב ביותר אינה מובילה לאסטרטגיה טובה. ישנן דרכים רבות ושונות כדי לערבב ניצול וחיפושי סוכני הערכה ליניארי, ואחד המפורסם ביותר הוא האמון העליון לינארי Bound (LinUCB) אלגוריתם (ראה למשל Li et al. 2010 ). ל-LinUCB יש שני אבני בניין עיקריות (עם כמה פרטים הושמטו):

1. היא שומרת על אומדנים לפרמטרים של כל זרוע עם הריבועים הפחותים לינארית: \(\hat\theta_i\sim X^+_i r_i\), שבו \(X_i\) ו \(r_i\) הם ההקשרים מוערמים ותגמולים של סיבובים שבו זרוע \(i\) נבחר, ו \(()^+\) הוא ההופכי פסאודו .
2. היא שומרת ellipsoids ביטחון מוגדר על ידי ההופכי השונה המשותפת \(X_i^\top X_i\) עבור האומדנים הנ"ל.

הרעיון המרכזי של LinUCB הוא של "אופטימיות מול אי ודאות". הסוכן משלב חיפושים באמצעות הגברת האומדנים בסכום התואם את השונות של ההערכות הללו. זה המקום שבו ellipsoids ביטחון נכנסים לתמונה: לכל זרוע, ההערכה האופטימית היא \(\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle\), שבו \(E_i\) הוא סביב אליפטיים \(\hat\theta_i\). בוחר הסוכן מחפש מיטב זרוע \(\arg\max_i\hat r_i\).

כמובן שהתיאור לעיל הוא רק סיכום אינטואיטיבי אך שטחי של מה של LinUCB עושה. יישום ניתן למצוא בסיס הקוד שלנו כאן

מה הלאה?

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