Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctions
This work addresses the challenge of efficient budget allocation in repeated auctions, such as in wholesale electricity markets, offering an incremental improvement with a near-optimal regret bound for bidders.
The paper tackles the problem of a bidder learning optimal bidding strategies in repeated multi-commodity auctions to maximize payoff, proposing a polynomial-time algorithm (DPDS) that achieves a regret of O(√(T log T)) and is shown to be order-optimal up to a √(log T) term, with empirical evaluation on electricity market data demonstrating consistent outperformance over benchmark methods.
We study the online learning problem of a bidder who participates in repeated auctions. With the goal of maximizing his T-period payoff, the bidder determines the optimal allocation of his budget among his bids for $K$ goods at each period. As a bidding strategy, we propose a polynomial-time algorithm, inspired by the dynamic programming approach to the knapsack problem. The proposed algorithm, referred to as dynamic programming on discrete set (DPDS), achieves a regret order of $O(\sqrt{T\log{T}})$. By showing that the regret is lower bounded by $Ω(\sqrt{T})$ for any strategy, we conclude that DPDS is order optimal up to a $\sqrt{\log{T}}$ term. We evaluate the performance of DPDS empirically in the context of virtual trading in wholesale electricity markets by using historical data from the New York market. Empirical results show that DPDS consistently outperforms benchmark heuristic methods that are derived from machine learning and online learning approaches.