Built independently by an author, for readers. Read the story and support ChapterPal
ChapterPal Logo
Log inSign up

keyword

logarithmic regret

Logarithmic regret is a performance guarantee in online learning and reinforcement learning where the cumulative difference between the performance of an optimal decision strategy with full information and that of a learning algorithm grows only logarithmically relative to the total number of time steps or learning episodes. In sequential decision-making problems, regret measures the accumulated loss incurred while gathering data, estimating unknown parameters, and exploring uncertain actions. A logarithmic regret bound indicates that the algorithm quickly identifies near-optimal actions, causing the average suboptimality per decision step to diminish rapidly toward zero as the time horizon expands. This scaling represents a standard benchmark for asymptotic optimality in many stationary learning environments, reflecting an efficient balance between exploring new actions and exploiting current knowledge.

1 item

Logarithmic Regret for Episodic Continuous-Time Linear-Quadratic Reinforcement Learning over a Finite-Time Horizon

Logarithmic Regret for Episodic Continuous-Time Linear-Quadratic Reinforcement Learning over a Finite-Time Horizon

Matteo Basei, Xin Guo, Anran Hu, Yufei Zhang

OrganizationsDepartment of Industrial Engineering and Operations ResearchÉlectricité de FranceMathematical InstituteUniversity of California BerkeleyUniversity of Oxford

Why you should read this

Establishes the first near-logarithmic regret bounds for episodic continuous-time linear-quadratic reinforcement learning with unknown dynamics, providing both theoretical guarantees via Riccati differential equation analysis and a practical discrete-time implementation that quantifies the impact of discretization stepsizes.

We study finite-time horizon continuous-time linear-quadratic reinforcement learning problems in an episodic setting, where both the state and control coefficients are unknown to the controller. We first propose a least-squares algorithm based on continuous-time observations and controls, and establish a logarithmic regret bound of magnitude O((ln M)(ln ln M)), with M being the number of learning episodes. The analysis consists of two components: perturbation analysis, which exploits the regularity and robustness of the associated Riccati differential equation; and parameter estimation error, which relies on sub-exponential properties of continuous-time least-squares estimators. We further propose a practically implementable least-squares algorithm based on discrete-time observations and piecewise constant controls, which achieves similar logarithmic regret with an additional term depending explicitly on the time stepsizes used in the algorithm.

Added

2026-10-03