| Full text | |
| Author(s): |
Truzzi, Flavio Sales
;
da Silva, Valdinei Freire
;
Reali Costa, Anna Helena
;
Cozman, Fabio Gagliardi
;
Pozo, ATR
;
Camargo, HD
;
Furtado, V
;
Pinheiro, V
Total Authors: 8
|
| Document type: | Journal article |
| Source: | 2013 BRAZILIAN CONFERENCE ON INTELLIGENT SYSTEMS (BRACIS); v. N/A, p. 6-pg., 2013-01-01. |
| Abstract | |
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) | |
| FAPESP's process: | 11/19280-8 - CogBot: integrating perceptual information and semantic knowledge in cognitive robotics |
| Grantee: | Anna Helena Reali Costa |
| Support Opportunities: | Regular Research Grants |