Обзор существующих алгоритмов

Классификация алгоритмов

Существует большое множество алгоритмов для обучения с подкреплением. Самые распространенные это Q-Learning (Q-Обучение), Sarsa, Эволюционные алгоритмы (ЭА).

Q-learning — это методика обучения с подкреплением Off-Policy (обучающийся алгоритм узнает ценность оптимальной политики независимо от своих действий) [5,6].

Политика — это правило, которым агент руководствуется при выборе действия, учитывая состояние, в котором он находится. В частности, Q-learning можно использовать для нахождения оптимальной политики выбора действия для любого заданного (конечного) МППР. В процессе обучения изучается action-value функция которая, в конечном счете, дает ожидаемую полезность принятия данного действия в данном состоянии и последующую оптимальную политику после этого. Когда данная функция изучена, оптимальная политика может быть построена простым выбором действия с самым высоким значением в каждом состоянии.

Одна из сильных сторон Q-learning заключается в том, что он способен сравнивать ожидаемую полезность доступных действий без использования модели среды. Кроме того, Q-learning может решать проблемы со стохастическими переходами и вознаграждениями, не требуя никаких адаптаций. Также было доказано, что для любого конечного МППР Q-learning в конечном итоге находит оптимальную политику в том смысле, что ожидаемое значение общего вознаграждения за все последующие шаги, начиная с текущего состояния, является максимально достижимым.

Алгоритм Sarsa является алгоритмом On-Policy (обучающаяся модель узнает ценность политики, выполняемой ею, включая все действия и шаги исследования) [6].

Основное различие между ним и Q-Learning заключается в том, что максимальное вознаграждение за следующее состояние не обязательно используется для обновления Q-значений. Вместо этого новое действие и, следовательно, вознаграждение выбираются с использованием той же политики, которая определяет исходное действие.

Название Sarsa фактически происходит от того, что обновления выполняются с использованием пятикратного.

.

Где: , — исходное состояние и действие, — вознаграждение, наблюдаемое в следующем состоянии, и — новая пара «состояние-действие» .

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

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