Um processo de decisão de Markov (MDP) é um modelo matemático para tomada de decisão sequencial quando os resultados são incertos. É um tipo de processo de decisão estocástico, frequentemente resolvido por métodos de programação dinâmica estocástica. Originário da pesquisa operacional na década de 1950, os MDPs ganharam reconhecimento em áreas como ecologia, economia, saúde, telecomunicações e aprendizado por reforço. No aprendizado por reforço, a estrutura do MDP modela a interação entre um agente de aprendizado e seu ambiente, caracterizada por estados, ações e recompensas, fornecendo uma representação simplificada de elementos-chave dos desafios de inteligência artificial, incluindo causa e efeito, incerteza e objetivos explícitos.
O nome deriva de sua conexão com cadeias de Markov, desenvolvidas pelo matemático russo Andrey Markov. A propriedade "Markov" refere-se à estrutura subjacente em que as transições de estado dependem apenas do estado e da ação atuais, não do histórico anterior. O processo é chamado de "processo de decisão" porque envolve tomar decisões que influenciam essas transições, estendendo as cadeias de Markov à tomada de decisão sob incerteza.
Definição Formal
Um MDP é tipicamente definido como uma 4-tupla \((S, A, P_a, R_a)\), onde:
- \(S\) é o espaço de estados, que pode ser discreto ou contínuo (por exemplo, o conjunto dos números reais).
- \(A\) é o espaço de ações, com \(A_s\) denotando o conjunto de ações disponíveis a partir do estado \(s\). Esse conjunto também pode ser discreto ou contínuo.
- \(P_a(s, s')\) é a probabilidade de transição de que a ação \(a\) no estado \(s\) no tempo \(t\) leve ao estado \(s'\) no tempo \(t+1\). Para estados discretos, \(P_a(s, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)\). Para espaços de estados contínuos, a probabilidade é definida por meio de uma integral, frequentemente em relação à medida de Lebesgue.
- \(R_a(s, s')\) é a recompensa imediata (ou recompensa esperada) recebida após tomar a ação \(a\) para transitar de \(s\) para \(s'\). A recompensa é geralmente uma variável aleatória.
Uma função de política \(\pi\) é um mapeamento (potencialmente probabilístico) do espaço de estados para o espaço de ações, especificando qual ação tomar em cada estado.
Objetivo de Otimização
O objetivo em um MDP é encontrar uma política \(\pi\) que maximize uma função cumulativa de recompensas aleatórias, tipicamente a soma descontada esperada em um horizonte infinito: \(\mathbb{E}[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})]\), onde \(\gamma \in [0, 1)\) é um fator de desconto. Uma vez que uma política é fixada, o MDP se comporta como uma cadeia de Markov, pois a ação em cada estado é determinada por \(\pi(s)\).
Métodos de solução comuns incluem técnicas de programação dinâmica, como iteração de valor e iteração de política, que calculam funções de valor ou políticas ótimas. Esses métodos são fundamentais em algoritmos de aprendizado por reforço, como Q-learning e SARSA.
Aplicações
Os MDPs são amplamente aplicados em diversos domínios. Na economia, eles modelam decisões ótimas de consumo e investimento. Na saúde, guiam o planejamento de tratamento sob incerteza, como no manejo de doenças crônicas. Em telecomunicações, otimizam a alocação de recursos e o roteamento de redes. Na ecologia, informam estratégias de conservação para o manejo de espécies. Em aprendizado de máquina, os MDPs são centrais para o aprendizado por reforço, permitindo que agentes aprendam com a interação com ambientes, como visto em robótica, jogos e sistemas autônomos.
Relação com o Aprendizado por Reforço
O aprendizado por reforço (RL) usa a estrutura do MDP para formalizar a interação agente-ambiente. No RL, o agente não conhece as probabilidades de transição ou funções de recompensa antecipadamente; em vez disso, ele aprende uma política ótima por tentativa e erro, usando amostras do ambiente. Isso distingue o RL da solução clássica de MDP, que assume parâmetros do modelo conhecidos. O RL moderno, incluindo o aprendizado por reforço profundo, combina MDPs com aproximadores de função baseados em redes neurais para lidar com grandes espaços de estados, como demonstrado em aplicações como jogos e direção autônoma.
Extensões e Variações
Várias extensões abordam limitações do MDP básico. Processos de decisão de Markov parcialmente observáveis (POMDPs) lidam com situações em que o agente não pode observar diretamente o estado completo. MDPs fatorados exploram a estrutura nas variáveis de estado para melhorar a escalabilidade. MDPs multiagente estendem a estrutura para múltiplos tomadores de decisão com objetivos interativos. Essas variações mantêm a propriedade de Markov central, ao mesmo tempo que se adaptam a problemas do mundo real mais complexos.
Contexto Histórico
A formalização dos MDPs é atribuída a Richard Bellman na década de 1950, que também desenvolveu a programação dinâmica. O trabalho anterior de Andrey Markov sobre processos estocásticos forneceu a base teórica. Desde então, os MDPs se tornaram uma pedra angular da pesquisa operacional e da inteligência artificial, influenciando tanto o trabalho teórico quanto o aplicado na tomada de decisão sequencial.