Всегда ли оптимальная политика стохастична, если среда также стохастична?

10

Является ли оптимальная политика всегда стохастической (то есть, карта от состояний к распределению вероятности по действиям), если среда также стохастическая?

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

нбро
источник
Вот связанный вопрос: mathoverflow.net/q/44677 .
nbro

Ответы:

6

Является ли оптимальная политика всегда стохастической (то есть, карта от состояний к распределению вероятности по действиям), если среда также стохастическая?

Нет.

Оптимальная политика обычно является детерминированной, если:

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

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

Интуитивно понятно, что если среда является детерминированной (то есть, если агент находится в состоянии 𝑠 и выполняет действие 𝑎, то следующее состояние always ′ всегда одинаково, независимо от того, какой шаг по времени), тогда оптимальная политика также должна быть детерминированной (то есть это должна быть карта от состояний к действиям, а не к распределению вероятностей по действиям).

Это кажется разумным, но вы можете развить эту интуицию с помощью любого метода, основанного на функции значения:

Если вы нашли функцию оптимального значения, то действовать жадно по отношению к ней - оптимальная политика.

Вышеприведенное утверждение является просто естественным языком переформулировки уравнения оптимальности Беллмана:

v(s)=maxar,sp(r,s|s,a)(r+γv(s))

maxa

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

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

Нил Слэйтер
источник
1
«Возможно в такой среде, что никакая стохастическая политика не является оптимальной», вы имеете в виду детерминированную политику?
nbro
2
@nbro: Нет, я действительно имею в виду, что нет оптимальной стохастической политики. Это обычно так. Подумайте, например, о простом лабиринте. Если оптимальное детерминированное решение - это единственный путь от начала до конца, добавление к нему любой случайности сделает политику строго хуже. Это не изменится, если окружающая среда добавляет случайный шум (например, движения иногда терпят неудачу)
Нил Слэйтер
2
Теперь я понимаю. Вы говорите, что всегда есть детерминированная политика, тогда политика, которая является стохастической и основана на детерминированной политике, вероятно, будет хуже, чем оптимальная детерминированная политика.
nbro
1
@nbro: Да, вот и все.
Нил Слэйтер
5

Я бы сказал нет.

npiin

pi

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

Адриен Форбу
источник
pipii
2
@nbro: Это определенно в ожидании, которое является то, что максимизирует оптимальная политика. Политики не пытаются угадать генераторы случайных чисел, что считается невозможным (если это было возможно из-за некоторого внутреннего состояния системы, вы должны либо добавить это внутреннее состояние в модель, либо рассматривать как POMDP)
Нейл Слейтер
@NeilSlater Хорошо. Но изменится ли заключение, если время конечно? Если у вас есть ограниченное количество времени для игры, то ожидание, я полагаю, также должно учитывать доступное время для игры.
nbro
2
@nbro: Это может изменить ваши решения, но это не совсем оптимальная политика. Оптимальная политика в отношении оружия бандитов по-прежнему детерминистична в отношении использования лучшего оружия, но вы этого не знаете. Это о разведке против эксплуатации. Вы могли бы сформулировать это как наличие «оптимальной политики для изучения проблемы бандитов», возможно. Не терминология, используемая, например, в Sutton & Barto, но, возможно, некоторые участники говорят, что я не знаю. , ,
Нил Слэйтер
1
Среда содержит только одно состояние, в котором вы снова и снова сталкиваетесь с одним и тем же решением: какую руку мне выбрать?
Адриен Форбу
0

Я думаю о вероятностном ландшафте, в котором вы окажетесь актером, с различными неизвестными пиками и впадинами. Хороший детерминистический подход всегда может привести вас к ближайшему локальному оптимуму, но не обязательно к глобальному оптимуму. Чтобы найти глобальный оптимум, что-то вроде алгоритма MCMC позволило бы стохастически принять временно худший результат, чтобы вырваться из локального оптимума и найти глобальный оптимум. Моя интуиция заключается в том, что в стохастической среде это также будет правдой.

Джонатан Мур
источник