Online Convex Optimization in Adversarial Markov Decision Processes

Aviv Rosenberg, Yishay Mansour

Introduction

In real-world reinforcement learning (RL) applications—such as high-frequency trading or BGP routing—environments are rarely static. The "losses" or rewards incurred can change unpredictably due to shifting conditions or adversarial actors, and the underlying physics of the world (the transition dynamics) are often unknown.

This paper introduces UC-O-REPS (Upper Confidence Online Relative Entropy Policy Search), a novel algorithm designed for RL in these volatile environments. It is the first algorithm to handle "convex performance criteria" in adversarial Markov Decision Processes (MDPs) with unknown transitions, allowing for complex, risk-sensitive goals while achieving near-optimal regret bounds.

The Challenge of Adversarial MDPs

Standard MDPs typically assume two things: fixed environment dynamics and stationary rewards. While "Adversarial MDPs" have been studied to address changing rewards, existing approaches suffer from two major limitations:

  1. Known Dynamics: They frequently assume the learner already knows the environment's transition probabilities.
  2. Simple Objectives: They typically aim to minimize the expected average loss (a linear sum). This fails to account for risk-sensitive objectives (e.g., avoiding the absolute worst-case scenario) or multi-objective optimization.

This paper bridges this gap by tackling the "unknown transition" problem while simultaneously expanding the mathematical framework to support convex performance criteria.

Methodology: UC-O-REPS

The authors propose UC-O-REPS, which elegantly combines three powerful concepts to navigate unknown, adversarial environments:

  • Occupancy Measures: Instead of searching directly for the best policy (which action to take in which state), the algorithm searches for the best "occupancy measure"—the probability distribution of visiting specific state-action-state triplets. This reframing turns the MDP problem into a convex optimization problem.
  • Online Mirror Descent (OMD): To handle losses that change every episode, the algorithm employs OMD. It selects a new occupancy measure that minimizes the current loss but stays "close" to the previous measure to ensure stability, using KL-divergence as the distance metric.
  • Optimism in the Face of Uncertainty (UCRL-2): Because the transition function is unknown, the learner builds "confidence sets" of possible environments based on observed data. It then acts optimistically by selecting the best possible occupancy measure within the set of plausible environments.

The core technical contribution lies in demonstrating that the resulting optimization problem—which involves a KL-divergence objective over a set of linear and confidence-based constraints—can be solved efficiently using Lagrange multipliers.

Key Insights

  • Universality of Convexity: The authors prove that many complex objectives, such as minimizing the maximum loss across multiple dimensions (min-max) or risk-sensitive "variance-aware" objectives, can be modeled as "convexly-measurable" criteria.
  • Bridging OCO and RL: The paper successfully maps the theoretical tools of Online Convex Optimization (OCO) onto the structure of Reinforcement Learning under uncertainty.
  • Tightening the Bounds: By utilizing entropic regularization (the "Relative Entropy" component of the algorithm), the authors improved the regret bound's dependence on the action space size ($|A|$) compared to previous state-of-the-art methods.
  • High Probability Guarantees: Unlike many algorithms that only offer guarantees "on average," the regret bounds for UC-O-REPS hold with high probability, making the approach significantly more reliable for real-world deployment.

Theoretical Results

As a theoretical work focused on proving regret bounds and algorithmic complexity, the paper does not rely on empirical datasets. Instead, it offers robust mathematical guarantees:

  • Regret Bound: The algorithm achieves a regret of $\tilde{O}(L|X|\sqrt{|A|T})$, where $L$ is the episode length, $|X|$ is the state space size, $|A|$ is the action space size, and $T$ is the number of episodes.
  • Optimality: This bound is optimal with respect to the number of episodes ($T$) and the number of actions ($|A|$), matching known lower bounds for simpler versions of the problem.
  • Efficiency: The optimization step is reduced to a convex problem with only non-negativity constraints, allowing it to be solved using standard iterative methods.

Limitations and Future Work

While UC-O-REPS represents a significant step forward, several challenges remain:

  • The Optimality Gap: Although optimal in $T$ and $|A|$, there remains a small gap in the factors of $L$ (episode length) and $|X|$ (state space) compared to the absolute theoretical lower bound.
  • Bandit Feedback: The current framework assumes "full information" feedback, meaning the learner sees the entire loss function after an episode. Extending these convex criteria to the "bandit" setting—where the learner only sees the loss for the specific path taken—is significantly harder, as building an unbiased estimate of the loss requires knowing the transition probabilities.
  • Computational Scaling: While the optimization is theoretically efficient, solving it every episode may still prove computationally expensive for systems with massive state spaces.

Summary updated

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 ...
BibTeX
@inproceedings{rosenberg2019online,
  author = {Aviv Rosenberg and Yishay Mansour},
  title = {{Online Convex Optimization in Adversarial Markov Decision Processes}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=Sk-Xl3Z_Wr},
}
Figure