# Exploiting Correlated Auxiliary Feedback in Parameterized Bandits

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 38 references that are in the map.
- First posted on arXiv 5 Nov 2023.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Bandit Structured Prediction for Neural Sequence-to-Sequence Learning](https://mlsanity.com/paper/1704.06497/) (2017)
- [Online Learning with Gaussian Payoffs and Side Observations](https://mlsanity.com/paper/1510.08108/) (2015)
- [Control Variates for Slate Off-Policy Evaluation](https://mlsanity.com/paper/2106.07914/) (2021)
- [Online Algorithm for Unsupervised Sensor Selection](https://mlsanity.com/paper/1901.04676/) (2019)
- [Online Algorithm for Unsupervised Sequential Selection with Contextual Information](https://mlsanity.com/paper/2010.12353/) (2020)
- [Stochastic Multi-Armed Bandits with Control Variates](https://mlsanity.com/paper/2105.03962/) (2021)
- [Ensemble approximate control variate estimators: Applications to multi-fidelity importance sampling](https://mlsanity.com/paper/2101.02786/) (2021)
- [Scalable Discrete Sampling as a Multi-Armed Bandit Problem](https://mlsanity.com/paper/1506.09039/) (2015)
- [Thompson Sampling for Unsupervised Sequential Selection](https://mlsanity.com/paper/2009.07554/) (2020)

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

- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing](https://mlsanity.com/paper/2607.09015/) (2026)
- [COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents](https://mlsanity.com/paper/2505.23720/) (2025)
- [Best-Arm Identification with Generative Proxy](https://mlsanity.com/paper/2607.06879/) (2026)
- [Multi-armed Bandits with Missing Outcome](https://mlsanity.com/paper/2411.05661/) (2024)
- [Stochastic Multi-Armed Bandits with Limited Control Variates](https://mlsanity.com/paper/2603.02100/) (2026)
- [Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback](https://mlsanity.com/paper/2610.17760/) (2026)

## Abstract (arXiv)

We study a novel variant of the parameterized bandits problem in which the learner can observe additional auxiliary feedback that is correlated with the observed reward. The auxiliary feedback is readily available in many real-life applications, e.g., an online platform that wants to recommend the best-rated services to its users can observe the user's rating of service (rewards) and collect additional information like service delivery time (auxiliary feedback). In this paper, we first develop a method that exploits auxiliary feedback to build a reward estimator with tight confidence bounds, leading to a smaller regret. We then characterize the regret reduction in terms of the correlation coefficient between reward and its auxiliary feedback. Experimental results in different settings also verify the performance gain achieved by our proposed method.