Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 224
Текст из файла (страница 224)
По этой причине задачи МГ)Р изучаются в нескольких научных областях, включая искусственный интеллект, исследование операций, экономику и теорию управления. Для вычисления оптимальных стратегий были предложены десятки алгоритмов. В разделах 17.2 и ! 7.3 описываются два наиболее важных семейства алгоритмов. Но вначале мы должны завершить начатое исследование полезностей и стратегий для задач последовательного принятия решений.
Оптимальность в задачах последовательного принятия решений В примере задачи МОР (см. рис. 17.1) производительность агента определялась по сумме вознаграждений, связанных с посешенными состояниями. Такой выбор показателя производительности нельзя назвать произвольным, но он не является также единственно допустимым. В данном разделе рассматриваются возможные варианты показателей производительности, т.е. варианты способов определения функции полезности по историям пребывания в среде, которые могут записываться КаК С)Ь)1я,, Э,, ..., Сь] ) .
ЭтОт раэдЕЛ ОСНОВаН На ИдЕяХ, ИЗЛОЖЕННЫХ В ГЛаВЕ 16, И яВ- ляется довольно формальным; основные его пункты подытожены в конце. Первый вопрос, на который нужно найти ответ, состоит в том, сушествует ли 'ск конечный горизонт или сь бесконечный горизонт для принятия решений. Наличие конечного горизонта означает, что есть такое фиксированное время И, после кото- 820 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности рого все теряет смысл,— так сказать, игра все равно окончена.
Таким образом, (т. ( [в вт ". я .«) ) =У«( [в,, ью ..., вп] ) для всех Л>0. Например, предположим, что агент начинает свое движение с квадрата (3, 1) в мире с размерами 4хЗ, показанном на рис. 17.1, а также допустим, что д(=З. В таком случае, чтобы получить хоть малейший шанс достичь состояния + 1, агент должен направиться непосредственно к нему, и оптимальное действие состоит в том, чтобы двигаться в направлении (тр. С другой стороны, если бь100, то запас времени настолько велик, что можно выбрать безопасный маршрут в направлении ьеГш с(т' Поэтому нри наличии конечного горизонта оптимальное действие в каясдам канкретлам состоянии са временем может измениться.
Принято считать, что оптимальная стратегия при наличии конечного горизонта является 'а. нестационарной. С другой стороны, если нет заданного предела времени, то нет смысла вести себя поразному в одном и том же состоянии в разное время. Поэтому оптимальное действие зависит только от текущего состояния и оптимальная стратегия является Ж стационарной. Таким образом, стратегии для случая с бесконечным горизонтом проще по сравнению с теми, которые применяются в случае с конечным горизонтом, и в данной главе будет в основном рассматриваться случай с бесконечным горизонтом'. Обратите внимание на то, что понятие "бесконечного горизонта" не обязательно означает, что все последовательности состояний являются бесконечными; оно просто говорит о том, что для их выполнения не устанавливаются фиксированные сроки.
В частности, в любой задаче М[ЗР с бесконечным горизонтом могут существовать конечные последовательности состояний, солержащие терминальное состояние. Следующий вопрос, на который необходимо найти ответ, состоит в том, как рассчитать полезность последовательностей состояний. Мы будем рассматривать задачу поиска ответа на этот вопрос как задачу многоатрибутной теории полезности (см. разлел 16.4), где каждое состояние в, рассматривается как атрибут последовательности состояний [ ве, вю в,, ... ] . Чтобы получить простое выражение в терминах атрибутов, необходимо принять своего рода предположение о независимости предпочтений.
Наиболее естественное предположение состоит в том, что отношение предпочтения агента между последовательностями состояний является Ъ.стационарным. Стационарность предпочтений означает следующее: если две последовательности состояний, [эс, вт, в,, ...] и [вс', в,', в,', ...], начинаются с одного и того же состояния [т.е. ве=ве '), то эти две последовательности должны быть упорядочены по предпочтениям таким же образом, как и последовательности [вз, в„...1 и [ в, ', в, ', .. ] .
На естественном языке эту мысль можно выразить так, что если вы предпочитаете одно будущее развитие событий, начинающееся завтра, другому развитию событий, то вы должны также предпочесть это будущее развитие событий, если оно начнется сегодня. На первый взгляд, предположение о стационарности выглядит довольно безобидно, но влечет за собой весьма важные последствия: как оказалось, в условиях стационарности существуют только два способа присваивания значений полезности последовательностям, которые описаны ниже. 1. о«Адаптивные вознаграящения. Полезность последовательности состояний определяется следующим образом: Оь( [вь вз, вт,...1 ) = я(вс) '.я(вт) ья(вз) +... ' Это утверждение касается полносп,ю наблюдьемых вариантов среды.
Как будет показано ниже, лля ча~ тично наблюдаемых вариантов среды случай с бесконечным горизонтом пе тлк уж прост. Глава 17. Принятие сложных решений 82! В мире 4хЗ, показанном на рис.!7.1, используются аддитивные вознаграждения. Обратите внимание на то, что свойство аддитивности уже было определено неявно в используемых нами функциях стоимости пути для алгоритмов эвристического поиска (см, главу 4).
2. еь Обесцениваемые вознаграждения, Полезность последовательности состояний определяется с помощью следующего соотношения: Уь((ла Яг,э2," 1) = л(зо)+Уд(Б~)~~т Я(Б~)+.-. где у — это сь коэффициент обесценивания, который представляет собой число от 0 до 1. Коэффициент обесценивания описывает предпочтение агентом текущих вознаграждений перед будущими вознаграждениями. Если коэффициент у близок к О, вознаграждения, которые должны быть получены в отлаленном будущем, рассматриваются как малозначащие, а если коэффициент у равен 1, то обесцениваемые вознаграждения полностью эквивалентны аддитивным вознаграждениям, поэтому аддитивные вознагражления прелставляют собой частный случай обесцениваемых вознаграждений.
Повидимому, обесценивание представляет собой хорошую модель изменения во времени предпочтений и животных, и человека. Коэффициент обесценивания у эквивалентен процентной ставке (177) -1. 1. Г1ри наличии обесцениваемых вознаграждений полезность любой бесконечной последовательности является конечной. В действительности, если вознаграждения ограничены значением Я, и у<1, то можно получить следующее соотношение с использованием стандартной формулы суммы бесконечных геометрических рядов: Ул( (ао, Ш, аг, ...1) =,) у К(ас) я,) у" Я =Л / (1-7) е=о е=о (17.1) 2. Если среда содержит терминальные состояния и гарантируется достижение агентом в конечном итоге одного из этих состояний, то нам никогда не придется сравнивать бесконечные последовательности действий. Стратегия, который гарантирует достижение терминального состояния, называется 'в. правильной стратегией.
При наличии правильных стратегий можно использовать 7=1 (т.е. аддитивные вознаграждения). Первые три стратегии, пока- По причинам, которые вскоре станут очевидными, до конца этой главы предполагается, что используются обесцениваемые вознаграждения, хотя иногда допускается применение значения 7=1. Сделанный нами выбор бесконечных горизонтов становится причиной возникновения определенной проблемы: если среда не содержит терминальное состояние или если агент никогда его не достигает, то все истории пребывания в среде будут иметь бесконечную длину, а полезности, связанные с алдитивными вознаграждениями, в общем случае будут бесконечными. Дело в том, что, безусловно, + лучше, чем —, но гораздо сложнее сравнивать две последовательности состояний, притом что обе имеют полезность + .
Для решения этой проблемы можно применить три описанных ниже подхода, два из которых уже упоминались в этой главе. 822 Частью. Неопределенные знания и рассуждения в условиях неопределенности занные на рис. !7.2, б, являются правильными, а четвертая — неправильной. В ней достигается бесконечное суммарное вознаграждение за счет предотвращения попадания в терминальные состояния, притом что вознаграждение за пребывание в нетерминальных состояниях является положительным. Само существование неправильных стратегий в сочетании с использованием аддитивных вознаграждений может стать причиной неудачного завершения стандартных алгоритмов решения задач МОР, поэтому является весомым доводом в пользу применения обесцениваемых вознаграждений. 3.
Еще один подход состоит в том, чтобы сравнивать бесконечные последовательности по 'в. среднему вознаграждению, получаемому в расчете на каждый временной интервал. Предположим, что с квадратом (1, 1) в мире 4хЗ связано вознаграждение О. 1, тогда как для других нетерминальных состояний предусмотрено вознаграждение О. 01. В таком случае стратегия, в которой агент предпочтет оставаться в квадрате (1, 1), позволит получать более высокое среднее вознаграждение по сравнению с той стратегией, в которой агент находится в каком-то другом квадрате. Среднее вознаграждение прелставляет собой полезный критерий для некоторых задач, но анализ алгоритмов со средним вознаграждением выходит за рамки данной книги. Полводя итог, можно сказать, что использование обесцениваемых вознаграждений связано с наименьшими трудностями при оценке последовательностей состояний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
