Reinforcement Learning без временных различий: новый подход «разделяй и властвуй»
Исследователи из Berkeley AI Research предложили альтернативу традиционному обучению с подкреплением на основе temporal difference (TD). Новый подход использует принцип «разделяй и властвуй», разбивая траекторию на сегменты и комбинируя их значения. Это позволяет логарифмически (а не линейно) сокращать ошибки обучения и масштабироваться на задачи с длинным горизонтом планирования, где классический Q-learning буксует.
Если этот подход действительно масштабируется, мы получим прорыв в off-policy RL для роботики, диалоговых систем, здравоохранения — всюду, где данные дороги, а задачи имеют длинный горизонт. Это может решить проблему, которую Q-learning не мог решить десятилетиями.
Проблема классического подхода
В reinforcement learning существует фундаментальная проблема масштабирования. Традиционные методы off-policy RL используют temporal difference (TD) learning — обновление Q-функции по правилу Беллмана:
Q(s, a) ← r + γ max Q(s', a')
Проблема в том, что ошибки в оценке следующего состояния Q(s', a') через бутстрэппинг распространяются на текущее Q(s, a), и эти ошибки накапливаются на всём горизонте задачи. Чем длиннее эпизод, тем хуже работает Q-learning.
Существующие костыли
Для борьбы с этим применяют n-step TD learning — используют реальные награды для первых n шагов, а дальше бутстрэп:
Q(s_t, a_t) ← Σ γ^i r_{t+i} + γ^n max Q(s_{t+n}, a')
Это уменьшает число рекурсий Беллмана в n раз, но фундаментально проблему не решает — только сокращает константу. При больших n растёт дисперсия и субоптимальность, приходится вручную подбирать n под каждую задачу.
Третья парадигма: divide and conquer
Берклиевские исследователи предлагают радикально другой подход: разбивать траекторию на две равные части и комбинировать их значения. Это логарифмически сокращает число рекурсий (не линейно!), не требует гиперпараметра n и теоретически не страдает от высокой дисперсии.
Для goal-conditioned RL (когда агент учится достигать любое состояние из любого) используется «транзитивное» правило Беллмана на основе неравенства треугольника:
V(s, g) ← max_w V(s, w) · V(w, g)
Интуиция: ценность достижения цели g из s обновляется через две "меньшие" ценности — от s до промежуточной точки w и от w до g. Это именно divide and conquer для функций ценности.
Практические результаты
В недавней работе команда впервые (насколько им известно) смогла масштабировать divide-and-conquer value learning на сложные задачи в классе goal-conditioned RL. Это первый шаг к созданию по-настоящему масштабируемого off-policy RL для задач с длинным горизонтом.
Ключевые выводы
- TD learning накапливает ошибки линейно по горизонту задачи — это фундаментальная проблема масштабирования
- N-step TD — полумера: сокращает ошибки только на константу и требует ручной настройки
- Divide and conquer может сокращать ошибки логарифмически через разбиение траектории пополам
- Для goal-conditioned RL существует естественная структура divide-and-conquer через неравенство треугольника
- Это первая работа, показавшая практическую масштабируемость такого подхода на сложных задачах
Автор: Артём Ковалёв · Источник: bair.berkeley.edu
**Честно говоря, это один из тех моментов, когда думаешь: «Чёрт, а почему никто раньше не додумался?»** Идея divide and conquer настолько очевидна в теории алгоритмов, что странно, как долго она не проникала в RL. Temporal difference — это как пузырьковая сортировка: работает, всем привычно, но масштабируется херово. А тут — mergesort для value learning.
**Но осторожно с эйфорией.** Во-первых, работа фокусируется на goal-conditioned RL — это важный, но узкий класс задач. Во-вторых, авторы сами не скрывают, что это «первая работа, которая смогла масштабировать» — значит, дальше могут быть подводные камни. В-третьих, нет сравнения с современными on-policy методами типа PPO на тех же задачах. Но даже если это окажется нишевым инструментом для специфичных сценариев (роботика с дорогими данными, например) — уже победа. Следим за продолжением.
Комментарии