INTRODUÇÃO PROGRAMAÇÃO DINÂMICA - PROCESSOS MARKOVIANOS

Prévia do material em texto

Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP
UNIVERSIDADE FEDERAL DO CEARA´ - OPL
21 de outubro de 2019
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 1 / 38
Conteu´do
1 Introduc¸a˜o
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 2 / 38
Conteu´do
1 Introduc¸a˜o
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 3 / 38
Introduc¸a˜o
Programac¸a˜o dinaˆmica e´ um me´todo algor´ıtmico usado para resolver
problemas em que ac¸o˜es (deciso˜es) sa˜o aplicadas por um determinado
per´ıodo de tempo.
Estes me´todos tem por base modelos de decisa˜o sequencial
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 4 / 38
Modelo de decisa˜o sequencial
Definic¸a˜o (MDS)
Em um ponto espec´ıfico no tempo, um decisor, agente ou controlador
observa o estado do sistema. Baseado neste estado, o agente escolhe uma
ac¸a˜o. A ac¸a˜o escolhida produz dois resultados: o sistema recebe uma
recompensa e o sistema evolui para um novo estado.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 5 / 38
Modelo de decisa˜o sequencial
Definic¸a˜o (MDS Estoca´stico)
Descrevemos um modelo de decisa˜o sequencial probabil´ıstico como aquele
em que o sistema evolui para um novo estado num ponto subsequente no
tempo de acordo com a distribuic¸a˜o de probabilidade determinada dada a
ac¸a˜o escolhida e o estado antecessor.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 6 / 38
Componentes chaves de um MDS
Conjunto de e´pocas de decisa˜o:
Conjunto de estados do ambiente
Conjunto de ac¸o˜es disponiveis no estado
Conjunto de recompensas (penalidades)
Conjunto de probabilidades de transic¸a˜o0
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 7 / 38
Markov Decision Processes - MDP
Definic¸a˜o
Um MDP consiste em um conjunto de estados, conjunto de ac¸o˜es
dispon´ıveis ao agente, recompensas e um func¸a˜o de probabilidade de
transic¸a˜o que depende apenas do atual estado e ac¸a˜o e na˜o das ac¸a˜os e
estados registrados no passado.
MDP’s sa˜o uma formalizac¸a˜o cla´ssica da tomar deciso˜es sequencialmente,
onde ac¸o˜es influenciam na˜o apenas a recompensa imediata, mas tambe´m
nas situac¸o˜es subsequentes, ou estados subsequentes, por meio de futuras
recompensas.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 8 / 38
Interface agente-ambiente
O agente e o ambiente iteragem em cada sequeˆncia discreta de etapas
de tempos (e´pocas de decisa˜o) t = 0,1,2,... .Em cada instante t, o
agente recebe uma representac¸a˜o do estado do ambiente, St ∈ S, com
base nisto, seleciona uma ac¸a˜o, At ∈ A(s). No instante de tempo a`
frente, em parte como uma consequeˆncia desta ac¸a˜o, o agente recebe uma
recompensa nume´rica, Rt+1 ∈ R ⊂ R, e passa a se encontrar em um
novo estado, St+1.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 9 / 38
MDP Finito
Definic¸a˜o
Em um Processo de Decisa˜o de Markov finito, os conjuntos de estados,
ac¸o˜es e recompensas (S,A,R) sa˜o todos finitos.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 10 / 38
E´pocas de decisa˜o
Deciso˜es sa˜o feitas em pontos de tempo referidas como e´pocas de
decisa˜o. Denotemos T como o conjunto de e´pocas de decisa˜o. Pode ser
discreto ou cont´ınuo. Quando discreto, as deciso˜es sa˜o feitas sobre todas
as e´pocas de decisa˜o.
Quando N e´ finito, chamamos o problema de horizonte finito, caso
contra´rio, chamamos de horizonte infinito
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 11 / 38
Conjuntos de estados e ac¸o˜es
Em cada e´poca de decisa˜o, o ambiente ocupa um estado. Se, em algum
e´poca de decisa˜o, o agente observa o ambiente no estado s ∈ S, ele pode
escolher uma ac¸a˜o a dentre as ac¸o˜es permitidas para o estado s,A(s).
Seja A = ∪s∈SA(s)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 12 / 38
Conjunto de estados e ac¸o˜es
Em MDP finito, as varia´veis aleato´rias, Rt+ e St+ sa˜o definidas por meio
de distribuic¸o˜es de probabilidade discreta que dependem apenas do estado
e ac¸a˜o antecessor.
Para um particulares valores destas varia´veis aleato´rias, s ′ ∈ S e r ∈ R,
existe uma probabilidade desses valores que ocorrem no instante t+1,
dado particulares valores do estado e ac¸a˜o precedente:
p(s ′, r |s, a) = P(St+ = s ′, Rt+ = r |St = s ′, At = a) (1)
∀s ′, s ∈ S, r ∈ R, a ∈ A(s)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 13 / 38
Conjunto de estados e ac¸o˜es
Para um particulares valores destas varia´veis aleato´rias, s ′ ∈ S e r ∈ R,
existe uma probabilidade desses valores que ocorrem no instante t+1,
dado particulares valores do estado e ac¸a˜o precedente:
p(s ′, r |s, a) = P(St+ = s ′, Rt+ = r |St = s ′, At = a)
∀s ′, s ∈ S, r ∈ R, a ∈ A(s)
A func¸a˜o p(s ′, r |s, a) e´ definida como a dinaˆmica do MPD.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 14 / 38
Conjunto de estados e ac¸o˜es
Definic¸a˜o (Func¸a˜o de transic¸a˜o)
Pass′ = P(St+ = s
′|St = s ′, At = a) (2)
Definic¸a˜o (Recompensa esperada)
Rass′ = E[Rt+|St = s ′, At = a, St = s] (3)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 15 / 38
Objetivo e Recompensa
O propo´sito ou objetivo do agente e´ formalizado em termos de uma sinal
especial, chamado de recompensa. Em cada t ∈ T , a recompensa e´ um
nu´mero, Rt ∈ R.
Informalmente, o objetivo do agente e´ maximizar o total acumulado de
recompensas recebidas. Isto significa maximizar na˜o a recompensa
imediata, mas a recompensa acumulada ao longo do tempo.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 16 / 38
Retornos
Considere a sequeˆncia de recompensas recebidas apo´s o instante t como
Rt, Rt+, Rt+, Rt+, .... Em geral, nos queremos maximizar o retorno
esperado,onde o retorno, denotado por Gt, e´ definido como alguma
func¸a˜o espec´ıfica da sequeˆncia de recompensas.
Gt = Rt + Rt+1 + Rt+2 + Rt+3, ... (4)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 17 / 38
Retornos
Um conceito adicional que precisamos e´ o discounting. De acordo come
esta te´cnica, o agente tenta seleciona ac¸o˜es tal que a soma dos descontos
das recompensas recebida sobre o futuro e´ maximizada.
Gt = Rt + γRt+1 + γ
2Rt+2 + γ
3Rt+3... =
∞∑
k=0
γkRt+k+1 (5)
Onde γ e´ uma paraˆmetro, 0 ≤ γ ≤ 1, e´ chamado de taxa de desconto. A
taxa de desconto determina o valor presente de uma recompensa futura.
Se γ = 0 dizemos que o agente e´ ”m´ıope”.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 18 / 38
Pol´ıtica e Func¸a˜o Valor
Definic¸a˜o(Pol´ıtica)
Formalmente, um pol´ıtica e´ um mapa entre os estados e as probabilidades
de selecionar cada ac¸a˜o dispon´ıvel. Se o agente segue a pol´ıtica pi no
instante t, enta˜o, pi(s, a) e´ a probabilidade de At = a se St = a
pi(s, a) = P(At = a|St = s) (6)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 19 / 38
Pol´ıtica e Func¸a˜o Valor
Definic¸a˜o(Func¸a˜o Valor Estado)
E´ uma func¸a˜o dos estados que estimam qua˜o ”bom”e´ para o agente estar
em um dado estado. A func¸a˜o valor de um estado s sob a pol´ıtica pi,
denotado por V pi(s) e´ o retorno esperado comec¸ando em s e sequindo a
pol´ıtica pi.
V pi(s) = Epi[Gt |St = s] = Epi
[ ∞∑
k=0
γkRt+k+1|St = s
]
,∀s ∈ S (7)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 20 / 38
Pol´ıtica e Func¸a˜o Valor
Definic¸a˜o(Func¸a˜oValor Estado-Ac¸a˜o)
Similarmente, definimos o valor de dado a ac¸a˜o a no estado s sob a
pol´ıtica pi, denotado por Qpi(s) como o retorno esperado comec¸ando em s,
tomando a ac¸a˜oa e sequindo a pol´ıtica pi.
Qpi(s) = Epi[Gt |St = s,At = a] = Epi
[ ∞∑
k=0
γkRt+k+1|St = s,At = a
]
(8)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 21 / 38
Programac¸a˜o Dinaˆmica
Definic¸a˜o (DP)
O termo programac¸a˜o dinaˆmica refere-se a uma colec¸a˜o de algoritmos que
podem ser usados para computar pol´ıticas o´timas dado um modelo do
ambiente como por exemplo um MDP.
A ideia centra de DP, e´ usar func¸a˜o valor para organizar e estruturar a
busca de boas pol´ıticas. Assim, podemos ”facilmente”obter pol´ıticas
o´timas um vez que tenhamos obtido a func¸a˜o valor o´tima.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 22 / 38
Programac¸a˜o Dinaˆmica
Definic¸a˜o (Pol´ıtica O´tima)
Uma pol´ıtica pi e´ definida como sendo melhor ou igual que a pol´ıtica pi′ se
o retorno esperado e´ maior ou igual que o de pi′ para todos os estados. Em
outras palavras, pi ≥ pi′, somente se V pi(s) ≥ V pi′(s).
Definic¸a˜o (func¸a˜o Valor O´tima)
Existe uma func¸a˜o valor o´tima se, somente se existe uma pol´ıtica o´tima.
Portanto, a func¸a˜o valor o´tima e´ dada por:
V ∗(s) = max
pi
V pi(s), ∀s ∈ S (9)
Q∗(s, a) = max
pi
Qpi(s, a), ∀s ∈ S, a ∈ A(s) (10)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 23 / 38
Func¸a˜o Valor o´tima
V ∗(s) = max
pi
V pi(s),∀s ∈ S (11)
V ∗(s) = max
a∈A(s)
∑
s′
Pass′ [R
a
ss′ + γV
∗(s ′)] (12)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 24 / 38
Func¸a˜o Valor o´tima
Q∗(s) = max
pi
Qpi(s, a) (13)
Q∗(s) =
∑
s′
Pass′ [R
a
ss′ + γmax
a′
V ∗(s ′)] (14)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 25 / 38
Exemplo(Processo de decisa˜o markoviano de 2 estados)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 26 / 38
Exemplo(Processo de decisa˜o markoviano de 2 estados)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 27 / 38
Programac¸a˜o Dinaˆmica
As classes de algoritmos de DP podem ser divididas em 3 subclasses:
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 28 / 38
Iterac¸a˜o de Pol´ıtica
Uma vez que uma pol´ıtica pi foi melhorada usando V pi para gerar uma
pol´ıtica melhor, pi′ podemos calcular V pi′ aprimora´-la novamente para
gerar uma pol´ıtica ainda melhor pi′′
Avalia a pol´ıtica ao construir sua func¸a˜o valor, e usa a func¸a˜o valor para
encontrar novas pol´ıticas melhoradas.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 29 / 38
Iterac¸a˜o de Pol´ıtica - Avaliac¸a˜o da Pol´ıtica
Primeiramente, consideramos calcular a func¸a˜o valor V pi(s) para uma
pol´ıtica arbitra´ria pi. Chamamos isto de avaliac¸a˜o da pol´ıtica (policy
envaluation). Comumente, nos referimos como problema de predic¸a˜o.
V pi(s) = Epi[Gt |St = s]
V pi(s) = Epi
[ ∞∑
k=0
γkRt+k+1|St = s
]
V pi(s) = Epi [Rt+1 + γV pi(St+1)|St = s]
V pi(s) =
∑
a
pi(s, a)
∑
s′
Pass′
[
Rass′ + γV
pi(s ′)
]
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 30 / 38
Iterac¸a˜o de Pol´ıtica - Avaliac¸a˜o da Pol´ıtica
Para nosso propo´sito, me´todos de soluc¸a˜o iterativa sa˜o mais adequados.
Considere uma sequeˆncia de func¸a˜o valor aproximadas V0,V1,V2, .... A
aproximac¸a˜o inicial V0 e´ escolhida arbitrariamente, e cada sucessiva
aproximac¸a˜o e´ obtida usando a equac¸a˜o de Bellman como regra de
atualizac¸a˜o:
V k+1(s) =
∑
a
pi(s, a)
∑
s′
Pass′
[
Rass′ + γV
k(s ′)
]
(15)
A sequeˆncia converge para V pi(s) quando k →∞ sob certas condic¸o˜es
que garatem a existeˆncia da func¸a˜o.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 31 / 38
Iterac¸a˜o de Pol´ıtica - Melhoria da Pol´ıtica
O propo´sito nesta etapa, e´ obter, por meio da func¸a˜o valor, uma pol´ıtica
que produza um resultado para esta func¸a˜o ta˜o bom quanto o gerado pela
pol´ıtica atual.
pi′ = argmin
a
∑
s′
Pass′ [R
a
ss′ + γV
∗(s ′)] (16)
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 32 / 38
Iterac¸a˜o de Pol´ıtica - Algoritmo
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 33 / 38
Iterac¸a˜o de Valor
Uma desvantagem da iterac¸a˜o de pol´ıtica e´ que cada uma de suas iterac¸o˜es
envolve avaliac¸a˜o de pol´ıtica, que por si so´ pode ser uma computac¸a˜o
iterativa prolongada que requer va´rias varreduras no conjunto de estados.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 34 / 38
Iterac¸a˜o de Valor - Algoritmo
A convergeˆncia mais ra´pida e´ frequentemente alcanc¸ada interpondo va´rias
varreduras de avaliac¸a˜o de pol´ıticas entre cada varredura de aprimoramen-
to de pol´ıticas
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 35 / 38
Dificuldades
Para aplicar estas te´cnicas de DP, precisamos de todo o conhecimento
do ambiente, ou seja, do modelo que o descreve. Se esse na˜o for o
caso, podemos fazer uso das te´cnicas de Reinforcement Learning, que
resolve a mesma problema´tica, sem necessariamente conhecer o
modelo.
As maldic¸o˜es da dimensionalidade.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 36 / 38
Refereˆncias I
Andrew G. Barto Richard S. Sutton.
Reinforcement Learning: An introduction.
Warren B. Powell.
Approximate Dynamic
ProgrammingSolvingtheCursesofDimensionality .
Alborz Geramifard.
A Tutorial on Linear Function Approximators for Dynamic
Programming and Reinforcement Learning.
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 37 / 38
Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP
UNIVERSIDADE FEDERAL DO CEARA´ - OPL
21 de outubro de 2019
(OPL - UFC) Introduc¸a˜o a` Programac¸a˜o Dinaˆmica - DP 21 de outubro de 2019 38 / 38
	Introdução