Ad network optimization evaluating linear relaxations

Abstract

This paper presents a theoretical and empirical analysis of linear programming relaxations to ad network op- timization. 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.