Abstract
We consider online learning in episodic loop-free Markov decision processes (MDPs), where the loss function can change arbitrarily between episodes, and the transition function is not known to the learner. We show a $\tilde{O}(L|X|\sqrt{|A|T})$ regret bound, where $T$ is the number of episodes, $X$ is the state space, $A$ is the action space, and $L$ is the length of each episode. Our online algorithm is implemented using entropic regularization methodology, which allows to extend the original adversarial MDP model to handle convex performance criteria (different ways to aggregate the losses of a single episode), as well as improve previous regret bounds.
Introduction
Standard Reinforcement Learning (RL) typically operates under the assumption of a stationary environment where rewards and transition dynamics remain fixed. However, many real-world applications—such as high-frequency trading, adaptive network routing, or competitive robotics—are inherently "adversarial." In these settings, rewards or losses can change unpredictably over time, often in response to the learner's own actions.
While prior research has addressed adversarial losses in MDPs, most existing frameworks assume the learner has prior knowledge of the transition function. Those that do account for unknown transitions have largely been restricted to minimizing simple expected average losses. This paper, presented at ICML 2019, introduces UC-O-REPS, an algorithm that achieves near-optimal regret bounds in adversarial MDPs with unknown transition dynamics and general convex performance criteria.
Problem Formulation
The paper focuses on episodic, loop-free MDPs. In this setting:
- Unknown Transitions: The learner does not know the underlying physics (transition function) of the environment.
- Adversarial Losses: Loss functions are not stochastic but can be chosen by an adversary at each episode $t$.
- Convex Performance Criteria: Instead of merely minimizing a linear sum of losses, the learner may optimize for more complex, convex objectives, such as risk-sensitive or robust measures.
The UC-O-REPS Algorithm
The authors propose UC-O-REPS (Upper Confidence Online Relative Entropy Policy Search), which integrates three core methodologies:
1. Occupancy Measures as a Bridge
The fundamental technical insight is the reformulation of the MDP problem into a convex optimization problem over occupancy measures. An occupancy measure represents the probability of visiting a specific state-action-state triple. This transformation allows the sequential decision-making problem to be treated as a structured optimization task.
2. Handling Uncertainty with UCRL-2
To manage unknown transitions, the algorithm adopts the "Optimism in the Face of Uncertainty" principle from the UCRL-2 framework. It maintains confidence sets—a collection of all transition functions consistent with the data observed so far. In each episode, the learner selects the occupancy measure that performs best across the most favorable transition function within this set.
3. Online Mirror Descent (OMD)
To handle the adversarial nature of the losses, UC-O-REPS employs Online Mirror Descent with entropic regularization. By using Relative Entropy (KL divergence) as a distance metric, the algorithm ensures that the policy evolves smoothly between episodes, preventing drastic, suboptimal shifts in strategy due to transient adversarial noise.
Key Results and Theoretical Impact
The primary contribution of this work is the establishment of a significantly improved regret bound. The authors prove that UC-O-REPS achieves a regret of: $$\tilde{O}(L|X|\sqrt{|A|T})$$
Comparison to Prior Art
Compared to the previous state-of-the-art (Neu et al., 2012), which established a regret bound of $\tilde{O}(L|X||A|\sqrt{T})$, UC-O-REPS improves the bound by a factor of $\sqrt{|A|}$. This improvement is critical for environments with large action spaces, where previous methods scaled poorly.
Beyond Linear Losses
Because the algorithm is built on entropic regularization, it naturally extends to convex performance criteria. This allows the learner to optimize for objectives beyond the simple sum of expected rewards, such as minimizing variance or ensuring robustness against worst-case loss scenarios across multiple functions.
Limitations and Future Directions
Despite its theoretical strengths, the paper identifies several areas for further exploration:
- Loop-Free Constraint: The current analysis assumes a layered, loop-free state space. While common in episodic RL, extending these bounds to general MDP structures remains a challenge.
- Feedback Models: The algorithm assumes "full information" feedback, meaning the learner observes the entire loss function at the end of an episode. Adapting this to "bandit feedback," where only the loss of the traversed path is visible, is a significant open problem.
- State Space Scaling: There remains a small gap between the achieved bound and the theoretical lower bound regarding the state space size $|X|$ and episode length $L$. Future work may close this gap through advanced variance-reduction techniques.
Summary updated