New algorithms minimize regret in combinatorial online learning with relative feedback.
problem Minimizing regret in online learning with subset-wise relative preference feedback.
method Instance-dependent and order-optimal regret algorithms for two settings: bounded size subsets and fixed size subsets.
result Regret bounds of O ( n m ln T ) O(\frac{n}{m} \ln T) O ( m n ln T ) and O ( n k ln T ) O(\frac{n}{k} \ln T) O ( k n ln T ) for respective settings. A new method for sparse linear bandits reduces exploration-exploitation tradeoff.
problem Sparse linear bandits in high-dimensional settings with finite actions.
method Best subset selection for parameter estimation and doubly growing epochs for regret minimization.
result Achieves nearly dimension-independent regret of i l d e O ( s T ) ilde{\mathcal{O}}(s\sqrt{T}) i l d e O ( s T ) with high probability. A learner selects subsets of choices for a user who then picks from them, aiming to minimize regret.
problem Optimizing subset selection for user choices in a stochastic setting.
method Introduces a new problem and defines regret, then proposes algorithms with matching upper and lower bounds.
result Upper and lower bounds on expected regret match up to a logarithmic term, demonstrating algorithm efficiency.
DART optimizes subset selection in non-linear bandit problems.
problem Optimizing subset selection in non-linear bandit problems with correlated rewards.
method DART algorithm for combinatorial bandits without individual arm feedback or linearity assumption.
result DART achieves a regret bound of i l d e O ( K K N T ) ilde{\mathcal{O}}(K\sqrt{KNT}) i l d e O ( K K N T ) . This paper studies the Best-of-K Bandit game: At each time the player chooses a subset S among all N-choose-K possible options and observes reward max(X(i) : i in S) where X is a random vector drawn from a joint distribution. The objective is to identify the subset that achieves the highest expected reward with high pr…
A new algorithm THV-UCB reduces regret in multi-objective bandit problems.
problem Maintaining a small set of actions that jointly approximate the Pareto frontier in multi-objective slate selection.
method THV-UCB, an optimistic algorithm that selects arms based on optimistic estimates of their marginal hypervolume contributions.
result The algorithm achieves a gap-free regret bound of i l d e O ( d n k T ) ilde{O}(d\sqrt{nkT}) i l d e O ( d nk T ) and a gap-dependent bound of i l d e O ( n k 2.5 / Δ min ) ilde{O}(nk^{2.5}/Δ_{\min}) i l d e O ( n k 2.5 / Δ m i n ) . New algorithms solve linear bandits in high dimensions efficiently.
problem Maximizing bilinear functions over convex sets and ellipsoids.
method Two novel algorithms for solving the problem efficiently.
result First known method to implement optimistic algorithms for linear bandits in high dimensions.
Memory-limited learning tackles adversarial bandits with reduced storage.
problem Adversarial bandit problem with limited memory storage.
method Hierarchical learning policy with sublinear memory requirement.
result Established sublinear regret bounds for weak and shifting regrets.
The paper tackles sequential experimental design for transductive linear bandits.
problem Inferring the maximum of a target vector with limited noisy measurements.
method Introduces a new transductive linear bandit problem and provides instance-dependent lower bounds, an algorithm matching these bounds, and evaluation.
result First non-asymptotic algorithm for linear bandits nearly achieving information theoretic lower bound.
Paper tackles adaptive sampling for identifying largest gaps between distributions.
problem Adaptive sampling from K distributions to identify the largest gap between any two adjacent means.
method Proposes elimination and UCB-style algorithms, showing minimax optimality.
result UCB-style algorithms require 6-8x fewer samples than non-adaptive sampling.
We consider stochastic multi-armed bandit problems with complex actions over a set of basic arms, where the decision maker plays a complex action rather than a basic arm in each round. The reward of the complex action is some function of the basic arms' rewards, and the feedback observed may not necessarily be the rewa…
New algorithms for neural bandits learn from context and arm features.
problem Learning from context and arm features in combinatorial bandit problems.
method Proposed algorithms CN-UCB and CN-TS using deep neural networks.
result Achieved regret guarantees for the first time in combinatorial neural bandits.
This review examines bandit problems in AI using statistical methods.
problem Sequential decision-making under uncertainty in AI environments.
method Foundational models, concentration inequalities, minimax regret bounds, frequentist and Bayesian algorithms, K-armed contextual bandits, SCAB, functional data analysis.
result Exploration-exploitation trade-offs and regret analyses in various bandit problems.
New algorithm tackles multi-player bandit problems with limited access to arms.
problem Limited access to dynamic local subsets of arms in multi-player multi-armed bandit problems.
method Adopted Upper Confidence Bound (UCB) for exploration-exploitation and distributed optimization for collisions.
result Proposes a decentralized algorithm with near-optimal regret guarantee.
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 ) . We introduce the probably approximately correct (PAC) \emph{Battling-Bandit} problem with the Plackett-Luce (PL) subset choice model--an online learning framework where at each trial the learner chooses a subset of k k k arms from a fixed set of n n n arms, and subsequently observes a stochastic feedback indicating prefere…
We use online convex optimization (OCO) for setpoint tracking with uncertain, flexible loads. We consider full feedback from the loads, bandit feedback, and two intermediate types of feedback: partial bandit where a subset of the loads are individually observed and the rest are observed in aggregate, and Bernoulli feed…
Optimal design for multinomial logit models improves assortment selection efficiency.
problem Optimal experimental design for multinomial logit models with feedback.
method Two complementary approaches: MILP reformulation and lifted design.
result Achieves statistical efficiency and scalability for MNL bandits.
New algorithm for recommending best arms with aggregated feedback.
problem Finding the best arm under aggregated feedback when precise rewards are unavailable.
method Gaussian Process Optimistic Optimisation (GPOO) algorithm with adaptive tree construction.
result The proposed algorithm achieves new simple regret bounds with aggregated feedback.
New algorithm for choosing top-K options efficiently with linear space and non-linear feedback.
problem Choosing the best K out of N options at each time instant with efficient trade-off between exploration and exploitation.
method CMAB-SM algorithm, divide-and-conquer strategy, linear space, non-linear feedback.
result Achieves a sub-linear regret bound of $O(K^{ rac{1}{2}}N^{ rac{1}{3}}T^{ rac{2}{3}})$ .
Simplifies large action space bandits by selecting representative actions.
problem Efficiently managing large action spaces with correlated outcomes.
method Random sampling and solving of bandit instances to identify representative actions.
result The algorithm selects a smaller set of representative actions that perform nearly as well as the full action space.
Conversational UCB accelerates bandit learning with user feedback.
problem Slow learning speed in traditional contextual bandit algorithms.
method Generalized contextual bandit to conversational contextual bandit, leveraging both behavioral and conversational feedbacks.
result ConUCB achieves a smaller regret upper bound, indicating faster learning speed.
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. Solves action selection for large spaces in RL, achieving near-optimal performance.
problem Selecting a small, representative subset of actions from a large, shared action space.
method Extends meta-bandit approach to MDPs, using a relaxed sub-Gaussian process model.
result Achieves performance comparable to full action space, with theoretical guarantees.
Unified approach translates classic bandit algorithms to structured settings.
problem Finite-armed structured bandit problem with unknown reward functions.
method Gradual estimation of hidden parameter θ* and use in mean reward functions.
result Structured bandit versions of UCB achieve bounded regret in practical scenarios.
New algorithm reduces regret in high-dimensional bandit problems.
problem High-dimensional bandit problems with sparse correlations.
method Doubly-Robust Lasso Bandit algorithm exploiting sparse regression structure.
result Regret bound scales with log(d) instead of polynomial of d.
Algorithm reduces regret in non-stationary bandits and meta-learning with optimal arms.
problem Sequential decision-making with changing task boundaries and optimal arms.
method Reduction to bandit submodular maximization, meta-learning algorithms.
result Regret bounds for both non-stationary and bandit meta-learning problems.
Study optimal arms in combinatorial bandits with semi-bandit feedback and finite budget.
problem Finding optimal arms in combinatorial bandits with semi-bandit feedback and finite budget constraints.
method Proposes a generic algorithm covering various arm elimination strategies and derives lower bounds.
result Demonstrates sufficient and necessary budget requirements for finding the best arm.
Study non-linear combinatorial bandits with polynomial rewards, finding significant differences from linear cases.
problem Adversarial combinatorial bandits with general non-linear reward functions.
method Extending existing work on adversarial linear combinatorial bandits, analyzing minimax optimal regret for polynomial and non-polynomial reward functions.
result Minimax optimal regret bounds for adversarial combinatorial bandits with general non-linear reward functions.
New algorithm reduces bandit problem's regret bound to logarithmic in dimension.
problem Sparse linear bandit problem with sparse reward structure.
method Proposes an algorithm that uses compatibility condition on optimal arm.
result Achieves regret bound of O(poly log dT) without additional diversity assumptions.
New algorithm optimizes smooth functions with Hölder exponent > 1.
problem Optimizing smooth functions with unknown Hölder exponent > 1.
method Two-layer algorithms using misspecified linear/polynomial bandit algorithms in bins.
result Regret bound of O ~ ( T d + α d + 2 α ) \tilde{O}(T^{\frac{d+\alpha}{d+2\alpha}}) O ~ ( T d + 2 α d + α ) for α > 1 \alpha > 1 α > 1 . Unified framework for expert selection with bandit and lower-bound feedback.
problem Selecting the best expert in scenarios with bandit feedback and lower-bound information.
method Introduces a new feedback model combining bandit and lower-bound information, proving optimal regret bounds for modified Exp3 algorithms.
result Optimal regret bounds for modified Exp3 algorithms, generalizing both bandit and full-information settings.
Algorithm tackles clustered contextual bandits with resource constraints.
problem Maximizing reward while respecting resource limits in unknown cluster contexts.
method Combines econometrics and bandit constraints techniques for sublinear regret.
result Achieves sublinear regret without needing all arm information.
New algorithm learns causal graph to minimize regret in bandits without full structure.
problem Learning optimal decisions in bandits with unknown causal graph and latent confounders.
method Two-stage approach: first learns ancestors and necessary confounders, second applies standard bandit algorithm.
result No full causal structure needed for optimal decisions; only necessary confounders are crucial.
GrAPL identifies arms above a threshold using graph similarity.
problem Efficiently identifying arms with means above a threshold in a graph-structured bandit problem.
method Thresholding Graph Bandits with GrAPL algorithm exploiting graph structure and reward homophily.
result GrAPL effectively identifies arms above a threshold using graph structure and reward homophily.
NK bandits improve performance on nonlinear tasks.
problem Improving performance on nonlinear sequential decision tasks.
method Proposed NK bandits using neural kernels to guide policies.
result NK bandits achieve state-of-the-art performance.
New method for evaluating and learning in complex decision-making scenarios.
problem Evaluating and learning from policies in contextual combinatorial bandits with high bias and variance.
method Factored action space decomposition and importance sampling-based estimator (OPCB).
result OPCB achieves superior performance in OPE and OPL compared to conventional methods.
New algorithm learns from sparse data without knowing sparsity index.
problem Sparse bandit problem where only a subset of features affects reward.
method Sparsity-agnostic Lasso Bandit algorithm that doesn't require prior sparsity index knowledge.
result Established tight regret bounds and outperforms existing methods.
New framework uses user feedback in CB problems for better decision-making.
problem Improving decision-making in contextual bandit problems with user-triggered feedback.
method Developed a new framework to leverage user-triggered feedback in CB problems, robust to feedback bias.
result Improved regret guarantees for CB algorithms using user feedback.
A new algorithm for cryo-EM data collection that balances reward and latency.
problem Optimizing data collection in cryo-EM experiments with action delays.
method Latency-aware contextual bandit framework and COAF algorithm.
result The COAF algorithm efficiently maximizes reward over time in cryo-EM experiments.
Federated learning for combinatorial multi-agent bandits reduces regret and speeds up with fewer communications.
problem Online combinatorial optimization with noisy feedback and cooperation.
method Transforms offline algorithms into online multi-agent algorithms with sublinear regret and communication efficiency.
result Achieves sublinear regret and linear speedup with more agents, communication-efficient.
Efficient strategies for online learning against bandit algorithms solve minimax problems.
problem Solving min-max problems in convex-linear settings with empirical distributions.
method Designing online learning algorithms that play against bandit algorithms, leveraging properties of the set of empirical distributions.
result High-probability convergence guarantees to minimax values for a specific family of sets.
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 ) . The paper tackles identifying multiple best arms in stochastic bandits, improving sample efficiency.
problem Identifying multiple best arms in stochastic multi-armed bandits.
method Developed a fully sequential PAC algorithm, GLUCB, and presented lower and upper bounds.
result Improved sample efficiency for identifying multiple best arms.
Paper generalizes reward distribution in multi-armed bandits with temporally-partitioned rewards.
problem Handling partial rewards distributed over multiple rounds in multi-armed bandits.
method Introduces Beta-spread property to generalize reward distribution, derives lower bound, and provides TP-UCB-FR-G algorithm.
result Improves regret upper bound for some scenarios using Beta-spread property.
FLIPHAT addresses joint differential privacy for high-dimensional sparse linear bandits.
problem Efficient sequential decision-making with high-dimensional sparse features and privacy concerns.
method FLIPHAT combines iterative forgetting and N-IHT for sparse linear regression, achieving optimal regret.
result FLIPHAT achieves optimal regret in terms of privacy parameters, context dimension, and time horizon.
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.
Robust algorithm optimizes corrupted Gaussian process bandits.
problem Sequential optimization of corrupted, expensive reward functions.
method Robust GP Phased Elimination (RGP-PE) algorithm.
result Algorithm balances robustness to corruptions with exploration and exploitation.