Research map / Reinforcement learning / MDPs and planning
MetaCURL: Non-stationary Concave Utility Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces MetaCURL, a sleeping-expert meta-algorithm over restarted Greedy MD-CURL instances that gives the first dynamic-regret bound for online concave utility RL in non-stationary MDPs with adversarial losses and non-stationary transition noise, without prior knowledge of non-stationarity.
Problem
Online concave utility reinforcement learning (CURL) in episodic loop-free MDPs whose losses (adversarial) and transition kernels change over time, where the learner must minimize dynamic regret without knowing the degree of non-stationarity.
Approach
Runs multiple black-box CURL instances started at different episodes and with different learning rates, aggregated via sleeping exponentially weighted average over state-action distributions; transition kernel is estimated online with a second layer of sleeping experts using the known dynamics and observed external noise, avoiding exploration.
Key results
- MetaCURL achieves dynamic regret of order Õ(sqrt(Δ^{π*} T) + min{sqrt(Δ^p_∞ T), T^{2/3}(Δ^p)^{1/3}}) with high probability, without prior knowledge of MDP changes.
- Under partial information (transition uncertainty only from external noise), the bound handles fully adversarial losses, improving the policy-variation dependency to sqrt(Δ^{π*} T) from (Δ^{π*})^{1/3} T^{2/3}.
- Greedy MD-CURL is shown to achieve the first dynamic regret bound for a CURL algorithm, serving as the black-box baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MetaCURL to handle changing transition kernels without prior knowledge of non-stationarity | CURL with non-stationary transitions and adversarial losses · Non-stationary CURL | dynamic regret | Helped |
| Compare against policy sequences with variation measured by Δ^{π*} | MetaCURL · Non-stationary CURL | dynamic regret dependency on policy variation: \sqrt{\Delta^{\pi^*} T} instead of (\Delta^{\pi^*})^{1/3} T^{2/3} | Helped |
| Use MetaCURL rather than the SoTA in RL | Non-stationary RL comparison · Non-stationary RL | dynamic regret | Mixed |
Limitations
- Assumes transition uncertainty comes only from external noise independent of agent state-action pairs, with known dynamics g_n.
- Meta-algorithm multiplies computational cost by T x |Lambda| with naive interval choice.
- No exploration: does not handle unknown transition structure requiring full exploration.
Experimental setup
Metrics: dynamic regret
Baselines: Greedy MD-CURL UCRL-based non-stationary RL methods
Builds on: Greedy MD-CURL exponentially weighted average (Hedge) sleeping experts restarted black-box online learning
Closest papers by meaning
- Online Episodic Convex Reinforcement Learning (ICML 2025 · similarity 0.92)
- NeoRL: Efficient Exploration for Nonepisodic RL (NeurIPS 2024 · similarity 0.89)
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.89)
- SOMBRL: Scalable and Optimistic Model-Based RL (NeurIPS 2025 · similarity 0.88)
- Optimal Dynamic Regret by Transformers for Non-Stationary Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.