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

Question

альтернативный текст http://img693.imageshack.us/img693/724/markov.png

Меня немного смущают некоторые моменты:

1. Что значит сказать, что данное действие будет успешным в 70% случаев?Означает ли это, что каждый раз, когда он пытается выполнить действие А, он в 70% случаев будет выполнять это действие А, а остальные 30% — действие, которое приводит к одному и тому же состоянию, или просто это так, как если бы он делал это всегда? действие А, но только в 30% случаев он его не выполняет?Надеюсь, я ясно выражаюсь :(
2. Как возможно иметь несколько последовательных состояний с одинаковой полезностью?По идее полезность не всегда должна уменьшаться по мере удаления от состояний с вознаграждением?
3. Зная только информацию, которую я дал выше, возможно ли сделать вывод, что такое фактор дисконтирования (гамма)?Если да, то как?
4. Можно ли рассчитать вознаграждение за государства?Как?

Answer 1

Существует шаблон решения большинства проблем 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 — конечное состояние
• ты — исходное состояние
• 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

Answer 2

объявление.1) вероятно дело не в том, что робот должен всегда двигаться, т.е.эти 30% — это «ах, теперь я немного отдохну» или «вообще не было сил двигаться».

Answer 3

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

Рассмотрите окончательную политику/стратегию на Этапе 4.Согласуется ли это с вашей интуицией?