Abstract
Policy optimization methods are popular reinforcement learning algorithms in practice. Recent works have built a theoretical foundation for them by proving $\sqrt{T}$ regret bounds even when the losses are adversarial. Such bounds are tight in the worst case but often overly pessimistic. In this work, we show that in tabular Markov decision processes (MDPs), by properly designing the regularizer, the exploration bonus, and the learning rates, one can achieve a more favorable polylog$(T)$ regret when the losses are stochastic, without sacrificing the worst-case guarantee in the adversarial regime. To our knowledge, this is also the first time a gap-dependent polylog$(T)$ regret bound is shown for policy optimization. Specifically, we achieve this by leveraging a Tsallis entropy or a Shannon entropy regularizer in the policy update. Then we show that under known transitions, we can further obtain a first-order regret bound in the adversarial regime by leveraging the log-barrier regularizer.
Introduction
In Reinforcement Learning (RL), the performance of an algorithm is typically measured by regret—the cumulative difference between the loss incurred by the learner and the loss of the best possible policy in hindsight. Traditionally, theoretical guarantees for RL algorithms fall into two distinct camps:
- Adversarial Settings: The environment is assumed to be non-stationary or even malicious. Algorithms must be robust, typically aiming for a $\sqrt{T}$ regret bound.
- Stochastic Settings: The environment is stable, with losses drawn from fixed distributions. In these "easier" settings, we expect much faster convergence, specifically logarithmic or polylogarithmic regret ($polylog(T)$).
In practice, a learner rarely knows the nature of the environment beforehand. While adversarial-optimal algorithms provide safety, they are often too pessimistic to exploit the structure of stable environments. Conversely, stochastic-focused algorithms can fail catastrophically if the environment shifts. This paper addresses the "Best of Both Worlds" (BoBW) challenge: designing a single policy optimization algorithm that automatically adapts to the environment's difficulty.
The Policy Optimization Framework
Previous BoBW solutions for MDPs relied on complex optimization over the entire "occupancy measure" space. While theoretically sound, these methods are computationally expensive and difficult to extend to model-free settings. This work proposes a more practical alternative: decentralized policy optimization.
The core idea is to treat each state in a tabular MDP as an individual multi-armed bandit problem. By running a version of Follow the Regularized Leader (FTRL) at every state, the algorithm updates policies locally while accounting for the global MDP structure through the transition kernel.
Key Technical Innovations
To bridge the gap between adversarial robustness and stochastic efficiency, the authors introduce several critical mechanisms:
- State-Wise Regularization: The choice of regularizer is pivotal. The paper analyzes Tsallis entropy, Shannon entropy, and the Log-barrier. Tsallis entropy, in particular, is shown to be highly effective for achieving gap-dependent polylogarithmic regret.
- Adaptive Exploration Bonuses: To ensure sufficient exploration without the overhead of traditional $1/\sqrt{t}$ rates, the authors design a two-part bonus. One part compensates for the FTRL update's regret, while the other accounts for errors in transition estimation.
- Implicit Exploration: By utilizing an exploration factor $\gamma_t \approx 1/t$ (rather than the standard $1/\sqrt{t}$), the algorithm can achieve the faster $polylog(T)$ rate in stable environments.
- Virtual Episodes: A novel stability technique used with the log-barrier regularizer. When learning rates must be adjusted downward to maintain stability, the algorithm "inserts" a virtual episode to update internal parameters without interacting with the environment, preventing large negative bonuses from destabilizing the policy.
Theoretical Results
The proposed framework yields several state-of-the-art regret bounds across different settings:
| Regularizer | Transitions | Adversarial Regret | Stochastic Regret |
|---|---|---|---|
| Tsallis Entropy | Known | $\sqrt{T}$ | $polylog(T)$ |
| Tsallis Entropy | Unknown | $\sqrt{T}$ | $polylog(T)$ |
| Log Barrier | Known | $\sqrt{L} \cdot polylog(T)$ | $polylog(T)$ |
Notably, the Tsallis entropy result for unknown transitions improves upon previous $T^{2/3}$ adversarial bounds while maintaining stochastic efficiency. Furthermore, the log-barrier regularizer achieves a first-order bound, where regret scales with the cumulative loss of the best policy ($L$) rather than the total time horizon ($T$). This is a significant advantage in environments where the optimal policy incurs very little loss.
Discussion and Limitations
While this work provides the first gap-dependent polylogarithmic regret bounds for policy optimization, it focuses on the tabular setting (finite states and actions). A major open challenge remains: extending these BoBW guarantees to environments requiring function approximation, such as those using neural networks. Additionally, achieving first-order bounds ($\sqrt{L}$) under unknown transitions remains an unresolved theoretical hurdle.
Despite these limitations, the paper demonstrates that simple, local policy optimization—when paired with the right regularizers and exploration schedules—can be both robust and highly adaptive, offering a computationally efficient path toward more versatile RL agents.
Summary updated