Processo de decisão de Markov (MDP, do inglês Markov decision process) é um modelo matemático para a tomada de decisão sequencial quando os resultados são incertos. É um tipo de processo de decisão estocástico, e é frequentemente resolvido usando os métodos da programação dinâmica estocástica.

Originário da pesquisa operacional na década de 1950, os MDPs desde então ganharam reconhecimento em uma variedade de campos, incluindo ecologia, economia, saúde, telecomunicações e aprendizado por reforço. O aprendizado por reforço utiliza a estrutura dos MDPs para modelar a interação entre um agente de aprendizado e seu ambiente. Nesta estrutura, a interação é caracterizada por estados, ações e recompensas. A estrutura MDP é projetada para fornecer uma representação simplificada de elementos-chave de desafios da inteligência artificial. Esta estrutura de modelagem incorpora a compreensão de causa e efeito, o gerenciamento de incerteza e não determinismo, e a busca de objetivos explícitos.

O nome vem de sua conexão com as Cadeias de Markov, um conceito desenvolvido pelo matemático russo Andrey Markov. O termo "Markov" em "Processo de decisão de Markov" refere-se à estrutura subjacente das transições de estado que ainda seguem a Propriedade de Markov. O processo é chamado de "processo de decisão" porque envolve tomar decisões que influenciam essas transições de estado, estendendo o conceito de uma cadeia de Markov para o reino da tomada de decisão sob incerteza.

Definição thumb|400x400px|Exemplo de um MDP simples com três estados (círculos verdes) e duas ações (círculos laranjas), com duas recompensas (setas laranjas) Um Processo de Decisão de Markov é uma 4-tupla , onde:

é um conjunto de estados chamado de espaço de estados. O espaço de estados pode ser discreto ou contínuo, como o conjunto dos números reais. é um conjunto de ações chamado de espaço de ações (alternativamente, é o conjunto de ações disponíveis a partir do estado ). Assim como para o estado, este conjunto pode ser discreto ou contínuo. é, em um nível intuitivo, a probabilidade de que a ação no estado no tempo levará ao estado no tempo . Em geral, esta probabilidade de transição é definida para satisfazer para todo mensurável. Caso o espaço de estados seja discreto, a integral é pretendida em relação à medida de contagem, de modo que esta última se simplifica como ; caso , a integral é usualmente pretendida em relação à Medida de Lebesgue. é a recompensa imediata (ou recompensa imediata esperada) recebida após a ação ser tomada para a transição do estado para o estado . A recompensa é, em geral, uma variável aleatória.

Uma função de política é um mapeamento (potencialmente probabilístico) do espaço de estados () para o espaço de ações ().

Objetivo de otimização

O objetivo em um processo de decisão de Markov é encontrar uma boa "política" para o tomador de decisão: uma função que especifica a ação que o tomador de decisão escolherá quando estiver no estado . Uma vez que um processo de decisão de Markov é combinado com uma política dessa maneira, isso fixa a ação para cada estado e a combinação resultante se comporta como uma cadeia de Markov (já que a ação escolhida no estado é completamente determinada por ).

O objetivo é escolher uma política que maximize alguma função cumulativa das recompensas aleatórias, tipicamente a soma descontada esperada ao longo de um horizonte potencialmente infinito:

(onde escolhemos , ou seja, ações dadas pela política). E a esperança é tomada sobre

onde é o fator de desconto satisfazendo , que geralmente é próximo de (por exemplo, para alguma taxa de desconto ). Um fator de desconto menor torna o tomador de decisão mais "míope", no sentido de que ele desconsidera comparativamente o efeito que seguir sua política atual tem em momentos mais no futuro.

Outro objetivo possível, mas estritamente relacionado e comumente usado, é o retorno de passos. Desta vez, em vez de usar um fator de desconto , o agente está interessado apenas nos primeiros passos do processo, com cada recompensa tendo o mesmo peso.

(onde escolhemos , ou seja, ações dadas pela política). E a esperança é tomada sobre

onde é o horizonte temporal. Comparado ao objetivo anterior, este último é mais utilizado na Teoria da Aprendizagem.

Uma política que maximiza a função acima é chamada de política ótima e é usualmente denotada por . Um MDP específico pode ter várias políticas ótimas distintas. Devido à propriedade de Markov, pode-se demonstrar que a política ótima é uma função do estado atual, conforme assumido acima. Quando é determinístico, sempre existirá uma política ótima que também seja determinística.

Assuma que é determinístico, o que significa que para as constantes o valor também é constante. Para sabe-se que existe um único ponto fixo que satisfaz a recursão de iteração de valor (equação de Bellman)

Por inspeção, note que este ponto fixo é a função de valor associada à seguinte política.

Ao desenrolar a recursão de Bellman, pode-se demonstrar que é de fato ótimo (simultaneamente para todos os estados) sobre o conjunto de políticas determinísticas.

Considere o caso onde é probabilístico, o que significa que a ação tomada é uma variável aleatória. Pode-se demonstrar que qualquer política não determinística desse tipo é dominada por uma determinística da seguinte forma.

Modelos de simulador

Em muitos casos, é difícil representar as distribuições de probabilidade de transição, , explicitamente. Nesses casos, um simulador pode ser usado para modelar o MDP implicitamente, fornecendo amostras das distribuições de transição. Uma forma comum de modelo MDP implícito é um simulador de ambiente episódico que pode ser iniciado a partir de um estado inicial e que rende um estado e recompensa subsequentes cada vez que recebe uma entrada de ação. Desta maneira, trajetórias de estados, ações e recompensas, muitas vezes chamadas de episódios, podem ser produzidas.

Outra forma de simulador é um modelo generativo, um simulador de passo único que pode gerar amostras do próximo estado e da recompensa, dado qualquer estado e ação. (Note que este é um significado diferente do termo modelo generativo no contexto da classificação estatística.) Em algoritmos que são expressos usando pseudocódigo, é frequentemente usado para representar um modelo generativo. Por exemplo, a expressão pode denotar a ação de amostragem a partir do modelo generativo, onde e são o estado e a ação atuais, e e são o novo estado e a recompensa. Comparado a um simulador episódico, um modelo generativo tem a vantagem de poder produzir dados a partir de qualquer estado, não apenas daqueles encontrados em uma trajetória.

Essas classes de modelo formam uma hierarquia de conteúdo de informação: um modelo explícito trivialmente gera um modelo generativo através da amostragem das distribuições, e a aplicação repetida de um modelo generativo gera um simulador episódico. Na direção oposta, só é possível aprender modelos aproximados através de análise de regressão. O tipo de modelo disponível para um MDP específico desempenha um papel significativo na determinação de quais algoritmos de solução são apropriados. Por exemplo, os algoritmos de programação dinâmica descritos na próxima seção exigem um modelo explícito, e a busca em árvore de Monte Carlo exige um modelo generativo (ou um simulador episódico que pode ser copiado em qualquer estado), enquanto a maioria dos algoritmos de aprendizado por reforço exige apenas um simulador episódico.

Exemplo

thumb|Exemplo do pêndulo invertido (renderização do ambiente a partir do benchmark do Open AI gym)

Um exemplo de MDP é o modelo do Pêndulo Invertido (Pole-Balancing), que advém da teoria de controle clássico.

Neste exemplo, temos:

é o conjunto de tuplas ordenadas dadas pelo ângulo do mastro, velocidade angular, posição do carrinho e sua velocidade. é , correspondendo à aplicação de uma força para a esquerda (ou direita) no carrinho. é a transição do sistema, que neste caso será determinística e impulsionada pelas leis da mecânica. é se o mastro estiver para cima após a transição, ou zero caso contrário. Portanto, essa função depende apenas de neste caso específico.

Algoritmos

Soluções para MDPs com espaços finitos de estados e ações podem ser encontradas através de uma variedade de métodos, como a programação dinâmica. Os algoritmos nesta seção se aplicam a MDPs com espaços finitos de estados e ações, probabilidades de transição e funções de recompensa dadas explicitamente, mas os conceitos básicos podem ser estendidos para lidar com outras classes de problemas, por exemplo, usando aproximação de funções. Além disso, alguns processos com espaços de estados e ações infinitos contáveis podem ser exatamente reduzidos a processos com espaços finitos de estados e ações.

A família padrão de algoritmos para calcular políticas ótimas para MDPs de estado e ação finitos requer armazenamento para dois arrays indexados por estado: valor , que contém valores reais, e política , que contém ações. Ao final do algoritmo, conterá a solução e conterá a soma descontada das recompensas a serem ganhas (em média) ao se seguir essa solução a partir do estado .

O algoritmo tem dois passos: (1) uma atualização de valor e (2) uma atualização de política, que são repetidas em alguma ordem para todos os estados até que nenhuma mudança adicional ocorra. Ambos atualizam recursivamente uma nova estimativa da política ótima e do valor do estado usando uma estimativa mais antiga desses valores.

A ordem deles depende da variante do algoritmo; pode-se também fazê-los para todos os estados de uma só vez ou estado por estado, e com mais frequência para alguns estados do que para outros. Desde que nenhum estado seja permanentemente excluído de qualquer um dos passos, o algoritmo eventualmente chegará à solução correta.

Variantes notáveis

Iteração de valor Na iteração de valor , que também é chamada de indução retroativa (backward induction), a função não é usada; em vez disso, o valor de é calculado dentro de sempre que for necessário. Substituir o cálculo de no cálculo de dá o passo combinado;

onde é o número da iteração. A iteração de valor começa com e como um palpite da função de valor. Em seguida, ela itera, computando repetidamente para todos os estados , até que convirja com o lado esquerdo igual ao lado direito (que é a "Equação de Bellman" para este problema). O artigo de 1953 de Lloyd Shapley sobre jogos estocásticos incluía, como um caso especial, o método de iteração de valor para MDPs, mas isso foi reconhecido apenas mais tarde.

A iteração de valor tem convergência garantida para pelo Teorema do ponto fixo de Banach.

O teorema do ponto fixo de Banach afirma que um dado mapeamento de contração tem um único ponto fixo; além disso, pode-se aproximar assintoticamente esse ponto fixo pela aplicação iterada do mapeamento de contração. Basta então mostrar que a iteração de valor é um mapeamento de contração, o que é demonstrado abaixo para .

Denotamos e por conveniência.

Iteração de política Na iteração de política, primeiro se executa a Determinação de Valor resolvendo para a partir do sistema linear descrito no passo um, depois se executa a Melhoria de Política computando como no passo dois, repetindo-se ambos os passos até que a política convirja. (A iteração de política foi inventada por Howard para otimizar as correspondências do catálogo da Sears, que ele vinha otimizando usando iteração de valor.Howard 2002, "Comments on the Origin and Application of Markov Decision Processes")

Uma vez que a iteração de política intercala efetivamente um problema inverso linear com uma operação não linear, ela pode ser interpretada como um tipo de método de relaxamento.

Essa variante tem a vantagem de ter uma condição de parada definida. Como existe uma solução única para cada política , o algoritmo é concluído assim que a Melhoria de Política produzir a mesma política duas vezes consecutivas.