Upper Confidence Primal-Dual Optimization: Stochastically Constrained Markov Decision Processes with Adversarial Losses and Unknown Transitions

Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, Zhaoran WangarXiv 2020 · OpenReview

Abstract

This paper introduces the Upper Confidence Primal-Dual (UCPD) algorithm, a novel reinforcement learning framework designed for environments characterized by unknown transition dynamics and adversarial losses. By integrating the principle of "optimism in the face of uncertainty" with a dual-mirror descent architecture, UCPD achieves near-optimal regret and constraint violation bounds. This work addresses a significant gap in Constrained Markov Decision Processes (CMDPs), providing the first solution that simultaneously handles unpredictable costs and unknown physics while maintaining strict safety guarantees.

Introduction

In standard Reinforcement Learning (RL), agents typically focus on maximizing cumulative rewards through environmental exploration. However, real-world deployment—ranging from autonomous vehicle navigation to industrial power grid management—demands adherence to strict safety and resource constraints. These scenarios are formally modeled as Constrained Markov Decision Processes (CMDPs).

Existing research in CMDPs often relies on two simplifying assumptions: either the transition model (the "physics" of the environment) is known a priori, or the costs and rewards remain stationary over time. In practice, environments are frequently unknown, and costs can be "adversarial," meaning they may change arbitrarily between episodes. The challenge lies in achieving sublinear regret (performing as well as the best fixed policy in hindsight) and sublinear constraint violation (ensuring long-term safety) without a pre-existing map of the environment. This paper presents the UCPD algorithm to bridge this gap.

The UCPD Framework

The Upper Confidence Primal-Dual (UCPD) Mirror Descent algorithm is built upon three foundational pillars designed to balance exploration, exploitation, and safety.

1. Optimism via Confidence Sets

To navigate unknown transitions, the algorithm maintains a confidence set of plausible transition models based on observed trajectories. Following the "Optimism in the Face of Uncertainty" (OFU) principle, UCPD selects the most optimistic transition model within this set—specifically, the model that minimizes expected costs while remaining statistically consistent with past data.

2. Primal-Dual Mirror Descent

Constraints are managed through the use of Lagrange multipliers (dual variables). These variables function as a dynamic penalty mechanism: as constraint violations occur, the multipliers increase, effectively raising the "cost" of unsafe actions. This forces the agent to prioritize safety in subsequent episodes. The policy is updated using a mirror descent step, which regularizes the policy shift to ensure stability.

3. Epoch-Based "Lazy" Updates

A critical innovation of UCPD is its epoch-based structure. Rather than updating the transition model and policy after every step, the algorithm employs a "lazy" update schedule. It only refines its world model once sufficient new data has been collected to significantly narrow the confidence set. This stability prevents the optimism-driven exploration from causing erratic policy swings that would lead to excessive safety violations.

Theoretical Results

The authors provide rigorous mathematical proofs demonstrating that UCPD achieves state-of-the-art performance bounds in tabular MDPs:

  • Regret Bound: The algorithm achieves a regret of $\tilde{O}(L|S|\sqrt{|A|T})$, where $L$ is the episode length, $|S|$ is the state space size, and $|A|$ is the action space size. This rate matches the near-optimal bounds found in unconstrained RL settings.
  • Constraint Violation: UCPD achieves a violation bound of $\tilde{O}(L|S|\sqrt{|A|T})$. As the number of episodes $T$ increases, the average violation per episode asymptotically approaches zero.
  • Computational Efficiency: The subproblems within the UCPD framework are reducible to convex optimization problems, ensuring that the algorithm is computationally tractable for practical implementation.
  • Relaxed Assumptions: Unlike many constrained optimization approaches that require a strict "Slater condition" (the existence of a strictly safe policy), this work utilizes a weaker assumption, broadening its applicability to environments with narrow safety margins.

Discussion and Future Work

While UCPD represents a significant theoretical advancement, several avenues for future research remain:

  1. Bandit Feedback: The current analysis assumes "full-information" feedback, where the agent observes the entire loss function at the end of an episode. Extending this to bandit feedback—where only the loss of the specific path taken is visible—is a necessary step for many real-world applications.
  2. Adversarial Constraints: While the losses in this framework are adversarial, the constraints are assumed to be stochastic (drawn from a fixed distribution). Developing algorithms capable of handling truly adversarial constraints remains an open challenge.
  3. Function Approximation: The current results are limited to tabular MDPs with finite states and actions. To scale these guarantees to high-dimensional tasks like robotics, the framework must be extended to incorporate deep neural networks and function approximation techniques.

Conclusion

UCPD provides a robust theoretical foundation for safe reinforcement learning in unpredictable environments. By proving that optimism can be safely integrated with dual-mirror descent, this work paves the way for RL agents that are both high-performing and reliably secure in the face of unknown dynamics and adversarial costs.

Summary updated

BibTeX
@misc{qiu2020upper,
  author = {Shuang Qiu and Xiaohan Wei and Zhuoran Yang and Jieping Ye and Zhaoran Wang},
  title = {{Upper Confidence Primal-Dual Optimization: Stochastically Constrained Markov Decision Processes with Adversarial Losses and Unknown Transitions}},
  year = {2020},
  url = {https://openreview.net/forum?id=dZpzEADNWMD},
}
Figure