Fast rates for online learning in Linearly Solvable Markov Decision Processes

Gergely Neu, Vicenç Gómez

Abstract

In the field of online Reinforcement Learning (RL), achieving fast regret rates in non-stochastic environments remains a significant challenge. This paper addresses the problem of online learning within Linearly Solvable Markov Decision Processes (LMDPs), a subclass of MDPs where the control cost is defined by the Kullback-Leibler (KL) divergence between controlled and passive dynamics. We demonstrate that a simple "Follow the Leader" (FTL) algorithm, which typically performs poorly in adversarial settings, achieves a logarithmic regret bound of $O(\log^2 T)$ in LMDPs. This result represents a substantial improvement over the previous state-of-the-art bound of $O(T^{3/4})$ and highlights how the inherent mathematical structure of LMDPs provides a natural regularization that facilitates rapid learning.

Introduction

Traditional Reinforcement Learning often operates under the assumption of stationarity, where costs and transitions are drawn from fixed probability distributions. However, real-world applications frequently encounter non-stochastic or "online" settings where costs may change unpredictably over time due to external shifts or adversarial behavior. In these scenarios, the objective is to minimize regret: the difference between the cumulative cost incurred by the learner and the cost of the single best stationary policy chosen in hindsight.

While general MDPs are typically limited to "slow" regret rates of $O(\sqrt{T})$, specific structural assumptions can sometimes yield faster convergence. This paper focuses on Linearly Solvable MDPs (LMDPs). Previous research into online learning for LMDPs only managed to secure a regret bound of $O(T^{3/4})$. By exploiting the unique properties of the LMDP framework, we show that it is possible to achieve "fast" rates, specifically $O(\log^2 T)$, using an unregularized FTL approach.

The LMDP Framework and Follow the Leader

In an LMDP, the learner does not select discrete actions but instead directly influences state transition probabilities. The cost function is partitioned into two distinct components:

  1. State-dependent cost: A standard cost associated with occupying a specific state.
  2. Control cost: A penalty based on the KL divergence between the learner's chosen transition probability and the environment's "passive dynamics" (the natural evolution of the system in the absence of control).

The algorithm proposed is Follow the Leader (FTL). At each time step $t$, the learner calculates the average of all state costs observed from time $1$ to $t-1$ and adopts the optimal policy for that average cost. In most online optimization problems, FTL is considered unstable because small changes in observed costs can lead to radical shifts in the optimal policy, resulting in high regret. However, in the context of LMDPs, the KL-divergence term acts as a built-in regularizer. This ensures that the optimal policy evolves smoothly as more data is collected, preventing the aggressive "jumping" that usually undermines FTL.

Theoretical Insights: Smoothness and Convexity

The success of FTL in this setting stems from several key mathematical insights:

  • Policy Smoothness: The primary discovery is that the control cost makes the optimal policy a smooth function of the underlying state costs. Because the policy reacts gradually to changes in the cost environment, the learner avoids the massive regret penalties associated with high-variance policy updates.
  • Convex Optimization Formulation: The authors reframe LMDPs as a convex optimization problem over stationary transition measures. This bridge allows the application of tools from Online Convex Optimization (OCO) to the complex dynamics of Markov processes.
  • Linearity of Bellman Equations: A defining characteristic of LMDPs is that the Bellman optimality equations can be transformed into a linear system, specifically an eigenvalue problem. This mathematical elegance allows for a precise analysis of how the optimal policy responds to perturbations in the cost sequence.

Results and Regret Analysis

The central result of this research is the derivation of a regret bound of $O(\log^2 T)$. This is a massive leap forward from the previous $O(T^{3/4})$ benchmark.

Furthermore, the analysis reveals that the regret bound scales polynomially with the "mixing time" of the environment—the time required for the Markov process to reach a steady state. Notably, the bound does not show an explicit dependence on the total number of states, suggesting that this approach may remain efficient even as the state space grows, provided the environment remains well-mixed.

Discussion and Future Directions

While the $O(\log^2 T)$ bound is a landmark improvement, several avenues for future research remain. The current proof assumes an oblivious adversary, where the sequence of costs is fixed at the start and does not react to the learner's specific trajectory. Extending these fast rates to adaptive adversaries is a critical next step for robust real-world deployment.

Additionally, the authors hypothesize that the loss function in LMDPs may possess a property called "exp-concavity." If proven, this could potentially tighten the regret bound even further to $O(\log T)$. Finally, while this work focuses on finite state spaces, the LMDP framework is naturally applicable to continuous spaces (often studied as path integral control). Adapting this analysis to continuous control tasks could provide new theoretical foundations for high-dimensional robotics and autonomous systems.

Summary updated

BibTeX
@inproceedings{neu2017fast,
  author = {Gergely Neu and Vicenç Gómez},
  title = {{Fast rates for online learning in Linearly Solvable Markov Decision Processes}},
  booktitle = {Conference on Learning Theory},
  year = {2017},
  url = {https://openreview.net/forum?id=RmtMM-w9hpiX},
}
Figure