חרטה (תורת ההחלטות)

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

חרטה של סדרות תוצאות והחלטות

נניח שתהליך מייצר סדרת תוצאות מספריות: ביחידת הזמן ה-$i$, התוצאה היא $x_{i}$. אלגוריתם מקוון משתמש במספרים שהתקבלו כדי לקבל החלטה $b_{i}=b_{i}(x_{1},\ldots ,x_{i-1})$ בתחילת יחידת הזמן ה-$i$. לאחר שהאלגוריתם מכריז על $b_{i}$, מתבררת התוצאה $x_{i}$. נניח שישנה פונקציה $P(x,b)$ המודדת את התועלת מהפעולה היא $b$ של התוצאה $x$.

החרטה של סדרת ההחלטות $b_{1},b_{2},\ldots ,b_{n}$ יחסית לסדרת החלטות אפשרית אחרת ${\hat {b}}_{1},{\hat {b}}_{2},\ldots ,{\hat {b}}_{n}$, מוגדרת כהפרש

$\sum _{i=1}^{n}\left[P(x_{i},{\hat {b}}_{i})-P(x_{i},b_{i})\right]$

.

דוגמאות

השקעה בתיק מניות

בשוק המניות יש $m$ מניות. הווקטור $x_{i}$ מציין את העלייה בערכי המניות ביום ה-$i$ (למשל $x_{i,j}=2$ אם המניה ה-$j$ הכפילה את ערכה ביום $i$, ואילו $x_{i,j}=0$ אם המניה ה-$j$ אבדה את כל ערכה).

השקעה בשוק זה היא וקטור שבו כל איבר $b_{ij}$ הוא החלק שנוטלת המניה ה-$j$ מתיק ההשקעות ביום ה- $i$. התועלת היא קצב הצטברות הרווחים, $\log(x_{i}\cdot b_{i})$. נניח שאלגוריתם ההשקעה משקיע בכל יום לפי היסטוריית השוק, כלומר וקטור ההשקעה הוא $b_{i}=b_{i}(x_{1},\ldots ,x_{i-1})$, ונשווה אותו לאלגוריתם השקעה פסיבי ${\hat {b}}_{1}={\hat {b}}_{2}=\cdots ={\hat {b}}$, המשקיע כל יום לפי תיק קבוע ${\hat {b}}$. לפי הגדרות אלה, החרטה שבהשקעה לפי האלגוריתם יחסית בהשקעה הפסיבית היא $\sum _{i=1}^{n}\left[\log({\hat {b}}\cdot x_{i})-\log(b_{i}\cdot x_{i})\right].$.

חיזוי תוצאת תנאי תוכנה

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

כל תוצאת תנאי היא $x_{i}\in \{0,1\}$. אלגוריתם חוזה את התוצאה הבאה $b_{i}=b_{i}(x_{1},\ldots ,x_{i-1})\in \{0,1\}$.

במקרה זה, נגדיר את תועלת הנחוש כ-$p(x,b)=1-|b-x|$, כלומר 1 אם הניחוש הצליח, ו-0 אם לא.

החרטה בהשוואה לסדרת ניחושים ${\hat {b}}_{1},\dots ,{\hat {b}}_{4}=1$ היא $\sum _{i=1}^{n}\left[|b_{i}-x_{i}|-|{\hat {b}}_{i}-x_{i}|\right].$.

הגדרות נוספות

חרטה אפשר למדוד בהשוואה לתוחלת של סדרת התוצאות (אם לתהליך $X$ יש התפלגות המייצרת את סדרת התוצאות, החרטה היא $E\left[\sum _{i=1}^{n}\left[P(x_{i},{\hat {b}}_{i})-P(x_{i},b_{i})\right]\right].$). אפשרות אחרת היא מדידה של התוצאה בהשוואה לסדרת התוצאות הגרועה ביותר: $\max _{x_{1},\ldots ,x_{n}}\left[\sum _{i=1}^{n}\left[P(x_{i},{\hat {b}}_{i})-P(x_{i},b_{i})\right]\right]$.

אפשרות נוספת היא להגדיר את החרטה כממוצע (בזמן) של אחד הביטויים הקודמים, דהיינו תוחלת או מקסימום של ${\frac {\sum _{i=1}^{n}\left[P(x_{i},{\hat {b}}_{i})-P(x_{i},b_{i})\right]}{n}}$.

חרטה פנימית וחיצונית

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

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

בהינתן רצף החלטות $b_{1},\ldots ,b_{n}$ אשר כל אחת מהן יכולה לקבל $m$ ערכים שונים, החרטה הפנימית מוגדרת כמקודם, אלא ששוקלים רק חרטה יחסית לסדרה ${\hat {b}}_{1},\ldots ,{\hat {b}}_{n}$ הנקבעת באופן הבא. בוחרים שני סוגי פעולות $i',j'\in \{1,\ldots ,m\}$, ומחליפים כל פעולה מסוג $i'$ בסדרה המקורית בפעולה מסוג $j'$.

דוגמה: חרטה פנימית במירוץ סוסים

באופן דומה לדוגמה בהשקעה בתיק מניות, נניח סדרת מרוצי סוסים שבכל אחד מהם יש (אותם) $m$ סוסים. בכל מרוץ $i$, הווקטור $x_{i}$ מציין את הניצחון: זהו וקטור שבו כל האיברים הם 0, למעט איבר יחיד שהוא 1 (האיבר המתאים לסוס הזוכה).

גם כאן נניח שהימור הוא וקטור שבו האיבר ה-$j$, כלומר $b_{ij}$, מציין את חלק ההשקעה של התיק ביום $i$ בסוס $j$ (כל רכיב כזה הוא לא-שלילי, וסכום הרכיבים בכל יום שווה ל-1), ונגדיר את תועלת ההימור כקצב הכפלת הכסף, או $\log(x_{i}\cdot b_{i})$ (גם כאן זו אינה האפשרות היחידה).

החרטה הפנימית היא $$\sum _{i=1}^{n}\left[\log({\hat {b}}_{i}\cdot x_{i})-\log(b_{i}\cdot x_{i})\right].$$ כאשר הסדרה ${\hat {b}}_{1},\ldots ,{\hat {b}}_{n}$ מושגת על ידי החלפת כל הימור על סוס $i'$ בהימור על סוס $j'$.

חרטה חיצונית

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

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

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

קטגוריה שנייה למדיניות חלופית היא זו המציעה שינוי פשוט לסדרת הפעולות המקוונות לפי חוק התאמה. החרטה החלופית מאפשרת לשנות את סדרת הפעולות המקוונת על ידי החלפת פעולה $i$ לפעולה $j$. ההבדל בין החרטה החלופית לחרטה הפנימית היא שמדיניות החרטה הפנימית היא שניתן להחליף פעולה אחת בפעולה אחרת בעוד חרטה חלופית מאפשרת להחליף אוסף של $N$ פעולות ב-$N$ פעולות אחרות. החרטה החלופית חסומה על ידי $O({\sqrt {T}}\cdot N\cdot log(N))$ כאשר T הוא מספר מקטעי הזמן.

שו"מ מתואם הוא התפלגות $Q$ על פני מרחב הפעולות כך שלכל שחקן אין חרטות פנימיות.

מזעור חרטה חיצונית

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

מודל

נניח מודל מקוון בו $N$ פעולות אפשריות: {X = {1,…,N. בכל מקטע זמן $t$ אלגוריתם מקוון $H$ בוחר התפלגות $p^{t}$ מעל $N$ הפעולות, לאחר-מכן היריב בוחר וקטור הפסד $l^{t}\in [0,1]^{N}$ כאשר $l_{i}^{t}\in [0,1]$ הוא ההפסד בפעולה ה-$i$-ית במקטע ה-$t$. במודל האינפורמציה המלאה האלגוריתם $H$ מקבל את וקטור ההפסד $l^{t}$ ומחשב את $(l^{t})_{H}=\sum _{i=1}^{N}p_{i}^{t}\cdot l_{i}^{t}$. במודל האינפורמציה החלקית האלגוריתם המקון מקבל $(l^{t},k^{t})$ כאשר $k^{t}$ מפולג לפי $p^{t}$ ו-$l_{H}^{t}=l_{(}^{t}k_{)}^{t}$ הוא ההפסד. ההפסד של הפעולה ה-$i$-ית במקטע הזמן $T$ הוא $L_{i}^{T}=\sum _{i=1}^{T}l_{i}^{t}$ וההפסד של האלגוריתם ה-$H$ הוא $L_{H}^{T}=\sum _{i=1}^{T}l_{H}^{t}$. נגדיר את החרטה החיצונית באופן שתהיה האפשרות לבחור מבין אוסף אלגוריתמים $A$, הנקראת קבוצת הכיווץ, את האלגוריתם עם הביצועים הטובים ביותר כך שההפסד יהיה: $L_{A}^{T},min=\min L_{a}^{T}$ כאשר $a\in A$.

נרצה למזער את החרטה החיצונית $R_{A}=L_{H}^{T}-L_{A}^{T},min$. בהינתן $A=X$ וגם $R=L_{H}^{T}-L^{T},min$, נחפש את האלגוריתם המקוון שהפסדו קרוב ל- $L^{T},min=\min _{i}L_{i}^{T}$.

חרטה חיצונית משתמשת בקבוצת כיווץ $A$ קבועה. נתייחס לחוקי ההתאמה כפעולות המשנות את הפעולות שנבחרו על ידי האלגוריתם המקוון. על ידי השינוי הנ"ל מתקבלת אסטרטגיה חלופית בה נרצה להשתמש כנגד היריב.

לחוק ההתאמה $F$ מקבל כקלט את היסטוריית הבחירות ואת הבחירה הנוכחית שבוצעה על ידי האלגוריתם המקוון ומחזיר כפלט פעולה אופציונלית. נסמן ב- $F^{T}$ את הפונקציה $F$ בזמן $t$, כולל תלות בהיסטוריה.

בהינתן אוסף התפלגויות הסתברותיות $p^{t}$ (בהן נעשה שימוש באלגוריתם המקוון $H$) וחוק ההתאמה $F$ נגדיר סדרה חדשה של התפלגויות הסתברותיות $f^{t}=F^{t}(p^{t})$ כאשר $f_{i}^{t}=\sum _{i}p_{i}^{t}$ כאשר $j:F^{t}(j)=i$. ההפסד של הסדרה המתואמת הוא $L_{H},_{F}=\sum _{t}\sum _{i}f_{i}^{t}\cdot l_{i}^{t}$. חוק ההתאמה $F$ מניב התפלגויות שונות.

בהינתן קבוצת חוקים סופית וחסרת זיכרון (=שאינה תלויה בהיסטוריה) Ғ ואוסף וקטורי הפסד, החרטה של האלגוריתם המקוון $H$ היא: $R_{F}=\max L_{H}^{T}-L_{h}^{T},_{F}$ כאשר Ғ$F\in$.

ראו גם

• ניתוח תחרותיות (competitive analysis) - חקר איכות החלטות של אלגוריתמים מקוונים.