Papers › Linear Contextual Bandits with Hybrid Payoff: Revisited
Linear Contextual Bandits with Hybrid Payoff: Revisited
Nirjhar Das, Gaurav Sinha
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 - LinUCB and DisLinUCB (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 HyLinUCB that crucially modifies LinUCB (using a new exploration coefficient) to account for sparsity in the hybrid setting. Under the same diversity assumptions, we prove that HyLinUCB also incurs only O(√(T)) regret for T rounds. We perform extensive experiments on synthetic and real-world datasets demonstrating strong empirical performance of HyLinUCB.For number of arm specific parameters much larger than the number of shared parameters, we observe that DisLinUCB incurs the lowest regret. In this case, regret of HyLinUCB is the second best and extremely competitive to DisLinUCB. In all other situations, including our real-world dataset, HyLinUCB has significantly lower regret than LinUCB, DisLinUCB and other SOTA baselines we considered. We also empirically observe that the regret of HyLinUCB grows much slower with the number of arms compared to baselines, making it suitable even for very large action spaces.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections