Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback

תקציר מקורי באנגליתarXiv:2502.04678v2 Announce Type: replace Abstract: 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 $\alpha$, one can remove every polynomial dependence on the number of contexts while attaining the classical graphical-bandit rate $\widetilde O(\sqrt{\alpha T})$. The question was open even for stochastic losses and graphs in whic