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.
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.
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.
We introduce a new algorithm for online linear-quadratic control in a known system subject to adversarial disturbances. Existing regret bounds for this setting scale as T \sqrt{T} T unless strong stochastic assumptions are imposed on the disturbance process. We give the first algorithm with logarithmic regret for arbitra…
We study the problem of regret minimization in partially observable linear quadratic control systems when the model dynamics are unknown a priori. We propose ExpCommit, an explore-then-commit algorithm that learns the model Markov parameters and then follows the principle of optimism in the face of uncertainty to desig…
Meta-learning control algorithm with finite-time guarantees for unknown systems.
problem Online control of unknown linear systems with constraints.
method Provable regret guarantees for an iterative control algorithm.
result Regret bounds of O ( T 3 / 4 ) O(T^{3/4}) O ( T 3/4 ) for controller cost and constraint violation. 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.
TSAC achieves optimal frequentist regret in adaptive control of LQRs.
problem Adaptive control of stabilizable linear-quadratic regulators with unknown dynamics.
method Thompson Sampling (TS) for adaptive control of LQRs, with a novel early exploration strategy.
result Achieves i l d e O ( T ) ilde O(\sqrt{T}) i l d e O ( T ) regret, optimal for multidimensional systems. We consider the problem of controlling a possibly unknown linear dynamical system with adversarial perturbations, adversarially chosen convex loss functions, and partially observed states, known as non-stochastic control. We introduce a controller parametrization based on the denoised observations, and prove that apply…
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 O ( T ) O(\sqrt{T}) O ( T ) regret bound for episodic settings. We consider the exploration-exploitation tradeoff in linear quadratic (LQ) control problems, where the state dynamics is linear and the cost function is quadratic in states and controls. We analyze the regret of Thompson sampling (TS) (a.k.a. posterior-sampling for reinforcement learning) in the frequentist setting, i.…
New algorithm achieves optimal regret in non-stochastic control, showing stochasticity is not beneficial.
problem Achieving optimal control in non-stochastic systems with adversarial noise.
method Novel online Newton step algorithm adapted to adversarial disturbances, using policy regret bounds.
result Optimal O ~ ( T ) \widetilde{\mathcal{O}}(\sqrt{T}) O ( T ) regret achieved in unknown dynamics, p o l y ( log T ) \mathrm{poly}(\log T) poly ( log T ) regret in known dynamics. PCGS-TF uses a Transformer to adaptively control expert switching in non-stationary environments.
problem Static regret is insufficient for strictly online prediction in non-stationary settings.
method Policy-Controlled Generalized Share (PCGS) with a Transformer as an update controller.
result PCGS-TF achieves the lowest dynamic regret in non-stationary families and expert pools.
Safe RL in linear systems achieves T \sqrt{T} T -regret.
problem Efficiently learning in safety-constrained online reinforcement learning.
method Study of linear quadratic regulator with safety constraints.
result First safe algorithm with i l d e O T ( T ) ilde{O}_T(\sqrt{T}) i l d e O T ( T ) -regret. The study sets limits on how well systems can be controlled adaptively.
problem Learning to control unknown linear Gaussian systems with quadratic costs.
method Combining ideas from experiment design, estimation theory, and perturbation bounds of information matrices.
result Regret lower bounds of the order of T \sqrt{T} T in the time horizon T T T accurately capture control-theoretic parameters. New algorithm minimizes regret in unknown LQ control systems.
problem Online learning in Linear Quadratic Control systems with unknown matrices.
method Developed an online learning algorithm with guarantees on expected regret.
result Upper bounds on regret are minimal and match existing lower bounds.
AdaptOn achieves logarithmic regret in adaptive control of unknown partially observable linear systems.
problem Adaptive control in partially observable linear dynamical systems.
method AdaptOn algorithm that estimates system dynamics through online learning and gradient descent.
result AdaptOn achieves a logarithmic regret bound of polylog(T) after T steps.
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…
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.
GP-PSRL achieves sublinear regret for continuous control with unbounded state space.
problem Analyzing regret bounds for GP-PSRL in continuous control with unbounded state space.
method Recursive application of Borell-Tsirelson-Ibragimov-Sudakov inequality and chaining method.
result Sublinear regret bound of O ~ ( H γ T T ) \widetilde{\mathcal{O}}(H\sqrt{γ_TT}) O ( H γ T T ) for GP-PSRL. The paper improves regret bounds for admission control in queueing systems.
problem Improving regret bounds for admission control in queueing systems.
method Proposes an algorithm inspired by UCRL2 and uses problem structure to bound regret.
result Proves an upper bound on the expected total regret of O ( S log T + m T log T ) O(S\log T + \sqrt{mT \log T}) O ( S log T + m T log T ) . 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…
Optimal algorithm for LQR control with improved regret bound.
problem Nonstochastic control with quadratic losses (LQR control).
method Online algorithm with optimal dynamic regret of i l d e O ( e x t m a x { n 1 / 3 T V ( M 1 : n ) 2 / 3 , 1 } ) ilde{O}( ext{max}\{n^{1/3} \mathcal{TV}(M_{1:n})^{2/3}, 1\}) i l d e O ( e x t ma x { n 1/3 TV ( M 1 : n ) 2/3 , 1 }) . result Improves the best known rate of i l d e O ( n ( T V ( M 1 : n ) + 1 ) ) ilde{O}(\sqrt{n (\mathcal{TV}(M_{1:n})+1)} ) i l d e O ( n ( TV ( M 1 : n ) + 1 ) ) for general convex losses. Paper tackles online control of linear systems with unbounded noise.
problem Online control of linear systems under unbounded noise with unknown convex cost functions.
method Developed an algorithm achieving i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) high-probability regret under unbounded noise, and established O ( m p o l y ( log T ) ) O({
m poly} (\log T)) O ( m p o l y ( log T )) regret bound for strongly convex costs and sub-Gaussian noise. result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) high-probability regret under unbounded noise, and O ( m p o l y ( log T ) ) O({
m poly} (\log T)) O ( m p o l y ( log T )) regret bound for specific noise and cost conditions. Study online control of unknown time-varying systems with negative and positive results.
problem Online control of time-varying systems with unknown dynamics.
method Algorithmic upper bounds and lower bounds for different policy classes.
result Sublinear adaptive regret bounds for Disturbance Response policies.
Logarithmic regret achieved in continuous-time linear-quadratic reinforcement learning.
problem Optimizing control actions in unknown continuous-time systems over a finite time horizon.
method Least-squares algorithm based on continuous-time observations and controls, with perturbation analysis and parameter estimation error analysis.
result Logarithmic regret bound of order O ( ( ln M ) ( ln ln M ) ) O((\ln M)(\ln\ln M)) O (( ln M ) ( ln ln M )) . Designs adaptive controller for networked control systems with wireless data transmission.
problem Adaptive control in networked systems with unreliable wireless channels.
method Upper Confidence Bounds for Networked Control Systems (UCB-NCS) learning rule.
result Non-asymptotic performance guarantees with a regret bound of O(C√T).
Optimal control in changing systems without strong convexity assumptions.
problem Adversarial changes in convex costs for unknown linear systems.
method Non-convex lower confidence bounds and computationally-efficient regret minimization.
result Achieves T \smash{\sqrt{T}} T -regret rate, optimal compared to best stabilizing controller. Study shows certainty equivalent policy minimizes regret in continuous-time systems.
problem Minimizing regret in continuous-time stochastic linear-quadratic systems.
method Theoretical analysis of randomized certainty equivalent policy.
result Establishes square-root of time regret bounds and linear scaling with parameters.
Study shows how to learn optimal policies quickly in stochastic control problems.
problem Learning optimal policies in large, continuous state and action spaces with limited data.
method Analyzes three geometric exponents to quantify fast policy regret convergence.
result Shows that fast policy regret convergence is induced by specific geometric structures.
LqgOpt learns optimal control in unknown LQG systems with minimal regret.
problem Adaptive control in partially observable linear quadratic Gaussian systems with unknown dynamics.
method Optimism in the face of uncertainty, predictor state evolution, closed-loop system identification, confidence bounds.
result Proves a regret upper bound of i l d e O ( T ) ilde{\mathcal{O}}(\sqrt{T}) i l d e O ( T ) for LQG systems. We consider the problem of controlling an unknown linear dynamical system in the presence of (nonstochastic) adversarial perturbations and adversarial convex loss functions. In contrast to classical control, the a priori determination of an optimal controller here is hindered by the latter's dependence on the yet unkno…
Efficient algorithm reduces control system regret to sqrt(t).
problem Control of linear quadratic systems with guaranteed anytime performance.
method Combines SDP-based framework with regularization and perturbation mechanisms.
result Achieves anytime regret of order sqrt(t) with explicit dependence on system dimensions.
New control methods for systems with adversarial perturbations.
problem Control systems with adversarial noise.
method Online convex optimization and convex relaxations.
result Low regret policies against adversarial perturbations.
New algorithm controls linear systems with bandit feedback, achieving optimal regret.
problem Controlling linear systems with bandit feedback under adversarial costs.
method Developed a new algorithm for linear control with memory optimization technique.
result Achieved optimal regret growth proportional to square root of time horizon.
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)$ .
This paper tackles adaptive control of unknown Markov jump systems with sample complexity and regret bounds.
problem Adaptive control of unknown Markov jump systems with changing dynamics.
method Identification-based adaptive control using a system identification algorithm and certainty equivalent control.
result The proposed adaptive control scheme achieves O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) regret, improving to O ( p o l y l o g ( T ) ) \mathcal{O}(polylog(T)) O ( p o l y l o g ( T )) with partial knowledge. Efficiently controls unknown linear systems with black-box interactions.
problem Controlling an unknown linear dynamical system from black-box interactions.
method First efficient algorithm with sublinear regret, using robust system identification.
result Resolves open problem on stochastic LQR and black-box LQR control.
New algorithm controls systems with unknown, changing losses.
problem Control systems with adversarial perturbations and unknown loss function.
method Efficient sublinear regret algorithm for bandit convex optimization with memory.
result Achieves efficient control with sublinear regret in the presence of unknown, changing losses.
New Q-learning algorithms reduce regret in inventory control problems.
problem Efficiently learning optimal policies in inventory control problems with limited feedback.
method Proposed Elimination-Based Half-Q-Learning (HQL) and Full-Q-Learning (FQL) algorithms with theoretical regret bounds.
result HQL incurs i l d e O ( H 3 T ) ilde{\mathcal{O}}(H^3\sqrt{ T}) i l d e O ( H 3 T ) regret, FQL incurs i l d e O ( H 2 T ) ilde{\mathcal{O}}(H^2\sqrt{ T}) i l d e O ( H 2 T ) regret, independent of state and action space sizes. New bounds for adaptive control in high dimensions without fixed state space.
problem Adaptive control of linear systems in high or infinite dimensions.
method Novel perturbation bound for certainty equivalence, scaling with prediction error.
result First regret bounds for LQR in infinite dimensional systems, independent of ambient dimension.
New model-free algorithm achieves similar LQR regret guarantees.
problem Model-free control of linear dynamical systems under quadratic costs.
method Online policy gradient scheme with policy space cost analysis.
result Achieves regret scaling with √T, matching model-based methods.
The paper tackles learning to control systems with unknown parameters using Brownian noise.
problem Learning to control systems with unknown parameters.
method Proposes algorithms based on moving empirical averages and integrates statistical methods with stochastic control theory.
result Achieves a logarithmic expected regret rate.
We consider the problem of online adaptive control of the linear quadratic regulator, where the true system parameters are unknown. We prove new upper and lower bounds demonstrating that the optimal regret scales as Θ ~ ( d u 2 d x T ) \widetildeΘ({\sqrt{d_{\mathbf{u}}^2 d_{\mathbf{x}} T}}) Θ ( d u 2 d x T ) , where T T T is the number of time steps, $d_{\m…
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 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.
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 i l d e O ( T V T ∨ log T ) ilde O(\sqrt{TV_T} \vee \log T) i l d e O ( T V T ∨ log T ) and i l d e O ( d T V T ∨ d log T ) ilde O(\sqrt{dTV_T} \vee d\log T) i l d e O ( d T V T ∨ d log T ) dynamic regret for strongly convex and exp-concave losses, respectively. Efficient algorithm for unknown linear systems with convex costs.
problem Controlling an unknown linear system with stochastic convex costs.
method Optimism in the Face of Uncertainty paradigm.
result Achieves optimal T \sqrt{T} T regret-rate.