Linear Bandits with Feature Feedback

Authors

  • Urvashi Oswal Oracle Labs
  • Aniruddha Bhargava University of Wisconsin-Madison
  • Robert Nowak University of Wisconsin-Madison

DOI:

https://doi.org/10.1609/aaai.v34i04.5980

Abstract

This paper explores a new form of the linear bandit problem in which the algorithm receives the usual stochastic rewards as well as stochastic feedback about which features are relevant to the rewards, the latter feedback being the novel aspect. The focus of this paper is the development of new theory and algorithms for linear bandits with feature feedback which can achieve regret over time horizon T that scales like kT, without prior knowledge of which features are relevant nor the number k of relevant features. In comparison, the regret of traditional linear bandits is dT, where d is the total number of (relevant and irrelevant) features, so the improvement can be dramatic if kd. The computational complexity of the algorithm is proportional to k rather than d, making it much more suitable for real-world applications compared to traditional linear bandits. We demonstrate the performance of the algorithm with synthetic and real human-labeled data.

Downloads

Published

2020-04-03

How to Cite

Oswal, U., Bhargava, A., & Nowak, R. (2020). Linear Bandits with Feature Feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 5331-5338. https://doi.org/10.1609/aaai.v34i04.5980

Issue

Section

AAAI Technical Track: Machine Learning