Submitted by Pedro Barros (pedro.silvabarros@ufpe.br) on 2018-08-03T18:32:40Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TESE Davi Carnaíba de Lima Vieira.pdf: 2812278 bytes, checksum: 49475e006f9c1cb1a583b085a286ad3f (MD5) / Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-08-09T17:13:59Z (GMT) No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TESE Davi Carnaíba de Lima Vieira.pdf: 2812278 bytes, checksum: 49475e006f9c1cb1a583b085a286ad3f (MD5) / Made available in DSpace on 2018-08-09T17:13:59Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TESE Davi Carnaíba de Lima Vieira.pdf: 2812278 bytes, checksum: 49475e006f9c1cb1a583b085a286ad3f (MD5) Previous issue date: 2016-03-03 / CAPES / Os algoritmos da Aprendizagem por Reforço (AR) têm sido amplamente utilizados para a construção de agentes autônomos. Inspirada no comportamento da aprendizagem animal, a AR é um paradigma que serve como base para algoritmos que aprendem por tentativa e erro. Apesar da sua popularidade e sua sólida base matemática e garantia teórica de convergência para uma solução ótima, a AR apresenta restrições de aplicação em tarefas em que o espaço de estados é muito grande. Por meio do agrupamento de estados similares é possível reduzir o tamanho do espaço de estados. Uma vez reduzido, o problema pode ser resolvido utilizando os algoritmos tradicionais da AR. A principal questão que se coloca aqui é como efetuar a agregação, de tal modo que, por um lado, se possa obter uma “boa” representação do espaço de estados, e pelo outro lado, o desempenho do modelo não degrade. Este é um dos grandes desafios da AR. Esta tese propõe agrupar estados similares, por meio do uso do mapa auto-organizável de Fritzke, como forma de reduzir o espaço de estados. A maior parte das pesquisas que envolvem o uso de algoritmos que discretizam o espaço de estados busca aprimorar o momento certo para a partição do espaço de estados, onde particionar e quando parar, enquanto os algoritmos AR permanecem inalterados. Esses trabalhos em geral resultam em algoritmos que não convergem em determinados problemas ou que possuem uma capacidade de aprendizagem “fraca”. O presente trabalho contribui mostrando a fragilidade destes algoritmos ao mesmo tempo em que apresenta uma solução eficaz para o problema. Esta tese compara o algoritmo proposto com quatro algoritmos AR chamados: Tile Coding (TC), Temporal Difference Adaptive Vector Quantification (TD-AVQ), Q(λ) com Discretização Uniforme (Q(λ)-DU) e Interpolating Growing Neural Gas Q-learning (IGNG-Q). Os experimentos mostram que o algoritmo proposto foi capaz de encontrar a solução dos cinco ambientes de teste envolvidos. Em comparação com o algoritmo TC, o algoritmo proposto foi capaz de proporcionar uma redução no uso da memória de 88%, 87%, 98% e 97% nos ambientes Continuous Maze, Slow Puddle World, Mountain Car e Acrobot, respectivamente. No teste, o algoritmo proposto foi o único capaz de produzir uma política utilizável nos ambientes Continuous Maze e Slow Puddle World. O presente trabalho também mostra que o algoritmo n-step Temporal Difference with Elegibility Traces (TD(nλ)) é mais indicado para o uso em ambientes discretizados que o Q(λ). O uso do algoritmo proposto com Discretização Uniforme (DU) foi capaz de mostrar convergência em problemas onde o Q(λ) não conseguiu. O produto final desta tese é um algoritmo robusto capaz de encontrar em tempo hábil uma solução para todos os ambientes de teste envolvidos. / Reinforcement Learning (RL) algorithms has been widely used for the construction of autonomous agents. Inspired by the behavior of animal learning, RL is a paradigm that serves as basis for algorithms that learn by trial and error. Despite its popularity, solid mathematical foundation and theoretical guarantee of convergence to an optimal solution, RL have applicability constraints on tasks where the state space is too large. By aggregating similar states one can reduce the state space size. Once reduced, the problem can be solved using traditional RL algorithms. The main question that arises here is how to realize the aggregation, so on the one hand, you can get a “good” representation of the state space, and on the other hand, the model performance does not degrade. This is one of the challenges of RL. This thesis proposes aggregation of similar states, through the use of Fritzke’s selforganizing map, in order to reduce the state space. Most research involving the use of algorithms that discretize the state space seek to improve the right time for the partition of the state space, where to partition and when to stop, while the RL algorithms remains unchanged. These works often result in algorithms that do not converge on certain problems or have a “weak” learning capacity. This work contributes showing the fragility of these algorithms while presents an effective solution to the problem. This thesis compares the proposed algorithm with four RL algorithms namely: Tile Coding (TC), Temporal Difference Adaptive Vector Quantization (TD-AVQ), Uniform Discretization (DU) and Interpolating Growing Neural Gas Q-learning (IGNG-Q). The experiments show that the proposed algorithm was able to find the solution on five testbed environments. Compared with TC, the proposed algorithm was able to provide a reduction in memory usage of 88%, 87%, 98% and 97% in the environments Continuous Maze, Slow Puddle World, Mountain Car and Acrobot respectively. In the test, the proposed algorithm was the only capable to found an solution for the environments Continuous Maze and Slow Puddle World. This thesis also shows that the RL algorithm proposed is more suitable for the use in discretized environments than Q(λ). The application of TD(nλ) with DU was able to show convergence in problems where Q(λ) failed. The final product of this thesis is a robust algorithm able to find in time a solution for all specified test environments.