Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference

• URL: http://arxiv.org/abs/2503.07555v2
• Date: Thu, 12 Jun 2025 12:49:14 GMT
• Title: Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference
• Authors: Fateme Jamshidi, Mohammad Shahverdikondori, Negar Kiyavash,
• Abstract summary: We study multi-armed bandits under network interference.<n>This induces an exponentially large action space.<n>We propose a novel algorithm that uses the local graph structure to minimize regret.
• Score: 18.101059380671582
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study multi-armed bandits under network interference, where each unit's reward depends on its own treatment and those of its neighbors in a given graph. This induces an exponentially large action space, making standard approaches computationally impractical. We propose a novel algorithm that uses the local graph structure to minimize regret. We derive a graph-dependent upper bound on cumulative regret that improves over prior work. Additionally, we provide the first lower bounds for bandits with arbitrary network interference, where each bound involves a distinct structural property of the graph. These bounds show that for both dense and sparse graphs, our algorithm is nearly optimal, with matching upper and lower bounds up to logarithmic factors. When the interference graph is unknown, a variant of our algorithm is Pareto optimal: no algorithm can uniformly outperform it across all instances. We complement our theoretical results with numerical experiments, showing that our approach outperforms the baseline methods.

Related papers

• Influential Bandits: Pulling an Arm May Change the Environment [44.71145269686588]
  Real-world applications often involve non-stationary environments and interdependencies between arms. We propose the influential bandit problem, which models inter-arm interactions through an unknown, symmetric, positive semi-definite interaction matrix. We introduce a new algorithm based on a lower confidence bound (LCB) estimator tailored to the structure of the loss dynamics.
  arXiv  Detail & Related papers  (2025-04-11T02:05:51Z)
• Causal bandits with backdoor adjustment on unknown Gaussian DAGs [5.807183284468881]
  We study the causal bandit problem when the graph structure is unknown.<n>We identify backdoor adjustment sets for each arm using sequentially generated experimental and observational data.<n>We develop a novel bandit algorithm, based on modified upper confidence bounds, to sequentially determine the optimal intervention.
  arXiv  Detail & Related papers  (2025-02-04T05:18:35Z)
• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  We study learning problems on correlated block models with two balanced communities.<n>Our main result gives the first efficient algorithm for graph matching in this setting.<n>We extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible.
  arXiv  Detail & Related papers  (2024-12-03T18:36:45Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  We make novel use of sparsification techniques from the non-private streaming and static algorithms literature to achieve new results in the sublinear space, continual release setting.<n>This includes algorithms for densest subgraph, maximum matching, and the first continual release $k$-core decomposition algorithm.
  arXiv  Detail & Related papers  (2024-07-24T20:15:07Z)
• Influence Maximization via Graph Neural Bandits [54.45552721334886]
  We set the IM problem in a multi-round diffusion campaign, aiming to maximize the number of distinct users that are influenced. We propose the framework IM-GNB (Influence Maximization with Graph Neural Bandits), where we provide an estimate of the users' probabilities of being influenced.
  arXiv  Detail & Related papers  (2024-06-18T17:54:33Z)
• Multi-Armed Bandits with Network Interference [5.708360037632367]
  We study a multi-armed bandit (MAB) problem where a learner sequentially assigns one of possible $mathcalA$ actions (discounts) to $N$ units (goods) over $T$ rounds to minimize regret. Unlike traditional MAB problems, the reward of each unit depends on the treatments assigned to other units, i.e., there is interference across the underlying network of units. We propose simple, linear regression-based algorithms to minimize regret.
  arXiv  Detail & Related papers  (2024-05-28T22:01:50Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  We provide an efficient ($epsilon,$delta$)-DP algorithm tailored specifically for such graphs. Our algorithm works for well-clustered graphs with $k$ nearly-balanced clusters.
  arXiv  Detail & Related papers  (2024-03-21T11:57:16Z)
• An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem [9.400610985728441]
  The Maximum s-Bundle Problem (MBP) addresses the task of identifying a maximum s-bundle in a given graph. We introduce a novel Partition-based Upper Bound (PUB) that leverages the graph partitioning technique to achieve a tighter upper bound. We also propose a new BnB algorithm that uses the initial lower bound and PUB in preprocessing for graph reduction.
  arXiv  Detail & Related papers  (2024-02-06T06:05:11Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Improved Exact and Heuristic Algorithms for Maximum Weight Clique [1.2074552857379273]
  We propose improved exact and labeling algorithms for solving the maximum weight clique problem. Our algorithms interleave successful techniques with novel data reduction rules that use local graph structure. We evaluate our algorithms on a range of synthetic and real-world graphs, and find that they outperform the current state of the art on most inputs.
  arXiv  Detail & Related papers  (2023-02-01T14:02:06Z)
• Causal Bandits without Graph Learning [28.021500949026766]
  We develop an efficient algorithm for finding the parent node of the reward node using atomic interventions. We extend our algorithm to the case when the reward node has multiple parents.
  arXiv  Detail & Related papers  (2023-01-26T20:27:14Z)
• Local Graph-homomorphic Processing for Privatized Distributed Systems [57.14673504239551]
  We show that the added noise does not affect the performance of the learned model. This is a significant improvement to previous works on differential privacy for distributed algorithms.
  arXiv  Detail & Related papers  (2022-10-26T10:00:14Z)
• Inverse Boundary Value and Optimal Control Problems on Graphs: A Neural and Numerical Synthesis [0.0]
  A key piece in the present architecture is our boundary injected message passing neural network. A regularization technique based on graphical distance is introduced that helps with stabilizing the predictions at nodes far from the boundary.
  arXiv  Detail & Related papers  (2022-06-06T21:26:23Z)
• 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)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems [30.759279275710078]
  We propose a new and scalable approach to computing index-based solutions. We provide algorithms designed to capture index decay without having to solve the costly finite horizon problem. Our algorithms achieve an over 150x speed-up over existing methods in these tasks without loss in performance.
  arXiv  Detail & Related papers  (2021-03-08T13:10:31Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

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.