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

count % of corpus

22 results for “Horizon-Free”

Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcs.LG

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.

reinforcement learning horizon-free instance-dependent regret bounds general function approximation

2023-12-07abs ↗pdf ↗

Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscs.LG

New algorithm for RL with horizon-free reward-free exploration for linear MDPs.

problem Reward-free reinforcement learning with long planning horizons.

method Uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward and moment estimator.

result Horizon-free sample complexity of

O(d^2\varepsilon^{-2})

for finding an

\varepsilon

-optimal policy.

reinforcement learning reward-free horizon-free linear MDPs value-targeted regression

2023-03-17abs ↗pdf ↗

Nearly Horizon-Free Offline Reinforcement Learningstat.ML

New method achieves nearly horizon-free offline reinforcement learning for tabular and linear MDPs.

problem Achieving efficient reinforcement learning without knowing the horizon.

method Simple recursion-based method to bound total variance in offline scenarios.

result Nearly horizon-free sample complexity bounds for offline policy evaluation and optimization.

reinforcement learning offline learning Markov Decision Processes horizon-free sample complexity

2021-03-25abs ↗pdf ↗

Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscs.LG

Efficient RL for linear MDPs with unknown transitions.

problem Long planning horizons and unknown state transitions in linear mixture MDPs.

method Horizon-free algorithm using weighted least squares with variance and uncertainty awareness.

result Achieves optimal regret up to logarithmic factors.

Reinforcement Learning Horizon-Free Linear Mixture MDPs Weighted Least Squares Regret Minimization

2022-05-23abs ↗pdf ↗

Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscs.LG

New algorithm tackles adversarial RL without horizon constraints.

problem Adversarial reinforcement learning with unknown transition kernel.

method Uses weighted least square estimator and occupancy measure for policy search.

result Achieves near-optimal regret bound of

O(\sqrt{K})

Reinforcement Learning Adversarial Horizon-free Policy Search Regret Bound

2023-05-15abs ↗pdf ↗

Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPsstat.ML

Significant improvements in regret analysis for adaptive online learning problems.

problem Exploiting low variance in online learning problems without known variances.

method Novel peeling-based regret analysis leveraging elliptical potential `count` lemma.

result Significant improvements in regret bounds for linear bandits and linear mixture MDPs.

online learning regret analysis variance-adaptive linear bandits linear mixture MDPs

2021-11-05abs ↗pdf ↗

Regret Analysis of the Anytime Optimally Confident UCB Algorithmcs.LG

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…

2016-03-29abs ↗pdf ↗

Anytime Pretraining: Horizon-Free Learning-Rate Schedules with Weight Averagingcs.LG

The study introduces anytime learning schedules for large language models without fixed horizons.

problem Training large language models without knowing the total training horizon.

method Theoretical analysis and weight averaging to create anytime learning schedules.

result Theoretical and empirical evidence shows that weight averaging with simple step sizes can achieve comparable final loss to well-tuned cosine schedules.

language models continual learning weight averaging stochastic gradient descent learning rate schedules

2026-02-03abs ↗pdf ↗

Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycs.LG

New algorithm reduces regret for linear bandits with unknown noise variance.

problem Finding optimal actions in linear bandits with varying noise variance.

method Adaptive algorithm with Freedman-type concentration inequality and multi-layer structure.

result Achieves

ilde{O}(d \sqrt{\sum_{k = 1}^K σ_k^2} + d)

regret for linear bandits.

Linear Bandits Adaptive Algorithms Variance-Dependent Regret Freedman-type Inequality Multi-Layer Structure

2023-02-21abs ↗pdf ↗

Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcs.LG

Study shows hard sample complexity for learning optimal policies in stochastic shortest path problems.

problem Learning optimal policies in stochastic shortest path problems.

method Analyzes sample complexity with and without generative models, derives lower and upper bounds.

result Proves sample complexity bounds and impossibility of horizon-free regret in SSPs.

Stochastic Shortest Path Sample Complexity Optimal Policy Regret Generative Model

2022-10-10abs ↗pdf ↗

Behavior Cloning is Not All You Need: The Optimality of On-Policy Distillation for Noisy Expert Feedbackcs.LG

New findings explain why online methods outperform offline methods in noisy expert feedback settings.

problem The challenge of learning from imperfect expert feedback in sequential decision-making systems.

method Introduced a noisy expert model and a novel variant of on-policy distillation (OPD) to address the gap between offline and online imitation learning.

result Online interaction with a noisy expert via OPD enables polynomial dependence on the horizon, unlike offline methods which require exponential growth in sample complexity.

Imitation Learning On-Policy Distillation Noisy Expert Feedback Language Model Training Sequential Decision-Making

2026-06-29abs ↗pdf ↗

Towards Weaker Variance Assumptions for Stochastic Optimizationmath.OC

The paper relaxes assumptions for analyzing stochastic optimization algorithms.

problem Analyzing the convergence of stochastic gradient algorithms under weaker variance assumptions.

method Building on and extending a connection to the Halpern iteration, the paper analyzes algorithms for convex nonsmooth optimization and min-max problems.

result Rates for optimality measures are obtained without requiring boundedness of the feasible set for problems beyond simple constrained optimization.

stochastic optimization variance assumptions Halpern iteration convex nonsmooth optimization min-max problems

2025-04-14abs ↗pdf ↗

Anytime Training with Schedule-Free Spectral Optimizationcs.LG

New optimizer SF-NorMuon matches tuned AdamW across various horizons.

problem Fixed learning-rate schedules in neural network training lead to strong path dependence and costly re-tuning.

method Schedule-Free Spectral Optimization (SF-NorMuon)

result SF-NorMuon outperforms tuned AdamW on 125M and 772M parameter models across different horizons.

Neural Networks Optimization Learning Rate Schedule-Free Spectral Dynamics

2026-05-21abs ↗pdf ↗

The Cost of Learning Under Multiple Change Pointsstat.ML

New algorithms detect and react to multiple change points in online learning.

problem Learning under multiple change points in environments with unknown and frequent shifts.

method Proposed Anytime Tracking CUSUM (ATC) algorithms that balance detection of significant shifts.

result Properly tuned ATC algorithms achieve nearly minimax-optimal performance.

online learning multiple change points CUSUM regret minimization information theory

2026-02-11abs ↗pdf ↗

WSqD: A Horizon-Free Learning Rate Schedule for Large Model Trainingcs.LG

WSqD extends learning rate schedules for large model training without fixed horizons.

problem Fixed learning rate schedules limit training horizon extension.

method WSqD replaces constant stable phase with a shifted inverse-square-root base, retaining linear cooldown.

result WSqD achieves minimax-optimal convergence rate and horizon-independence.

learning rate schedules horizon extension stochastic convex optimization last-iterate convergence language-model pretraining

2026-07-12abs ↗pdf ↗

MuonEq: Balancing Before Orthogonalization with Lightweight Equilibrationcs.LG

MuonEq improves training of matrix-valued parameters by rebalancing momentum before orthogonalization.

problem Training matrix-valued parameters with orthogonalized-update optimizers like Muon.

method MuonEq introduces three lightweight pre-orthogonalization equilibration schemes: two-sided row/column normalization (RC), row normalization (R), and column normalization (C).

result Row/column normalization acts as a zeroth-order surrogate for whitening and improves the geometry seen by orthogonalization.

Muon orthogonalization matrix-valued parameters pre-orthogonalization rebalancing

2026-03-30abs ↗pdf ↗

Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learningcs.LG

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

1000 \cdot (\frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon})

private online learning stochastic decision-theoretic pure differential privacy regret minimization entropy-potential argument

2026-05-27abs ↗pdf ↗

User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientmath.ST

In this paper, we study the problem of sampling from a given probability density function that is known to be smooth and strongly log-concave. We analyze several methods of approximate sampling based on discretizations of the (highly overdamped) Langevin diffusion and establish guarantees on its error measured in the W…

2017-09-29abs ↗pdf ↗

Fast Spawn\&Prune (FS\&P): Global convergence of stochastic conic particle gradient descent via birth/death processmath.OC

FS&P uses birth-death process to ensure global convergence of stochastic conic particle gradient descent.

problem Global optimization of non-convex objective functions over measure space.

method Introduces Fast Spawn\&Prune (FS\&P) combining CPGD with birth-death process.

result First theoretical guarantee of global convergence for discrete-time stochastic algorithms.

Global Optimization Conic Particle Gradient Descent Birth-Death Process Continuous Sparse Regression Excess Risk

2026-05-19abs ↗pdf ↗

Waiting to Borrow From a 457(b) Planecon.GN

Optimal timing for borrowing from a 457(b) plan to maximize returns.

problem Deciding the best time to borrow from a tax-advantaged retirement account.

method Formulated and solved the optimal stopping problem for a loan from a 457(b) plan.

result Derived cutoff rules for optimal loan control, showing how to wait until a certain amount of money is accumulated.

optimal stopping 457(b) plan tax-advantaged retirement loan capital growth

2021-07-09abs ↗pdf ↗

Signed Compression Progress on a Sealed Audit is Goodhart-Resistantcs.LG

Signed compression progress on a sealed audit is goodhart-resistant.

problem Intrinsic motivation for agents to improve their world models by compressing experience.

method Rewarding agents for the signed decrease of a fixed sealed-audit loss.

result Cumulative reward telescopes exactly to endpoint audit improvement, preventing infinite reward push while true audit performance stagnates.

compression audit intrinsic motivation goodhart resistance

2026-06-09abs ↗pdf ↗

Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcs.LG

New algorithm reduces offline RL sample complexity for MDPs.

problem Learning optimal policies from offline data in unknown MDPs.

method Adaptive Pessimistic Value Iteration (APVI) algorithm.

result Suboptimality bound nearly matches theoretical limits.

offline reinforcement learning Markov Decision Process value iteration sample complexity pessimism

2021-10-17abs ↗pdf ↗