Reviews: Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctions

This paper studies the online learning (stochastic and full-information) problem of bidding in multi commodity first price auctions. The paper introduces a polynomial time algorithm that achieves a regret of \sqrt{T log(T)} that has a near optimal dependence on T. The main challenge that the paper has to deal with is to find a computationally efficient algorithm for computing the best biding strategy given a known distribution.The authors first demonstrate that natural approaches for solving this problem exactly are not computationally efficient (this is not a formal np-hardness proof). Then, they provide a FPTAS for solving the problem using dynamic programming. Once they have a FPTAS for the offline problem, their results hold for the stochastic online setting using existing reductions. I haven't carefully looked in to the details of their analysis of the dynamic programming, but I think the effectiveness of it here is interesting and surprising -- specially given that the variation of this problem for the second price auctions is hard to approximate.