Tomada de Decisão Sequencial (MDPs)

A tomada de decisão sequencial formaliza como um agente deve agir ao longo do tempo em um ambiente estocástico, utilizando processos de decisão de Markov nos quais as ações geram recompensas e alteram probabilisticamente o estado, para calcular uma política que maximize a recompensa esperada a longo prazo.

Definition

Um processo de decisão de Markov é definido por estados, ações, uma função de probabilidade de transição e uma função de recompensa; a tomada de decisão sequencial busca uma política que mapeia estados para ações que maximiza a recompensa cumulativa esperada (tipicamente descontada), dado o modelo.

Scope

Este tópico abrange o planejamento de decisão teórica ao longo do tempo: o modelo de processo de decisão de Markov (MDP) de estados, ações, probabilidades de transição, recompensas e desconto; políticas e funções de valor; as equações de Bellman que caracterizam o comportamento ótimo; e os algoritmos de programação dinâmica de iteração de valor e iteração de política para resolver um modelo conhecido. Também introduz MDPs parcialmente observáveis (POMDPs) e planejamento de estado de crença. O foco está no planejamento quando o modelo é dado; aprender uma política a partir da experiência sem um modelo conhecido é aprendizado por reforço, que pertence ao subcampo de aprendizado de máquina.

Core questions

• Como a ação ao longo do tempo sob transições estocásticas é modelada como estados, ações, transições e recompensas?
• O que a equação de otimalidade de Bellman diz sobre o valor de uma política ótima?
• Como a iteração de valor e a iteração de política calculam uma política ótima quando o modelo é conhecido?
• Como a observabilidade parcial leva a POMDPs e ao planejamento sobre estados de crença?

Key concepts

• estados, ações, transições, recompensas
• política
• função de valor
• fator de desconto
• equações de Bellman
• iteração de valor
• iteração de política
• POMDP e estado de crença

Key theories

Equação de otimalidade de Bellman

O valor ótimo de um estado é igual à melhor recompensa imediata mais o valor ótimo esperado descontado do próximo estado; esta relação recursiva caracteriza o comportamento sequencial ótimo e é a base das soluções de programação dinâmica.

Iteração de valor e de política

Para um MDP conhecido, a iteração de valor aplica repetidamente a atualização de Bellman até a convergência, e a iteração de política alterna a avaliação e a melhoria da política; ambas são garantidas para encontrar uma política ótima.

MDPs parcialmente observáveis

Quando o estado não é diretamente observável, o planejamento é feito sobre um estado de crença (uma distribuição sobre estados) atualizado a partir de observações; resolver tais POMDPs é muito mais difícil do que o caso totalmente observável, mas captura limitações de sensoriamento realistas.

Clinical relevance

A tomada de decisão baseada em MDP e POMDP sustenta a navegação e controle de robôs, gerenciamento automatizado de diálogo, decisões de manutenção e inventário, e alocação de recursos, e fornece a base de planejamento de decisão teórica sobre a qual o aprendizado por reforço se constrói quando o modelo do ambiente deve ser aprendido.

History

A tomada de decisão sequencial surgiu da programação dinâmica de Bellman (1957) e da iteração de política de Howard (1960). A monografia de Puterman de 1994 consolidou a teoria dos processos de decisão de Markov, e Kaelbling, Littman e Cassandra (1998) trouxeram os MDPs parcialmente observáveis para o mainstream da IA como um modelo para agir sob percepção incerta.

Key figures

• Richard Bellman
• Ronald A. Howard
• Martin L. Puterman
• Leslie P. Kaelbling
• Michael L. Littman

Seminal works

• bellman1957
• puterman1994
• kaelbling1998

Frequently asked questions

Como isso difere do aprendizado por reforço?

A tomada de decisão sequencial com MDPs assume que o modelo de transição e recompensa é conhecido, então uma política ótima pode ser calculada diretamente por programação dinâmica. O aprendizado por reforço aborda o caso em que o modelo é desconhecido e o agente deve aprender uma boa política a partir da experiência; ele usa o MDP como seu formalismo subjacente.

O que é um estado de crença em um POMDP?

Em um MDP parcialmente observável, o agente não consegue ver o estado verdadeiro, então ele mantém um estado de crença, uma distribuição de probabilidade sobre os estados possíveis, atualizada à medida que ele realiza ações e recebe observações. O planejamento então ocorre sobre esses estados de crença, em vez de diretamente sobre os estados ocultos.