Related papers: Bandits on graphs and structures

Bandits on graphs and structures

URL: http://arxiv.org/abs/2605.03493v1
Date: Tue, 05 May 2026 08:33:24 GMT
Title: Bandits on graphs and structures
Abstract summary: The goal of this thesis is to investigate the structural properties of certain problems in order to bring the solutions closer to a practical use.<n>In the first part, we put a special emphasis on structures that can be represented as graphs on actions.<n>In the second part, we study the large action spaces that can be of exponential size in the number of base actions or even infinite.
Score: 19.66115828957497
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The goal of this thesis is to investigate the structural properties of certain sequential problems in order to bring the solutions closer to a practical use. In the first part, we put a special emphasis on structures that can be represented as graphs on actions. In the second part, we study the large action spaces that can be of exponential size in the number of base actions or even infinite. For graph bandits, we consider the settings of smoothness of rewards (spectral bandits), side observations, and influence maximization. For large structured domains, we cover kernel bandits, polymatroid bandits, bandits for function optimization (including unknown smoothness), and infinitely many-arms bandits. The thesis aspires to be a survey of the author's contributions on graph and structured bandits.

Related papers

Revealing graph bandits for maximizing local influence [64.91400609178565]
We study a graph bandit setting where the objective of the learner is to detect the most influential node of a graph by requesting as little information from the graph as possible.<n>One of the relevant applications for this setting is marketing in social networks, where the marketer aims at finding and taking advantage of the most influential customers.
arXiv Detail & Related papers (2026-05-01T07:54:58Z)
Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Bandits is a framework to generalize rested and restless bandits. In this work, we focus on two specific types of monotonic bandits: rising, where the expected reward of an arm grows as the number of triggers increases, and rotting, where the opposite behavior occurs.
arXiv Detail & Related papers (2024-09-09T18:23:07Z)
Stochastic contextual bandits with graph feedback: from independence number to MAS number [28.10186884181921]
We consider contextual bandits with graph feedback. Unlike the multi-armed bandits setting, much remains unexplored in the contextual bandits counterpart. We provide algorithms that achieve near-optimal regret for important classes of context sequences and/or feedback graphs.
arXiv Detail & Related papers (2024-02-12T06:56:13Z)
Causal Bandits with Unknown Graph Structure [24.58691421788476]
We develop novel causal bandit algorithms without knowing the causal graph. Our algorithms work well for causal trees, causal forests and a general class of causal graphs.
arXiv Detail & Related papers (2021-06-05T23:41:38Z)
Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
Combinatorial bandits generalize multi-armed bandits, where the agent chooses sets of arms and observes a noisy reward for each arm contained in the chosen set. We focus on the pure-exploration problem of identifying the best arm with fixed confidence, as well as a more general setting, where the structure of the answer set differs from the one of the action set. Based on a projection-free online learning algorithm for finite polytopes, it is the first computationally efficient algorithm which is convexally optimal and has competitive empirical performance.
arXiv Detail & Related papers (2021-01-21T10:35:09Z)
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)
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)
Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems [40.957688390621385]
Our framework captures complex statistical dependencies between actions, latent variables, and observations. We develop novel online learning algorithms that learn to act efficiently in our models.
arXiv Detail & Related papers (2020-07-09T16:25:40Z)
A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
We study finite-armed bandits where the rewards of each arm might be correlated to those of other arms. We introduce a novel phased algorithm that exploits the given structure to build confidence sets over the parameters of the true bandit problem.
arXiv Detail & Related papers (2020-05-23T19:52:44Z)
Predictive Bandits [68.8204255655161]
We introduce and study a new class of bandit problems, referred to as predictive bandits. In each round, the decision maker first decides whether to gather information about the rewards of particular arms. The decision maker then selects an arm to be actually played in the round.
arXiv Detail & Related papers (2020-04-02T17:12:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.