Improved Algorithms for Bandit with Graph Feedback via Regret Decomposition

• URL: http://arxiv.org/abs/2205.15076v2
• Date: Fri, 4 Aug 2023 05:13:42 GMT
• Title: Improved Algorithms for Bandit with Graph Feedback via Regret Decomposition
• Authors: Yuchen He and Chihao Zhang
• Abstract summary: The problem of bandit with graph feedback generalizes both the multi-armed bandit (MAB) problem and the learning with expert advice problem. We propose a new algorithmic framework for the problem based on a partition of the feedback graph.
• Score: 2.3034251503343466
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of bandit with graph feedback generalizes both the multi-armed bandit (MAB) problem and the learning with expert advice problem by encoding in a directed graph how the loss vector can be observed in each round of the game. The mini-max regret is closely related to the structure of the feedback graph and their connection is far from being fully understood. We propose a new algorithmic framework for the problem based on a partition of the feedback graph. Our analysis reveals the interplay between various parts of the graph by decomposing the regret to the sum of the regret caused by small parts and the regret caused by their interaction. As a result, our algorithm can be viewed as an interpolation and generalization of the optimal algorithms for MAB and learning with expert advice. Our framework unifies previous algorithms for both strongly observable graphs and weakly observable graphs, resulting in improved and optimal regret bounds on a wide range of graph families including graphs of bounded degree and strongly observable graphs with a few corrupted arms.

Related papers

• The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
  The noisy version of the graph isomorphism problem aims to find a matching between the nodes of two graphs which preserves most of the edges. This thesis focuses on understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data.
  arXiv  Detail & Related papers  (2024-04-18T15:31:13Z)
• Efficient Contextual Bandits with Uninformed Feedback Graphs [48.77120088347271]
  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.
  arXiv  Detail & Related papers  (2024-02-12T23:50:47Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  Graph neural networks (GNNs) are able to leverage the structure of graph data by passing messages along the edges of the graph. We propose a computationally efficient algorithm that prevents oversquashing by systematically adding edges to the graph. We find experimentally that our algorithm outperforms existing graph rewiring methods in several graph classification tasks.
  arXiv  Detail & Related papers  (2022-10-21T07:58:03Z)
• Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback [15.429356827868514]
  We introduce a new trade-off mechanism for exploration and exploitation of general feedback graphs. We prove the proposed algorithm simultaneously achieves $mathrmpoly-designed log T$ regret in the adversarial setting. This is the first best-of-both-worlds result for general feedback graphs.
  arXiv  Detail & Related papers  (2022-06-16T04:21:27Z)
• A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs [21.563733343861713]
  We consider online learning with feedback graphs, a sequential decision-making framework where the learner's feedback is determined by a directed graph over the action set. We present a computationally efficient algorithm for learning in this framework that simultaneously achieves near-optimal regret bounds in both and adversarial environments.
  arXiv  Detail & Related papers  (2022-06-01T15:14:32Z)
• Towards Graph Self-Supervised Learning with Contrastive Adjusted Zooming [48.99614465020678]
  We introduce a novel self-supervised graph representation learning algorithm via Graph Contrastive Adjusted Zooming. This mechanism enables G-Zoom to explore and extract self-supervision signals from a graph from multiple scales. We have conducted extensive experiments on real-world datasets, and the results demonstrate that our proposed model outperforms state-of-the-art methods consistently.
  arXiv  Detail & Related papers  (2021-11-20T22:45:53Z)
• Deep graph matching meets mixed-integer linear programming: Relax at your own risk ? [8.05409526074409]
  We propose an approach integrating a MILP formulation of the graph matching problem. Similar approaches are derived by releasing the optimal guarantee of the graph matching solver and by introducing a quality level. Our experimental evaluation gives several theoretical insights and guides the direction of deep graph matching methods.
  arXiv  Detail & Related papers  (2021-08-01T08:29:55Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)
• 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)
• Reinforcement Learning with Feedback Graphs [69.1524391595912]
  We study episodic reinforcement learning in decision processes when the agent receives additional feedback per step. We formalize this setting using a feedback graph over state-action pairs and show that model-based algorithms can leverage the additional feedback for more sample-efficient learning.
  arXiv  Detail & Related papers  (2020-05-07T22:35:37Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.