No-regret Learning in Repeated First-Price Auctions with Budget Constraints
Recently the online advertising market has exhibited a gradual shift from
second-price auctions to first-price auctions. Although there has been a line
of works concerning online bidding strategies in first-price auctions, it still
remains open how to handle budget constraints in the problem. In the present
paper, we initiate the study for a buyer with budgets to learn online bidding
strategies in repeated first-price auctions. We propose an RL-based bidding
algorithm against the optimal non-anticipating strategy under stationary
competition. Our algorithm obtains $\widetilde O(\sqrt T)$-regret if the bids
are all revealed at the end of each round. With the restriction that the buyer
only sees the winning bid after each round, our modified algorithm obtains
$\widetilde O(T^{\frac{7}{12}})$-regret by techniques developed from survival
analysis. Our analysis extends to the more general scenario where the buyer has
any bounded instantaneous utility function with regrets of the same order.