Introdução ao algoritmo

Iteração de Política

Daniel Baptista Dias

Grupo de Planejamento, IME / USP

05 de outubro de 2012

O algoritmo

• Dado um Processo de Decisão Markoviano (MDP, do inglês Markov

Decision Process), este algoritmo tenta encontrar uma política ótima uma

aproximação no espaço de políticas

• Ele se baseia na estrutura de um MDP para encontrar esta política ótima

• Resolve problemas de horizonte infinito

• Serve de inspiração para uma série de outros algoritmos que tentam

encontrar uma política ótima através da melhoria de uma política existente

Processo de Decisão Markoviano

• Para resolver um Processo de Decisão Markoviano, consideramos a

seguinte estrutura de tupla 𝑀 = 𝑆, 𝐴, 𝑃, 𝑅 , onde:

o 𝑆 é o conjunto finito de estados possíveis do problema

o 𝐴 é o conjunto finito de ações executáveis no ambiente do

problema

o 𝑃 ∶ 𝑆 × 𝐴 × 𝑆 ↦ [0,1] é uma função de transição de estados

probabilística

o 𝑅 ∶ 𝑆 × 𝐴 ↦ ℜ é uma função que associa uma recompensa a uma

ação aplicada em um determinado estado

• Uma solução para um MDP pode ser dada pela função 𝜋 ∶ 𝑆 ↦ 𝐴, que

define qual ação será tomada dado um estado. Esta função é chamada

de política de um MDP.

Etapas do algoritmo

O algoritmo possui as seguintes etapas:

1. Atribui 𝑖 = 0 e seleciona uma política inicial aleatória 𝜋0;

2. (Avaliação da política) Dado a política aleatória 𝜋𝑖, resolve o sistema de

equações abaixo, identificando os valores da função 𝑉𝑖:

𝑉𝑖 𝑠 = 𝑅 𝑠, 𝜋 𝑠 + 𝛾 𝑃 𝑠′ 𝑠, 𝜋 𝑠 𝑉𝑖(𝑠′)𝑠′∈𝑆 , para todo 𝑠 ∈ 𝑆

3. (Melhora da política) Escolhe uma política 𝜋𝑖+1 seguindo o seguinte critério:

𝜋𝑖+1 𝑠 ∈ argmax𝑎∈𝐴𝑅 𝑠, 𝑎 + 𝛾 𝑃 𝑠′ 𝑠, 𝑎 𝑉𝑖(𝑠

′)

𝑠′∈𝑆

4. Caso 𝜋𝑖+1 = 𝜋𝑖, encerra as iterações. Caso contrário, incrementa 𝑖 em 1 e

volta para o passo 2.

Exemplo

• Problema: Robô Vigilante

o Um robô deve permanecer em um corredor de um prédio vigiando,

porém sem atrapalhar o fluxo de pessoas no corredor.

o Como as pessoas vêm da salas de reunião e trafegam a esquerda, o

robô deve dar prioridade a se locomover a direita.

o Ao tentar mudar de lugar no corredor, existe uma probabilidade de o

robô não conseguir se mover e se manter no mesmo lugar.

Exemplo

• Características do problema:

o 𝛾 = 0.9

o S = 𝑒𝑠𝑞,𝑚𝑒𝑖𝑜, 𝑑𝑖𝑟

o A = 𝑝𝑒𝑟𝑚𝑎𝑛𝑒𝑐𝑒𝑟, 𝑝𝑎𝑟𝑎𝑒𝑠𝑞, 𝑝𝑎𝑟𝑎𝑑𝑖𝑟

o R esq,∙ = −1, R meio,∙ = 0 , R dir,∙ = 4

o 𝑃, conforme a figura abaixo:

Execução do algoritmo

Primeira iteração:

• Passo 1:

o 𝑖 = 0

o 𝜋𝑖 𝑒𝑠𝑞 = 𝑝𝑒𝑟𝑚𝑎𝑛𝑒𝑐𝑒𝑟

o 𝜋𝑖 𝑚𝑒𝑖𝑜 = 𝑝𝑒𝑟𝑚𝑎𝑛𝑒𝑐𝑒𝑟

o 𝜋𝑖 𝑑𝑖𝑟 = 𝑝𝑒𝑟𝑚𝑎𝑛𝑒𝑐𝑒𝑟

• Passo 2 (avaliação da política):

o resolver:

𝑉0 𝑒𝑠𝑞 = 𝑅 𝑒𝑠𝑞, 𝜋 𝑒𝑠𝑞 + 𝛾 𝑃 𝑠′ 𝑒𝑠𝑞, 𝜋 𝑒𝑠𝑞 𝑉0(𝑠′)𝑠′∈𝑆

𝑉0 𝑚𝑒𝑖𝑜 = 𝑅 𝑚𝑒𝑖𝑜, 𝜋 𝑚𝑒𝑖𝑜 + 𝛾 𝑃 𝑠′ 𝑚𝑒𝑖𝑜, 𝜋 𝑚𝑒𝑖𝑜 𝑉0(𝑠′)𝑠′∈𝑆

𝑉0 𝑑𝑖𝑟 = 𝑅 𝑑𝑖𝑟, 𝜋 𝑑𝑖𝑟 + 𝛾 𝑃 𝑠′ 𝑑𝑖𝑟, 𝜋 𝑑𝑖𝑟 𝑉0(𝑠′)𝑠′∈𝑆

Execução do algoritmo

• Passo 2 (cont):

o transformando em números:

𝑉0 𝑒𝑠𝑞 = −1 + 0.9 1 × 𝑉0 𝑒𝑠𝑞 + 0 × 𝑉0 𝑚𝑒𝑖𝑜 + 0 × 𝑉0 𝑑𝑖𝑟

𝑉0 𝑚𝑒𝑖𝑜 = 0 + 0.9 0 × 𝑉0 𝑒𝑠𝑞 + 1 × 𝑉0 𝑚𝑒𝑖𝑜 + 0 × 𝑉0 𝑑𝑖𝑟

𝑉0 𝑑𝑖𝑟 = 4 + 0.9 0 × 𝑉0 𝑒𝑠𝑞 + 0 × 𝑉0 𝑚𝑒𝑖𝑜 + 1 × 𝑉0 𝑑𝑖𝑟

o resultando em:

𝑉0 𝑒𝑠𝑞 = −10, 𝑉0 𝑚𝑒𝑖𝑜 = 0 e 𝑉0 𝑑𝑖𝑟 = 40

• Passo 3 (melhoria da política):

o resolução para cada estado de:

𝜋1 𝑒𝑠𝑞 ∈ argmax𝑎∈𝐴𝑅 𝑒𝑠𝑞, 𝑎 + 𝛾 𝑃 𝑠′ 𝑒𝑠𝑞, 𝑎 𝑉0 𝑠

′𝑠′∈𝑆

𝜋1 𝑚𝑒𝑖𝑜 ∈ argmax𝑎∈𝐴𝑅 𝑚𝑒𝑖𝑜, 𝑎 + 𝛾 𝑃 𝑠′ 𝑚𝑒𝑖𝑜, 𝑎 𝑉0(𝑠

′)𝑠′∈𝑆

𝜋1 𝑑𝑖𝑟 ∈ argmax𝑎∈𝐴𝑅 𝑑𝑖𝑟, 𝑎 + 𝛾 𝑃 𝑠′ 𝑑𝑖𝑟, 𝑎 𝑉0(𝑠

′)𝑠′∈𝑆

Execução do algoritmo

• Passo 3 (cont):

o executando argmax𝑎∈𝐴 para 𝜋1 𝑒𝑠𝑞 :

𝑝𝑒𝑟𝑚𝑎𝑛𝑒𝑐𝑒𝑟, −1 + 0.9 1 × 𝑉0 𝑒𝑠𝑞

𝑝𝑎𝑟𝑎𝑒𝑠𝑞, −1 + 0.9 1 × 𝑉0 𝑒𝑠𝑞

𝑝𝑎𝑟𝑎𝑑𝑖𝑟, −1 + 0.9 0.3 × 𝑉0 𝑒𝑠𝑞 + 0.7 × 𝑉0 𝑑𝑖𝑟

o resultando em:

𝑝𝑒𝑟𝑚𝑎𝑛𝑒𝑐𝑒𝑟, −10

𝑝𝑎𝑟𝑎𝑒𝑠𝑞, −10

𝒑𝒂𝒓𝒂𝒅𝒊𝒓, 21.5

o assim teremos 𝜋1 𝑒𝑠𝑞 = 𝑝𝑎𝑟𝑎𝑑𝑖𝑟

o Executando para os outros estados e ações, teremos:

𝜋1 𝑒𝑠𝑞 = 𝑝𝑎𝑟𝑎𝑑𝑖𝑟, 𝜋1 meio = 𝑝𝑎𝑟𝑎𝑑𝑖𝑟 e 𝜋1 dir = permanece

Execução do algoritmo

• Passo 4

o verifica se 𝜋1 = 𝜋0

negativo, então incrementa 𝑖 para 1 e retorna ao passo 2

• Executando mais uma iteração teremos:

o 𝜋2 𝑒𝑠𝑞 = 𝑝𝑎𝑟𝑎𝑑𝑖𝑟, 𝜋2 meio = 𝑝𝑎𝑟𝑎𝑑𝑖𝑟 e 𝜋2 dir = permanece

o como 𝜋2 = 𝜋1, o algoritmo encerrará e considerará 𝜋∗ = 𝜋2