Ad Network Optimization: Evaluating Linear Relaxations

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.