# Linear Contextual Bandits with Hybrid Payoff: Revisited

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 14 Jun 2024.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [An Efficient Bandit Algorithm for Realtime Multivariate Optimization](https://mlsanity.com/paper/1810.09558/) (2018)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits](https://mlsanity.com/paper/1905.10040/) (2019)
- [Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits](https://mlsanity.com/paper/2006.02612/) (2020)
- [Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits](https://mlsanity.com/paper/2206.05404/) (2022)

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

- [Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback](https://mlsanity.com/paper/2506.13163/) (2025)
- [Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces](https://mlsanity.com/paper/2510.19349/) (2025)
- [Scalable and Interpretable Contextual Bandits: A Literature Review and Retail Offer Prototype](https://mlsanity.com/paper/2505.16918/) (2025)
- [Decentralized Contextual Bandits with Network Adaptivity](https://mlsanity.com/paper/2508.13411/) (2025)
- [Contextual Slate GLM Bandits with Limited Adaptivity](https://mlsanity.com/paper/2606.31449/) (2026)

## Abstract (arXiv)

We study the Linear Contextual Bandit problem in the hybrid reward setting. In this setting every arm's reward model contains arm specific parameters in addition to parameters shared across the reward models of all the arms. We can reduce this setting to two closely related settings (a) Shared - no arm specific parameters, and (b) Disjoint - only arm specific parameters, enabling the application of two popular state of the art algorithms - textttLinUCB and textttDisLinUCB (Algorithm 1 in (Li et al. 2010)). When the arm features are stochastic and satisfy a popular diversity condition, we provide new regret analyses for both algorithms, significantly improving on the known regret guarantees of these algorithms. Our novel analysis critically exploits the hybrid reward structure and the diversity condition. Moreover, we introduce a new algorithm textttHyLinUCB that crucially modifies textttLinUCB (using a new exploration coefficient) to account for sparsity in the hybrid setting. Under the same diversity assumptions, we prove that textttHyLinUCB also incurs only O(√T) regret for T rounds. We perform extensive experiments on synthetic and real-world datasets demonstrating strong empirical performance of textttHyLinUCB.For number of arm specific parameters much larger than the number of shared parameters, we observe that textttDisLinUCB incurs the lowest regret. In this case, regret of textttHyLinUCB is the second best and extremely competitive to textttDisLinUCB. In all other situations, including our real-world dataset, textttHyLinUCB has significantly lower regret than textttLinUCB, textttDisLinUCB and other SOTA baselines we considered. We also empirically observe that the regret of textttHyLinUCB grows much slower with the number of arms compared to baselines, making it suitable even for very large action spaces.