Pure Exploration in Multi-armed Bandits with Graph Side Information
- URL: http://arxiv.org/abs/2108.01152v1
- Date: Mon, 2 Aug 2021 20:06:04 GMT
- Title: Pure Exploration in Multi-armed Bandits with Graph Side Information
- Authors: Parth K.Thaker, Nikhil Rao, Mohit Malu, Gautam Dasarathy
- Abstract summary: We study pure exploration in multi-armed bandits with graph side-information.
We propose a novel algorithm GRUB (GRaph based UcB) for this problem.
We show that capitalizing on available graph side information yields significant improvements over pure exploration methods.
- Score: 11.633592964399806
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study pure exploration in multi-armed bandits with graph side-information.
In particular, we consider the best arm (and near-best arm) identification
problem in the fixed confidence setting under the assumption that the arm
rewards are smooth with respect to a given arbitrary graph. This captures a
range of real world pure-exploration scenarios where one often has information
about the similarity of the options or actions under consideration. We propose
a novel algorithm GRUB (GRaph based UcB) for this problem and provide a
theoretical characterization of its performance that elicits the benefit of the
graph-side information. We complement our theory with experimental results that
show that capitalizing on available graph side information yields significant
improvements over pure exploration methods that are unable to use this
information.
Related papers
- Stochastic Graph Bandit Learning with Side-Observations [4.910658441596583]
We propose an algorithm that adapts to both the underlying graph structures and reward gaps.
To the best of our knowledge, our algorithm is the first to provide a gap-dependent upper bound in this setting.
arXiv Detail & Related papers (2023-08-29T08:14:19Z) - Graph Neural Bandits [49.85090929163639]
We propose a framework named Graph Neural Bandits (GNB) to leverage the collaborative nature among users empowered by graph neural networks (GNNs)
To refine the recommendation strategy, we utilize separate GNN-based models on estimated user graphs for exploitation and adaptive exploration.
arXiv Detail & Related papers (2023-08-21T15:57:57Z) - Differential Good Arm Identification [4.666048091337632]
This paper targets a variant of the multi-armed bandit problem called good arm identification (GAI)
GAI is a pure-exploration bandit problem with the goal to output as many good arms using as few samples as possible.
We propose DGAI - a differentiable good arm identification algorithm.
arXiv Detail & Related papers (2023-03-13T14:28:21Z) - Towards Explanation for Unsupervised Graph-Level Representation Learning [108.31036962735911]
Existing explanation methods focus on the supervised settings, eg, node classification and graph classification, while the explanation for unsupervised graph-level representation learning is still unexplored.
In this paper, we advance the Information Bottleneck principle (IB) to tackle the proposed explanation problem for unsupervised graph representations, which leads to a novel principle, textitUnsupervised Subgraph Information Bottleneck (USIB)
We also theoretically analyze the connection between graph representations and explanatory subgraphs on the label space, which reveals that the robustness of representations benefit the fidelity of explanatory subgraphs.
arXiv Detail & Related papers (2022-05-20T02:50:15Z) - Improving Subgraph Recognition with Variational Graph Information
Bottleneck [62.69606854404757]
Subgraph recognition aims at discovering a compressed substructure of a graph that is most informative to the graph property.
This paper introduces a noise injection method to compress the information in the subgraphs, which leads to a novel Variational Graph Information Bottleneck (VGIB) framework.
arXiv Detail & Related papers (2021-12-18T10:51:13Z) - Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
We study the setting when, despite the means being unknown, there is a known additive relationship between the source and target MAB instances.
We propose and theoretically analyze an LUCB-style algorithm to identify an $epsilon$-optimal target arm with high probability.
arXiv Detail & Related papers (2021-12-08T02:20:18Z) - The Role of Contextual Information in Best Arm Identification [13.651941268805693]
We study the best-arm identification problem with fixed confidence when contextual information is available in bandits.
We show the instance-specific sample complexity lower bounds for the problem.
We experimentally confirm that context information contributes to faster best-arm identification.
arXiv Detail & Related papers (2021-06-26T18:39:38Z) - Recognizing Predictive Substructures with Subgraph Information
Bottleneck [97.19131149357234]
We propose a novel subgraph information bottleneck (SIB) framework to recognize such subgraphs, named IB-subgraph.
Intractability of mutual information and the discrete nature of graph data makes the objective of SIB notoriously hard to optimize.
Experiments on graph learning and large-scale point cloud tasks demonstrate the superior property of IB-subgraph.
arXiv Detail & Related papers (2021-03-20T11:19:43Z) - Best Arm Identification in Graphical Bilinear Bandits [9.052414772641011]
We introduce a new graphical bilinear bandit problem where a learner allocates arms to the nodes of a graph.
We study the best arm identification problem in which the learner wants to find the graph allocation maximizing the sum of the bilinear rewards.
arXiv Detail & Related papers (2020-12-14T15:25:23Z) - Graph Information Bottleneck for Subgraph Recognition [103.37499715761784]
We propose a framework of Graph Information Bottleneck (GIB) for the subgraph recognition problem in deep graph learning.
Under this framework, one can recognize the maximally informative yet compressive subgraph, named IB-subgraph.
We evaluate the properties of the IB-subgraph in three application scenarios: improvement of graph classification, graph interpretation and graph denoising.
arXiv Detail & Related papers (2020-10-12T09:32:20Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.