New algorithm tackles adversarial corruption in Lipschitz bandits with sub-linear regret.
problem Adversarial corruption in Lipschitz bandits.
method Developed robust Lipschitz bandit algorithms for weak and strong adversaries.
result Achieved sub-linear regret under both weak and strong adversaries.
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.
New algorithm tackles delayed feedback in Lipschitz bandits with sublinear regret.
problem Delayed feedback in Lipschitz bandits.
method Design of algorithms for bounded and unbounded stochastic delays.
result Sublinear regret guarantees for both bounded and unbounded delays.
Stochastic Lipschitz bandit algorithms balance exploration and exploitation, and have been used for a variety of important task domains. In this paper, we present a framework for Lipschitz bandit methods that adaptively learns partitions of context- and arm-space. Due to this flexibility, the algorithm is able to effic…
Algorithm tackles adaptive discretization in adversarial Lipschitz bandits for dynamic pricing and auctions.
problem Adaptive discretization in adversarial Lipschitz bandits.
method Adversarial Zooming algorithm for adaptive discretization.
result First algorithm for adversarial Lipschitz bandits with instance-dependent regret bounds.
Transfer learning for bandits with latent Lipschitz continuity.
problem Learning to transfer structural information from prior tasks to new tasks.
method Proposes a framework to estimate Lipschitz constant from prior tasks and apply it to new tasks.
result Regret bound close to oracle algorithm with full knowledge of Lipschitz constant under mild assumptions.
Paper introduces risk assessment for contextual bandits without experiments.
problem Evaluate policies using logged data in context bandits.
method Lipschitz risk functionals and Off-Policy Risk Assessment (OPRA) framework.
result OPRA provides finite sample guarantees for various risk estimates.
New algorithm tracks changes in infinite action space rewards.
problem Non-stationary Lipschitz bandits with infinite actions.
method Adaptive tracking of significant shifts using hierarchical discretization.
result Achieves minimax-optimal dynamic regret bound of O ~ ( i l d e L 1 / 3 T 2 / 3 ) \mathcal{\widetilde{O}}( ilde{L}^{1/3}T^{2/3}) O ( i l d e L 1/3 T 2/3 ) . Improved adaptive rates for Lipschitz bandit problem.
problem Sequentially maximize an unknown Lipschitz function with noisy evaluations.
method Characterizes regret through integrals of suboptimality gaps over level sets, adapting to local growth.
result Improved adaptive rates strictly improving over classical zooming bounds.
The paper tackles multi-player information asymmetry bandits in metric spaces.
problem Information asymmetry in rewards, actions, or both in multiplayer bandit problems.
method Adopted CAB and zooming algorithms for information asymmetry in rewards and actions.
result Regret bounds of the same order in all 3 problem settings.
Improved Thompson Sampling for smoother functions with noise.
problem Applying Thompson Sampling to continuum armed bandits with weak conditions.
method Analysis of eluder dimension for function classes with smooth derivatives.
result New bounds on eluder dimension for classes of functions with Lipschitz derivatives.
A new method optimizes in nonstationary environments with many arms efficiently.
problem Optimizing in nonstationary environments with a large number of arms.
method Gaussian interpolation to learn continuous Lipschitz reward functions in nonstationary environments.
result Efficiently learns continuous Lipschitz reward functions with O ∗ ( T ) \mathcal{O}^*(\sqrt{T}) O ∗ ( T ) cumulative regret. The Piyavskii-Shubert algorithm is analyzed for global optimization of Lipschitz functions.
problem Maximizing a non-concave Lipschitz function over a compact domain.
method Sequential function evaluations using a bandit-optimization approach.
result New bounds on the number of evaluations needed for optimization accuracy.
Paper tackles robust batched bandits for heavy-tailed rewards.
problem Clinical trials and other applications with heavy-tailed rewards.
method Proposes robust batched bandit algorithms for heavy-tailed rewards in finite-arm and Lipschitz-continuous settings.
result Heavier-tailed rewards require fewer batches for near-optimal regret in the instance-independent regime and Lipschitz setting.
BLiE optimizes hyperparameters with theoretical guarantees and superior performance.
problem Hyperparameter optimization in machine learning.
method Lipschitz bandit approach exploiting Lipschitz continuity.
result BLiE finds ε-optimal hyperparameters with theoretical complexity.
Unified framework for risk-aware policy learning in contextual bandits.
problem Optimizing decision rules in high-stakes domains with adverse outcomes.
method Distributional framework for Lipschitz-continuous risk functionals, with novel empirical concentration inequalities.
result Data-dependent suboptimality bounds with an i l d e O ( 1 / n ) ilde{\mathcal{O}}(1/\sqrt{n}) i l d e O ( 1/ n ) rate, matching risk-neutral offline policy optimization. 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 . New algorithms reduce regret for convex bandits with small comparator norms.
problem Optimizing in bandit convex optimization with varying comparator norms.
method Developed algorithms using techniques from full-information setting and new gradient estimators.
result Regret bounds are small when comparator norm is small.
ABoB optimizes online configuration tuning by clustering parameters and accelerating learning.
problem Online optimization in large, dynamic parameter spaces.
method Hierarchical adversarial bandit framework.
result Significant performance gains in adversarial metric scenarios.
Algorithm improves wildlife protection patrols.
problem Balancing exploration and exploitation in patrolling vast protected areas.
method Formulated as a stochastic multi-armed bandit problem, leveraging smoothness and decomposability.
result Algorithm LIZARD improves performance on real-world poaching data.
We investigate contextual online learning with nonparametric (Lipschitz) comparison classes under different assumptions on losses and feedback information. For full information feedback and Lipschitz losses, we design the first explicit algorithm achieving the minimax regret rate (up to log factors). In a partial feedb…
The paper tackles minimax optimality in continuum contextual bandits with Hölder continuity.
problem Minimizing regret in a continuum of contexts with Hölder continuity.
method Proves a static-to-contextual regret conversion theorem and analyzes various dependency cases.
result Achieves minimax optimal contextual regret for convex and strongly convex bandits.
We consider the Lipschitz bandit optimization problem with an emphasis on practical efficiency. Although there is rich literature on regret analysis of this type of problem, e.g., [Kleinberg et al. 2008, Bubeck et al. 2011, Slivkins 2014], their proposed algorithms suffer from serious practical problems including extre…
We investigate online classification with paid stochastic experts. Here, before making their prediction, each expert must be paid. The amount that we pay each expert directly influences the accuracy of their prediction through some unknown Lipschitz "productivity" function. In each round, the learner must decide how mu…
ECP optimizes expensive functions without knowing Lipschitz constant.
problem Optimizing expensive, non-convex functions with unknown Lipschitz constants.
method ECP minimizes evaluations by focusing on potentially optimal regions, eliminating Lipschitz constant estimation.
result Guaranteed no-regret performance and minimax-optimal regret bounds.
The paper analyzes Random Search and introduces BLiN-MOS for bandit learning.
problem Understanding and optimizing hyperparameter tuning in metric measure spaces.
method Introducing scattering dimension to quantify performance, and developing BLiN-MOS for bandit learning.
result Random Search converges to optimal values with specific rates in noise-free and noisy environments.
Efficient algorithms for contextual bandits with smooth regret in continuous action spaces.
problem Efficient learning in large or continuous action spaces.
method Smooth regret notion and efficient algorithms for general function approximation.
result Statistically and computationally efficient algorithms for contextual bandits with smooth regret.
We study contextual bandit learning with an abstract policy class and continuous action space. We obtain two qualitatively different regret bounds: one competes with a smoothed version of the policy class under no continuity assumptions, while the other requires standard Lipschitz assumptions. Both bounds exhibit data-…
Nonparametric Thompson Sampling achieves optimal regret for risk-averse bandits with sub-Gaussian rewards.
problem Optimizing risk-averse bandit problems with sub-Gaussian rewards.
method Anchor-free nonparametric Thompson Sampling algorithm ρ e x t − N P T S S G ρ ext{-}NPTS_{\mathrm{SG}} ρ e x t − N P T S SG . result Achieves regret matching the instance-dependent lower bound to leading order in log n \log n log n . 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…
The paper extends Thompson Sampling to infinite action spaces using information theory.
problem Addressing the limitation of finite action spaces in Thompson Sampling.
method Information-theoretic analysis, extending rate-distortion theory to infinite action spaces.
result Derives a near-optimal regret bound for bandits with infinite and continuous action spaces.
We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per round. We provide a simple algorithm and analysis which is optimal for convex Lipschitz functions. This improves on \cite{dujww13}, which only p…
Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory, textbook-like treatment of the subject. Each chapter tackles a p…
This paper studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
problem Optimizing an unknown function with limited evaluations.
method Studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
result Minimax rates over Besov spaces are identical to those over the smallest Hölder space into which Besov spaces embed.
New lower bound shows bandit convex optimization is harder than previously thought.
problem Establishing a lower bound on the minimax expected regret for bandit convex optimization.
method Constructing a hard class of convex functions and analyzing the posterior spread of Fisher information matrices.
result A Ω ~ ( d 5 / 4 T ) \widetildeΩ(d^{5/4}\sqrt{T}) Ω ( d 5/4 T ) lower bound on the minimax expected regret. A bandit problem with filtered Poisson process data.
problem Maximizing points revealed from a continuum action space.
method Upper confidence bound algorithm with data-adaptive discretisation.
result Regret bound of O(T^(2/3)) under Lipschitz assumption.
This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural properties. Most existing structures (e.g. linear, Lipschitz, unimodal, combinatorial, dueling, ...) are covered by our framework. We derive an asy…
Meta-learning improves performance across similar tasks in adversarial bandit settings.
problem Improving performance across multiple similar tasks in adversarial bandit scenarios.
method Designing meta-algorithms that combine outer learners to tune hyperparameters of inner learners for MAB and BLO.
result Meta-algorithms improve task-averaged regret for MAB and BLO, showing direct relationship with action space-dependent measures.
New algorithm reduces regret for single-index bandits to nearly optimal.
problem Optimizing rewards from unknown projections of high-dimensional contexts.
method Two-phase algorithm: estimate projection direction, reduce to 1D bandit, use UCB.
result Achieved optimal regret of i l d e O ( T 2 / 3 ) ilde{\mathcal{O}}(T^{2/3}) i l d e O ( T 2/3 ) . Improved regret for single-index bandits with optimal algorithm.
problem Optimizing rewards from unknown one-dimensional projections of high-dimensional contexts.
method Two-phase algorithm: first estimate projection direction, then discretize and use UCB.
result Achieved optimal regret of i l d e O ( T 2 / 3 ) ilde{\mathcal{O}}(T^{2/3}) i l d e O ( T 2/3 ) . The paper tackles online learning problems with monotone arm sequences, achieving optimal or near-optimal regret bounds.
problem Online learning problems with ordinal and monotone arm sequences, such as dynamic pricing and clinical trials.
method Proposes algorithms for continuum-armed bandit problems with monotone arm sequences, achieving optimal or near-optimal regret bounds.
result Achieves optimal or near-optimal regret bounds for monotone arm sequences, differing from the continuous-armed bandit literature.
Kernelized bandit algorithm tackles adaptive contextual bandits with single-index models.
problem Adaptive contextual bandits with single-index models and unknown link functions.
method Kernelized ε-greedy algorithm combining Stein-based index estimation and kernel ridge regression for reward functions.
result Unified framework for simultaneous learning and inference in single-index contextual bandits.
Stochastic zeroth-order (SZO), or gradient-free, optimization allows to optimize arbitrary functions by relying only on function evaluations under parameter perturbations, however, the iteration complexity of SZO methods suffers a factor proportional to the dimensionality of the perturbed function. We show that in scen…
New method tracks significant shifts in nonparametric bandits.
problem Tracking significant changes in nonparametric contextual bandits.
method Proposed a notion of 'experienced significant shifts' to adapt to minimax rate without knowledge of change parameters.
result Experienced significant shifts count fewer changes than traditional metrics, leading to an adaptive algorithm.
BaNk-UCB tackles batched nonparametric bandits with k-NN regression and UCB.
problem Sequential decision-making with limited online feedback in domains like medicine and marketing.
method Combines k-NN regression with UCB principle for fully nonparametric, adaptive, and simple implementation.
result Near-optimal regret guarantees under Lipschitz smoothness and margin assumptions, with minimax-optimal rates.
The paper tackles causal bandits with unknown SCMs and soft interventions, providing upper and lower bounds on regret.
problem Optimizing interventions in a causal system with unknown SCMs and soft interventions.
method Assumes unknown SCMs from a general class, allows infinite interventions, and provides upper and lower bounds on regret.
result General upper and lower bounds on cumulative achievable regret for various SCMs.
Certified algorithms optimize functions with varying costs, providing error bounds.
problem Optimizing functions with varying evaluation costs and error bounds.
method Formalized as a min-max game, proposed certified MFDOO algorithm with cost complexity bound.
result Proposed certified MFDOO algorithm has near-optimal cost complexity for Lipschitz functions.
We study online optimization of smoothed piecewise constant functions over the domain [0, 1). This is motivated by the problem of adaptively picking parameters of learning algorithms as in the recently introduced framework by Gupta and Roughgarden (2016). Majority of the machine learning literature has focused on Lipsc…