Condições de convergência do algoritmo de iteração de política e valor

8

Os algoritmos de iteração de política e valor podem ser usados ​​para resolver problemas no processo de decisão de Markov. É difícil entender as condições necessárias para a convergência. Se a política óptima não se altera durante dois passos (ou seja, durante as iterações i e i + 1 ), pode-se concluir que os algoritmos têm convergido? Se não, então quando?

ELEC
fonte

Respostas:

3

Para responder à sua pergunta, deixe-me primeiro escrever algumas (in) igualdades importantes.

Equação de otimização de Bellman:

v(s)=maxaE[Rt+1+γv(St+1)St=s,At=a]=maxasp(ss,a)[r(s,a,s)+γv(s)]

onde v(.) é a função de valor ideal.

Teorema da melhoria de políticas ( Pit ):

Seja e qualquer par de políticas determinísticas que, para todos os , Então a política deve ser tão bom quanto, ou melhor que, . Ou seja, ele deve obter um retorno esperado maior ou igual de todos os estados . ππsSqπ(s,π(s))vπ(s)ππsS:vπ(s)vπ(s)

(encontre na página 89 de Sutton & Barto, Aprendizado por reforço: um livro de introdução )

Podemos melhorar uma política em todos os estados pela seguinte regra:π

π(s)=argmaxaqπ(s,a)=argmaxasp(ss,a)[r(s,a,s)+γvπ(s)]

Nossa nova política satisfaz a condição do Pit e, portanto, é tão boa quanto ou melhor que . Se é tão bom quanto, mas não melhor que , então para todos os . Da nossa definição de deduzimos que:ππππvπ(s)=vπ(s)sπ

vπ(s)=maxaE[Rt+1+γvπ(St+1)St=s,At=a]=maxasp(ss,a)[r(s,a,s)+γvπ(s)]

Mas essa igualdade é a mesma da equação de idealidade de Bellman, portanto deve ser igual a .vπv

Do exposto acima, espera-se claramente que, se melhorarmos uma política e obtivermos a mesma função de valor que tínhamos antes, a nova política deverá ser uma das políticas ideais. Para mais informações, consulte Sutton & Barto (2012)

Jan Vainer
fonte
1

Você está certo: a estimativa da função de valor atual ou a estimativa da política atual podem descrever completamente o estado do algoritmo. Cada um implica uma próxima escolha única para o outro. No artigo abaixo,

"A iteração da política continua até ."Vn+1=Vn,αn+1=αn

https://editorialexpress.com/jrust/research/siam_dp_paper.pdf

eric_kernfeld
fonte