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

Чтобы попасть туда, у вас есть 4 действия:

  • иди направо
  • идти налево
  • садитесь на метро M1
  • садитесь на метро M2

Чтобы найти наиболее эффективный путь к вашему местоположению, мы создали упрощенную модель мира:

Когда вы идете, это самый безопасный вариант, он имеет вероятность перехода 1,00. Для метро вероятность перехода равна 0,66, потому что вы можете его пропустить. Если вы пропустите метро с вероятностью 0,33, вы пойдете либо вправо, либо влево случайным образом, потому что, выходя из метро, ​​вы путаетесь с улицами.

Есть 3 особых состояния:

  • состояние 15: целевое состояние, в котором мы можем сфотографироваться;
    наша награда за это состояние +20
  • состояние 4: грязное место, где у нас портится настроение;
    наша награда за это состояние - -5
  • состояние 10: место, где мы встречаем старого друга;
    наша награда за это состояние +3

Для каждого другого состояния мы получим вознаграждение (штраф) в размере -0,3, что должно означать, что мы хотим добраться до пункта назначения как можно скорее.

Какие действия лучше всего предпринять для каждого из 21 штата?

Основываясь на данном предположении, мы имеем дело с проблемой, основанной на модели, и мы решили выполнить итерацию значений, чтобы ответить на наш вопрос.

Тогда модель, представленная в коде, будет выглядеть следующим образом:

Для каждого состояния мы также должны определить, в каком направлении и как далеко двигаться:

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

MDP определяется таким образом, что значение каждого состояния зависит только от значений следующих состояний. Итак, MDP — это модель, которая может быть описана только текущим состоянием s_t и его следующими прямыми последующими состояниями s_t+1.

Чтобы представить эту концепцию и ценности государства, мы будем использовать известное уравнение Беллмана:

Уравнение Беллмана утверждает, что значение V для каждого состояния s представляет собой награду за это состояние плюс дисконтированную сумму значений следующих состояний с учетом вероятностей перехода из состояния в следующие состояния, если мы предпримем действие, которое максимизирует наше значение. .

где:

  • гамма дисконта является константой (гиперпараметр)
  • награда дается нашей моделью
  • вероятности перехода задаются нашей моделью (прогулка или метро)

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

Чтобы поместить это в несколько строк кода, это будет выглядеть следующим образом:

Тогда лучшими действиями для каждого состояния в соответствии с итерацией значений будут:

{0: ‘M1’,
1: ‘L’,
2: ‘L’,
3: ‘R’,
4: ‘R’,
5: ‘R’,
6: ‘R’,
7: ‘M1’,
8: ‘L’,
9: ‘R’,
10: ‘R’,
11: ‘R’,
12: ‘R’,
13: ‘R’,
14: ‘R’,
15: ‘S’,
16: ‘L’,
17: ‘L’,
18: ‘L’,
19: ‘R’,
20: ‘M2’}

А с учетом модели это выглядит вполне разумно!