Show simple item record

dc.contributor.authorHanawal, Manjeshen_US
dc.contributor.authorSaligrama, Venkateshen_US
dc.contributor.authorValko, Michalen_US
dc.contributor.authorMunos, Rémien_US
dc.date.accessioned2019-08-29T13:47:45Z
dc.date.available2019-08-29T13:47:45Z
dc.date.issued2015
dc.identifier.citationManjesh Hanawal, Venkatesh Saligrama, Michal Valko, Rémi Munos. 2015. "Cheap bandits." Proceedings of the 32 nd International Conference on Machine Learning, Lille, France, 2015. JMLR: W&CP volume 37.
dc.identifier.urihttps://hdl.handle.net/2144/37517
dc.description.abstractWe 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 CheapUCB, 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. As a by-product of our analysis, we establish a Ω(dT‾‾‾√) lower bound on the cumulative regret of spectral bandits for a class of graphs with effective dimension d.en_US
dc.rightsCopyright 2015 by the author(s).en_US
dc.subjectComputer scienceen_US
dc.subjectMachine learningen_US
dc.titleCheap banditsen_US
dc.typeConference materialsen_US
dc.description.versionPublished versionen_US
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: Not knownen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Engineeringen_US
pubs.organisational-groupBoston University, College of Engineering, Department of Electrical & Computer Engineeringen_US
dc.identifier.orcid0000-0002-0675-2268 (Saligrama, Venkatesh)
dc.identifier.mycv59451


This item appears in the following Collection(s)

Show simple item record