No processo de resolução de um problema de Aprendizagem por Reforço, uma po- lítica de seleção de ações tem como objetivo estabelecer o comportamento do agente aprendiz para que o mesmo alterne adequadamente entre o uso do conhecimento já ad- quirido e a aquisição de conhecimento novo, de forma a otimizar o processo de explora- ção/explotação do espaço de busca.
A idéia de experimentar mais de uma política de seleção de ações para o Q-learning, tem como meta verificar qual destas políticas é mais adequada para ser utilizada na im- plementação do métodos híbridos propostos.
Políticaε-Gulosa
A política ε-gulosa escolhe a ação que possui o maior valor esperado, com probabi- lidade definida por(1 − ε), e de ação aleatória, com probabilidade ε. Matematicamente,
dada a matriz dos Q-valores Q obtém-se a ação gulosa a∗para um estado s fazendo:
a∗ = max
a∈A(s)Q(s, a)
π(s,a∗) = 1− ε + ε
|A(s)|
π(s,a) = |A(s)|ε ∀a ∈ A(s) − {a∗}
(4.3)
onde|A(s)| corresponde ao número de ações possíveis de serem executadas a partir de
s, e ε é o parâmetro de controle entre gula e aleatoriedade. A restrição presente em
4.3 permite que o Q− learning explore o espaço de estados do problema, e é uma das
condições necessárias para que o mesmo encontre uma política de controle ótima.
Políticaε-Gulosa Adaptativa
A política ε-gulosa adaptativa é semelhante a política ε − gulosa já descrita anteri- ormente, ou seja, ela permite escolher a ação que possui o maior valor esperado, com probabilidade definida por (1 -ε), e a ação aleatória, com probabilidade ε. O que a dife- rencia, e também justifica o termo “Adaptativa” é que o valor deε sofre um decaimento exponencial calculado por:
ε = max{vi, vf.bk} (4.4)
onde, k é o contador de episódios do Q-learning, b é um valor próximo de 1 e vi< vf ∈
[0, 1]. Desta forma inicialmente o algoritmo utilizará valores grandes para ε (próximos a
vf) e a medida que o valor de k cresce a escolha deε é direcionada para valores menores
(mais próximos a vi). A idéia é permitir que inicialmente sejam feitas escolhas mais
aleatórias e a medida que o número de episódios aumentem o aspecto guloso seja mais explorado.
Política Baseada na Contagem de Visitas
Nesta política a escolha das ações é feita baseada em uma técnica denominada Com- paração de Reforço (Reinforcement Comparison) [Sutton & Barto 1998]. Nesta técnica a escolha das ações é feita com base no princípio de que ações seguidas de grandes recom- pensas devem ser preferidas em detrimento de ações seguidas de pequenas recompensas. Para definir o que significa uma “grande recompensa” é feita uma comparação com um nível de recompensa padrão denominado recompensa referencial.
A idéia da política aqui proposta é semelhante a técnica de comparação de reforço, entretanto, a escolha das ações preferidas é feita com base na contagem de visitas aos estados atingidos por tais ações, ou seja, os estados mais visitados indicarão as ações preferidas, em detrimento de ações que levam a estados com menor número de visitas. De posse da medida de preferência das ações, pode-se determinar a probabilidade de seleção das ações de acordo com a seguinte relação Softmax:
πt(a) = Pr{at= a} =
ept−1(a)
∑
b
ept−1(b) (4.5)
onde πt(a) denota a probabilidade de se escolher a ação a no passo t e pt(a) denota a
preferência da ação a no tempo t, e que é calculada por:
pt+1(at) = pt(at) + β(Nv(s, at)/NE p) (4.6)
onde s é o estado atingido em conseqüência da escolha da ação a no passo t, Nv(s, at)
é o número de visitas ao estado s, NE p é o número total de episódios e β ∈ [0,1] é um parâmetro de controle que pondera o nível de influência das ações preferenciais.
Comparação entre as Políticas Implementadas
Com o objetivo de comparar as políticas testadas foi realizado um experimento no qual foram utilizadas 10 instâncias do PCV disponíveis na biblioteca T SPLIB [TSPLIB 2008]. Para a realização experimento utilizou-se a seguinte metodologia:
• Os dados apresentados na tabela 4.1 foram gerados pela média de 30 execuções de
três versões distintas do algoritmo Q-learning (uma versão para cada política), que utilizaram os mesmos valores para os parâmetros em comum.
• Para facilitar a comparação dos resultados foi feita uma normalização dos dados
para plotagem, sendo que, para normalizar os dados da função objetivo foi utili- zado como referência o valor ótimo conhecido para cada instância, enquanto que os dados do tempo de processamento foram normalizados pela média dos valores obtidos.
Os dados listados na tabela 4.1 mostram os resultados obtidos no experimento para cada versão do algoritmo Q-learning. Este experimento tem o propósito de comparar o desempenho do algoritmo Q-learning implementado utilizando três políticas distintas, as políticas “contagem de visitas”, “ε-gulosa” e “ε-gulosa adaptativa” descritas na seção
Tabela 4.1: Comparação das políticas: Contagem de Visitas,ε-Gulosa e ε-Gulosa Adap- tativa
Instância Número Contagem de Visita ε-Gulosa ε-Gulosa Adaptativa
TSPLIB Episódio Valor Tempo Valor Tempo Valor Tempo
gr17 300 2628,37 1,32 2499,56 0,82 2446,40 0,52 bays29 300 2967,83 2,23 2792,87 0,99 2690,70 0,80 swiss42 300 1804,27 3,26 1879,90 1,24 1830,70 1,19 gr48 300 7902,00 3,70 7630,83 1,36 7415,17 1,38 berlin52 300 11789,63 3,90 11376,50 1,48 10910,30 1,43 pr76 1000 178615,33 20,45 161144,33 6,36 156374,00 6,89 gr120 1000 12378,50 39,36 10938,87 9,20 10501,20 11,04 ch150 2000 12443,93 83,17 10122,90 20,67 9342,03 27,85 si175 5000 25721,53 280,45 26000,63 57,54 24642,17 82,10 a280 5000 5206,73 1388,33 4056,17 98,01 3748,80 139,46
g17 bays29 swiss42 gr48 berlin52 pr76 gr120 ch150 si175 a280 0 0.5 1 1.5 2 2.5
Valor da Função Objetivo
Comparação entre as Políticas Contagen de Visitas, ε−Gulosa, e ε−Gulosa Adaptativa
g17 bays29 swiss42 gr48 berlin52 pr76 gr120 ch150 si175 a280 0 0.5 1 1.5 2 2.5 3
Tamanho da Instância (Número de Cidades)
Tempo de Processamento
Valor Ótimo Contagen de Visitas ε−Gulosa ε−Gulosa Adaptativa
Contagen de Visitas
ε−Gulosa
ε−Gulosa Adaptativa
Figura 4.3: Comparação das Políticas testadas para o Q-learning implementado 4.3.1. Na mesma tabela pode-se também observar que a quantidade de episódios variou em função do tamanho das instâncias. O experimento realizado não tem o objetivo de comparar os resultados obtidos com as diferentes versões do algoritmo Q-learning com os valores ótimos das 10 instâncias do PCV utilizadas, e sim verificar, dentre as três políticas implementadas qual a de melhor desempenho. A figura 4.3 apresenta uma comparação do desempenho das políticas descritas anteriormente.
Ao analisar os resultados obtidos para as três políticas testadas, considerando simulta- neamente os fatores: valor da função e tempo de processamento, percebe-se que a política
ε-gulosa adaptativa foi a que obteve melhor desempenho e portanto, será a política utili-
zada na versão do algoritmo Q-learning implementado nos métodos híbridos propostos neste Capítulo.