Statistical performance bounds for reinforcement learning (RL) algorithms can be critical for high-stakes applications like healthcare. This paper introduces a new framework for theoretically measuring the performance of such algorithms called Uniform-PAC, which is a strengthening of the classical Probably Approximatel…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “PAC regret”
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.
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 …
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 achieve uniform-PAC guarantees for RL with bounded eluder dimension.
problem Achieving strong performance guarantees in reinforcement learning.
method Proposes algorithms for nonlinear bandits and model-based episodic RL with a bounded eluder dimension.
result Achieves uniform-PAC sample complexity that matches state-of-the-art regret bounds or sample complexity guarantees.
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 regret for bounded losses.
New algorithm FLUTE achieves uniform-PAC convergence in RL with linear approx.
problem RL with linear function approximation lacks uniform-PAC guarantees.
method FLUTE algorithm with minimax value function estimator and multi-level partition scheme.
result Uniform-PAC convergence to optimal policy with high probability.
Private RL algorithm with privacy guarantees for personalized medicine decisions.
problem Privacy-preserving reinforcement learning for personalized medicine decisions.
method Developed a private optimism-based RL algorithm using joint differential privacy (JDP).
result Achieved strong PAC and regret bounds with a privacy guarantee.
New reinforcement learning algorithm achieves instance-optimal sample complexity.
problem Achieving low regret and identifying optimal policies in reinforcement learning.
method A novel planning-based algorithm that explicitly accounts for state visitation distributions.
result The proposed algorithm attains nearly minimax optimal sample complexity, improving over worst-case bounds.
Hybrid RL algorithms improve offline and online RL in linear MDPs.
problem Improving RL performance without single-policy concentrability.
method Developed computationally efficient algorithms for PAC and regret-minimizing RL in linear MDPs.
result Achieved sharper error or regret bounds for linear MDPs.
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 -dimensional Gaussian location hypothesis class.
Paper establishes new lower bounds for MDPs with changing transition kernels.
problem Minimizing sample complexity and regret in non-stationary MDPs.
method Developed novel lower bounds and constructed hard MDPs.
result Proved sample complexity lower bound.
New algorithm reduces contextual bandit identification to argmax calls.
problem Best-arm identification in stochastic contextual bandits.
method Instance-optimal PAC algorithm using argmax oracle calls.
result First instance-dependent PAC sample complexity for contextual bandits.
New framework connects online learning to statistical learning for better generalization bounds.
problem Deriving generalization bounds for statistical learning algorithms.
method Constructing an online learning game and showing a connection to statistical learning.
result Established a connection between online and statistical learning, leading to new generalization bounds.
Paper improves PAC-Bayes bounds using a better-than-KL divergence.
problem Estimating the generalization error of stochastic algorithms.
method Developed new PAC-Bayes bounds with a novel divergence.
result Achieved strictly tighter bounds than the KL divergence.
Study on a new family of problems interpolating expert advice and multi-armed bandits.
problem A new family of problems combining expert advice and multi-armed bandits.
method Proved minimax regret bounds and designed optimal PAC algorithms for pure exploration.
result Tight minimax regret bounds and optimal PAC algorithm for -BAI.
Unified model for interactive estimation with improved learnability measure.
problem Improving learnability in interactive estimation models.
method Introducing a combinatorial measure (dissimilarity dimension) and a general algorithm with polynomial bounds.
result Unified model subsumes statistical-query learning and structured bandits.
This paper establishes strong lower bounds for learning in revealing POMDPs.
problem Understanding the fundamental limits of reinforcement learning in revealing partially observable Markov Decision Processes (POMDPs).
method Develops strong PAC and regret lower bounds for learning in revealing POMDPs using multi-step revealing POMDPs as a case study.
result Strong polynomial lower bounds for learning in revealing POMDPs, achieving significantly smaller gaps against current upper bounds.
New PAC-Bayesian approach stabilizes actor-critic learning.
problem Training instability in actor-critic algorithms.
method Employing PAC-Bayesian bound as the critic training objective.
result Significant improvement in online learning performance.
Study robust online learning with adversarial perturbations.
problem Learning robust classifiers in the presence of adversarial perturbations.
method Formulated as an online learning problem, considered both realizable and agnostic learnability, defined new dimension controlling mistake/regret bounds.
result Showed new dimension controls mistake/regret bounds, generalized to multiclass hypothesis classes.
New method for semiparametric bandits reduces regret to optimal levels.
problem Complex reward structures in semiparametric bandits.
method Experimental-design approach with sharp regret bound and PAC bound.
result Minimax regret of and logarithmic regret under positive suboptimality gap.
Unified CS for GLMs improves bandit regret bounds.
problem Improving regret bounds for GLMs in bandit settings.
method Unified likelihood ratio-based CS with PAC-Bayesian bound.
result Unified CS attains poly(S)-free regret for Bernoulli.
State of the art online learning procedures focus either on selecting the best alternative ("best arm identification") or on minimizing the cost (the "regret"). We merge these two objectives by providing the theoretical analysis of cost minimizing algorithms that are also delta-PAC (with a proven guaranteed bound on th…
Efficient algorithms for online learning with changing action sets, achieving no-approximate-regret guarantees.
problem Online learning with sleeping experts/bandits, where only a subset of actions are available each time.
method Developed computationally efficient algorithms providing no-approximate-regret guarantees for the general problem and better approximation ratios for special cases.
result Achieved no-approximate-regret guarantees for the general sleeping expert/bandit problems and better approximation ratios for specific cases.
Dynamic pricing learns demand model from sparse product networks.
problem Minimizing revenue loss in a large network of products with unknown demand parameters.
method Combines optimism-in-the-face-of-uncertainty and PAC-Bayesian approaches.
result Achieves asymptotically optimal performance in terms of network size and time horizon.
Paper tightens PAC-Bayes bounds using coin-betting for better estimates.
problem Estimating mean of random elements with possibly S-dependent parameters.
method Refined PAC-Bayes proof strategy based on coin-betting framework.
result Derives tighter concentration inequalities for all sample sizes.
Study optimal stopping for diffusion processes using data-driven methods.
problem Optimal stopping for diffusion processes under unknown conditions.
method Data-driven approach, deriving upper and lower bounds on simple and cumulative regret.
result Verified minimax optimality and improved convergence rates.
We take initial steps in studying PAC-MDP algorithms with limited adaptivity, that is, algorithms that change its exploration policy as infrequently as possible during regret minimization. This is motivated by the difficulty of running fully adaptive algorithms in real-world applications (such as medical domains), and …
Survey of reinforcement learning guarantees with data constraints.
problem Guaranteeing near-optimal policies with limited data in reinforcement learning.
method Coverage-Structure-Objective (CSO) framework to decompose sample complexity results.
result Progress on PAC guarantees for reinforcement learning, covering various models and settings.
Simulators enable learning with generalization guarantees in computationally bounded worlds.
problem Generalization in learning theory
method Simulatable processes
result Recovery of PAC learning guarantees with VC dimension
Study laws of large numbers in online classification, determining optimal regret bounds.
problem Understanding how sequential sampling affects online learning and classification.
method Characterized online learnable classes and determined optimal regret bounds using Littlestone's dimension.
result Optimal regret bounds in online learning are determined, resolving open questions.
Efficient algorithm predicts unknown linear systems with long-term memory.
problem Predicting unknown and partially observed linear dynamical systems with long-term memory.
method Bounding the generalized Kolmogorov width of the Kalman filter model using spectral methods and conducting tight convex relaxation.
result Competes with Kalman filter in hindsight with only logarithmic regret.
We present a novel notion of complexity that interpolates between and generalizes some classic existing complexity notions in learning theory: for estimators like empirical risk minimization (ERM) with arbitrary bounded losses, it is upper bounded in terms of data-independent Rademacher complexity; for generalized Baye…
New algorithm reduces prediction error in online learning without knowing base measure.
problem Smoothed online learning without knowledge of base measure.
method R-Cover algorithm based on recursive coverings.
result First algorithm to guarantee sublinear regret for agnostic smoothed online learning without prior knowledge of base measure.
PAC-Bayesian bounds for MLPs with cross entropy loss validated.
problem Generalization bounds for MLPs with cross entropy loss.
method Introduced probabilistic explanations and proved PAC-Bayesian bounds using ELBO.
result MLPs with cross entropy loss inherently guarantee PAC-Bayesian generalization bounds.
Unified derivation of PAC-Bayes and MI bounds for general VC classes with fast rates.
problem Generalization bounds for machine learning models with VC classes.
method Unified derivation of conditional PAC-Bayesian and mutual information bounds, including MAC-Bayesian bounds.
result Nontrivial bounds for general VC classes and faster rates for specific conditions.
The developments of Rademacher complexity and PAC-Bayesian theory have been largely independent. One exception is the PAC-Bayes theorem of Kakade, Sridharan, and Tewari (2008), which is established via Rademacher complexity theory by viewing Gibbs classifiers as linear operators. The goal of this paper is to extend thi…
PAC-Wrap provides provable guarantees for semi-supervised anomaly detection.
problem Ensuring reliable anomaly detection in safety-critical applications.
method PAC-Wrap wraps around existing anomaly detection methods to provide PAC guarantees.
result PAC-Wrap effectively provides rigorous guarantees for various anomaly detectors.
Efficient PAC learning for contrastive linear representations is achieved.
problem Efficient PAC learning for contrastive linear representations.
method Relaxing the problem to a semi-definite program and using Rademacher complexity.
result First efficient PAC learning algorithm for contrastive learning.
This research improves PAC-Bayesian bounds for classification tasks using convexified loss.
problem Deriving generalization bounds for classification tasks with non-convex loss functions.
method Shift focus to misclassification excess risk bounds for PAC-Bayesian classification using convex surrogate loss and leveraging PAC-Bayesian relative bounds in expectation.
result Improved PAC-Bayesian bounds for classification tasks with convex surrogate loss.
Meta-learning bounds derived using PAC-Bayes theory for improved generalization.
problem Uncertainty in generalization performance for meta-learning with new tasks.
method PAC-Bayes relative entropy bounds and empirical risk minimization (ERM) method.
result Competitive generalization performance and rapid convergence with data-dependent prior.
PAC-Bayes framework fails on simple 1D linear classification task.
problem Proving the learnability of simple 1D linear classification tasks using PAC-Bayes bounds.
method Demonstrated a specific 1D linear classification task that PAC-Bayes cannot analyze.
result PAC-Bayes framework cannot prove learnability of simple 1D linear classification tasks.
New algorithm optimizes PAC-Bayes bound without surrogate loss.
problem Mismatch between optimisation objective and generalisation bound in stochastic neural networks.
method Proposes a novel training algorithm that optimizes the PAC-Bayesian bound directly.
result Empirical results show improved performance over existing PAC-Bayesian training methods.
Introduces PAC-Bayes bounds for understanding learning procedures.
problem Understanding the generalization ability of learning procedures.
method PAC-Bayesian bounds and their applications to neural networks.
result Simplified version of localization technique described.
PAC-Bayes bound requires prior to place mass on high-performing predictors.
problem Explaining generalization in machine learning.
method Analyzing necessary conditions for PAC-Bayes bounds to provide meaningful generalization guarantees.
result Achieving a target generalisation level requires the prior to place sufficient mass on high-performing predictors.
New method reduces computational cost for estimating PAC-Bayes bounds.
problem High computational cost in estimating PAC-Bayes bounds.
method General alternative method that makes computational savings.
result Reduces computational cost on the order of the dataset size.
New algorithms reduce communication costs in collaborative learning.
problem Reducing communication costs in collaborative learning.
method Distributed boosting and adaptation to classification noise.
result Communication-efficient algorithms for collaborative PAC learning robust to noise.
Paper develops PAC verification for hypothesis classes and statistical algorithms.
problem Verifying machine learning models interactively.
method Develops interactive proof for PAC verification, proves lower bounds, and introduces a generalization.
result Improved protocol for verifying unions of intervals and statistical query algorithms.