Q-learning: off-policy метод на gridworld

Урок разбирает Q-learning и показывает рабочую реализацию на сетке 4x4 прямо в браузере.

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

Формула обновления

Q-learning применяет уравнение Беллмана оптимальности к опыту:

Q(s,a) = Q(s,a) + alpha * [ r + gamma * max_a' Q(s', a') - Q(s,a) ]

Интуиция: мы обновляем оценку действия a в сторону «награда + дисконтированная ценность лучшего, что можно сделать дальше». Ключевое слово — max: мы учитываем лучшее возможное продолжение, даже если на исследовании выбрали другое. Поэтому Q-learning называют off-policy: целевая (оптимальная) политика отличается от поведенческой (epsilon-greedy), которой агент собирает опыт.

Реализация на gridworld 4x4

Сетка 4×4: клетки 0..15, старт в углу 0, цель в углу 15. Каждый шаг стоит −1 (чтобы агент искал короткий путь), достижение цели даёт +10. Действия: вверх/вниз/влево/вправо.

Сетка состояний (клетка = номер):
 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15  <- цель (+10)

import random
random.seed(1)

# Среда: gridworld 4x4. Действия 0=вверх,1=вниз,2=влево,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

for episode in range(2000):
    s = 0
    for _ in range(50):
        if random.random() < eps:
            a = random.randint(0, 3)                     # исследование
        else:
            a = max(range(4), key=lambda x: Q[s][x])     # использование
        ns, reward, done = step(s, a)
        # Q-learning: цель = reward + gamma * max_a' Q(ns, a')
        Q[s][a] += alpha * (reward + gamma * max(Q[ns]) - Q[s][a])
        s = ns
        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("Агент обучился за 2000 эпизодов.")
print("Шагов до цели по жадной политике:", steps)
print("Оптимум для сетки 4x4 из угла в угол:", 6)

Вывод:

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

Агент с нуля, без всякой подсказки о геометрии сетки, нашёл кратчайший путь из 6 шагов — только за счёт наград и формулы Q-learning.

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

В начале Q-таблица заполнена нулями. Награда +10 у цели сначала «прокрашивает» Q соседних с целью клеток, потом — клеток через одну, и так волна высокой ценности расходится назад к старту. Шаговый штраф −1 заставляет агента предпочитать короткие пути. epsilon-greedy гарантирует, что все клетки будут испробованы. При затухающем alpha и достаточном исследовании Q-learning доказуемо сходится к оптимальной Q-функции.

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

• Нет исследования (eps=0). Агент застрянет и не прокрасит дальние состояния — Q так и останется нулевым.
• Только положительные награды без штрафа за шаг. Агенту незачем спешить, и он может бродить вечно. Штраф за шаг или дисконтирование задают «срочность».
• Слишком большой alpha. Q-значения скачут; обычно alpha уменьшают по ходу обучения.

Итоги

• Q-learning обновляет Q в сторону r + gamma·max Q(s', a') — учитывает лучшее будущее действие.
• Он off-policy: учит оптимальную политику независимо от исследующей политики.
• На gridworld агент с нуля находит кратчайший путь, опираясь только на награды.