Q-learning

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

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

למידת חיזוק

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

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

דוגמה

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

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

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

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

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

אלגוריתם

המשקל עבור צעד ממצב ל- $\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.^[3] ב-1992 פורסמה הוכחת התכנסות של האלגוריתם על ידי ווטקינס ודיין,^[4] וב-1994 בצורה מפורטת על יותר על ידי טסיטסיקיליס.^[5]

הערות שוליים

^ ^1.0 ^1.1 Melo, Francisco S. "Convergence of Q-learning: a simple proof" (PDF).
^ Matiisen, Tambet (19 בדצמבר 2015). "Demystifying Deep Reinforcement Learning". neuro.cs.ut.ee (באנגלית אמריקאית). Computational Neuroscience Lab. נבדק ב-2018-04-06. {{cite web}}: (עזרה)
^ Watkins, C.J.C.H. (1989), Learning from Delayed Rewards (PDF) (Ph.D. thesis), Cambridge University
^ Watkins and Dayan, C.J.C.H., (1992), 'Q-learning.Machine Learning'
^ Tsitsiklis, J., (1994), 'Asynchronous Stochastic Approximation and Q-learning. Machine Learning'

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

35322565Q-learning

[auto-1] 1.0 ^1.1 Melo, Francisco S. "Convergence of Q-learning: a simple proof" (PDF).

[הערה_מספר_25495495:0-2] Matiisen, Tambet (19 בדצמבר 2015). "Demystifying Deep Reinforcement Learning". neuro.cs.ut.ee (באנגלית אמריקאית). Computational Neuroscience Lab. נבדק ב-2018-04-06. {{cite web}}: (עזרה)

[3] Watkins, C.J.C.H. (1989), Learning from Delayed Rewards (PDF) (Ph.D. thesis), Cambridge University

[4] Watkins and Dayan, C.J.C.H., (1992), 'Q-learning.Machine Learning'

[5] Tsitsiklis, J., (1994), 'Asynchronous Stochastic Approximation and Q-learning. Machine Learning'

[1]

[2]

[3]

[4]

[5]