Усиление обучения: введение. Второе издание, в процессе ., Ричард С. Саттон и Эндрю Дж. Барто (с) 2012, с. 67-68.
Решение задачи обучения с подкреплением означает, грубо говоря, поиск политики, которая в конечном итоге приносит много пользы. Для конечных MDP мы можем точно определить оптимальную политику следующим образом. Функции значения определяют частичное упорядочение по политикам. Политика определяется как лучшая или равная политике если ее ожидаемая отдача больше или равна таковой для всех состояний. Другими словами, тогда и только тогда, когда для всех . Всегда есть хотя бы одна политика, которая лучше или равна всем другим политикам. Это оптимальная политика.
Почему всегда есть хотя бы одна политика, которая лучше или равна всем другим политикам?
Ответы:
Только после процитированной части, тот же параграф фактически говорит вам, что это за политика: именно она принимает наилучшие меры в каждом штате. В MDP действие, которое мы предпринимаем в одном государстве, не влияет на вознаграждение за действия, предпринимаемые в других государствах, поэтому мы можем просто максимизировать политику в каждом штате.
источник
Существование оптимальной политики не очевидно. Чтобы понять почему, обратите внимание, что функция value обеспечивает только частичное упорядочение в пространстве политик. Это означает:
Поскольку это только частичное упорядочение, может быть случай, когда две политики, и π 2 , не сравнимы. Другими словами, существуют подмножества пространства состояний S 1 и S 2, такие что:π1 π2 S1 S2
В этом случае нельзя сказать, что одна политика лучше другой. Но если мы имеем дело с конечными MDP с ограниченными функциями значений, то такой сценарий никогда не происходит. Существует ровно одно оптимальное значение функции, хотя может быть несколько оптимальных политик.
Для доказательства этого вам нужно понять теорему Банаха о неподвижной точке. Для подробного анализа, пожалуйста, обратитесь .
источник
настройка
Мы рассматриваем в настройках:
Политика оптимальной определяется как: и значение функции оптимальным является: V * = макс π V π ( ы ) , ∀ s ∈ S Там может быть множество политики, которые достигают максимума. Но есть только одна функция оптимального значения: V ∗ = V π ∗
Вопрос
Как доказать, что существует хотя бы один который удовлетворяет (1) одновременно для всех s ∈ S ?π∗ s∈S
План доказательства
Построить оптимальное уравнение для использования в качестве временного суррогатного определения функции оптимального значения, которое мы докажем на шаге 2, что оно эквивалентно определению с помощью уравнения (2).
Вывести эквивалентность определения функции оптимального значения через уравнение (4) и уравнение (2).
(Обратите внимание, что на самом деле нам нужно только направление необходимости в доказательстве, поскольку достаточность очевидна, поскольку мы построили уравнение (4) из уравнения (2).)
Докажите, что существует единственное решение уравнения (4).
На шаге 2 мы знаем, что решение, полученное на шаге 3, также является решением уравнения (2), поэтому оно является функцией оптимального значения.
Из функции оптимального значения мы можем восстановить оптимальную политику, выбрав действие максимизатора в уравнении (4) для каждого состояния.
Детали шагов
1V∗(s)=Vπ∗(s)=Ea[Qπ∗(s,a)] , we have Vπ∗(s)≤maxa∈AQπ∗(s,a) . And if there is any s~ such that Vπ∗≠maxa∈AQπ∗(s,a) Q∗(s,a)=Qπ∗(s,a) over a .
2(=>)
Follows by step 1.
(<=)
i.e. IfV~ satisfies V~(s)=maxa∈A[R(s,a)+γ∑s′∈ST(s,a,s′)V~(s′)] , then V~(s)=V∗(s)=maxπVπ(s),∀s∈S .
Define the optimal Bellman operator as
a) IfV~≥TV~ , then V~≥V∗ .
b) IfV~≤TV~ , then V~≤V∗ .
Proof:
a)
For anyπ=(d1,d2,...) ,
By induction, for anyn ,
Since
Follows from step 1.
3The optimal Bellman operator is a contraction inL∞ norm, cf. [2].
Proof: For anys ,
Thus by Banach fixed point theorum it follows thatT has a unique fixed point.
References
[1] Puterman, Martin L.. “Markov Decision Processes : Discrete Stochastic Dynamic Programming.” (2016).
[2] A. Lazaric. http://researchers.lille.inria.fr/~lazaric/Webpage/MVA-RL_Course14_files/slides-lecture-02-handout.pdf
источник