# Contextual Bandits with Cross-learning

arXiv: https://arxiv.org/abs/1809.09582 · HTML: https://mlsanity.com/paper/1809.09582/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2018.

## Built on by (most cited first, 30 of 31)

- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [Multi-channel Autobidding with Budget and ROI Constraints](https://mlsanity.com/paper/2302.01523/) (2023)
- [Contextual Games: Multi-Agent Learning with Side Information](https://mlsanity.com/paper/2107.06327/) (2021)
- [Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2211.06358/) (2022)
- [Improved Algorithms for Contextual Dynamic Pricing](https://mlsanity.com/paper/2406.11316/) (2024)
- [HyperBandit: Contextual Bandit with Hypernewtork for Time-Varying User Preferences in Streaming Recommendation](https://mlsanity.com/paper/2308.08497/) (2023)
- [No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions](https://mlsanity.com/paper/2110.03906/) (2021)
- [Offline Reinforcement Learning for Optimizing Production Bidding Policies](https://mlsanity.com/paper/2310.09426/) (2023)
- [Strategizing against No-Regret Learners in First-Price Auctions](https://mlsanity.com/paper/2402.08637/) (2024)
- [Optimal cross-learning for contextual bandits with unknown context distributions](https://mlsanity.com/paper/2401.01857/) (2024)
- [Joint Value Estimation and Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2502.17292/) (2025)
- [Incrementality Bidding via Reinforcement Learning under Mixed and Delayed Rewards](https://mlsanity.com/paper/2206.01293/) (2022)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Adversarial Online Learning with Temporal Feedback Graphs](https://mlsanity.com/paper/2407.00571/) (2024)
- [Improved learning rates in multi-unit uniform price auctions](https://mlsanity.com/paper/2501.10181/) (2025)
- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback](https://mlsanity.com/paper/2502.04678/) (2025)
- [Adversarial Combinatorial Semi-bandits with Graph Feedback](https://mlsanity.com/paper/2502.18826/) (2025)
- [Episodic Contextual Bandits with Knapsacks under Conversion Models](https://mlsanity.com/paper/2507.06859/) (2025)
- [Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization](https://mlsanity.com/paper/2510.19591/) (2025)
- [Enhancing Bandit Algorithms with LLMs for Time-varying User Preferences in Streaming Recommendations](https://mlsanity.com/paper/2602.08067/) (2026)
- [Active Learning for Contextual Search with Binary Feedbacks](https://mlsanity.com/paper/2110.01072/) (2021)
- [Advancing Ad Auction Realism: Practical Insights & Modeling Implications](https://mlsanity.com/paper/2307.11732/) (2023)
- [Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments](https://mlsanity.com/paper/2506.19038/) (2025)
- [Is Online Linear Optimization Sufficient for Strategic Robustness?](https://mlsanity.com/paper/2602.12253/) (2026)

## Abstract (arXiv)

In the classical contextual bandits problem, in each round t, a learner observes some context c, chooses some action i to perform, and receives some reward ri,t(c). We consider the variant of this problem where in addition to receiving the reward ri,t(c), the learner also learns the values of ri,t(c') for some other contexts c' in set Oi(c); i.e., the rewards that would have been achieved by performing that action under different contexts c'∈ Oi(c). This variant arises in several strategic settings, such as learning how to bid in non-truthful repeated auctions, which has gained a lot of attention lately as many platforms have switched to running first-price auctions. We call this problem the contextual bandits problem with cross-learning. The best algorithms for the classical contextual bandits problem achieve tildeO(√CKT) regret against all stationary policies, where C is the number of contexts, K the number of actions, and T the number of rounds. We design and analyze new algorithms for the contextual bandits problem with cross-learning and show that their regret has better dependence on the number of contexts. Under complete cross-learning where the rewards for all contexts are learned when choosing an action, i.e., set Oi(c) contains all contexts, we show that our algorithms achieve regret tildeO(√KT), removing the dependence on C. For any other cases, i.e., under partial cross-learning where |Oi(c)|< C for some context-action pair of (i,c), the regret bounds depend on how the sets mathcal Oi(c) impact the degree to which cross-learning between contexts is possible. We simulate our algorithms on real auction data from an ad exchange running first-price auctions and show that they outperform traditional contextual bandit algorithms.