Allerton 2015 Paper Abstract


Paper ThD3.1

Hanawal, Manjesh (Boston University), Saligrama, Venkatesh (Boston University)

Cost Effective Algorithms for Spectral Bandits

Scheduled for presentation during the Regular Session "Machine Learning II" (ThD3), Thursday, October 1, 2015, 15:30−15:50, Butternut

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on December 5, 2021

Keywords Sensor Networks, Sparse Data Analysis, Machine Learning and Approximate Dynamic Programming


We consider stochastic sequential learning problems where the learner can observe the textit{average reward of several actions}. Such a setting is interesting in many applications involving monitoring and surveillance, where the set of the actions to observe represent some (geographical) area. The importance of this setting is that in these applications, it is actually textit{cheaper} to observe average reward of a group of actions rather than the reward of a single action. We show that when the reward is textit{smooth} over a given graph representing the neighboring actions, we can maximize the cumulative reward of learning while textit{minimizing the sensing cost}. In this paper we propose CheapSpectralEliminator, an algorithm that matches the regret guarantees of the known algorithms for this setting and at the same time guarantees a linear cost again over them. We show that the algorithm achieves the lower bound of a$Omega(sqrt{dT})$ lower bound on the cumulative regret of spectral bandits for a class of graphs with effective dimension $d$.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2021 PaperCept, Inc.
Page generated 2021-12-05  09:14:12 PST  Terms of use