Processos de decisão de Markov e aprendizado por reforço

Um processo de decisão de Markov, ou MDP, descreve decisões repetidas quando ações podem ter resultados incertos. O agente observa seu estado atual, escolhe uma ação disponível, recebe uma recompensa e passa para um novo estado. Esses quatro componentes descrevem uma transição; uma sequência de transições descreve uma execução.

Interprete um modelo de transição

O conjunto de estados é $S$, e $A(s)$ lista as ações permitidas no estado $s$. O modelo de transição $T(s,a,s^{\mathrm{\prime }})=P(s^{\mathrm{\prime }}\mid s,a)$ fornece a probabilidade de chegar a $s^{\mathrm{\prime }}$ após executar $a$ em $s$. Para cada par estado–ação, todas essas probabilidades são não negativas e somam 1. A recompensa $R(s,a,s^{\mathrm{\prime }})$ pertence a essa transição. Uma recompensa negativa representa um custo ou uma penalidade.

Considere um robô de entrega com os estados bateria Alta, bateria Baixa e Descarregada. Descarregada encerra o episódio. Seu modelo é:

As probabilidades de cada uma das duas linhas de Trabalhar somam 1. Para Trabalhar em Baixa, a recompensa imediata esperada é $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$. Essa média é útil para o planejamento, mas uma tentativa real rende 4 ou −10. Escolher Trabalhar seleciona a distribuição; não seleciona o resultado bem-sucedido.

Inclua o passado relevante no estado

A propriedade de Markov significa que o estado e a ação atuais contêm as informações necessárias para prever o próximo estado:

O mundo pode ter uma longa história. Essa história importa por meio das variáveis incluídas no estado atual. A localização de um robô, por si só, pode ser insuficiente se sua bateria determinar o sucesso de uma tarefa. Incluir o nível da bateria permite que o modelo diferencie situações com riscos distintos.

Um MDP padrão supõe que o agente observa o estado exatamente. Se partes importantes do estado estiverem ocultas, o agente precisará de uma crença sobre os estados possíveis; isso leva a um MDP parcialmente observável, ou POMDP.

Reconheça términos e movimentos aleatórios

Um estado terminal tem valor 0 porque nenhuma recompensa vem depois dele. A recompensa ao entrar nele ainda conta: o robô recebe −10 em sua última transição para Descarregada. Tarefas episódicas terminam em um estado terminal; tarefas continuadas, como o controle contínuo de temperatura, não precisam de estado terminal.

Em um ambiente em grade, um movimento pretendido pode ter sucesso com probabilidade 0,8 e deslizar em cada direção perpendicular com probabilidade 0,1. Uma tentativa de atravessar uma parede mantém o agente no lugar. As probabilidades dos resultados que chegam à mesma casa devem ser somadas.

Transições determinísticas são um caso particular: um sucessor tem probabilidade 1. Para um início conhecido e uma tarefa adequada de alcançar um objetivo, um plano fixo pode ser suficiente. Com resultados incertos, uma política especifica como reagir em qualquer estado que de fato ocorra. Alguns textos escrevem recompensas como $R(s)$ ou $R(s,a)$; confira a convenção sobre quando a recompensa ocorre antes de adaptar uma fórmula.

Uma política descreve como o agente age. Uma política determinística e estacionária $\pi (s)$ escolhe uma ação para cada estado e mantém essa escolha ao longo do tempo. Para o robô, “Trabalhar em Alta, Carregar em Baixa” é uma dessas políticas. Uma política estocástica $\pi (a\mid s)$ atribui probabilidades às ações disponíveis.

Calcule um retorno

O retorno descontado combina as recompensas ao longo de uma execução:

A primeira transição rende $r_0$ com peso 1. Cada recompensa posterior recebe mais um fator de desconto $\gamma$. Para as recompensas −1, −1, −1 e +10 seguidas do término, usar $\gamma =\mathrm{0,9}$ fornece

Com $\gamma =\mathrm{0,5}$, a mesma execução fornece $-1-\mathrm{0,5}-\mathrm{0,25}+10(\mathrm{0,125})=-\mathrm{0,5}$. O ganho adiado perde grande parte de seu peso. O desconto pode representar uma preferência por recompensas mais cedo ou a probabilidade de o processo continuar por mais um passo.

Uma política é avaliada por seu retorno esperado, calculando-se a média de suas execuções possíveis. Uma execução de sorte não demonstra que uma política é boa. Uma política ótima ${\pi }^{\ast }$ fornece o maior retorno esperado a partir de cada estado. Um MDP finito com desconto tem uma política ótima determinística e estacionária.

Mantenha finito um futuro infinito

Para recompensas limitadas e $0\le \gamma <1$, a série geométrica limita todo retorno. Se $\mathrm{\mid }{r}_t\mathrm{\mid }\le R_{\max }$, então

A recompensa de maior módulo do robô é 10, então $\gamma =\mathrm{0,9}$ fornece $\mathrm{\mid }U\mathrm{\mid }\le 100$. Como sua maior recompensa positiva é 4, seu retorno também não pode exceder $4\mathrm{/}(1-\mathrm{0,9})=40$. Esses são limites, não afirmações de que o robô possa alcançá-los.

A quantidade $1\mathrm{/}(1-\gamma )$ é um horizonte efetivo aproximado: cerca de 10 passos para $\gamma =\mathrm{0,9}$. Ela não é um corte. Uma recompensa 10 passos depois ainda recebe peso ${\mathrm{0,9}}^{10}\approx \mathrm{0,35}$. Tarefas continuadas sem desconto exigem cuidado especial: recompensas positivas repetidas podem tornar os retornos infinitos. Um horizonte finito fixo torna a soma finita; modelos episódicos também precisam de durações de episódios adequadas para que os valores esperados sejam finitos.

Deixe que o tempo e as recompensas por passo afetem as decisões

Com um prazo, a melhor ação pode depender do tempo restante. Considere uma máquina em condição Desgastada. Operar rende 6 e a deixa Desgastada ou Quebrada com probabilidades iguais. Reparar rende −4 e a deixa em condição Boa. Em Boa, Operar rende 10; em Quebrada, Reparar rende −20. Com um passo restante, Desgastada favorece Operar: $6>-4$. Com dois passos restantes e $\gamma =\mathrm{0,9}$, Reparar fornece $-4+\mathrm{0,9}(10)=5$. Operar fornece $6+\mathrm{0,9}[\mathrm{0,5}(6)+\mathrm{0,5}(-20)]=-\mathrm{0,3}$. O tempo adicional inverte a escolha.

A recompensa por permanência de um ambiente em grade, recebida em passos não terminais, altera o custo da demora. Recompensas negativas por passo incentivam alcançar uma saída; uma penalidade maior pode tornar uma saída ruim próxima preferível a uma rota longa. Uma recompensa positiva por passo suficientemente grande pode favorecer a permanência na grade. A escolha exata também depende do desconto, das distâncias e dos riscos de deslizar.

Formular um MDP transforma um objetivo prático em decisões que um computador pode avaliar. Comece escolhendo quando as decisões acontecem. Depois defina um estado observável, ações permitidas, probabilidades de transição, recompensas, eventuais estados terminais e um desconto ou horizonte. A qualidade da política resultante depende dessas escolhas.

Modele a manutenção de máquinas

Suponha que uma máquina seja inspecionada uma vez por passo de decisão. Sua condição é Boa, Desgastada ou Quebrada. O modelo é:

Quebrada não é terminal: o reparo permite que o trabalho continue. A tarefa é continuada, com $\gamma =\mathrm{0,9}$. Observe que as ações disponíveis dependem do estado; Operar não está disponível em Quebrada.

A solução desse modelo fornece valores ótimos de aproximadamente 78,64 em Boa, 66,78 em Desgastada e 50,78 em Quebrada. Em Desgastada, Reparar tem valor $-4+\mathrm{0,9}(\mathrm{78,64})\approx \mathrm{66,78}$. Operar tem valor $6+\mathrm{0,9}[\mathrm{0,5}(\mathrm{66,78})+\mathrm{0,5}(\mathrm{50,78})]\approx \mathrm{58,90}$. A recompensa imediata negativa pelo reparo compra acesso a um futuro mais produtivo.

Escolha informações de estado suficientes

O estado deve permitir prever tanto os resultados quanto as recompensas. A posição de uma bola em movimento, por si só, omite sua velocidade, então duas posições idênticas podem levar a próximas posições diferentes. Uma posição em um jogo de tabuleiro também precisa indicar de quem é a vez. Se o tempo restante altera quais ações compensam, inclua-o em uma regra de decisão de horizonte finito ou acrescente-o ao estado.

Variáveis adicionais aumentam o espaço de estados. Dez variáveis de sim/não permitem $2^{10}=1024$ combinações. Mantenha as informações que alteram previsões ou recompensas; armazenar todo o histórico pode tornar um modelo viável desnecessariamente grande. O MDP estacionário usual supõe as mesmas regras de transição e recompensa ao longo do tempo. Um estado oculto exige um modelo de crença, enquanto oponentes estratégicos exigem um modelo de jogo.

Faça a recompensa expressar o objetivo

Um robô de limpeza recompensado por cada porção de sujeira recolhida pode lucrar espalhando e recolhendo sujeira novamente. Isso é exploração de falhas da recompensa: a otimização bem-sucedida de uma medida inadequada. Uma recompensa ligada à limpeza desejada evita esse ciclo específico. Uma recompensa esparsa pelo objetivo expressa o sucesso com clareza, mas fornece pouco retorno durante uma tentativa longa.

A modelagem da recompensa acrescenta retorno sobre o progresso. Bônus arbitrários podem alterar o objetivo. Duas comparações úteis são:

• Multiplicar todas as recompensas pelo mesmo número positivo preserva a ordem de preferência das políticas.
• Somar uma constante a toda recompensa preserva as políticas ótimas em uma tarefa continuada com desconto, pois toda política ganha a mesma constante descontada. Em uma tarefa episódica, execuções mais longas e mais curtas ganham quantias diferentes, então a ordem pode mudar.

Um termo de modelagem que preserva políticas tem a forma $F(s,a,s^{\mathrm{\prime }})=\gamma \mathrm{\Phi }(s^{\mathrm{\prime }})-\mathrm{\Phi }(s)$. Aqui $\mathrm{\Phi }$ atribui um potencial a cada estado. Com potenciais limitados em uma tarefa continuada com desconto, os termos descontados adicionados se cancelam, exceto por um deslocamento referente ao estado inicial. Para tarefas episódicas, definir todo potencial terminal como 0 elimina o termo terminal restante. Um potencial terminal diferente de zero pode alterar qual término, ou qual momento de parada, é preferido.

Um valor mede o retorno disponível a partir de uma situação sob uma determinada maneira de agir. Ele inclui recompensas futuras, ponderadas por suas probabilidades e pelo momento em que ocorrem. Isso diferencia os valores da recompensa recebida em uma única transição.

Diferencie a escolha inicial

O valor de estado $V^{\pi }(s)$ é o retorno descontado esperado ao começar no estado $s$ e seguir a política $\pi$. O valor de ação $Q^{\pi }(s,a)$ fixa a primeira ação como $a$ e depois segue $\pi$. Ele não significa executar $a$ em todos os passos posteriores.

Valores ótimos substituem essa política de continuação pelo melhor comportamento possível. Assim, $V^{\ast }(s)$ é o melhor retorno esperado a partir de $s$, e $Q^{\ast }(s,a)$ é o melhor retorno esperado depois de fixar a primeira ação. A relação entre eles é

O máximo é um número; o argumento de máximo (argmax) identifica uma ação que o alcança. Se várias ações empatarem, qualquer uma delas pode ser escolhida.

Interprete as escolhas do robô

Para o robô de entrega com $\gamma =\mathrm{0,9}$, os valores Q ótimos são:

O máximo de cada linha é o valor ótimo do estado. Alta favorece Trabalhar; Baixa favorece Carregar. Carregar rende 0 imediatamente, mas em Baixa restabelece o acesso a Alta e às suas melhores oportunidades futuras. Trabalhar em Baixa ainda tem valor Q ótimo positivo porque um robô que continua funcionando pode carregar depois.

A política de continuação importa. Sob “sempre Trabalhar”, os valores de estado caem para cerca de 8,27 em Alta e −3,48 em Baixa. O modelo não mudou; mudaram as decisões após cada resultado. Um número identificado apenas como “o valor” está incompleto, a menos que a política pretendida ou a otimalidade esteja clara.

Veja escolhas e acaso como camadas separadas

Uma árvore expectimax alterna dois tipos de nó. Em um estado, o agente seleciona uma ação; em um par estado–ação, às vezes chamado de estado Q, o acaso seleciona o próximo estado de acordo com o modelo de transição. O agente maximiza entre as ações e calcula a média dos resultados de cada uma.

Um MDP cíclico repete os mesmos estados em muitos pontos da árvore. A programação dinâmica armazena um valor para cada estado e o reutiliza. Isso evita recalcular o mesmo problema de continuação sempre que um caminho da árvore retorna a esse estado.

Extraia uma política dos valores disponíveis

Com uma tabela Q, compare os valores de ação na linha correspondente ao estado atual. Não é necessário um modelo de transição. Apenas com valores de estado, primeiro calcule a recompensa esperada de uma ação mais o valor descontado do sucessor:

Esse cálculo exige transições e recompensas. Simplesmente escolher a ação que pode alcançar o sucessor de maior valor ignora a probabilidade desse sucessor e o custo da ação. Um valor esperado alto também deixa espaço para uma execução de azar: ele descreve uma média dos resultados, não uma recompensa garantida em cada tentativa.

O retorno de uma execução pode ser dividido após sua primeira transição: a recompensa imediata mais o retorno descontado a partir do próximo estado. Calcular o valor esperado produz uma equação de Bellman. Ela relaciona o valor de um estado aos valores de seus sucessores, incluindo a possibilidade de retornar ao mesmo estado.

Avalie uma política fixa

Para uma política determinística, aparece apenas a ação escolhida por ela:

Cada ramo contribui com sua probabilidade multiplicada pela soma da recompensa imediata e do valor futuro. Há uma equação por estado. Em um MDP finito com desconto, essas equações são lineares e têm uma solução única.

Para a política “sempre Trabalhar” do robô, comece em Baixa. As duas transições possíveis fornecem

Expanda e agrupe a incógnita: $V(L)=\mathrm{2,4}+\mathrm{0,54}V(L)-4$, então $\mathrm{0,46}V(L)=-\mathrm{1,6}$. Portanto, $V(L)\approx -\mathrm{3,48}$. A recompensa −10 permanece, embora o valor futuro de Descarregada seja 0.

Em Alta, ambos os resultados rendem 4, então suas recompensas imediatas combinadas resultam em 4:

Agrupar os termos fornece $\mathrm{0,37}V(H)=4+\mathrm{0,27}V(L)$. Usar o valor de Baixa sem arredondamento resulta em $V(H)\approx \mathrm{8,27}$. Mantenha a precisão completa durante a substituição; arredonde os valores apresentados ao final.

Acrescente a escolha da ação

Para valores ótimos, calcule o valor esperado de cada ação disponível e depois escolha o melhor:

A maximização fica fora da soma porque o agente escolhe uma ação antes de ver o resultado. Escolher uma ação atual diferente para cada próximo estado possível daria ao agente informações que ele ainda não tem.

A forma de Q fixa essa primeira ação, mas permite a melhor próxima ação após observar o sucessor:

Essas equações de otimalidade contêm máximos, então uma única resolução linear para política fixa não as resolve diretamente.

Verifique valores propostos

Use os candidatos a valores ótimos do robô $V(H)\approx \mathrm{31,50}$ e $V(L)\approx \mathrm{28,35}$. Em Alta, Trabalhar fornece $4+\mathrm{0,9}[\mathrm{0,7}(\mathrm{31,50})+\mathrm{0,3}(\mathrm{28,35})]\approx \mathrm{31,50}$. Carregar fornece $\mathrm{0,9}(\mathrm{31,50})=\mathrm{28,35}$. O maior resultado coincide com o valor proposto para Alta.

Em Baixa, Trabalhar fornece $\mathrm{0,6}[4+\mathrm{0,9}(\mathrm{28,35})]+\mathrm{0,4}(-10)\approx \mathrm{13,71}$; Carregar fornece 28,35. O máximo também coincide com o valor proposto para Baixa. Verificar apenas um estado deixaria a outra equação sem teste. Pequenas diferenças são esperadas quando os valores propostos foram arredondados.

Desconte apenas o termo futuro. Substituir $R+\gamma V$ por $\gamma (R+V)$ adia incorretamente a recompensa imediata em um passo.

A avaliação de política pergunta quanto retorno esperado uma política fixa obtém. O modelo e a política são conhecidos. Nenhuma escolha de ação é melhorada durante esse cálculo; a saída é $V^{\pi }$, que pode depois apoiar uma etapa separada de melhoria.

Resolva as equações exatamente

Considere a política “Trabalhar em Alta, Carregar em Baixa” e $\gamma =\mathrm{0,9}$. Carregar em Baixa não fornece recompensa imediata e sempre leva a Alta, então $V(L)=\mathrm{0,9}V(H)$. Trabalhar em Alta fornece

Substitua a primeira equação na segunda:

Então $\mathrm{0,127}V(H)=4$, o que fornece $V(H)=4\mathrm{/}\mathrm{0,127}\approx \mathrm{31,50}$ e $V(L)\approx \mathrm{28,35}$. Isso estabelece os valores dessa política. Demonstrar que ela é ótima também exige verificar as ações concorrentes.

A avaliação exata resolve uma equação linear por estado não terminal. A eliminação padrão em matrizes densas custa uma quantidade de operações da ordem de $\mathrm{\mid }S{\mathrm{\mid }}^3$. O método é conveniente para um modelo pequeno porque as relações podem ser examinadas diretamente.

Avalie por varreduras repetidas

Uma alternativa iterativa começa com $V_0(s)=0$ e aplica a atualização para a política fixa a cada estado:

Cada novo valor usa o vetor antigo. Para “sempre Trabalhar”, as três primeiras varreduras, na ordem Alta e depois Baixa, fornecem:

Por exemplo, o segundo valor de Baixa é $\mathrm{0,6}[4+\mathrm{0,9}(-\mathrm{1,6})]+\mathrm{0,4}(-10)=-\mathrm{2,464}$. Alta, nessa mesma varredura, usa o valor antigo 4 de Alta e o valor antigo −1,6 de Baixa, fornecendo $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(-\mathrm{1,6})]=\mathrm{6,088}$.

Com desconto menor que 1, as varreduras convergem para aproximadamente 8,27 e −3,48. Uma varredura densa para uma política fixa custa uma quantidade de operações da ordem de $\mathrm{\mid }S{\mathrm{\mid }}^2$ porque cada estado soma sobre os sucessores. Modelos de transição esparsos podem ignorar sucessores com probabilidade 0.

Interprete valores intermediários

Começando em zero, $V_k(s)$ é a recompensa descontada esperada nas próximas $k$ transições sob a política fixa, sem valor além desse horizonte. A primeira varredura vê apenas recompensas imediatas. A segunda inclui mais uma transição. Esses valores intermediários têm um significado claro mesmo antes da convergência.

A atualização no próprio local usa alguns valores recém-calculados na mesma varredura. Nas condições usuais de desconto, ela também pode convergir, mas seus vetores intermediários não precisam ser iguais a esses valores síncronos de horizonte finito. Em um cálculo à mão, mantenha vetores antigos e novos separados ao comparar varreduras síncronas.

Não acrescente um máximo sobre as ações durante a avaliação. Isso permitiria que o agente mudasse seu comportamento e responderia a uma pergunta diferente daquela definida pela política fixa.

A iteração de valor pergunta repetidamente o que é melhor quando se permite mais uma decisão. Ela começa com $V_0=0$ e atualiza cada estado com sua melhor recompensa esperada mais o valor descontado do sucessor. O mesmo cálculo lida com ciclos porque os valores dos sucessores vêm de um vetor armazenado.

Faça uma varredura completa

Para cada estado não terminal, calcule

Na primeira varredura do robô, todos os termos futuros são 0. Alta compara Trabalhar com valor 4 e Carregar com valor 0, então $V_1(H)=4$. Baixa compara Trabalhar com valor $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$ e Carregar com valor 0, então $V_1(L)=0$.

A segunda varredura usa todo esse vetor antigo. Em Alta, Trabalhar fornece $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(0)]=\mathrm{6,52}$, enquanto Carregar fornece $\mathrm{0,9}(4)=\mathrm{3,6}$. Em Baixa, Trabalhar ainda fornece −1,6, enquanto Carregar fornece 3,6. Assim, $V_2=(\mathrm{6,52};\mathrm{3,6})$. Uma terceira varredura fornece aproximadamente $(\mathrm{9,08};\mathrm{5,87})$.

Se o novo valor 6,52 de Alta fosse usado imediatamente para atualizar Baixa, o resultado seria diferente. Isso seria uma atualização no próprio local, não a segunda varredura síncrona mostrada acima.

Entenda o que converge

Com inicialização em zero, $V_k$ é o retorno esperado ótimo com exatamente $k$ oportunidades de decisão restantes, permitindo que episódios terminais terminem antes. Cada varredura amplia o horizonte útil de planejamento em um passo. O operador de otimalidade de Bellman é uma contração para $\gamma <1$: o maior erro entre os estados diminui pelo menos por um fator de $\gamma$ a cada aplicação. Os valores convergem para o único $V^{\ast }$ a partir de qualquer vetor inicial finito.

Uma varredura densa considera estados, ações e sucessores, custando uma quantidade de operações da ordem de $\mathrm{\mid }S{\mathrm{\mid }}^2\mathrm{\mid }A\mathrm{\mid }$. Um desconto próximo de 1 geralmente retarda a convergência porque recompensas distantes mantêm mais peso.

Pare com um limite de erro

Seja ${\mathrm{\Delta }}_k={\max }_s\mathrm{\mid }{V}_{k+1}(s)-V_k(s)\mathrm{\mid }$. Para $0<\gamma <1$, o erro máximo do novo vetor é limitado por $\gamma {\mathrm{\Delta }}_k\mathrm{/}(1-\gamma )$. Para garantir um erro inferior a uma tolerância escolhida $\epsilon$, basta que

Para $\gamma =\mathrm{0,9}$ e tolerância 0,01, o limite é aproximadamente 0,00111. Uma mudança inferior a 0,01, por si só, não garante erro de valor inferior a 0,01. Com $\gamma =0$, uma única atualização fornece as recompensas imediatas ótimas, então não é necessária uma divisão pelo desconto.

Extraia a política

Após parar, compare os valores esperados das ações usando o vetor de valores final. Essa antecipação de um passo fornece uma política gulosa. A política pode se estabilizar antes dos valores: a política gulosa do robô a partir de $V_1$ já diz “Trabalhar em Alta, Carregar em Baixa”, mas seus valores precisam de 77 varreduras para chegar a uma distância máxima de 0,01 do par ótimo $(\mathrm{31,50};\mathrm{28,35})$.

Uma política aparentemente estável e valores precisos são verificações diferentes. A atualização deve comparar os resultados esperados de cada ação; selecionar o único sucessor possível de maior valor deixa de fora tanto o risco quanto a recompensa imediata.

A iteração de política alterna duas tarefas: medir uma política e depois melhorar suas ações usando essa medida. Comece com qualquer política determinística. Uma boa escolha inicial pode economizar trabalho, mas não é necessária para a correção em um MDP finito com desconto.

Separe avaliação de melhoria

Primeiro, calcule $V^{{\pi }_i}$, os valores da política atual. Depois, para cada estado, compare todas as ações usando esses mesmos valores:

A avaliação descreve o comportamento anterior. A melhoria pergunta se mudar a primeira ação melhoraria o retorno caso a política anterior fosse seguida depois. Alterar todas essas ações produz uma política pelo menos tão boa em todos os estados. Se a política anterior não for ótima, há uma melhoria estrita em pelo menos um estado.

Mantenha a ação atual sempre que ela empatar como a melhor. Caso contrário, ações igualmente boas podem dar a impressão de que uma política continua mudando mesmo sem melhoria de valor.

Melhore a política do robô

Comece com “sempre Trabalhar”. A avaliação exata fornece aproximadamente 8,27 em Alta e −3,48 em Baixa. Em Alta, manter Trabalhar fornece 8,27; mudar para Carregar fornece $\mathrm{0,9}(\mathrm{8,27})\approx \mathrm{7,45}$. Mantenha Trabalhar. Em Baixa, Trabalhar fornece −3,48 e Carregar fornece aproximadamente 7,45. Mude Baixa para Carregar.

Agora avalie a nova política “Trabalhar em Alta, Carregar em Baixa”. Seus valores são aproximadamente 31,50 e 28,35. Melhore novamente:

Nenhuma ação muda, então a iteração de política para. Os valores da política fixa também satisfazem as equações de otimalidade, estabelecendo que essa política é ótima. O robô precisou de duas avaliações completas a partir dessa política inicial.

Explique por que o processo termina

Um MDP finito tem apenas um número finito de políticas determinísticas. Se cada um dos $\mathrm{\mid }S\mathrm{\mid }$ estados tiver $\mathrm{\mid }A\mathrm{\mid }$ escolhas, haverá $\mathrm{\mid }A{\mathrm{\mid }}^{\mathrm{\mid }S\mathrm{\mid }}$ dessas políticas. O robô tem dois estados não terminais com duas ações cada, resultando em $2^2=4$ políticas. Com melhoria estrita sempre que necessário e tratamento consistente de empates, o processo não pode retornar a uma política pior e deve terminar.

Compare os métodos de planejamento

Avaliações completas tornam as rodadas de iteração de política mais caras, mas muitas vezes são necessárias menos rodadas. As 77 varreduras da iteração de valor e as duas avaliações de política do robô são unidades de trabalho diferentes, então as contagens, por si só, não estabelecem qual método é mais rápido. Use valores pertencentes à política atual durante cada melhoria; misturá-los com valores de uma política anterior compromete o significado dessa etapa.

No aprendizado por reforço, um agente aprende com a experiência em um problema de decisão. Ele observa um estado, escolhe uma ação disponível e recebe uma amostra $(s,a,r,s^{\mathrm{\prime }})$: o estado anterior, a ação, a recompensa e o próximo estado. O objetivo continua sendo um alto retorno esperado, mas as probabilidades de transição e as recompensas precisam ser aprendidas.

Separe aprendizado de planejamento

O planejamento usa um modelo do MDP para calcular valores ou políticas. Ele pode acontecer antes de agir ou enquanto um agente planeja novamente durante a operação. O aprendizado usa experiências observadas, seja da interação contínua, seja de um conjunto de dados coletado anteriormente. O aprendizado por reforço com dados previamente coletados ainda aprende com a experiência; ele apenas usa experiências registradas.

No aprendizado passivo, uma política é fixa e a tarefa é estimar seu desempenho. No aprendizado ativo, o agente também escolhe ações para descobrir comportamentos melhores. Essas escolhas afetam tanto a recompensa coletada quanto as informações disponíveis para atualizações futuras.

Estime transições com contagens

Um agente que aprende com base em modelo registra quantas vezes cada ação é experimentada em cada estado. Seja $N(s,a)$ a contagem dessas tentativas e $N(s,a,s^{\mathrm{\prime }})$ a contagem das tentativas que terminam em determinado sucessor. Então

As contagens no numerador dividem as tentativas do denominador entre os sucessores, então suas probabilidades estimadas somam 1. Um par não experimentado tem denominador 0 e precisa de mais experiência ou de uma escolha explícita de modelagem; ele ainda não tem uma distribuição empírica de transição.

Para o robô, Trabalhar em Alta foi experimentado 20 vezes: 13 transições permaneceram em Alta e 7 chegaram a Baixa. As estimativas são $13\mathrm{/}20=\mathrm{0,65}$ e $7\mathrm{/}20=\mathrm{0,35}$. Trabalhar em Baixa foi experimentado 10 vezes: em 7 o robô continuou funcionando e em 3 chegou a Descarregada, resultando em 0,7 e 0,3. A segunda estimativa subestima a probabilidade real de ficar descarregado, 0,4.

Registre também as recompensas de cada transição. O robô tem recompensas fixas para seus resultados. Se transições idênticas repetidas tiverem recompensas com ruído, estime a recompensa média condicional a partir das amostras observadas.

Planeje com o modelo aprendido

Use as transições e recompensas estimadas na iteração de valor ou de política. Para essas contagens do robô, com as transições de Carregar conhecidas e $\gamma =\mathrm{0,9}$, os valores ótimos estimados são aproximadamente $(\mathrm{30,42};\mathrm{27,38})$. As escolhas de ações ótimas ainda coincidem com as do modelo real: Trabalhar em Alta, Carregar em Baixa. Portanto, políticas semelhantes podem surgir de estimativas de valor diferentes.

Poucas amostras podem produzir modelos imprecisos. Mais experiências representativas melhoram as estimativas, mas coletar dados apenas sob uma política restrita pode deixar ações úteis sem experimentação. Um agente que aprende com base em modelo ainda precisa explorar.

Compare duas abordagens de aprendizado

Um modelo aprendido pode reutilizar amostras em muitas atualizações de planejamento e permitir novo planejamento quando os objetivos mudam. Ele também exige armazenamento e processamento, e erros no modelo podem distorcer o plano. Métodos sem modelo evitam construir uma tabela de transição, mas geralmente exigem muita experiência para tornar confiáveis suas estimativas de valor.

Uma política fixa pode ser avaliada sem conhecer seu modelo de transição. A avaliação direta calcula a média de retornos completos amostrados. O aprendizado por diferença temporal, ou aprendizado TD, atualiza a partir de uma única recompensa e de um valor estimado do sucessor. Ambos aprendem os valores da política com a experiência.

Calcule a média dos retornos de episódios inteiros

Siga “sempre Trabalhar” com $\gamma =\mathrm{0,9}$. Um episódio do robô é Alta → Alta (+4), Alta → Baixa (+4), Baixa → Descarregada (−10). Os retornos de suas visitas a Alta são $4+\mathrm{0,9}(4)+\mathrm{0,81}(-10)=-\mathrm{0,5}$ e $4+\mathrm{0,9}(-10)=-5$. Seu retorno em Baixa é −10.

Um segundo episódio é Alta → Baixa (+4), Baixa → Baixa (+4), Baixa → Descarregada (−10). Seu retorno em Alta é −0,5; seus retornos em Baixa são −5 e −10. As médias da avaliação por todas as visitas são, portanto, $(-\mathrm{0,5}-5-\mathrm{0,5})\mathrm{/}3=-2$ para Alta e $(-10-5-10)\mathrm{/}3\approx -\mathrm{8,33}$ para Baixa. Um método de primeira visita contaria apenas a primeira visita a um estado em cada episódio.

Essas estimativas diferem muito dos valores reais da política $(\mathrm{8,27};-\mathrm{3,48})$ porque ambos os episódios terminaram rapidamente. Retornos completos apresentam variação amostral. Com episódios concluídos suficientes e representativos, suas médias se aproximam dos retornos esperados da política. A avaliação direta espera até que o retorno necessário esteja disponível no fim do episódio e estima os estados separadamente.

Atualize após uma transição

O TD usa a estimativa atual do que vem em seguida:

O alvo é $r+\gamma V(s^{\mathrm{\prime }})$. O erro TD é o alvo menos a estimativa atual. A taxa de aprendizado $\alpha$ controla a fração desse erro usada na atualização.

Suponha $V(H)=10$, $V(L)=8$, $\gamma =\mathrm{0,9}$ e $\alpha =\mathrm{0,5}$. Após Alta → Baixa com recompensa 4, o alvo é $4+\mathrm{0,9}(8)=\mathrm{11,2}$. O erro é $\mathrm{11,2}-10=\mathrm{1,2}$, então a nova estimativa de Alta é $10+\mathrm{0,5}(\mathrm{1,2})=\mathrm{10,6}$. O valor armazenado de Baixa permanece 8 nessa atualização. Um próximo estado terminal não contribui com termo futuro.

O TD atualiza estimativas com base em outras estimativas: ele usa uma estimativa para melhorar outra. Isso transmite informações entre estados conectados e permite atualizações em tarefas continuadas, mas os primeiros alvos podem ser enviesados por estimativas ruins dos sucessores.

Controle quanto as novas evidências influenciam

Uma taxa de aprendizado alta reage fortemente a cada alvo. Com $\alpha =1$, a estimativa antiga é substituída pelo alvo mais recente. Uma taxa positiva fixa geralmente continua acompanhando o ruído das amostras. Taxas adequadamente decrescentes, com visitas repetidas e as hipóteses usuais de um modelo finito com desconto, favorecem a convergência do TD tabular. Uma taxa $1\mathrm{/}N(s)$ calcula a média da sequência de alvos TD observados; esses próprios alvos mudam à medida que as estimativas dos sucessores melhoram.

Valores de estado, por si só, não revelam a melhor ação sem informações sobre transições e recompensas para uma antecipação. O TD passivo avalia o comportamento que gera suas amostras. Aprender valores de ação dá ao agente uma maneira direta de comparar ações sem primeiro aprender um modelo.

O aprendizado Q aprende valores de ação a partir de transições observadas. Seu alvo pressupõe a melhor próxima ação, mesmo enquanto o agente escolhe ações exploratórias. Isso permite que ele aprenda a agir bem sem estimar um modelo de transição.

Substitua uma atualização esperada por uma amostra

Uma atualização Q baseada em modelo calcula a média sobre todos os sucessores possíveis:

O aprendizado Q observa um sucessor por vez. Após uma amostra $(s,a,r,s^{\mathrm{\prime }})$, ele calcula

e atualiza $Q(s,a)\leftarrow Q(s,a)+\alpha [y-Q(s,a)]$. Um sucessor terminal faz $y=r$. O máximo é calculado sobre as ações disponíveis no próximo estado, não no estado que acabou de ser deixado.

Inicialize a tabela Q, escolha uma ação com uma regra de exploração, observe o resultado, atualize a entrada selecionada e continue a partir do próximo estado. Reinicie após o término. Para usar a política aprendida, selecione uma ação que alcance o maior valor Q na linha atual.

Acompanhe duas atualizações

Sejam $\gamma =\mathrm{0,9}$ e $\alpha =\mathrm{0,5}$. Inicialmente, $Q(L,\text{Trabalhar})=5$. O robô tenta Trabalhar em Baixa e fica descarregado, com recompensa −10. O alvo é −10, então o novo valor é $5+\mathrm{0,5}(-10-5)=-\mathrm{2,5}$. Não há retorno futuro após Descarregada.

Em seguida, suponha $Q(H,\text{Trabalhar})=6$ e que o robô trabalhe em Alta, receba 4 e chegue a Baixa. Em Baixa, as estimativas são −2,5 para Trabalhar e 3 para Carregar. O melhor valor seguinte é 3, fazendo o alvo ser $4+\mathrm{0,9}(3)=\mathrm{6,7}$. O valor atualizado de Alta–Trabalhar é $6+\mathrm{0,5}(\mathrm{6,7}-6)=\mathrm{6,35}$. Essa amostra atualiza apenas essa entrada da tabela.

Diferencie o comportamento do alvo do comportamento real

O aprendizado Q é fora da política: a continuação em seu alvo é gulosa, mesmo que sua regra de seleção de ações explore. O SARSA é na política: ele usa $r+\gamma Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$ para a ação realmente escolhida em seguida.

Perto de um penhasco, um agente em exploração pode dar passos perigosos acidentalmente. O SARSA leva em conta essas ações exploratórias futuras e pode aprender uma rota mais cautelosa. O aprendizado Q tem como alvo a continuação gulosa e pode favorecer uma rota mais curta pela borda, mesmo enquanto a exploração torna arriscados seus trajetos de treinamento.

Apresente a garantia tabular com precisão

Em um MDP estacionário finito com recompensas limitadas e $\gamma <1$, o aprendizado Q tabular converge para $Q^{\ast }$ com probabilidade 1 quando todo par estado–ação recebe infinitas atualizações e suas taxas de aprendizado satisfazem

Uma taxa por par $1\mathrm{/}N(s,a)$ tem essa forma. Uma taxa $1\mathrm{/}N(s,a{)}^2$ diminui rápido demais: sua soma total é finita, então ela pode deixar ajustes insuficientes para eliminar um erro inicial. Um ajuste total infinito impede que o aprendizado pare cedo demais; um ajuste quadrático finito controla o ruído acumulado. Taxas constantes geralmente mantêm oscilações em tarefas estocásticas. Essas são condições no limite, portanto um treinamento finito ainda precisa ser avaliado.

Explotação seleciona a ação que parece melhor no momento. Exploração reúne informações que podem revelar uma escolha melhor. Se uma tentativa inicial malsucedida de Trabalhar fizer o robô preferir Carregar em Alta, a explotação pura poderá mantê-lo carregando para sempre e deixar a estimativa de Trabalhar sem correção.

Conte corretamente o ramo aleatório

Uma regra épsilon-gulosa explora uniformemente com probabilidade $\epsilon$ e, caso contrário, escolhe uma ação gulosa. Suponha que haja uma ação gulosa entre quatro e $\epsilon =\mathrm{0,2}$. Sua probabilidade de seleção é $\mathrm{0,8}+\mathrm{0,2}\mathrm{/}4=\mathrm{0,85}$. Cada outra ação tem probabilidade 0,05. O ramo aleatório também inclui a ação gulosa.

Pouca exploração no início do treinamento pode deixar ações úteis sem teste; muita exploração no fim do treinamento continua sacrificando recompensa. Um cronograma pode tornar-se guloso no limite e ainda experimentar cada par relevante infinitas vezes. Essa propriedade GLIE é mais forte do que simplesmente reduzir épsilon, e a possibilidade de alcançar os estados importa para que todos sejam visitados.

Favoreça ações com poucas evidências

Uma função de exploração pode acrescentar um bônus a uma estimativa de valor. Com $f(u,n)=u+k\mathrm{/}n$ para uma ação experimentada, escolha a ação com a maior pontuação. Dê prioridade a ações não experimentadas, por exemplo, com pontuação $+\mathrm{\infty }$. Com $k=10$, um valor 5 experimentado 20 vezes recebe pontuação 5,5; um valor 4 experimentado duas vezes recebe 9. A ação menos experimentada é selecionada apesar de sua estimativa atual menor.

O bônus também pode entrar em um alvo de atualização: $r+\gamma {\max }_{a^{\mathrm{\prime }}}f(Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }}),N(s^{\mathrm{\prime }},a^{\mathrm{\prime }}))$. Isso propaga a atratividade de ações não exploradas para estados anteriores. Valores Q iniciais otimistas também podem incentivar a experimentação de ações cujas estimativas ainda não foram corrigidas pela experiência.

Use um limite de confiança para problemas do bandido

Um problema do bandido de múltiplos braços tem um estado de decisão e vários braços com recompensas médias fixas e desconhecidas. Cada acionamento ensina ao agente sobre a distribuição de recompensas de um braço. O UCB1 supõe sorteios independentes de recompensas limitadas, com uma distribuição fixa por braço; reescale as recompensas para o intervalo de 0 a 1. Acione cada braço uma vez e depois escolha a maior pontuação

Aqui ${\bar{x}}_j$ é a média amostral do braço $j$, $n_j$ é sua contagem de acionamentos e $N$ é a contagem total entre os braços. O bônus cresce para braços pouco amostrados. Com médias de 0,6 e 0,5 após 10 e 2 acionamentos, $N=12$. As pontuações são aproximadamente 1,30 e 2,08, então o segundo braço é selecionado. A pontuação pode exceder 1 mesmo que as recompensas observadas não possam: ela é um índice de decisão, não uma recompensa observada.

Meça o custo do aprendizado

O arrependimento compara a recompensa coletada com o que escolhas ótimas teriam rendido. Em um problema do bandido estacionário com um braço realmente inferior, um épsilon positivo fixo continua selecionando esse braço a uma taxa positiva, produzindo arrependimento esperado linear. Sob suas hipóteses de problema do bandido estocástico, o UCB1 tem arrependimento esperado logarítmico. Um cronograma de épsilon decrescente cuidadosamente ajustado também pode alcançar essa ordem; uma redução arbitrária não pode garanti-la.

O alvo fora da política do aprendizado Q permite amostras exploratórias sem redefinir os valores ótimos buscados. A exploração ainda afeta a recompensa coletada durante o treinamento. Em sistemas físicos, use simulação, experiência registrada ou limites para as ações permitidas para evitar que a exploração cause danos.

Uma tabela Q armazena um número para cada par estado–ação. Em um problema grande, muitos pares talvez nunca sejam visitados. Entradas separadas também não compartilham evidências entre situações semelhantes. O aprendizado Q aproximado substitui a tabela por uma função de características.

Represente valores com uma soma ponderada

Uma característica $f_i(s,a)$ é um número que descreve um aspecto do estado e da ação. Para um robô de entrega, características poderiam descrever o nível da bateria, a distância até um carregador e os pacotes aguardando entrega. Uma aproximação linear é escrita como

Os pesos $w_i$ descrevem a intensidade com que cada característica contribui. As características podem depender tanto da ação quanto do estado, permitindo que escolhas diferentes no mesmo estado tenham valores diferentes.

Atualize cada peso a partir de um erro

Calcule o valor Q atual e depois o alvo $y=r+\gamma {\max }_{a^{\mathrm{\prime }}}Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$. A diferença $\delta =y-Q(s,a)$ orienta cada atualização:

Todos os valores usados para o alvo e o erro vêm dos pesos anteriores à atualização. Uma característica igual a zero não altera seu peso. Uma característica diferente de zero dimensiona o ajuste, incluindo seu sinal.

Para pesos $(1;-\mathrm{0,5})$ e características atuais $(1,2)$, a estimativa é $1(1)+(-\mathrm{0,5})(2)=0$. Suponha que a recompensa seja 4, o melhor próximo valor Q seja 4 e $\gamma =\mathrm{0,9}$. O alvo é $4+\mathrm{0,9}(4)=\mathrm{7,6}$, então $\delta =\mathrm{7,6}$. Com $\alpha =\mathrm{0,1}$:

A nova estimativa para as mesmas características passa a ser $\mathrm{1,76}+\mathrm{1,02}(2)=\mathrm{3,8}$. Uma atualização de pesos compartilhados não equivale a substituir uma entrada independente da tabela pelo alvo.

Entenda o alcance e os limites do compartilhamento

Um peso participa de muitas previsões. Atualizá-lo altera os valores de todos os pares com valor diferente de zero para essa característica. Isso é generalização e pode ajudar o agente a agir de modo sensato em estados não vistos. Também pode propagar uma atualização equivocada.

Se duas situações tiverem vetores de características idênticos para cada ação correspondente, o modelo terá de atribuir a elas valores de ação idênticos. Se elas exigirem ações diferentes, nenhum ajuste de pesos poderá representar corretamente ambas as decisões. São necessárias características melhores ou uma função mais rica. O aprendizado tabular é o caso particular com uma característica indicadora para cada par estado–ação, ativa apenas para esse par.

A garantia de convergência do aprendizado Q tabular não se estende à aproximação arbitrária de funções. A atualização de estimativas com base em outras estimativas fora da política, com previsões compartilhadas, pode oscilar ou divergir, então avalie a política aprendida em testes separados. Redes Q profundas aprendem características a partir de entradas como pixels de uma tela de jogo; a busca no espaço de políticas, por sua vez, ajusta diretamente uma política para aumentar o retorno.