Tese (Doutorado em Engenharia Elétrica) - Centro Universitário FEI, São Bernardo do Campo, 2017

A inteligência artificial não busca somente entender mas construir entidades inteligentes. A inteligência pode ser dividida em vários fatores e um deles é conhecido como aprendizado. A área de aprendizado de máquina visa o desenvolvimento de técnicas para aprendizado automático de máquinas, que incluem computadores, robôs ou qualquer outro dispositivo. Entre essas técnicas encontra-se o Aprendizado por Reforço, foco principal deste trabalho. Mais especificamente, o aprendizado por reforço relacional (ARR) foi investigado, que representa na forma relacional o aprendizado obtido através da interação direta com o ambiente. O ARR é bem interessante no campo de robótica, pois, em geral, não se dispôe do modelo do ambiente e se requer econômia de recursos utilizados. A técnica ARR foi investigada dentro do contexto de aprendizado de uma cabeça robótica. Uma modificação no algoritmo ARR foi proposta, denominada por ETG, e incorporada em uma arquitetura de controle de uma cabeça robótica. A arquitetura foi avaliada no contexto de um problema real não trivial: o aprendizado da atenção compartilhada. Os resultados obtidos mostram que a arquitetura é capaz de exibir comportamentos apropriados durante uma interação social controlada, através da utilização do ETG. Uma análise comparativa com outros métodos foi realizada que mostram que o algoritmo proposto conseguiu obter um desempenho superior na maioria dos experimentos realizados / The artificial Intelligence search not only understand but to build intelligent entities. The intelligence can be divided into several factors and one of them is known as learning. The area of machine learning aimed at the development techniques for automatic learning of machinery, including computers, robots or any other device. Reinforcement Learning is one of those techniques, main focus of this work. Specifically, the relational reinforcement learning was investigated, which is use relational representation for learning obtained through direct interaction with the environment. The relational reinforcement learning is quite interesting in the field of robotics, because, in general, it does not have the model of environment and economy of resources used are required. The relational reinforcement learning technique was investigated within the context of learning a robotic head. A change in the relational reinforcement learning algorithm was proposed, called TGE, and incorporated into an architecture of control of a robotic head. The architecture was evaluated in the context of a real problem not trivial: the learning of shared attention. The results show that the architecture is capable of displaying appropriate behavior during a social interaction controlled through the use of TGE. A comparative analysis was performed with other methods show that the proposed algorithm has achieved a superior performance in most experiments

Agentes que utilizam técnicas de Aprendizado por Reforço (AR) buscam resolver problemas que envolvem decisões sequenciais em ambientes estocásticos sem conhecimento a priori. O processo de aprendizado desenvolvido pelo agente em geral é lento, visto que se concretiza por tentativa e erro e exige repetidas interações com cada estado do ambiente e como o estado do ambiente é representado por vários fatores, a quantidade de estados cresce exponencialmente de acordo com o número de variáveis de estado. Uma das técnicas para acelerar o processo de aprendizado é a generalização de conhecimento, que visa melhorar o processo de aprendizado, seja no mesmo problema por meio da abstração, ao explorar a similaridade entre estados semelhantes ou em diferentes problemas, ao transferir o conhecimento adquirido de um problema fonte para acelerar a aprendizagem em um problema alvo. Uma abstração considera partes do estado e, ainda que uma única não seja suficiente, é necessário descobrir qual combinação de abstrações pode atingir bons resultados. Nesta dissertação é proposto um método para seleção de abstração, considerando o processo de avaliação da aprendizagem durante o aprendizado. A contribuição é formalizada pela apresentação do algoritmo REPO, utilizado para selecionar e avaliar subconjuntos de abstrações. O algoritmo é iterativo e a cada rodada avalia novos subconjuntos de abstrações, conferindo uma pontuação para cada uma das abstrações existentes no subconjunto e por fim, retorna o subconjunto com as abstrações melhores pontuadas. Experimentos com o simulador de futebol mostram que esse método é efetivo e consegue encontrar um subconjunto com uma quantidade menor de abstrações que represente o problema original, proporcionando melhoria em relação ao desempenho do agente em seu aprendizado / Agents that use Reinforcement Learning (RL) techniques seek to solve problems that involve sequential decisions in stochastic environments without a priori knowledge. The learning process developed by the agent in general is slow, since it is done by trial and error and requires repeated iterations with each state of the environment and because the state of the environment is represented by several factors, the number of states grows exponentially according to the number of state variables. One of the techniques to accelerate the learning process is the generalization of knowledge, which aims to improve the learning process, be the same problem through abstraction, explore the similarity between similar states or different problems, transferring the knowledge acquired from A source problem to accelerate learning in a target problem. An abstraction considers parts of the state, and although a single one is not sufficient, it is necessary to find out which combination of abstractions can achieve good results. In this work, a method for abstraction selection is proposed, considering the evaluation process of learning during learning. The contribution is formalized by the presentation of the REPO algorithm, used to select and evaluate subsets of features. The algorithm is iterative and each round evaluates new subsets of features, giving a score for each of the features in the subset, and finally, returns the subset with the most highly punctuated features. Experiments with the soccer simulator show that this method is effective and can find a subset with a smaller number of features that represents the original problem, providing improvement in relation to the performance of the agent in its learning

Agentes que utilizam técnicas de Aprendizado por Reforço (AR) buscam resolver problemas que envolvem decisões sequenciais em ambientes estocásticos sem conhecimento a priori. O processo de aprendizado desenvolvido pelo agente em geral é lento, visto que se concretiza por tentativa e erro e exige repetidas interações com cada estado do ambiente e como o estado do ambiente é representado por vários fatores, a quantidade de estados cresce exponencialmente de acordo com o número de variáveis de estado. Uma das técnicas para acelerar o processo de aprendizado é a generalização de conhecimento, que visa melhorar o processo de aprendizado, seja no mesmo problema por meio da abstração, ao explorar a similaridade entre estados semelhantes ou em diferentes problemas, ao transferir o conhecimento adquirido de um problema fonte para acelerar a aprendizagem em um problema alvo. Uma abstração considera partes do estado e, ainda que uma única não seja suficiente, é necessário descobrir qual combinação de abstrações pode atingir bons resultados. Nesta dissertação é proposto um método para seleção de abstração, considerando o processo de avaliação da aprendizagem durante o aprendizado. A contribuição é formalizada pela apresentação do algoritmo REPO, utilizado para selecionar e avaliar subconjuntos de abstrações. O algoritmo é iterativo e a cada rodada avalia novos subconjuntos de abstrações, conferindo uma pontuação para cada uma das abstrações existentes no subconjunto e por fim, retorna o subconjunto com as abstrações melhores pontuadas. Experimentos com o simulador de futebol mostram que esse método é efetivo e consegue encontrar um subconjunto com uma quantidade menor de abstrações que represente o problema original, proporcionando melhoria em relação ao desempenho do agente em seu aprendizado / Agents that use Reinforcement Learning (RL) techniques seek to solve problems that involve sequential decisions in stochastic environments without a priori knowledge. The learning process developed by the agent in general is slow, since it is done by trial and error and requires repeated iterations with each state of the environment and because the state of the environment is represented by several factors, the number of states grows exponentially according to the number of state variables. One of the techniques to accelerate the learning process is the generalization of knowledge, which aims to improve the learning process, be the same problem through abstraction, explore the similarity between similar states or different problems, transferring the knowledge acquired from A source problem to accelerate learning in a target problem. An abstraction considers parts of the state, and although a single one is not sufficient, it is necessary to find out which combination of abstractions can achieve good results. In this work, a method for abstraction selection is proposed, considering the evaluation process of learning during learning. The contribution is formalized by the presentation of the REPO algorithm, used to select and evaluate subsets of features. The algorithm is iterative and each round evaluates new subsets of features, giving a score for each of the features in the subset, and finally, returns the subset with the most highly punctuated features. Experiments with the soccer simulator show that this method is effective and can find a subset with a smaller number of features that represents the original problem, providing improvement in relation to the performance of the agent in its learning

Submitted by Lara Oliveira (lara@ufersa.edu.br) on 2017-04-17T22:15:28Z No. of bitstreams: 1 AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-26T12:14:12Z (GMT) No. of bitstreams: 1 AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-26T12:16:44Z (GMT) No. of bitstreams: 1 AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) / Made available in DSpace on 2017-04-26T12:19:14Z (GMT). No. of bitstreams: 1 AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) Previous issue date: 2016-07-20 / The use of metaheuristics for solving combinatorial optimization problems belong to NP-Hard class is becoming increasingly common, and second Temponi (2007 apud RIBEIRO, 1996) a metaheurist should be modeled according to the problem she was designed to solve. This most often requires many changes when you have to apply the same metaheuristic to various types of combinatorial optimization problems. In this work we propose a framework for use of a hybrid metaheuristic proposed by Almeida (2014) who used the GRASP Reactive along with a reinforcement learning technique (called GR-learning). Specifically, the Q-learning algorithm that was used to learn over which the iterations value for the parameter α (alpha) used during the construction phase of GRASP. The GR-Learning was used to solve the problem of p-centers applied to Public Security in the city of Mossoró/RN. To validate the effectiveness of the framework proposed it was used to solve two classical problems of combinatorial optimi-zation: The Hub Location Problem (HLP), and the Cutting Stock Problem (CSP). To validate the results obtained we used instances with results known in the literature and in addition has created an instance with data from the Brazilian airline industry. The results showed that the proposed framework was quite competitive when compared to other results of different algo-rithms known in the literature as got great value in almost all instances of HLP as well as new values (better than those obtained with other algorithms known in the literature) for some ins-tances of CSP / A utilização de metaheurísticas para resolução de problemas de otimização combinatória per-tencentes à classe NP-Difícil vem se tornando cada vez mais comum, e segundo Temponi (2007 apud RIBEIRO, 1996) uma metaheurística deve ser modelada de acordo com o proble-ma que ela foi projetada para resolver. Isto na maioria vezes requer muitas alterações quando se tem que aplicar uma mesma metaheurística a diversos tipos de problemas de otimização combinatória. Neste trabalho foi proposto um framework para utilização de uma metaheurísti-ca híbrida proposta por Almeida (2014) que utilizou a metaheurística GRASP Reativo junta-mente com uma técnica de aprendizagem por reforço (denominada GR-Learning). Especifi-camente, o algoritmo Q-learning, que foi utilizado para aprender com o passar das iterações qual valor para o parâmetro α (alfa) utilizar durante a fase de construção da GRASP. O GR-Learning foi utilizado para resolver o problema dos p-Centros aplicado a Segurança Pública na Cidade de Mossoró/RN. Para validar a eficácia do framework proposto o mesmo foi utili-zado para resolver dois problemas clássicos de otimização combinatória: O Problema de Lo-calização de Hubs (do inglês Hub Location Problem - HLP) e o Problema de Corte e Estoque – PCE (do inglês Cutting Stock Problem - CSP). Para validação dos resultados obtidos foram utilizadas instâncias com resultados já conhecidos na literatura e adicionalmente foi criada uma instância com dados do setor aeroviário Brasileiro. Os resultados obtidos mostraram que o framework proposto foi bastante competitivo quando comparado a outros resultados de di-versos algoritmos já conhecidos na literatura, pois obteve o valor ótimo em quase todas as instâncias do HLP como também novos valores (melhores que os obtidos com outros algorit-mos já conhecido na literatura) para algumas instâncias do CSP / 2017-04-17

A inteligência artificial não busca somente entender mas construir entidades inteligentes. A inteligência pode ser dividida em vários fatores e um deles é conhecido como aprendizado. A área de aprendizado de máquina visa o desenvolvimento de técnicas para aprendizado automático de máquinas, que incluem computadores, robôs ou qualquer outro dispositivo. Entre essas técnicas encontra-se o Aprendizado por Reforço, foco principal deste trabalho. Mais especificamente, o aprendizado por reforço relacional (ARR) foi investigado, que representa na forma relacional o aprendizado obtido através da interação direta com o ambiente. O ARR é bem interessante no campo de robótica, pois, em geral, não se dispôe do modelo do ambiente e se requer econômia de recursos utilizados. A técnica ARR foi investigada dentro do contexto de aprendizado de uma cabeça robótica. Uma modificação no algoritmo ARR foi proposta, denominada por ETG, e incorporada em uma arquitetura de controle de uma cabeça robótica. A arquitetura foi avaliada no contexto de um problema real não trivial: o aprendizado da atenção compartilhada. Os resultados obtidos mostram que a arquitetura é capaz de exibir comportamentos apropriados durante uma interação social controlada, através da utilização do ETG. Uma análise comparativa com outros métodos foi realizada que mostram que o algoritmo proposto conseguiu obter um desempenho superior na maioria dos experimentos realizados / The artificial Intelligence search not only understand but to build intelligent entities. The intelligence can be divided into several factors and one of them is known as learning. The area of machine learning aimed at the development techniques for automatic learning of machinery, including computers, robots or any other device. Reinforcement Learning is one of those techniques, main focus of this work. Specifically, the relational reinforcement learning was investigated, which is use relational representation for learning obtained through direct interaction with the environment. The relational reinforcement learning is quite interesting in the field of robotics, because, in general, it does not have the model of environment and economy of resources used are required. The relational reinforcement learning technique was investigated within the context of learning a robotic head. A change in the relational reinforcement learning algorithm was proposed, called TGE, and incorporated into an architecture of control of a robotic head. The architecture was evaluated in the context of a real problem not trivial: the learning of shared attention. The results show that the architecture is capable of displaying appropriate behavior during a social interaction controlled through the use of TGE. A comparative analysis was performed with other methods show that the proposed algorithm has achieved a superior performance in most experiments

As técnicas de Aprendizado por Reforço permitem a solução de um problema através da escolha de ações que maximizem valores de recompensas recebidas que refletem a qualidade das ações tomadas pelo agente em um processo de tentativa e erro. Em problemas com estrutura hierárquica, a solução final depende do encadeamento de soluções para subproblemas aí presentes, sendo frequente a repetição de subproblemas nesse encadeamento. Nesses casos, a utilização de políticas parciais permite o aprendizado e armazenamento das soluções individuais para cada subproblema, que podem então ser utilizadas múltiplas vezes na composição de uma solução completa para o problema final, acelerando o aprendizado. Apesar de vantajosa, a utilização de políticas parciais necessita de definições por parte do projetista, o que representa uma sobrecarga. Para contornar esse problema, foram propostas técnicas de descoberta automática de políticas parciais, dentre as quais a utilização de motivação intrínseca se destaca por permitir ao agente aprender soluções de subproblemas úteis na solução do problema final sem a necessidade de se definir manualmente novas recompensas para esses subproblemas individualmente. Apesar de promissora, essa proposta utiliza um conjunto de componentes de aprendizado que ainda carece de investigação aprofundada acerca dos impactos individual e coletivo de cada componente, notadamente a aplicação das políticas parciais durante o aprendizado. Nesta dissertação são propostas duas abordagens para a aplicação de políticas parciais no Aprendizado por Reforço com Motivação Intrínseca: (i) armazenamento das políticas parciais em aplicação pelo agente e (ii) exploração interna à aplicação das políticas parciais. O impacto das propostas no desempenho de aprendizado é avaliado experimentalmente em um domínio com forte caracterização hierárquica. / Reinforcement Learning techniques allow an agent to learn the solution to a problem by interacting with the environment and executing actions, thus receiving rewards that reflect the value of the actions taken, on a process of trial and error. When a problem has a hierarchical structure, its final solution depends on several solutions to the subproblems it contains, and it is rather common the repetition of subproblems. On these cases, by using options it is possible to learn the solution to each subproblem individually, keeping and then using them multiple times to compose the complete solution to the problem, thus accelerating the learning process. But, despite this advantage, the use of options create the need for some definitions, what can represent a burden to the designer. To circumvent this problem, automatic option discovery techniques were proposed, among which the use of intrinsic motivation deserves special attention for allowing the agent to learn the solution of the subproblems, which are useful to compose the final solution, without the need to manually define new rewards to these subproblems individually. Despite being promising, this technique is built upon a set of several learning components that need a more deep investigation on the individual and collective impacts of each component, mostly the options application strategies during the learning process. On this work two modifications are proposed concerning the application process of options on the Intrinsically Motivated Reinforcement Learning: (i) storage of the history of the options applied by the agent and (ii) allow the agent to explore, even when following an option. These modifications were implemented on an algorithm present on the literature and evaluated on a domain with strong hierarchical characteristics.

A principal motivação para o surgimento do conceito de Smart Grid é a otimização do uso das redes de energia através da inserção de novas tecnologias de medição, automação e telecomunicações. A implementação desta complexa infra-estrutura produz ganhos em confiabilidade, eficiência e segurança operacional. Além disso, este sistema tem como principais objetivos promover a geração distribuída e a tarifa diferenciada de energia para usuários residenciais, provendo ferramentas para a participação dos consumidores no gerenciamento global do fornecimento de energia. Considerando também o uso de dispositivos de armazenamento de energia, o usuário pode optar por vender ou armazenar energia sempre que lhe for conveniente, reduzindo a sua conta de energia ou, quando a geração exceder a demanda de energia, lucrando através da venda deste excesso. Esta pesquisa propõe um Sistema Inteligente de Suporte à Decisão baseado em técnicas de aprendizado por reforço como uma solução para o problema de decisão sequencial referente ao gerenciamento de energia de uma Smart Home. Resultados obtidos mostram um ganho significativo na recompensa financeira a longo prazo através do uso de uma política obtida pela aplicação do algoritmo Q-Learning, que é um algoritmo de aprendizado por reforço on-line, e do algoritmo Fitted Q-Iteration, que utiliza uma abordagem diferenciada de aprendizado por reforço ao extrair uma política através de um lote fixo de transições adquiridas do ambiente. Os resultados mostram que a aplicação da técnica de aprendizado por reforço em lote é indicada para problemas reais, quando é necessário obter uma política de forma rápida e eficaz dispondo de uma pequena quantidade de dados para caracterização do problema estudado. / The main motivation for the emergence of the Smart Grid concept is the optimization of power grid use by inserting new measurement, automation and telecommunication technologies into it. The implementation of this complex infrastructure also produces gains in reliability, efficiency and operational safety. Besides, it has as main goals to encourage distributed power generation and to implement a differentiated power rate for residential users, providing tools for them to participate in the power grid supply management. Considering also the use of energy storage devices, the user can sell or store the power generated whenever it is convenient, reducing the electricity bill or, when the power generation exceeds the power demand, make profit by selling the surplus in the energy market. This research proposes an Intelligent Decision Support System as a solution to the sequential decision-making problem of residential energy management based on reinforcement learning techniques. Results show a significant financial gain in the long term by using a policy obtained applying the algorithm Q-Learning, which is an on-line Reinforcement Learning algorithm, and the algorithm Fitted Q-Iteration, which uses a different reinforcement learning approach called Batch Reinforcement Learning. This method extracts a policy from a fixed batch of transitions acquired from the environment. The results show that the application of Batch Reinforcement Learning techniques is suitable for real problems, when it is necessary to obtain a fast and effective policy considering a small set of data available to study and solve the proposed problem.

As técnicas de Aprendizado por Reforço permitem a solução de um problema através da escolha de ações que maximizem valores de recompensas recebidas que refletem a qualidade das ações tomadas pelo agente em um processo de tentativa e erro. Em problemas com estrutura hierárquica, a solução final depende do encadeamento de soluções para subproblemas aí presentes, sendo frequente a repetição de subproblemas nesse encadeamento. Nesses casos, a utilização de políticas parciais permite o aprendizado e armazenamento das soluções individuais para cada subproblema, que podem então ser utilizadas múltiplas vezes na composição de uma solução completa para o problema final, acelerando o aprendizado. Apesar de vantajosa, a utilização de políticas parciais necessita de definições por parte do projetista, o que representa uma sobrecarga. Para contornar esse problema, foram propostas técnicas de descoberta automática de políticas parciais, dentre as quais a utilização de motivação intrínseca se destaca por permitir ao agente aprender soluções de subproblemas úteis na solução do problema final sem a necessidade de se definir manualmente novas recompensas para esses subproblemas individualmente. Apesar de promissora, essa proposta utiliza um conjunto de componentes de aprendizado que ainda carece de investigação aprofundada acerca dos impactos individual e coletivo de cada componente, notadamente a aplicação das políticas parciais durante o aprendizado. Nesta dissertação são propostas duas abordagens para a aplicação de políticas parciais no Aprendizado por Reforço com Motivação Intrínseca: (i) armazenamento das políticas parciais em aplicação pelo agente e (ii) exploração interna à aplicação das políticas parciais. O impacto das propostas no desempenho de aprendizado é avaliado experimentalmente em um domínio com forte caracterização hierárquica. / Reinforcement Learning techniques allow an agent to learn the solution to a problem by interacting with the environment and executing actions, thus receiving rewards that reflect the value of the actions taken, on a process of trial and error. When a problem has a hierarchical structure, its final solution depends on several solutions to the subproblems it contains, and it is rather common the repetition of subproblems. On these cases, by using options it is possible to learn the solution to each subproblem individually, keeping and then using them multiple times to compose the complete solution to the problem, thus accelerating the learning process. But, despite this advantage, the use of options create the need for some definitions, what can represent a burden to the designer. To circumvent this problem, automatic option discovery techniques were proposed, among which the use of intrinsic motivation deserves special attention for allowing the agent to learn the solution of the subproblems, which are useful to compose the final solution, without the need to manually define new rewards to these subproblems individually. Despite being promising, this technique is built upon a set of several learning components that need a more deep investigation on the individual and collective impacts of each component, mostly the options application strategies during the learning process. On this work two modifications are proposed concerning the application process of options on the Intrinsically Motivated Reinforcement Learning: (i) storage of the history of the options applied by the agent and (ii) allow the agent to explore, even when following an option. These modifications were implemented on an algorithm present on the literature and evaluated on a domain with strong hierarchical characteristics.

Redes de Anúncios (Ad Networks) são redes que promovem a distribuição de anúncios pela internet, de forma a maximizar o lucro total gerado pela exibição dos anúncios nos websites. Estas redes tipicamente operam através do modelo de negócios chamado CPC (Custo por Clique), em que o anunciante paga um determinado valor somente se algum usuário clicar em seu anúncio. A escolha de como o intermediador planeja a distribuição dos anúncios aos websites é de extrema importância, já que a taxa de cliques nos anúncios é extremamente baixa. Atualmente a alocação dos anúncios tem sido feita através de uma solução aproximada baseada na alocação ótima definida com dados de um período anterior, a qual é calculada através de programação linear aliada à utilização de heurísticas. Entretanto, este sistema claramente é um processo de decisão sequencial em que diversas restrições são aplicáveis, como por exemplo: o orçamento dos anunciantes, limites mínimos do número de exibições de cada anúncio, categorias dos anúncios, entre outras. Neste trabalho argumenta-se que MDPs (Markov Decision Processes) fornecem uma melhor modelagem para o problema, já que conseguem levar em conta a dinâmica do sistema, considerando, por exemplo, que um anúncio que tem poucas chances de ser clicado consiga ser alocado de forma eficiente em relação ao retorno de longo prazo, mesmo quando outros anúncios proveriam um lucro maior a curto prazo. No entanto, devido ao grande número de estados, utilizar uma solução ótima através de MDPs é impraticável. Portanto analisa-se o desempenho relativo entre o estado da arte e a modelagem ótima, obtendo garantias de que a solução aproximada baseada em programação linear não está longe da solução ótima, e que em problemas grandes (similares aos encontrados na prática) essa diferença pode ser ignorada. Por fim, propõe-se uma modelagem baseada em aprendizado por reforço para a solução deste problema, utilizando duas abordagens, uma desconsiderando informações de contexto e outra considerando informações de contexto. Aqui argumenta-se que o uso de aprendizado por reforço é mais apropriado para a solução do problema de alocação de anúncios, já que ele é capaz de adaptar sua política de alocação em função das mudanças que ocorrem como, por exemplo, no perfil do usuário. / Ad Networks promote the distribution of ads in the internet, so as to maximize the revenue generated by their display of ads in websites. These networks typically operate using the CPC (Cost per Click) business model, where the advertiser pays a monetary value when a user clicks in its advertisement. The choice of how the Ad Network distributes ads to websites is of utmost importance, since the rate of clicks on ads is extremely low. The allocation of ads has been done by an approximate solution based on data from an early period of time, which is calculated using linear programming combined with heuristics. However, this problem is clearly a sequential decision process in which multiple sequential restrictions apply, such as: the budget of the advertisers, minimum limits on the number of views for each campaign, categories of advertisements. In this dissertation we argue that MDPs (Markov Decision Processes) provide a better model for the problem, since they can automatically take into account the dynamics of the system, considering, for example, an ad with little chance of being clicked can be allocated in an efficient way, even when other ads would provide a higher profit in the short term. However, due to the large number of states, an optimal solution through MDPs is impractical; therefore we analyze here the relative performance between the linear programming and the MDP approaches, deriving guarantees that the approximate solution based on linear programming is not far from the MDP optimal solution, and in large problems (similar to those found in practice) this difference can be disregarded. Finally, we propose a model based on reinforcement learning using two different approaches, one disregarding the contextual information, and the other using contextual information. We argue that the use of reinforcement learning is more suitable for solving the problem of allocation of ads, since it is able to adapt its allocation policy to reflect changes that occur, e.g., in the user profile.