Критерии конвергенции в Q-Learning

Question

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

Большинство источников рекомендуют повторять несколько раз (например, N = 1000), в то время как другие говорят, что сходимость достигается, когда все пары состояний и действий (а, а) посещаются бесконечно часто. Но вопрос здесь в том, сколько стоит бесконечно часто. Каков наилучший критерий для того, кто хочет решить алгоритм вручную?

Я был бы признателен, если бы кто-нибудь смог рассказать мне об этом. Я также был бы признателен за любые статьи на этот счет.

С уважением.

Answer 1

Q-Learning был главным прорывом в обучении с подкреплением именно потому, что это был первый алгоритм с гарантированной конвергенцией к оптимальной политике. Первоначально он был предложен в (Watkins, 1989) , а его доказательство сходимости было уточнено в (Watkins & Dayan, 1992) .

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

1. Скорость обучения должна приближаться к нулю, но не слишком быстро. Формально, для этого необходимо, чтобы сумма скоростей обучения должна была расходиться, но сумма их квадратов должна сходиться. Пример последовательности, которая имеет эти свойства: 1/1, 1/2, 1/3, 1/4, ...
2. Каждая пара состояния-действия должна посещаться бесконечно часто. Это имеет точное математическое определение: каждое действие должно иметь ненулевую вероятность быть выбранной политикой в ​​каждом штате, , т.е. π(s, a) > 0 для всех (s, a). На практике использование политики ε-жадности (где ε > 0) обеспечивает выполнение этого условия.

Answer 2

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

Теоретически доказано, что Q-Learning сходится к оптимальному решению, но обычно не очевидно, как настроить гиперпараметры, такие как ? и ?, таким образом, чтобы обеспечить сходимость.

Имейте в виду, что Q-learning - это старый алгоритм, который устарел, это хороший способ узнать о RL, но есть более эффективные способы решения реальной проблемы.