Qual é a diferença entre iteração de valor e iteração de política?

98

Na aprendizagem por reforço, qual é a diferença entre iteração de política e iteração de valor ?

Tanto quanto eu entendo, na iteração de valor, você usa a equação de Bellman para resolver a política ótima, enquanto, na iteração de política, você seleciona aleatoriamente uma política π e encontra a recompensa dessa política.

Minha dúvida é que se você estiver selecionando uma política aleatória π em PI, como é que ela é garantida como a política ótima, mesmo se estivermos escolhendo várias políticas aleatórias.

Arslán
fonte
13
Teria sido mais apropriado fazer essa pergunta em sites como ai.stackexchange.com , stats.stackexchange.com ou datascience.stackexchange.com .
novembro

Respostas:

128

Vamos examiná-los lado a lado. As principais partes para comparação são destacadas. As figuras são do livro de Sutton e Barto: Reinforcement Learning: An Introduction .

insira a descrição da imagem aqui Pontos chave:

  1. A iteração de política inclui: avaliação de política + melhoria de política , e os dois são repetidos iterativamente até que a política converta.
  2. A iteração de valor inclui: encontrar a função de valor ideal + uma extração de política . Não há repetição dos dois porque, uma vez que a função de valor é ótima, a política gerada por ela também deve ser ótima (ou seja, convergente).
  3. Encontrar a função de valor ideal também pode ser visto como uma combinação de melhoria de política (devido ao máximo) e avaliação de política truncada (a reatribuição de v_ (s) após apenas uma varredura de todos os estados, independentemente da convergência).
  4. Os algoritmos para avaliação de política e localização da função de valor ideal são altamente semelhantes, exceto para uma operação máxima (conforme destacado)
  5. Da mesma forma, a etapa principal para a melhoria e extração de políticas são idênticas, exceto que a primeira envolve uma verificação de estabilidade.

Em minha experiência, a iteração de política é mais rápida do que a iteração de valor , pois uma política converge mais rapidamente do que uma função de valor. Lembro que isso também está descrito no livro.

Acho que a confusão veio principalmente de todos esses termos um tanto semelhantes, que também me confundiram antes.

zyxue
fonte
4
Concordo que a iteração de política converge em menos iterações e também li em vários lugares que ela é mais rápida. Fiz alguns experimentos simples de resolução de mundo de caixa e labirinto com os dois métodos no Burlap. Descobri que a iteração de valor executou mais iterações, mas levou menos tempo para atingir a convergência. YMMV.
Ryan
1
@Chrom, você deveria ter lido o oposto. Aqui está uma citação do livro, " A iteração de política frequentemente converge em surpreendentemente poucas iterações. Isso é ilustrado pelo exemplo na Figura 4.1. ", Da página 65 da versão 2017nov5 do livro.
zyxue
3
Sim, eu brinquei com vários sabores do mundo Grid. Eu estava apenas tentando apontar que "Faster" em termos de iterações provavelmente vai favorecer o PI. Mas "mais rápido" em termos de segundos pode realmente favorecer VI.
Ryan
3
Para esclarecer, a iteração de política exigirá menos iterações, mas é mais complexa computacionalmente do que a iteração de valor; qual é o mais rápido depende do ambiente.
RF Nelson
2
Eu sei que este é um post antigo. Mas eu sugiro fortemente, olhando para isso ( medium.com/@m.alzantot/… ) O link fornece um código e tornou-o muito mais claro para mim.
tandem
76

Em algoritmos de iteração de política , você começa com uma política aleatória, em seguida, encontra a função de valor dessa política (etapa de avaliação de política) e, em seguida, encontra uma nova política (aprimorada) com base na função de valor anterior e assim por diante. Neste processo, cada política tem a garantia de ser uma melhoria estrita em relação à anterior (a menos que já seja ótima). Dada uma política, sua função de valor pode ser obtida usando o operador Bellman .

Na iteração de valor , você começa com uma função de valor aleatório e então encontra uma nova função de valor (melhorada) em um processo iterativo, até atingir a função de valor ideal. Observe que você pode derivar facilmente a política ideal da função de valor ideal. Este processo é baseado no operador Bellman de otimalidade .

Em certo sentido, os dois algoritmos compartilham o mesmo princípio de funcionamento e podem ser vistos como dois casos de iteração de política generalizada . No entanto, o operador Bellman de otimalidade contém um operador máximo , que não é linear e, portanto, possui características diferentes. Além disso, é possível usar métodos híbridos entre iteração de valor puro e iteração de política pura.

Pablo EM
fonte
1
Boa descrição sobre isso. Bem, deixe-me adicionar isso na iteração de política, ela usa a equação de expectativa de Belman e na iteração de valor usa a equação máxima de Melman. Para iteração de valor, pode haver menos iterações, mas para uma iteração pode haver muito trabalho. Para a política de iteração mais iterações
Shamane Siriwardhana
não existe um operador máximo na iteração de política também? caso contrário, como atualizar a política com base na nova função de valor?
huangzonghao
Não, o algoritmo SARSA é um exemplo típico de iteração de política. Como você pode ver neste pseudo código ( incompleteideas.net/book/ebook/node64.html ), a atualização da função de valor não contém nenhum operador máximo. No entanto, se você se refere a um operador máximo para escolher as melhores ações da função de valor (ou seja, ações gananciosas), sim, há uma operação máxima nesse processo.
Pablo EM
12

A diferença básica é -

Na Iteração de Política - você seleciona aleatoriamente uma política e encontra a função de valor correspondente a ela, em seguida, encontra uma nova política (aprimorada) com base na função de valor anterior e, assim, isso levará à política ideal.

Em Iteração de valor - você seleciona aleatoriamente uma função de valor e, em seguida, encontra uma nova função de valor (aprimorada) em um processo iterativo, até atingir a função de valor ideal e, a seguir, obtém a política ideal dessa função de valor ideal.

A iteração de política funciona com base no princípio de “Avaliação de política —-> Melhoria de política”.

A iteração de valor funciona com base no princípio de “Função de valor ideal —-> política ótima”.

Himanshu Gupta
fonte
0

No que me diz respeito, ao contrário da ideia de @zyxue, VI é geralmente muito mais rápido que PI.

O motivo é muito simples, como você já sabia, a Equação de Bellman é usada para resolver a função de valor para determinada política. Uma vez que podemos resolver a função de valor para a política ótima diretamente , resolver a função de valor para a política atual é obviamente uma perda de tempo.

Quanto à sua pergunta sobre a convergência do PI, acho que você pode ignorar o fato de que se você melhorar a estratégia para cada estado de informação, você melhorará a estratégia para todo o jogo. Isso também é fácil de provar, se você estiver familiarizado com Minimização de arrependimento contrafactual - a soma do arrependimento para cada estado de informação formou o limite superior do arrependimento geral e, assim, minimizar o arrependimento de cada estado irá minimizar o arrependimento geral, que conduz à política ideal.

Response777
fonte
0

A principal diferença na velocidade é devido à operação máxima em cada iteração de iteração de valor (VI).

No VI, cada estado usará apenas uma ação (com o valor de utilidade máximo) para calcular o valor de utilidade atualizado, mas primeiro deve calcular o valor de todas as ações possíveis para encontrar essa ação por meio da Equação de Bellman.

Na iteração de política (PI), essa operação máxima é omitida na etapa 1 (avaliação de política), apenas seguindo a política intermediária para escolher a ação.

Se houver N ações possíveis, VI deve calcular a equação de bellman N vezes para cada estado e, em seguida, tirar o máximo, enquanto PI calcula apenas uma vez (para a ação declarada pela política atual).

No entanto, no PI, há uma etapa de melhoria de política que ainda usa o operador máximo e é tão lenta quanto uma etapa no VI, mas como o PI converge em menos iterações, essa etapa não acontecerá com tanta frequência quanto no VI.

bcbertyboy
fonte