Q-Learning applied to games: a reward focused study

Abstract

Q-Learning is one of the most popular reinforcement learning algorithms. It can solve different complex problems with interesting tasks where decisions have to be made, all the while using the same algorithm with no interfer ence from the developer about specific strategies. This is achieved by processing a reward received after each decision is made. In order to evaluate the performance of Q-Learning on different problems, video games prove to be a great asset for testing purposes, as each game has its own unique mechanics and some kind of objective that needs to be learned. Furthermore, the results from testing different algorithms on the same conditions can be easily compared. This thesis presents a study on Q-Learning, from its origins and how it operates, showcasing various state of the art techniques used to improve the algorithm and detailing the procedures that have become standard when training Q-Learning agents to play video games for the Atari 2600. Our implementation of the algorithm following the same techniques and procedures is ran on different video games. The training performance is compared to the one obtained in articles that trained on the same games and attained state of the art performance. Additionally, we explored crafting new reward schemes modifying game default rewards. Various custom rewards were created and combined to evaluate how they affect performance. During these tests, we found that the use of rewards that inform about both good and bad behaviour led to better performance, as opposed to rewards that only inform about good behaviour, which is done by default in some games. It was also found that the use of more game specific rewards could attain better results, but these also required a more careful analysis of each game, not being easily transferable into other games. As a more general approach, we tested reward changes that could incentivize exploration for games that were harder to navigate, and thus harder to learn from. We found that not only did these changes improve exploration, but they also improved the performance obtained after some parameter tuning. These algorithms are designed to teach the agent to accumulate rewards. But how does this relate to game score? To assess this question, we present some preliminary experiments showing the relationship between the evolution of reward accumulation and game score.

Q-Learning é um dos algoritmos mais populares de aprendizagem por reforço. Este consegue resolver vários problemas complexos que tenham tarefas interessantes e decisões que devem ser tomadas. Para todos os problemas, o mesmo algoritmo é utilizado sem haver interferência por parte do desenvolvedor sobre estratégias específicas que existam. Isto tudo é alcançado processando uma recompensa que é recebida após tomar cada decisão. Para avaliar o desempenho de Q-Learning em problemas diferentes, os jogos eletrónicos trazem grandes vantagens para fins de teste, pois cada jogo tem as suas próprias regras e algum tipo de objetivo que precisa de ser compreendido. Além disso, os resultados dos testes usando diferentes algoritmos nas mesmas condições podem ser facilmente comparados. Esta tese apresenta um estudo sobre Q-Learning, explicando as suas origens e como funciona, apresentando várias técnicas de estado da arte usadas para melhorar o algoritmo e detalhando os procedimentos padrão usados para treinar agentes de Q-Learning a jogar jogos eletrónicos da Atari 2600. A nossa implementação do algoritmo seguindo as mesmas técnicas e procedimentos é executada em diferentes jogos eletrónicos. O desempenho durante o treino é comparado ao desempenho obtido em artigos que treinaram nos mesmos jogos e atingiram resultados de estado da arte. Além disso, exploramos a criação de novos esquemas de recompensas, modificando as recompensas usadas nos jogos por defeito. Várias recompensas novas foram criadas e combinadas para avaliar como afetam o desempenho do agente. Durante estes testes, observamos que o uso de recompensas que informam tanto sobre o bom como o mau comportamento levaram a um melhor desempenho, ao contrário de recompensas que apenas informam sobre o bom comportamento, que acontece em alguns jogos usando as recompensas por defeito. Também se observou que o uso de recompensas mais específicas para um jogo pode levar a melhores resultados, mas essas recompensas também exigem uma análise mais cuidadosa de cada jogo e não são facilmente transferíveis para outros jogos. Numa abordagem mais geral, testamos mudanças de recompensas que poderiam incentivar a exploração em jogos mais difíceis de navegar e, portanto, mais difíceis de aprender. Observamos que estas mudanças não só melhoraram a exploração, como também o desempenho obtido após alguns ajustes de parâmetros. Estes algoritmos têm como objetivo ensinar o agente a acumular recompensas. Como é que isto está relacionado com a pontuação obtida no jogo? Para abordar esta questão, apresentamos alguns testes preliminares que mostram a relação entre a evolução da acumulação de recompensas e da pontuação no jogo.