Спецификацию вероятностей результатов каждого действия в каждом возможном состоянии принято называть моделью перехода (или просто "моделью", если не может возникнуть путаница). Для обозначения вероятности достижения состояния s', если в состоянии s было выполнено действие а, будет применяться запись . Предполагается, что эти переходы являются марковскими в том смысле, какой указан в главе 15, т.е. что вероятность достижения состояния s' из s зависит только от s, а не от истории пребывания в предыдущих состояниях. На данный момент запись T(s, a, s' ) может рассматриваться как большая трехмерная таблица, содержащая вероятности. В дальнейшем, в разделе 17.5, будет показано, что модель перехода может быть представлена как динамическая байесовская сеть, точно так же, как и в главе 15.

В завершение этого определения среды задачи необходимо сформулировать функцию полезности для агента. Поскольку эта задача принятия решений является последовательной, функция полезности должна зависеть от последовательности состояний (от истории пребывания в среде), а не от отдельного состояния. Ниже в этом разделе будет приведено описание того, как такие функции полезности могут быть определены в целом, а на данный момент просто примем предположение, что в каждом состоянии s агент получает вознаграждение R( s), которое может быть положительным или отрицательным, но должно быть ограниченным. В данном конкретном примере вознаграждение равно -0.04 во всех состояниях, кроме конечных (с которыми связаны вознаграждения +1 и -1). Полезность, связанная с историей пребывания в среде (на данный момент), рассматривается как сумма полученных вознаграждений. Например, если агент достиг состояния +1 после 10 шагов, суммарная полезность его действий будет равна 0.6. Отрицательное вознаграждение -0.04 побуждает агента быстрее достичь квадрата (4,3), поэтому данная среда представляет собой стохастическое обобщение вариантов среды, которые рассматривались в задачах поиска в главе 3. Еще один способ описать эту игровую ситуацию состоит в том, что агенту "не нравится" находиться в этой среде, поэтому он стремится выйти из игры как можно быстрее.

Такая спецификация задачи последовательного принятия решений для полностью наблюдаемой среды с марковской моделью перехода и дополнительными вознаграждениями называется спецификацией марковского процесса принятия решений, или сокращенно MDP (Markov Decision Process). Любая задача MDP определяется тремя перечисленными ниже компонентами.

•    Начальное состояние — S0.

•    Модель перехода — T(s,a, s' ).

•    Функция вознаграждения — R(s).