MetaCURL: Non-stationary Concave Utility Reinforcement Learning

Bianca Marin Moreno, Margaux Brégère, Pierre Gaillard, Nadia Oudjane

Introduction

Reinforcement Learning (RL) has traditionally focused on maximizing the expected sum of rewards in stationary environments. However, real-world applications—ranging from autonomous drone fleets to smart grid management—often involve non-linear objectives and environments where transition dynamics and loss functions shift over time. This paper introduces MetaCURL, a novel framework designed to address Concave Utility Reinforcement Learning (CURL) in non-stationary, adversarial settings.

The CURL Problem and Non-Stationarity

Concave Utility Reinforcement Learning (CURL) extends RL to objectives that are concave functions of the long-term state-action distribution. This is essential for tasks such as:

  • Pure Exploration: Maximizing state entropy.
  • Imitation Learning: Minimizing divergence from an expert's behavior.
  • Fairness and Risk-Aversion: Balancing rewards across different criteria.

The primary difficulty in CURL is that the non-linearity of the objective invalidates the standard Bellman equations, precluding the use of traditional dynamic programming. Furthermore, most existing CURL algorithms assume the environment is stationary. In practice, external factors like hardware degradation or market fluctuations cause the environment's transition probabilities ($p^t$) and loss functions to change. MetaCURL is the first algorithm to provide a solution for CURL in these dynamic, non-stationary environments without requiring prior knowledge of the environment's "variation budget."

The MetaCURL Algorithm

MetaCURL is a meta-algorithm that aggregates multiple instances of a baseline RL algorithm, specifically Greedy MD-CURL, treating them as "experts."

1. Multi-Layered Expert Aggregation

To handle the complexity of non-stationary CURL, MetaCURL employs a two-layer expert system:

  • Layer 1 (Distribution Aggregation): While CURL objectives are non-convex over the space of policies, they remain convex over the space of state-action distributions. MetaCURL aggregates the distributions suggested by different policy experts to optimize the non-linear utility.
  • Layer 2 (Transition Estimation): Since transition dynamics are unknown and changing, a second layer of experts is dedicated to estimating the transition kernel. This layer uses a smoothed logarithmic loss to ensure robustness against adversarial shifts.

2. Sleeping Experts Framework

The algorithm initializes new baseline instances at different time intervals and with varying learning rates. To manage these overlapping instances, MetaCURL utilizes a "sleeping expert" framework. This allows the meta-algorithm to focus on "fresh" experts that are better suited to the current environment state while ignoring inactive or outdated instances.

Theoretical Results: Dynamic Regret

The authors provide a rigorous dynamic regret analysis, marking a significant milestone for CURL research. MetaCURL achieves a regret bound of:

$$\tilde{O}(\sqrt{\Delta^{\pi^*} T} + \min\{\sqrt{\Delta^p_\infty T}, T^{2/3}(\Delta^p)^{1/3}\})$$

Where $\Delta^{\pi^*}$ and $\Delta^p$ represent the variation in the optimal policy sequence and the transition kernel, respectively. Key advantages of this result include:

  • Adversarial Robustness: The regret bound is independent of the variation in the loss function, allowing MetaCURL to perform reliably even when losses are chosen adversarially.
  • Parameter-Free Adaptation: The algorithm does not require advance knowledge of the environment's non-stationarity; it adapts on the fly by evaluating the performance of its internal experts.
  • Computational Efficiency: By avoiding the heavy computational cost of "Upper Confidence" exploration (common in algorithms like UCRL), MetaCURL remains more tractable for complex tasks.

Limitations and Future Directions

While MetaCURL represents a major step forward, it has certain limitations. The current "naive" implementation requires running $O(T \log T)$ instances of the baseline algorithm, though the authors suggest this can be optimized to $O(\log T)$. Additionally, the algorithm operates under the "Dynamics Hypothesis," assuming the deterministic physics of the environment are known while the noise/external dynamics are unknown. Future research aims to bridge the gap between non-stationarity and full exploration in environments where the underlying physics are also unknown and changing.

Conclusion

MetaCURL provides a robust theoretical foundation for solving non-linear RL problems in changing worlds. By combining expert aggregation with a distribution-focused approach, it offers a path toward more resilient and flexible autonomous systems in real-world applications.

Summary updated

BibTeX
@inproceedings{moreno2024metacurl,
  author = {Bianca Marin Moreno and Margaux Brégère and Pierre Gaillard and Nadia Oudjane},
  title = {{MetaCURL: Non-stationary Concave Utility Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=TS09IypR3r},
}
Figure