PROGRAMACAO_DINAMICA_APROXIMADA

Prévia do material em texto

38
3 PROGRAMAÇÃO DINÂMICA APROXIMADA
3.1 A necessidade de aproximação em programação dinâmica
No capítulo 2, foram apresentados os fundamentos da programação dinâmica clássica,
cujas técnicas envolvem computar exatamente a função de valor para cada estado viável. Porém,
algoritmos tradicionais, tais como programação dinâmica reverso (horizonte finito), iteração de
política e iteração de valor (horizonte infinito), podem não ser suficientes para encontrar uma
solução exata dentro de um tempo razoável. Note que estes algoritmos requerem pelo menos três
laços de repetição aninhados: o primeiro sobre todos os estados, o segundo sobre todas as ações,
e o terceiro sobre todos os estados futuros (POWELL, 2012). Tal exigência computacional é
intensivamente custosa nos casos em que o espaço das variáveis do sistema é consideravelmente
grande.
Inevitavelmente, em muitos dos problemas reais, o espaço de estados pode ser imenso,
e os processos de informação exógena podem ser desconhecidos, de modo que a estocasticidade
do sistema ocorre às cegas. Tal cenário faz surgir um dos principais impasses da programação
dinâmica tradicional, que é o fato da equação de otimalidade de Bellman não ser aplicável para
todos os problemas, uma vez que é afetada pelas maldições da dimensionalidade (veja 2.6).
Uma alternativa a estas limitações computacionais está em reunir todas as proprie-
dades vantajosas da PD e combiná-las a técnicas de aproximação de funções e simulação para
aliviar as maldições da dimensionalidade associadas a abordagem clássica (WANG et al., 2009).
Em resposta a impossibilidade de computar a equação de Bellman em algumas configurações,
subcomunidades da ciência da computação, teoria de controle e pesquisa operacional por meio
de seus esforços, inicialmente de forma independente, propuseram soluções aproximadas para
problemas de decisão sequencial. Um vez que as pequisas foram desenvolvidas sem que houvesse
muita interseção entre as subcomunidades cientificas interessadas, não há uma unificação formal
de notação ou um nome específico que se dê a área de pesquisa em aproximação de funções
em programação dinâmica (POWELL, 2012). Assim, este campo tem se desenvolvido sob os
nomes de programação dinâmica aproximada ou adaptativa (approximate dynamic programming
- Programação dinâmica aproximada (PDA)), aprendizagem por reforço (reinforcement learning
- RL), programação neuro-dinâmica (neuro-dynamic programming) e programação dinâmica
heurística (heuristic dynamic programming). Estes campos são iguais no seu propósito, mas
diferentes em sua execução, embora estas diferenças sejam tão sutis que às vezes é difícil
39
percebê-las.
Neste trabalho, será feito uso do framework desenvolvido pela comunidade da PDA.
A justificativa está em que as aplicações que serão feitas são do campo da pesquisa operacional,
comunidade que contribui e adota as técnicas da PDA.
3.2 Ideia base para aproximação
Resolver um problema de programação dinâmica envolve computar a equação de
otimalidade de Bellman, dada por
Vt(St) = max
xt∈Xt
{Ct(St, xt) + γE {Vt+1(St+1)|St}} . (3.1)
Em PD exata, a função de valor é computada exatamente retrocedendo no horizonte de decisão.
Tal comportamento fica bem evidente no algoritmo de programação dinâmica reverso (Algoritmo
1). Em PDA, a estratégia é diferente. Os passos são dados avançando no tempo, de modo que
são feitas simulações sobre o futuro e as decisões são tomadas aproximadamente. Portanto, a
equação de Bellman, no contexto aproximado, assume a seguinte forma
V t(St) = max
xt∈Xt
{
Ct(St, xt) + γE
{
V t+1(St+1)|St
}}
, (3.2)
onde V t(St) é um aproximação do valor de estar no estado St. A aproximação é uma estimativa
da função de valor para cada estado viável do sistema, e pode assumir qualquer forma funcional
que se deseje. O grande desafio está em obter aproximações de funções boas o suficiente para o
contexto proposto.
De modo geral, programação dinâmica aproximada se desenvolve a partir destas
duas principais bases: modelar funções de aproximação e simular a estocasticidade do sistema.
3.3 Arquiteturas de aproximação
As aproximações de funções devem ser construídas de modo que representem da
melhor forma a função desejada. A arquitetura de aproximação é fundamental neste processo,
pois ela precisa ser rica o suficiente para representar com tantos detalhes quanto possível a função
alvo (BERTSEKAS; TSITSIKLIS, 1996).
Genericamente, os métodos de aproximação podem ser separados em dois principais
tipos: paramétricos e não paramétricos. Resumidamente, aproximadores paramétricos são
40
mapeamentos de um espaço de parâmetros para o espaço das funções que se deseja representar.
Em contraste aproximadores não paramétricos, não há conhecimento a priori da representação
da função que se objetiva aproximar (BUSONIU et al., 2010).
3.3.1 Aproximação paramétrica
Nesta classe de aproximadores, a forma funcional do mapeamento e o número de
parâmetros são tipicamente definidos a priori, não dependem dos dados. Os parâmetros da
função de aproximação são ajustados usando dados sobre a função desejada.
Considere V o espaço das funções de valor. Suponha que a função de valor aproxi-
mada é por um vetor parametrizado n-dimensional θ. Assim, o aproximador será um mapeamento
F : Rn → V . Cada vetor de parâmetros θ provê uma representação compacta de uma função de
valor aproximada correspondente:
V̂ = F (θ).
Por meio desta representação, ao invés de armazenar a função de valor para cada estado,
armazena-se apenas o vetor de parâmetros. Estes aproximadores podem ser lineares ou não
lineares.
. Aproximação linear
– É formulada a partir de um conjunto de funções base (basis function) e um vetor
de parâmetros θ. As funções base capturam algumas características subjacentes ao
sistema. Seja φf (S) as funções base, onde f ∈ F é o índice de uma característica
(feature), e θ um vetor |F|-dimensional, a função de valor aproximada é estimada a
partir da seguinte arquitetura:
F (θ) =
∑
f∈F
θfφf (S). (3.3)
– Geralmente os |F| features são drasticamente menores que a dimensão do espaço de
estados, fazendo com que seja muito mais fácil trabalhar em termos de estimar o vetor
de parâmetros θ (POWELL, 2012). Portanto, o problema de computar exatamente a
41
função de valor para cada estado, nesta versão, se reduz a projetar um conjunto de
funções base e estimar os parâmetros.
. Aproximação não-linear
– Nesta arquitetura, a dependência da função F em θ é não linear. Um típico exemplo
de um aproximador não-linearmente parametrizado são as redes neurais feed-foward
(BERTSEKAS; TSITSIKLIS, 1996).
3.3.2 Aproximação não paramétrica
Uma questão que envolve modelos paramétricos é o fato de que estes modelos só se
mostram eficazes se a configuração do modelo for eficaz. Projetar boas funções base é uma “arte”
e um processo de tentativa e erro. Modelos não paramétricos surgem contornando a necessidade
de definir a quantidade de parâmetros e a configuração dos features a priori, evitando de certa
forma o trabalho artístico na modelagem (POWELL, 2012).
Apesar do nome, aproximadores deste tipo ainda possuem parâmetros. No entanto, o
número de parâmetros, bem como a forma do aproximador derivam dos dados (BUSONIU et al.,
2010). Modelos não parametrizados são caracterizados pela propriedade de que, a medida em
que o número de dados observados cresce, é possível aproximar qualquer função com precisão
arbitrária (POWELL, 2012).
Importantes classes de aproximadores não parametrizados que podem ser utilizados
em PDA incluem métodos baseado em kernel, dentre os quais máquina de vetores de suporte são
os mais populares.
Nas próximas seções deste capítulo serão apresentados métodos de aproximação que
se configuram como possuindo uma arquitetura com aproximadores linearmente parametrizados.
3.4 Iteração de política aproximada
A versão aproximada do algoritmo de iteração de política, de modo geral, segue a
mesma estrutura da sua versãoexata, ou seja, o algoritmo continua a ser executado em duas
etapas: avaliação e melhoria da política (Figura 8). Entretanto, as diferenças entre eles estão em
que para uma dada política, a função de valor não é computada diretamente, e a nova política
é gulosa com respeito a esta aproximação. Em resumo, os algoritmos de iteração de política
aproximada partem de uma política inicial, esta política é avaliada sob uma função de valor
42
aproximada, que segue uma determinada arquitetura de aproximação. Em seguida, esta função
de valor aproximada é utilizada para produzir novas políticas. O processo é repetido até atingir
uma determinada taxa de convergência.
Figura 8 – Diagrama das etapas do algoritmo de iteração de política
aproximada
Fonte: (BERTSEKAS; TSITSIKLIS, 1996), adaptado pela autora (2020).
3.4.1 Equação de Bellman projetada
Inicialmente, considere uma matriz A ∈ Rn×n e um vetor b ∈ Rn, e sejam x∗ e x̄,
respectivamente, as soluções dos dois sistemas de equações lineares de ponto fixo
x = Ax+ b (3.4)
x = Π(Ax+ b), (3.5)
de modo que Π denota uma matriz de projeção em um subespaço P com respeito a norma
Euclidiana ponderada ‖·‖ξ 1, onde ξ ∈ Rn é um vetor de componentes positivas. Assume-se que
x∗ e x̄ existem, e que a matriz (I − ΠA) é invertível, e x̄ é único. Assim, resolvendo a equação
projetada, o objetivo é utilizar deste resultado (3.5) para aproximar a equação original. (3.4)
(YU; BERTSEKAS, 2010).
Agora, considere a equação de Bellman em sua versão matricial
vπ = cπ + Pπvπ, (3.6)
1 ‖x‖ξ =
(∑
i ξix
2
)1/2
43
onde cπ é o vetor-coluna da função de retornos, Pπ é a matriz de transição e vπ o vetor-coluna
correspondendo à função de valor. Perceba que (3.6) pode ser facilmente vista sob a ótica das
equações (3.4) e (3.5). No contexto de PDM, x∗ é a função de valor, a equação original é a
equação de Bellman, o vetor de pesos ξ na norma de projeção corresponde a uma distribuição
invariante da cadeia de Markov associada a política, e o subespaço P é determinado indiretamente
pelo conjunto de features (YU; BERTSEKAS, 2010).
Então, seja um conjunto de funções base φi : S → R, i = 1, 2, . . . , n. Além
disto, considere que arquitetura de representação da função de valor é linear, então tem-se
que V
π
(s|θ) =
∑n
i=1 φi(s)θi. Para um conjunto de estados finitos S, defina Φ uma matriz
cujas colunas são vetores contendo o valor da função base para cada estado s ∈ S. Portanto,
Φ = [φ1, φ2, . . . , φn] ∈ R|P|×n. Em sua forma vetorial, a aproximação da função de valor é
representada por
vπ = Φθ, (3.7)
onde θ = [θ1, θ2, . . . , θn] é o vetor de parâmetros.
A versão projetada da equação Bellman assume a forma descrita a seguir
Φθ = ΠT (Φθ) = Π(cπ + PπΦθ), (3.8)
cujo o subespaço de projeção é P = {Φθ : θ ∈ Rn}. Solucionar a equação de Bellman projetada
corresponde obter uma função de valor representada por Φθ que, após a aplicação do operador
de Bellman e da projeção no subespaço, resulta em um ponto fixo da função.
Por definição, a projeção sobre a função desejada é um vetor que pertence ao
subespaço de projeção que está mais próxima da função original dada uma métrica induzida por
uma norma, que neste caso é a norma Euclidiana ponderada (BERTSEKAS; TSITSIKLIS, 1996).
Deseja-se obter θ de modo que a norma da diferença entre a função original e sua aproximação
seja mínima. Portanto, seja Ξ uma matriz diagonal cujos os elementos são os pesos da norma.
Tem-se que, o valor ótimo para θ é dado por
44
θ∗ = argmin
θ∈R
‖v − v‖ξ
θ∗ = argmin
θ∈R
(Φθ − v)TΞ(Φθ − v)
θ∗ = (ΦTΞΦ)−1ΦTΞv, (3.9)
e consequentemente, a projeção da função de valor é
v = Φθ∗ = Φ(ΦTΞΦ)−1ΦTΞv. (3.10)
Logo, a matriz de projeção é definida como
Π = Φ(ΦTΞΦ)−1ΦTΞ. (3.11)
Por fim, substituindo a matriz de projeção (3.11) em (3.8), a versão da equação
projetada de Bellman pode ser escrita como
Φθ = Φ(ΦTΞΦ)−1ΦTΞ(cπ + PπΦθ) (3.12)
ΦTΞΦθ = ΦTΞ(cπ + PπΦθ) (3.13)
ΦTΞ(Φ− PπΦ)θ = ΦTΞcπ. (3.14)
Fazendo A = ΦTΞ(Φ− PπΦ) e b = ΦTΞcπ, e assumindo a existência de A−1, é possível obter
θ∗ resolvendo um sistema linear da forma
θ∗ = A−1b. (3.15)
Logo, resolver a equação projetada de Bellman equivale a obter θ∗ resolvendo A−1b. Os métodos
que utilizam esta aproximação como forma de de estimar a função de valor são conhecidos como
métodos de diferença temporal de mínimos quadrados (least square temporal difference-LSTD)
(BRADTKE; BARTO, 1996) (LAGOUDAKIS; PARR, 2003).
3.4.2 Iteração de política aproximada baseada em simulação
As técnicas de programação dinâmica aproximada são projetadas com o propósito
de oferecer alternativas que contornem as dificuldades encontradas em representações de alta
dimensionalidade. Embora resolver a equação de Bellman projetada ofereça um caminho de
aproximação, as funções base que compõe a matriz Φ precisam ser computadas para todos
45
os estados. Portanto, para problemas com espaço de estados com alta dimensionalidade é
impraticável resolver a equação de Bellman da forma que foi apresentada na seção anterior.
Uma possibilidade oferecida para evitar operações com matrizes de alta dimensão
surgiu a partir da ideia de trabalhar apenas com amostras do espaço de estados, produzindo
trajetórias que representam a evolução do sistema. De modo bem prático, uma trajetória
representa uma sequência imediata de estados, decisões e recompensas (SUTTON; BARTO,
2018). Então, para uma dada política fixa π = {Xπ(S0), Xπ(S1), . . . }, é possível simular
a trajetória S0, Xπ(S0), C0, S1, Xπ(S1), C1, . . . , SN , Xπ(SN), CN e utilizar destas amostras e
computar a aproximação θ = A
−1
b, que equivale a
Φ̄T (Φ̄− ¯PπΦ)θ = Φ̄T c̄π (3.16)
em que para φ(si) = (φ1(si), φ2(si), . . . , φn(si)) tem-se
Φ̄ =

φ(s0)
φ(s1)
...
φ(sN−1)
 (3.17)
e
¯PπΦ =

φ(s1)
φ(s2)
...
φ(sN)
 (3.18)
e a aproximação do vetor de retornos é
c̄π =

C(s0, X
π(s0))
C(s1, X
π(s1))
...
C(sN−1, X
π(sN−1))
 (3.19)
Em seguida, obtém-se a função de valor aproximada para a política π resolvendo
a aproximação da equação de Bellman (3.16). Após a etapa de avaliação da política, um nova
política será produzida. A etapa de melhoria de política é muito semelhante com relação ao
algoritmo exato, sendo gerada a partir de uma estratégia gulosa, diferenciando-se apenas pelo
46
fator de que a função de valor é estimada por um aproximador linear. Portanto, a nova política
π′ =
{
Xπ
′
(S0), X
π′(S1), . . .
}
é dada por
Xπ
′
(s) = argmax
x∈Xs
{
C(s, x) + γ
∑
s′∈S
P(s′|s, x)φ(s′)T θ
}
∀s ∈ S (3.20)
Algoritmo 4: ALGORITMO DE ITERAÇÃO DE POLÍTICA BASEADO EM SIMU-
LAÇÃO
Entrada: θ, MDP
1 início
2 Inicialize arbitrariamente θ0
3 Para k ∈ {0, 1, ..., N − 1} faça:
4 Para t ∈ {0, 1, ..., T − 1} faça:
5 Xπt ← argmax
x∈Xst
{
C(st, x) + γ
∑
st+1∈S P(st+1|st, x)φ(st+1)
T θ
}
6 st+1 ∼ P(st+1|st, x)
7 Fim
8 θk+1 ←
(
Φ̄T (Φ̄− ¯PπΦ)
)−1
Φ̄T c̄π
9 Fim
10 return θN guloso com relação a V
11 fim
3.5 Iteração de valor aproximada
Na seção 2.5.2.2, é visto que o algoritmo de iteração de valor parte de uma função
de valor inicial arbitrária V0, e segue atualizando a função de valor de acordo com a decisão que
produz um maior retorno para cada função, até que atinja um nível de convergência. Em que
para cada iteração, a equação (3.21)
V n(s) = max
x∈X
{
C(Sn, x+ γE
{
V
n−1
(s′)|s
}}
, (3.21)
precisa ser executada para cada estado viável. Após cada varredura sobre o espaço de estados, a
nova estimativa da função de valor substitui a antiga estimação.
Então, volte a equação de Bellman projetada com aproximação linear (3.14) e note
que a equação pode ser reescrita como
Aθ − b = ΦTΞ(Φθ − (cπ + γPπΦθ)). (3.22)
O termo Φθ é a aproximação do valor de estar em cada estado, e (cπ + γPπΦθ) é a contribuição
imediada recebida em um dado estado somado ao valor esperado do próximo estado após a
47
transição. De forma bem simplificada, pense em δπ como sendo um diferença temporal dado
uma política π, que pode ser vista como o estimado menoso previsto (POWELL, 2011). Assim,
em (3.22) a diferença temporal com relação a π pode ser
δπ = − (Φθ − (cπ + γPπΦθ)) . (3.23)
Partindo disto, para o algoritmo de iteração de política aproximada, deseja-se obter
θ tal que a diferença quadrática entre entre a função a estimar e a estimativa seja minimizada.
Para isto, θ é atualizado por do método do gradiente, de modo que a atualização segue a seguinte
forma:
θ ← θ − α ∂
∂θ
(Φθ − vπ) (3.24)
θ ← θ − αΦ (Φθ − vπ) (3.25)
θ ← θ + αΦδπ, (3.26)
onde o tamanho do passo é α ∈ (0, 1].
Segue abaixo o algoritmo de iteração de valor baseado em trajetória (trajectory based
value iteration - TBVI) (GERAMIFARD, 2013).
Algoritmo 5: ALGORITMO DE ITERAÇÃO DE VALOR BASEADO EM TRAJE-
TÓRIA
Entrada: α, MDP
1 início
2 Inicialize arbitrariamente θ0
3 Enquanto tempo de execução faça:
4 Para s na trajetória produzida seguindo π faça:
5 Gere N amostras de s′ ∼ P(s′|s, x)
6 V(s)← max
x∈X
{
C(s, x) + γ
∑
s′∈S P(s′|s, x)φT θ
}
7 δ ← (Φθ − (cπ + γPπΦθ))
8 θ ← θ + αδφ
9 Fim
10 Fim
11 return π
12 fim