Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 277

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 277)

Авторы называют такого агента, действующего с помощью жадного алгоритма, просто 'в. жадным агентом. Повторные эксперименты показали, что поиски жадного агента очень редко сходятся в пределе к оптимальной стратегии для данной среды, а иногда сходятся к таким стратегиям, которые являются действительно устрашающими по своей неэффективности. Как могло оказаться, что выбор оптимального действия приводит к неоптимальным результатам? Ответ состоит в том, что модель, определяемая с помощью обучения, не является такой же, как истинная среда; поэтому то, что оптимально в модели, определяемой с помощью обучения, может оказаться неоптимальным в истинной среде. К сожалению, агент не имеет информации о том, какова истинная среда, поэтому не может вычислить оптимальное действие для истинной среды.

Так что же делать? В проекте жадного агента не учтено то, что действия не только предоставляют вознаграждения в соответствии с моделью, определяемой в настоящее время с помощью обучения, но и вносят вклад в определение с помощью обучения самой истинной модели, влияя на полученные результаты восприятия. Совершенствуя эту модель, агент сможет получать большие вознаграждения не сразу же, а в будущем'.

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

В реальном мире человеку постоянно приходится решать, стоит ли продолжать беззаботное существование или нужно окунуться в неизвестность в надежде найти новые и лучшие условия жизни. Но чем большими знаниями он облалает, тем меньше нуждается в дальнейших исследованиях. Можно ли выработать более точные рекомендации по сравнению с этими общими рассуждениями? Существует ли оптимальный способ организации исследования среды? Как оказалось, эти вопросы глубоко изучались в той области статистической теории принятий решений, которая касается так называемых 'в. задач с п-рукими бандитами, — так принято называть игорные автоматы, управляемые с помощью рукояток (см.

врезку). ' Обратите внимание на то, что здесь просматривается прямая аналогия с теорией пенности информации, описанной в главе 16. (бг) Глава 21. Обучение с подкреплением лениях требуется, чтобы ожидаемое вознаграждение оценивалось по всем возможным мирам, в которых может оказаться агент, а также по возможным результатам каждой последовательности действий в любом конкретном мире. В данном случае "мир" определяется моделью перехода т(в, а, в' ).

Таким образом, для того чтобы действовать оптимальным образом, агент должен знать распределение априорных вероятностей по всем возможным моделям. Возникающие в конечном итоге задачи оптимизации обычно являются крайне трудно разрешимыми. В некоторых случаях (например, когда вознаграждение, получаемое от игры на каждом автомате, является независимым и используются обесцениваемые вознаграждения) существует возможность рассчитать индекс Гиттииса для каждого игорного автомата (561). Этот индекс представляет собой функцию, параметрами которой являются только количество игр, проведенных на игорном автомате, и сумма полученного выигрыша.

Индекс для каждого автомата показывает, насколько оправданы дополнительные затраты денег на продолжение игры с учетом комбинации ожидаемой прибыли и ожидаемой стоимости информации. Выбор автомата с наибольшим значением индекса позволяет найти оптимальную стратегию исследования среды. К сожалению, до сих пор не было обнаружено ни одного метода, позволяющего распространить понятие индексов Гиттинса на проблематику задач последовательного принятия решений. Теорию и-руких бандитов можно использовать для обоснования приемлемости стратегии отбора в генетических алгоритмах (см. главу 4).

Если в задаче с и-руким бандитом каждая рукоятка рассматривается как возможная строка генов, а вкладывание монеты для подтягивания одной рукоятки — как воспроизведение этих генов, то генетические алгоритмы должны обеспечить оптимальное вложение монет в игорный автомат с учетом соответствующего множества предположений о независимости. Хотя задачи с и-рукими бандитами чрезвычайно трудно поддаются точному решению для получения оптимального метода исследования среды, тем не менее возможно предложить приемлемую схему, которая в конечном итоге приводит к оптимальному поведению со стороны агента. Формально любая такая схема должна быть жадной в пределе бесконечного исследования; это свойство сокращенно обозначается как 'ъ ОВ1Е (Огееду ш бзе 1.ппй о(1пйп!ге Ехр1огайоп).

Схема ОЫЕ должна предусматривать опробование каждого действия в каждом состоянии путем осуществления неограниченного количества попыток такого действия для предотвращения появления конечной вероятности того, что будет пропущено какое-то оптимальное действие из-за крайне неудачного стечения обстоятельств. Агент АОР, в котором используется такая схема, должен в конечном итоге определить с помощью обучения истинную модель среды.

Кроме того, схема С 1.1Е должна в конечном итоге стать жадной, для того чтобы действия агента стали оптимальными по отношению к определенной с помощью обучения (и поэтому истинной) модели. Предложено несколько схем О) 1Е; в одной из простейших из этих схем предусматривается, что агент должен в течение 1! с части времени выбирать случайное действие, а в течение остального времени придерживаться жадной стратегии. Хотя такая схема в конечном итоге сходится к оптимальной стратегии, весь этот процесс 1024 Часть 1)).

Обучение может оказаться чрезвычайно замедленным. Более обоснованный подход предусматривает присваивание определенных весов тем действиям, которые агент не опробовал очень часто, стараясь вместе с тем избегать действий, которые считаются имеющими низкую полезность. Такой подход может быть реализован путем модификации уравнения ограничения 21.4 таким образом, чтобы в нем присваивалась более высокая оценка полезности относительно мало исследованным парам "состояние — действие".

По сути это сводится к определению оптимистического распределения априорных вероятностей по возможным вариантам среды и вынуждает агента на первых порах вести себя так, как если бы повсеместно были разбросаны замечательные вознаграждения. Допустим, что для обозначения оптимистической оценки полезности состояния э (т.е. ожидаемого будущего вознаграждения) используется запись (г' ( э), и предположим, что лг( а, в) — количество попыток опробования действия а в состоянии э. Предположим также, что в обучающемся агенте АРР используется метод итерации по значениям; в таком случае необходимо переписать уравнение обновления (т.е. уравнение !7.6), чтобы включить в него оптимистическую оценку. Именно такая цель достигается с помощью следующего уравнения: У (э) с — Я(а) (2з.в) где г( и, п) называется ск функцией исследования.

Эта функция определяет компромисс между жадностью (предпочтениями, отданными высоким значениям и) и любопытством (предпочтениями, отданными низким значениям п, характеризующим действия, которые еще не были опробованы достаточно часто). Функция Е( ц, и) должна увеличиваться в зависимости от и и уменьшаться в зависимости от п. Безусловно, что существует много возможных функций, которые соответствуют этим условиям. Одним из особенно простых определений такой функции является следукнцее: Я г(и,п) и если п < № в противном случае где Я" — оптимистическая оценка наилучшего возможного вознаграждения, которое может быть получено в любом состоянии; и, — постоянный параметр. Результатом применения такой функции становится то, что агент пытается проверить каждую пару "состояние — действие" по меньшей мере № раз. Тот факт, что в правой части уравнения 21.5 присутствует величина и', а не (г, очень важен.

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

Эффект использования такой исследовательской стратегии наглядно показан на рис. 21.5, который демонстрирует более быструю сходимость к оптимальной производительности в отличие от жадного подхода. Способ действий, очень близкий к оптималь- !лава 21.

Характеристики

Список файлов книги