SARSA: on-policy метод

Урок разбирает SARSA и сравнивает её с Q-learning на одной и той же сетке.

SARSA — это TD-метод, который обновляет Q в сторону награды плюс ценности реально выбранного следующего действия (а не лучшего). Он on-policy: учит ту самую политику, которой действует.

Откуда название

SARSA — это аббревиатура из пяти элементов одного обновления: State, Action, Reward, next State, next Action — (s, a, r, s', a'). В отличие от Q-learning, в формуле фигурирует a' — действие, которое агент реально выберет в s' по своей политике, а не лучшее.

Q-learning (off-policy): Q(s,a) += alpha*[ r + gamma * max_a' Q(s',a') - Q(s,a) ]
SARSA      (on-policy):  Q(s,a) += alpha*[ r + gamma *        Q(s',a') - Q(s,a) ]
                                                          ^ реально выбранное a'

On-policy против off-policy

Разница тонкая, но важная. Q-learning учит оптимальную политику, «представляя», что дальше будет действовать жадно. SARSA учитывает, что агент продолжит исследовать (иногда делать случайные ходы), и потому оценивает реальную, исследующую политику. Из-за этого SARSA осторожнее: рядом с обрывом она учитывает риск случайно туда упасть и держится подальше, тогда как Q-learning смело идёт по краю, рассчитывая на жадные ходы.

Реализация на том же gridworld

import random
random.seed(3)

def step(s, a):
    r, c = divmod(s, 4)
    if a == 0:   r = max(0, r - 1)
    elif a == 1: r = min(3, r + 1)
    elif a == 2: c = max(0, c - 1)
    elif a == 3: c = min(3, c + 1)
    ns = r * 4 + c
    if ns == 15:
        return ns, 10.0, True
    return ns, -1.0, False

Q = [[0.0] * 4 for _ in range(16)]
alpha, gamma, eps = 0.5, 0.9, 0.2

def pick(s):
    if random.random() < eps:
        return random.randint(0, 3)
    return max(range(4), key=lambda x: Q[s][x])

for episode in range(2000):
    s = 0
    a = pick(s)
    for _ in range(50):
        ns, reward, done = step(s, a)
        na = pick(ns)                 # реально выбираем следующее действие
        # SARSA использует Q(ns, na), а не max
        Q[s][a] += alpha * (reward + gamma * Q[ns][na] - Q[s][a])
        s, a = ns, na
        if done:
            break

s, steps = 0, 0
for _ in range(30):
    a = max(range(4), key=lambda x: Q[s][x])
    s, _, done = step(s, a)
    steps += 1
    if done:
        break

print("SARSA обучился за 2000 эпизодов.")
print("Шагов до цели по жадной политике:", steps)

Вывод:

SARSA обучился за 2000 эпизодов.
Шагов до цели по жадной политике: 6

На безопасной сетке SARSA тоже находит кратчайший путь. Разница с Q-learning ярко проявляется в средах с «обрывами», где цена случайной ошибки высока.

Как работает под капотом

Поскольку SARSA оценивает текущую политику, при затухании epsilon до нуля она сходится к той же оптимальной политике, что и Q-learning. Но в процессе обучения, при ненулевом epsilon, SARSA даёт более «безопасную» промежуточную политику. Классический пример — задача Cliff Walking: Q-learning выучивает оптимальный путь вдоль обрыва, но в обучении часто падает; SARSA выбирает чуть длиннее, зато безопаснее.

Частые ошибки

• Брать max вместо Q(s',a'). Это превращает SARSA обратно в Q-learning — теряется on-policy свойство.
• Выбирать a' заново при обновлении. Нужно использовать ровно то действие, которым агент пойдёт дальше, иначе нарушается согласованность.
• Ждать, что SARSA всегда «лучше». Она безопаснее в процессе, но Q-learning часто быстрее находит оптимальную политику в безопасных средах.

Итоги

• SARSA обновляет Q по реально выбранному следующему действию a', а не по максимуму.
• Это on-policy метод: он учит ту политику, которой действует, и потому осторожнее.
• В безопасных средах результат близок к Q-learning; различие видно у «обрывов».