Марковский процесс принятия решений: одно и то же действие, ведущее к разным состояниям

Question

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

Если мы предположим для простоты однопользовательскую систему, то состояния выглядят как k-кортежи (x1, x2, .. , xk), где последний элемент xk представляет собой последний элемент, который был приобретен пользователем. Например, предположим, что наше текущее состояние равно (x1, x2, x3), что означает, что пользователь приобрел x1, затем x2, затем x3, в хронологическом порядке. Теперь, если он покупает x4, новое состояние будет (x2, x3, x4).

Теперь, что предлагает бумага, заключается в том, что эти переходы состояния инициируются действиями, где действие «рекомендует пользователю x_i». но проблема в том, что такое действие может привести к нескольким состояниям.

Например, если наше текущее состояние (x1, x2, x3), и действие «рекомендовать x4» к пользователю, то возможный результат может быть один из двух:

пользователь принимает рекомендацию х4, и новое состояние будет (x2, x3, x4)
пользователь игнорирует рекомендацию x4 (т.е. покупает что-то еще) и новое состояние будет любое состояние (x2, x3, xi) где хи! = x4

Мой вопрос, действительно MDP фактически поддерживает те же действия запускающего два или более различных состояния ?

ОБНОВЛЕНИЕ. Я думаю, что действия должны быть сформулированы так: «получает рекомендацию пункта x_i и принимает его» и «получает рекомендацию пункта x_i и отклоняет его», а не просто «получает рекомендацию по пункту x_i»

Answer 1

На основании this Wikipedia article, да, это делает.

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

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

Answer 2

Несомненно, это называется рандомизированной политикой. Если вы хотите оценить вознаграждение определенной политики, вы должны принять решение о распределении вероятностей рандомизированных действий.

Возможна следующая ссылка: Путерман, Мартин Л. Марков Процессы принятия решений: дискретное стохастическое динамическое программирование. John Wiley Sons &, 2014.

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