A batched Gaussian Process bandit optimization method achieves near-optimal regret bounds.
problem Black-box optimization with limited function evaluations.
method Batched Gaussian Process bandit optimization algorithm.
result Achieves near-optimal cumulative regret bound of O ∗ ( T γ T ) O^\ast(\sqrt{Tγ_T}) O ∗ ( T γ T ) using O ( log log T ) O(\log\log T) O ( log log T ) batches. The paper refines and extends batched kernelized bandits, improving regret bounds and introducing a robust setting.
problem Optimizing black-box functions with noisy batches in Reproducing Kernel Hilbert Space.
method Refined and extended existing regret bounds, including adaptive batch sizes and robust optimization.
result Improved regret bounds for batched kernelized bandits, showing optimal number of batches and adaptive batch sizes.
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.
Study nonparametric contextual bandits with batched updates, achieving optimal regret.
problem Optimal regret in nonparametric contextual bandits with batch constraints.
method Dynamic binning of covariate space, optimal regret achieved.
result Achieves optimal regret (up to logarithmic factors) for nonparametric contextual bandits.
BLAE solves batched linear bandits with optimal regret and practical performance.
problem Batched linear bandit problem with limited adaptivity.
method Integrates arm elimination with regularized G-optimal design, achieving minimax optimal regret.
result Achieves minimax optimal regret in both large- K K K and small- K K K regimes with O ( log log T ) O(\log\log T) O ( log log T ) batches. 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.
The study analyzes batched methods for early stopping in stochastic multi-armed bandits.
problem Early stopping in stochastic multi-armed bandits with fixed confidence.
method Instance-dependent lower bounds and a general batched algorithm with upper bounds.
result Upper and lower bounds on the number of batches and sample complexity.
Study dynamic batch learning in high-dimensional sparse linear bandits.
problem Dynamic batch learning in high-dimensional sparse linear contextual bandits under batch constraints.
method Characterized fundamental learning limits via regret lower bound and provided matching upper bound.
result Prescribed an optimal scheme for dynamic batch learning in high-dimensional sparse linear contextual bandits.
In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has been completely characterized in \cite{perchet2016batched}, the effect of the number of arms on the re…
E 4 ^4 4 algorithm optimizes batched linear bandits with minimal regret and batches.
problem Optimizing batched linear bandits for minimal regret.
method Explore-Estimate-Eliminate-Exploit framework with optimal exploration rate.
result Achieves minimax and asymptotic optimality in regret and batch complexity.
Study batch learning in linear bandits with context, achieving near-optimal performance.
problem Sequential batch learning in linear contextual bandits with finite actions.
method Established regret bounds and provided algorithms for two settings: arbitrary contexts and i.i.d. contexts.
result Regret upper bound nearly matches lower bound, showing polynomial and logarithmic batch requirements.
Batched Neural Bandits reduces policy updates in sequential decision-making.
problem Sequential decision-making with batched policy changes.
method BatchNeuralUCB algorithm combining neural networks and optimism.
result Achieves similar regret as fully sequential version with fewer policy updates.
GN algorithm solves batched bandit for nondegenerate functions near-optimally.
problem Batched bandit learning for nondegenerate functions.
method Introduces Geometric Narrowing (GN) algorithm with a O ~ ( A + d T ) \widetilde{\mathcal{O}} ( A_{+}^d \sqrt{T} ) O ( A + d T ) regret bound and O ( log log T ) \mathcal{O} (\log \log T) O ( log log T ) batches. result GN achieves near optimal regret with minimal number of batches.
New method for identifying best arm in batched multi-armed bandit problems.
problem Identifying the best arm in multi-armed bandit problems where arms are sampled in batches.
method General linear programming framework for best arm identification in batched multi-armed bandit problems.
result Demonstrated good performance in numerical studies compared to UCB-type or Thompson sampling methods.
New algorithms for batched dueling bandits with improved regret bounds.
problem Batched dueling bandits with noisy pairwise comparisons.
method Developed algorithms for two settings: Condorcet winner and strong stochastic transitivity.
result Regret bounds match sequential bounds using only a logarithmic number of batches.
Proposes a new semi-parametric framework for batched bandits with covariates.
problem Sequential decision-making with batched feedback and contextual information.
method Batched single-Index Dynamic binning and Successive arm elimination (BIDS) using single-index regression.
result Achieves minimax-optimal rates for nonparametric batched bandits.
A new batch ensemble method reduces regret in stochastic bandits.
problem Efficiently balancing exploration and exploitation in online RL.
method Proposes a batch ensemble scheme to achieve near-optimal regret.
result Proves near-optimal regret with a single parameter independent of variance.
Batch Thompson Sampling reduces exploration-exploitation trade-off in online decision making.
problem Balancing exploration and exploitation in online decision making.
method Introducing a batch Thompson Sampling framework for stochastic multi-arm bandit and linear contextual bandit problems.
result Achieves asymptotic regret bound with O ( log T ) O(\log T) O ( log T ) batch queries, significantly reducing interactions. 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.
Novel algorithm reduces feature inclusion in online decision-making.
problem Optimizing decision-making for personalized user experiences with fairness.
method Online Batched Sequential Inclusion (OBSI) algorithm for sequential feature inclusion.
result OBSI outperforms other algorithms in terms of regret, relevance of features, and compute.
New study reveals a polynomial penalty for adapting to unknown margin parameters in batched nonparametric bandits.
problem Adapting to an unknown margin parameter in batched nonparametric bandits.
method Introduces the regret inflation criterion and develops RoBIN algorithm to achieve optimal regret inflation.
result The optimal regret inflation grows polynomially with the horizon T, characterized by a convex optimization problem.
New algorithms tackle adversarial combinatorial bandits with switching costs.
problem Adversarial combinatorial bandits with switching costs.
method Design algorithms operating in batches to restrict switches, proving lower bounds and achieving upper bounds on regret.
result Achieved upper bounds on regret for both bandit and semi-bandit feedback settings.
Algorithm achieves comparable performance to fully dynamic data with only a few batches.
problem High-dimensional multi-armed contextual bandits with batched feedback.
method Provable sample-efficient algorithm using batch allocation method.
result Achieves regret bounds comparable to fully sequential setting with only L = O(log T) batches.
Gaussian processes (GP) are one of the most successful frameworks to model uncertainty. However, GP optimization (e.g., GP-UCB) suffers from major scalability issues. Experimental time grows linearly with the number of evaluations, unless candidates are selected in batches (e.g., using GP-BUCB) and evaluated in paralle…
As bandit algorithms are increasingly utilized in scientific studies and industrial applications, there is an associated increasing need for reliable inference methods based on the resulting adaptively-collected data. In this work, we develop methods for inference on data collected in batches using a bandit algorithm. …
Improved batched SH algorithm maintains original performance.
problem Maintaining performance in batched multi-armed bandits.
method Simple batch version of Sequential Halving algorithm.
result Batching does not degrade SH algorithm's performance.
We study the multi-armed bandit problem with subgaussian rewards. The explore-then-commit (ETC) strategy, which consists of an exploration phase followed by an exploitation phase, is one of the most widely used algorithms in a variety of online decision applications. Nevertheless, it has been shown in Garivier et al. (…
ARC algorithm optimizes dynamic pricing with correlated observations.
problem Optimizing dynamic pricing with correlated and generally distributed observations.
method Extends ARC algorithm to batched bandits with generalised linear model.
result ARC algorithm outperforms alternative approaches in dynamic pricing.
Paper addresses OPE for dependent bandit samples using MDS and batch updates.
problem Evaluating policies from non-i.i.d. historical data in contextual bandits.
method Constructs an MDS-based estimator for dependent samples, solves batch update and deficient support issues.
result Derives an asymptotically normal estimator for evaluation policy value.
Study on adaptivity constraints in linear contextual bandits with optimal design.
problem Impact of adaptivity constraints on linear contextual bandits.
method Two models of limited adaptivity: batch learning and rare policy switches. Proposed distributional optimal design.
result Achieves minimax-optimal regret with optimal number of policy switches and batches.
New algorithm tackles batched stochastic linear bandits with 1-bit communication constraints.
problem Stochastic linear bandits with 1-bit communication constraints.
method Phased-elimination algorithms based on G-optimal designs and 1-bit mean estimation.
result Achieves near-optimal regret bounds for broad scaling regimes.
Paper addresses privacy and robustness in stochastic linear bandits.
problem Stochastic linear bandits with differential privacy and adversarial robustness.
method Logarithmic batch queries, arm elimination algorithm, two privacy models.
result First algorithms providing differential privacy and adversarial robustness.
Determining the appropriate batch size for mini-batch gradient descent is always time consuming as it often relies on grid search. This paper considers a resizable mini-batch gradient descent (RMGD) algorithm based on a multi-armed bandit for achieving best performance in grid search by selecting an appropriate batch s…
Efficient optimisation of black-box problems that comprise both continuous and categorical inputs is important, yet poses significant challenges. We propose a new approach, Continuous and Categorical Bayesian Optimisation (CoCaBO), which combines the strengths of multi-armed bandits and Bayesian optimisation to select …
New algorithm achieves near-optimal performance in dueling bandit problem.
problem Optimizing decision-making in dueling bandit problems with limited adaptive rounds.
method Developed a batched algorithm that matches the asymptotic regret bounds of sequential algorithms under the Condorcet condition.
result Asymptotic regret of O ( K 2 log 2 ( K ) ) + O ( K log ( T ) ) O(K^2\log^2(K)) + O(K\log(T)) O ( K 2 log 2 ( K )) + O ( K log ( T )) in O ( log ( T ) ) O(\log(T)) O ( log ( T )) rounds. A new framework scales active search for large datasets.
problem Scaling active search for large, high-dimensional data sets.
method Hierarchical Batch Bandit Search (HBBS) framework.
result HBBS improves performance and scalability for batch search.
New constraints on space and adaptivity in bandits force more batches and memory use.
problem Simultaneous space and adaptivity constraints in stochastic bandits.
method Proved lower bounds and constructed an algorithm with near-minimax regret.
result Near-minimax regret requires more batches and memory than previously thought.
Study on adaptivity to kernel regularity in bandit problems.
problem Adaptation to unknown kernel regularity in continuum-armed bandit problems.
method Derive adaptivity lower bound and verify with minimax non-adaptive kernelised bandit algorithms.
result Impossibility of achieving optimal cumulative regret in different RKHSs with varying regularities.
Develops a flexible batched experimentation framework for limited adaptivity.
problem Challenges of continual reallocation in bandit algorithms with delayed feedback.
method Computational framework leveraging Gaussian sequential experiment and dynamic programming.
result Improves statistical power over standard methods, even compared to Bayesian bandit algorithms.
Efficient algorithms for contextual slate bandits with limited adaptivity.
problem Contextual slate bandit problem with limited adaptivity.
method Proposed B-SlateGLinCB and RS-SlateGLinCB algorithms for batched and rarely-switching settings.
result Achieved regret bounds of O(Nd^(3/2)√T) and O(Nd√T) under diversity assumption.
LIBO optimizes repeated bandit tasks without prior knowledge or regret.
problem Optimizing repeated bandit tasks without prior knowledge or regret.
method LIBO sequentially meta-learns a kernel to adapt to the environment and solve tasks with the latest estimate.
result LIBO achieves sublinear lifelong regret, converging to oracle performance as more tasks are solved.
This paper tackles open problem of tight bounds for KBs with Bernoulli rewards.
problem Open problem of tight bounds for Kernelized Bandits with Bernoulli rewards.
method Focus on Bernoulli model, not subgaussian noise, and optimize function in RKHS.
result Open problem remains unsolved in this context.
Optimal algorithm for minimizing regret in heavy-tailed bandits.
problem Minimizing regret in stochastic multi-armed bandits with heavy-tailed distributions.
method Proposes an optimal algorithm under the assumption of uniformly bounded moments of order (1+ε).
result Matches the lower bound exactly in the first-order term and provides a finite-time bound on its regret.
Algorithm adapts to non-stationary rewards without prior knowledge.
problem Optimizing decisions in non-stationary environments without prior knowledge of changes.
method Optimization-based algorithm that restarts when non-stationarity is detected.
result Achieves tighter dynamic regret bound and is nearly minimax optimal.
Paper improves CMAB regret bounds by reducing batch-size dependency.
problem Reducing batch-size dependency in combinatorial semi-bandits.
method Developed BCUCB-T and SESCB algorithms with new TPVM conditions.
result Significantly improved regret bounds for various applications.
A new algorithm for differential privacy in kernelized contextual bandits reduces error rate.
problem Joint differential privacy in kernelized contextual bandits.
method Proposes a novel algorithm with a specific error rate and privacy parameter dependence.
result Achieves an error rate of $\mathcal{O}\left(\sqrt{\frac{γ_T}{T}} + \frac{γ_T}{T \varepsilon}
ight)$ after T T T queries. Unified framework for multi-user bandits using Laplacian kernels.
problem Multi-user contextual bandits with graph-related users and non-linear rewards.
method Joint penalty combining graph smoothness and individual roughness in a unified RKHS.
result Unified multi-user RKHS and effective dimension for regret bounds.
Kernel ε ε ε -Greedy optimizes multi-armed bandits with covariates for sub-linear regret.
problem Optimizing multi-armed bandits with covariates in a reproducing kernel Hilbert space.
method Online weighted kernel ridge regression estimator for mean reward function estimation.
result Achieves sub-linear regret rate and optimal T \sqrt{T} T regret rate under margin condition.