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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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