Stochastic contextual bandits with graph feedback: from independence number to MAS number
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909379228336128 |
|---|---|
| author | Wen, Yuxiao Han, Yanjun Zhou, Zhengyuan |
| author_facet | Wen, Yuxiao Han, Yanjun Zhou, Zhengyuan |
| contents | 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 regret lower bound $Ω(\sqrt{β_M(G) T})$, where $M$ is the number of contexts, $G$ is the feedback graph, and $β_M(G)$ is our proposed graph-theoretic quantity that characterizes the fundamental learning limit for this class of problems. Interestingly, $β_M(G)$ interpolates between $α(G)$ (the independence number of the graph) and $\mathsf{m}(G)$ (the maximum acyclic subgraph (MAS) number of the graph) as the number of contexts $M$ varies. We also provide algorithms that achieve near-optimal regret for important classes of context sequences and/or feedback graphs, such as transitively closed graphs that find applications in auctions and inventory control. In particular, with many contexts, our results show that the MAS number essentially characterizes the statistical complexity for contextual bandits, as opposed to the independence number in multi-armed bandits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18591 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Stochastic contextual bandits with graph feedback: from independence number to MAS number Wen, Yuxiao Han, Yanjun Zhou, Zhengyuan Machine Learning Computer Science and Game Theory Statistics Theory 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 regret lower bound $Ω(\sqrt{β_M(G) T})$, where $M$ is the number of contexts, $G$ is the feedback graph, and $β_M(G)$ is our proposed graph-theoretic quantity that characterizes the fundamental learning limit for this class of problems. Interestingly, $β_M(G)$ interpolates between $α(G)$ (the independence number of the graph) and $\mathsf{m}(G)$ (the maximum acyclic subgraph (MAS) number of the graph) as the number of contexts $M$ varies. We also provide algorithms that achieve near-optimal regret for important classes of context sequences and/or feedback graphs, such as transitively closed graphs that find applications in auctions and inventory control. In particular, with many contexts, our results show that the MAS number essentially characterizes the statistical complexity for contextual bandits, as opposed to the independence number in multi-armed bandits. |
| title | Stochastic contextual bandits with graph feedback: from independence number to MAS number |
| topic | Machine Learning Computer Science and Game Theory Statistics Theory |
| url | https://arxiv.org/abs/2402.18591 |