Вопросы процесса принятия решений Маркова [закрываются]

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

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

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

Прежде чем начать, вернитесь к вопросу и убедитесь, что вы можете уверенно ответить на следующие вопросы.

1. Что такое государство? Сколько существует состояний?
2. Что такое действие? Сколько существует действий?
3. Если вы начинаете в состоянии u и применяете действие a, какова вероятность достижения нового состояния v?

Итак, ответы на вопросы?

1. Состояние - это вектор (x,y). Сетка имеет размер 5 на 5, поэтому существует 25 состояний.
2. Есть четыре возможных действия, {E,N,S,W}
3. Вероятность успешного перехода в соседнее состояние после применения соответствующего действия равна 0.7, вероятность не перехода (остаться в том же состоянии - 0.3). Если предположить, что (0,0) - левая верхняя клетка, а (4,4) - правая нижняя, то в следующей таблице показано небольшое подмножество всех возможных переходов.

Start State Action           Final State    Probability
---------------------------------------------------
(0,0)           E               (0,0)          0.3
(0,0)           E               (1,0)          0.7
(0,0)           E               (2,0)          0
...
(0,0)           E               (0,1)          0
... 
(0,0)           E               (4,4)          0
(0,0)           N               (0,0)          0.3
...
(4,4)           W               (3,4)          0.7
(4,4)           W               (4,4)          0.3

Как мы можем проверить, что это имеет смысл для данной задачи?

1. Проверьте, что таблица имеет соответствующее количество записей. На сетке 5 на 5 есть 25 состояний и 4 действия, поэтому в таблице должно быть 100 записей.
2. Проверьте, что для начальной пары состояние/действие только две записи имеют ненулевую вероятность появления.

Редактирование. Ответ на запрос о вероятностях перехода в целевое состояние. Приведенная ниже нотация предполагает, что

• v - конечное состояние
• u - исходное состояние
• a - действие, где оно не упомянуто, подразумевается, что примененное действие не имеет значения.

P( v=(3,3) | u =(2,3), a=E ) = 0.7
P( v=(3,3) | u =(4,3), a=W ) = 0.7
P( v=(3,3) | u =(3,2), a=N ) = 0.7
P( v=(3,3) | u =(3,4), a=S ) = 0.7
P( v=(3,3) | u =(3,3) ) = 0.3