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.
Optimal strategy proposed for maximizing cumulative reward in continuum-armed bandits.
problem Maximizing cumulative reward in a scenario with limited resources and unknown stochastic rewards.
method Proposed an optimal strategy for a nonparametric setting with side information on actions.
result Optimal regret scales as \(O(T^{1/3})\) up to poly-logarithmic factors when \(T\) is proportional to \(N\).
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.
Thompson Sampling is a well established approach to bandit and reinforcement learning problems. However its use in continuum armed bandit problems has received relatively little attention. We provide the first bounds on the regret of Thompson Sampling for continuum armed bandits under weak conditions on the function cl…
Paper tackles constrained bandit problems with a new learning framework.
problem Optimizing a black-box reward function subject to a black-box constraint function over a continuous space.
method Rectified Pessimistic-Optimistic Learning (RPOL) framework, incorporating optimistic and pessimistic GP bandit learning.
result RPOL achieves sublinear regret and minimal cumulative constraint violation.
We describe a novel algorithm for noisy global optimisation and continuum-armed bandits, with good convergence properties over any continuous reward function having finitely many polynomial maxima. Over such functions, our algorithm achieves square-root regret in bandits, and inverse-square-root error in optimisation, …
We consider a stochastic continuum armed bandit problem where the arms are indexed by the ℓ 2 \ell_2 ℓ 2 ball B d ( 1 + ν ) B_{d}(1+ν) B d ( 1 + ν ) of radius 1 + ν 1+ν 1 + ν in R d \mathbb{R}^d R d . The reward functions r : B d ( 1 + ν ) → R r :B_{d}(1+ν) \rightarrow \mathbb{R} r : B d ( 1 + ν ) → R are considered to intrinsically depend on k ≪ d k \ll d k ≪ d unknown linear parameters so that $r(\mathbf{x}) = g(\ma…
In contextual continuum-armed bandits, the contexts x x x and the arms y y y are both continuous and drawn from high-dimensional spaces. The payoff function to learn f ( x , y ) f(x,y) f ( x , y ) does not have a particular parametric form. The literature has shown that for Lipschitz-continuous functions, the optimal regret is $\tilde{O}(T^{\fr…
In the context of stochastic continuum-armed bandits, we present an algorithm that adapts to the unknown smoothness of the objective function. We exhibit and compute a polynomial cost of adaptation to the H{ö}lder regularity for regret minimization. To do this, we first reconsider the recent lower bound of Locatelli an…
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.
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.
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.
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.
A new framework tunes hyperparameters in real-time for contextual bandits.
problem Optimizing hyperparameters for contextual bandits in real-time.
method CDT (Continuous Dynamic Tuning) framework using Zooming TS algorithm.
result Achieves sublinear regret and performs better than existing methods.
A new Bayesian framework simplifies stochastic optimization by focusing on key parameters.
problem Bayesian methods struggle with complex structural constraints.
method Minimalist Bayesian framework that eliminates nuisance parameters via profile likelihood.
result Near-optimal regret guarantees for multi-armed bandits and convex optimization.
We consider the problem of adaptively placing sensors along an interval to detect stochastically-generated events. We present a new formulation of the problem as a continuum-armed bandit problem with feedback in the form of partial observations of realisations of an inhomogeneous Poisson process. We design a solution m…
The paper improves bounds on regret in Gaussian process bandits.
problem Sequential optimization of expensive, possibly non-convex functions with noisy feedback.
method Analyzes maximal information gain and decay rates of GP kernel eigenvalues to improve regret bounds.
result General bounds on maximal information gain and improved regret bounds for various settings, including Matérn kernels.
This paper tackles bandit optimization with a new pairwise comparison oracle for unknown strongly concave functions.
problem Maximizing an unknown strongly concave function over T periods with a biased pairwise comparison oracle.
method Introduced a discretization technique and local polynomial approximation to relate the problem to linear bandits. Developed a tournament successive elimination technique to localize the discretized cell and run LinUCB algorithm on cells.
result Established optimal regret bounds and improved state-of-the-art results in operations management problems.
We consider the problem of global optimization of a function over a continuous domain. In our setup, we can evaluate the function sequentially at points of our choice and the evaluations are noisy. We frame it as a continuum-armed bandit problem with a Gaussian Process prior on the function. In this regime, most algori…
Efficient global optimization is the problem of minimizing an unknown function f, using as few evaluations f(x) as possible. It can be considered as a continuum-armed bandit problem, with noiseless data and simple regret. Expected improvement is perhaps the most popular method for solving this problem; the algorithm pe…
Unified GP model optimizes hyperparameters with conditional dependence.
problem Efficient tuning of hyperparameters in neural networks.
method Unified Bayesian optimization framework based on a new Gaussian process (GP) model.
result Higher prediction accuracy and better optimization efficiency observed.
New algorithms tackle RKHS bandits with reduced complexity and improved performance.
problem Adversarial and stochastic RKHS bandit problems with high computational complexity.
method Combining approximation theory with misspecified linear bandit methods.
result First general algorithm for adversarial RKHS bandit problem.
Unified formulation bridges adversarial and nonstationary bandits.
problem Handling time-varying reward distributions in multi-armed bandit problems.
method Unified oracle that switches between adversarial and nonstationary bandit oracles based on window size.
result Optimal regret achieved with matching lower bound.
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.
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 ) . Graph-Triggered Bandits unify rested and restless bandits with graph-defined arm interactions.
problem Modeling sequential decision-making problems with evolving arm rewards.
method Graph-Triggered Bandits (GTBs) framework that generalizes rested and restless bandits using a graph.
result Rested and restless bandits are special cases of GTBs for suitable graphs.
New definition resolves ambiguity in non-stationary bandit classification.
problem Ambiguity in classifying non-stationary bandits using existing definitions.
method Introducing a formal definition that resolves ambiguity and provides a unified approach.
result Unified approach applicable to both Bayesian and frequentist formulations, resolves classification issues.
Unified approach for non-stationary and clustered bandits.
problem Solving non-stationary and clustered bandits with overlapping solutions.
method Test of homogeneity for seamless integration of non-stationary and clustered bandits.
result Unified solution framework for change detection and cluster identification.
A framework for auto-tuning hyper-parameters in contextual bandit algorithms.
problem Auto-tuning hyper-parameters in real-time for contextual bandit algorithms.
method Proposes a Syndicated Bandits framework to learn multiple hyper-parameters dynamically.
result Achieves optimal regret bounds under certain scenarios and handles multiple contextual bandit algorithms.
Stochastic multi-armed bandits form a class of online learning problems that have important applications in online recommendation systems, adaptive medical treatment, and many others. Even though potential attacks against these learning algorithms may hijack their behavior, causing catastrophic loss in real-world appli…
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.
Investigates sequential problems on graph structures and large action spaces.
problem Sequential decision-making on graph structures and large action spaces.
method Spectral bandits, side observations, influence maximization, kernel bandits, polymatroid bandits, function optimization, infinitely many-arms bandits.
result Contributions to graph and structured bandits.
Study on indexability of restless multi-armed bandits and rollout policy performance.
problem Maximizing discounted rewards in finite state restless multi-armed bandit problems.
method Decouple the problem into single-armed restless bandits, analyze using value iteration, and compare with Whittle index policy.
result Demonstrates conditions for indexability and compares performance of index policy and rollout policy.
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.
A meta-UCB method combines stochastic bandit algorithms.
problem Combining multiple stochastic bandit algorithms efficiently.
method Meta-UCB procedure solving an N-armed bandit problem.
result Final regret depends only on the best base algorithm's regret.
New method for contextual bandits with corrupted context.
problem Contextual bandits with corrupted context in online settings.
method Combining contextual bandit and multi-armed bandit approaches.
result Improved learning from all iterations, including corrupted ones.
A new framework for structured bandits using influence diagrams and variational Thompson sampling.
problem Complex statistical dependencies in structured bandit problems.
method Influence diagram framework, variational Thompson sampling, tracking structured posterior distribution.
result Empirically evaluated algorithms perform as well as or better than existing baselines.
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.
First robust bandit algorithm for contextual bandits with sub-linear regret.
problem Vulnerability of linear contextual bandit algorithms to adversarial attacks.
method Proposes a robust bandit algorithm for stochastic linear contextual bandits under fully adaptive and omniscient attacks.
result Sub-linear regret under various attacks without requiring attack information.
Unified framework for high-dimensional bandit problems with low-dimensional structures.
problem Stochastic high-dimensional bandit problems with low-dimensional structures.
method Proposed a simple unified algorithm and a general analysis framework for the regret upper bound.
result Unified algorithm achieves comparable regret bounds in various high-dimensional bandit problems.
Survey and compare PAC-Bayes bounds for bandit problems.
problem Designing and evaluating bandit algorithms with strong performance guarantees.
method PAC-Bayes bounds applied to bandit problems.
result PAC-Bayes bounds useful for offline bandit algorithms, but loose for online algorithms.
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.
Paper tackles domain adaptation for contextual bandits with sub-linear regret.
problem Adapting contextual bandit algorithms across domains with distribution shift.
method Learn a bandit model for the target domain using feedback from the source domain.
result Sub-linear regret bound maintained across domains.
New model tackles causal bandits with dependent variables.
problem Understanding reward-maximizing interventions in causal networks with dependent variables.
method Introduces hierarchical causal bandit model with a contextual variable capturing interactions among variables.
result Derives nearly matching regret bounds for binary context in causal bandits with dependent arms.
We consider the problem of best arm identification in a variant of multi-armed bandits called linked bandits. In a single interaction with linked bandits, multiple arms are played sequentially until one of them receives a positive reward. Since each interaction provides feedback about more than one arm, the sample comp…
New dynamic allocation methods for multi-armed bandit models.
problem Dynamic allocation problems in multi-armed bandit models.
method New types of dynamic allocation problems and proofs for Gittins index decomposition.
result New proofs for Gittins index decomposition and related results.
The paper tackles lifelong learning in multi-armed bandits, aiming to minimize average regret over multiple tasks.
problem Minimizing average regret in multi-armed bandits over multiple tasks.
method Confidence interval tuning of UCB algorithms and greedy algorithms applied to a bandit over bandit approach.
result Empirical improvement over previous work in the mortal bandit problem.
New algorithm for partially observable contexts in finance.
problem Decision making based on partially observable, correlated market information.
method EMKF-Bandit algorithm integrating system identification, filtering, and bandit algorithms.
result Sub-linear regret under conditions on filtering.