Vroom optimizes in unpredictable conditions without derivatives.
problem Optimizing in non-stationary, adversarial environments.
method Zeroth-order online learning with vanishing regret.
result Achieves favorable rates in stochastic settings.
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,742 papers · 148 categories
Trend · papers per month
48 results for “order optimal regret”
Study noise-free kernel bandits, finding upper bounds on regret.
problem Optimizing unknown functions without noise.
method Upper bounds on regret for noise-free kernel-based bandits.
result No order optimal regret bounds are established, conjecture on optimal bound.
Balances the regret of different algorithms in bandit and RL problems.
problem Model selection in bandit and reinforcement learning.
method Estimates and balances the empirical regrets of algorithms.
result Achieves near-optimal regret compared to the optimal base algorithm.
New algorithms reduce regret in online MDPs by adapting to data and variance.
problem Adapting to both adversarial and stochastic environments in online MDPs.
method Develops algorithms based on global optimization and policy optimization, using optimistic follow-the-regularized-leader with log-barrier regularization.
result Achieves refined data-dependent and variance-dependent regret bounds.
New algorithm reduces regret in infinite MDPs with optimal variance-dependent bounds.
problem Infinite horizon MDPs lack optimal algorithms with low regret.
method Developed a UCB-style algorithm for average-reward and γ-regret.
result Achieved optimal variance-dependent regret bounds for both objectives.
A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancestat.ML
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.
New algorithm reduces regret in bandit optimization for high-dimensional data.
problem Optimizing decisions in uncertain environments with high-dimensional data.
method Inspired by online Newton step, proposes a simple and efficient BCO algorithm.
result Achieves optimal regret bounds for -convex functions.
Bandit algorithms have been predominantly analyzed in the convex setting with function-value based stationary regret as the performance measure. In this paper, motivated by online reinforcement learning problems, we propose and analyze bandit algorithms for both general and structured nonconvex problems with nonstation…
We demonstrate that, in the classical non-stochastic regret minimization problem with decisions, gains and losses to be respectively maximized or minimized are fundamentally different. Indeed, by considering the additional sparsity assumption (at each stage, at most decisions incur a nonzero outcome), we derive…
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.
GN algorithm solves batched bandit for nondegenerate functions near-optimally.
problem Batched bandit learning for nondegenerate functions.
method Introduces Geometric Narrowing (GN) algorithm with a regret bound and batches.
result GN achieves near optimal regret with minimal number of batches.
New RL method handles large state-action spaces with complex models.
problem Complex models and large state-action spaces in reinforcement learning.
method π-KRVI, an optimistic modification of least-squares value iteration using kernel ridge regression.
result First order-optimal regret guarantees under general settings, improving over state of the art.
Unified framework for analyzing online convex optimization across various settings.
problem Analyzing online convex optimization in different settings and feedback types.
method Unified framework allowing systematic proposal and analysis of meta-algorithms.
result Comparable regret bounds for various feedback types and adversary types.
Optimal simple regret bound for Gaussian Process bandits.
problem Sequential optimization of expensive-to-evaluate functions.
method Proved a bound on simple regret for pure exploration algorithms.
result Order optimal bound on simple regret for Gaussian Process bandits.
New algorithm reduces regret in stochastic bandit convex optimization.
problem Optimizing decisions in uncertain environments with convex losses.
method Introduces a second-order method for zeroth-order stochastic convex bandits.
result Regret bound of .
New algorithm achieves data-dependent regret bounds in MDPs with unknown transitions.
problem Achieving best-of-both-worlds guarantees with data-dependent regret bounds in MDPs with unknown transitions.
method Optimistic follow-the-regularized-leader algorithm with new optimistic Q-function estimators and transition bonus.
result First-order, second-order, and path-length bounds with polylog(T) regret in the stochastic regime.
Paper analyzes algorithms for nonstationary saddle-point optimization problems.
problem Nonstationary saddle-point optimization problems in game theory, reinforcement learning, and machine learning.
method Proposes extragradient and Frank-Wolfe algorithms for online and bandit settings.
result Establishes sub-linear regret bounds for the proposed algorithms.
This paper achieves first-order regret bounds in reinforcement learning with large state spaces.
problem Achieving first-order regret bounds in reinforcement learning with large state spaces.
method Developed a novel robust self-normalized concentration bound based on the robust Catoni mean estimator.
result Obtained regret bounds scaling as .
Optimal algorithm for minimizing regret in heavy-tailed bandits.
problem Minimizing regret in stochastic multi-armed bandits with heavy-tailed distributions.
method Proposes an optimal algorithm under the assumption of uniformly bounded moments of order (1+ε).
result Matches the lower bound exactly in the first-order term and provides a finite-time bound on its regret.
Optimal algorithm found for collaborative learning in bandits with optimal regret bounds.
problem Minimizing regret in collaborative multi-agent bandit problems.
method Proposed an algorithm with optimal regret bounds for collaborative multi-agent multi-armed bandit model.
result First algorithm with order optimal regret bounds for collaborative bandit model.
Kernel online convex optimization (KOCO) is a framework combining the expressiveness of non-parametric kernel models with the regret guarantees of online learning. First-order KOCO methods such as functional gradient descent require only time and space per iteration, and, when the only information on t…
We consider -armed stochastic bandits and consider cumulative regret bounds up to time . We are interested in strategies achieving simultaneously a distribution-free regret bound of optimal order and a distribution-dependent regret that is asymptotically optimal, that is, matching the lower b…
We study the problem of regret minimization for distributed bandits learning, in which agents work collaboratively to minimize their total regret under the coordination of a central server. Our goal is to design communication protocols with near-optimal regret and little communication cost, which is measured by the…
New framework for decentralized optimization of upper-linearizable functions with improved regret and complexity.
problem Decentralized optimization of upper-linearizable functions with general constraints.
method Decentralized projection-free optimization with upper-linearizable function framework.
result Regret of with communication complexity of and linear optimization calls of .
We consider the adversarial convex bandit problem and we build the first -time algorithm with -regret for this problem. To do so we introduce three new ideas in the derivative-free optimization literature: (i) kernel methods, (ii) a generalization of Bernoulli convolutions, …
Randomized exploration in linear bandits achieves optimal regret bounds.
problem Optimizing exploration in high-dimensional linear bandit problems.
method Analysis of Thompson sampling without forced optimism.
result Randomized exploration algorithms achieve an regret bound in smooth, strongly convex action spaces.
Efficient algorithm for zeroth-order bandit convex optimization with bounds on regret.
problem Optimizing in unknown, noisy environments with limited information.
method Online Newton Method for bandit convex optimization, proving regret bounds.
result Regret bounds for both adversarial and stochastic settings.
We consider stochastic multi-armed bandits where the expected reward is a unimodal function over partially ordered arms. This important class of problems has been recently investigated in (Cope 2009, Yu 2011). The set of arms is either discrete, in which case arms correspond to the vertices of a finite graph whose stru…
New framework for Adam-type algorithms with constant β1, improving regret analysis.
problem Theoretical vs. practical use of Adam and variants with constant β1.
method Proposed a novel framework to derive optimal, data-dependent regret bounds with constant β1.
result Optimal, data-dependent regret bounds with constant β1 are achievable without further assumptions.
The paper sets bounds on how much regret is unavoidable in adaptive LQR with unknown B-matrix.
problem Understanding the limits of adaptive LQR with unknown B-matrix.
method Local asymptotic minimax regret lower bounds using van Trees' inequality and Bellman error representation.
result Logarithmic regret is impossible if the parametrization induces an uninformative optimal policy.
A new metric, Weighted Regret, unifies FDR and power evaluation in online multiple testing.
problem The asymmetric costs of false positives and false negatives in automated pipelines.
method Introducing Weighted Regret and Decoupled-OMT (DOMT) to unify FDR and power evaluation.
result DOMT achieves an order-optimal sublinear mitigation of threshold depletion in bursty environments.
We address the online linear optimization problem with bandit feedback. Our contribution is twofold. First, we provide an algorithm (based on exponential weights) with a regret of order for any finite action set with actions, under the assumption that the instantaneous loss is bounded by 1. This…
New method reduces ensemble size for linear bandits, achieving near optimal regret.
problem Achieving near optimal regret in linear bandits with limited ensemble size.
method Ensemble sampling with a size of order for a -dimensional stochastic linear bandit.
result Regret is at most , improving over linear scaling with .
Improves policy optimization with polylog(T) regret bounds for stochastic losses.
problem Improves theoretical guarantees for policy optimization in stochastic settings.
method Leverages Tsallis and Shannon entropy regularizers for polylog(T) regret, and log-barrier regularizer for adversarial settings.
result Achieves a first-order polylog(T) regret bound for policy optimization in stochastic settings.
Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscs.LG
Algorithm reduces regret in distributed kernel bandits with shared randomness.
problem Minimizing regret in collaborative function maximization.
method Uniform exploration at local agents and shared randomness with central server.
result Achieves optimal regret order with sublinear communication cost.
Study optimizes zero-order strongly convex function minimization with higher order smoothness.
problem Optimizing a strongly convex function with noisy evaluations.
method Randomized approximation of projected gradient descent with smoothing kernel.
result Upper bounds and minimax lower bounds for the algorithm, showing near-optimality.
The problem of distributed learning and channel access is considered in a cognitive network with multiple secondary users. The availability statistics of the channels are initially unknown to the secondary users and are estimated using sensing decisions. There is no explicit information exchange or prior agreement amon…
New algorithm reduces regret in private online learning with optimal gap-dependent rate.
problem Optimal gap-dependent regret rate for private stochastic decision-theoretic online learning.
method Horizon-free pure-DP algorithm with exponential block partitioning and softmax selection.
result Explicit regret bound of .
New algorithm learns optimal policies with minimal memory and time.
problem Learning optimal policies in discounted MDPs with short burn-in time.
method Variance reduction and adaptive policy switching.
result First regret-optimal model-free algorithm with low burn-in time.
Continuous-time algorithms improve online learning performance.
problem Online learning with sequential data and minimizing overall regret.
method Extending discrete-time algorithms to continuous-time models for online linear optimization, adversarial bandit, and adversarial linear bandit.
result Optimal regret bounds are proven for continuous-time settings.
New RL algorithm reduces sample complexity for optimal learning.
problem Achieving optimal learning with minimal samples in RL.
method Early-settled variance reduction method with Q-learning sequences.
result Near-optimal regret achieved with sample size .
We provide the first algorithm for online bandit linear optimization whose regret after T rounds is of order sqrt{Td ln N} on any finite class X of N actions in d dimensions, and of order d*sqrt{T} (up to log factors) when X is infinite. These bounds are not improvable in general. The basic idea utilizes tools from con…
Paper explores rate-preserving reductions between Blackwell approachability and no-regret learning.
problem Tackles rate-preserving reductions between Blackwell approachability and no-regret learning.
method Studies fine-grained reductions and optimal rates of convergence.
result Shows that rate-preserving reductions do not always hold, but provides conditions for when they do.
We study the stochastic multi-armed bandit problem when one knows the value of an optimal arm, as a well as a positive lower bound on the smallest positive gap . We propose a new randomized policy that attains a regret {\em uniformly bounded over time} in this setting. We also prove several lower bound…
New algorithm reduces dynamic regret in time-varying movement costs.
problem Dynamic regret in online convex optimization with time-varying movement costs.
method Introduced a novel algorithm for time-varying movement costs, achieving comparator-adaptive dynamic regret bound.
result Established first comparator-adaptive dynamic regret bound of .
Algorithm optimizes spectrum access for dynamic multi-user environments.
problem Optimizing spectrum access in uncoordinated multi-user environments with potential collisions.
method Stochastic multi-user bandit framework with estimation and allocation phases.
result Order-optimal system-wide regret of for dynamic and static cases.
Algorithm learns to bid optimally in repeated first-price auctions with censored feedback.
problem Learning to bid optimally in repeated first-price auctions with incomplete feedback.
method Developed an algorithm exploiting the specific feedback structure and payoff function of first-price auctions.
result Achieved a near-optimal regret bound for first-price auctions.
New algorithm minimizes expert selection regret in partial bandit feedback.
problem Minimizing expert selection regret in partial bandit feedback.
method Develops a sequential minimax optimal algorithm for a generalized partial monitoring setting.
result Second order regret bounds against a general expert selection sequence.