We consider the problem of online prediction in a marginally stable linear dynamical system subject to bounded adversarial or (non-isotropic) stochastic perturbations. This poses two challenges. Firstly, the system is in general unidentifiable, so recent and classical results on parameter recovery do not apply. Secondl…
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 “Polynomial Regret”
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradoxstat.ML
Thompson Sampling shows polynomial regret for combinatorial semi-bandits with subgaussian rewards.
problem Finding optimal solutions in combinatorial semi-bandits with suboptimal sampling.
method Proposes Thompson Sampling with polynomial regret for linear combinatorial semi-bandits.
result Demonstrates 'mismatched sampling paradox' where knowing distributions can lead to worse performance.
New algorithm reduces dynamic regret for noisy gradient feedback with piecewise polynomial comparators.
problem Online estimation of piecewise polynomial trends with noisy feedback.
method Introduces variational constraint for piecewise polynomial comparators, designs adaptive algorithm.
result Achieves nearly optimal dynamic regret of $ ilde{O}(n^{ rac{1}{2k+3}}C_n^{ rac{2}{2k+3}})$.
Universal preconditioning reduces sequential prediction regret.
problem Improving sequential prediction performance.
method Convolve target sequence with orthogonal polynomial coefficients.
result First sublinear and hidden-dimension-independent regret bounds.
We study the decades-old problem of online portfolio management and propose the first algorithm with logarithmic regret that is not based on Cover's Universal Portfolio algorithm and admits much faster implementation. Specifically Universal Portfolio enjoys optimal regret for financial instrum…
New study reveals a polynomial penalty for adapting to unknown margin parameters in batched nonparametric bandits.
problem Adapting to an unknown margin parameter in batched nonparametric bandits.
method Introduces the regret inflation criterion and develops RoBIN algorithm to achieve optimal regret inflation.
result The optimal regret inflation grows polynomially with the horizon T, characterized by a convex optimization problem.
Algorithm reduces control regret for unknown systems.
problem Minimizing control regret for unknown linear systems.
method Novel geometric exploration strategy and polynomial-time algorithms.
result First polynomial-time algorithms with optimal regret bounds.
Improved RL algorithm stabilizes unknown linear systems with polynomial regret.
problem Learning and stabilizing unknown linear dynamical systems.
method Proposes an algorithm with an improved exploration strategy for fast stabilization.
result Achieves regret after time steps.
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.
GP-UCB performs suboptimally under certain conditions, as shown by a new regret lower bound.
problem The suboptimality of GP-UCB under polynomial effective optimism.
method Analysis of effective optimism level and new regret lower bound.
result GP-UCB is not minimax optimal under polynomial growth of effective optimism.
Paper develops algorithms for PWA systems with polynomial regret.
problem Learning in piecewise affine systems due to discontinuities.
method Smoothed online learning framework applied to PWA systems.
result First algorithms with polynomial regret in PWA systems.
Extends algorithms for computing -equilibria to higher polynomial dimensions.
problem Computing -equilibria for higher-dimensional polynomial deviations.
method Nested application of the EAH algorithm to handle polynomial dimension.
result Efficient algorithms for computing -approximate -equilibria and online -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 with probability .
We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of objects is chosen, and a linear cost associated with the chosen subset is incurred. To measure the performance of our algorithms, we use the notion of regret which is the difference between the to…
Adaptive-treed banditsmath.ST
We describe a novel algorithm for noisy global optimisation and continuum-armed bandits, with good convergence properties over any continuous reward function having finitely many polynomial maxima. Over such functions, our algorithm achieves square-root regret in bandits, and inverse-square-root error in optimisation, …
We consider Markov Decision Processes (MDPs) where the rewards are unknown and may change in an adversarial manner. We provide an algorithm that achieves state-of-the-art regret bound of , where is the state space, is the action space, is the mixing time of the MDP, and $…
We consider adaptive control of the Linear Quadratic Regulator (LQR), where an unknown linear system is controlled subject to quadratic costs. Leveraging recent developments in the estimation of linear systems and in robust controller synthesis, we present the first provably polynomial time algorithm that provides high…
Paper proposes an efficient RL algorithm for discounted MDPs using feature mapping.
problem Efficient reinforcement learning for large state and action spaces.
method Uses feature mapping to represent states and actions in a low-dimensional space, proposing a novel algorithm with polynomial regret bound.
result Achieves a regret bound, near-optimal up to a factor.
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.
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.
New algorithm achieves online calibration in polynomial time for high-dimensional problems.
problem Online calibration of high-dimensional probability distributions over many days.
method Randomly selects among sub-forecasters, each predicting empirical outcome frequency over recent time windows.
result Achieves asymptotically calibrated strategies after polynomial number of rounds, resolving open questions.
New method achieves near-optimal regret without simulator.
problem Adversarial linear contextual bandits with unknown loss vectors.
method Near-optimally reduces regret to sqrt(T) without simulator.
result Achieves regret of sqrt(T) without simulator, improving existing methods.
The experimental design problem concerns the selection of k points from a potentially large design pool of p-dimensional vectors, so as to maximize the statistical efficiency regressed on the selected k design points. Statistical efficiency is measured by optimality criteria, including A(verage), D(eterminant), T(race)…
The paper improves bounds on regret in Gaussian process bandits.
problem Sequential optimization of expensive, possibly non-convex functions with noisy feedback.
method Analyzes maximal information gain and decay rates of GP kernel eigenvalues to improve regret bounds.
result General bounds on maximal information gain and improved regret bounds for various settings, including Matérn kernels.
We consider online algorithms under both the competitive ratio criteria and the regret minimization one. Our main goal is to build a unified methodology that would be able to guarantee both criteria simultaneously. For a general class of online algorithms, namely any Metrical Task System (MTS), we show that one can sim…
Unified analysis of kernel-based and locally adaptive bandit optimization methods.
problem Performance of bandit optimization algorithms in RKHS functions.
method Investigates the relationship between kernel regularity and algorithmic performance, characterizing spectral properties of various kernels.
result Unified framework for analyzing kernel-based and locally adaptive bandit algorithms, deriving explicit regret bounds.
New research shows no-regret learning is impossible in Markov games under certain assumptions.
problem Achieving no-regret learning in decentralized Markov games.
method Novel application of aggregation techniques from online learning to prove lower bounds.
result No polynomial-time algorithm exists for independent no-regret learning in general-sum Markov games.
New algorithms achieve better regret bounds for online classification with relaxed benchmarks.
problem Competing with worst-case optimal binary loss in online classification.
method Comparing against predictors robust to small input perturbations, performing well under Gaussian smoothing, or maintaining a prescribed output margin.
result Regret guarantees depend only on VC dimension and instance space complexity, with an dependence on the generalized margin.
The paper tackles Nash-regret minimization in congestion games with bandit feedback.
problem Minimizing Nash-regret in congestion games with bandit feedback.
method Proposes centralized and decentralized algorithms for congestion games with bandit feedback, and a centralized algorithm for Markov congestion games.
result Sample complexity depends polynomially on the number of players and facilities, not the size of the action set.
Study sparsity benefits in infinite feature contextual bandits.
problem Minimizing regret in infinite feature contextual bandits.
method Novel reduction to multi-armed bandits, Feel-Good Thompson Sampling algorithm.
result Regret bounds match lower bounds up to logarithmic factors, logarithmic dependence on effective features.
Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum Statescs.LG
New algorithm reduces regret in online portfolio and quantum state learning.
problem Efficiently learning portfolios and quantum states online with minimal regret.
method BISONS algorithm for online portfolio selection, SCHRODINGER'S BISONS for quantum states, with polylogarithmic regret.
result First efficient algorithm with polylogarithmic regret for online portfolio selection and quantum states.
Study non-linear combinatorial bandits with polynomial rewards, finding significant differences from linear cases.
problem Adversarial combinatorial bandits with general non-linear reward functions.
method Extending existing work on adversarial linear combinatorial bandits, analyzing minimax optimal regret for polynomial and non-polynomial reward functions.
result Minimax optimal regret bounds for adversarial combinatorial bandits with general non-linear reward functions.
New insights into natural exponential families improve regret bounds for bandit problems.
problem Improving regret bounds for bandit problems with subexponential tails.
method Proving self-concordance for natural exponential families and applying to bandits.
result Optimistic algorithms for generalized linear bandits have second-order regret bounds that are free of an exponential dependence on problem parameters.
We present a generalization of the adversarial linear bandits framework, where the underlying losses are kernel functions (with an associated reproducing kernel Hilbert space) rather than linear functions. We study a version of the exponential weights algorithm and bound its regret in this setting. Under conditions on …
Lower bounds on eigenspectrum show rich action spaces force polynomial regret in linear bandits.
problem Understanding the minimum eigenvalue growth in linear bandits with rich action sets.
method Non-asymptotic lower bound on eigenspectrum of design matrix.
result Minimum eigenvalue of expected design matrix grows as for sub-linear regret.
Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Lossescs.LG
Near-logarithmic regret per switch achieved for mixable/exp-concave losses.
problem Online optimization of mixable loss functions with dynamic environments.
method Online mixture framework using static solvers and hyper-expert creations.
result Near-logarithmic regret per switch with sub-polynomial complexity.
Two new algorithms reduce online kernel regression's computational cost while maintaining optimal regret bounds.
problem Trade-off between regret and computational cost in online kernel regression.
method AOGD-ALD and NONS-ALD algorithms dynamically maintain nearly orthogonal basis to approximate kernel mapping and control approximate error.
result Achieves nearly optimal regret bounds at sublinear computational complexity.
New framework analyzes regret in guided diffusion for optimizing structured inputs.
problem Understanding regret behavior in guided-diffusion black-box optimization for structured design problems.
method Developed a certificate-based expected simple-regret framework that avoids assumptions breaking down in modern diffusion BO pipelines.
result Explains how exponential and polynomial convergence can arise from mass lift in near-optimal designs.
In the context of stochastic continuum-armed bandits, we present an algorithm that adapts to the unknown smoothness of the objective function. We exhibit and compute a polynomial cost of adaptation to the H{ö}lder regularity for regret minimization. To do this, we first reconsider the recent lower bound of Locatelli an…
New algorithm optimizes Hölder smooth functions in RKHS with tighter regret bounds.
problem Optimizing Hölder smooth functions in RKHS with bounded norm.
method Proposes a new algorithm ( exttt{LP-GP-UCB}) using Local Polynomial (LP) estimators and multi-scale UCB.
result Derives high probability bounds on simple and cumulative regret, matching optimal performance for SE kernel and uniformly tighter bounds for Matérn kernels.
New method controls linear systems with adversarial disturbances.
problem Controlling linear dynamical systems under adversarial conditions.
method Novel convex relaxation using spectral filters from Hankel matrix eigenvectors.
result Polylogarithmic running time improvement over prior methods.
New algorithm reduces sleeping bandits' regret to O(sqrt(T)).
problem Improving sleeping bandits with stochastic actions and adversarial rewards.
method Inspired by EXP3, new algorithm with regret.
result Achieves regret, improving over existing .
New algorithm reduces pricing error by a factor of T^2/3.
problem Optimal pricing under non-Lipschitz demand with unknown jumps and atoms.
method Conservative-Markdown Redirect-UCB Pricing, combining estimation, probing, and redirection.
result Achieves optimal regret of O(T^2/3), matching lower bounds.
UCRL-WVTR tackles long-term reinforcement learning with general approximations, achieving horizon-free and instance-dependent regret bounds.
problem Long-term reinforcement learning with general function approximations.
method UCRL-WVTR proposes a novel algorithm, UCRL-WVTR, with weighted value-targeted regression and a high-order moment estimator.
result Achieves horizon-free and instance-dependent regret bounds matching minimax lower bounds up to logarithmic factors.
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.
A new pricing controller handles resource constraints to infer target prices effectively.
problem Resource constraints prevent fixed-price inference, leading to support exclusion.
method Formalizes support-exclusion failure, designs a target-aware controller, and uses a realized information clock.
result The controller can certify feasible target bands and log continuous local densities, leading to polynomial rates of inference.
Algorithm finds optimal regularizers for online linear optimization.
problem Finding optimal regularizers to minimize regret in online linear optimization.
method Algorithm takes input sets and outputs an optimal regularizer for FTRL.
result Algorithm guarantees regret within a constant factor of the best possible learning algorithm.
Doubly-Robust Lasso Banditstat.ML
Contextual multi-armed bandit algorithms are widely used in sequential decision tasks such as news article recommendation systems, web page ad placement algorithms, and mobile health. Most of the existing algorithms have regret proportional to a polynomial function of the context dimension, . In many applications ho…