2025/02/07 by Ruiyuan Huang, Huang, Ruiyuan, Zengfeng Huang +1
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Data Stream Mining Techniques #Smart Grid Energy Management #cs.LG
paper · pdf · doi:10.48550/arxiv.2502.04678
openalex publication_date 2025/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
Repeated first-price auctions are contextual decision problems with censored but reusable feedback: after submitting a bid, a learner can infer the outcomes of related bids and evaluate them under different private values. This structure motivates cross-learning contextual bandits with graphical feedback, where playing an arm reveals the losses of its out-neighbors in every context. A central open question was whether, under i.i.d. contexts and a fixed strongly observable feedback graph with independence number α, one can remove every polynomial dependence on the number of contexts while attaining the classical graphical-bandit rate \widetilde O(√(αT)). The question was open even for stochastic losses and graphs in which every arm has a self-loop. We answer it affirmatively under the stronger model of oblivious adversarial losses and for all strongly observable graphs, including those with arms without self-loops. The key obstruction is that a frequently played no-self-loop arm can nevertheless have a vanishing observation probability. Our algorithm isolates one such arm per epoch, uses a pessimistic correction to cancel its first-order estimation drift, and shifts the losses in the FTRL analysis to control the resulting quadratic term. It achieves expected regret \widetilde O(√(αT)). Controlled synthetic experiments show the benefit of combining graph feedback with cross-learning and exhibit the predicted scaling in both T and α. The main theorem is formalized in Lean in an end-to-end development exceeding 100,000 lines of Lean code. The formalization and experiment artifacts are available in the GitHub repository: https://github.com/RuiyuanHuang/graphical-cross-learning-review-artifact.