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

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?

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

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

$$\begin{align} v_∗(s) &= \max_{a} \mathbb{E}[R_{t+1} + \gamma v_* (S_{t+1}) \mid S_t =s, A_t =a] \\ &= \max_{a} \sum_{s'}p(s'\mid s, a) \biggl[r(s, a, s') + \gamma v_∗(s')\biggl] \end{align}$$

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 . $\pi$$\pi'$$s \in S$$q_\pi(s, \pi'(s)) \geq v_\pi(s)$$\pi'$$\pi$$s \in S: v_{\pi'} (s) \geq v_\pi(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:$\pi$

$$\begin{align} \pi'(s) &= \arg \max_{a}q_π(s, a)\\ &= \arg \max_{a} \sum_{s'}p(s' \mid s, a)\biggl[r(s, a, s') + \gamma v_\pi(s')\biggl] \end{align}$$

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:$\pi'$$\pi$$\pi'$$\pi$$v_{\pi'}(s)=v_{\pi}(s)$$s$$\pi'$

$$\begin{align} v_{\pi'}(s)&=\max_{a} \mathbb{E}\biggl[R_{t+1} + \gamma v_{ \pi'}(S_{t+1}) \mid S_t =s, A_t =a \biggl]\\ &= \max_{a}\sum_{s'}p(s' \mid s, a) \biggl[r(s, a, s') + \gamma v_{π'}(s') \biggl] \end{align}$$

Mas essa igualdade é a mesma da equação de idealidade de Bellman, portanto deve ser igual a .$v_{\pi'}$$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)

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é ."$V_{n+1} = V_n, α_{n+1} = α_n$

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