Искусственный интеллект. Современный подход

Оптимальность в задачах последовательного принятия решений

В примере задачи MDP (см. рис. 17.1) производительность агента определялась по сумме вознаграждений, связанных с посещенными состояниями. Такой выбор показателя производительности нельзя назвать произвольным, но он не является также единственно допустимым. В данном разделе рассматриваются возможные варианты показателей производительности, т.е. варианты способов определения функции полезности по историям пребывания в среде, которые могут записываться как uh ( [ s0 / si,..., sn] ). Этот раздел основан на идеях, изложенных в главе 16, и является довольно формальным; основные его пункты подытожены в конце.
Первый вопрос, на который нужно найти ответ, состоит в том, существует ли конечный горизонт или бесконечный горизонт для принятия решений. Наличие конечного горизонта означает, что есть такое фиксированное время N, после которого все теряет смысл, — так сказать, игра все равно окончена. Таким образом, Uh ( [ s0, Si,..., sN+k] ) = L7h ( [ s0, Si,..., %] ) для всех k>0. Например, предположим, что агент начинает свое движение с квадрата (3,1) в мире с размерами 4x3, показанном на рис. 17.1, а также допустим, что N=3. В таком случае, чтобы получить хоть малейший шанс достичь состояния +1, агент должен направиться непосредственно к нему, и оптимальное действие состоит в том, чтобы двигаться в направлении Up. С другой стороны, если N=100, то запас времени настолько велик, что можно выбрать безопасный маршрут в направлении Left. Поэтому при наличии конечного горизонта оптимальное действие в каждом конкретном состоянии со временем может измениться. Принято считать, что оптимальная стратегия при наличии конечного горизонта является нестационарной. С другой стороны, если нет заданного предела времени, то нет смысла вести себя по-разному в одном и том же состоянии в разное время. Поэтому оптимальное действие зависит только от текущего состояния и оптимальная стратегия является стационарной. Таким образом, стратегии для случая с бесконечным горизонтом проще по сравнению с теми, которые применяются в случае с конечным горизонтом, и в данной главе будет в основном рассматриваться случай с бесконечным горизонтом2. Обратите внимание на то, что понятие "бесконечного горизонта" не обязательно означает, что все последовательности состояний являются бесконечными; оно просто говорит о том, что для их выполнения не устанавливаются фиксированные сроки. В частности, в любой задаче MDP с бесконечным горизонтом могут существовать конечные последовательности состояний, содержащие терминальное состояние.
Следующий вопрос, на который необходимо найти ответ, состоит в том, как рассчитать полезность последовательностей состояний. Мы будем рассматривать задачу поиска ответа на этот вопрос как задачу многоатрибутной теории полезности (см. раздел 16.4), где каждое состояние s рассматривается как атрибут последовательности состояний [s0,si,s2,...]. Чтобы получить простое выражение в терминах атрибутов, необходимо принять своего рода предположение о независимости предпочтений. Наиболее естественное предположение состоит в том, что отношение предпочтения агента между последовательностями состояний является .стационарным. Стационарность предпочтений означает следующее: если две последовательности состояний, [ s0, Si, s2,... ] и [ s0' , Si' , s2',...], начинаются с одного и того же состояния (т.е. s0=s01), то эти две последовательности должны быть упорядочены по предпочтениям таким же образом, как и последовательности [si,s2,...] и [s1* , s21 ,...]. На естественном языке эту мысль можно выразить так, что если вы предпочитаете одно будущее развитие событий, начинающееся завтра, другому развитию событий, то вы должны также предпочесть это будущее развитие событий, если оно начнется сегодня. На первый взгляд, предположение о стационарности выглядит довольно безобидно, но влечет за собой весьма важные последствия: как оказалось, в условиях стационарности существуют только два способа присваивания значений полезности последовательностям, которые описаны ниже.
1. Аддитивные вознаграждения. Полезность последовательности состояний определяется следующим образом:
Uh{ [so, si, s2, ...] ) = R{s0)+R{s1)+R(s2)+...
В мире 4x3, показанном на рис. 17.1, используются аддитивные вознаграждения. Обратите внимание на то, что свойство аддитивности уже было определено неявно в используемых нами функциях стоимости пути для алгоритмов эвристического поиска (см. главу 4).
2. Обесцениваемые вознаграждения, Полезность последовательности состояний определяется с помощью следующего соотношения: Uh( [s0f si, s2, ...] ) = R(s0) +YK(si) +y2R(s2) +...
где у — это коэффициент обесценивания, который представляет собой число от 0 до 1. Коэффициент обесценивания описывает предпочтение агентом текущих вознаграждений перед будущими вознаграждениями. Если коэффициент у близок к 0, вознаграждения, которые должны быть получены в отдаленном будущем, рассматриваются как малозначащие, а если коэффициент Y равен 1, то обесцениваемые вознаграждения полностью эквивалентны аддитивным вознаграждениям, поэтому аддитивные вознаграждения представляют собой частный случай обесцениваемых вознаграждений. По-видимому, обесценивание представляет собой хорошую модель изменения во времени предпочтений и животных, и человека. Коэффициент обесценивания у эквивалентен процентной ставке (1/у) -1.
По причинам, которые вскоре станут очевидными, до конца этой главы предполагается, что используются обесцениваемые вознаграждения, хотя иногда допускается применение значения у=1.
Сделанный нами выбор бесконечных горизонтов становится причиной возникновения определенной проблемы: если среда не содержит терминальное состояние или если агент никогда его не достигает, то все истории пребывания в среде будут иметь бесконечную длину, а полезности, связанные с аддитивными вознаграждениями, в общем случае будут бесконечными. Дело в том, что, безусловно, +°° лучше, чем -<*>, но гораздо сложнее сравнивать две последовательности состояний, притом что обе имеют полезность +°°. Для решения этой проблемы можно применить три описанных ниже подхода, два из которых уже упоминались в этой главе.
1. При наличии обесцениваемых вознаграждений полезность любой бесконечной последовательности является конечной. В действительности, если вознаграждения ограничены значением R и у<1, то можно получить следующее соотношение с использованием стандартной формулы суммы бесконечных геометрических рядов:
2. Если среда содержит терминальные состояния и гарантируется достижение агентом в конечном итоге одного из этих состояний, то нам никогда не придется сравнивать бесконечные последовательности действий. Стратегия, который гарантирует достижение терминального состояния, называется правильной стратегией. При наличии правильных стратегий можно использовать у=1 (т.е. аддитивные вознаграждения). Первые три стратегии, показанные на рис. 17.2, 6~, являются правильными, а четвертая — неправильной. В ней достигается бесконечное суммарное вознаграждение за счет предотвращения попадания в терминальные состояния, притом что вознаграждение за пребывание в нетерминальных состояниях является положительным. Само существование неправильных стратегий в сочетании с использованием аддитивных вознаграждений может стать причиной неудачного завершения стандартных алгоритмов решения задач MDP, поэтому является весомым доводом в пользу применения обесцениваемых вознаграждений.
3. Еще один подход состоит в том, чтобы сравнивать бесконечные последовательности по среднему вознаграждению, получаемому в расчете на каждый временной интервал. Предположим, что с квадратом (1,1) в мире 4x3 связано вознаграждение 0.1, тогда как для других нетерминальных состояний предусмотрено вознаграждение 0.01. В таком случае стратегия, в которой агент предпочтет оставаться в квадрате (1,1), позволит получать более высокое среднее вознаграждение по сравнению с той стратегией, в которой агент находится в каком-то другом квадрате. Среднее вознаграждение представляет собой полезный критерий для некоторых задач, но анализ алгоритмов со средним вознаграждением выходит за рамки данной книги.
Подводя итог, можно сказать, что использование обесцениваемых вознаграждений связано с наименьшими трудностями при оценке последовательностей состояний. Заключительный этап состоит в том, чтобы показать, как осуществляется выбор между стратегиями с учетом того, что каждая конкретная стратегия п вырабатывает не только одну последовательность состояний, но целый ряд возможных последовательностей состояний, притом что каждая из этих последовательностей имеет конкретную вероятность, определяемую моделью перехода для данной среды. Таким образом, стоимость любой стратегии представляет собой ожидаемую сумму полученных обесцениваемых вознаграждений, где это ожидаемое значение вычисляется по всем возможным последовательностям состояний, которые могут возникнуть при осуществлении данной стратегии. Любая оптимальная стратегия п* удовлетворяет следующему соотношению: