Study collaborative learning among multi-agents in multi-armed bandits.
problem Minimizing group cumulative regret in a heterogeneous multi-agent setting.
method Developed decentralized algorithms for collaboration between N agents learning M stochastic multi-armed bandits. result Proved near-optimal behavior of proposed algorithms for group regret.
Optimal algorithm found for collaborative learning in bandits with optimal regret bounds.
problem Minimizing regret in collaborative multi-agent bandit problems.
method Proposed an algorithm with optimal regret bounds for collaborative multi-agent multi-armed bandit model.
result First algorithm with order optimal regret bounds for collaborative bandit model.
New algorithms balance collaboration and adversarial behavior in linear bandits.
problem Minimizing regret in a collaborative linear bandit problem with adversarial agents.
method Robust collaborative phased elimination algorithm with tight analyses.
result Achieves near-optimal regret bounds of $O\left(α+ 1/\sqrt{M}
ight) \sqrt{dT}$ for good agents.
New algorithm reduces regret in collaborative multi-agent bandit problems.
problem Optimizing decisions in a network of agents with communication delays.
method Follow-the-Regularized-Leader (FTRL) algorithm with suitable regularizers and communication protocols.
result Upper bound on individual regret matches lower bound up to a constant factor.
New algorithm balances exploration cost between groups in multi-armed bandits.
problem Balancing exploration cost between groups in multi-armed bandits.
method Introducing Col-UCB algorithm that dynamically coordinates exploration across groups.
result Achieves optimal minimax and instance-dependent collaborative regret up to logarithmic factors.
Algorithm maximizes user rewards under per-item budget constraints.
problem Maximizing cumulative rewards in collaborative bandits with budget constraints.
method Collaborative algorithm B-LATTICE that clusters users and collaborates across groups.
result Achieves sub-linear regret bounds matching minimax bounds.
New algorithm for collaborative bandit learning reduces sample complexity and regret.
problem Optimal arm identification in a multi-agent bandit model with communication.
method Phased elimination with data-dependent sampling schemes.
result Near-optimal algorithm for pure exploration in collaborative bandit learning.
There is much empirical evidence that item-item collaborative filtering works well in practice. Motivated to understand this, we provide a framework to design and analyze various recommendation algorithms. The setup amounts to online binary matrix completion, where at each time a random user requests a recommendation a…
New algorithm reduces regret in multi-agent bandits with malicious agents.
problem Collaboration between honest and malicious agents in multi-armed bandits.
method Dynamic reduction of communication with malicious agents, learning who is malicious.
result Algorithm reduces regret even with a single malicious agent, assuming m is small compared to K. We consider a decentralized multi-agent Multi Armed Bandit (MAB) setup consisting of N agents, solving the same MAB instance to minimize individual cumulative regret. In our model, agents collaborate by exchanging messages through pairwise gossip style communications on an arbitrary connected graph. We develop two no…
Algorithm optimizes collaborative learning among distributed clients using kernel-based bandits.
problem Optimizing personalized objectives in a distributed system with limited global information.
method Kernel-based bandit framework with surrogate Gaussian process models, sparse approximations.
result Order-optimal regret performance (up to polylogarithmic factors) and reduced communication overhead.
Partner-aware algorithms improve AI collaboration in multi-agent settings.
problem Improving AI cooperation in teams with shared rewards.
method Proposed Partner-Aware strategy extending Upper Confidence Bound for decentralized MAB.
result Achieves logarithmic regret in collaborative decision-making.
We consider a collaborative online learning paradigm, wherein a group of agents connected through a social network are engaged in playing a stochastic multi-armed bandit game. Each time an agent takes an action, the corresponding reward is instantaneously observed by the agent, as well as its neighbours in the social n…
A collaborative algorithm reduces regret in federated linear contextual bandits.
problem Optimizing decision-making in federated learning with heterogeneous data.
method Fed-PE algorithm, leveraging geometric structure of rewards, multi-client G-optimal design.
result Achieves near-optimal regrets with logarithmic communication costs.
A new algorithm reduces communication costs for collaborative decision-making across clients.
problem Collaborative decision-making with sparse rewards and heterogeneous contexts.
method Federated Lasso algorithm for sparse linear contextual bandits.
result Achieves near-optimal regret with logarithmic communication costs.
Agents collaborate to reduce regret in a multi-agent linear bandit problem with side information.
problem Reducing regret in a multi-agent stochastic linear bandit with side information.
method A decentralized algorithm where agents communicate subspace indices and each plays a projected LinUCB on the corresponding low-dimensional subspace.
result Per-agent finite-time regret is much smaller when agents communicate compared to non-communicating case.
Study on collaborative vs. non-collaborative online and bandit convex optimization.
problem Minimizing average regret in distributed online and bandit convex optimization.
method Analyzes the impact of collaboration in adaptive and zeroth-order feedback settings.
result Collaboration is beneficial in high-dimensional federated online optimization with limited feedback.
New algorithm reduces multi-agent bandit regret by sharing data.
problem Designing efficient collaboration between multi-agent linear bandits.
method Bandit Adaptive Sample Sharing (BASS) algorithm, without assumptions on bandit parameters structure.
result Validated through theoretical analysis and empirical evaluations, BASS outperforms current state-of-the-art.
Optimum-statistical collaboration improves black-box optimization efficiency.
problem Improving black-box optimization efficiency through better statistical collaboration.
method Introducing optimum-statistical collaboration framework for hierarchical bandits-based optimization.
result Demonstrated improved regret bounds and better performance in experiments.
We consider a two-agent MDP framework where agents repeatedly solve a task in a collaborative setting. We study the problem of designing a learning algorithm for the first agent (A1) that facilitates a successful collaboration even in cases when the second agent (A2) is adapting its policy in an unknown way. The key ch…
Two efficient algorithms improve online item recommendation for large user-item matrices.
problem Low rank matrix completion in an online setting with noisy rewards.
method Phased algorithms extsc{PhasedClusterElim} and extsc{DeterminantElim} for item recommendation.
result Near-optimal per-user regret guarantees for item recommendation.
We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating the neighborhood of users in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into …
We study the problem of regret minimization for distributed bandits learning, in which M agents work collaboratively to minimize their total regret under the coordination of a central server. Our goal is to design communication protocols with near-optimal regret and little communication cost, which is measured by the…
We consider an online model for recommendation systems, with each user being recommended an item at each time-step and providing 'like' or 'dislike' feedback. Each user may be recommended a given item at most once. A latent variable model specifies the user preferences: both users and items are clustered into types. Al…
A federated learning algorithm tackles unknown contexts in multi-arm bandits.
problem Learning optimal actions in federated multi-arm bandits with unobserved contexts.
method Elimination-based algorithm for linearly parametrized reward functions.
result Proved regret bound for linearly parametrized reward functions.
In this paper, we introduce a distributed version of the classical stochastic Multi-Arm Bandit (MAB) problem. Our setting consists of a large number of agents n that collaboratively and simultaneously solve the same instance of K armed MAB to minimize the average cumulative regret over all agents. The agents can co…
Agents collaborate to minimize regret while keeping costs under a threshold.
problem Collaborative multi-agent stochastic linear bandits with cost constraints.
method Safe distributed upper confidence bound algorithm (MA-OPLB) with accelerated consensus.
result Regret bound of order $ \mathcal{O}\left(\frac{d}{τ-c_0}\frac{\log(NT)^2}{\sqrt{N}}\sqrt{\frac{T}{\log(1/|λ_2|)}}
ight)$.
Classical collaborative filtering, and content-based filtering methods try to learn a static recommendation model given training data. These approaches are far from ideal in highly dynamic recommendation domains such as news recommendation and computational advertisement, where the set of items and users is very fluid.…
Paper proposes FedQ-Advantage for federated Q-learning with near-optimal regret and low communication cost.
problem Near-optimal federated Q-learning with low communication cost.
method Reference-advantage decomposition for variance reduction, synchronization between agents and server, policy update.
result Achieves almost optimal regret and near-linear regret speedup compared to single-agent learning.
Algorithm reduces regret in distributed kernel bandits with shared randomness.
problem Minimizing regret in collaborative function maximization.
method Uniform exploration at local agents and shared randomness with central server.
result Achieves optimal regret order with sublinear communication cost.
A new federated algorithm reduces regret in X-armed bandit problems.
problem Collaborative optimization of heterogeneous local objectives.
method Fed-PNE algorithm using hierarchical partitioning and weak smoothness.
result Achieves sublinear cumulative regret with minimal communication.
New algorithm reduces regret in multi-agent bandits over undirected graphs.
problem Minimize regret in a multi-agent bandit setting with malicious agents.
method Proposed a new algorithm for undirected graphs, considering the number of malicious neighbors.
result The new algorithm achieves nearly linear regret improvement over existing methods.
We consider the problem of online collaborative filtering in the online setting, where items are recommended to the users over time. At each time step, the user (selected by the environment) consumes an item (selected by the agent) and provides a rating of the selected item. In this paper, we propose a novel algorithm …
The paper addresses the Multiplayer Multi-Armed Bandit (MMAB) problem, where M decision makers or players collaborate to maximize their cumulative reward. When several players select the same arm, a collision occurs and no reward is collected on this arm. Players involved in a collision are informed about this collis…
New protocol reduces communication costs for heterogeneous bandits over complex networks.
problem Minimizing group regret in a multi-agent, heterogeneous bandit setting over complex networks.
method Flooding with Absorption (FwA) protocol for heterogeneous bandits over complex networks.
result FwA protocol significantly reduces communication costs compared to flooding while maintaining similar regret performance.
Paper addresses robust federated linear bandits against Byzantine attacks.
problem Byzantine attacks on a small fraction of agents in federated learning.
method Proposes a geometric median-based robust aggregation oracle.
result Achieves sublinear regret bound of ildeO(T3/4) robust to fewer than half Byzantine agents. Study improves privacy-preserving online prediction from experts with speed-ups.
problem Privacy-preserving online prediction from experts with speed-ups.
method Differentially private federated online prediction algorithms.
result Achieves m-fold regret speed-up with low-loss expert in federated setting. New method learns decisions from collective preferences without individual covariates.
problem Making decisions online without individual covariates.
method Collaborative filtering, matrix completion bandit, ε-greedy policy, online gradient descent, inverse propensity weighting.
result Method outperforms benchmarks and reveals new discoveries.
Federated Q-Learning achieves linear regret speedup with low communication cost.
problem Achieving linear regret speedup in federated reinforcement learning without high communication costs.
method Proposed two federated Q-Learning algorithms: FedQ-Hoeffding and FedQ-Bernstein, using event-triggered synchronization, novel step size selection, and concentration inequalities.
result Total regrets achieve linear speedup compared to single-agent counterparts with logarithmic communication cost.
A novel algorithm minimizes regret in a multi-agent bandit problem with time-varying random graphs and heterogeneous rewards.
problem Minimizing regret in a multi-agent multi-armed bandit problem with time-varying random graphs and heterogeneous rewards.
method Introduces a novel algorithmic framework combining averaging-based consensus with a weighting technique and upper confidence bound.
result Derives optimal instance-dependent regret upper bounds of order logT in both sub-gaussian and sub-exponential environments. We consider the problem of recommending relevant labels (items) for a given data point (user). In particular, we are interested in the practically important setting where the evaluation is with respect to non-decomposable (over labels) performance metrics like the F1 measure, and the training data has missing labels…
New method for online low-rank matrix completion with improved regret.
problem Designing an efficient algorithm for online recommendation systems with low regret.
method Explore-then-commit (ETC) approach and iterative user clustering (OCTAL) for rank-1 setting.
result Nearly optimal regret bounds for online low-rank matrix completion.
New algorithms reduce communication costs in collaborative learning.
problem Reducing communication costs in collaborative learning.
method Distributed boosting and adaptation to classification noise.
result Communication-efficient algorithms for collaborative PAC learning robust to noise.
A new federated bandit problem with multiple adversaries, solved with a near-optimal algorithm.
problem Non-stochastic federated multi-armed bandit problem with multiple adversaries.
method Proposed a near-optimal federated bandit algorithm called FEDEXP3.
result Guaranteed sub-linear regret without exchanging sequences of selected arm identities or loss sequences among agents.
Supply Chain Management often requires independent organizations to work together to achieve shared objectives. This collaboration is necessary when coordinated actions benefit the group more than the uncoordinated efforts of individual firms. Despite the commonly reported benefits that can be gained in close relations…
This paper considers the problem of high dimensional signal detection in a large distributed network whose nodes can collaborate with their one-hop neighboring nodes (spatial collaboration). We assume that only a small subset of nodes communicate with the Fusion Center (FC). We design optimal collaboration strategies w…
A new algorithm improves stochastic linear bandit performance using residual bootstrap.
problem Improving performance in stochastic linear bandit problems.
method Residual bootstrap exploration to estimate mean reward and pull the arm with the highest estimate.
result Proposed algorithm exttt{LinReBoot} achieves high-probability sub-linear regret under mild conditions.
FedConPE improves conversational recommender systems efficiency and privacy.
problem Efficiently eliciting user preferences in interactive systems with heterogeneous clients.
method Phase elimination-based federated conversational bandit algorithm with adaptive key term construction.
result Minimizes uncertainty across all dimensions in feature space and offers improved efficiency and privacy.