New tighter confidence bounds for sequential kernel regression.
problem Quantifying uncertainty in sequential learning algorithms.
method Martingale tail inequalities and conic programming.
result New confidence bounds are tighter than existing ones.
A new differentiable UCB algorithm for linear bandits learns adaptive confidence bounds.
problem Inability of UCB to strike optimal exploration-exploitation due to confidence bounds.
method Proposes a differentiable linear bandit algorithm and a gradient estimator for learning adaptive confidence bounds.
result Achieves a i l d e O ( β ^ d T ) ilde{\mathcal{O}}(\hatβ\sqrt{dT}) i l d e O ( β ^ d T ) upper bound of T T T -round regret. The paper honors Lai's contributions to multi-armed bandits and establishes new regret bounds.
problem Improving regret bounds in multi-armed bandit problems.
method Establishes non-asymptotic regret bounds for upper confidence bound indices.
result New regret bounds match Lai-Robbins lower bound.
The paper extends confidence sequences for infinite variance data.
problem Addressing confidence sequences for distributions with infinite variance.
method Establishing lower bounds and deriving tight confidence sequences for relaxed bounded p t h p^{th} p t h -moment distributions. result Derived confidence sequences are tighter than those using Dubins-Savage inequality.
Improved confidence bounds for linear logistic model with applications to bandits.
problem Improving confidence bounds for linear logistic model.
method Self-concordant analysis of the logistic loss to avoid dependence on worst-case variance.
result Significant improvement in confidence bounds, avoiding dependence on 1 / κ 1/κ 1/ κ . Research aims to improve confidence intervals for RKHS elements in online learning.
problem Improper confidence intervals lead to suboptimal regret bounds in kernel-based bandit and reinforcement learning.
method Formalizes the open problem of online confidence intervals in RKHS and reviews existing results.
result Identifies the online nature of observation points as the main challenge for tight confidence intervals.
Near-optimal confidence intervals for bounded data.
problem Online inference for sequential decision problems like A/B testing.
method Utilizing Bentkus' concentration results to improve on existing methods.
result Near-optimal confidence intervals confirmed favorable in synthetic and practical applications.
A new framework tightens risk measure confidence bounds.
problem Improving confidence bounds for various risk measures.
method Distribution optimization framework with two estimation schemes based on concentration bounds.
result Consistently tighter confidence bounds compared to previous methods.
Note improves confidence bounds for random variables.
problem Improving confidence bounds for random variables with unbounded ranges and different distributions.
method PAC-Bayes-ification of a derived confidence bound.
result Streamlined proofs for existing results.
Improved algorithms for stochastic linear bandits using tighter confidence sequences.
problem Stochastic linear bandits with improved worst-case regret guarantees.
method Novel tail bound for adaptive martingale mixtures to construct tighter confidence sequences.
result Linear bandit algorithm achieves competitive worst-case regret.
Paper presents robust confidence sequences for means with known moment bounds and arbitrary corruption.
problem Tackles robustness to outliers and adversarial corruptions in mean estimation.
method Designs new robust exponential supermartingales to create confidence sequences.
result Achieves optimal width and shows smaller margin of error compared to fixed-time robust methods.
The paper finds a fundamental trade-off between confidence and efficiency in transductive conformal prediction.
problem The challenge is to balance confidence and efficiency in predicting multiple data points.
method The authors derive a strict finite-sample bound and introduce a practical algorithm to approach this bound.
result Any non-trivial confidence level leads to exponential growth in prediction set size, with a linear scaling in the number of samples.
This paper improves GP-UCB by using a shifted exponential distribution for confidence parameters.
problem Theoretical confidence parameter in GP-UCB increases with iterations, leading to large values.
method Introduced IRGP-UCB, a randomized variant of GP-UCB using a shifted exponential distribution for confidence parameters.
result IRGP-UCB achieves sub-linear regret without increasing the confidence parameter.
Improved online confidence bounds for multinomial logistic models in bandits.
problem Achieving optimal regret in multinomial logistic bandits with bounded parameters and outcomes.
method Deriving an improved online confidence bound and proposing OFU-MNL++ and OFU-MN 2 ^2 2 L algorithms. result Achieved variance-dependent optimal regret for MNL bandits.
The paper presents a method to compute trusted confidence bounds for LECs in CPS.
problem Non-transparent predictions of LECs make CPS safety challenging.
method Inductive Conformal Prediction (ICP) and Triplet Network architecture.
result Efficient real-time computation of trusted confidence bounds.
Develops confidence bounds for off-policy evaluation in contextual bandits.
problem Evaluating policies that were not used to collect data.
method Martingale analysis for non-asymptotic, non-parametric, and valid confidence sequences.
result Empirically tight bounds on failure probability and width.
In the field of reinforcement learning there has been recent progress towards safety and high-confidence bounds on policy performance. However, to our knowledge, no practical methods exist for determining high-confidence policy performance bounds in the inverse reinforcement learning setting---where the true reward fun…
The paper improves confidence regions for band-limited functions using tighter norm bounds and majority voting.
problem Constructing reliable confidence regions for band-limited functions from noisy data.
method Improved norm bounds using Hoeffding's inequality and empirical Bernstein bound, majority voting to aggregate intervals.
result Confidence intervals retain their simultaneous coverage guarantee even when aggregated from random subsamples.
Paper improves confidence intervals and variance estimation for deep learning models.
problem Improving confidence intervals and variance estimation in deep learning models.
method Residual-based framework for conditional variance estimation; robust bootstrap procedure for confidence intervals.
result First non-asymptotic bounds for variance estimation using ReLU networks.
The estimation of probabilities of default (PDs) for low default portfolios by means of upper confidence bounds is a well established procedure in many financial institutions. However, there are often discussions within the institutions or between institutions and supervisors about which confidence level to use for the…
We provide a pointwise confidence bound for non-linear least-squares with fixed design.
problem Confidence estimation in non-linear ℓ 2 \ell^2 ℓ 2 -regularized least squares. method Pointwise confidence bound for local minimizers, using weighted norm involving inverse-Hessian.
result The proposed confidence bound scales with the test input's similarity to the training data.
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. For an autonomous agent, executing a poor policy may be costly or even dangerous. For such agents, it is desirable to determine confidence interval lower bounds on the performance of any given policy without executing said policy. Current methods for exact high confidence off-policy evaluation that use importance sampl…
Proposes a method to compute valid lower confidence bounds for multiple models selected based on their performance.
problem Model selection and evaluation in machine learning.
method Interprets model selection as a simultaneous inference problem, uses bootstrap tilting and maxT-type multiplicity correction.
result Yields valid lower confidence bounds that are at least as good as standard approaches and reliably reach nominal coverage probability.
Paper improves CI and CS for bounded means using betting and mixtures.
problem Estimating means of bounded random variables.
method Composite nonnegative martingales, testing by betting, method of mixtures.
result Empirically outperforms existing CI and CS methods.
Improved regret bounds for logistic bandits via novel confidence set construction.
problem Dependencies in parameter space for logistic bandits, especially when S ≥ d S \geq d S ≥ d . method Regret-to-confidence-set conversion (R2CS) to construct convex confidence sets.
result Strict improvement in regret bound w.r.t. S S S in logistic bandits. The paper improves confidence ellipsoids for ridge regression with PAC bounds.
problem Uncertainty quantification in ridge regression for insufficiently exciting inputs.
method Extension of SPS EOA algorithm to ridge regression with PAC bounds.
result Explicitly shows how regularization parameter affects region sizes and provides tighter bounds.
We propose an estimator and confidence interval for computing the value of a policy from off-policy data in the contextual bandit setting. To this end we apply empirical likelihood techniques to formulate our estimator and confidence interval as simple convex optimization problems. Using the lower bound of our confiden…
Improved Bayesian optimisation method using randomised Gaussian process UCB.
problem Improving performance in Bayesian optimisation.
method Developed a modified Gaussian process upper confidence bound (GP-UCB) acquisition function.
result The method achieves better performance than GP-UCB in various problems.
WS-KDE provides robust confidence bounds for stochastic functions.
problem Optimizing time-consuming black-box functions with stochastic outputs.
method Wilson Score Kernel Density Estimation (WS-KDE) for Bayesian optimization.
result WS-KDE provides reliable confidence bounds for any stochastic function.
Confidence measures for the generalization error are crucial when small training samples are used to construct classifiers. A common approach is to estimate the generalization error by resampling and then assume the resampled estimator follows a known distribution to form a confidence set [Kohavi 1995, Martin 1996,Yang…
This note gives a short, self-contained, proof of a sharp connection between Gittins indices and Bayesian upper confidence bound algorithms. I consider a Gaussian multi-armed bandit problem with discount factor γ γ γ . The Gittins index of an arm is shown to equal the γ γ γ -quantile of the posterior distribution of the arm'…
Bayesian methods improve drug discovery experiment design.
problem Optimizing drug screening experiments in high-dimensional data.
method Bayesian inference and optimisation with upper confidence bound algorithms, Thompson sampling, and sparse tree search.
result Sparse tree search techniques outperform other methods in drug toxicity screening.
Upper Confidence Bound (UCB) method is arguably the most celebrated one used in online decision making with partial information feedback. Existing techniques for constructing confidence bounds are typically built upon various concentration inequalities, which thus lead to over-exploration. In this paper, we propose a n…
The paper improves confidence set construction for statistical inference.
problem Constructing reliable confidence sets in statistical inference.
method Establishes a finite-sample bound using effective dimension and generalized self-concordance.
result Developed a confidence set adapted to optimization landscapes.
Berry et al. (1997) initiated the development of the infinite arms bandit problem. They derived a regret lower bound of all allocation strategies for Bernoulli rewards with uniform priors, and proposed strategies based on success runs. Bonald and Proutière (2013) proposed a two-target algorithm that achieves the regret…
Study optimizes dynamic product selection and pricing using censored preference feedback.
problem Maximizing revenue from dynamic assortment and pricing decisions.
method Proposes a censored multinomial logit model and LCB pricing strategy combined with UCB or TS product selection.
result Achieves optimal regret bounds for dynamic pricing and selection.
New principle optimizes bandit decisions with context.
problem Dealing with general function classes and large context spaces in bandits.
method Upper Counterfactual Confidence Bounds (UCCB) principle.
result Proves optimality and efficiency in complex settings.
The betting CI outperforms classical methods in constructing confidence intervals for bounded means.
problem Constructing nonasymptotic confidence intervals for bounded means.
method A betting-based approach to define and time-uniform variants of confidence intervals (CSs).
result The betting CI matches the fundamental limits, outperforming existing empirical Bernstein CIs.
EB-TCε identifies the best arm with ε confidence in stochastic bandits.
problem Identifying the best arm in stochastic bandits with a fixed level of confidence.
method EB-TCε is a novel sampling rule for ε-best arm identification in stochastic bandits.
result EB-TCε is the first anytime algorithm for fixed confidence or fixed budget identification.
We propose an algorithm combining calibrated prediction and generalization bounds from learning theory to construct confidence sets for deep neural networks with PAC guarantees---i.e., the confidence set for a given input contains the true label with high probability. We demonstrate how our approach can be used to cons…
Bayes-assisted confidence sequences improve efficiency for bounded means.
problem Efficient uncertainty quantification for bounded IID means without parametric assumptions.
method Bayesian working predictive model selects adaptive martingale updates maximizing predictive log-growth.
result Asymptotically log-optimal performance with informative priors reducing width and sampling effort.
Paper defines and solves a problem in representation learning to ensure fairness with high confidence.
problem Learning fair representations with high confidence guarantees for all downstream tasks.
method Formally defines the problem, introduces FRG framework, proves high probability fairness, and demonstrates effectiveness empirically.
result FRG framework provides high-confidence guarantees for limiting unfairness across all downstream models and tasks.
One-bit feedback suffices for a bandit problem's optimal strategy.
problem Optimal strategy for multi-armed bandit problem with limited feedback.
method Coding and decoding schemes for one-bit feedback to mimic full-reward feedback.
result Regret ratio approaches 1 with one-bit feedback.
A new method optimizes robustness measures under input uncertainty using randomized Gaussian process upper confidence bound.
problem Optimizing robustness measures under input uncertainty.
method Randomized robustness measure GP-UCB (RRGP-UCB) that samples β from a chi-squared-based distribution.
result RRGP-UCB provides tight bounds on expected regret.
New algorithm optimizes online decision-making with dynamically generated actions.
problem Balancing action generation costs with optimal decision-making in online learning.
method Doubly-optimistic algorithm using LCB for action selection and UCB for action generation.
result Achieves optimal regret bound of O ( T d d + 2 d d d + 2 + d T log T ) O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}} + d\sqrt{T\log T}) O ( T d + 2 d d d + 2 d + d T log T ) . We design a general framework for answering adaptive statistical queries that focuses on providing explicit confidence intervals along with point estimates. Prior work in this area has either focused on providing tight confidence intervals for specific analyses, or providing general worst-case bounds for point estimate…
The SPS method constructs confidence regions for true parameters with optimal sample complexity.
problem Constructing exact, non-asymptotic confidence regions for true system parameters.
method Sign-Perturbed Sums (SPS) method, generalized to various types of problems.
result High probability upper bounds for SPS confidence regions show optimal shrinkage rate.