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) - From Unsupervised to Few-shot Graph Anomaly Detection: A Multi-scale
Contrastive Learning Approach [49.439021563395976]
Anomaly detection from graph data is an important data mining task in many applications such as social networks, finance, and e-commerce.
We propose a novel framework, graph ANomaly dEtection framework with Multi-scale cONtrastive lEarning (ANEMONE in short)
By using a graph neural network as a backbone to encode the information from multiple graph scales (views), we learn better representation for nodes in a graph.
arXiv Detail & Related papers (2022-02-11T09:45:11Z) - 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) - 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) - On Under-exploration in Bandits with Mean Bounds from Confounded Data [41.09427248084205]
We study a variant of the multi-armed bandit problem where side information in the form of bounds on the mean of each arm is provided.
We develop the novel non-optimistic Global Under-Explore (GLUE) algorithm which uses the provided mean bounds.
We show that mean bounds can be inferred naturally from such logs and can thus be used to improve the learning process.
arXiv Detail & Related papers (2020-02-19T19:36:43Z)
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.