New algorithms minimize simple and cumulative regret in contextual bandits.
problem Minimizing simple and cumulative regret in contextual bandit settings.
method Proposed new algorithms using conformal arm sets (CASs).
result Near-optimal minimax guarantees for simple regret and state-of-the-art guarantees for cumulative regret.
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 δ δ δ . 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.
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.
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.
The paper tackles best arm identification with minimal regret in experiments.
problem Identifying the best arm with minimal regret in experiments.
method Information-theoretic techniques and Double KL-UCB algorithm.
result Achieves asymptotic optimality in identifying the best arm with minimal regret.
Logarithmic regret achieved in Q-learning with positive gap.
problem Achieving logarithmic cumulative regret in Q-learning with positive sub-optimality gap.
method Optimistic Q-learning with logarithmic regret bound.
result Logarithmic cumulative regret bound proven for optimistic Q-learning.
Optimistic algorithm reduces regret and constraint violations in online convex optimization with adversarial constraints.
problem Online convex optimization with adversarial constraints.
method Improved algorithm using accurate predictions of loss and constraint functions.
result Improved bounds on regret and cumulative constraint violations.
Inexact acquisition solutions in BO lead to sublinear cumulative regret.
problem Inexact maximization of acquisition functions in Bayesian optimization.
method Define inaccuracy measure, establish cumulative regret bounds for GP-UCB and GP-TS.
result Inexact BO algorithms can achieve sublinear cumulative regret under appropriate inaccuracy conditions.
New algorithm reduces regret in CBs with time-varying models.
problem Designing robust interventions in CBs with unknown, fluctuating causal models.
method Proposes a robust CB algorithm with upper and lower bounds on regret.
result Achieves nearly optimal i l d e O ( T ) ilde{\mathcal{O}}(\sqrt{T}) i l d e O ( T ) regret under certain conditions. 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.
Study collaborative learning among multi-agents in multi-armed bandits.
problem Minimizing group cumulative regret in a heterogeneous multi-agent setting.
method Developed decentralized algorithms for collaboration between N N N agents learning M M M stochastic multi-armed bandits. result Proved near-optimal behavior of proposed algorithms for group regret.
This paper addresses robust CBs for linear SEMs with model fluctuations.
problem Designing interventions in causal systems with linear SEMs that are robust to model fluctuations.
method Develops a robust CB algorithm and analyzes its regret under model deviation.
result The proposed algorithm achieves nearly optimal i l d e O ( T ) ilde{\mathcal{O}}(\sqrt{T}) i l d e O ( T ) regret when C C C is o ( T ) o(\sqrt{T}) o ( T ) and maintains sub-linear regret for a broader range of C C C . 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.
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.
LinConTS improves regret and constraint violations in probabilistic linearly constrained bandits.
problem Maximizing cumulative reward under probabilistic linear constraints.
method LinConTS, a Thompson Sampling-based algorithm for bandits with linear constraints.
result LinConTS achieves O(log T) regret and constraint violations for suboptimal arms.
Study on sequential prediction with log-loss, focusing on well-specified and misspecified cases.
problem Sequential prediction with log-loss under different specification conditions.
method Analysis of cumulative regret in well-specified and misspecified cases for a Gaussian location hypothesis class.
result Cumulative regrets in well-specified and misspecified cases asymptotically coincide for the d d d -dimensional Gaussian location hypothesis class. New algorithms for efficient causal interventions with budget constraints and without constraints.
problem Efficiently learning best interventions in causal graphs with budget constraints.
method Developed algorithms for both budgeted and non-budgeted causal bandits, optimizing regret and side-information usage.
result Proposed algorithms minimize cumulative regret and perform better than standard methods.
Study uses contextual bandits to optimize charity exposure in donation solicitation.
problem Optimizing charity exposure in donation solicitation using survey responses.
method Adaptive experiment design to balance cumulative regret minimization and simple regret minimization.
result Adaptive experimentation yields better policy learning outcomes than uniform randomization.
UCRL-CMDP algorithm optimizes RL with constraints on average costs.
problem Optimizing RL in MDPs with average cost constraints.
method Model-based RL algorithms maximizing reward while keeping costs within bounds.
result UCRL-CMDP algorithm's expected regret is upper-bounded by $T^{2\slash 3}$ .
New algorithm reduces constraint violation to O ( T 1 / 3 ) O(T^{1/3}) O ( T 1/3 ) while maintaining O ( T ) O(\sqrt{T}) O ( T ) regret.
problem Minimizing static regret and cumulative constraint violation in constrained online convex optimization.
method Proposes an algorithm that achieves O ( T ) O(\sqrt{T}) O ( T ) regret and O ( T 1 / 3 ) O(T^{1/3}) O ( T 1/3 ) cumulative constraint violation. result Shows that O ( T 1 / 3 ) O(T^{1/3}) O ( T 1/3 ) cumulative constraint violation is achievable with O ( T ) O(\sqrt{T}) O ( T ) regret. A new bandit problem where experiments can be interrupted if results are not promising.
problem Interruptible multi-armed bandit problem with a threshold for cumulative reward.
method Formalized survival regret, identified key components (regret and probability of ruin), derived lower bounds and optimal policies.
result No policy can achieve sublinear survival regret, but optimal policies minimize survival regret in a Pareto sense.
Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning
problem Multi-agent multi-armed bandit problem in competitive setup with two-sided matching markets under human-centric decision making model
method Using cumulative prospect theory (CPT) to emulate human preferences
result Improved regret guarantees in adversarial markets with CPT as risk-sensitive measure
The paper analyzes Q-learning in 2-player Markov games and provides gap-dependent logarithmic regret bounds.
problem Analyzing the cumulative regret of Nash Q-learning in 2-player turn-based stochastic Markov games.
method Proposed gap-dependent logarithmic upper bounds for cumulative regret in episodic tabular setting and discounted game setting.
result The proposed bounds match theoretical lower bounds up to a logarithmic term.
In this paper, we analyze a generic algorithm scheme for sequential global optimization using Gaussian processes. The upper bounds we derive on the cumulative regret for this generic algorithm improve by an exponential factor the previously known bounds for algorithms like GP-UCB. We also introduce the novel Gaussian P…
Proposes a new sampling method for online learning with cumulative oversampling.
problem Budgeted Influence Maximization in online learning.
method Cumulative Oversampling (CO) method for online learning.
result CO-based algorithm achieves comparable regret to UCB-based algorithms and performs similarly to Thompson Sampling.
We consider a stochastic bandit problem with infinitely many arms. In this setting, the learner has no chance of trying all the arms even once and has to dedicate its limited number of samples only to a certain number of arms. All previous algorithms for this setting were designed for minimizing the cumulative regret o…
New findings show increased exploration needed in non-stationary RL tasks.
problem Task non-stationarity leads to conflicting goals in RL.
method Analyzes the trade-off between cumulative and simple regret in non-stationary environments.
result Increased exploration is necessary to balance CR and SR in non-stationary tasks.
Proposes a max-utility arm selection strategy for reducing cumulative regret in sequential query recommendations.
problem Reduces cumulative regret in sequential query recommendations for closed loop interactive learning settings.
method Proposes a max-utility arm selection strategy based on the maximum utility of arms.
result Improves cumulative regret substantially compared to baseline algorithms and random selection.
New algorithms achieve near-optimal cumulative loss in nonparametric online learning and games.
problem Fast rates of convergence in nonparametric online regression and classification.
method Randomized proper learning algorithms, hierarchical aggregation, multi-scale extension, stability proof.
result Achieved near-optimal cumulative loss bounds for real-valued and binary games.
Optimal algorithm for high-dimensional stochastic linear bandits with sparse parameters.
problem High-dimensional stochastic linear bandits with sparse parameters.
method Three-stage arm selection algorithm using thresholded Lasso for estimation.
result Achieves exact minimax optimality in cumulative regret.
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.
Algorithm optimizes cascaded functions with known structure.
problem Optimizing a function network with known structure.
method GPN-UCB algorithm with upper confidence bounds and theoretical regret bounds.
result Near-optimal cumulative and simple regret bounds.
Improved cumulative regret for sequence prediction with limited expert advice.
problem Minimizing cumulative regret in sequence prediction with limited information.
method Convex combination of experts with limited observation, achieving constant regret.
result Strategies achieve constant regret independent of the horizon T, improving over standard bounds.
New method optimizes multiple objectives in A/B testing for AI and clinical trials.
problem Minimizing cumulative regret, maximizing CATE, and ensuring differential privacy in large-scale experiments.
method ConSE and DP-ConSE algorithms for sequential segmentation and elimination, achieving Pareto-optimal frontier.
result Privacy comes 'for free' in our framework, with only asymptotically negligible costs to regret and accuracy.
Efficient binary sampling method for global optimization of univariate functions with low regret.
problem Global optimization of univariate loss functions.
method Binary sampling approach to circumvent hard-to-determine query points in traditional methods.
result At most L log ( 3 T ) L\log (3T) L log ( 3 T ) and 2.25 H 2.25H 2.25 H regret for L L L -Lipschitz continuous and H H H -Lipschitz smooth functions respectively. The paper proves a regret bound for a sub-Gaussian mixture on unbounded data.
problem Tackles the challenge of achieving regret bounds for sub-Gaussian mixtures on unbounded data.
method Uses path-wise (deterministic) regret bounds and a cumulative variance process to derive the bound.
result Shows that on a specific event, the regret is eventually bounded by ln(ln V_T).
New algorithm minimizes cumulative loss in dynamic linear bandits without prior knowledge of comparator switches.
problem Minimizing cumulative loss in dynamic linear bandits with unknown number of switches.
method Combining several bandit algorithms to adapt to unknown number of switches without prior knowledge.
result First algorithm achieving optimal regret guarantee of O ( d ( 1 + S T ) T ) \mathcal{O}\big(\sqrt{d(1+S_T) T}\big) O ( d ( 1 + S T ) T ) up to poly-logarithmic terms. I introduce and analyse an anytime version of the Optimally Confident UCB (OCUCB) algorithm designed for minimising the cumulative regret in finite-armed stochastic bandits with subgaussian noise. The new algorithm is simple, intuitive (in hindsight) and comes with the strongest finite-time regret guarantees for a hori…
New framework finds periodic policies in reset-free MDPs with sublinear regret.
problem Reset-free reinforcement learning with unknown dynamics and terminal law constraints.
method Periodic framework, periodic policies, periodic regret.
result First non-asymptotic guarantees for reset-free learning in multi-agent settings.
EgalMAB solves fair resource allocation in stochastic bandits.
problem Fair resource allocation in a stochastic multi-armed bandit setting.
method Design and analysis of UCB-based policy EgalUCB.
result Established upper bounds on cumulative regret.
Reduces dynamic regret to static problem in RKHS.
problem Minimizing cumulative loss in online convex optimization.
method Reduces dynamic regret to static regret problem in RKHS.
result Optimal dynamic regret guarantees for linear losses and new bounds for exp-concave and improper linear regression.
In this paper, we consider the problem of sequentially optimizing a black-box function f f f based on noisy samples and bandit feedback. We assume that f f f is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yielding a commonly-considered non-Bayesian form of Gaussian process …
New algorithms minimize regret in both adversarial and stochastic contexts.
problem Minimizing regret in linear contextual bandits.
method Best-of-both-worlds algorithms using FTRL with Shannon entropy regularizer.
result Achieves near-optimal regret bounds in both adversarial and stochastic regimes.
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 method reduces dynamic regret for non-stationary bandits.
problem Non-stationary stochastic multi-armed bandit problem with changing optimal arm.
method Proposes a method achieving near-optimal dynamic regret without prior knowledge of changes.
result Achieves O ~ ( K N ( S + 1 ) ) \widetilde O(\sqrt{K N(S+1)}) O ( K N ( S + 1 ) ) dynamic regret. Neural Thompson Sampling uses deep neural networks for contextual bandit problems.
problem Solving contextual multi-armed bandit problems.
method Adapts deep neural networks for exploration and exploitation in a novel posterior distribution.
result Guaranteed cumulative regret of O ( T 1 / 2 ) \mathcal{O}(T^{1/2}) O ( T 1/2 ) for bounded reward functions. New algorithms reduce dynamic regret for convex and smooth functions in non-stationary environments.
problem Online convex optimization in non-stationary environments.
method Proposed novel online algorithms exploiting smoothness to reduce dynamic regret.
result Dynamic regret improved to O ( T ) \mathcal{O}(T) O ( T ) for convex and smooth functions.