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

Обновление: лучший способ изучить и практиковать обучение с подкреплением - зайти на http://rl-lab.com

Введение

Использование обучения с подкреплением в игре с нулевой суммой требует более сложных методов, чем стандартная фиктивная игра. Стандартная фиктивная игра используется в играх нормальной формы, в которых не учитывается время. Чтобы применить обучение с подкреплением к играм с нулевой суммой, необходим другой подход. Эта статья основана на статье Йоханнеса Генриха и Дэвида Сильвера Фиктивная игра с самим собой в играх расширенной формы.

Игра с расширенными формами

Игры в нормальной форме моделируются в виде таблицы, в которой действия (называемые стратегиями) каждого игрока представляют собой заголовки строк и столбцов, а содержимое каждой ячейки является результатом стратегии, используемой каждым игроком.

Проблема этой формы в том, что она не фиксирует последовательность или время. По этой причине в Extensive Form Game используются древовидные представления, в которых каждый узел является игроком, а каждое ребро - стратегией, и последовательность может быть четко видна, когда ход идет от узла к узлу.

Обратите внимание, что для каждой игры с расширенной формой мы можем найти игру с нормальной формой, которая дает те же результаты.

Обучение

Обучение направлено на то, чтобы найти, какие стратегии использовать для достижения равновесия по Нэшу, чтобы мы не проиграли (в среднем).
Другой способ сказать то же самое, процесс обучения - это найти вероятности (или распределение вероятностей) использовать каждую стратегию (или действие), чтобы мы не проиграли в среднем.

ε-лучший ответ

В стандартной фиктивной игре каждый игрок будет искать наилучший ответ на ход оппонента.
Наилучший ответ означает стратегию, которая приводит к наилучшей возможной ценности или вознаграждению в текущей ситуации. Считайте R наградой за лучший ответ. Мы определяем ε-лучший ответ как набор ответов, которые приводят к вознаграждению r такое, что r ≥ R-ε .

Обобщенная ослабленная фиктивная игра

Обобщенная ослабленная фиктивная игра - это итерационный процесс вычисления смешанной стратегии ∏ с использованием текущей стратегии и ε-наилучшего ответа bɛ, а также некоторые другие возмущения М.

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

Подробности обобщенной ослабленной фиктивной игры можно найти в статье, написанной Leslie & Collins.

Фиктивная игра в расширенной форме (XFP)

Расширенная форма фиктивной игры использует концепцию обобщенной ослабленной фиктивной игры для итеративного вычисления равновесия по Нэшу, поэтому в игре с нулевой суммой для двух игроков XFP сходится.

Однако есть проблема.
XFP страдает проклятием размерности. На каждой итерации необходимо выполнять вычисления на всех этапах игры. Это приведет к экспоненциальному вычислению.

По этой причине в игру вступает обучение с подкреплением, чтобы создать фиктивную игру с самим собой.

Фиктивная игра с самим собой (FSP)

Рассмотрим игру с расширенной формой. В своей статье Генрих и Сильвер продемонстрировали, что игра с расширенными формами определяется процессом принятия решений Маркова (MDP) и, таким образом, подходит для метода обучения с подкреплением. Мы называем это фиктивной игрой с самим собой (FSP).

Помните, что XFP использует вычисление наилучшего отклика и обновления стратегии, но это вычисление является экспоненциальным. Что делает FSP, так это заменяет эти два вычисления методами машинного обучения, например следующими:

  1. Лучший ответ: FSP приближает лучший ответ, используя метод обучения с подкреплением. Как следует из названия, приближение означает, что лучший ответ не вычисляется, а что-то близкое к нему, что является ε-лучшим ответом.
  2. Обновление стратегии: FSP обновляет среднюю стратегию как контролируемую обучающую задачу, в которой каждый игрок изучает переходную модель своего собственного поведения.

ВАЖНАЯ ИНФОРМАЦИЯ:
Чтобы убедиться, что FSP соответствует обобщенной ослабленной фиктивной игре (помните, что нам необходимо свойство сходимости). Доказано, что выборка данных должна быть такой, чтобы выборка бралась из наилучшего ответа с вероятностью η и текущей стратегии с (1 - η).
Это можно увидеть в GenerateData метод алгоритма ниже:
σ ← (1 - η) π + ηβ

Объяснение алгоритма

  • Эпизоды игры моделируются из стратегий агентов с использованием метода GENERATEDATA.
  • Данные хранятся в виде эпизодов перехода кортежей текущее состояние, действие, следующая награда, следующее состояние.

  • Полученный опыт или данные хранятся в двух типах памяти агента ограниченного размера FIFO:
    - Mʀʟ хранит опыт поведения оппонентов агента. Другими словами, он имитирует «поведение среды», с которым сталкивается агент. Это требует использования алгоритма обучения с подкреплением для изучения наилучших ответов.
    - Msʟ сохраняет собственное поведение агента и используется в контролируемом обучении для обновления стратегии агента.
  • Каждый агент вычисляет приблизительный лучший ответ путем обучения с подкреплением вне политики Mʀʟ.
  • Каждый агент обновляет свою собственную среднюю стратегию, контролируя обучение на основе памяти Msʟ.

Эксперименты

Эти два алгоритма оцениваются в двух параметризованных играх с нулевой суммой и несовершенной информацией. Leduc Hold'em и River Poker.
В игре с нулевой суммой для двух игроков возможность использования профиля стратегии π определяется как δ = R1 + R2
где R1 - это вознаграждение лучший ответ игрока 1 и R2 - это награда за лучший ответ игрока 2.
В идеале при равновесии Нэша δ должно стремиться к нулю.

На рисунке 2 показано, что в покере Leduc Hold’em с 6 и 60 картами XFP явно превзошел FSP.

На рисунке 3 FSP улучшил свой средний профиль стратегии намного быстрее, чем полноразмерный вариант в обоих случаях ривера. В ривер-покере уязвимость FSP составила 0,11 через 30 секунд, тогда как через 300 секунд XFP можно было использовать более чем на 0,26.

Вывод

Генрих и Сильвер утверждают, что XFP, представляющий собой алгоритм фиктивной игры, сохраняет сходимость, гарантированную в играх с фиктивным свойством игры. Однако он страдает проклятием размерности.
FSP - это подход, основанный на выборке, который реализует обобщенную ослабленную фиктивную игру в среде машинного обучения. Остается открытым вопрос о том, может ли быть достигнута гарантированная сходимость с конечным вычислительным бюджетом на итерацию.

Статьи по Теме

Нейронная фиктивная игра с самим собой
Введение в фиктивную игру