Dynamic programming for reinforcement-learning
Теги: machine-learning r-learning
ДП - это семейство алгоритмов для вычисления оптимальных стратегий при условии что имеется идеальная модель окружающей среды в виде [mppr]. Из-за этого от ДП мало пользы из-за предположения об идеальной модели, а так-же из-за вычислительных затрат. Ключевая идея ДП и обучения с подкреплением в целом заключается в использовании функции ценности для организации и структурирования поиска хороших стратегий.
В ДП входят слудующие этапы:
- оценивание стратегии (предсказание) - итеративное вычисление функции ценности для заданной стратегии
- улучшение стратегии - вычисление улучшенной стратегии при заданной функции ценности
- итерация по стратегиям (после улучшения стратегии \(\pi\) до \(\pi'\) мы получаем последовательность монотонно улучшающихся стратегий и функций ценности. Гарантируется что каждая следующая стратегия лучше предыдущей, если только предыдущая не является оптимальной. Т.к. МППР допускает только конечное число стратегий, этот процесс должен сойтись к оптимальной стратегии и оптимальной функции ценности за конечное число итераций. Итерация по стратегиям ДП состоит по сути из двух разнонаправленных процессов - оценивания стратегии, который согласует функцию ценности с текущей стратегией и улучшения стратегии, который делает стратегию жадной относительно текущей ф-ции ценности. В ходе итерации эти процессы чередуются.)
- итерация по ценности (т.к. оценка стратегии на каждой итерации является недостатком. чтобы усечь вычисления используется остановка оценивания после всего одного прохода)
Основной недостаток ДП - алгоритмы ДП включают операции над всем множеством состояний, т.е. выполняется полное обновление состояний. Если такое множество очень велико, то даже один проход будет стоить недопустимо дорого. Эту проблему отчасти реализуцет ассинхронный ДП. Такие алгоритмы обновляют ценности состояний в произвольном порядке, используя ценности состояний, которые существуют на данный момент.
Смотри еще: