Pure Exploration with Feedback Graphs

• URL: http://arxiv.org/abs/2503.07824v1
• Date: Mon, 10 Mar 2025 20:11:59 GMT
• Title: Pure Exploration with Feedback Graphs
• Authors: Alessio Russo, Yichen Song, Aldo Pacchiano,
• Abstract summary: We study the sample complexity of pure exploration in an online learning problem with a feedback graph.<n>We derive an instance-specific lower bound on the sample complexity of learning the best action with fixed confidence.<n>Our findings reveal how the sample complexity scales with key graph-dependent quantities.
• Score: 23.16863295063427
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the sample complexity of pure exploration in an online learning problem with a feedback graph. This graph dictates the feedback available to the learner, covering scenarios between full-information, pure bandit feedback, and settings with no feedback on the chosen action. While variants of this problem have been investigated for regret minimization, no prior work has addressed the pure exploration setting, which is the focus of our study. We derive an instance-specific lower bound on the sample complexity of learning the best action with fixed confidence, even when the feedback graph is unknown and stochastic, and present unidentifiability results for Bernoulli rewards. Additionally, our findings reveal how the sample complexity scales with key graph-dependent quantities. Lastly, we introduce TaS-FG (Track and Stop for Feedback Graphs), an asymptotically optimal algorithm, and demonstrate its efficiency across different graph configurations.

Related papers

• Towards joint graph learning and sampling set selection from data [27.52699981080567]
  We explore the problem of sampling graph signals in scenarios where the graph structure is not predefined.<n>Existing approaches rely on a two-step process, where a graph is learned first, followed by sampling.<n>This work provides a foundational step towards jointly optimizing the graph structure and sampling set.
  arXiv  Detail & Related papers  (2024-12-12T23:05:40Z)
• Uncertainty-Aware Robust Learning on Noisy Graphs [22.848589361600382]
  We propose a novel uncertainty-aware graph learning framework inspired by distributionally robust optimization. We use a graph neural network-based encoder to embed the node features and find the optimal node embeddings. Such an uncertainty-aware learning process leads to improved node representations and a more robust graph predictive model.
  arXiv  Detail & Related papers  (2023-06-14T02:45:14Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  We propose a novel non-parametric subgraph matching framework, dubbed MatchExplainer, to explore explanatory subgraphs. It couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding-based distance. Experiments on synthetic and real-world datasets show the effectiveness of our MatchExplainer by outperforming all state-of-the-art parametric baselines with significant margins.
  arXiv  Detail & Related papers  (2023-01-07T05:14:45Z)
• Joint graph learning from Gaussian observations in the presence of hidden nodes [26.133725549667734]
  We propose a joint graph learning method that takes into account the presence of hidden (latent) variables. We exploit the structure resulting from the previous considerations to propose a convex optimization problem. We compare the proposed algorithm with different baselines and evaluate its performance over synthetic and real-world graphs.
  arXiv  Detail & Related papers  (2022-12-04T13:03:41Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Context-Aware Graph Convolution Network for Target Re-identification [61.34688291210318]
  The proposed method achieves state-of-the-art performance on both person and vehicle re-identification datasets. We present a novel Context-Aware Graph Convolution Network (CAGCN), where the probe-gallery relations are encoded into the graph nodes. Experiments show that the proposed method achieves state-of-the-art performance on both person and vehicle re-identification datasets.
  arXiv  Detail & Related papers  (2020-12-08T09:18:39Z)
• 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)
• Sample Efficient Graph-Based Optimization with Noisy Observations [17.91308664586981]
  We show that a variant of best-arm identification can find a near-optimal solution after a small number of queries independent of the size of the graph. We show effectiveness of the greedy algorithm with restarts and the simulated annealing on problems of graph-based nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-06-04T07:22:28Z)
• 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)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

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.