TD Learning и Q-Learning

Агент, которому не нужна ни карта мира, ни правила игры. Он просто играет, смотрит, какая награда последовала, и обновляет свою оценку по разнице между двумя последовательными предсказаниями. Эта единственная идея - temporal-difference error - и позволила TD-Gammon достичь уровня лучших игроков в нарды, и движет Q-learning повсюду: от лифтов до аукционов рекламы. Модель среды не требуется.

• **TD-Gammon (IBM, 1992)** - выучил нарды на уровне лучших игроков мира за 1.5 миллиона партий самоигры через TD(lambda), найдя дебюты, которые гроссмейстеры упускали десятилетиями
• **Управление лифтами и светофорами** - Q-learning контроллеры снижают среднее время ожидания, обучаясь на отложенных наградах без явной модели поступления заявок
• **Рекомендательные и рекламные системы** - агенты на базе Q-learning оптимизируют долгосрочное удержание и доход за сессию, а не один следующий клик
• **Робототехника и управление** - SARSA и Q-learning позволяют агентам учить политику прямо из взаимодействия, когда динамика переходов неизвестна

TD-Gammon: нарды без правил

Gerry Tesauro из IBM Research запускает TD-Gammon. Нейросеть с одним скрытым слоем, алгоритм TD(lambda), самоигра: 1.5 миллиона партий против себя. Ноль экспертных знаний, ноль правил игры - только позиция доски на входе и оценка позиции на выходе. Через несколько недель TD-Gammon играет на уровне лучших игроков мира и находит дебютные варианты, которые гроссмейстеры не рассматривали десятилетиями. Первый практический успех TD-обучения в задаче, которую считали слишком сложной для нейросетей. TD-Gammon доказал: агент открывает нетривиальные стратегии через самоигру без единой инструкции от людей. Та же идея - через 23 года - легла в основу AlphaGo Zero.

TD-learning способен превзойти экспертный уровень через чистую самоигру - без правил, без обучителя

Предварительные знания

• Value functions V(s) и Q(s,a)
• Уравнение Беллмана и bootstrapping
• Dynamic programming как model-based baseline, который ослабляет TD
• Exploration vs exploitation и epsilon-greedy

• Bellman Equations
• Dynamic Programming в RL

TD-ошибка и bootstrapping

1992 год. Gerry Tesauro запускает TD-Gammon - нейросеть, которая учится играть в нарды без единого правила, без единого эксперта. Только самоигра: 1.5 миллиона партий, каждая - сигнал обратной связи. Через несколько недель TD-Gammon играет на уровне чемпиона мира. Механизм, который это сделал возможным - **Temporal Difference learning**.

Классические методы оценки (Monte Carlo) ждут конца эпизода. Агент разыгрывает партию до конца, получает финальную награду, потом откатывается назад и пересчитывает оценки. Это честно, но медленно. TD-обучение делает иначе: обновляет оценки **прямо по ходу**, используя следующее состояние как оракул. Это называется bootstrapping - оценка через оценку.

Ключевое число в TD - это **ошибка временной разницы** (TD-error, обозначается $\delta$). Агент находится в состоянии $s$, делает действие, получает награду $r$, попадает в $s'$. Разница между тем, что агент ожидал, и тем, что получилось - это $\delta$.

**Bootstrapping** - обновление оценки через другую оценку. Звучит как порочный круг, но сходится: пока V(s') чуть точнее V(s), информация распространяется. Нейробиологи нашли прямой аналог $\delta$ в дофаминовых нейронах мозга - те же сигналы предсказательной ошибки, только биохимические.

В RLHF (обучение с обратной связью от людей - механизм ChatGPT, Claude, Gemini) critic-сеть, которая оценивает качество ответов, обучается именно через TD-подобные обновления. Каждый раз, когда модель генерирует ответ и получает оценку от reward model - идёт $\delta$-update по всей траектории токенов.

SARSA: on-policy TD-контроль

TD(0) обновляет $V(s)$ - оценку состояний. Но агенту нужно выбирать **действия**. Для этого нужно оценивать пары $(s, a)$, а не просто $s$. Переходим от $V$ к $Q$: функции ценности действия $Q(s, a)$ - сколько суммарной награды принесёт действие $a$ в состоянии $s$ при дальнейшем следовании политике.

**SARSA** - первый алгоритм TD-контроля. Название - акроним из пяти переменных одного перехода: State, Action, Reward, next State, next Action. Именно этот квинтет нужен для каждого обновления.

**On-policy** означает: обучаемся на том, что реально делаем. Если политика осторожная - Q-оценки будут отражать осторожное поведение. Это важно в опасных средах. Робот-манипулятор, обученный SARSA с ε-жадной политикой, учитывает реальный риск случайных действий при разведке.

Главный предел SARSA: оценки Q зависят от текущей политики. Если политика субоптимальна - Q-оценки будут субоптимальны. Нельзя учиться у эксперта, пока сам играешь по-другому. Именно это ограничение снимает следующий алгоритм.

Q-Learning: off-policy прорыв

1989 год. Кристофер Уоткинс публикует диссертацию с алгоритмом, который станет основой DQN, AlphaGo и каждой видеоигровой победы RL. Идея деceptively простая: **разделить политику исследования и политику обучения**. Агент может блуждать как угодно - хоть случайно, хоть по чужим траекториям - а Q-оценки всё равно сойдутся к оптимальным.

Q-learning - off-policy метод. Разница с SARSA в одной строчке формулы, но последствия огромны.

Off-policy означает: можно учиться на чужом опыте. Именно это делает возможным **Experience Replay** в DQN - хранить миллион прошлых переходов в буфере и обучаться на случайных выборках из него. SARSA так не работает: старые переходы собраны другой политикой, их нельзя честно использовать. Q-learning - можно.

**Гарантия сходимости Q-learning**: если каждая пара $(s, a)$ посещается бесконечно часто, $\alpha$ убывает по правилам Роббинса-Монро ($\sum \alpha = \infty$, $\sum \alpha^2 < \infty$) - Q сойдётся к $Q^*$ с вероятностью 1. Это одна из немногих строгих теоретических гарантий в RL.

ε-жадная стратегия и дилемма исследования

Q-learning гарантирует сходимость - при одном условии: каждая пара $(s, a)$ должна посещаться бесконечно часто. Но жадная политика ($\arg\max_a Q(s, a)$) никогда не исследует - всегда берёт то, что кажется лучшим прямо сейчас. Замкнутый круг: недостаточно исследовал, значит Q неточен, значит жадная политика субоптимальна, значит снова не исследуешь нужные области.

**ε-жадная стратегия** - минимальное решение: с вероятностью $\varepsilon$ брать случайное действие, с вероятностью $1-\varepsilon$ брать $\arg\max$. Простая идея, удивительно устойчивая на практике. AlphaGo использует MCTS + ε-жадные rollouts. DQN стартует с $\varepsilon = 1.0$ и линейно снижает до $\varepsilon = 0.1$ за первые миллион шагов.

Альтернативы ε-жадному подходу существуют и активно применяются в production системах. **Softmax (Boltzmann exploration)**: выбор действия пропорционально $\exp(Q(s,a)/T)$, где $T$ - температура. Именно этот механизм - температурный сэмплинг - используется в language models при генерации текста. **UCB (Upper Confidence Bound)**: исследовать состояния, в которых неопределённость высока. Bandit-алгоритмы на UCB управляют A/B-тестами в Netflix и Google.

**Exploration-exploitation tradeoff** - фундаментальная дилемма не только в RL. Venture-капиталист выбирает между эксплуатацией (вкладывать в проверенные индустрии) и исследованием (ставить на новые). Врач - между назначением лучшего известного лечения и участием пациента в клиническом испытании. Математическая структура идентична Thompson Sampling в многоруком бандите.

Ключевые идеи

• **TD-ошибка** $\delta = r + \gamma V(s') - V(s)$ - единица обучения: разница между ожиданием и реальностью на каждом шаге. Тот же сигнал есть в мозге - дофаминовые нейроны кодируют именно его.
• **SARSA** - on-policy: обновляет Q через то действие, которое реально выбрала политика. Консервативен, учитывает реальный риск исследования.
• **Q-learning** - off-policy: обновляет Q через максимум по всем действиям. Может учиться на чужом опыте (experience replay в DQN). Сходится к оптимальной Q* при правильных условиях.
• **ε-жадная стратегия**: $\varepsilon$-вероятность случайного действия, $(1-\varepsilon)$ - жадного. Простейший способ решить exploration-exploitation дилемму - и до сих пор базовый во всех production-системах.

Связанные темы

TD Learning и Q-Learning - мост между классической теорией оптимального управления и современным deep RL:

• Deep Q-Network (DQN) — Q-learning + нейросеть + experience replay + target network
• Policy Gradient — Альтернативный подход без явной Q-функции
• Уравнение Беллмана — Математическая основа TD-обновлений
• RLHF — Reward model + PPO строятся поверх тех же принципов

Вопросы для размышления

• TD-Gammon нашёл нестандартные дебютные ходы в нардах, которые эксперты потом признали сильными. Означает ли это, что самоигра может находить истину, недоступную человеческой интуиции?
• Q-learning гарантирует сходимость к оптимальной политике в таблицах. Но в DQN нейросеть аппроксимирует Q - гарантий уже нет. Как это меняет подход к обучению на практике?
• ε-жадная стратегия делает случайные действия. Если среда опасна (робот, торговый алгоритм) - как балансировать исследование и безопасность?

Связанные уроки

• rl-03 — Уравнение Беллмана - математическое ядро TD-обновления
• rl-05 — Policy gradient - альтернативный подход без Q-таблицы
• rl-07 — DQN = Q-learning + нейросеть вместо таблицы
• rl-17 — RLHF строится поверх policy optimization, корни в TD/Q-learning
• prob-17 — Цепи Маркова - математический фундамент TD-среды
• ml-49-q-learning