Q-learning (Q-обучение) - метод применяемый в искусственном интеллекте при агентном подходе. Относится к экспериментам вида oбучения с подкреплением. На основе получаемого от среды вознаграждения агент формирует функцию полезности Q, что в последствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ Q-обучения - то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды.
Формализация постановки задачи[]
При формализации важно отделить агента и среду.
В распоряжении агента имеются некоторое множество действий A(a1, a2 ... an). Действия агента влияют на среду, и агент в состоянии определить в каком состоянии он находится в данный момент и получает то или иное вознаграждение от среды за свои действия R(a,s).
Для построения среды важно определить всё множество возможных состояний среды S(s1, s2 ... sn). А также матрицу переходов 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 не смотря на детерминированность задачи.
Алгоритм и реализация[]
Псевдокод алгоритма можно посмотреть в Википедии, а реализацию на C# можно скачать здесь. Там реализован простой агент в идеальной среде. Ряд практических соображений для более сложных задач описывается в рамках проекта RNAFoldingAI - Постановка задачи в терминах Q-learning.
Ссылки[]
См. также[]
- RNAFoldingAI - открытый проект в Викиверситете, в котором применяется Q-learning