Должна ли матрица переходов из марковского процесса принятия решений быть стохастической?

Question

Я пытаюсь найти оптимальную политику для задачи процесса принятия решений Маркова, указанной на этой диаграмме, используя Value Iteration (через pymdptoolbox) и NumPy. Но pymdptoolbox говорит, что моя матрица переходов "не стохастическая".

Это из-за массивов с [0, 0, 0, 0]? Некоторые переходы невозможны, например, из состояния 1 в состояние 3. Как мне представить эти невозможные переходы, если не с нулями?

Мой код:

import mdptoolbox 
import numpy as np

transitions = np.array([
#action1
    [
            [0.2, 0.8, 0, 0], #s1
            [0, 0, 0, 0], #s2
            [0, 0, 0, 0], #s3
            [0, 0, 0.9, 0.1] #s4
    ],

#action2
    [
            [0.2, 0, 0, 0.8], #s1
            [0, 0.2, 0.8, 0], #s2
            [0, 0, 0, 0], #s3
            [0, 0, 0, 0] #s4
    ],

#action3
    [
            [0, 0, 0, 0], #s1
            [0.8, 0.2, 0, 0], #s2
            [0, 0, 0, 1], #s3
            [0, 0, 0, 0] #s4
    ],

#action4
        [
                [0.8, 0, 0, 0.2], #s1
                [0, 0, 0, 0], #s2
                [0, 1, 0, 0], #s3
                [0, 0, 0, 0] #s4
        ]
])

rewards = np.array([
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [1, 1, 1, 1],
        [0, 0, 0, 0]
        ])

vi = mdptoolbox.mdp.ValueIteration(transitions, rewards, 0.4)

Answer 1

Проблема в том, что вы использовали все 0 значений для представления недоступного состояния. Вы должны иметь общую вероятность 1 в каждой строке. Поскольку состояние недоступно, не имеет значения, как вы это сделаете - поместите "1" в первый столбец, распределяйте значения равномерно, в зависимости от ваших предпочтений. Когда я сталкиваюсь с этой проблемой, я просто использую "1" на главной диагонали: пусть невозможное состояние будет стоком.

Answer 2

У меня недостаточно репутации, чтобы прокомментировать ответ, но я хотел бы подробнее рассказать об ответе Prune. В настоящее время выполняю упражнение, сравнивающее результаты итерации значений набора инструментов mdp с результатами нашей собственной реализации алгоритма на python. Я скажу, что я не совсем уверен, что вы имеете в виду под сливом Prune, поэтому я могу в некотором роде повторить ваш ответ и, если да, отредактировать / пометить мой комментарий для удаления все в порядке.

Я в основном следую твоему совету. Однако мой одноклассник внес хороший вклад, который, я думаю, действительно помог. В основном, скажем, у вас есть три состояния: state1, state2 и state 3. Кроме того, у вас есть матрица перехода для данного действия,3x3 с состояниями 1,2,3 в виде строк и вероятностью перехода в состояния 1,2.,3 в столбцах (таким образом, ячейка [1,2] будет означать вероятность перехода в состояние 2 при выполнении действия из состояния 1. Если бы у вас были все 1 на диагонали, как предложил Prune, у вас был бы 100% шанс остаться в состоянии, если вы предприняли действие, независимо от того, в каком состоянии вы находитесь.

Чтобы заставить это работать с mdptoolbox и быть стохастическим, вы хотите, чтобы все строки суммировались до 1, как сказал Прун. Однако я не думаю, что вы можете произвольно выбирать, в какой столбец вы можете поместить "1" в строку со всеми нулями. Я думаю, что для того, чтобы программа работала последовательно и точно, вам необходимо убедиться, что в этой строке всех нулей (т.е. для состояния s) вы помещаете 1 в ячейку, соответствующую переходу обратно в то же состояние (т.е. [s,s] =1). По сути, это было бы то же самое, что поместить его в правильную "диагональную" позицию для данной строки. Кроме того, убедитесь, что вознаграждение за это действие (reward[s,s]) равно 0. По сути, это означает, что если вы предпримете интересное невозможное действие в состоянии s, у вас есть 100% шанс остаться в том же состоянии. без награды.

Этот ответ с моей стороны довольно наивен, хотя я скажу, что просмотрел руководство и исходный код, пытаясь найти решение (вот ссылка на руководство). Я чувствую себя достаточно уверенно в этом ответе, чтобы опубликовать его, потому что я закодировал реализацию итерации значений, которая не зависит от совершенно стохастической матрицы, и получил те же оптимальные политики и значения, которые были у меня, когда я следовал методу, описанному выше для итерации значений mdptoolbox. Более того, когда я произвольно выбирал столбцы, чтобы ввести "1" и сделать матрицу стохастической, я не получил согласованных результатов, и ни один из них не соответствовал ручной реализации алгоритма. Для справки вот псевдо-код, на который я ссылался для итерации значений. Если я делаю что-то не так, меня зовут!