Сокращение числа марковских государств в обучении с подкреплением

Question

Я начал играть с обучением подкреплению (используя книгу Саттона). Я не могу до конца понять, что это парадокс между необходимостью сокращать пространство состояний Маркова и в то же время не делать предположений о том, что важно, а что нет.

Например.В примере с шашками Саттон говорит, что не следует назначать награды за определенные действия в игре, такие как победа противника.Он утверждает, что это может оптимизировать ИИ для взятия фигур, а не для победы в игре.Таким образом, награды должны даваться только за результат, которого вы хотите достичь (например, выиграть игру).

Вопрос 1

Предположим, что (Техасский Холдем) ПокерИИ с марковским состоянием только руки игроков и карт на столе.Это имеет около 52 * 51 * 50 * 49 * 48 * 47 * 46/1 * 2 * 3 * 4 * 5 * 6 * 7 состояний.Теперь предположим, что мы хотим, чтобы ИИ принимал во внимание денежный пул игроков + их ставки.Это сделает марковский подход к пространству состояний «бесконечным числом комбинаций», если предположить, что 8 игроков имеют по 1-200 000 долларов.

Вопрос 2

Одно сокращение состояния-стратегия может заключаться в разделении денег игроков на бедных , средних или богатых .Это серьезно уменьшает наше пространство состояний, однако, откуда мне знать, что a) 3 группы достаточно?б) Каковы пределы дискриминации для каждой группы?

ура,

Answer 1

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

Чтобы ответить на ваши вопросы, 1) производительность даже на начальном уровне в лимите на 8 игроков texas holdem 'намного превосходит современное состояние исследований. Посмотрите текущее исследование "Лучший в мире игрок в компьютерный покер" на http://poker.cs.ualberta.ca/. Тем не менее, вы можете попытаться разделить пространство на произвольные функции, такие как: (player [1] .cash> 1000) 0: 1, ( игрок [1] ​​.cash> 2500) 0: 1 и т. д.

2) Трудно понять, насколько хорошо ваше представление, обычно люди просто запускают его, пока оно не начнет сходиться и не увидят, насколько хорошо оно работает ...

Answer 2

Предложенный подход к сокращению пространства состояний в RL заключается в использовании иерархии действий состояния.Вместо того, чтобы иметь единственную переменную состояния X, вы бы разбили ее на более мелкие переменные, скажем, x1, x2, x3.Затем вы измеряете их частоты перехода и определяете зависимости между ними (например, x1 обычно изменяется, когда x2 = abc).Затем вы можете сформировать политику, объясняющую, как лучше всего переходить с переменной с более быстрым изменением, чтобы изменить переменную с более медленным изменением, чтобы максимизировать вознаграждение.

Этот подход все еще относительно новый, и я незнать о каких-либо публичных реализациях этого.Тем не менее, есть несколько статей, предлагающих возможные реализации.Алгоритм MAXQ предполагает определенную человеком иерархию, тогда как алгоритм HEXQ описывает метод изучения иерархии, а также политики.