ד.4 — תכנון דינמי: Policy Iteration

המצגת: תכנון דינמי (עותק מקומי) · קוד: הסביבה הנתונה · Policy Iteration · מבוך 5×5 · הרצת המדיניות במבוך

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

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

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

משוואת בלמן: צעד אחד וההמשך שלו

בפרק הקודם חישבנו את ערך המצב V כסכום כל התגמולים לאורך המסלול עד סוף המשחק. חישוב כזה יקר: בכל מצב צריך לעקוב אחר מסלול שלם, ובלוח גדול המסלולים ארוכים. נחפש דרך לחשב את הערך צעד אחד קדימה בלבד. נניח שהמדיניות בוחרת במצב s את הפעולה a, ושהמודל הידוע מחזיר מצב חדש s′ ותגמול r. את ערך המצב אפשר לפרק לשני חלקים: התגמול שמתקבל עכשיו, והערך של ההמשך כשהוא מוכפל במקדם ההיוון. למושגי הערך וההיוון ראו פרק המודל.

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

אותו פירוק חל על ערך מצב–פעולה. אם אחרי הפעולה הראשונה ממשיכים לפי המדיניות ובוחרים a′=π(s′), מקבלים:

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

מתחילים ממדיניות נתונה

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

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

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

from gridworld import Action, GOAL

def initial_policy(env):
    policy = {}
    for state in env.states:
        if env.end_of_game(state):
            continue
        actions = env.get_actions(state)
        action = Action.DOWN if Action.DOWN in actions else Action.UP
        if state == (GOAL[0], GOAL[1] - 1):
            action = Action.RIGHT
        policy[state] = action
    return policy

ממשק הסביבה בקוד כבר נתון: env.states מכיל את המצבים, env.get_actions(state) מחזירה פעולות חוקיות, env(state, action) מחזירה מצב חדש ותגמול, ו־env.end_of_game(state) בודקת סיום. פעולות מחוץ לגבולות הלוח אינן נכללות ברשימת הפעולות החוקיות.

Policy Evaluation — מעריכים את המדיניות

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

נעקוב אחר ההתפשטות של הערכים במדיניות ״למטה״ שבנינו. תחילה מתקבל ‎−1 מעל תא ההפסד, ו־1 בשני שכני היעד. לאחר מכן מתפשט 0.9 אל המצבים שמגיעים לשכנים האלה לפי המדיניות, ולבסוף 0.81 לתא הימני העליון. בסיום ההערכה הראשונה מתקבלת:

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

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

def policy_eval(env, policy, values, gamma=0.9, accuracy=0.0001):
    while True:
        delta = 0
        for state in env.states:
            if env.end_of_game(state):
                continue
            old_value = values[state]
            action = policy[state]
            next_state, reward = env(state, action)
            values[state] = reward + gamma * values[next_state]
            delta = max(delta, abs(old_value - values[state]))
        if delta < accuracy:
            return

השורה המרכזית היא values[state] = reward + gamma * values[next_state] — זו משוואת בלמן בדיוק כפי שכתבנו אותה. old_value שומר את המספר שלפני העדכון, ו־delta מודד עד כמה הטבלה עדיין משתנה; הפרמטר accuracy קובע מתי השינוי קטן מספיק כדי לעצור. מצבים סופיים נשארים באפס. העדכון נעשה בטבלה עצמה, ולכן מצב שנבדק בהמשך הסריקה עשוי להשתמש בערך שכבר התעדכן באותה סריקה. אין צורך לחכות לסריקה נוספת כדי להשתמש במידע החדש.

Policy Improvement — משפרים את המדיניות

עכשיו יש לנו טבלת ערכים שמתארת את המדיניות הנוכחית, והיא מגלה לנו היכן המדיניות חלשה: למשל, התא שמעל תא ההפסד יורד היישר אל ‎−1, בעוד שכנו מימין שווה 0.81. השלב השני, שיפור המדיניות — Policy Improvement, מנצל את המידע הזה. כעת נשאל בכל מצב אם פעולה אחרת תיתן תוצאה טובה יותר. לכל פעולה חוקית מחשבים את התגמול המיידי ואת ערך ההמשך. בוחרים פעולה עם הציון הגדול ביותר ומשנים את המדיניות בהתאם. זו בחירה חמדנית — Greedy: בכל מצב לוקחים את הפעולה שנראית הכי טובה לפי הטבלה הנוכחית.

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

def policy_improv(env, policy, values, gamma=0.9):
    stable = True
    for state in env.states:
        if env.end_of_game(state):
            continue
        old_action = policy[state]
        best_action = old_action
        next_state, reward = env(state, old_action)
        best_value = reward + gamma * values[next_state]
        for action in env.get_actions(state):
            next_state, reward = env(state, action)
            candidate = reward + gamma * values[next_state]
            if candidate > best_value + 1e-12:
                best_value = candidate
                best_action = action
        policy[state] = best_action
        if best_action != old_action:
            stable = False
    return stable

הפונקציה מחזירה True אם לא נדרשה החלפה בשום מצב — סימן שהמדיניות יציבה ואי אפשר לשפר אותה עוד לפי הערכים הנוכחיים. כאשר כמה פעולות נותנות אותו ערך, נשמור את הפעולה הקודמת. כך לא נחליף הלוך ושוב פעולות שקולות. התוספת הזעירה 1e-12 מונעת החלפה בגלל הבדלי עיגול מזעריים.

מעריכים שוב ומשפרים שוב

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

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

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

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

Policy Iteration — מחברים את השלבים

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

def policy_iteration(env, gamma=0.9):
    values = {state: 0.0 for state in env.states}
    policy = initial_policy(env)
    while True:
        policy_eval(env, policy, values, gamma)
        if policy_improv(env, policy, values, gamma):
            return policy, values

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

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

הסוכן פותר מבוך 5×5

לוח 4×4 מספיק כדי לעקוב אחר החישוב ביד, אבל בו הדרך ליעד כמעט מתבקשת. כדי לראות שהמדיניות שחושבה באמת "יודעת" ללכת, נפעיל את אותו אלגוריתם בדיוק על לוח גדול יותר: מבוך 5×5 מתוך פרויקט GridWorld של הקורס. שמונה תאים אדומים משמשים כקירות: כניסה לכל אחד מהם מסיימת את המשחק בתגמול ‎−1, כמו התא האדום בלוח הקטן. היעד הירוק בפינה הימנית התחתונה נותן 1, ומתחילים בפינה השמאלית העליונה. כדי להגיע ליעד הסוכן חייב לעקוף את שתי שורות הקירות: ימינה לאורך השורה העליונה, למטה דרך הפתח היחיד, שמאלה לאורך השורה האמצעית, למטה בעמודה השמאלית, ומשם ימינה עד היעד.

הסביבה כתובה באותו ממשק בדיוק: env.states, env.get_actions(state), env.end_of_game(state) והקריאה env(state, action); רק גודל הלוח ורשימת התאים הסופיים השתנו. לכן policy_eval ו־policy_improv מהפרק פועלות עליה ללא שינוי. המדיניות ההתחלתית כאן היא פשוט הפעולה החוקית הראשונה בכל תא. אין צורך לתכנן אותה בחוכמה; האלגוריתם ישפר אותה:

from gridworld_maze import COLS, ROWS, START, GridWorld
from policy_iteration import policy_eval, policy_improv

def first_action_policy(env):
    return {state: env.get_actions(state)[0]
            for state in env.states if not env.end_of_game(state)}

def solve_policy(env, gamma=0.9):
    values = {state: 0.0 for state in env.states}
    policy = first_action_policy(env)
    while True:
        policy_eval(env, policy, values, gamma)
        if policy_improv(env, policy, values, gamma):
            return policy, values

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

def run_policy(env, policy, start):
    state = start
    path = [state]
    while not env.end_of_game(state):
        state, reward = env(state, policy[state])
        path.append(state)
    return path

env = GridWorld()
policy, values = solve_policy(env)
path = run_policy(env, policy, START)
print(f'{len(path) - 1} steps: {path}')

פלט

14 steps: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (2, 1), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]

הסוכן הגיע ליעד ב־14 צעדים, שהם המסלול הקצר ביותר האפשרי, בלי להיכנס לאף תא אדום ובלי צעד מיותר. הקובץ maze_demo.py מדפיס גם את המדיניות ואת טבלת הערכים. הנה המדיניות כחצים; לתאים הסופיים אין פעולה:

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

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

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