ד.5 — תכנון דינמי: Value Iteration

המצגת: תכנון דינמי — המשך (עותק מקומי) · קוד: ממשק הפאזל · Value Iteration בפאזל

הפרק הזה עונה על אותה שאלה כמו הפרק הקודם: כשחוקי המשחק ידועים לנו במלואם, איך מחשבים את המהלך הטוב ביותר בכל מצב? ההבדל הוא בדרך. ב־Policy Iteration עבדנו בשני שלבים נפרדים — הערכה מלאה של המדיניות הנוכחית, ורק אחר כך שיפור שלה — וחזרנו עליהם עד שהמדיניות התייצבה. הערכה מלאה בכל סבב היא עבודה רבה, וחלק גדול ממנה מתבזבז: אנחנו מחשבים במדויק את ערכיה של מדיניות שממילא עומדים להחליף.

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

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

האם נחוצה טבלת מדיניות?

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

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

Value Iteration — בוחרים ומעדכנים יחד

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

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

נראה איך זה נראה בפועל. בלוח 4×4 שלנו נתחיל מכל הערכים באפס ונשתמש ב־γ=0.9. לשני השכנים של היעד יש פעולה שנותנת מיד 1, ולכן הערך שלהם עולה ל־1. מצבים שיכולים להגיע אליהם יקבלו בהמשך 0.9, ואחריהם יתפשטו 0.81, 0.729 וכן הלאה. מעל תא ההפסד אין הכרח לבחור בירידה אליו: העדכון בוחן גם את שאר הפעולות.

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

בסיום מתקבלת הטבלה הבאה, בעיגול לשלוש ספרות. השורות נספרות מלמעלה והעמודות משמאל; תאי הסיום מסומנים בצבע ונשארים בערך 0, מפני שהתגמול ניתן בכניסה אליהם. זו בדיוק הטבלה שאליה הגיע Policy Iteration בפרק הקודם — אבל הפעם בלי טבלת מדיניות ובלי הפרדה בין הערכה לשיפור.

אותו כלל עדכון פועל גם על מבוך 5×5 שפתרנו בסוף הפרק הקודם. מתחילים מטבלת אפסים, סורקים את המצבים ובכל תא שומרים את הציון הגבוה ביותר מבין הפעולות החוקיות; המידע על היעד מתפשט לאורך המסדרון, מסביב לשורות הקירות, עד מצב ההתחלה. הטבלה המתקבלת זהה לזו ש־Policy Iteration הגיע אליה, ולכן גם המסלול שהסוכן יבחר לפיה זהה: 14 צעדים אל היעד.

Bootstrapping — לומדים מהערכות קיימות

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

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

סדר הפעולות ותנאי העצירה

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

Initialize V(s) = 0 for every state
Repeat:
    delta = 0
    For every nonterminal state s:
        old_value = V(s)
        V(s) = maximum of r + gamma * V(next_state)
               over all legal actions
        delta = max(delta, abs(old_value - V(s)))
Until delta < accuracy

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

ממשק פאזל המספרים הנתון

לוח 4×4 עם 16 מצבים נוח להמחשה, אבל לא משכנע: את הטבלה שלו אפשר למלא גם ביד. כדי לראות שהאלגוריתם באמת מועיל, ניישם אותו על בעיה שאי אפשר לפתור בעיון. כעת ניישם את האלגוריתם על פאזל של שמונה מספרים ומשבצת ריקה בלוח 3×3, שהזכרנו כדוגמה בפרק ד.3. המטרה היא להגיע לסדר 1 עד 8, כשהמשבצת הריקה נמצאת בפינה הימנית התחתונה. בניגוד לגריד 4×4, כאן מצב הוא סידור הלוח כולו, ולא מיקומו של הסוכן בתא. הפעולות הן ארבע הזזות אפשריות של המשבצת הריקה, והמודל ידוע: אנחנו יודעים בדיוק איזה סידור יתקבל מכל הזזה.

לצורך טבלת הערכים נייצג מצב באמצעות tuple של תשעה מספרים, לפי סדר השורות; 0 מציין את המשבצת הריקה. בקוד המקור משתמשים גם באובייקט State, וממירים את הלוח ל־tuple כמפתח. בעותק המצורף ממשק המשחק מקבל את ה־tuple ישירות כדי למקד את הקוד בחישוב הערכים.

start = (1, 2, 3,
         4, 5, 6,
         0, 7, 8)

goal = (1, 2, 3,
        4, 5, 6,
        7, 8, 0)

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

אתחול טבלת הערכים וקוד התכנון

טבלת הערכים צריכה שורה לכל מצב אפשרי. יש 9! = 362,880 סידורים של תשעת התאים — לעומת 16 בלוח הקטן. כמו בקוד הפתרון, ניצור מילון המכיל את כולם. חלק מהסידורים אינם ניתנים להגעה ממצב היעד; עצם הוספתם למילון אינה הופכת אותם לפתירים. בדוגמה נבחר מצב התחלתי פתיר.

from itertools import permutations
from puzzle_env import Puzzle

def init_values():
    return {state: 0.0 for state in permutations(range(9))}

permutations מייצרת את כל הסידורים, וכל סידור משמש מפתח במילון. כעת נפעיל סריקות על המילון, עם γ=0.95 ודיוק 0.001, לפי גרסת הפתרון. הפונקציה היא תרגום ישיר של הפסאודו־קוד שראינו למעלה:

def value_iteration(env, values, gamma=0.95, accuracy=0.001):
    sweeps = 0
    while True:
        delta = 0.0
        for state, old_value in values.items():
            if state == env.goal:
                continue
            best_value = float('-inf')
            for action in env.get_actions(state):
                next_state, reward = env(state, action)
                candidate = reward + gamma * values[next_state]
                best_value = max(best_value, candidate)
            values[state] = best_value
            delta = max(delta, abs(old_value - best_value))
        sweeps += 1
        if delta < accuracy:
            return sweeps

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

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

בחירת פעולה ופתרון פאזל

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

def get_action(env, state, values, gamma=0.95):
    if state == env.goal:
        return None
    best_action = None
    best_value = float('-inf')
    for action in env.get_actions(state):
        next_state, reward = env(state, action)
        candidate = reward + gamma * values[next_state]
        if candidate > best_value:
            best_value = candidate
            best_action = action
    return best_action

כך מפעילים את התכנון ומשתמשים בתוצאה על מצב המרוחק שני צעדים מהיעד:

env = Puzzle()
values = init_values()
sweeps = value_iteration(env, values)
state = (1, 2, 3, 4, 5, 6, 0, 7, 8)
print(state)

while state != env.goal:
    action = get_action(env, state, values)
    state, reward = env(state, action)
    print(state)

פלט

(1, 2, 3, 4, 5, 6, 0, 7, 8)
(1, 2, 3, 4, 5, 6, 7, 0, 8)
(1, 2, 3, 4, 5, 6, 7, 8, 0)

כל שורה בפלט היא סידור הלוח, לפי סדר השורות, ו־0 מסמן את המשבצת הריקה. המשבצת הריקה זזה פעמיים ימינה, ובסוף הלוח מסודר. הערך של מצב ההתחלה הוא 0.95, משום שהתגמול 1 מתקבל בצעד השני: 0 + 0.95×1. הטבלה שחושבה יכולה לשמש גם מצבי התחלה אחרים; אין מחשבים אותה מחדש עבור כל פאזל.

ההרצה הזאת קצרה, שני מהלכים בלבד, ואפשר לבדוק אותה בעין. כדי לראות שהטבלה באמת פותרת פאזל, ניקח סידור רחוק יותר: הלוח שבתמונה מרוחק 14 מהלכים מהיעד, וזהו המרחק הקצר ביותר האפשרי ממנו. אותה לולאה, עם אותה get_action ואותה טבלה, מסדרת אותו ב־14 מהלכים בדיוק, בלי מהלך מיותר. ערך מצב ההתחלה הוא 0.95¹³≈0.513, כי התגמול 1 מגיע במהלך ה־14.

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

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

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

מה קורה כשהמודל אינו ידוע?

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

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