Q-learning

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

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

למידת חיזוק

ערך מורחב – למידת חיזוק

בבעיה של למידת חיזוק מוגדרים סוכן, קבוצת מצבים $S$, וקבוצת פעולות למצב $A$. באמצעות ביצוע פעולה $a\in A$ הסוכן עובר ממצב למצב. ביצוע פעולה במצב נתון, מספקת לסוכן תגמול (ניקוד מספרי).

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

דוגמה

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

• 0 שניות זמן המתנה + 15 שניות מאבק בין הנוסע העולה לנוסעים היורדים.

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

• 5 המתנה + 0 שניות מאבק עם הנוסעים.

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

אלגוריתם

טבלת Q-Learning של מצבים ופעולות שמתאוחלת באפס, ואז כל תא מתעדכן באמצעות אימון.

המשקל עבור צעד ממצב ל-$\Delta t$ צעדים לעתיד מסומן באמצעות ${\ce {\gamma^{\Delta t}}}$ . $\gamma$ הוא מספר בין 0 ל 1 והוא קובע העדפה של תגמולים שהתקבלו מוקדם יותר מאשר אלה שהתקבלו מאוחר יותר. ניתן לתת ל-$\gamma$ פירוש של הסתברות הצלחה בכל $\Delta t$ צעדים.

האלגוריתם מתבסס על פונקציה המחשבת את האיכות של שילוב מצב-פעולה: $Q:S\times A\to \mathbb {R}$

לפני תחילת הלמידה, Q מאותחל לערך קבוע שרירותי. בכל זמן t, הסוכן בוחר פעולה $a_{t}$ ובעקבותיה מקבל תגמול $r_{t}$ ועובר למצב חדש $s_{t+1}$ (התלוי במצב הקודם ובפעולה שנבחרה) ו-Q מעודכן. האלגוריתם מבוסס על value iteration וממוצע משוקלל של הערך הישן והמידע החדש:

$Q^{new}(s_{t},a_{t})\leftarrow (1-\alpha )\cdot \underbrace {Q(s_{t},a_{t})} _{\text{old value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot \overbrace {{\bigg (}\underbrace {r_{t}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(s_{t+1},a)} _{\text{estimate of optimal future value}}{\bigg )}} ^{\text{learned value}}$

כאשר $r_{t}$ הוא התגמול המתקבל בביצוע המעבר ממצב $s_{t}$ למצב $s_{t+1}$ו-$\alpha$ הוא קצב הלמידה ($0<\alpha \leq 1$).

הרצה של האלגוריתם מסתיימת כאשר $s_{t+1}$ הוא מצב סופי.

היסטוריה

אלגוריתם Q-learning פורסם לראשונה על ידי ווטקינס (Watkins) ב-1989. ב-1992 פורסמה הוכחת התכנסות של האלגוריתם על ידי ווטקינס ודיין, וב-1994 בצורה מפורטת על יותר על ידי טסיטסיקיליס.