arXiv research

AGG-UCB uses neural networks to optimize group behaviors in contextual bandits.

Study on a new family of problems interpolating expert advice and multi-armed bandits.

We study a distributed decision-making problem in which multiple agents face the same multi-armed bandit (MAB), and each agent makes sequential choices among arms to maximize its own individual reward. The agents cooperate by sharing their estimates over a fixed communication graph. We consider an unconstrained reward …

Paper tackles outlier detection in multi-armed bandits, achieving high accuracy with reduced exploration costs.

New algorithm minimizes regret in multi-agent bandit problem with probabilistic communication.

Graph-Triggered Bandits unify rested and restless bandits with graph-defined arm interactions.

We consider a problem of stochastic online learning with general probabilistic graph feedback, where each directed edge in the feedback graph has probability $p_{ij}$. Two cases are covered. (a) The one-step case, where after playing arm $i$ the learner observes a sample reward feedback of arm $j$ with independent prob…

In this paper, we introduce a new online decision making paradigm that we call Thresholding Graph Bandits. The main goal is to efficiently identify a subset of arms in a multi-armed bandit problem whose means are above a specified threshold. While traditionally in such problems, the arms are assumed to be independent, …

New algorithms optimize decision-making under uncertainty with graph information.

Paper tackles efficient BAI in graph-smooth bandits.

The paper tackles a bandit problem with infinitely many arms per group, aiming to identify the group with the highest quantile reward.

A graph bandit algorithm learns optimal paths on unknown graphs.

We study the stochastic multi-armed bandit problem with the graph-based feedback structure introduced by Mannor and Shamir. We analyze the performance of the two most prominent stochastic bandit algorithms, Thompson Sampling and Upper Confidence Bound (UCB), in the graph-based feedback setting. We show that these algor…

We study small-loss bounds for adversarial multi-armed bandits with graph feedback, that is, adaptive regret bounds that depend on the loss of the best arm or related quantities, instead of the total number of rounds. We derive the first small-loss bound for general strongly observable graphs, resolving an open problem…

Study local exploration on dynamic graphs with time-varying edges.

New algorithm finds best feasible arm in grouped bandits.

A new algorithm balances global reward and group constraints in federated multi-armed bandits.

In this paper, we solve the arms exponential exploding issue in multivariate Multi-Armed Bandit (Multivariate-MAB) problem when the arm dimension hierarchy is considered. We propose a framework called path planning (TS-PP) which utilizes decision graph/trees to model arm reward success rate with m-way dimension interac…

This paper extends combinatorial semi-bandits to graph feedback, improving regret bounds.

Algorithm reduces decision-making errors in multi-agent bandit problems.

We investigate an efficient context-dependent clustering technique for recommender systems based on exploration-exploitation strategies through multi-armed bandits over multiple users. Our algorithm dynamically groups users based on their observed behavioral similarity during a sequence of logged activities. In doing s…

We study, to the best of our knowledge, the first Bayesian algorithm for unimodal Multi-Armed Bandit (MAB) problems with graph structure. In this setting, each arm corresponds to a node of a graph and each edge provides a relationship, unknown to the learner, between two nodes in terms of expected reward. Furthermore, …

New bandit problem for finding best group of arms with worst mean reward.

We propose a novel formulation of group fairness with biased feedback in the contextual multi-armed bandit (CMAB) setting. In the CMAB setting, a sequential decision maker must, at each time step, choose an arm to pull from a finite set of arms after observing some context for each of the potential arm pulls. In our mo…

New algorithm tackles multi-agent bandits with heavy-tailed data.

Bandit is a framework for designing sequential experiments. In each experiment, a learner selects an arm $A \in \mathcal{A}$ and obtains an observation corresponding to $A$. Theoretically, the tight regret lower-bound for the general bandit is polynomial with respect to the number of arms $|\mathcal{A}|$. This makes ba…

New algorithm reduces super-arm selection complexity exponentially.

A novel algorithm minimizes regret in a multi-agent bandit problem with time-varying random graphs and heterogeneous rewards.

We formulate the problem of sampling and recovering clustered graph signal as a multi-armed bandit (MAB) problem. This formulation lends naturally to learning sampling strategies using the well-known gradient MAB algorithm. In particular, the sampling strategy is represented as a probability distribution over the indiv…

A new algorithm tackles graph-based contextual bandits with efficient regret bounds.

Two algorithms minimize regret in adversarial bandit problems with side-observation losses.

New algorithm balances exploration cost between groups in multi-armed bandits.

We consider a variant of the classic multi-armed bandit problem where the expected reward of each arm is a function of an unknown parameter. The arms are divided into different groups, each of which has a common parameter. Therefore, when the player selects an arm at each time slot, information of other arms in the sam…

New algorithm eliminates arms to minimize regret in complex bandit problems.

This paper proposes a novel policy for a group of agents to, individually as well as collectively, solve a multi armed bandit (MAB) problem. The policy relies solely on the information that an agent has obtained through sampling of the options on its own and through communication with neighbors. The option selection po…

We present a formal model of human decision-making in explore-exploit tasks using the context of multi-armed bandit problems, where the decision-maker must choose among multiple options with uncertain rewards. We address the standard multi-armed bandit problem, the multi-armed bandit problem with transition costs, and …

New algorithm reduces regret in multi-agent bandits over undirected graphs.

New study on regret lower bounds for multi-agent multi-armed bandit problems.

BAICS identifies best arm with fairness constraints on subpopulations.

New graph feedback model for bandits with improved regret bounds.

Study collaborative learning among multi-agents in multi-armed bandits.

We study the explore-exploit tradeoff in distributed cooperative decision-making using the context of the multiarmed bandit (MAB) problem. For the distributed cooperative MAB problem, we design the cooperative UCB algorithm that comprises two interleaved distributed processes: (i) running consensus algorithms for estim…

Develops a framework for clustering and distribution matching with bandit feedback.

Study on individual regret in cooperative MAB with agents communicating over a graph.

New algorithm improves bandit with graph feedback by decomposing regret.

Boltzmann exploration is widely used in reinforcement learning to provide a trade-off between exploration and exploitation. Recently, in (Cesa-Bianchi et al., 2017) it has been shown that pure Boltzmann exploration does not perform well from a regret perspective, even in the simplest setting of stochastic multi-armed b…

Optimizes arm selection with side information in Gaussian bandits.

Algorithm identifies best arm in bandit game with variance consideration.