Regret minimization is treated as the golden rule in the traditional study of online learning. However, regret minimization algorithms tend to converge to the static optimum, thus being suboptimal for changing environments. To address this limitation, new performance measures, including dynamic regret and adaptive regr…
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 “Dynamic Regret”
New algorithms reduce dynamic regret in non-stationary RL environments.
problem Optimizing policies in environments that change over time.
method POWER and POWER++ algorithms for policy optimization with dynamic regret analysis.
result POWER++ improves dynamic regret by actively adapting to non-stationarity.
In online learning, the dynamic regret metric chooses the reference (optimal) solution that may change over time, while the typical (static) regret metric assumes the reference solution to be constant over the whole time horizon. The dynamic regret metric is particularly interesting for applications such as online reco…
Optimistic Hedge achieves optimal regret bounds in two-player zero-sum games.
problem Achieving optimal regret bounds for optimistic Hedge in two-player zero-sum games.
method Refined regret analysis and optimization problem formulation.
result Optimistic Hedge achieves regret bounds, matching upper and lower bounds.
New algorithm reduces control error in systems with changing dynamics.
problem Online control of systems with time-varying linear dynamics.
method Introduces adaptive regret metric and a novel meta-algorithm.
result First adaptive regret bound for online convex optimization with memory.
Recursive least-squares algorithms often use forgetting factors as a heuristic to adapt to non-stationary data streams. The first contribution of this paper rigorously characterizes the effect of forgetting factors for a class of online Newton algorithms. For exp-concave and strongly convex objectives, the algorithms a…
Reduces dynamic regret to static problem in RKHS.
problem Minimizing cumulative loss in online convex optimization.
method Reduces dynamic regret to static regret problem in RKHS.
result Optimal dynamic regret guarantees for linear losses and new bounds for exp-concave and improper linear regression.
SCaLE tackles dynamic regret in noisy bandit feedback with switching costs.
problem Unbounded metric movement costs in bandit online convex optimization.
method SCaLE algorithm for high-dimensional dynamic quadratic hitting costs and -norm switching costs, with spectral regret analysis.
result First algorithm achieving sub-linear dynamic regret without hitting cost knowledge.
Online learning is a powerful tool for analyzing iterative algorithms. However, the classic adversarial setup sometimes fails to capture certain regularity in online problems in practice. Motivated by this, we establish a new setup, called Continuous Online Learning (COL), where the gradient of online loss function cha…
Improved algorithm for adaptive dueling bandits with near-optimal regret bound.
problem Non-stationary dueling bandits with unknown number of preference changes.
method Elimination-based rescheduling algorithm for adaptive dynamic regret.
result Near-optimal dynamic regret bound.
As a metric to measure the performance of an online method, dynamic regret with switching cost has drawn much attention for online decision making problems. Although the sublinear regret has been provided in many previous researches, we still have little knowledge about the relation between the dynamic regret and the s…
New algorithm reduces dynamic regret without prior function change knowledge.
problem Non-stationary stochastic optimization with bandit feedback.
method Fixed step sizes combined with multi-scale sampling framework.
result Achieves optimal dynamic regret without prior function change knowledge.
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 .
Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Lossescs.LG
New algorithm achieves both static and dynamic regret optimally against an oblivious adversary for deterministic losses.
problem Achieving optimal static and dynamic regret simultaneously in adversarial bandits.
method Extends impossibility result to deterministic losses, uses negative static regret and Blackwell approachability.
result First algorithm achieving optimal static and dynamic regret simultaneously against an oblivious adversary.
New algorithms reduce dynamic regret in online MDPs with changing losses.
problem Online MDPs with adversarial loss changes and known transitions.
method Dynamic regret measure, novel ensemble algorithms for three models.
result Provably optimal dynamic regret bounds for episodic SSP, improved bounds for predictable environments.
Sequential screening and dynamic regret in multi-armed bandits with arriving arms
problem Sequential experimentation with expanding arm set
method UCB-AA with preliminary screening
result Regret bounds depend on arrival process
New algorithms minimize dynamic regret for strongly convex losses.
problem Minimizing dynamic regret for strongly convex losses.
method Developed Strongly Adaptive algorithms exploiting KKT conditions.
result Achieved near optimal dynamic regret of .
Improved dynamic regret analysis for strongly convex and smooth functions.
problem Analyzing dynamic regret for online learning algorithms.
method Improved analysis of the Online Multiple Gradient Descent (OMGD) algorithm.
result Achieved a best-of-three-worlds guarantee for dynamic regret.
Dynamic regret minimization is shown equivalent to static regret minimization for linear losses.
problem Dynamic regret minimization in online convex optimization.
method Equivalence between dynamic and static regret minimization for linear losses.
result Dynamic regret minimization is equivalent to static regret minimization for linear losses.
New algorithms reduce dynamic regret for convex and smooth functions in non-stationary environments.
problem Online convex optimization in non-stationary environments.
method Proposed novel online algorithms exploiting smoothness to reduce dynamic regret.
result Dynamic regret improved to for convex and smooth functions.
Universal online optimization for dynamic environments using uniclass prediction.
problem Online optimization in changing environments with dynamic regret.
method Reduces dynamic online optimization to uniclass prediction problem, allowing control over dynamic regret bounds.
result First paper with state-of-the-art dynamic regret guarantees for general convex cost functions.
New algorithms minimize dynamic regret in non-stationary online learning.
problem Universal dynamic regret minimization under exp-concave and smooth losses.
method Strongly Adaptive algorithms with a path variational based on second order differences of the comparator sequence.
result Achieve a dynamic regret of , optimal modulo dependencies.
New algorithm adapts to unknown demand smoothness for dynamic pricing.
problem Dynamic pricing with unknown Hölder smoothness of demand function.
method Self-similarity condition and adaptive algorithm.
result Adaptive algorithm achieves minimax optimal regret without prior knowledge of smoothness.
Study risk-sensitive reinforcement learning with Lipschitz dynamic risk measures, establishing regret bounds.
problem Risk-sensitive reinforcement learning in Markov decision processes.
method Two model-based algorithms for Lipschitz dynamic risk measures, focusing on regret bounds.
result Upper bounds demonstrate optimal dependencies on actions and episodes, reflecting risk sensitivity vs. sample complexity trade-off.
Unified approach for non-stationary linear bandits with dynamic regret.
problem Non-stationary linear bandits with round-specific feasible actions and drifting reward models.
method Unified misspecification-reduction viewpoint, restarting algorithms with misspecification-dependent regret guarantees.
result Optimal \(T^{2/3}P_T^{1/3}\) dynamic-regret dependence for both linear bandits and contextual linear bandits.
This paper describes a new online convex optimization method which incorporates a family of candidate dynamical models and establishes novel tracking regret bounds that scale with the comparator's deviation from the best dynamical model in this family. Previous online optimization methods are designed to have a total a…
This work focuses on dynamic regret of online convex optimization that compares the performance of online learning to a clairvoyant who knows the sequence of loss functions in advance and hence selects the minimizer of the loss function at each step. By assuming that the clairvoyant moves slowly (i.e., the minimizers c…
Optimal switching regret for all segmentations in online convex optimisation.
problem Non-stationary online convex optimisation problems.
method Developed an efficient algorithm to achieve optimal switching regret on every possible segmentation.
result Achieved asymptotically optimal switching regret on every possible segmentation simultaneously.
Transformers achieve near-optimal dynamic regret in non-stationary reinforcement learning.
problem Understanding and handling non-stationary environments in reinforcement learning.
method Demonstrated that transformers can achieve nearly optimal dynamic regret bounds in non-stationary settings.
result Transformers can approximate and learn strategies for non-stationary environments, matching or outperforming existing expert algorithms.
SA algorithms control dynamic regret in non-stationary settings with strong convexity or exp-concavity.
problem Non-stationary Online Convex Optimization with dynamic regret control.
method Strongly Adaptive (SA) algorithms view dynamic regret as path variation of the comparator sequence.
result SA algorithms achieve and dynamic regret for strongly convex and exp-concave losses, respectively.
New algorithm minimizes worst-case regret in uncertain, time-varying dynamics.
problem Model-based policy learning in uncertain, time-varying dynamics.
method Planning regret metric and iterative algorithm for minimizing it.
result Empirical evidence shows the proposed algorithm outperforms existing methods.
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.
We study optimal regret bounds for control in linear dynamical systems under adversarially changing strongly convex cost functions, given the knowledge of transition dynamics. This includes several well studied and fundamental frameworks such as the Kalman filter and the linear quadratic regulator. State of the art met…
Regret analysis is challenging in Multi-Agent Reinforcement Learning (MARL) primarily due to the dynamical environments and the decentralized information among agents. We attempt to solve this challenge in the context of decentralized learning in multi-agent linear-quadratic (LQ) dynamical systems. We begin with a simp…
Study optimal control in unknown nonlinear systems with near-optimal regret bound.
problem Sequential control in unknown, nonlinear dynamical systems.
method LC^3 algorithm, based on information theory.
result Near-optimal regret bound for episodic settings.
New method reduces dynamic regret for non-stationary bandits.
problem Non-stationary stochastic multi-armed bandit problem with changing optimal arm.
method Proposes a method achieving near-optimal dynamic regret without prior knowledge of changes.
result Achieves dynamic regret.
We consider online forecasting problems for non-convex machine learning models. Forecasting introduces several challenges such as (i) frequent updates are necessary to deal with concept drift issues since the dynamics of the environment change over time, and (ii) the state of the art models are non-convex models. We ad…
New method for online meta-learning reduces dynamic regret in changing environments.
problem Learning new tasks quickly from limited data in dynamic settings.
method Established dynamic regret analysis using generalized adaptive gradient methods.
result Logarithmic local dynamic regret with dependence on total iterations and learner parameters.
Study on learning to predict dynamical systems without assuming their structure.
problem Learning to predict the next state of a dynamical system with unknown evolution function.
method Defined new combinatorial measures to quantify mistake and regret bounds in realizable and agnostic settings.
result In the realizable setting, the number of mistakes can grow arbitrarily with time.
A method to minimize regret in multi-agent control systems with adversarial disturbances.
problem Optimal control of dynamical systems with adversarial disturbances and multiple agents.
method Reduction from online convex optimization to a distributed algorithm for multi-agent control.
result The resulting distributed algorithm has low regret relative to the optimal precomputed joint policy.
Dynamic pricing improves DeFi lending efficiency by reducing regret to logarithmic levels.
problem Static pricing mechanisms in DeFi lending protocols lead to suboptimal welfare and revenue.
method Online learning model for static and dynamic pricing models in DeFi lending.
result Adaptive supply models achieve logarithmic regret, outperforming static models.
New algorithm learns LQR with regret using Langevin dynamics and excitation.
problem Learning LQR with a regret bound.
method Thompson sampling with Langevin dynamics and excitation mechanism.
result Achieved regret bound for LQR learning.
In this paper, we study online convex optimization in dynamic environments, and aim to bound the dynamic regret with respect to any sequence of comparators. Existing work have shown that online gradient descent enjoys an dynamic regret, where is the number of iterations and is the path-le…
Efficient methods reduce projections in non-stationary online learning.
problem Optimizing dynamic and adaptive regret in non-stationary online learning environments.
method Presented efficient methods reducing the number of projections per round from to .
result Reduced number of projections per round from to for optimizing dynamic and adaptive regret.
New algorithm reduces decision switching in dynamic environments.
problem Online learning with memory and non-stationary environments.
method Dynamic policy regret, novel ensemble approach, meta-base decomposition.
result Proves optimal dynamic policy regret for memory length, non-stationarity, and time horizon.
New algorithm reduces dynamic regret for exp-concave losses.
problem Minimizing dynamic regret in online learning with exp-concave losses.
method Integrates KKT conditions to achieve optimal dynamic regret.
result Achieves dynamic regret of .
Dynamic pricing algorithms can work with covariates without i.i.d. assumptions.
problem Dynamic pricing with covariates under a generalized linear demand model.
method UCB and Thompson sampling-based pricing algorithms.
result Achieves an regret upper bound without i.i.d. covariates assumption.
Algorithm minimizes control regret for non-stationary LQR systems.
problem Control of non-stationary LQR systems with unknown dynamics.
method Adaptive non-stationarity detection and OLS estimator with small bias.
result Achieves optimal dynamic regret of $ ilde{\mathcal{O}}\left(V_T^{2/5}T^{3/5}
ight)$.