Optimal algorithm for identifying best arm in stochastic linear bandits with fixed confidence.
problem Identifying the best arm in stochastic linear bandits with fixed confidence.
method Extending an algorithm designed for Best Arm Identification to the ε ε ε -Thresholding Bandit Problem (TBP). result Asymptotically optimal algorithm for TBP.
Optimizes algorithms for non-concave bandit problems.
problem Optimizing algorithms for non-concave bandit problems.
method Unified zeroth-order optimization paradigm.
result Minimax-optimal algorithms in the dimension for low-rank generalized linear bandit problems.
New algorithm tackles multimodal bandits with optimal regret bounds.
problem Stochastic multi-armed bandit problem with multimodal rewards.
method Proposed computationally tractable algorithm for multimodal rewards.
result Asymptotically optimal algorithms implemented for the bandit problem.
Polynomial-time method solves complex combinatorial semi-bandits.
problem Optimal strategies for combinatorial semi-bandits with uncorrelated Gaussian rewards.
method Proposes a polynomial-time method to solve the Graves-Lai optimization problem for various combinatorial structures.
result First known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.
Optimizes pure exploration in linear bandits with a new algorithm.
problem Best-arm identification in linear stochastic bandits.
method Developed the first asymptotically optimal algorithm for fixed-confidence pure exploration in linear bandits.
result Avoids the pitfall of a simple but difficult instance and bypasses the need to solve an optimal design problem.
Develops first optimal algorithm for logistic bandits.
problem Pure exploration in logistic bandits.
method Logistic track-and-stop (Log-TS) algorithm.
result Asymptotically matches lower bound for expected sample complexity.
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.
New algorithm for nonstationary multi-armed bandits with optimal performance.
problem Nonstationary multi-armed bandits with changing model parameters over time.
method Adaptive Resetting Bandit (ADR-bandit) algorithm using adaptive windowing techniques.
result ADR-bandit achieves nearly optimal performance in both abrupt and gradual changes.
Bayesian optimization improved for biased data.
problem Adversarial bias in observations, especially hidden confounders.
method Reduction to dueling bandits, information-directed sampling (IDS).
result First efficient kernelized algorithm with regret guarantees.
New algorithm reduces individual regret and communication costs in cooperative bandits.
problem Optimal individual and group regret in cooperative multi-agent bandits.
method Integrates a new communication policy into a learning algorithm.
result Achieves optimal individual regret and constant communication costs.
Study on Pareto optimality in multi-objective bandit problems.
problem Pareto optimality in multi-objective multi-armed bandit problems.
method Formulated adversarial multi-objective multi-armed bandit, defined Pareto regrets, presented algorithms, established upper and lower bounds.
result New algorithms are optimal in adversarial settings and nearly optimal in stochastic settings.
Paper tackles LDP bandits learning with improved results and sub-linear regret.
problem Contextual bandits learning with LDP privacy constraints.
method Simple black-box reduction frameworks for context-free bandits, extended to GLB.
result First result for BCO with multi-point feedback under LDP, sub-linear regret for GLB.
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 introduces risk-sensitive bandits with optimal arm mixtures.
problem Designing algorithms for risk-sensitive multi-armed bandits.
method Formalizes risk-sensitive bandits framework, identifies optimal arm mixtures, designs regret-efficient algorithms.
result Regret-efficient algorithms track optimal arm mixtures or solitary arms.
Improves bandit convex optimization with gradient variations.
problem Bandit Convex Optimization with Gradient Variations.
method Refined analysis of non-consecutive gradient variation.
result Improved dimension dependence for convex and strongly convex functions.
This article introduces the concepts around Online Bandit Linear Optimization and explores an efficient setup called SCRiBLe (Self-Concordant Regularization in Bandit Learning) created by Abernethy et. al.\cite{abernethy}. The SCRiBLe setup and algorithm yield a O ( T ) O(\sqrt{T}) O ( T ) regret bound and polynomial run time comple…
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.
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.
Faster algorithm reduces contextual bandit regret with fewer offline regression calls.
problem Optimizing reward in contextual bandits with unknown functions.
method Designing a simple algorithm with O ( log T ) {O}(\log T) O ( log T ) offline regression calls. result Achieves statistically optimal regret with minimal offline calls.
New approach reduces unconstrained linear bandits to simpler optimization problems.
problem Unconstrained linear bandits problem.
method Perturbation-based approach combined with comparator-adaptive OLO algorithms.
result First high-probability guarantees for both static and dynamic regret in unconstrained linear bandits.
Paper solves Bayesian bandit problem with continuous-time limit and approximate policy.
problem Finding optimal policy in Bayesian bandit problems with large horizons.
method Reformulates Bayesian bandit problem as continuous Hamilton-Jacobi-Bellman (HJB) equation and proposes approximate Bayes-optimal policy.
result Approximate Bayes-optimal policy for large horizons with constant computational cost.
New algorithm learns optimal exploration parameters for contextual bandits.
problem Learning optimal exploration in contextual bandits.
method Proposes two algorithms that learn optimal exploration parameters online based on context and reward.
result Demonstrates improved performance in learning optimal exploration compared to traditional methods.
Presents SPEED, an algorithm for optimal policy evaluation in linear bandits with heteroscedastic noise.
problem Optimal data collection for policy evaluation in linear bandits with heteroscedastic reward noise.
method Formulated an optimal design for weighted least squares estimates, derived the optimal sample allocation, introduced SPEED algorithm, and derived regret bounds.
result SPEED leads to policy evaluation with MSE comparable to oracle strategy and significantly lower than random policy execution.
We consider the stochastic linear (multi-armed) contextual bandit problem with the possibility of hidden simple multi-armed bandit structure in which the rewards are independent of the contextual information. Algorithms that are designed solely for one of the regimes are known to be sub-optimal for the alternate regime…
Unified proof for various bandit algorithms with logarithmic regret.
problem Achieving logarithmic regret in stochastic bandit algorithms.
method Minimal high-probability concentration condition and two deterministic lemmas.
result Unified proofs for classical and contemporary bandit algorithms.
We provide the first algorithm for online bandit linear optimization whose regret after T rounds is of order sqrt{Td ln N} on any finite class X of N actions in d dimensions, and of order d*sqrt{T} (up to log factors) when X is infinite. These bounds are not improvable in general. The basic idea utilizes tools from con…
New algorithm improves game learning with randomised optimism.
problem Learning in matrix games with unknown payoffs and bandit feedback.
method Integrates evolutionary algorithms into bandit framework for randomised optimism.
result Achieves sublinear regret, outperforming classical methods.
New bandit problem for finding best group of arms with worst mean reward.
problem Finding the best group of arms with the worst mean reward in overlapping groups.
method Two algorithms based on successive elimination and robust optimization.
result Upper bounds on the number of samples to find max-min optimal or near-optimal group.
Paper proposes no-regret algorithms for private GP bandit optimization.
problem Private Gaussian process bandit optimization.
method Combines uniform kernel approximator with random perturbations for differentially private GP bandit algorithms.
result Provable no-regret algorithms for stationary kernel functions in two DP settings.
New algorithm optimizes dueling bandits for both stochastic and adversarial preferences.
problem Optimizing decision-making in environments where only relative preferences are observed.
method Proposed a reduction from dueling bandits to multi-armed bandits, achieving optimal regret bounds.
result First best-of-both-world result for dueling bandits, optimal regret bound for Condorcet-winner benchmark.
New findings show many popular bandit algorithms are unstable, contradicting minimax optimality.
problem Challenges in statistical inference from bandit algorithms due to adaptive, non-i.i.d. nature.
method Analysis of stability properties of optimism-based bandit algorithms.
result Widely used minimax-optimal UCB-style algorithms are unstable.
The dueling bandit is a learning framework wherein the feedback information in the learning process is restricted to a noisy comparison between a pair of actions. In this research, we address a dueling bandit problem based on a cost function over a continuous space. We propose a stochastic mirror descent algorithm and …
Paper analyzes nonconvex bandit problems with improved adaptive methods.
problem Continuous armed bandit problems for nonconvex cost functions.
method Simple and adaptive bin splitting methods.
result Adaptive method achieves locally minimax optimal expected cumulative regret.
Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notably the optimism principle and Thompson sampling. While prior work has mostly been in the worst-case …
Bayesian bandits misspecification affects UX optimization, revealing new models.
problem Misspecification of value models in Bayesian bandits impacts UX optimization.
method Formulated UXO as a restless, sleeping bandit with unobserved confounders and optional stopping. Provided model extensions to address misspecifications.
result Common misspecifications lead to sub-optimal rewards, demonstrating overdispersion's effects on bandit performance.
New algorithm identifies best arm in semiparametric bandits with near optimal efficiency.
problem Fixed-confidence Best Arm Identification in semiparametric bandits with unknown baseline shift.
method Phase-elimination algorithm based on orthogonalized regression design.
result Nearly optimal high-probability sample-complexity upper bound established.
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.
An optimal algorithm for multi-armed bandits with constraints.
problem Optimizing decisions in constrained multi-armed bandit problems.
method An index-based deterministic algorithm using Locatelli's anytime thresholding under known optimal value assumption.
result The algorithm achieves asymptotic optimality with probability approaching 1.
Paper confirms Feldman's conjecture on two-armed bandit problem.
problem Two-armed bandit problem with general distributions and utility functions.
method Obtained necessary and sufficient condition for myopic strategy optimality.
result Myopic strategy stochastically maximizes wins in Bernoulli bandit problems.
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.
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.
We study a nonparametric contextual bandit problem where the expected reward functions belong to a Hölder class with smoothness parameter β β β . We show how this interpolates between two extremes that were previously studied in isolation: non-differentiable bandits ( β ≤ 1 β\leq1 β ≤ 1 ), where rate-optimal regret is achieved by run…
This paper improves offline contextual bandits using distributional robustness.
problem Improving offline contextual bandits with robustness.
method Extends Distributionally Robust Optimization (DRO) for offline contextual bandits, introducing a convex reformulation of Counterfactual Risk Minimization.
result Automatic calibration of asymptotic confidence intervals for policy optimization.
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.
PyXAB is a Python library for X-armed bandits and online optimization.
problem Efficiently solving X-armed bandit problems and online blackbox optimization.
method Implementation of 10+ X-armed bandit algorithms and synthetic objectives.
result Evaluation of different algorithms' performance on various synthetic objectives.
Optimal algorithm found for collaborative learning in bandits with optimal regret bounds.
problem Minimizing regret in collaborative multi-agent bandit problems.
method Proposed an algorithm with optimal regret bounds for collaborative multi-agent multi-armed bandit model.
result First algorithm with order optimal regret bounds for collaborative bandit model.
We consider the problem of bandit optimization, inspired by stochastic optimization and online learning problems with bandit feedback. In this problem, the objective is to minimize a global loss function of all the actions, not necessarily a cumulative loss. This framework allows us to study a very general class of pro…
Randomized exploration in linear bandits achieves optimal regret bounds.
problem Optimizing exploration in high-dimensional linear bandit problems.
method Analysis of Thompson sampling without forced optimism.
result Randomized exploration algorithms achieve an O ( d n log ( n ) ) O(d\sqrt{n} \log(n)) O ( d n log ( n )) regret bound in smooth, strongly convex action spaces.