New lower bounds for combinatorial multi-armed bandits for general reward functions.
problem Maximizing reward in sequential decisions with sets of arms.
method Proved tight regret lower bounds for all smooth reward functions under mild assumptions.
result Lower bounds are tight up to log-factors for monotone reward functions.
Master-slave architecture tackles combinatorial multi-armed bandits with diversity constraints.
problem Solving top- K K K combinatorial multi-armed bandits with non-linear feedback and diversity constraints. method Master-slave architecture with six slave models, teacher learning, and policy co-training.
result Significantly outperforms existing algorithms in synthetic and real datasets.
Improved statistical efficiency of Thompson Sampling for combinatorial semi-bandits.
problem Efficiency of policies in stochastic combinatorial multi-armed bandits with semi-bandit feedback.
method Analysis of Combinatorial Thompson Sampling (CTS) using Beta and Gaussian priors for mutually independent and multivariate sub-Gaussian outcomes.
result CTS provides an efficient policy with optimal asymptotic regret for both mutually independent and multivariate sub-Gaussian outcomes.
Study on reward poisoning attacks on CMAB, revealing attackability depends on adversary's knowledge.
problem Reward poisoning attacks on Combinatorial Multi-Armed Bandits (CMAB).
method Provided a sufficient and necessary condition for attackability, devised an attack algorithm.
result Attackability of CMAB depends on adversary's knowledge of the bandit instance.
We analyze the regret of combinatorial Thompson sampling (CTS) for the combinatorial multi-armed bandit with probabilistically triggered arms under the semi-bandit feedback setting. We assume that the learner has access to an exact optimization oracle but does not know the expected base arm outcomes beforehand. When th…
Reduces user feedback needed for accurate recommender systems.
problem Limited user feedback in recommender systems.
method Partial Bandit and Semi-Bandit approach for efficient user feedback retrieval.
result Similar global accuracy and learning efficiency with reduced feedback.
This paper tackles combinatorial optimization under uncertainty with limited feedback.
problem Tackling combinatorial optimization problems with uncertain or unknown parameters.
method Review of techniques for combinatorial pure exploration with limited bandit feedback.
result Introduction of methods for combinatorial optimization under uncertainty with limited observation.
New algorithm eliminates arms to minimize regret in complex bandit problems.
problem Minimizing regret in combinatorial bandit problems with explicit exploration.
method Introduces a novel arm elimination scheme that partitions arms into three categories and incorporates explicit exploration.
result Achieves near-optimal regret in combinatorial multi-armed and linear contextual bandit problems.
A new algorithm for top-k combinatorial bandits with full-bandit feedback.
problem Optimizing decisions among subsets of arms with only aggregate rewards observed.
method CSAR algorithm using Hadamard matrices for estimating individual arm rewards.
result Proved a tight lower bound on sample complexity for k = O ( 1 ) k=O(1) k = O ( 1 ) . This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting under semi-bandit feedback, we derive a problem-specific regret lower bound, and discuss its scaling with the dimension of the decision space. We propose ESCB, an algorithm that efficiently exploits t…
Study resource allocation strategies in sequential decisions with unknown rewards.
problem Sequential resource allocation with unknown rewards.
method Design combinatorial multi-armed bandit algorithms for discrete or continuous budgets.
result Prove algorithms achieve logarithmic cumulative regret under semi-bandit feedback.
Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.
problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.
method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.
result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret with O ( log log T ) O(\log\log T) O ( log log T ) oracle queries for worst-case linear rewards. Paper uses CMAB to improve NAS efficiency and accuracy.
problem Improving efficiency and accuracy of NAS for DNNs.
method Formulated NAS as CMAB, used Nested Monte-Carlo Search.
result Discovered cell structure achieves comparable accuracy to state-of-the-art, 20x faster.
New algorithm tackles unknown utility network resource allocation.
problem Maximizing network utility with unknown agent utilities.
method Modeling as a bandit problem, proposing algorithms for resource allocation.
result Proposed algorithms are optimal when all agents have the same utility.
New algorithms improve hiring decisions by optimizing tiered interview processes.
problem Optimizing tiered interview allocation for better hiring decisions.
method Casted tiered hiring as a combinatorial pure exploration (CPE) problem in the stochastic multi-armed bandit setting, presenting new algorithms in PAC and fixed-budget settings.
result Our algorithms select a near-optimal cohort with provable guarantees, making better hiring decisions or using less budget than the status quo.
Algorithm improves movie recommendation efficiency with fairness constraints.
problem Improving movie recommendation efficiency with fairness constraints in combinatorial semi-bandits.
method Adopted Thompson Sampling with beta priors and Bernoulli likelihoods to handle fairness constraints.
result Time-averaged regret upper bounded by $\frac{N}{2η} + O\left(\frac{\sqrt{mNT\ln T}}{T}
ight)$ , with fairness constraints satisfied.
New algorithm detects changes in combinatorial semi-bandit rewards.
problem Detecting changes in piecewise-stationary reward distributions in combinatorial semi-bandits.
method Combination of CUCB algorithm and GLRT change-point detector.
result Regret bound of O(√(NKTlogT)) for piecewise-stationary combinatorial semi-bandits.
New framework tackles submodular welfare with multi-agent combinatorial bandits.
problem Maximizing total welfare among agents with shared constraints and submodular utilities under bandit feedback.
method Proposes an explore-then-commit strategy with randomized assignments for multi-agent combinatorial bandits.
result Achieves i l d e O ( T 2 / 3 ) ilde{\mathcal{O}}(T^{2/3}) i l d e O ( T 2/3 ) regret, first for partition-based submodular welfare problem under bandit feedback. Cost-efficient distributed learning via combinatorial bandits.
problem Trade-off between error and runtime in distributed SGD.
method Combinatorial multi-armed bandit model to learn fastest workers.
result Significantly lower errors with same computational efforts and less communication.
New insights into multi-armed bandits with budget constraints.
problem Multi-armed bandits with supply/budget constraints.
method Characterization of logarithmic regret rates, simple regret, and reduction to other bandit problems.
result Full characterization of logarithmic, instance-dependent regret rates for BwK.
Paper analyzes FTPL's effectiveness in combinatorial semi-bandit problems.
problem Optimizing FTPL policy in combinatorial semi-bandit problems.
method Geometric resampling (GR) and conditional geometric resampling (CGR) for FTPL in semi-bandit setting.
result FTPL achieves optimal regret bounds in both Fréchet and Pareto distributions.
The paper emphasizes the importance of joint predictions over marginal predictions for decision-making.
problem The need for accurate joint predictions in decision-making problems.
method The paper analyzes combinatorial decision problems, sequential predictions, and multi-armed bandits, introducing an approximate Thompson sampling algorithm and new regret bounds.
result Accurate joint predictions are essential for good performance in decision-making problems.
Book introduces multi-armed bandits for decision-making under uncertainty.
problem Decision-making under uncertainty with limited information.
method Self-contained chapters covering various types of bandits.
result Provides a comprehensive introduction to multi-armed bandits.
New algorithm identifies optimal actions in large reward spaces efficiently.
problem Finding the best action from a large set of options with minimal trials.
method GenTS-Explore algorithm for real-valued combinatorial pure exploration.
result Achieves optimal sample complexity for large action sets.
Algorithm identifies best arm in combinatorial bandits with semi-bandit feedback.
problem Identifying the best arm in combinatorial bandits with semi-bandit feedback.
method Interpreted as a sequential zero-sum game, developed a CombGame meta-algorithm with finite time guarantees.
result First computationally efficient algorithm that is asymptotically optimal and has competitive empirical performance.
A new algorithm for contextual combinatorial bandits reduces regret.
problem Balancing exploration and exploitation in sequential decisions with risk sensitivity.
method Contextual combinatorial conservative bandits framework, with algorithms and regret bounds proven.
result Proven regret bound of i l d e O ( d 2 + d T ) ilde O(d^2+d\sqrt{T}) i l d e O ( d 2 + d T ) for known conservative reward, and unknown reward case. MOCA-HESP optimizes high-dimensional combinatorial and mixed spaces using hyper-ellipsoid partitioning.
problem Challenges in optimizing high-dimensional, combinatorial and mixed spaces.
method MOCA-HESP uses hyper-ellipsoid space partitioning with different categorical encoders and multi-armed bandit for adaptive selection.
result MOCA-HESP outperforms existing methods on various synthetic and real-world benchmarks.
We study combinatorial multi-armed bandit with probabilistically triggered arms (CMAB-T) and semi-bandit feedback. We resolve a serious issue in the prior CMAB-T studies where the regret bounds contain a possibly exponentially large factor of 1 / p ∗ 1/p^* 1/ p ∗ , where p ∗ p^* p ∗ is the minimum positive probability that an arm is trigg…
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.
Improved batch-size independent regret bounds for nonlinear reward functions.
problem Nonlinear reward functions in combinatorial multi-armed bandit problems.
method Introducing Gini-weighted smoothness to account for both nonlinearity and concentration properties of arms.
result Achieved dramatic improvements in upper bounds for the probabilistic maximum coverage problem.
Aims to optimize influence spread in social networks using bandit algorithms.
problem Maximizing influence spread in unknown social networks.
method Combines Thompson Sampling and Epsilon Greedy algorithms with automatic ensemble learning.
result Demonstrates effectiveness of automatic ensemble learning for combinatorial bandit problems.
Develops a combinatorial semi-bandit method for electric vehicle charging station selection.
problem Long-distance navigation for BEVs with unknown charging station availability and performance.
method Combinatorial semi-bandit framework, pre-processing road network, Bayesian modeling, Thompson Sampling, BayesUCB, Epsilon-greedy.
result Demonstrates improved navigation performance on long-distance BEV charging station selection.
New framework for resilient bi-criteria optimization under noisy feedback.
problem Bi-criteria combinatorial optimization with noisy function evaluations.
method Introducing ( α , β , δ , e x t t t N ) (α,β,δ, exttt{N}) ( α , β , δ , e x ttt N ) -resilience and developing a black-box framework. result Achieves sublinear regret and constraint violation for bi-criteria bandit problems.
New algorithm for combinatorial bandit problems reduces regret.
problem Optimal selection of sets of arms in bandit problems.
method SGB algorithm with optimized exploration of unselected arms.
result Achieves ( 1 − 1 / e ) (1-1/e) ( 1 − 1/ e ) -regret bound of O ( n 1 3 k 2 3 T 2 3 log ( T ) 2 3 ) \mathcal{O}(n^{\frac{1}{3}} k^{\frac{2}{3}} T^{\frac{2}{3}} \log(T)^{\frac{2}{3}}) O ( n 3 1 k 3 2 T 3 2 log ( T ) 3 2 ) . Paper closes the gap in MP-MAB problems with novel adaptive communication and exploration.
problem Closing the gap between decentralized MP-MAB and natural centralized lower bound.
method BEACON: Batched Exploration with Adaptive COmmunicatioN, incorporating ADC and batched exploration.
result Proves logarithmic regret for a generalized MP-MAB problem.
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.
New method uses offline data to improve online bandit learning, even when distributions differ.
problem Improving online bandit learning with different offline and online distributions.
method MIN-UCB policy that adapts to offline data when informative, achieving tight regret bounds.
result MIN-UCB policy outperforms UCB policy with offline data and provides tight regret bounds.
In this paper, we study the combinatorial multi-armed bandit problem (CMAB) with probabilistically triggered arms (PTAs). Under the assumption that the arm triggering probabilities (ATPs) are positive for all arms, we prove that a class of upper confidence bound (UCB) policies, named Combinatorial UCB with exploration …
Study on resource allocation with unknown thresholds in semi-bandit problems.
problem Learning optimal allocation of resources to arms with unknown threshold values.
method Established equivalence to MP-MAB and Combinatorial Semi-Bandits, derived optimal algorithms.
result Developed algorithms validated by experiments on synthetic data.
This paper tackles combinatorial pure exploration for dueling bandits, aiming to find the best candidate-position match.
problem Finding the best candidate-position match in a dueling bandit setting.
method The paper adapts combinatorial pure exploration for multi-armed bandits to dueling bandits, considering both Borda winner and Condorcet winner cases. It designs PAC and exact algorithms for Borda winner and a fully polynomial time approximation scheme (FPTAS) for Condorcet winner.
result The paper introduces the first algorithm with polynomial running time per round for identifying the Condorcet winner in CPE-DB.
New strategy achieves optimal regret without communication or collisions in multi-player bandit.
problem Cooperative multi-player stochastic multi-armed bandit with shared randomness.
method Combination of combinatorial approach to generalize geometric intuition.
result Achieves near-optimal regret i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) for any number of players and arms without collisions. Optimal resource allocation in censored semi-bandits with unknown thresholds.
problem Sequential resource allocation with unknown thresholds and hidden parameters.
method Established equivalence to MP-MAB and Combinatorial Semi-Bandits, derived optimal algorithms.
result Validated performance of proposed algorithms on synthetic data.
Motivated by problems in search and detection we present a solution to a Combinatorial Multi-Armed Bandit (CMAB) problem with both heavy-tailed reward distributions and a new class of feedback, filtered semibandit feedback. In a CMAB problem an agent pulls a combination of arms from a set { 1 , . . . , k } \{1,...,k\} { 1 , ... , k } in each round, g…
New analysis shows Thompson Sampling can work with greedy approximations in combinatorial bandits.
problem Thompson Sampling's theoretical limits with greedy approximations in combinatorial semi-bandits.
method Study with greedy oracle, providing lower and upper bounds on regret.
result First theoretical results showing TS can work with greedy approximations, breaking misconceptions.
New dynamic allocation methods for multi-armed bandit models.
problem Dynamic allocation problems in multi-armed bandit models.
method New types of dynamic allocation problems and proofs for Gittins index decomposition.
result New proofs for Gittins index decomposition and related results.
PAC-Bayesian analysis improves lifelong learning in multi-armed bandits.
problem Improving lifelong learning in multi-armed bandits.
method PAC-Bayesian analysis for deriving lower bounds and proposing lifelong learning algorithms.
result Proposed algorithms outperform baseline methods in lifelong multi-armed bandit problems.
Paper addresses privacy in combinatorial semi-bandits with improved bounds.
problem Privacy-preserving learning in combinatorial semi-bandits with additional dimension dependence.
method Proposes novel algorithms and proves optimal regret bounds for LDP and DP settings.
result Achieves nearly optimal regret bounds for LDP and DP settings, matching non-private rates.
Paper tackles stochastic k k k -submodular bandits with full feedback, achieving sublinear regret.
problem Online optimization of k k k -submodular functions with full-bandit feedback. method Proposes online algorithms for various k k k -submodular stochastic combinatorial multi-armed bandit problems. result Achieves sublinear α α α -regret bounds for multiple k k k -submodular stochastic combinatorial multi-armed bandit problems.