# Optimal cross-learning for contextual bandits with unknown context distributions

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 19 references that are in the map.
- First posted on arXiv 3 Jan 2024.

## Builds on (most cited first, 9 of 9)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2002.00287/) (2020)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards](https://mlsanity.com/paper/2004.06248/) (2020)
- [Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2211.06358/) (2022)
- [Hardness of Online Sleeping Combinatorial Optimization Problems](https://mlsanity.com/paper/1509.03600/) (2015)

## Built on by (most cited first, 7 of 7)

- [Improved Algorithms for Contextual Dynamic Pricing](https://mlsanity.com/paper/2406.11316/) (2024)
- [Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions](https://mlsanity.com/paper/2402.07363/) (2024)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction](https://mlsanity.com/paper/2508.11931/) (2025)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback](https://mlsanity.com/paper/2502.04678/) (2025)

## Abstract (arXiv)

We consider the problem of designing contextual bandit algorithms in the ``cross-learning'' setting of Balseiro et al., where the learner observes the loss for the action they play in all possible contexts, not just the context of the current round. We specifically consider the setting where losses are chosen adversarially and contexts are sampled i.i.d. from an unknown distribution. In this setting, we resolve an open problem of Balseiro et al. by providing an efficient algorithm with a nearly tight (up to logarithmic factors) regret bound of widetildeO(√TK), independent of the number of contexts. As a consequence, we obtain the first nearly tight regret bounds for the problems of learning to bid in first-price auctions (under unknown value distributions) and sleeping bandits with a stochastic action set. At the core of our algorithm is a novel technique for coordinating the execution of a learning algorithm over multiple epochs in such a way to remove correlations between estimation of the unknown distribution and the actions played by the algorithm. This technique may be of independent interest for other learning problems involving estimation of an unknown context distribution.