Stochastic contextual bandits with graph feedback: from independence number to MAS number

arXiv:2402.18591v1 Announce Type: new
Abstract: We consider contextual bandits with graph feedback, a class of interactive learning problems with richer structures than vanilla contextual bandits, where taking an action reveals the rewards for all neighboring actions in the feedback graph under all contexts. Unlike the multi-armed bandits setting where a growing literature has painted a near-complete understanding of graph feedback, much remains unexplored in the contextual bandits counterpart. In this paper, we make inroads into this inquiry by establishing a …

abstract arxiv class cs.gt cs.lg feedback graph interactive math.st multi-armed bandits stat.th stochastic type