بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 60: یادگیری تقویتی ۲ Reinforcement Learning 2

عامل ماز خودش یاد می‌گیرد: یک جدول Q از حدس‌ها می‌سازیم، با قانون Q-learning بعد از هر قدم حدس را درست‌تر می‌کنیم، بین کشف و بهره‌برداری تعادل می‌گذاریم و مسیر یادگرفته را با فلش و turtle می‌کشیم.

در این جلسه یاد می‌گیری

درس

جلسه‌ی قبل سیاست ماز را خودمان نوشتیم. امروز عامل باید خودش پیدایش کند. ایده: یک دفترچه که برای هر خانه و هر عمل یک عدد دارد: «اگر این‌جا این کار را بکنم، از الان تا آخر بازی چقدر پاداش می‌گیرم؟». به این دفترچه جدول Q می‌گویند. اول همه‌ی عددها صفرند، یعنی عامل هیچ چیز نمی‌داند. مثل وقتی تازه به یک مدرسه‌ی جدید رفته‌ای و نمی‌دانی کدام راهرو به بوفه می‌رسد.

با numpy جدول Q یک آرایه‌ی ۱۲ در ۴ است: ۱۲ خانه‌ی ماز (۳ سطر × ۴ ستون) و ۴ عمل. هر خانه‌ی (r, c) را با r * COLS + c به یک شماره تبدیل می‌کنیم تا شماره‌ی سطر جدول شود. Q[s] همه‌ی حدس‌های یک خانه است و np.argmax(Q[s]) بهترین عمل آن خانه.

import numpy as np

MAZE = ["S..#", "#.#.", "...G"]
ROWS, COLS = len(MAZE), len(MAZE[0])
ACTIONS = ["U", "D", "L", "R"]


def index(state):
    return state[0] * COLS + state[1]


Q = np.zeros((ROWS * COLS, 4))
print(Q.shape)             # (12, 4)
print(index((2, 1)))       # 9
Q[9] = [0.5, -1.0, 2.0, 6.2]
print(ACTIONS[int(np.argmax(Q[9]))])   # R

قانون Q-learning به زبان ساده: «حدست را کمی به سمت چیزی ببر که واقعاً اتفاق افتاد، به‌علاوه‌ی بهترین حدس از خانه‌ی بعدی». یعنی هدف = پاداشی که همین الان گرفتی + gamma × بهترین عدد خانه‌ی بعد. فاصله‌ی حدس قبلی تا هدف را حساب می‌کنیم و فقط بخشی از آن (نرخ یادگیری lr) را جلو می‌رویم، همان قدم کوچک گرادیان کاهشی. اگر خانه‌ی بعد هدف بازی باشد، آینده‌ای ندارد و هدف فقط خود پاداش است.

lr, gamma = 0.5, 0.9
old = 0.0          # Q[s, a] before
r = -1             # what really happened: one step
best_next = 4.0    # max(Q[s2]): the best guess from the next cell
target = r + gamma * best_next
new = old + lr * (target - old)
print(round(target, 2), round(new, 2))   # 2.6 1.3

# Q[s, a] += lr * (r + gamma * np.max(Q[s2]) - Q[s, a])

کشف یا بهره‌برداری؟ اگر همیشه غذای محبوبت را سفارش بدهی، هیچ‌وقت نمی‌فهمی غذای بهتری هم در منو هست. اگر همیشه غذای تازه امتحان کنی، خیلی وقت‌ها غذای بد می‌خوری. راه وسط: بیشتر وقت‌ها بهترین را بردار، گاهی (با احتمال epsilon، مثلاً ۲۰٪) یک کار تصادفی بکن. به این اپسیلون-حریصانه (epsilon-greedy) می‌گویند. بدون کشف، عامل اولین راهی را که پیدا کرد تا ابد تکرار می‌کند، حتی اگر بد باشد. (در ماز کوچک ما حدس‌های اول صفرند و هر قدم -1 می‌گیرد، پس کارهای امتحان‌نشده جذاب‌تر به نظر می‌رسند و عامل حتی با epsilon = 0 کمی می‌گردد؛ در بازی‌های بزرگ این کافی نیست.)

import random

epsilon = 0.2


def choose(s):
    if random.random() < epsilon:
        return random.randrange(4)        # explore: a random action
    return int(np.argmax(Q[s]))           # exploit: the best guess so far

حالا همه را کنار هم می‌گذاریم. step این بار سه چیز برمی‌گرداند: خانه‌ی جدید، پاداش و این‌که بازی تمام شد یا نه. هر اپیزود از S شروع می‌شود؛ بعد از هر قدم یک به‌روزرسانی. اپیزود اول عامل ۵۰ قدم سرگردان است، اما از اپیزود ۵۰ به بعد معمولاً در ۵ قدم می‌رسد. گاهی ۶ یا ۷ قدم می‌شود: آن قدم‌های اضافه همان ۲۰٪ کشف است.

START, GOAL = (0, 0), (2, 3)
DELTA = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
lr, gamma, epsilon = 0.5, 0.9, 0.2


def step(state, a):
    r, c = state
    dr, dc = DELTA[ACTIONS[a]]
    nr, nc = r + dr, c + dc
    if not (0 <= nr < ROWS and 0 <= nc < COLS) or MAZE[nr][nc] == "#":
        nr, nc = r, c
    if (nr, nc) == GOAL:
        return (nr, nc), 10, True
    return (nr, nc), -1, False


Q = np.zeros((ROWS * COLS, 4))
random.seed(0)
for episode in range(1, 201):
    state, steps, done = START, 0, False
    while not done and steps < 50:
        s = index(state)
        a = choose(s)
        state, r, done = step(state, a)
        best_next = 0 if done else np.max(Q[index(state)])
        Q[s, a] += lr * (r + gamma * best_next - Q[s, a])
        steps += 1
    if episode in (1, 10, 50, 200):
        print("episode", episode, ":", steps, "steps")

بعد از آموزش، کشف را خاموش می‌کنیم و در هر خانه فقط بهترین عمل جدول را برمی‌داریم: مسیر حریصانه. یک حد ۲۰ قدمی هم می‌گذاریم تا اگر جدول بد یاد گرفته بود، در حلقه‌ی بی‌پایان گیر نکنیم. برای دیدن مسیر، روی یک کپی از ماز در هر خانه‌ی مسیر یک فلش می‌گذاریم: ^ v < >.

state, path = START, []
while state != GOAL and len(path) < 20:
    a = int(np.argmax(Q[index(state)]))
    path.append(ACTIONS[a])
    state, r, done = step(state, a)
print(path)          # ['R', 'D', 'D', 'R', 'R']

ARROWS = {"U": "^", "D": "v", "L": "<", "R": ">"}
grid = [list(row) for row in MAZE]
state = START
for move in path:
    grid[state[0]][state[1]] = ARROWS[move]
    state, r, done = step(state, ACTIONS.index(move))
for row in grid:
    print("".join(row))

با turtle هم مسیر را می‌کشیم: اول ماز را مثل جلسه‌ی قبل با مربع‌ها، بعد یک خط قرمز کلفت از وسط خانه‌ی شروع، خانه به خانه. وسط خانه‌ی (r, c) نقطه‌ی (-60 + c * 40, 40 - r * 40) است.

import turtle

t = turtle.Turtle()
t.speed(0)
COLORS = {"#": "black", "S": "blue", "G": "green", ".": "white"}
for r in range(ROWS):
    for c in range(COLS):
        t.penup()
        t.goto(-80 + c * 40, 60 - r * 40)
        t.pendown()
        t.fillcolor(COLORS[MAZE[r][c]])
        t.begin_fill()
        for side in range(4):
            t.forward(40)
            t.right(90)
        t.end_fill()

t.penup()
t.goto(-60, 40)
t.pendown()
t.pencolor("red")
t.pensize(4)
state = START
for move in path:
    state, r, done = step(state, ACTIONS.index(move))
    t.goto(-60 + state[1] * 40, 40 - state[0] * 40)
t.hideturtle()

یک نکته‌ی جالب از جدول: خانه‌ی (1, 3) سمت راست هیچ‌وقت دیده نشد و همه‌ی عددهایش صفر ماند. عامل فقط چیزی را یاد می‌گیرد که تجربه کرده. برای همین در بازی‌های بزرگ، عامل‌ها میلیون‌ها اپیزود بازی می‌کنند؛ AlphaGo و عامل‌های بازی‌های ویدیویی هم با همین ایده‌ی پاداش ساخته شده‌اند، فقط به جای جدول ۱۲ در ۴ یک شبکه‌ی عصبی بزرگ دارند.

⚠️ دور زدن پاداش (reward hacking): عامل دقیقاً همان چیزی را بیشتر می‌کند که با عدد گفتی، نه چیزی که در ذهنت بود. در یک بازی معروف قایق‌رانی، پژوهشگران برای جمع کردن امتیازهای کنار مسیر پاداش دادند؛ عامل یاد گرفت در یک دایره‌ی کوچک بچرخد و همان امتیازها را بارها بگیرد و هیچ‌وقت مسابقه را تمام نکند! در ماز ما هم اگر به جای -1 برای هر قدم +1 می‌دادیم، بهترین سیاست این بود که هرگز به G نرسد و ۵۰ قدم بچرخد. پاداش باید همان چیزی را بگوید که واقعاً می‌خواهی.

مثال‌های این جلسه

چالش‌ها

  1. One Update by Hand (آسان)
  2. Explore or Exploit (آسان)
  3. The Update Function (متوسط)
  4. Train in the Maze (متوسط)
  5. The Greedy Path (سخت)
  6. Arrows on the Maze (سخت)

بیشتر بخوان

← جلسه‌ی 59: یادگیری تقویتی ۱ جلسه‌ی 61: پروژه: عامل بازی →