| Texto completo | |
| Autor(es): |
Truzzi, Flavio Sales
;
da Silva, Valdinei Freire
;
Reali Costa, Anna Helena
;
Cozman, Fabio Gagliardi
;
Pozo, ATR
;
Camargo, HD
;
Furtado, V
;
Pinheiro, V
Número total de Autores: 8
|
| Tipo de documento: | Artigo Científico |
| Fonte: | 2013 BRAZILIAN CONFERENCE ON INTELLIGENT SYSTEMS (BRACIS); v. N/A, p. 6-pg., 2013-01-01. |
| Resumo | |
This paper presents a theoretical and empirical analysis of linear programming relaxations to ad network optimization. The underlying problem is to select a sequence of ads to send to websites; while an optimal policy can be produced using a Markov Decision Process, in practice one must resort to relaxations to bypass the curse of dimensionality. We focus on a state-of-art relaxation scheme based on linear programming. We build a Markov Decision Process that captures the worst-case behavior of such a linear programming relaxation, and derive theoretical guarantees concerning linear relaxations. We then report on extensive empirical evaluation of linear relaxations; our results suggest that for large problems (similar to ones found in practice), the loss of performance introduced by linear relaxations is rather small. (AU) | |
| Processo FAPESP: | 11/19280-8 - CogBot: integrando informação perceptual e conhecimento semântico na robótica cognitiva |
| Beneficiário: | Anna Helena Reali Costa |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |