ד.9 — TD באיקס עיגול ו־AfterState

המצגת: TD באיקס עיגול (עותק מקומי) · קוד: אימון SARSA · סוכן AfterState

בפרק הקודם למדנו את הרעיון של TD ואת שני האלגוריתמים SARSA ו־Q-learning על נייר: מצב, פעולה, תגמול, מצב הבא. בפרק הזה נחזור לאיקס עיגול ונשאל שאלה מעשית: איך נראה "צעד אחד" במשחק שבו יש יריב? בפרק ד.7 בנינו סוכן מונטה קרלו שמשחק אפיזודה שלמה ולומד רק בסופה. עכשיו נשנה דבר אחד בלבד: מועד העדכון. הסוכן ילמד תוך כדי המשחק, מכל מהלך.

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

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

מה נכלל במעבר אחד?

בפרק הקודם המעבר היה S, A, R, S′, A′. במשחק מול יריב, בין הפעולה שלנו לבין המצב שבו נבחר שוב מסתתר מהלך של O. לכן נגדיר "מעבר אחד" כזוג תורים: התור שלנו ותגובת היריב. נפרק את המעבר לחמישה שלבים, לפי סדרם:

1. במצב state, הסוכן X בוחר action.
2. הסביבה מבצעת את הפעולה ומחזירה after_state ותגמול.
3. אם המשחק נמשך, היריב O בוחר פעולה.
4. הסביבה מבצעת את פעולת O ומחזירה next_state ותגמול.
5. אם המשחק עדיין נמשך, X בוחר next_action.

כך after_state הוא הלוח לפני תגובת היריב, ואילו next_state הוא הלוח שבו X עומד לבחור שוב. אין להחליף בין השניים בעדכון SARSA: ה־S′ של הנוסחה הוא next_state, כי רק בו X חוזר ומחליט. מנקודת המבט של הסוכן, היריב הוא חלק מהסביבה, ותגובתו היא חלק מה"אקראיות" של המעבר.

למשל, בלוח ריק X בוחר במרכז (1,1). ב־after_state יש רק X אחד במרכז. O בוחר בפינה השמאלית התחתונה (2,0), ולכן ב־next_state יש שני סימנים. כעת X יכול לבחור, למשל, (2,2) כפעולתו הבאה. היא נבחרה אך טרם בוצעה.

כשהמשחק נמשך

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

next_action = agent.get_action(next_state, epsilon)
target = reward + gamma * agent.get_Q(next_state, next_action)

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

כשהמשחק מסתיים אחרי הפעולה של X

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

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

כשהמשחק מסתיים אחרי תגובת O

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

O X X
. O .
. . .

אם X בוחר (1,2) ואחריו O בוחר (2,2), היריב משלים אלכסון. התגמול לסוכן X הוא ‎−1. גם כאן אין לבחור פעולה נוספת: יעד העדכון הוא ‎−1, ללא ערך עתידי.

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

קוד אימון SARSA

אחרי שטיפלנו בשלושת המקרים, אפשר לחבר אותם ללולאת אימון אחת. הקוד הבא משתמש ברכיבים מהפרק הקודם: מחלקת המשחק TicTacToe, הסוכן הטבלאי TabularAgent, פונקציית הדעיכה של ε ‏epsilon_at, ופונקציות הדגימה והבדיקה sample_step ו־evaluate. נוספה לסוכן המתודה set_Q(state, action, value), שמציבה את הערך במילון. בתחילת כל אפיזודה בוחרים פעולה אחת. בכל איטרציה לומדים מן המעבר, ואם המשחק נמשך מעבירים קדימה את המצב ואת הפעולה שכבר נבחרה.

import random
from ttt_env import State, TicTacToe
from tabular_agent import TabularAgent, epsilon_at
from ttt_training import sample_step, evaluate

def train(epochs=100000, seed=0, agent_type=TabularAgent):
    env = TicTacToe()
    agent = agent_type(env, seed)
    opponent_rng = random.Random(seed + 1)
    gamma, alpha = 0.9, 0.1
    for epoch in range(epochs):
        epsilon = epsilon_at(epoch)
        state = State()
        action = agent.get_action(state, epsilon)
        while True:
            next_state, reward, done = sample_step(
                env, state, action, opponent_rng)
            if done:
                target = reward
            else:
                next_action = agent.get_action(next_state, epsilon)
                target = reward + gamma * agent.get_Q(next_state, next_action)
            old_value = agent.get_Q(state, action)
            agent.set_Q(state, action, old_value + alpha * (target - old_value))
            if done:
                break
            state, action = next_state, next_action
    return env, agent

נשווה ללולאה של מונטה קרלו מהפרק ד.7: שם קראנו ל־generate_episode ואחר כך ל־update_episode, כלומר קודם שיחקנו הכול ורק אז למדנו. כאן אין רשימת אפיזודה כלל; כל מעבר מעדכן את הטבלה ונשכח. העדכון מתבצע לפני בדיקת break, כך שגם המעבר האחרון מלמד את הסוכן. ענף done אינו קורא ל־get_action, ולכן לא מנסים לבחור מתוך רשימה ריקה במצב סופי. כשהמשחק נמשך, השורה האחרונה שומרת את next_action לצעד הבא, בדיוק כפי שדרש הפסאודו־קוד של SARSA: הפעולה שנכנסה ליעד היא הפעולה שתבוצע.

agent_type מאפשר להשתמש בהמשך בסוכן אחר עם אותן מתודות, בלי לשנות את לולאת האימון. בשלב הזה הוא TabularAgent. הפרמטרים 100,000 אפיזודות, γ=0.9 ו־α=0.1 נלקחו מ־SARSA_Trainer.py בענף solved; הדעיכה המעריכית והיריב האקראי משותפים לדוגמאות הספר.

AfterState — החלק של המודל שכבר ידוע לנו

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

במקום לשמור ערך לכל זוג (state, action), נשמור אותו תחת after_state שנוצר מהזוג הזה. בהגדרה הזאת, V של AfterState הוא הערך של בחירת הפעולה שהביאה אליו:

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

כיצד נחסכות רשומות כפולות?

מה מרוויחים מהמעבר ל־AfterState? התשובה היא שכמה זוגות מצב–פעולה שונים יכולים להוביל לאותו לוח, ואז אפשר ללמוד ערך אחד במקום כמה. נבחן שני מצבים שבשניהם תור X. בראשון X נמצא בשמאל למעלה ו־O במרכז; X בוחר בימין השורה האמצעית. בשני X כבר נמצא בימין השורה האמצעית ו־O במרכז; X בוחר בשמאל למעלה. שני זוגות המצב–פעולה מובילים לאותו לוח:

X . .
. O X
. . .

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

מחברים את AfterState לקוד האימון

היופי בגישה הזאת הוא שלולאת האימון אינה צריכה לדעת דבר על השינוי. היא קוראת ל־get_Q ול־set_Q, ורק הסוכן מחליט מה המפתח שמאחוריהן. כדי להשתמש ב־AfterState, נשנה את המפתח שבאמצעותו הסוכן ניגש לטבלת הערכים. נחליף את אופן הקריאה והכתיבה של הערכים. שאר התנהגות הסוכן, כולל בחירת פעולה ב־ε-greedy, נשארת במחלקת הבסיס TabularAgent בעזרת ירושה:

class AfterStateAgent(TabularAgent):
    def __init__(self, env, seed=0):
        super().__init__(env, seed)
        self.V = {}

    def get_Q(self, state, action):
        after_state, _ = self.env.next_state(state, action)
        return self.V.get(after_state, 0.0)

    def set_Q(self, state, action, value):
        after_state, _ = self.env.next_state(state, action)
        self.V[after_state] = value

המתודה self.env.next_state(state, action) מחשבת את הלוח שייווצר אחרי הפעולה, בלי לבצע אותה במשחק בפועל; זהו החלק של המודל שכן ידוע לנו. כעת הקריאה get_Q(next_state, next_action) בלולאת SARSA יוצרת את ה־AfterState שאחרי הפעולה הבאה של X. היא אינה משתמשת ב־next_state עצמו כמפתח. לפי הגדרת הטבלה החדשה, העדכון בלולאה שקול לעדכון הבא:

במעבר סופי נשאר ענף target = reward, בלי קריאת ערך המשך. AfterState שבו X ניצח יכול ללמוד ערך 1, מפני שהטבלה מייצגת את הפעולה המנצחת ואת התגמול שלה. אין כאן סתירה לערך המשך 0 אחרי סיום משחק: אלה שתי הגדרות שונות של הערך.

שימוש בסוכן לאחר האימון

לבדיקת SARSA רגיל מפעילים train() ולאחריו את evaluate מהפרק הקודם. לאימון עם AfterState משנים רק את סוג הסוכן:

env, agent = train(agent_type=AfterStateAgent)
print(len(agent.V))
print(evaluate(env, agent.get_action, games=1000, seed=100))

בהרצות שבוצעו עם 100,000 אפיזודות אימון, זרע אימון 0 ואותה בדיקה מול יריב אקראי התקבלו:

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

שמרו את קובצי הפרק לצד ttt_env.py, ‏tabular_agent.py ו־ttt_training.py מהפרק הקודם. הפעילו את sarsa_tictactoe.py או את afterstate_tictactoe.py. שתי ההרצות מתמקדות באימון ובבדיקת הסוכן, ללא חלון משחק.

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