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

Я пытаюсь найти оптимальную политику для задачи Марковского процесса принятия решений, указанной на этой диаграмме, используя итерацию значений (через 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)

python dynamic-programming stochastic markov-chains mdptoolbox
person James C    schedule 27.04.2017    source источник

Ответы (2)


arrow_upward
5
arrow_downward

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

person Prune    schedule 27.04.2017

arrow_upward
0
arrow_downward

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

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

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

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

psuedocode для итерации значения

person Robert Silver    schedule 26.07.2020