Por que o algoritmo de iteração de política converge para a função ideal de política e valor?

Eu estava lendo as notas da aula de Andrew Ng sobre aprendizado por reforço e estava tentando entender por que a iteração de políticas convergiu para a função de valor ideal e a política ideal .$V^*$$\pi^*$

Lembre-se de que a iteração da política é:

$\text{Initialize $\pi$ randomly} \\ \text{Repeat}\{\\ \quad Let \ V := V^{\pi} \text{ \\for the current policy, solve bellman's eqn's and set that to the current V}\\ \quad Let \ \pi(s) := argmax_{a \in A} \sum_{s'}P_{sa}(s') V(s')\\ \}$

Por que um algoritmo ganancioso leva a uma política ótima e a uma função de valor ideal? (Eu sei que algoritmos gananciosos nem sempre garantem isso ou podem ficar presos nos ótimos locais, então eu só queria ver uma prova de sua otimização do algoritmo).

Além disso, parece-me que a iteração da política é algo análogo à descida em cluster ou gradiente. Para cluster, porque com a configuração atual dos parâmetros, otimizamos. Semelhante à descida do gradiente, porque apenas escolhe algum valor que parece aumentar alguma função. Esses dois métodos nem sempre convergem para o máximo ideal e eu estava tentando entender como esse algoritmo era diferente dos anteriores.

---

Estes são os meus pensamentos até agora:

Digamos que começamos com alguma política ; depois da primeira etapa, para essa política fixa, temos o seguinte:$\pi_1$

$V^{\pi_1}(s) = R(s) + \gamma \sum_{s'}P_{s\pi_1(s)}(s')V^{\pi_1}(s')$

$V^{(1)} := V^{\pi_1}(s)$

Onde V ^ {(1)} é a função de valor para a primeira iteração. Depois da segunda etapa, escolhemos uma nova política para aumentar o valor de . Agora, com a nova política , se fizermos o segundo passo do algoritmo, a seguinte desigualdade será verdadeira:$\pi_2$$V^{\pi_1}(s)$$\pi_2$

$R(s) + \gamma \sum_{s'}P_{s\pi_1(s)}(s')V^{\pi_1}(s') \leq R(s) + \gamma \sum_{s'}P_{s\pi_2(s)}(s')V^{\pi_1}(s')$

Como escolhemos na segunda etapa para aumentar a função de valor na etapa anterior (ou seja, para melhorar . Até agora, é claro que a escolha de só pode aumentar V ^ {(1)}, porque é assim que escolhemos No entanto, minha confusão vem na etapa de repetição, porque, uma vez que repetimos e voltamos à etapa 1, na verdade mudamos completamente as coisas porque recalculamos para a nova política . Que dá:$\pi_2$$V^{(1)}$$\pi_2$$\pi_2$$V^{2}$$\pi_2$

$V^{\pi_2}(s) = R(s) + \gamma \sum_{s'}P_{s\pi_2(s)}(s')V^{\pi_2}(s')$

mas NÃO é:

$V^{\pi_1}(s) = R(s) + \gamma \sum_{s'}P_{s\pi_2(s)}(s')V^{\pi_1}(s')$

O que parece ser um problema porque foi escolhido para melhorar , e não esse novo . Basicamente, o problema é que garantias para melhorar , fazendo vez de quando a função de valor é . Porém, na etapa de repetição, para , mas não vejo como isso garante que a função value melhore monotonicamente a cada repetição porque foi calculado para melhorar a função value quando as funções de valor permanecem em$\pi_2$$V^{(1)}$$V^{\pi_2}$$pi_2$$R(s) + \gamma \sum_{s'}P_{s\pi_1(s)}(s')V^{\pi_1}(s')$$\pi_2$$pi_1$$V^{\pi_1}$$V^{\pi_1}$$V^{\pi_2}$$\pi_2$$V^{\pi_1}$ V π 1, mas a etapa 1 altera para (o que é ruim porque eu apenas a função de valor anterior que tínhamos).$V^{\pi_1}$$V^{\pi_2}$$\pi_2$

Acho que a parte que você está perdendo é que está garantida pelo mesmo motivo que podemos solicitar . Essa é essencialmente a definição de uma política como melhor do que outra - que sua função de valor é maior ou igual em todos os estados. Você garantiu isso escolhendo as ações de maximização - nenhum valor de estado pode ser pior do que era antes e, se apenas uma opção de ação foi alterada para escolher uma ação de maximização melhor, você já sabe (mas pode não ter calculado) que o valor para esse estado será maior do que era para . π 2 ≥ π 1 V π 2 ( s ) V π 1 ( s $V^{\pi_2} \ge V^{\pi_1}$$\pi_2 \ge \pi_1$$V^{\pi_2}(s)$$V^{\pi_1}(s)$

Quando optamos por maximizar os resultados para gerar , não sabemos quais os novos para qualquer estado, mas sabemos que .V π 2 ( s ) ∀ s : V π 2 ( s ) ≥ V π 1 ( s $\pi_2$$V^{\pi_2}(s)$$\forall s: V^{\pi_2}(s) \ge V^{\pi_1}(s)$

Portanto, é garantido que o retorno ao loop e o cálculo de para a nova política tenham valores iguais ou superiores aos anteriores e, quando se trata de atualizar a política novamente, . π 3 ≥ π 2 ≥ π $V^{\pi_2}$$\pi_3 \ge \pi_2 \ge \pi_1$

Primeiro vamos ver por que o algoritmo de iteração de políticas funciona. Tem dois passos.

Etapa de avaliação de políticas:

$v_n = r_{d_n} + \gamma P_{d_n}v_n$ é a forma vetorial geral do sistema de equações lineares.

Aqui, os termos são recompensas imediatas e linhas correspondentes da matriz de transição.$r_{d_n}, P_{d_n}$

Esses termos dependem da política$\Pi_n$

Resolvendo o sistema de equações acima, podemos encontrar os valores de$v_n$

Etapa de aprimoramento de políticas:

Suponha que fomos capazes de encontrar uma nova política que$\Pi_{n+1}$

$$\begin{align} r_{d_n+1} + \gamma P_{d_n+1}v_n & \ge r_{d_n} + \gamma P_{d_n}v_n \\ \implies r_{d_n+1} & \ge [I - \gamma P_{d_n+1}]v_n \quad \text{say this is eqn. 1}\\ \end{align}$$

Agora, com base na nova política , podemos encontrar , diga que esta é a equação 2. v n + 1 = r d n + 1 + γ P d n + 1 v n + $\Pi_{n+1}$$v_{n+1} = r_{d_{n+1}} + \gamma P_{d_{n+1}}v_{n+1}$

Vamos mostrar que ;$v_{n+1} \ge v_n$

ou seja, essencialmente para todos os estados, a política recém-escolhida fornece um valor melhor em comparação com a política Π $\Pi_{n+1}$$\Pi_{n}$

Prova:

A partir da equação 2, temos,

$[I - \gamma P_{d_{n+1}}]v_{n+1} = r_{d_n+1}$

De, , temos$1 \&2$

$v_{n+1} \ge v_{n}$

Essencialmente, os valores estão aumentando monotonicamente a cada iteração.

É importante entender por que a Política de Interação não ficará paralisada no máximo local.

Uma política nada mais é que um espaço de ação estatal.

Em cada etapa da iteração de política, tentamos encontrar pelo menos uma ação de estado diferente entre e e ver se . Somente se a condição for atendida, calcularemos a solução para o novo sistema de equações lineares. Π $\Pi_{n+1}$$\Pi_{n}$$\quad r_{d_n+1} + \gamma P_{d_n+1}v_n \ge r_{d_n} + \gamma P_{d_n}v_n$

Suponha que e são o ideal global e local, respectivamente.Π $\Pi^*$$\Pi^\#$

Implica,$v_* \ge v_\#$

Suponha que o algoritmo esteja travado no ideal local.

Se esse for o caso, a etapa de aprimoramento da política não será interrompida no espaço de ação de estado ideal local , pois existe pelo menos uma ação de estado em que é diferente de e gera um valor mais alto de comparado aΠ ∗ Π # v ∗ v $\Pi^\#$$\Pi^*$$\Pi^\#$$v_{*}$$v_{\#}$

ou, em outras palavras,

$[I-\gamma P_{d_*}]v_* \ge [I-\gamma P_{d_*}]v_{\#}$

$\implies r_{d_*} \ge [I-\gamma P_{d_*}]v_{\#}$

$\implies r_{d_*} + \gamma P_{d_*}v_{\#} \ge v_{\#}$

$\implies r_{d_*} + \gamma P_{d_*}v_{\#} \ge r_{d_\#} + \gamma P_{d_\#}v_\#$

Portanto, a iteração da política não para em um local ideal