TD-обучение: временные различия

Урок разбирает TD-обучение — способ обновлять ценность сразу, не дожидаясь конца эпизода.

TD-обучение (temporal difference) обновляет оценку ценности на каждом шаге, используя награду и уже имеющуюся оценку следующего состояния, без ожидания конца эпизода.

Лучшее от двух миров

TD объединяет идеи Монте-Карло и динамического программирования. Как MC, он учится на опыте, без модели среды. Как value iteration, он использует уравнение Беллмана — обновляет оценку на основе оценки следующего состояния. Этот приём называют бутстрэппингом: оценку улучшают через другую оценку, а не только через настоящий итоговый результат.

TD-ошибка — двигатель обучения

Сердце метода — TD-ошибка: разница между «тем, что мы думали» и «уточнённой оценкой после одного шага».

TD-ошибка = r + gamma * V(s') - V(s)
новое V(s) = V(s) + alpha * TD-ошибка

Если после действия мир оказался лучше ожиданий (TD-ошибка положительна) — поднимаем оценку состояния; если хуже — опускаем. alpha — скорость обучения (как быстро доверяем новой информации).

# TD(0): оцениваем V(s) по ходу. Цепочка 0..4, цель=4, шаг=-0.1, политика "вправо".
gamma, alpha = 0.9, 0.1
V = {s: 0.0 for s in range(5)}

for episode in range(300):
    s = 0
    while s != 4:
        ns = s + 1
        reward = 1.0 if ns == 4 else -0.1
        # TD-обновление: V(s) += alpha * (r + gamma*V(s') - V(s))
        V[s] += alpha * (reward + gamma * V[ns] - V[s])
        s = ns

for s in range(4):
    print("V(", s, ") =", round(V[s], 2))

Вывод:

V( 0 ) = 0.46
V( 1 ) = 0.62
V( 2 ) = 0.8
V( 3 ) = 1.0

Оценки совпали с тем, что давал Монте-Карло, но TD обновлял V на каждом шаге, ни разу не дожидаясь конца, чтобы посчитать полный возврат.

TD против Монте-Карло

	Монте-Карло	TD
Когда обновляет	в конце эпизода	на каждом шаге
Нужен конец эпизода	да	нет
Дисперсия / смещение	высокая дисперсия, без смещения	ниже дисперсия, но смещение

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

Бутстрэппинг — это и сила, и слабость TD. Сила: обучение идёт онлайн, по одному шагу, и применимо к непрерывным задачам. Слабость: оценка V(s') сама неточна, поэтому TD на старте смещён. Но по мере обучения оценки уточняются, и метод сходится. Q-learning и SARSA — это TD, применённый к Q-функции вместо V.

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

Слишком большой alpha. Оценки скачут и не стабилизируются; слишком маленький — обучение ползёт.
Считать TD точным с первого шага. Бутстрэппинг вносит смещение, которое уходит только со временем.
Путать TD-ошибку и награду. Награда — часть TD-ошибки, но не вся: ошибка ещё учитывает разницу оценок состояний.

Итоги

TD обновляет ценность на каждом шаге по TD-ошибке r + gamma·V(s') − V(s).
Бутстрэппинг: оценка улучшается через другую оценку, без ожидания конца эпизода.
TD — основа Q-learning и SARSA; компромисс между MC и динамическим программированием.