Modelagem e soluções para redes de anúncios.

• Ano de defesa: 2014
• Autor(a) principal: Truzzi, Flávio Sales
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Ad Networks; Aprendizado por reforço; Artificial inteligence; Inteligência artificial; Markov Decision Processes; Processos de decisão Markov; Redes de anúncios; Reinforcement learning
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/3/3141/tde-24042015-113950/

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.