New bandit problem for finding best group of arms with worst mean reward.
problem Finding the best group of arms with the worst mean reward in overlapping groups.
method Two algorithms based on successive elimination and robust optimization.
result Upper bounds on the number of samples to find max-min optimal or near-optimal group.
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.
Study invariant Lipschitz bandits, improving regret bounds.
problem Optimizing decisions under symmetry in online settings.
method Integrates side observations using group orbits into UniformMesh algorithm.
result Improved regret bound for invariant Lipschitz bandit class.
AGG-UCB uses neural networks to optimize group behaviors in contextual bandits.
problem Optimizing group behaviors in contextual bandits with mutual impacts.
method Introduces Arm Group Graph (AGG) and AGG-UCB algorithm using neural networks and graph neural networks.
result Achieves near-optimal regret bound with over-parameterized neural networks.
The paper tackles a bandit problem with infinitely many arms per group, aiming to identify the group with the highest quantile reward.
problem Max-quantile group bandit problem with infinitely many arms per group.
method Two-step algorithm: first request arms from each group, then apply a finite-arm max-quantile bandit algorithm.
result Characterization of instance-dependent and worst-case regret, with matching lower bounds.
A new algorithm balances global reward and group constraints in federated multi-armed bandits.
problem Maximizing global reward while protecting client privacy in federated learning.
method Combinatorial contextual bandit with group constraints, using a two-output Gaussian process.
result TCGP-UCB incurs low regret, balancing super arm reward and group reward constraints.
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 N N agents learning M M M stochastic multi-armed bandits. result Proved near-optimal behavior of proposed algorithms for group regret.
New algorithm finds best feasible arm in grouped bandits.
problem Finding the best arm with all attributes above a threshold.
method Feasibility Constrained Successive Rejects (FCSR) algorithm.
result FCSR identifies the best feasible arm with optimal dependence on problem parameters.
New algorithm for bandits with delayed action effects, reducing regret.
problem Delayed impact of actions in multi-armed bandits.
method Formulated a new bandit setting with delayed action effects, proposed an algorithm with regret bound.
result Achieved a regret of i l d e O ( K T 2 / 3 ) ilde{\mathcal{O}}(KT^{2/3}) i l d e O ( K T 2/3 ) and showed a matching lower bound. ComEx protocol reduces communication costs in cooperative bandits.
problem Minimizing communication costs in cooperative bandits while maintaining optimal performance.
method Developed ComEx protocol to reduce communication from Θ ( T ) Θ(T) Θ ( T ) to O ( log T ) O(\log T) O ( log T ) messages. result Achieves state-of-the-art performance with significantly reduced communication cost.
New algorithm reduces individual regret and communication costs in cooperative bandits.
problem Optimal individual and group regret in cooperative multi-agent bandits.
method Integrates a new communication policy into a learning algorithm.
result Achieves optimal individual regret and constant communication costs.
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…
Unified framework for high-dimensional bandit problems with low-dimensional structures.
problem Stochastic high-dimensional bandit problems with low-dimensional structures.
method Proposed a simple unified algorithm and a general analysis framework for the regret upper bound.
result Unified algorithm achieves comparable regret bounds in various high-dimensional bandit problems.
Study cooperative bandit learning with imperfect communication, achieving near-optimal performance.
problem Real-world distributed decision-making with imperfect communication.
method Proposed decentralized algorithms for three communication scenarios: stochastic networks, random delays, and adversarially corrupted rewards.
result Achieved competitive performance and near-optimal guarantees on group regret.
New algorithm minimizes regret in multi-agent bandit problem with probabilistic communication.
problem Minimizing group regret in multi-agent multi-armed bandit problem with probabilistic communication.
method Proposes a new UCB-based algorithm for decentralized multi-agent multi-armed bandit problem on d d d -regular graphs with probabilistic communication. result The proposed algorithm outperforms state-of-the-art algorithms in minimizing group regret.
A new algorithm reduces regret in cooperative multi-agent bandits with heavy-tailed data.
problem Cooperative multi-agent bandits with heavy-tailed data.
method MP-UCB algorithm incorporating robust estimation with message-passing protocol.
result Optimal regret bounds for MP-UCB in various settings.
We analyze how batch learning impacts bandit problems.
problem Impact of batch learning in stochastic bandits.
method Policy-agnostic regret analysis, upper and lower bounds demonstration.
result The impact of batch learning can be measured in terms of online behavior.
New algorithms allocate sampling budget to estimate group means without exploration.
problem Allocate sampling budget to estimate means of multiple groups.
method Design exploration-free non-adaptive and adaptive algorithms.
result Prove tighter regret bounds for multi-group mean estimation.
New algorithm reduces clustering cost in bandit feedback.
problem Discovering hidden groupings in stochastic bandit feedback.
method ACB algorithm for active clustering with non-asymptotic lower bound.
result ACB algorithm's budget matches lower bound in most regimes.
The paper tackles fair sharing of exploration costs across groups in online learning.
problem Sharing the cost of exploration fairly across multiple groups in online learning.
method The paper introduces the 'grouped' bandit model and uses axiomatic bargaining theory, specifically the Nash bargaining solution, to formalize fairness.
result The paper derives policies that are optimally fair and regret-optimal, showing that regret-optimal policies can be unfair.
New bandit model for e-commerce with ordered categories.
problem Optimizing customer experience in e-commerce with unknown preferences.
method Introducing three types of ordering between categories and proving lower bounds on cumulative regret.
result Proved that algorithms can fully leverage the structure of the model with theoretical guarantees.
Study adapts combinatorial semi-bandit for piecewise stationary, causally related rewards.
problem Nonstationary environment with changing base arms' distributions and causal relationships.
method Upper Confidence Bound (UCB) algorithm with change-point detector and group restart strategy.
result Regret upper bound reflecting effects of structural and distribution changes.
Kernel method improves cooperative decision-making among agents.
problem Cooperative multi-agent decision making with contextual information.
method Proposed extsc{Coop-KernelUCB} algorithm for near-optimal per-agent regret.
result Near-optimal bounds on per-agent regret with efficient computation and communication.
Study on a new family of problems interpolating expert advice and multi-armed bandits.
problem A new family of problems combining expert advice and multi-armed bandits.
method Proved minimax regret bounds and designed optimal PAC algorithms for pure exploration.
result Tight minimax regret bounds and optimal PAC algorithm for m \mathbf{m} m -BAI. Improved regret bounds for structured linear contextual bandits with Gaussian noise.
problem Optimizing bandit learning algorithms for structured contexts with Gaussian perturbations.
method Proposed simple greedy algorithms for structured linear contextual bandits with Gaussian noise.
result Unified regret analysis for structured parameters with geometric quantities as bounds.
A fair policy for hiring candidates from different groups is proposed in a linear contextual bandit problem.
problem Selecting candidates from different sensitive groups in a fair manner.
method A greedy policy that constructs a ridge regression estimate and computes relative rank using empirical cumulative distribution function.
result The greedy policy achieves fair pseudo-regret of order d T \sqrt{dT} d T after T T T rounds, satisfying demographic parity. Bandit algorithms optimize treatment decisions for precision medicine.
problem Optimizing treatment decisions for individual patients based on genetic or molecular profiling.
method Contextual bandit algorithms that consider patient characteristics.
result Bandit algorithms are useful for mobile health and digital phenotyping.
Paper optimizes clustering with bandit feedback, reducing errors.
problem Online clustering with bandit feedback, minimizing errors.
method Instance-dependent information-theoretic lower bound, BOC algorithm with adaptive stopping rule.
result BOC algorithm matches lower bound asymptotically and significantly outperforms non-adaptive baseline.
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.
Multi-armed bandit problems are receiving a great deal of attention because they adequately formalize the exploration-exploitation trade-offs arising in several industrially relevant applications, such as online advertisement and, more generally, recommendation systems. In many cases, however, these applications have a…
New algorithm reduces super-arm selection complexity exponentially.
problem Combinatorial multi-armed bandits with cardinality constraint.
method Combination of group-testing and quantized Thompson sampling.
result Achieves same regret order as state-of-the-art algorithms with perfect oracle, but with reduced complexity.
Paper tackles outlier detection in multi-armed bandits, achieving high accuracy with reduced exploration costs.
problem Detecting outlier arms in multi-armed bandit settings.
method Proposes GOLD algorithm based on upper confidence bounds to identify generic outlier arms.
result Achieves 98% accuracy with 83% reduction in exploration cost compared to state-of-the-art techniques.
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…
Selective reinitialization improves adaptability of neural bandits in dynamic environments.
problem Loss of plasticity in neural bandits, leading to rigid neural network parameters.
method Selective Reinitialization (SeRe) framework that dynamically resets underutilized units.
result SeRe enhances adaptability of CNB algorithms, reducing cumulative regret in dynamic environments.
New framework tackles stochastic latent subgroup heterogeneity in online decision-making.
problem Stochastic latent heterogeneity in online decision-making where individual responses vary with unobserved subgroups.
method Latent heterogeneous bandit framework using EM-greedy algorithm to learn subgroup probabilities and reward parameters.
result Achieves optimal estimation and classification guarantees, revealing a fundamental stochastic barrier in online decision-making.
Two new algorithms improve online clustering of bandits by accelerating cluster identification without strong assumptions.
problem Challenges in accurately identifying unknown user clusters in online bandit settings.
method Proposes UniCLUB and PhaseUniCLUB algorithms with enhanced exploration mechanisms.
result Achieves comparable regret bounds to prior work with weaker assumptions.
Adaptive clustering and personalization algorithms minimize regret in multi-agent stochastic linear bandits.
problem Minimizing regret in a multi-agent stochastic linear bandits framework with user heterogeneity.
method Proposes a novel algorithm that refines cluster identities and minimizes regret, adapting to cluster separation and user parameter deviations.
result Regret scales as O ( T / N ) \mathcal{O}(\sqrt{T/N}) O ( T / N ) for well-separated clusters and O ( T 1 2 + ε / ( N ) 1 2 − ε ) \mathcal{O}(T^{\frac{1}{2} + \varepsilon}/(N)^{\frac{1}{2} -\varepsilon}) O ( T 2 1 + ε / ( N ) 2 1 − ε ) for poorly separated clusters. An algorithm for efficient experimentation in a dynamic environment with personalized preferences and context drifts.
problem Efficiently recommending decisions to users with personalized preferences in a context where the environment is changing over time.
method Dri-MED, inspired from the linear version of the MED strategy, adapted to handle non-stationary heteroskedastic noise.
result The instance-dependent regret scales as $ ilde{\mathcal O}\left(\fracκ{ ildeΔ}d^2(\log(T)
ight)$ , with i l d e Δ ildeΔ i l d e Δ being the constraint-aware sub-optimality gap. 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.…
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…
We consider the online multiclass linear classification under the bandit feedback setting. Beygelzimer, Pál, Szörényi, Thiruvenkatachari, Wei, and Zhang [ICML'19] considered two notions of linear separability, weak and strong linear separability. When examples are strongly linearly separable with margin γ γ γ , they prese…
Algorithm clusters items by sequentially selecting features, minimizing observations.
problem Clustering items based on bandit feedback with many features.
method Sequential Halving algorithm for feature selection.
result Accurate recovery of item partition with minimal observations.
Agents cooperate to make decisions in multi-armed bandits over a graph.
problem Optimizing decisions in multi-agent multi-armed bandits with shared information.
method Designs consensus-based distributed estimation and cooperative algorithms for group decision-making.
result Achieves group performance close to centralized fusion center.
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…
Develops a framework for clustering and distribution matching with bandit feedback.
problem Clustering and distribution matching problems with limited feedback.
method General framework using K K K -armed bandit model, Track-and-Stop method, and Frank--Wolfe algorithm. result Average number of arm pulls matches lower bound, with asymptotic convergence to fundamental limit.
New strategies improve multi-agent decision-making on irregular networks.
problem Maximizing group reward in multi-agent settings with heterogeneous strategies.
method Design and analysis of heterogeneous explore-exploit strategies for multi-star networks.
result Group performance improves under heterogeneous strategies compared to homogeneous strategies.
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.
Study symmetric linear bandits with hidden symmetry, achieving improved regret bounds.
problem High-dimensional linear bandits with hidden symmetry.
method Model selection within low-dimensional subspaces to learn hidden symmetry.
result Achieved improved regret bounds of O ( d 0 2 / 3 T 2 / 3 log ( d ) ) O(d_0^{2/3} T^{2/3} \log(d)) O ( d 0 2/3 T 2/3 log ( d )) and O ( d 0 T log ( d ) ) O(d_0\sqrt{T\log(d)} ) O ( d 0 T log ( d ) ) .