Processo de Decisão de Markov

Processo de Decisão de Markov

(Parte 1 de 10)

Processos de Decisão de Markov: um tutorial

Jerônimo Pellegrini 1 Jacques Wainer 1

Resumo: Há situações em que decisões devem ser tomadas em seqüência, e o resultado de cada decisão não é claro para o tomador de decisões. Estas situações podem ser formuladas matematicamente como processos de decisão de Markov, e dadas as probabilidades dos valores resultantes das decisões, é possível determinar uma política que maximize o valor esperado da seqüência de decisões. Este tutorial descreve os processos de decisão de Markov (tanto o caso completamente observável como o parcialmente observável) e discute brevemente alguns métodos para a sua solução. Processos semi-Markovianos não são discutidos.

Palavras-chave: processos de decisão de Markov, raciocínio com incerteza, planejamento probabilístico.

Abstract: There are situations where decisions must be made in sequence, and the result of each decision is not clear to the decision maker. These situations can be formulated mathematically as Markov decision processes, and given the probabilities of each value, it is possible to determine a policy that maximizes the expected outcome of a sequence of decisions. This tutorial explains Markov decision processes (both completely observable and partially observable) and briefly discusses some methods for solving them. Semi-Markov processes (where continuous time is modeled) are not discussed.

Keywords: Markov decicion processes, reasoning under uncertainty, probabilistic planning.

1 Introdução

A tomada de decisões em seqüência é uma atividade de grande importância. O diagnóstico médico e tratamento de enfermidades é um exemplo: um médico deve escolher entre diversas ações (exames, tratamento, alta) sem ter certeza do estado atual do paciente. Mesmo após uma ação ter sido escolhida, não há também certeza de como ela influenciará o paciente (um tratamento pode resultar em cura em alguns casos, mas não em outros). O médico só recebe, após cada ação, algum sinal (o resultado de um exame, a melhoria ou não do paciente,

1Instituto de Computação, Unicamp, Caixa Postal 6176, CEP 13084-971, Campinas – SP, Brazil {jeronimo,wainer}@ic.unicamp.br

Processos de Decisão de Markov: um tutorial etc.) [1, 2]. Outros exemplos são o sistema de navegação de um robô (que deve decidir para que direção ir, contando apenas com sensores imprecisos) [3]; sistemas de ajuda online (que devem tentar ajudar o usuário ao mesmo tempo em que tentam determinar o que realmente o usuário quer) [4]; uma empresa que deve decidir periodicamente a respeito de promoções e mudanças de preço. Até mesmo um diálogo envolve tomada de ações em seqüência e incerteza [5]. Em todas estas situações, decisões precisam ser tomadas sem que haja certeza nem sobre o estado atual do mundo e nem sobre o resultado de cada ação.

Este tutorial tem como objeto de estudo os processos de decisão de Markov, que são usados para modelar situações onde é necessário executar ações em seqüência em ambientes com incerteza (tanto incerteza quanto ao resultado das ações executadas como incerteza quanto ao estado atual do ambiente). Uma situação que pode ser modelada como processo de decisão de Markov envolve um sistema com vários estados, ações que (possivelmente) modificam o estado do sistema e a possibilidade de perceber (talvez indiretamente) o resultado de cada ação executada. Dada a descrição do problema, resolvê-lo significa encontrar uma política otimal que determine a cada momento que ação tomar para maximizar a recompensa esperada (ou minimizar o custo esperado).

As seções seguintes apresentam primeiro os processos de decisão de Markov completamente observáveis, onde o estado do sistema é conhecido sempre que uma decisão é tomada, mas cada decisão tem resultado incerto. Em seguida, os processos de Markov parcialmente observáveis são apresentados. Nestes, o estado do sistema não é conhecido quando as decisões devem ser tomadas, e a única informação disponível para o tomador de decisões é a seqüência de decisões já tomadas e a seqüência de observações resultantes de cada decisão (uma observação é probabilisticamente relacionada ao estado do sistema e à decisão tomada).

2 Processos de Decisão de Markov

Um processo de decisão de Markov (MDP - Markov Decision Process) é uma forma de modelar processos onde as transições entre estados são probabilísticas, é possível observar em que estado o processo está e é possível interferir no processo periodicamente (em “épocas de decisão”) executando ações [6–8]. Cada ação tem uma recompensa (ou custo), que depende do estado em que o processo se encontra. Alternativamente, pode-se definir recompensas por estado apenas, sem que estas dependam da ação executada. São ditos “de Markov” (ou “Markovianos”) porque os processos modelados obedecem a propriedade de Markov: o efeito de uma ação em um estado depende apenas da ação e do estado atual do sistema (e não de como o processo chegou a tal estado); e são chamados de processos “de decisão” porque modelam a possibilidade de um agente (ou “tomador de decisões”) interferir periodicamente no sistema executando ações, diferentemente de Cadeias de Markov, onde não se trata de como interferir no processo. MDPs podem ser aplicados em um grande

Processos de Decisão de Markov: um tutorial número de áreas diferentes, como mostra White [9]. O exemplo a seguir é descrito por Puterman [8]:

Toda semana um revendedor de carros faz um pedido para a fábrica dizendo quantos carros ele quer (cada carro tem um custo c). A fábrica manda os carros rapidamente, de forma que podemos considerar que a entrega é imediata e que os novos carros “aparecem” imediatamente no estoque. Durante a semana ele vende k carros (k é aleatório), a um preço p cada. O revendedor tem um custo fixo para manter os carros no estoque (u por carro).

Este é um sistema que pode estar em vários estados (onde cada estado é um possível número de carros no estoque); as ações são de compra: o revendedor pode comprar diferentes quantidades de carros, e para cada quantidade temos uma ação; o revendedor não tem controle sobre quantos carros ele vende (este é um evento estocástico). Esta situação pode ser modelada como um processo de decisão de Markov.

Definição 2.1 (MDP) Um processo de decisão de Markov (MDP) é uma tupla (S,A,T,R), onde:

• S é um conjunto de estados em que o processo pode estar; • A é um conjunto de ações que podem ser executadas em diferentes épocas de decisão;

• T : S ×A×S 7→ [0,1] é uma função que dá a probabilidade de o sistema passar para um estado s′ ∈ S, dado que o processo estava em um estado s ∈ S e o agente decidiu executar uma ação a ∈ A (denotada T(s′|s,a));

• R : S ×A 7→ R é uma função que dá o custo (ou recompensa) por tomar uma decisão a ∈ A quando o processo está em um estado s ∈ S.

Pode-se também definir, para cada estado s ∈ S, um conjunto de ações possíveis naquele estado (As). Assim, o conjunto de todas as ações poderia ser A = ∪s∈SAs. Usaremos apenas “A”, a fim de simplificar a notação.

Os conjuntos S e A podem ser finitos ou infinitos. Este tutorial tratará apenas do caso em que ambos são finitos.

Definição 2.2 (Horizonte) O horizonte de um MDP é o número de épocas de decisão disponíveis para a tomada de decisões. Usaremos z para denotar o horizonte de um MDP.

O horizonte pode ser finito (quando há um número fixo de decisões a tomar), infinito (quando a tomada de decisão é feita repetidamente, sem a possibilidade de parada) ou in-

Processos de Decisão de Markov: um tutorial definido (semelhante ao horizonte infinito, mas com a possibilidade do processo parar se chegar a algum estado que tenha sido marcado como final2).

2.1 Política para um MDP

A Figura 1 mostra a dinâmica de funcionamento de um sistema modelado como processo de decisão de Markov. O tomador de decisões verifica o estado atual do sistema (s), consulta uma política (pi) e executa uma ação (a). Esta ação pode ter um efeito sobre o ambiente e modificar o estado atual. O tomador de decisões, então, verifica o novo estado para que possa tomar a próxima decisão.

pi (polıtica) ambiente s (novo estado) a (acao executada)

Figura 1. Funcionamento de um sistema modelado como MDP.

A cada época de decisão, o tomador de decisões usa uma regra de decisão para escolher a próxima ação. Uma forma simples de regra de decisão é um mapeamento direto de estados em ações (uma regra de decisão pode ser d : S 7→ A, por exemplo). O conjunto de todas as regras de decisão (uma para cada época de decisão) é chamado de política.

Normalmente se quer encontrar uma política que otimize um dado critério de desempenho das decisões. Uma política pode ser:

• Total, se cada uma de suas regras de decisão é definida para todos os estados do MDP;

• Parcial, se alguma de suas regras de decisão é definida para apenas alguns estados do MDP.

Quanto à sua relação com as épocas de decisão, uma política pode ainda ser classificada como:

• Estacionária, se a ação recomendada independe da época de decisão (ou seja, dk = dj para todo k e j).

2É possível também definir ações finais.

Processos de Decisão de Markov: um tutorial

• Não-estacionária, se a ação tomada depende da época de decisão.

Quando uma política for estacionária, pi(s) pode ser usada como sinônimo de dk(s). Apesar de ser mais comum o uso de políticas estacionárias para horizonte infinito e não- estacionárias para horizonte finito, tanto políticas estacionárias como não estacionárias podem ser usadas com qualquer horizonte: um sistema com horizonte finito pode ter a mesma política para cada época de decisão; em um sistema com horizonte infinito, pode-se mudar a política periodicamente.

Uma política pode ainda ser:

• Determinística, quando cada estado é sempre mapeado em uma única ação;

• Não-determinística (randomizada ou estocástica), quando um estado é mapeado em um conjunto de ações, sendo que cada ação tem uma probabilidade de ser escolhida.

Finalmente, uma política pode ser classificada como

• Markoviana (ou sem memória), quando a escolha da ação depende apenas do estado corrente;

• Não-Markoviana, quando a escolha da ação depende de todo o histórico de ações e estados do sistema até o momento. As regras de decisão são definidas então como funções dk : Hk 7→ A, onde Hk é o histórico de ações e estados até a época de decisão k.

Ao executar uma política, o tomador de decisões receberá recompensas em cada época de decisão. Para comparar duas políticas, é necessário um critério de desempenho (de outra forma a comparação não é possível). Pode-se definir diversos critérios de desempenho (ou “de otimalidade”) para MDPs, e entre os mais conhecidos podemos citar:

• A recompensa média por época de decisão, 1 z

A recompensa na época de decisão k é denotada por rk e γ ∈ ]0,1[ é um fator de desconto. O fator de desconto é usado com horizonte infinito para garantir a convergência do

Processos de Decisão de Markov: um tutorial valor da recompensa total esperada. Quando o horizonte é infinito, usa-se o limite no infinito

(Parte 1 de 10)

Comentários