New algorithm optimizes best arm identification with minimal regret.
problem Best arm identification in multi-armed bandit problems.
method Characterized Bayesian simple regret with continuity conditions of prior, proposed a simple algorithm.
result Proposed algorithm achieves rate-optimal Bayesian simple regret.
New algorithm minimizes Bayesian regret in offline linear bandits.
problem Minimizing Bayesian regret in offline linear bandits.
method Proposes a new algorithm that directly minimizes upper bounds on Bayesian regret using conic optimization.
result Upper bounds are tight and guarantee superior performance compared to LCB.
IDS improves sparse linear bandits by balancing information and regret.
problem Sparse linear bandits in high-dimensional decision-making.
method Information-directed sampling (IDS) with Bayesian regret bounds and empirical Bayesian sparse posterior sampling.
result IDS nearly matches existing lower bounds and significantly reduces regret.
Paper improves regret bounds for Gaussian process upper confidence bound in Bayesian optimization.
problem Minimizing regret in Gaussian process bandit optimization.
method Gaussian process upper confidence bound (GP-UCB) algorithm with refined analysis.
result Achieves O ( T ln 2 T ) O(\sqrt{T \ln^2 T}) O ( T ln 2 T ) cumulative regret under squared exponential kernel. Bayesian bandit algorithms with approximate inference improve regret bounds in stochastic linear bandits.
problem Theoretical justification for Bayesian bandit algorithms with approximate inference in stochastic linear bandits.
method Proposed a theoretical framework to analyze approximate inference impact and conducted frequentist regret analysis on LinTS and LinBUCB.
result LinTS and LinBUCB preserve their original regret upper bounds with larger constant terms in approximate inference settings.
Mirror descent linked to information ratio via Bayesian regret bounds.
problem Understanding stability in mirror descent and its relation to information ratio.
method Developed a connection between mirror descent and information ratio using Bayesian regret bounds.
result Mirror descent with suitable estimators and distributions achieves bounds similar to information-directed sampling.
Paper analyzes GP-EI for Bayesian optimization with no regret and provides guidance on choosing incumbents.
problem Analyzing cumulative regret of GP-EI with different incumbents in noisy Bayesian optimization.
method Analyzes GP-EI with three incumbents (BPMI, BSPMI, BOI) in both SE and Matérn kernels, proving no-regret for BPMI and BSPMI.
result GP-EI with BPMI and BSPMI is a no-regret algorithm for both SE and Matérn kernels, providing theoretical guidance for choosing incumbents.
This paper analyzes regret bounds for Gaussian process Thompson sampling.
problem Analyzing the performance of Gaussian process Thompson sampling (GP-TS) in Bayesian optimization.
method The paper derives several regret bounds for GP-TS, including a lower bound, upper bounds on the second moment of cumulative regret, expected lenient regret, and improved cumulative regret.
result The paper provides improved regret upper bounds for GP-TS, showing that it suffers from a polynomial dependence on 1 / δ 1/δ 1/ δ with probability δ δ δ . Distributed Thompson sampling improves regret convergence in constrained communication networks.
problem Maximizing a black-box function with multi-agent Bayesian optimization under communication constraints.
method Distributed Thompson sampling using Gaussian processes, with theoretical bounds on regret convergence.
result Theoretical bounds on Bayesian average and simple regret depend on communication graph structure and are applicable in constrained networks.
EBUCB framework achieves optimal regret with bounded approximate inference error.
problem Theoretical gap between practical performance and theoretical justification of Bayesian bandit algorithms with approximate inference.
method Enhanced Bayesian Upper Confidence Bound (EBUCB) framework that accommodates bandit problems with approximate inference.
result EBUCB achieves optimal regret order O ( log T ) O(\log T) O ( log T ) under certain conditions on inference error. Bayesian optimisation algorithm for unknown search spaces with sub-linear regret.
problem Efficient optimisation of expensive black-box functions in unknown search spaces.
method Expands search space over iterations based on a hyperharmonic series, scales to high dimensions.
result Sub-linear regret growth for both algorithms.
Posterior sampling-based EI achieves sublinear regret bounds for expensive function optimization.
problem Theoretical analysis of expected improvement (EI) in Bayesian optimization.
method Randomized posterior sampling of EI.
result Achieves sublinear Bayesian cumulative regret bounds.
TVBO optimizes time-varying functions with asymptotically vanishing regret.
problem Understanding the asymptotic performance of TVBO for time-varying black-box functions.
method Provided upper and lower bounds for cumulative regret of TVBO algorithms.
result TVBO algorithms can achieve asymptotically vanishing regret under certain conditions.
Bayesian algorithms minimize cumulative regret in decentralized multi-agent bandits.
problem Minimizing cumulative regret in a decentralized multi-agent multi-armed bandit problem.
method Proposed decentralized Bayesian multi-armed bandit framework, including Thompson Sampling and Bayes-UCB algorithms.
result Regret scales logarithmically with constants matching those of an optimal centralized agent.
Enhances RL with function approximation, improving regret bounds.
problem Improving exploration in reinforcement learning with function approximation.
method Prior-dependent Bayesian regret bound for PSRL with linear mixture MDPs, using value-targeted model learning and variance reduction.
result Established an upper bound of O ( d H 3 T log T ) {\mathcal{O}}(d\sqrt{H^3 T \log T}) O ( d H 3 T log T ) for PSRL. TS-RSR improves batch Bayesian Optimization by minimizing redundancy and focusing on high uncertainty points.
problem Efficient batch selection in Bayesian Optimization to reduce redundancy and improve performance.
method TS-RSR uses Thompson Sampling to minimize a regret to uncertainty ratio for batch selection.
result TS-RSR outperforms state-of-the-art batch BO algorithms on various test functions.
New meta-learning framework for minimizing simple regret in bandits.
problem Minimizing simple regret in a sequence of bandit tasks with unknown distributions.
method Developed Bayesian and frequentist meta-learning algorithms for bandits, analyzing their meta simple regret.
result Bayesian algorithm achieves i l d e O ( m / n ) ilde{O}(m / \sqrt{n}) i l d e O ( m / n ) meta simple regret, frequentist algorithm i l d e O ( m n + m / n ) ilde{O}(\sqrt{m} n + m/ \sqrt{n}) i l d e O ( m n + m / n ) . Bayesian framework reduces online optimization regret.
problem Sequential optimization in dynamic environments with bounded losses.
method PAC-Bayes theory and Bayesian updating principles.
result Achieves O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) regret for bounded losses. This paper improves Bayesian optimization methods with tighter regret bounds and practical solutions.
problem Improving Bayesian optimization methods with tighter regret bounds and practical solutions.
method The paper analyzes and compares different acquisition functions (GP-UCB, TS, PIMS) to achieve tighter Bayesian cumulative regret bounds and address practical issues.
result PIMS achieves the tighter BCR bound and avoids hyperparameter tuning, unlike GP-UCB and TS.
New geometric metrics improve Bayesian optimization performance evaluation.
problem Current metrics lack geometric insights and cannot compare algorithms effectively.
method Proposed four geometric metrics: precision, recall, average degree, and average distance.
result Proposed metrics provide more detailed evaluation of Bayesian optimization.
Paper improves Bayesian regret bounds for Thompson Sampling in reinforcement learning.
problem Improving Bayesian regret bounds for Thompson Sampling in reinforcement learning.
method Using a discrete set of surrogate environments and posterior consistency analysis, the authors derive an upper bound of order O ( H d l 1 T ) O(H\sqrt{d_{l_1}T}) O ( H d l 1 T ) . result The derived upper bound of O ( H d l 1 T ) O(H\sqrt{d_{l_1}T}) O ( H d l 1 T ) is a significant improvement over previous bounds. New algorithm reduces regret in sequential decision-making problems.
problem Balancing exploration and exploitation in online sequential decision problems.
method Variational Bayesian optimistic sampling (VBOS) for optimizing policies.
result VBOS achieves i l d e O ( A T ) ilde O(\sqrt{AT}) i l d e O ( A T ) Bayesian regret for stochastic multi-armed bandits. Bayes optimal algorithm under certain conditions doesn't achieve exponential simple regret.
problem Best arm identification with normal rewards over time.
method Fixed-budget best arm identification problem with rewards from normal distributions. Evaluates performance via simple regret.
result Bayes optimal algorithm does not yield exponential decrease in simple regret.
We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the information-theoretic tools of Russo and Van Roy (2016) for proving Bayesian regret bounds and combine th…
Bayesian framework learns latent preference archetypes for many-objective optimization.
problem Expanding space of trade-offs and context-dependent human values.
method Dirichlet-process mixture model for latent preference archetypes, hybrid queries for efficient information.
result Mixture-aware Bayesian optimization outperforms standard methods on synthetic and real-world benchmarks.
Improved BO algorithms reduce prediction error under Gaussian noise.
problem Reducing prediction error in Bayesian optimization with Gaussian noise.
method Established new prediction error bounds for Gaussian process under frequentist setting.
result Proved improved convergence rates of cumulative regret for GP-UCB and GP-TS.
Algorithm reduces regret in safe Bayesian optimization with monotonicity constraints.
problem Sequentially maximize unknown function with safety constraints.
method Sequential algorithms using Gaussian processes with safety constraints modeled as monotonicity.
result Sublinear regret achieved for expanding safe region and finding optimal s s s . The paper addresses frequentist regret of Linear Thompson Sampling in stochastic linear bandits.
problem The frequentist regret of Linear Thompson Sampling (LinTS) is worse than its Bayesian counterpart.
method The paper proves the fundamental nature of the frequentist regret bound for LinTS and proposes a data-driven version of LinTS to achieve minimax optimal frequentist regret.
result The frequentist regret bound for LinTS is O ~ ( d d T ) \widetilde{\mathcal{O}}(d\sqrt{dT}) O ( d d T ) , which is the best possible under certain conditions. Thompson Sampling tackles noisy context in stochastic bandits.
problem Designing an action policy for noisy, corrupted contexts in stochastic bandits.
method Introducing a Thompson Sampling algorithm for Gaussian bandits with Gaussian context noise, adopting an information-theoretic analysis.
result Demonstrates the Bayesian regret of the proposed algorithm concerning the oracle's action policy.
We present two alternative ways to apply PAC-Bayesian analysis to sequences of dependent random variables. The first is based on a new lemma that enables to bound expectations of convex functions of certain dependent random variables by expectations of the same functions of independent Bernoulli random variables. This …
Proposes MCBO for causal Bayesian optimization with model learning and regret bounds.
problem Maximizing downstream variables in unknown structural models.
method Model-based causal Bayesian optimization (MCBO) that learns full system models and trades off exploration and exploitation.
result First non-asymptotic bounds for CBO and practical implementation showing superior performance.
New algorithm reduces regret bounds for Bayesian optimization with unknown hyperparameters.
problem Optimizing black-box functions with unknown hyperparameters, especially length scale.
method Length Scale Balancing (LB) - aggregating multiple surrogate models with varying length scales.
result LB achieves a regret bound only logaritically away from the oracle algorithm.
Bayesian optimization method for permutations accelerates combinatorial search.
problem Optimizing expensive-to-evaluate objectives on permutation problems.
method LAW2ORDER, a batch Bayesian optimization method based on the acquisition weighted kernel.
result LAW2ORDER achieves sublinear batch cumulative regret, demonstrating accelerated search.
Bayesian optimization algorithm reduces regret with efficient region pruning.
problem Sequential optimization of unknown functions in high-dimensional spaces.
method Gaussian process-based, domain shrinking through tree-based region pruning.
result Order-optimal regret performance with reduced computational complexity.
Random exploration optimizes Bayesian optimization with optimal error rates and computational efficiency.
problem Optimizing Gaussian Process models in Bayesian optimization.
method Random sampling from a distribution in an infinite dimensional Hilbert space, with domain shrinking and order-optimal regret guarantees.
result Achieves optimal error rates and computational efficiency in both noise-free and noisy settings.
PS4POMDPs algorithm simplifies online learning for episodic POMDPs with unknown models.
problem Learning in POMDPs is harder than in MDPs; online learning is especially challenging.
method Posterior Sampling-based reinforcement learning algorithm (PS4POMDPs)
result Bayesian regret scales as √number of episodes and is polynomial in other parameters.
The paper tightens the regret rate for linear bandit problems.
problem Bayesian regret in linear bandit problems.
method Information-theoretic framework and chaining argument.
result Established a new bound with a tight rate of O ( d T ) O(d\sqrt{T}) O ( d T ) . New algorithm robust to outliers in Bayesian Optimization.
problem Vulnerability of Bayesian Optimization to extreme outliers.
method Introduces a new adversary with a frequency-bounded corruption budget and derives RCGP-UCB algorithm.
result Achieves sublinear regret in the presence of up to O ( T 1 / 4 ) O(T^{1/4}) O ( T 1/4 ) and O ( T 1 / 7 ) O(T^{1/7}) O ( T 1/7 ) corruptions with possibly infinite magnitude. New PAC-Bayesian bounds for online learning with data streams.
problem Challenges of traditional PAC-Bayesian bounds in dynamic data collection.
method Developed new PAC-Bayesian bounds in online learning framework, using updated regret definition and batch-to-online conversion.
result PAC-Bayesian bounds hold for online learning with dependent data and non-convex losses.
qEUBO optimizes decision-making with noisy feedback.
problem Optimizing decision-making with noisy preference feedback.
method Introduces qEUBO as a novel acquisition function for preferential Bayesian optimization.
result qEUBO is one-step Bayes optimal and enjoys an approximation guarantee under noise.
MINTS uses a minimalist Bayesian framework to tackle multi-armed bandits with structural constraints.
problem Sequential decision-making under uncertainty with complex structural constraints.
method Minimalist Bayesian framework with profile likelihood to eliminate nuisance parameters.
result MINTS achieves near-optimal regret guarantees and adapts to unimodal structure.
New algorithm learns LQR with O ( T ) O(\sqrt{T}) O ( T ) regret using Langevin dynamics and excitation.
problem Learning LQR with a O ( T ) O(\sqrt{T}) O ( T ) regret bound. method Thompson sampling with Langevin dynamics and excitation mechanism.
result Achieved O ( T ) O(\sqrt{T}) O ( T ) regret bound for LQR learning. Paper establishes no-regret property for practical EGO optimization.
problem No theoretical bounds on cumulative regret for practical EGO.
method Introduced practical EGO with a positive nugget, analyzed its regret bounds.
result Practical EGO is a no-regret algorithm with sublinear regret bounds.
Proposes a new PBO method with theoretical guarantees.
problem Optimizing expensive functions in parallel with noisy evaluations.
method Randomized Kriging Believer (KB) based on KB heuristic.
result Randomized KB achieves Bayesian expected regret guarantees.
We consider the stochastic multi-armed bandit problem with a prior distribution on the reward distributions. We are interested in studying prior-free and prior-dependent regret bounds, very much in the same spirit as the usual distribution-free and distribution-dependent bounds for the non-Bayesian stochastic bandit. B…
GACBO optimizes unknown causal graphs with interventions.
problem Optimizing a target variable on an unknown causal graph with interventions.
method Graph Agnostic Causal Bayesian Optimisation (GACBO) seeks to balance exploitation and exploration of causal structures and functions.
result GACBO outperforms baselines in simulated and real-world applications.
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.
Bayesian algorithms improve online learning with adversaries over infinite action spaces.
problem Online learning with adversaries over infinite action spaces.
method Developed a Thompson sampling algorithm for online learning with an adversary's prior over the space of actions.
result Thompson sampling over a Gaussian process prior achieves a rate of O ( β T d log ( 1 + d λ β ) ) O(β\sqrt{Td\log(1+\sqrt{d}\fracλβ)}) O ( β T d log ( 1 + d β λ ) ) against a β β β -bounded λ λ λ -Lipschitz adversary.