Processo de decisão de Markov 📖 Wikipedia

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.^[1] É um tipo de processo de decisão estocástico,^[2] e é frequentemente resolvido usando os métodos da programação dinâmica estocástica.

Originário da pesquisa operacional na década de 1950,^[3][4] os MDPs desde então ganharam reconhecimento em uma variedade de campos, incluindo ecologia, economia, saúde, telecomunicações e aprendizado por reforço.^[5] 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.^[5]

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.

Um Processo de Decisão de Markov é uma 4-tupla ${\displaystyle (S,A,P_{a},R_{a})}$, onde:

• ${\displaystyle S}$ é 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.
• ${\displaystyle A}$ é um conjunto de ações chamado de espaço de ações (alternativamente, ${\displaystyle A_{s}}$ é o conjunto de ações disponíveis a partir do estado ${\displaystyle s}$). Assim como para o estado, este conjunto pode ser discreto ou contínuo.
• ${\displaystyle P_{a}(s,s')}$ é, em um nível intuitivo, a probabilidade de que a ação ${\displaystyle a}$ no estado ${\displaystyle s}$ no tempo ${\displaystyle t}$ levará ao estado ${\displaystyle s'}$ no tempo ${\displaystyle t+1}$. Em geral, esta probabilidade de transição é definida para satisfazer ${\displaystyle \Pr(s_{t+1}\in S'\mid s_{t}=s,a_{t}=a)=\int _{S'}P_{a}(s,s')ds',}$ para todo ${\displaystyle S'\subseteq S}$ 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 ${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$; caso ${\displaystyle S\subseteq \mathbb {R} ^{d}}$, a integral é usualmente pretendida em relação à Medida de Lebesgue.
• ${\displaystyle R_{a}(s,s')}$ é a recompensa imediata (ou recompensa imediata esperada) recebida após a ação ${\displaystyle a}$ ser tomada para a transição do estado ${\displaystyle s}$ para o estado ${\displaystyle s'}$. A recompensa é, em geral, uma variável aleatória.

Uma função de política ${\displaystyle \pi }$ é um mapeamento (potencialmente probabilístico) do espaço de estados (${\displaystyle S}$) para o espaço de ações (${\displaystyle A}$).

O objetivo em um processo de decisão de Markov é encontrar uma boa "política" para o tomador de decisão: uma função ${\displaystyle \pi }$ que especifica a ação ${\displaystyle \pi (s)}$ que o tomador de decisão escolherá quando estiver no estado ${\displaystyle s}$. 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 ${\displaystyle s}$ é completamente determinada por ${\displaystyle \pi (s)}$).

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

${\displaystyle E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]}$ (onde escolhemos ${\displaystyle a_{t}=\pi (s_{t})}$, ou seja, ações dadas pela política). E a esperança é tomada sobre ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

onde ${\displaystyle \ \gamma \ }$ é o fator de desconto satisfazendo ${\displaystyle 0\leq \ \gamma \ \leq \ 1}$, que geralmente é próximo de ${\displaystyle 1}$ (por exemplo, ${\displaystyle \gamma =1/(1+r)}$ para alguma taxa de desconto ${\displaystyle r}$). 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 ${\displaystyle H-}$passos. Desta vez, em vez de usar um fator de desconto ${\displaystyle \ \gamma \ }$, o agente está interessado apenas nos primeiros ${\displaystyle H}$ passos do processo, com cada recompensa tendo o mesmo peso.

${\displaystyle E\left[\sum _{t=0}^{H-1}{R_{a_{t}}(s_{t},s_{t+1})}\right]}$ (onde escolhemos ${\displaystyle a_{t}=\pi (s_{t})}$, ou seja, ações dadas pela política). E a esperança é tomada sobre ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

onde ${\displaystyle \ H\ }$ é 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 ${\displaystyle \pi ^{*}}$. 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 ${\displaystyle R_{a}(s,s')}$ é determinístico, sempre existirá uma política ótima ${\displaystyle \pi ^{*}}$ que também seja determinística.

Em muitos casos, é difícil representar as distribuições de probabilidade de transição, ${\displaystyle P_{a}(s,s')}$, 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.^[6] (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, ${\displaystyle G}$ é frequentemente usado para representar um modelo generativo. Por exemplo, a expressão ${\displaystyle s',r\gets G(s,a)}$ pode denotar a ação de amostragem a partir do modelo generativo, onde ${\displaystyle s}$ e ${\displaystyle a}$ são o estado e a ação atuais, e ${\displaystyle s'}$ e ${\displaystyle r}$ 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.

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

Neste exemplo, temos:

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

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.^[7]

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 ${\displaystyle V}$, que contém valores reais, e política ${\displaystyle \pi }$, que contém ações. Ao final do algoritmo, ${\displaystyle \pi }$ conterá a solução e ${\displaystyle V(s)}$ conterá a soma descontada das recompensas a serem ganhas (em média) ao se seguir essa solução a partir do estado ${\displaystyle s}$.

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.

${\displaystyle V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)}$

${\displaystyle \pi (s):=\operatorname {argmax} _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\}}$

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.^[8]

Na iteração de valor (Bellman 1957), que também é chamada de indução retroativa (backward induction), a função ${\displaystyle \pi }$ não é usada; em vez disso, o valor de ${\displaystyle \pi (s)}$ é calculado dentro de ${\displaystyle V(s)}$ sempre que for necessário. Substituir o cálculo de ${\displaystyle \pi (s)}$ no cálculo de ${\displaystyle V(s)}$ dá o passo combinado;^{[mais explicações necessárias]}

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},}$

onde ${\displaystyle i}$ é o número da iteração. A iteração de valor começa com ${\displaystyle i=0}$ e ${\displaystyle V_{0}}$ como um palpite da função de valor. Em seguida, ela itera, computando repetidamente ${\displaystyle V_{i+1}}$ para todos os estados ${\displaystyle s}$, até que ${\displaystyle V}$ convirja com o lado esquerdo igual ao lado direito (que é a "Equação de Bellman" para este problema^{[necessário esclarecer]}). 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,^[9] mas isso foi reconhecido apenas mais tarde.^[10]

A iteração de valor tem convergência garantida para ${\displaystyle \gamma <1}$ pelo Teorema do ponto fixo de Banach.

Na iteração de política,^[11] primeiro se executa a Determinação de Valor resolvendo para ${\displaystyle V}$ a partir do sistema linear descrito no passo um, depois se executa a Melhoria de Política computando ${\displaystyle \pi }$ 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.^[12])

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 ${\displaystyle V}$ para cada política ${\displaystyle \pi }$, o algoritmo é concluído assim que a Melhoria de Política produzir a mesma política duas vezes consecutivas.

Embora existam situações em que a iteração de política possa ser mais rápida que a iteração de valor (por exemplo, quando o espaço de ações é significativamente maior que o espaço de estados), a iteração de política costuma ser mais lenta que a iteração de valor para um grande número de estados possíveis.

Na iteração de política modificada (van Nunen 1976; Puterman & Shin 1978), o passo um é repetido várias vezes, e então o passo dois é executado uma vez.^[13][14] Depois, o passo um é novamente repetido várias vezes e assim por diante.

Nesta variante (Prioritized sweeping), os passos são aplicados preferencialmente a estados que são de alguma forma importantes – seja com base no algoritmo (houve grandes mudanças em ${\displaystyle V}$ ou ${\displaystyle \pi }$ ao redor desses estados recentemente) ou com base no uso (aqueles estados estão próximos ao estado inicial, ou são de outro modo interessantes para a pessoa ou programa que está usando o algoritmo).

Existem algoritmos para encontrar políticas ótimas com complexidade de tempo polinomial no tamanho da representação do problema para MDPs finitos. Assim, problemas de decisão baseados em MDPs pertencem à classe de complexidade P.^[15] No entanto, devido à maldição da dimensionalidade, o tamanho da representação do problema é frequentemente exponencial no número de variáveis de estado e de ação, limitando as técnicas de solução exata a problemas que têm uma representação compacta. Na prática, técnicas de planejamento online, como a busca em árvore de Monte Carlo, podem encontrar soluções úteis em problemas maiores e, em teoria, é possível construir algoritmos de planejamento online que podem encontrar uma política arbitrariamente quase ótima sem dependência da complexidade computacional no tamanho do espaço de estados.^[16]

Um processo de decisão de Markov é um jogo estocástico com apenas um jogador.

A solução acima pressupõe que o estado ${\displaystyle s}$ é conhecido no momento em que a ação deve ser tomada; caso contrário, ${\displaystyle \pi (s)}$ não pode ser calculado. Quando essa suposição não é verdadeira, o problema é chamado de processo de decisão de Markov parcialmente observável ou POMDP.

Processos de decisão de Markov restritos (CMDPs) são extensões dos processos de decisão de Markov (MDPs). Existem três diferenças fundamentais entre MDPs e CMDPs.^[17]

• Existem múltiplos custos incorridos após a aplicação de uma ação em vez de um só.
• Os CMDPs são resolvidos apenas com programas lineares, e a programação dinâmica não funciona.
• A política final depende do estado inicial.

O método dos Multiplicadores de Lagrange aplica-se aos CMDPs. Muitos algoritmos baseados em Lagrangianos foram desenvolvidos.

• Método primal-dual de gradiente de política natural.^[18]

Existem várias aplicações para CMDPs. Recentemente, foi utilizado em cenários de planejamento de movimento na robótica.^[19]

Nos Processos de Decisão de Markov de tempo discreto, as decisões são tomadas em intervalos de tempo discretos. No entanto, para os processos de decisão de Markov de tempo contínuo, as decisões podem ser tomadas a qualquer momento que o tomador de decisão escolher. Em comparação com os processos de tempo discreto, os processos de decisão de Markov de tempo contínuo podem modelar melhor o processo de tomada de decisão para um sistema que tem dinâmicas contínuas, ou seja, a dinâmica do sistema é definida por equações diferenciais ordinárias (EDOs). Esta estrutura de modelagem pode ser aplicada a áreas como sistemas de filas, processos epidêmicos e processos populacionais.

Assim como os processos de tempo discreto, nos processos de decisão de Markov de tempo contínuo, o agente busca encontrar a política ótima que maximizaria a recompensa cumulativa esperada. A diferença fundamental em relação ao caso padrão é que, devido à natureza contínua da variável tempo, a soma é substituída por uma integral:

${\displaystyle \max \operatorname {E} _{\pi }\left[\left.\int _{0}^{\infty }\gamma ^{t}r(s(t),\pi (s(t)))\,dt\;\right|s_{0}\right]}$

onde ${\displaystyle 0\leq \gamma <1.}$

Se o espaço de estados e o espaço de ações forem finitos, poderíamos usar programação linear para encontrar a política ótima, que foi uma das primeiras abordagens aplicadas. Aqui, consideramos apenas o modelo ergódico, o que significa que nosso MDP de tempo contínuo se torna uma cadeia de Markov de tempo contínuo ergódica sob uma política estacionária. Sob essa premissa, embora o tomador de decisão possa tomar uma decisão a qualquer momento no estado atual, não há benefício em tomar múltiplas ações. É melhor tomar uma ação apenas no momento em que o sistema está transitando do estado atual para outro estado. Sob algumas condições,^[20] se nossa função de valor ótima ${\displaystyle V^{*}}$ for independente do estado ${\displaystyle i}$, teremos a seguinte desigualdade:

${\displaystyle g\geq R(i,a)+\sum _{j\in S}q(j\mid i,a)h(j)\quad \forall i\in S{\text{ e }}a\in A(i)}$

Se existe uma função ${\displaystyle h}$, então ${\displaystyle {\bar {V}}^{*}}$ será o menor ${\displaystyle g}$ que satisfaz a equação acima. Para encontrar ${\displaystyle {\bar {V}}^{*}}$, poderíamos usar o seguinte modelo de programação linear:

• Programa linear primal (P-LP)

${\displaystyle {\begin{aligned}{\text{Minimizar}}\quad &g\\{\text{s.a}}\quad &g-\sum _{j\in S}q(j\mid i,a)h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}}$

• Programa linear dual (D-LP)

${\displaystyle {\begin{aligned}{\text{Maximizar}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\\{\text{s.a.}}&\sum _{i\in S}\sum _{a\in A(i)}q(j\mid i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i){\text{ e }}\forall i\in S\end{aligned}}}$

${\displaystyle y(i,a)}$ é uma solução viável para o D-LP se ${\displaystyle y(i,a)}$ for não negativo e satisfizer as restrições no problema D-LP. Uma solução viável ${\displaystyle y^{*}(i,a)}$ para o D-LP é considerada uma solução ótima se

${\displaystyle {\begin{aligned}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{aligned}}}$

para toda solução viável ${\displaystyle y(i,a)}$ do D-LP. Uma vez encontrada a solução ótima ${\displaystyle y^{*}(i,a)}$, podemos usá-la para estabelecer as políticas ótimas.

Em um MDP de tempo contínuo, se o espaço de estados e o espaço de ações forem contínuos, o critério ótimo pode ser encontrado resolvendo a equação diferencial parcial de Hamilton–Jacobi–Bellman (HJB). Para discutir a equação HJB, precisamos reformular nosso problema

${\displaystyle {\begin{aligned}V(s(0),0)={}&\max _{a(t)=\pi (s(t))}\int _{0}^{T}r(s(t),a(t))\,dt+D[s(T)]\\{\text{s.a.}}\quad &{\frac {ds(t)}{dt}}=f[t,s(t),a(t)]\end{aligned}}}$

${\displaystyle D(\cdot )}$ é a função de recompensa terminal, ${\displaystyle s(t)}$ é o vetor de estado do sistema, ${\displaystyle a(t)}$ é o vetor de controle do sistema que tentamos encontrar. ${\displaystyle f(\cdot )}$ mostra como o vetor de estado muda ao longo do tempo. A equação de Hamilton–Jacobi–Bellman é a seguinte:

${\displaystyle 0=\max _{a}(r(t,s,a)+{\frac {\partial V(t,s)}{\partial s}}f(t,s,a))}$

Poderíamos resolver a equação para encontrar a função de valor ótima ${\displaystyle V^{*}}$, que por sua vez fornece o controle ótimo a qualquer momento ${\displaystyle t}$, ${\displaystyle a(t)}$, através de ${\displaystyle a(t)={\underset {a}{\text{argmax}}}(r(t,s,a)+{\frac {\partial V^{*}(t,s)}{\partial s}}f(t,s,a)).}$

O Aprendizado por reforço é uma área interdisciplinar do aprendizado de máquina e do controle ótimo que tem, como principal objetivo, encontrar uma política aproximadamente ótima para MDPs nos quais as probabilidades de transição e recompensas são desconhecidas.^[21]

O aprendizado por reforço pode resolver processos de Decisão de Markov sem a especificação explícita das probabilidades de transição que são necessárias para realizar a iteração de política. Neste cenário, as probabilidades de transição e recompensas devem ser aprendidas a partir da experiência, ou seja, permitindo que um agente interaja com o MDP por um determinado número de passos. Tanto no nível teórico quanto no prático, o esforço é direcionado para a maximização da eficiência da amostra, ou seja, minimizar o número de amostras necessárias para aprender uma política cujo desempenho seja ${\displaystyle \varepsilon -}$próximo do ideal (devido à natureza estocástica do processo, aprender a política ótima com um número finito de amostras é, em geral, impossível).

Para os propósitos desta seção, é útil definir uma função adicional, que corresponde a tomar a ação ${\displaystyle a}$ e depois continuar de forma otimizada (ou de acordo com a política que se possui atualmente):

${\displaystyle \ Q(s,a)=\sum _{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\ }$

Embora essa função também seja desconhecida, a experiência durante o aprendizado baseia-se em pares ${\displaystyle (s,a)}$ (junto com o resultado ${\displaystyle s'}$; ou seja, "Eu estava no estado ${\displaystyle s}$, tentei fazer ${\displaystyle a}$ e aconteceu ${\displaystyle s'}$"). Assim, tem-se um array ${\displaystyle Q}$ e utiliza-se a experiência para atualizá-lo diretamente. Isso é conhecido como Q-learning.

Outra aplicação do processo MDP na teoria do aprendizado de máquina é chamada de autômatos de aprendizado. Este também é um tipo de aprendizado por reforço se o ambiente for estocástico. O primeiro artigo detalhado sobre autômatos de aprendizado foi revisado por Narendra e Thathachar (1974), que foram originalmente descritos explicitamente como autômatos de estado finito.^[22] Assim como no aprendizado por reforço, um algoritmo de autômatos de aprendizado também possui a vantagem de resolver o problema quando as probabilidades ou recompensas são desconhecidas. A diferença entre os autômatos de aprendizado e o Q-learning é que a técnica anterior omite a memória dos valores-Q, mas atualiza a probabilidade de ação diretamente para encontrar o resultado do aprendizado. Os autômatos de aprendizado são um esquema de aprendizado com uma prova rigorosa de convergência.^[23]

Na teoria dos autômatos de aprendizado, um autômato estocástico consiste em:

• um conjunto x de entradas possíveis,
• um conjunto Φ = { Φ₁, ..., Φ_s } de estados internos possíveis,
• um conjunto α = { α₁, ..., α_r } de saídas ou ações possíveis, com r ≤ s,
• um vetor de probabilidade de estado inicial p(0) = ≪ p₁(0), ..., p_s(0) ≫,
• uma função computável A que, após cada passo de tempo t, gera p(t + 1) a partir de p(t), da entrada atual e do estado atual, e
• uma função G: Φ → α que gera a saída a cada passo de tempo.

Os estados de tal autômato correspondem aos estados de um "processo de Markov de parâmetros discretos e estados discretos".^[24] A cada passo de tempo t = 0,1,2,3,..., o autômato lê uma entrada de seu ambiente, atualiza P(t) para P(t + 1) pela função A, escolhe aleatoriamente um estado sucessor de acordo com as probabilidades P(t + 1) e emite a ação correspondente. O ambiente do autômato, por sua vez, lê a ação e envia a próxima entrada para o autômato.^[23]

Além das recompensas, um processo de decisão de Markov ${\displaystyle (S,A,P)}$ pode ser compreendido em termos da Teoria das categorias. Nomeadamente, seja ${\displaystyle {\mathcal {A}}}$ o monoide livre com conjunto gerador A. Seja Dist a categoria de Kleisli da mônada de Giry. Então um funtor ${\displaystyle {\mathcal {A}}\to \mathbf {Dist} }$ codifica tanto o conjunto S de estados quanto a função de probabilidade P.

Desta forma, os processos de decisão de Markov poderiam ser generalizados de monoides (categorias com um objeto) para categorias arbitrárias. Pode-se chamar o resultado ${\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )}$ de um processo de decisão de Markov dependente de contexto, porque mudar de um objeto para outro em ${\displaystyle {\mathcal {C}}}$ muda o conjunto de ações disponíveis e o conjunto de estados possíveis.

A terminologia e a notação para MDPs não estão inteiramente consolidadas. Existem duas correntes principais — uma foca em problemas de maximização de contextos como economia, usando os termos ação, recompensa, valor e chamando o fator de desconto de β ou γ, enquanto a outra se concentra em problemas de minimização de engenharia e navegação, usando os termos controle, custo, custo a percorrer e chamando o fator de desconto de α. Além disso, a notação para a probabilidade de transição varia.

neste artigo	alternativa	comentário
ação a	controle u
recompensa R	custo g	g é o negativo de R
valor V	custo-a-percorrer (cost-to-go) J	J é o negativo de V
política π	política μ
fator de desconto γ	fator de desconto α
probabilidade de transição ${\displaystyle P_{a}(s,s')}$	probabilidade de transição ${\displaystyle p_{ss'}(a)}$

Ademais, a probabilidade de transição é por vezes escrita como ${\displaystyle \Pr(s,a,s')}$, ${\displaystyle \Pr(s'\mid s,a)}$ ou, raramente, ${\displaystyle p_{s's}(a).}$

• Bellman, R. (1957), Dynamic Programming, ISBN 978-0-486-42809-3, Princeton University Press . Edição de bolso da Dover (2003)
• Bellman., R. E. (2003) [1957]. Dynamic Programming Dover paperback ed. Princeton, NJ: Princeton University Press. ISBN 978-0-486-42809-3 
• Bertsekas, D. (1995). Dynamic Programming and Optimal Control. 2. MA: Athena 
• Derman, C. (1970). Finite state Markovian decision processes. [S.l.]: Academic Press 
• Feinberg, E.A.; Shwartz, A., eds. (2002). Handbook of Markov Decision Processes. Boston, MA: Kluwer. ISBN 9781461508052 
• Guo, X.; Hernández-Lerma, O. (2009). Continuous-Time Markov Decision Processes. Col: Stochastic Modelling and Applied Probability. [S.l.]: Springer. ISBN 9783642025464 
• Meyn, S. P. (2007). Control Techniques for Complex Networks. [S.l.]: Cambridge University Press. ISBN 978-0-521-88441-9. Cópia arquivada em 19 de junho de 2010  Apêndice contém resumo de «Meyn & Tweedie». Cópia arquivada em 18 de dezembro de 2012 
• Puterman., M. L. (1994). Markov Decision Processes. [S.l.]: Wiley 
• Ross, S. M. (1983). Introduction to stochastic dynamic programming (PDF). [S.l.]: Academic press. Consultado em 19 de janeiro de 2019. Arquivado do original (PDF) em 4 de março de 2022 
• Sutton, R. S.; Barto, A. G. (2017). Reinforcement Learning: An Introduction. Cambridge, MA: The MIT Press 
• Tijms., H.C. (2003). A First Course in Stochastic Models. [S.l.]: Wiley. ISBN 9780470864289