Efficient Contextual Bandits with Uninformed Feedback Graphs
- URL: http://arxiv.org/abs/2402.08127v1
- Date: Mon, 12 Feb 2024 23:50:47 GMT
- Title: Efficient Contextual Bandits with Uninformed Feedback Graphs
- Authors: Mengxiao Zhang, Yuheng Zhang, Haipeng Luo, Paul Mineiro
- Abstract summary: Bandits with feedback graphs are powerful online learning models that interpolate between the full information and classic bandit problems.
We show that it is critical to learn the graphs using log loss instead of squared loss to obtain favorable regret guarantees.
- Score: 48.77120088347271
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bandits with feedback graphs are powerful online learning models that
interpolate between the full information and classic bandit problems, capturing
many real-life applications. A recent work by Zhang et al. (2023) studies the
contextual version of this problem and proposes an efficient and optimal
algorithm via a reduction to online regression. However, their algorithm
crucially relies on seeing the feedback graph before making each decision,
while in many applications, the feedback graph is uninformed, meaning that it
is either only revealed after the learner makes her decision or even never
fully revealed at all. This work develops the first contextual algorithm for
such uninformed settings, via an efficient reduction to online regression over
both the losses and the graphs. Importantly, we show that it is critical to
learn the graphs using log loss instead of squared loss to obtain favorable
regret guarantees. We also demonstrate the empirical effectiveness of our
algorithm on a bidding application using both synthetic and real-world data.
Related papers
- Online Network Inference from Graph-Stationary Signals with Hidden Nodes [31.927912288598467]
We present a novel method for online graph estimation that accounts for the presence of hidden nodes.
We then formulate a convex optimization problem for graph learning from streaming, incomplete graph signals.
arXiv Detail & Related papers (2024-09-13T12:09:09Z) - Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
We present a novel algorithm that leverages graph neural networks to tackle the problem efficiently, particularly for large graphs.
We demonstrate the effectiveness of our method on a dataset of Erdos-Renyi graphs, showing its applicability also in hard-to-solve connectivity regions.
arXiv Detail & Related papers (2024-08-02T18:02:51Z) - A Topology-aware Graph Coarsening Framework for Continual Graph Learning [8.136809136959302]
Continual learning on graphs tackles the problem of training a graph neural network (GNN) where graph data arrive in a streaming fashion.
Traditional continual learning strategies such as Experience Replay can be adapted to streaming graphs.
We propose TA$mathbbCO$, a (t)opology-(a)ware graph (co)arsening and (co)ntinual learning framework.
arXiv Detail & Related papers (2024-01-05T22:22:13Z) - Efficiently Learning the Graph for Semi-supervised Learning [4.518012967046983]
We show how to learn the best graphs from the sparse families efficiently using the conjugate gradient method.
Our approach can also be used to learn the graph efficiently online with sub-linear regret, under mild smoothness assumptions.
We implement our approach and demonstrate significant ($sim$10-100x) speedups over prior work on semi-supervised learning with learned graphs on benchmark datasets.
arXiv Detail & Related papers (2023-06-12T13:22:06Z) - State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
Graph-level learning has been applied to many tasks including comparison, regression, classification, and more.
Traditional approaches to learning a set of graphs rely on hand-crafted features, such as substructures.
Deep learning has helped graph-level learning adapt to the growing scale of graphs by extracting features automatically and encoding graphs into low-dimensional representations.
arXiv Detail & Related papers (2023-01-14T09:15:49Z) - Adversarial Graph Contrastive Learning with Information Regularization [51.14695794459399]
Contrastive learning is an effective method in graph representation learning.
Data augmentation on graphs is far less intuitive and much harder to provide high-quality contrastive samples.
We propose a simple but effective method, Adversarial Graph Contrastive Learning (ARIEL)
It consistently outperforms the current graph contrastive learning methods in the node classification task over various real-world datasets.
arXiv Detail & Related papers (2022-02-14T05:54:48Z) - Deep Fraud Detection on Non-attributed Graph [61.636677596161235]
Graph Neural Networks (GNNs) have shown solid performance on fraud detection.
labeled data is scarce in large-scale industrial problems, especially for fraud detection.
We propose a novel graph pre-training strategy to leverage more unlabeled data.
arXiv Detail & Related papers (2021-10-04T03:42:09Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
Data association across frames is at the core of Multiple Object Tracking (MOT) task.
Existing methods mostly ignore the context information among tracklets and intra-frame detections.
We propose a novel learnable graph matching method to address these issues.
arXiv Detail & Related papers (2021-03-30T08:58:45Z) - Graph Coarsening with Neural Networks [8.407217618651536]
We propose a framework for measuring the quality of coarsening algorithm and show that depending on the goal, we need to carefully choose the Laplace operator on the coarse graph.
Motivated by the observation that the current choice of edge weight for the coarse graph may be sub-optimal, we parametrize the weight assignment map with graph neural networks and train it to improve the coarsening quality in an unsupervised way.
arXiv Detail & Related papers (2021-02-02T06:50:07Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications.
In this formalism, a link prediction problem is converted to a graph classification task.
We propose to seek a radically different and novel path by making use of the line graphs in graph theory.
In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
arXiv Detail & Related papers (2020-10-20T05:54:31Z)
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.