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. 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.
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.
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.
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.
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.
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.
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.
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. 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.
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.
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.
Two algorithms for linear contextual bandits with rare updates achieve optimal regret and efficiency.
problem Linear contextual bandits with infrequent parameter updates.
method Two practical algorithms with O ( log log T ) O(\log\log T) O ( log log T ) updates, BLCE-G and BLCE. result Minimax-optimal regret with low computational complexity.
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.
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.
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.
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…
The paper studies early stopping methods in linear contextual bandits.
problem Minimizing in-experiment regret and conducting robust post-experiment inferences in contextual bandits.
method The study proposes early stopping rules based on the Opportunity Cost and Threshold Method, using variances of estimators to quantify upper regret bounds.
result The proposed method provides a systematic approach to minimize in-experiment regret and conduct robust post-experiment inferences.
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.
Study shows efficient neural network approach for stochastic bandits.
problem Optimizing decisions in uncertain environments with neural network models.
method OFU-ReLU algorithm that balances exploration and exploitation, using a transformed feature space.
result Achieves i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret guarantee for stochastic bandits with ReLU neural networks. Study model selection in batch policy optimization with three error sources.
problem Learn a policy competitive with the best model class in batch policy optimization.
method Formalized in contextual bandit setting with linear model classes, addressing approximation error, statistical complexity, and dataset shift.
result No algorithm can optimally trade-off all three error sources, but relaxing any one enables near-oracle inequalities for the others.
Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of O ( d T log T ) O(d\sqrt{T\log T}) O ( d T log T ) . 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 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 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. 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.
DETC algorithm achieves asymptotic optimality in multi-armed bandit problems.
problem Multi-armed bandit problem with subgaussian rewards.
method DETC algorithm with two exploration and exploitation phases.
result DETC achieves asymptotically optimal regret bound.
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 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.
Parallelized bandit algorithms speed up decision-making.
problem Sequential exploration limits decision-making speed.
method Developed parallel contextual bandit algorithms.
result Regret nearly identical to sequential algorithms.
New algorithm speeds up Gaussian process optimization.
problem Scalability issues in Gaussian process optimization.
method BBKB (Batch Budgeted Kernel Bandits) algorithm that selects candidates in batches and adaptively delays updates.
result Provable near-linear time complexity and significant speedup over existing methods.
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.
Designs a single policy for collecting data to train near-optimal policies.
problem Engineering overhead in deploying minimax procedures for stochastic linear contextual bandits.
method Designs a single stochastic policy to collect data from which a near-optimal policy can be extracted.
result The designed policy can collect data from which a near-optimal policy can be extracted.
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.
A new bandit strategy improves learning speed at the cost of accuracy.
problem Learning speed vs. accuracy trade-off in multi-armed bandits.
method Weighted Thompson Sampling (WTS) for multi-armed bandits with Gaussian feedback.
result Upper bound matches log(T) lower bound, solving fundamental problem.
A distributed algorithm reduces communication cost in linear bandits to near-optimal levels.
problem Cooperative linear bandit optimization with stochastic contexts.
method DisBE-LUCB algorithm, DecBE-LUCB algorithm, sharing information through a central server or immediate neighbors.
result Communication cost of DisBE-LUCB matches information-theoretic lower bound up to logarithmic factors.
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.
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…
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 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. Extends Thompson sampling for RL with fewer episodes.
problem Limited episodes in RL settings.
method Batch Bayesian optimization over episodes to learn action bias terms.
result Significantly outperforms standard Thompson sampling.
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.