DAgger מוסבר: מדוע Behavior Cloning סוטה וממה Dataset Aggregation בעצם משיג הוכחה

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

לכשל זה יש שם וחלק תיאוריה מוסכם מאחוריו. זה הראשון משלוש מאמרים על DAgger, וזה מכסה את הטיעון עצמו: מדוע התאמת מדיניות על המסלולים של המדגים עצמו מייצרת שגיאה שיכולה לגדול עם הריבוע של אורך הפרק, מה Dataset Aggregation משנה, ומה הוכחת ה-no-regret לא מבטיחה. הלולאה בחומרה אמיתית מסוגלת ב-הפעלת לולאת DAgger ב-SO-100, הגרסה המעניינת בצל בתוך HG-DAgger ותערמולות מעניינות בצל, ושאלת המדידה ב-מדידת לולאת DAgger.

ההנחה שـBehavior cloning עושה בשקט

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

מה שמוד הוא בדיקה של היכן הגיעו הזוגות האלה. כל אחד מהם שוכן על מסלול שהמדגים ייצרו. המדיניות שאתה מפתח מייצרת את שלה. ברגע שהוא חורג, הוא נשאל על מצבים שלא היו בהתפלגות ההכשרה, ותשובתו מזיזה אותו הלאה. Ross, Gordon ו-Bagnell פותחים את מאמר ה-DAgger בדיוק בזה: חיזוי סדרתי מפר את ההנחה i.i.d. תחתון למידה סטטיסטית, כי החיזויים של הלומד עצמו קובעים את הקלטים שהוא רואה הבא.

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

החלף Mario ל-SO-100 arm והמבנה זהה. ההפגנות שלך מראות גישה נקייה ותפיסה נקייה, לא את הגריפר סוגר שני סנטימטרים קצרים - כך שלמדיניות אין מושג מה לעשות משם, וכל מה שהוא מנחש לוקח אותה הלאה. Covariate shift הוא רכוש של ה-data collection procedure, לא של ארכיטקטורת הרשת.

היכן המונח הריבועי מגיע

נייר AISTATS 2010 מאת Ross ו-Bagnell, Efficient Reductions for Imitation Learning, עושה את הסתערות הדיוק. תן לT להיות אופק המשימה, תן לעלות המשימה להיות מוגבלת בתוך המרווח היחידה, ותן לאפסילון להיות אובדן החלופי שנמדד תחת התפלגות המצב של ה-expert's - המספר שקבוצת הוידוליציה שלך דווחה. ואז העלות הנוספת של הפעלת המדיניות לשלבי T, ביחס למומחה, מוגבלת ב-T בריבוע כפול אפסילון. Ross, Gordon ו-Bagnell מדווחים מחדש זה כ-Theorem 2.1 במאמר DAgger ומוסיפים את המשפט שחשוב: הגבול הוא הדוק. בעיות קיימות שבהן מדיניות עם אובדן אפסילון בהתפלגות המומחה באמת כרוכה בעלות נוספת הגדלה ריבועית ב-T.

Tight אינו פירושו טיפוסי. המונח הריבועי הוא מקרה גרוע על סוג של בעיות, לא חיזוי על משימת pick-and-place שלך. מה שזה יוצר הוא שיותר הפגנה של מומחה לא יכול להסיר את הבעיה: זה רק משחיזה את ההערכה של אפסילון על התפלגות שהמדיניות לא תיבדק.

דרך המילוט נמצאת באותו נייר, מצוינת מחדש כ-Theorem 2.2. אם מדיניות משיגה אובדן אפסילון תחת ה-its own התפלגות המצב, וביצוע אחד שגוי עולה לכל היותר u בעלות-לך מול המומחה, העלות הנוספת מוגבלת ב-u כפול T כפול אפסילון - ליניארי בהיקף. הקבוע u הוא הכמות המעניינת: לכל היותר 1 עבור 0-1 חוסר הסכמה עם המומחה, וO(1) בעת שהמומחה יכול להתאושש בתוך כמה שלבים. במקרה הגרוע ביותר זה O(T), והגבול הליניארי אז לא טוב יותר מהריבועי.

שתי הניסיונות שהגיעו לפני DAgger

Forward training היא התשובה כנה אך לא מעשית. הדרכת מדיניות נפרדת עבור כל Timestep, בסדר, כל אחת בהתפלגות המצב המעורר על ידי המדיניות שכבר קבעו צעדים קודמים, כך שכל מדיניות רואה בדיוק את ההתפלגות שהיא תתמודד. הלכידות נמצאת בתיאור: T מדיניות, מוכשרות ברציפות, ללא עצירה מוקדמת. לתמרון episode ב-30 מסגרות לשנייה, T נמצא במאות.

SMILe, מאותו נייר, וSEARN, מעבודתו של Daume, Langford ו-Marcu על ניבוי מובנה, קח את הדרך השנייה: מדיניות סטציונרית אחת, אך סטוכסטית. כל איטרציה מוכשרת רכיב ומוסיפה אותו לתערובת, הזחת פי כוח הרחק מהמומחה. התוצאה היא תערובת שבה חלקים מסוימים גרועים יותר מאחרים - על זרוע פיזית, בקר שיכול לדגום רכיב רע באמצע תנועה. זה המוטיבציה הנאמרת לכן רוצה מדיניות סטציונרית deterministic במקום.

DAgger: רעיון אחד, קופסה אחת

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

D            <- {}                      # the aggregate dataset
pi_hat_1     <- any policy in Pi

for i = 1 .. N:
    pi_i  = beta_i * expert  +  (1 - beta_i) * pi_hat_i
    roll out pi_i for T steps, record every visited state s
    D_i   = { (s, expert(s))  for every visited state s }
    D     = D  union  D_i               # aggregate, do not replace
    pi_hat_{i+1} = train on all of D

return the best pi_hat_i on a validation set

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

ה-Beta schedule, ולמה זה לא כפתור כיוונון

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

התיאוריה מטילה בדיוק תנאי אחד: הממוצע הפועל של ה-betas חייב ללכת לאפס. הניתוח עובד עם beta_i קשור על ידי (1 - אלפא) בעוצמה i-1, עבור קבוע אלפא עצמאית של T.

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

הערובה: הפחתה ללמידה מקוונת ללא חרטה

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

אלגוריתם הוא ללא חרטה אם ממוצע אובדן שלו על סיבובי N מתקרבת שלה של הטוב ביותר מדיניות אחת בדיעבד. Follow-The-Leader על הפסדים קמורים חזקים הוא אלגוריתם כזה, עם חרטה ממוצעת ימצאך על ההזמנה של 1/N - והדרכה מחדש על הצבירה המלאה היא בדיוק Follow-The-Leader. כל לומד שאינו-חרטה אחר שירת גם כן: הניתוח הוא הפחתה, לא רכוש של אופטימיזר אחד.

Lemma אחד גשר את הפער בין המדיניות המעורבת שאספה את הנתונים והמדיניות הלמודה שתפותחה: Lemma 4.1 מגביל את ה-L1 מרחק בין התפלגויות המצבים שלהם על ידי 2 T beta_i. זו הסיבה beta ים חייבים להתפורר - בעוד שהמומחה עדיין מחזיק סמכות בקרה משמעותית, המצבים שאתה אוסף לא המצבים שהמדיניות שלך תייצר. שלבו את ה-Lemma עם גבול החרטה ותוצאה ראשית עוקבת: לאחר בערך איטרציות T, יש מדיניות כלשהיא ברצף יש אובדן החלופי בהתפלגות שלה בתוך O(1/T) של epsilon_N. הזן את זה לגבול הליניארי ואתה נוחת ב-Theorem 3.2.

הצד האמפירי הוא צנוע לפי תקנים הנוכחיים. ב-Super Tux Kart קו הבסיס בפיקוח לא שיפר את הנפילות הממוצעות שלו לכל הקפה כאשר יותר נתונים הגיע, DAgger הגיע למדיניות שאף פעם לא נפלה מהמסלול לאחר חמש עשרה איטרציה, וSMILe לאחר עשרים עדיין נפל בערך פעמיים לכל הקפה. בחוקי הסימון, דיוק תו רץ 82 אחוז ללא מבנה, 83.6 אחוז בפיקוח, 85.5 אחוז עם DAgger. אף אחד מאלה אינו תוצאה תמרון.

מה ההוכחה לא מבטיחה

הצהרות משפט הם מותנים, ותנאים מוטלים הם עמוסים.

תוצאה נוספת אחת מצוטט לעתים קרובות כ-refutation ואינו אחד. Rajaraman, Yang, Jiao ו-Ramachandran לחקור את הגבולות מינימקס של Imitation Learning ב-MDPs epISodic עם מרחב מצב סופי S ואופק H, וקבל אי-נחיות להרטות בהזמנה של |S| H בריבוע על N שמחזיק אפילו כאשר הלומד עשוי באופן פעיל שאלה את המומחה בכל מצב בקרה. זה שיעור מקרה גרוע על סוג של MDPs ב-תקציב פרק קבוע, ומה זה מחסם הוא הרעיון שהאינטרקציה משפרת את שיעור ה-minimax; משפט ה-DAgger היא הצהרה שונה, מגבילה את המדיניות המפותחת ביחס למה כיתת המדיניות שלה יכולה להשיג.

Swamy, Choudhury, Bagnell ו-Wu מאוחר יותר סווגו אלגוריתמים אלה לפי אילו רגעים של התנהגות המומחה הם תואמים, וציגו מושג של Recoverability רגע שמכנחה כמה טוב כל משפחה מטת שגיאה סתערות. הסקרים על ידי Osa וב-Celemin כיסוי הנוף אלגוריתם וממשקי Feedback אדם.

הדברים: תיוג מצבים המומחה אף פעם לא ייצר

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

Kelly, Sidrane, Driggs-Campbell ו-Kochenderfer קובע את הטענה ישירות בנייר HG-DAgger. Vanilla DAgger דורש שהמומחה יספק תוויות פעולה בזמן לא להיות בשליטה מלאה בו. זה מפחית בטיחות, ועם מומחים אדם זה כנראה להשתפל את האיכות של התוויות שנאספו, שהם לשים למטה לתפיסה lag actuator. התווית שאתה מקבל חזרה היא לא התווית האלגוריתם הנחה.

Laskey וקולגות תקוף את הבעיה מהצד השני עם DART, וה-framing שלהם היא בוטה: טכניקות מקוניות-מדיניות הם tedious עבור מעת אנשים, להוסיף עול חישוב, ויכול להיות מדינות שטחניות מסוכנות בזמן הכשרה. החלופה שלהם הזריקה רעש כיול לתוך הפגנות של העמידות שלהם עצמו, כך התאוששות מקבלת הדגימו ללא הרובוט אי פעם הפעלה מדיניות לא מהימנה. על MuJoCo Humanoid הם דיווח DART הפחתת פרס מצטבר של העמידות של 5 אחוז בזמן הכשרה, בעוד DAgger ביצוע מדיניות עם פרס מצטבר 80 אחוז פחות מאשר העמידות; על grasping בבלגן עם טויוטה HSR, ממוצע 62 אחוז עלייה על Behavior cloning.

Zhang וה-Cho SafeDAgger יחס שאילתות לתיקייה מדיניות כמשאב דל: מדיניות בטיחות נפרדת חוזה, ללא שאילתה, אם המדיניות ראשונית הוא עתידה לחרוג מהתיקייה מעבר סף, ורק אלה מצבים הם הועברו. כל שלוש לתגובה לאותה עובדה - ה-ניתוח DAgger מטיל חינם עבור תוויות מומחה, ומציאות מטילה דבר גדול.

מה פירושו הדבר עבור SO-100 על שולחנך

תרגם את אופק לתוך יחידות שלך. פרק עשרים שנייה ב-30 מסגרות לשנייה הוא 600 צעדים החלטה, וT בכל קשור למעלה היא מספר הזה. ב-T = 600, הפער בין טווח מונח ביחס ל-T וזה ביחס ל-T בריבוע היא הפער בין מדיניות שמתאוששת מגישה רע וזה לא.

זה חלק של מדוע כוונון פעולה עוזר: כאשר מדיניות פולטת סדרה קצרה של פעולות לכל צעד הסקה, מספר של נקודות החלטה טיפות, וכך עושה מספר של סיכויים להתסתכל. Zhao, Kumar, Levine וFinn שם Compounding error כמו ה-Motivation עבור Action Chunking עם Transformers, ודווח 80 כדי 90 אחוז הצלחה על שש משימות קשה בעלות-נמוכה בעלות-נמוכה, מ-עשר דקות deserving הפגנות. Chunking לא להסיר Covariate shift - המצבים עדיין מדיניות שלו - אבל זה מקצר את ההיקף יעיל. ראה action chunking והוא SO-100 imitation learning guide.

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

שלישי תרגום היא קו-איכות נתונים הערה האנליזה לא כיסוי. Mandlekar וקולגות ללמוד שישה offline למידה אלגוריתמים על חמש מדומה וושלוש עלות העולם רבי-שלב תמרון משימות, ודווח רגישות לאלגוריתמי עיצוב בחירות, תלות על איכות של הפגנות, וvariability כל ידי עצירה אמות קבע. Belkhale, Cui וSadigh טיעון כי איכות נתונים צריך להיות formalized דרך פעולה כלי ו-Transition גיוון, וציין שגיוון מצב לא תמיד בנוחות. סיבוב DAgger מוסיף מצבים אף אחד בחרו בכוונון: כמה התאוששות נתונים צריך, כמה הרובוט בלגן בעוד תתאומים עבור שער takeover שליטה.

Mechanically סיבוב היא שישה צעדים: הפעלה הסקה עם רישום על, לקחת סוגר כאשר מדיניות misbehaves, בדיקה הרץ ודירוג כל פרק, סינק התיקונים, לחבור מעורב נתונים מ-מקורות וא תיקונים עם בחירת פרק שנעשה בצורה מפורשת לכל מקור, והמשך הכשרה מהקודם checkpoint למדי מה בסיס דם. על ay-robots אלה צעדים קיימים כמו כפתורים, שמסיר את plumbing אבל לא את השיקול. שתיים caveats: החל מא checkpoint initializes משקל וזה לא הסקה אופטימיזר המשך, ו-ha leader-arm יישור צעד הוא עדיין בקלות מבחן על חומרה. ראה training ו-datasets.

עץ משפחה, בטבלה אחת

שאלות שנשאלות לעתים קרובות

היכן ללכת מכאן

אם אתה לא אם הכשיל מדיניות עדיין, התיאוריה היא מוקדם: תיעוד נתונים ראשון, התחלה מ-training your first policy וה-desktop client. אם אתה שוקל קו שיקול מאה הפגנות ניקיות נגד התחלת תיקונים: הפגנות ניקיות לא תקן בעיה חלוקה. לגבי ה-Mechanika, להמשיך עם the human-gated variant ואז the SO-100 walkthrough.