Research map / Bandits and online learning / RL theory and MDPs

Optimal Regret Bounds via Low-Rank Structured Variation in Non-Stationary Reinforcement Learning

NeurIPS 2025 · Bandits and online learning › RL theory and MDPs · approach: Regret bounds with function approximation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes SVUCRL, a UCRL-style algorithm for non-stationary communicating MDPs with low-rank-plus-sparse transition drift, proving a dynamic-regret bound.

Problem

Dynamic regret in non-stationary reinforcement learning where transition dynamics drift over time, with the drift assumed to have a low-rank plus sparse structure.

Approach

Exploits a low-rank-plus-sparse structure in the transition drift to obtain a dynamic-regret bound that depends on structured variation quantities (B_r, B_p, delta_B) rather than only total variation.

Key results

• SVUCRL achieves dynamic-regret bound O~(D_max S sqrt(AT) + D_max sqrt((B_r+B_p) K S T) + D_max delta_B B_p) in non-stationary communicating MDPs with low-rank plus sparse transition drift.

Experimental setup

Metrics: dynamic regret

Builds on: UCRL

Closest papers by meaning

• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (ICML 2020 · similarity 0.91)
• Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (ICML 2021 · similarity 0.91)
• DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.91)
• Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.90)
• Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs (NeurIPS 2024 · similarity 0.90)
• No-Regret Reinforcement Learning in Smooth MDPs (ICML 2024 · similarity 0.89)