Как хеши помогли считать состояния в глубоком обучении с подкреплением

Классическое обучение с подкреплением давно знает рецепт разведки: посчитай, сколько раз агент был в каждом состоянии, и добавляй бонус к награде за редкие состояния. В табличных задачах это доказуемо оптимально. Проблема в том, что в Atari или непрерывном управлении состояний фактически бесконечно много, и наивный счётчик всегда показывает ноль. Работа под названием #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning предложила обходной путь — хешировать состояния в дискретные коды и считать уже коды. Идея звучит примитивно, но на печально известной Montezuma's Revenge она дала результат, сравнимый с куда более сложными методами.

Почему разведка — узкое место

В средах с плотной наградой агент учится почти на любой стратегии: сигнал приходит часто, и достаточно жадно двигаться по градиенту. Но есть класс задач, где награда разрежена — её можно не увидеть за сотни или тысячи шагов. Montezuma's Revenge из набора Atari стала эталоном такой боли: чтобы получить первое очко, нужно взять ключ, пройти по платформам, избежать врагов. Случайный агент почти никогда не соберёт нужную последовательность действий.

Здесь и нужен направленный поиск. Агент должен сам стремиться в те части среды, где он ещё не был, а не ждать, пока награда случайно упадёт с неба. Формально это выражается через бонус исследования, который добавляется к внешней награде.

Счётчик посещений как источник любопытства

В теории для конечного числа состояний бонус задаётся простой формулой: чем меньше раз агент был в состоянии, тем выше добавка. Типичный вид бонуса — величина, обратно пропорциональная корню из числа посещений. Пока состояний немного, счётчик n(s) честно растёт, и агент методично заполняет карту.

В глубоком RL наблюдение — это кадр игры или вектор из непрерывных признаков. Двух одинаковых кадров практически не бывает, поэтому n(s) застревает на нуле или единице. Счётчик перестаёт нести информацию.

Что предложили авторы: хеширование состояний

Ключевой ход — отобразить непрерывное или очень большое пространство состояний в компактный набор дискретных кодов с помощью хеш-функции, а затем вести счётчик уже по кодам. Похожие наблюдения должны попадать в одну корзину, разные — в разные. Тогда счётчик снова начинает работать: он показывает, как часто агент бывал в окрестности, а не в точной точке.

Авторы использовали два подхода к построению хеша.

• Статический хеш (SimHash). Наблюдение проецируется случайной матрицей, а знак каждой координаты даёт бит кода. Метод дешёвый и не требует обучения. Параметр — длина кода: чем он длиннее, тем тоньше различаются состояния.
• Обучаемый хеш через автоэнкодер. Наблюдение прогоняется через автоэнкодер, а бинаризованный скрытый слой служит кодом. Так хеш подстраивается под структуру среды и лучше группирует семантически близкие кадры.

После вычисления кода агент увеличивает соответствующий счётчик и получает бонус, обратный корню из его значения. Дальше это обычный алгоритм — авторы совмещали приём с TRPO поверх политики.

Самое любопытное в работе — не рекорд, а то, что грубый детерминированный хеш без единого шага обучения местами обгоняет тяжёлые нейросетевые модели плотности. Простое решение оказалось неприлично конкурентоспособным.

Как настраивается длина кода

Длина хеша задаёт компромисс. Слишком короткий код — и разные состояния сливаются в одну корзину, агент считает уже исследованным то, что не видел. Слишком длинный — и каждая точка снова получает свою уникальную корзину, счётчик деградирует к нулю. В экспериментах авторы подбирали длину под конкретную среду, и от неё заметно зависел итог.

Результаты на бенчмарках

Метод проверяли на непрерывном управлении (rllab) и на сложных играх Atari с разреженной наградой. Ниже — обобщённая картина того, где хеш-бонус давал прирост. Конкретные числовые очки лучше смотреть в самой работе: они зависят от версии среды и бюджета обучения, и приводить их по памяти как точные значения было бы неверно.

Вывод авторов трезвый: там, где разведка не была проблемой, бонус не помогает и иногда мешает, потому что уводит агента от уже найденной награды. Ценность метода проявляется именно на разреженных задачах.

Место работы в общем ряду методов разведки

К моменту публикации уже существовали более сложные подходы к внутренней мотивации — от моделей плотности состояний до прогнозирования динамики среды. Ценность #Exploration в том, что она вернула в разговор старую табличную идею и показала: её можно масштабировать почти без затрат. Это важный ориентир — прежде чем городить сложную модель любопытства, стоит проверить, не решает ли задачу дешёвый счётчик по хешу.

• Метод легко встроить поверх существующего алгоритма политики.
• Статический хеш не требует обучения и почти не тратит вычислений.
• Главный настраиваемый параметр — длина кода — интуитивно понятен.
• Слабое место — чувствительность к тому, какие признаки наблюдения попадают в хеш: на сырых пикселях группировка хуже, чем на осмысленных признаках.

Что взять на практике

Если вы строите агента для среды с редким сигналом награды, порядок действий такой:

1. Сначала оцените, действительно ли проблема в разведке, а не в самой оптимизации политики.
2. Начните с самого дешёвого варианта — SimHash поверх осмысленных признаков состояния.
3. Переберите длину кода: следите, чтобы счётчики не были поголовно единичными и не сливались в пару корзин.
4. Если статический хеш плохо группирует наблюдения, переходите к обучаемому хешу через автоэнкодер.
5. Сравнивайте не только финальный счёт, но и скорость, с которой агент покрывает новые состояния.

Работа не закрывает тему разведки — на самых злых задачах специализированные методы всё ещё сильнее. Но она задаёт полезную нижнюю планку сложности: простой счётчик по хешу должен быть первой, а не последней попыткой.