Почему всегда есть хотя бы одна политика, которая лучше или равна всем другим политикам?

15

Усиление обучения: введение. Второе издание, в процессе ., Ричард С. Саттон и Эндрю Дж. Барто (с) 2012, с. 67-68.

Решение задачи обучения с подкреплением означает, грубо говоря, поиск политики, которая в конечном итоге приносит много пользы. Для конечных MDP мы можем точно определить оптимальную политику следующим образом. Функции значения определяют частичное упорядочение по политикам. Политика π определяется как лучшая или равная политике π если ее ожидаемая отдача больше или равна таковой π для всех состояний. Другими словами, ππ тогда и только тогда, когда vπ(s)vπ(s) для всех sS . Всегда есть хотя бы одна политика, которая лучше или равна всем другим политикам. Это оптимальная политика.

Почему всегда есть хотя бы одна политика, которая лучше или равна всем другим политикам?

sh1ng
источник
Очень подробное доказательство (которое использует теорему Банаха о неподвижной точке) появляется в главе 6.2 «Марковских процессов принятия решений» Путермана.
Тогс

Ответы:

3

Только после процитированной части, тот же параграф фактически говорит вам, что это за политика: именно она принимает наилучшие меры в каждом штате. В MDP действие, которое мы предпринимаем в одном государстве, не влияет на вознаграждение за действия, предпринимаемые в других государствах, поэтому мы можем просто максимизировать политику в каждом штате.

Дон реба
источник
Не является ли этот ответ совершенно неправильным? Как можно сказать, что оптимизация государственной политики государством приводит к оптимальной политике. Если я оптимизирую по состоянию St и это занимает у меня St+1 а затем оптимизация при St+1 приводит к функции оптимального значения Vt+1 но есть другая политика, в которой St приводит неоптимально к Sl и оптимальному Функция значения Sl выше, чем Vt+1 . Как вы можете исключить это с помощью такого беглого анализа?
MiloMinderbinder
@MiloMinderbinder Если оптимальной политикой в St является выбор St+1 , то значение St+1 выше, чем значение Sl .
Дон Реба
Виноват. Опечатка исправлена: «Не является ли этот ответ совершенно неправильным? Как вы можете сказать, что оптимизация государственной политики приводит к оптимальной политике? Если я оптимизирую по состоянию и это приводит меня к S t + 1, а затем оптимизация при S t + 1 приводит к функции оптимального значения V t + 2 из S t + 2, но есть другая политика, в которой S t, хотя и приводит субоптимально к S l + 1 и, следовательно, функция значения S t + 1StSt+1St+1Vt+2St+2StSl+1St+1выше, чем но функция значения S t + 2 в этой политике выше, чем в соответствии с политикой, определяемой путем оптимизации состояния за состоянием. Как это нарушено вами? Vl+1St+2
MiloMinderbinder
Я думаю, что определение предотвратит это прежде всего, так как оно должно учитывать и будущие доходы. V
Flying_Banana
Тогда возникает вопрос: почему существует ? Вы не можете обойти теорему Банаха о неподвижной точке :-)q
Фабиан Вернер
10

Существование оптимальной политики не очевидно. Чтобы понять почему, обратите внимание, что функция value обеспечивает только частичное упорядочение в пространстве политик. Это означает:

ππvπ(s)vπ(s),sS

Поскольку это только частичное упорядочение, может быть случай, когда две политики, и π 2 , не сравнимы. Другими словами, существуют подмножества пространства состояний S 1 и S 2, такие что:π1π2S1S2

vπ(s)vπ(s),sS1

vπ(s)vπ(s),sS2

В этом случае нельзя сказать, что одна политика лучше другой. Но если мы имеем дело с конечными MDP с ограниченными функциями значений, то такой сценарий никогда не происходит. Существует ровно одно оптимальное значение функции, хотя может быть несколько оптимальных политик.

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

Картик Тиагараджан
источник
8

настройка

Мы рассматриваем в настройках:

  • Дискретные действия
  • Дискретные состояния
  • Ограниченные награды
  • Стационарная политика
  • Бесконечный горизонт

Политика оптимальной определяется как: и значение функции оптимальным является: V * = макс π V π ( ы ) , s S Там может быть множество политики, которые достигают максимума. Но есть только одна функция оптимального значения: V = V π

(1)πargmaxπVπ(s),sS
(2)V=maxπVπ(s),sS
(3)V=Vπ

Вопрос

Как доказать, что существует хотя бы один который удовлетворяет (1) одновременно для всех s S ?πsS

План доказательства

  1. Построить оптимальное уравнение для использования в качестве временного суррогатного определения функции оптимального значения, которое мы докажем на шаге 2, что оно эквивалентно определению с помощью уравнения (2).

    (4)V(s)=maxaA[R(s,a)+γsST(s,a,s)V(s)]
  2. Вывести эквивалентность определения функции оптимального значения через уравнение (4) и уравнение (2).

    (Обратите внимание, что на самом деле нам нужно только направление необходимости в доказательстве, поскольку достаточность очевидна, поскольку мы построили уравнение (4) из уравнения (2).)

  3. Докажите, что существует единственное решение уравнения (4).

  4. На шаге 2 мы знаем, что решение, полученное на шаге 3, также является решением уравнения (2), поэтому оно является функцией оптимального значения.

  5. Из функции оптимального значения мы можем восстановить оптимальную политику, выбрав действие максимизатора в уравнении (4) для каждого состояния.

Детали шагов

1

V(s)=Vπ(s)=Ea[Qπ(s,a)], we have Vπ(s)maxaAQπ(s,a). And if there is any s~ such that VπmaxaAQπ(s,a)Q(s,a)=Qπ(s,a) over a.

2

(=>)

Follows by step 1.

(<=)

i.e. If V~ satisfies V~(s)=maxaA[R(s,a)+γsST(s,a,s)V~(s)], then V~(s)=V(s)=maxπVπ(s),sS.

Define the optimal Bellman operator as

(5)TV(s)=maxaA[R(s,a)+γsST(s,a,s)V(s)]
So our goal is to prove that if V~=TV~, then V~=V. We show this by combining two results, following Puterman[1]:

a) If V~TV~, then V~V.

b) If V~TV~, then V~V.

Proof:

a)

For any π=(d1,d2,...),

V~TV~=maxd[Rd+γPdV~]Rd1+γPd1V~
Here d is the decision rule(action profile at specific time), Rd is the vector representation of immediate reward induced from d and Pd is transition matrix induced from d.

By induction, for any n,

V~Rd1+i=1n1γiPπiRdi+1+γnPπnV~
where Pπj represents the j-step transition matrix under π.

Since

Vπ=Rd1+i=1γiPπiRdi+1
we have
V~VπγnPπnV~i=nγiPπiRdi+10 as n
So we have V~Vπ. And since this holds for any π, we conclude that
V~maxπVπ=V
b)

Follows from step 1.

3

The optimal Bellman operator is a contraction in L norm, cf. [2].

Proof: For any s,

|TV1(s)TV2(s)|=|maxaA[R(s,a)+γsST(s,a,s)V1(s)]maxaA[R(s,a)+γsST(s,a,s)V(s)]|()|maxaA[γsST(s,a,s)(V1(s)V2(s))]|γV1V2
where in (*) we used the fact that
maxaf(a)maxag(a)maxa[f(a)g(a)]

Thus by Banach fixed point theorum it follows that T 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

LoveIris
источник