Q-learning

Q-learning (Q-обучение) - метод применяемый в искусственном интеллекте при агентном подходе. Относится к экспериментам вида oбучения с подкреплением. На основе получаемого от среды вознаграждения агент формирует функцию полезности Q, что в последствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ Q-обучения - то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды.

Формализация постановки задачи

При формализации важно отделить агента и среду.

В распоряжении агента имеются некоторое множество действий A(a₁, a₂ ... a_n). Действия агента влияют на среду, и агент в состоянии определить в каком состоянии он находится в данный момент и получает то или иное вознаграждение от среды за свои действия R(a,s).

Для построения среды важно определить всё множество возможных состояний среды S(s₁, s₂ ... s_n). А также матрицу переходов T(s, a, s' ), которая содержит вероятности достижения состояния s', если в состоянии s было выполнено действие а. Предполагается, что эти переходы являются марковскими в том смысле, что вероятность достижения состояния s' из s зависит только от s, а не от истории пребывания в предыдущих состояниях. На данный момент запись T(s, a, s' ) может рассматриваться как большая трехмерная таблица, содержащая вероятности.

Задачей агента является найти наилучшую стратегию. В данном случае она будет описываться Q-значениями, которые определяют полезность выполняемого действия в соответствующем состоянии. Для обозначения стоимости выполнения действия а в состоянии s будет использоваться запись Q(a,s).

Пример простой задачи

Черные стрелки - переходы по действию 0 или 1 (совпадают), зеленые стрелки переходы по действию 1, синие стрелки переходы по действию 0. Красные узлы - состояния в которых получают награждение (независимо от действия, величина награды указана в скобках)

• Множество действий - A = {0, 1};
• Множество состояний - S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
• Матрица переходов - T[s', a, s] (показана на рисунке в виде графа);
• Задачи могут быть определены как с целевым состоянием, или как нахождение траектории с максимальным вознаграждением. В данном случае, нахождение траектории с максимальным вознаграждением.
• Вознаграждения определяются матрицей R(s, a). Величина вознаграждений показана на рисунке.

Максимальная выгода в этой задаче 1000 ед. награды за каждые 5 ходов. Т.е. при 1000 итерациях = 200 тыс., а при 10000 итераций = 2000 тыс.

Наличие перехода из 1 в 7 - превращает задачу с наличием двух траекторий к максимальной цели. Это существенно влияет на алгоритм Q-learning. При 1000 итераций и различных LF, DF и EF=0 - очень мало решений которые находят сокращенный путь (5 шагов, вместо 10-11) к цели 9. Приходится использовать EF несмотря на детерминированность задачи.

Алгоритм и реализация

Псевдокод алгоритма можно посмотреть в Википедии. Ряд практических соображений для более сложных задач описывается в рамках проекта RNAFoldingAI - Постановка задачи в терминах Q-learning.

Ссылки

• глава из книги Рассел Норвиг, "ИИ - современный подход"

См. также

• RNAFoldingAI - открытый проект в Викиверситете, в котором применяется Q-learning