Q‑learning

Учиться на вознаграждении

Представьте существо, которое ничего не знает о мире. Оно в некотором состоянии$s$, выбирает действие$a$, получает награду$r$ и попадает в новое состояние $s^{\prime }$. Так по кругу. Цель одна — набрать как можно больше награды за всю жизнь.

Этот цикл «агент ↔ среда» и есть суть обучения с подкреплением (Reinforcement Learning):

Награду будущего мы ценим чуть меньше, чем награду сейчас. Поэтому суммарная отдача с момента $t$ считается с коэффициентом дисконтирования$\gamma \in [0,1]$:

При $\gamma \to 1$ агент дальновиден; при $\gamma \to 0$ — живёт одним мгновением.

Ценность действия: Q(s,a)

Ключевая идея — завести число $Q(s,a)$: «насколько хорошо в состоянии $s$ выбрать действие $a$», если дальше играть наилучшим образом. Знай мы все $Q$, задача решена: в каждом состоянии берём действие с максимальным $Q$.

Но $Q$ неизвестна. Зато у неё есть красивое рекуррентное свойство — она «согласована сама с собой». Ценность действия = немедленная награда плюс дисконтированная ценность лучшего продолжения. Это уравнение Беллмана:

Как учить Q на опыте

Мы не знаем матожидание, но можем подталкивать оценку к наблюдаемому результату после каждого шага. Пожив один переход $(s,a,r,s^{\prime })$, делаем маленький шаг в сторону беллмановской цели:

Выражение в скобках — «ошибка предсказания» (TD-error). $\alpha$ — скорость обучения.

Величина в квадратных скобках — насколько реальность разошлась с ожиданием. Шаг $\alpha \in (0,1]$ говорит, как сильно верить свежему опыту. Повторяя это правило снова и снова, $Q$ сходится к $Q^{\star }$.

Целиком алгоритм — это тот же шаг обновления, завёрнутый в цикл по эпизодам:

Именно этот цикл крутится в интерактивах ниже — по одному эпизоду за нажатие кнопки. Больше ничего в Q-learning нет.

Дилемма исследования — снова

Если всегда брать текущее лучшее действие, агент рискует не найти по-настоящему хороший путь. Простейшее лекарство — $\epsilon$-жадная стратегия: с вероятностью $\epsilon$ берём случайное действие (исследуем), иначе — жадно лучшее по $Q$:

Учим агента игре в камни

Возьмём ту же игру, что и в части про MCTS: куча из 15 камней, за ход берём 1–3, кто взял последний — победил. Теперь состояние — это число камней на ходу агента, действия — «взять 1/2/3», а награда$=+1$ за победу и $-1$ за поражение.

Агент играет против случайного соперника и после каждого хода обновляет $Q$. Ниже — опорный срез Q-таблицы от конца партии до начальной позиции: строка это состояние, столбец — действие, цвет — выученная ценность (красная — плохо, зелёная — хорошо). После начала обучения рамка и звезда отмечают ход с единственной наибольшей оценкой. При равных оценках выделения нет.

Начните с одного эпизода и найдите изменившиеся оценки ближе к концу партии. Затем обучите агента на серии эпизодов и сравните действия в одной строке таблицы. Может ли равенство текущих оценок означать, что действия действительно равноценны?

Прогоните пару сотен эпизодов и посмотрите на столбцы: агент сам, без всякой теории игр, выясняет, какие ходы ведут к победе против случайного соперника — цвета в таблице «прорастают» из выигрышных состояний в проигрышные, ровно как награда $+1$ распространяется назад по уравнению Беллмана.

Мир-сетка: ценность в пространстве

Игра в камни одномерна. Чтобы увидеть, как ценность растекается по состояниям, перейдём к классике RL — gridworld. Агент 🤖 стартует в углу и ищет путь к цели ⚑ (награда $+1$), обходя ловушку ☠ (награда $-1$) и стены. Каждый шаг стоит немного ($-0.02$) — чтобы путь был короче.

Сначала запустите один эпизод и найдите посещённые клетки. Затем добавьте серию эпизодов: как меняются оценки возле цели и у старта? Различайте текущую оценку клетки и действие, которое агент иногда выбирает для исследования.

Сначала стрелки хаотичны, а карта серая — агент блуждает. Но с каждым эпизодом награда цели «протекает» на соседние клетки: сначала загораются клетки рядом с ⚑, потом их соседи, и так до старта. Через сотню-другую эпизодов стрелки складываются в оптимальный маршрут в обход ловушки.

Планирование против обучения

MCTS и Q-learning решают одну задачу — «что делать?» — но с разных сторон. Один думает наперёд под текущую ситуацию, другой помнит опыт всех прошлых ситуаций.

Оба страдают от размера пространства состояний. Q-таблица не влезет для го или шахмат, а MCTS в одиночку слишком поверхностен. Решение оказалось в их союзе:

Сверху — обучение, снизу — планирование. Две стороны одной медали.