Q-Learning и Deep Q-Network

В 2013 году маленький лондонский стартап DeepMind показал, что один алгоритм может научиться играть в 49 разных игр Atari на сверхчеловеческом уровне - используя только сырые пиксели в качестве входных данных. Google купил эту компанию за 500 миллионов долларов. Алгоритм назывался DQN - Deep Q-Network. Разберём его по частям: от простой таблицы Q-значений до нейросетевой аппроксимации, которая изменила всю область reinforcement learning.

• **Игры и симуляции** - DQN и его варианты играют в Atari, Go, StarCraft II, Dota 2. OpenAI Five обыграл чемпионов мира по Dota 2, используя варианты Q-Learning с experience replay для обучения на тысячах лет игрового опыта в симуляции
• **Управление дата-центрами** - Google использует DQN для оптимизации охлаждения серверов, снизив энергопотребление на 40%. Агент определяет оптимальные настройки кондиционирования, где состояние - температуры и нагрузки, а действия - параметры охлаждения
• **Рекомендательные системы** - Q-Learning применяется для последовательных рекомендаций: состояние - история действий пользователя, действие - какой контент показать следующим. YouTube и Netflix экспериментируют с RL-подходами, максимизируя долгосрочное вовлечение вместо кликов на один шаг

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

• Introduction to Reinforcement Learning

От диссертации до сверхчеловеческого уровня в Atari

У Q-learning необычно чистая история происхождения. В 1989 году Крис Уоткинс представил его в своей кембриджской диссертации 'Learning from Delayed Rewards'. Его прозрение было в том, что агент может выучить оптимальную функцию ценности действий Q* напрямую из опыта, вообще не строя модель среды, многократно подталкивая каждую оценку к награде плюс дисконтированной лучшей следующей ценности. Метод был model-free и off-policy: агент мог выучить оптимальную стратегию, даже ведя себя случайно ради исследования. Алгоритм был изящным, но без доказательства, что он действительно сходится. Этот пробел закрылся в 1992 году, когда Уоткинс и Питер Дайан опубликовали строгое доказательство сходимости, показав, что при мягких условиях Q-значения гарантированно достигают оптимума. Два десятилетия Q-learning оставался в рамках малых табличных задач, ведь таблица не масштабируется на изображения. Прорыв пришёл от DeepMind: их работа 2013 года о Deep Q-Network (DQN), расширенная статьёй в Nature в 2015, заменила таблицу свёрточной нейросетью и добавила experience replay и target network ради устойчивости. DQN научился играть в десятки игр Atari прямо по пикселям, достигнув сверхчеловеческих результатов во многих из них и заново разжёг всю область глубокого обучения с подкреплением.

Q-таблица

В предыдущем уроке мы узнали, что агент получает награды за действия в среде. Но как ему понять, какое действие выбрать в каждом состоянии? Для этого нужно оценить **ценность** каждой пары (состояние, действие). Именно это хранит **Q-таблица** - двумерная таблица, где строки представляют состояния, столбцы - действия, а значения Q(s, a) показывают ожидаемую суммарную награду, если в состоянии s выполнить действие a и далее действовать оптимально.

В начале обучения Q-таблица заполнена нулями - агент ничего не знает о среде. Он начинает **исследовать** (explore), выполняя случайные действия. После каждого перехода (state, action, reward, next_state) агент обновляет соответствующую ячейку таблицы. Постепенно значения Q сходятся к истинным, и агент начинает **использовать** (exploit) накопленные знания, выбирая действие с максимальным Q.

**Epsilon-greedy стратегия - баланс explore vs exploit:** - С вероятностью epsilon: случайное действие (exploration) - С вероятностью 1 - epsilon: действие с максимальным Q (exploitation) Типичная схема: epsilon начинается с 1.0 (100% случайных действий) и постепенно уменьшается до 0.01-0.1. В начале агент исследует среду, в конце - использует выученную стратегию. Без exploration агент может застрять в локальном оптимуме: нашёл одну награду и повторяет те же действия, не зная, что рядом есть награда побольше.

Q-таблица отлично работает для сред с небольшим числом состояний и действий: FrozenLake (16 состояний), Taxi-v3 (500 состояний), простые сеточные миры. Но что если состояний миллиарды? В игре Atari Breakout каждый кадр - это изображение 210 x 160 пикселей с 128 возможными цветами. Количество уникальных состояний: 128^(210*160) - это число настолько большое, что не хватит атомов во Вселенной для хранения такой таблицы. Именно здесь на сцену выходит нейросетевая аппроксимация.

Уравнение Беллмана

Как именно обновляются значения в Q-таблице? За этим стоит **уравнение Беллмана** - фундаментальное рекуррентное соотношение, которое связывает ценность текущего состояния с ценностью следующего. Идея: ценность действия a в состоянии s складывается из немедленной награды r и дисконтированной ценности лучшего действия в следующем состоянии s'. Формально: **Q(s, a) = r + gamma * max_a' Q(s', a')**.

Но мы не знаем истинных Q-значений заранее - мы их **обучаем**. Поэтому используется **temporal difference (TD) update**: на каждом шаге мы сдвигаем текущее значение Q(s, a) в сторону новой оценки. Параметр alpha (learning rate) определяет, насколько сильно каждое обновление меняет таблицу. Формула обновления: **Q(s, a) <- Q(s, a) + alpha * (target - Q(s, a))**, где target = r + gamma * max Q(s', a').

**Условия сходимости Q-Learning:** Q-Learning гарантированно сходится к оптимальным Q-значениям, если: 1. **Каждая пара (s, a) посещается бесконечное число раз** - поэтому нужен exploration (epsilon-greedy) 2. **Learning rate уменьшается со временем**, но не слишком быстро: сумма alpha_t = бесконечность, сумма alpha_t^2 < бесконечность 3. **Среда стационарна** - правила игры не меняются На практике часто используют фиксированный alpha = 0.001-0.1, и Q-Learning сходится достаточно хорошо, хотя без формальных гарантий.

Уравнение Беллмана - это не просто формула обновления. Это **принцип оптимальности**: оптимальная стратегия состоит из оптимальных подстратегий. Если вы знаете оптимальные Q-значения для всех следующих состояний, вы можете вычислить оптимальное Q для текущего состояния. Q-Learning использует этот принцип итеративно: начиная с нулей, каждое обновление приближает таблицу к истинным оптимальным значениям, распространяя информацию о наградах "назад" по цепочке состояний.

Deep Q-Network (DQN)

Q-таблица работает для FrozenLake с 16 состояниями. Но в игре Atari Breakout состояние - это изображение экрана: 210 x 160 пикселей. Хранить Q-значение для каждого уникального кадра в таблице невозможно - таблица должна быть больше, чем число атомов во Вселенной. Решение DeepMind (2013): **заменить таблицу нейросетью**. Вместо явного хранения Q(s, a) для каждого состояния, нейросеть *обучается предсказывать* Q-значения для любого входного состояния. Это и есть **Deep Q-Network (DQN)**.

Ключевое отличие DQN от обычного Q-Learning: нейросеть **обобщает** - похожие состояния получают похожие Q-значения. Если агент научился, что мяч в правом верхнем углу требует движения вправо, он применит это знание и когда мяч будет чуть левее. Q-таблица не умеет обобщать: каждое состояние независимо. Именно способность к обобщению позволила DQN освоить 49 игр Atari, используя одну и ту же архитектуру.

**DeepMind и прорыв DQN:** **2013** - статья "Playing Atari with Deep Reinforcement Learning". Одна нейросеть научилась играть в 7 игр Atari лучше человека. Вход: сырые пиксели. Выход: Q-значения для каждого действия (left, right, fire и др.). **2015** - статья в Nature "Human-level control through deep reinforcement learning". 49 игр Atari, в 29 из них DQN превзошёл профессионального игрока. Google купил DeepMind за 500 млн. Две ключевые инновации, которые сделали обучение стабильным: 1. **Experience replay** - хранение и случайная выборка переходов 2. **Target network** - отдельная сеть для вычисления target-значений

Зачем нужна **target network** - вторая копия нейросети? Представьте: вы обновляете Q(s, a) в сторону target = r + gamma * max Q(s', a'). Но Q(s', a') вычисляет та же самая сеть, которую вы обновляете! Получается, что target постоянно "убегает" - вы гонитесь за целью, которая движется. Это приводит к нестабильности и расходимости обучения. Решение: заморозить копию сети (target network) и обновлять её раз в N шагов. Основная сеть обучается, target network остается фиксированной, давая стабильные target-значения.

Experience Replay

Нейросети обучаются на **мини-батчах** - случайных подмножествах данных. Но в RL данные приходят последовательно: s1->s2->s3->... Если обучать сеть на последовательных переходах, два соседних примера будут сильно коррелированы (state 5 похож на state 6), и сеть будет забывать старый опыт, переобучаясь на последние данные. **Experience replay** решает эту проблему: все переходы (s, a, r, s') сохраняются в буфер памяти, а для обучения из буфера извлекаются **случайные мини-батчи**.

Experience replay дает три ключевых преимущества. Первое: **разрушение корреляции** между последовательными примерами - случайная выборка делает данные i.i.d. (независимые и одинаково распределенные), что требуется для стабильного обучения нейросетей. Второе: **эффективное использование данных** - каждый переход может быть использован для обучения много раз, а не один. Третье: **стабилизация обучения** - сеть видит разнообразный опыт из разных частей среды, а не только текущий регион.

**Prioritized Experience Replay (PER):** Обычный replay buffer выбирает переходы равномерно-случайно. Но некоторые переходы более "информативные" - те, где TD error (разница между предсказанным и фактическим Q) большой. Агент больше узнает из неожиданных событий. **PER** присваивает каждому переходу приоритет, пропорциональный его TD error: - Большой TD error = переход сильно удивил агента = высокий приоритет - Маленький TD error = агент уже хорошо предсказывает = низкий приоритет PER ускоряет обучение DQN примерно в 2 раза на играх Atari. Но требует дополнительной структуры данных (sum tree) для эффективной выборки по приоритетам.

DQN с experience replay и target network стал фундаментом современного deep RL. Но у него есть важное ограничение: DQN работает только с **дискретным пространством действий** - left, right, fire. Для непрерывных действий (поворот руля на 17.3 градуса, мощность мотора 0.73) нужны другие методы: policy gradient и actor-critic алгоритмы, которые мы рассмотрим в следующем уроке. DQN выбирает лучшее действие через argmax по Q-значениям - это невозможно, когда действий бесконечно много.

Итоги

• **Q-таблица:** двумерная таблица Q(s, a), где каждая ячейка хранит ожидаемую суммарную награду за выбор действия a в состоянии s - epsilon-greedy стратегия балансирует exploration и exploitation, а таблица работает для сред с малым числом состояний (FrozenLake, Taxi)
• **Уравнение Беллмана:** Q(s, a) = r + gamma * max Q(s', a') - фундаментальная рекурсия, связывающая ценность текущего действия с немедленной наградой и лучшей ценностью следующего состояния, TD update сдвигает Q-значение в сторону target с шагом alpha
• **Deep Q-Network:** когда состояний слишком много для таблицы (миллиарды пикселей в Atari), нейросеть аппроксимирует Q-функцию и обобщает на новые состояния - target network стабилизирует обучение, фиксируя цели для обновления
• **Experience replay:** буфер хранит переходы (s, a, r, s'), случайная выборка мини-батчей разрушает корреляцию между последовательными данными - именно эти идеи позволили тому самому лондонскому стартапу DeepMind создать алгоритм, который освоил 49 игр Atari и был куплен Google за полмиллиарда долларов

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

Q-Learning находится на пересечении reinforcement learning и deep learning, связывая теорию оптимального управления с нейросетевой аппроксимацией:

• Введение в Reinforcement Learning — Фундамент Q-Learning: концепции agent, environment, state, action, reward, policy, MDP - всё это необходимо для понимания Q-функции и уравнения Беллмана. Q-Learning конкретизирует абстрактную задачу RL до алгоритма обновления таблицы
• Policy Gradient — Альтернативный подход к RL, который решает главное ограничение DQN: вместо Q-значений обучается policy network, напрямую выдающая действия. Работает с непрерывными пространствами действий (робототехника, управление), где argmax по Q невозможен
• Нейронные сети — DQN использует нейросеть как аппроксиматор Q-функции: архитектура (fully connected или CNN), backpropagation, loss function (MSE между Q-предсказанием и target) - все эти концепции из урока нейросетей применяются в DQN
• CNN — В оригинальной архитектуре DQN для Atari вход - пиксели экрана (84x84x4), обрабатываемые свёрточными слоями для извлечения визуальных признаков. CNN позволяет DQN работать с сырыми изображениями вместо инженерных признаков

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

• Q-Learning гарантированно сходится для табличного случая. Но DQN использует нейросеть как аппроксиматор - и эта гарантия пропадает. Какие механизмы (target network, experience replay) помогают стабилизировать обучение DQN, и достаточно ли их?
• Experience replay хранит старые переходы и переиспользует их. Но политика агента меняется со временем - переходы, собранные старой политикой, могут не соответствовать текущей. Это проблема off-policy обучения. Как DQN справляется с ней, и в каких случаях это может стать критичным?
• DQN выбирает действие через argmax - максимальное Q-значение. Но что если два действия имеют Q = 10.0 и Q = 9.99? Агент всегда выберет первое, хотя второе почти так же хорошо. Как это связано с overestimation bias, и какие модификации DQN (Double DQN) решают эту проблему?

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

• ml-48-rl-intro — Q-learning строится на MDP и value-основах
• ml-50-policy-gradient — Value-based против policy-based RL
• ml-25-neural-networks — DQN приближает Q нейросетью
• ml-29-cnn — DQN читает пиксели через CNN
• prob-13-clt — Replay стабилизирует оценки ценности
• rl-06