Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback

Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni, Alberto Marchesi, Nicola GattiSubmission to ICLR 2025 · Rejected

Here is a blog-style summary of the paper:

TL;DR

This paper introduces the first "best-of-both-worlds" learning algorithm for episodic Constrained Markov Decision Processes (CMDPs) operating under realistic bandit feedback. By pairing a primal policy optimization method (incorporating dilated exploration bonuses and fixed-share updates) with dual online gradient descent, the algorithm achieves optimal $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and constraint violation without needing prior knowledge of the environment's feasibility margin or solving costly convex programs at every round.

What Problem Does This Paper Address?

In online reinforcement learning with safety or budget requirements (modeled as CMDPs), an agent aims to maximize rewards while keeping cumulative constraint violations low over $T$ episodes. However, in real-world scenarios:

  1. Nature of feedback: Agents typically receive bandit feedback (observing rewards/costs only along the executed trajectory), not full feedback (observing the entire state-action loss matrix).
  2. Environment behavior: Rewards and constraints can be stochastic (drawn from a fixed distribution) or adversarial (chosen arbitrarily without statistical assumptions). Designing an algorithm that performs optimally in both regimes without knowing which one it faces beforehand is the "best-of-both-worlds" (BOBW) challenge.
  3. Computational efficiency: Existing BOBW approaches rely on optimizing directly over occupancy measures by solving large convex optimization problems at every episode, which is computationally prohibitive.

Methods

The authors propose Primal-Dual Bandit Policy Search (PDB-PS), a framework updating primal policy parameters and dual Lagrange multipliers state-by-state:

  • Primal Player (FS-PODB): Uses Fixed Share Policy Optimization with Dilated Bonus. It updates policies layer-by-layer rather than solving global linear/convex programs.
  • Fixed-Share Updates: Mixes the exponential mirror descent update with a uniform distribution ($\sigma = 1/T$) to guarantee policy exploration across all actions and ensure the no-interval-regret property.
  • Dilated Exploration Bonuses & Optimistic Q-estimators: Mitigates variance from bandit feedback and unknown transitions by adding exploration bonuses weighted by layer depth.
  • Dual Player (OGD): Runs Online Projected Gradient Descent over the Lagrange multipliers $\lambda$ associated with constraint violations.
  • Self-Bounding Lagrange Multipliers: Rather than artificially clipping the dual space using an unknown Slater's margin $\rho$, the authors prove that primal and dual no-interval-regret properties naturally keep the multipliers bounded during learning.

Datasets

Not discussed in the paper. (This is a purely theoretical paper with no empirical simulations or benchmark datasets.)

Key Insights and Ideas

  • No-Interval-Regret under Bandit Feedback: While no-interval regret is relatively straightforward under full information, establishing it in adversarial episodic MDPs with bandit feedback and unknown transitions is non-trivial. The paper achieves this by combining fixed-share policy updates with dilated exploration bonuses.
  • Automatic Bounding of Dual Variables: Knowing the Slater parameter $\rho$ (the margin by which the strictly feasible policy satisfies constraints) is usually assumed in literature. By pitting the primal interval regret against the dual interval regret, the authors establish a proof by contradiction showing that Lagrange multipliers remain naturally bounded by $\Lambda = \mathcal{O}(mH^2 / \rho^2)$ as long as $\rho \ge T^{-1/8} H \sqrt{112m}$.
  • Overcoming Impossibility in the Adversarial Setting: Due to classic impossibility results (Mannor et al., 2009), achieving sublinear regret against an average-in-hindsight comparator is impossible with adversarial constraints. The paper shows that PDB-PS achieves a tight competitive ratio $\frac{\rho}{\rho + H}$ against this standard baseline, and can achieve full $\widetilde{\mathcal{O}}(\sqrt{T})$ regret if evaluated against a slightly weaker baseline that must satisfy constraints at every round.

Key Results

Under Slater's condition ($\rho \ge T^{-1/8} H \sqrt{112m}$):

  • Stochastic Constraints: Achieves high-probability $\widetilde{\mathcal{O}}(\Lambda \sqrt{T})$ regret and $\widetilde{\mathcal{O}}(\Lambda \sqrt{T})$ constraint violation (matching full-feedback rates up to poly-logarithmic factors), whether rewards are stochastic or adversarial.
  • Adversarial Constraints (Standard Baseline): Achieves $\widetilde{\mathcal{O}}(\Lambda \sqrt{T})$ violation and guarantees at least a $\frac{\rho}{\rho + H}$ fraction of the optimal reward in hindsight.
  • Adversarial Constraints (Per-Round Baseline): Achieves $\widetilde{\mathcal{O}}(\Lambda \sqrt{T})$ regret and $\widetilde{\mathcal{O}}(\Lambda \sqrt{T})$ violation against policies that satisfy constraints episode-by-episode.
  • Degenerate Feasibility ($\rho \to 0$): If Slater's condition does not hold, the algorithm gracefully falls back to dual-space projection $[0, T^{1/4}]^m$, guaranteeing $\widetilde{\mathcal{O}}(T^{3/4})$ regret and violation.

Limitations and Future Work

  • Dependence on Problem Parameters: The bound scales quadratically with $1/\rho$ ($\Lambda \propto 1/\rho^2$) and contains polynomial factors of state/action spaces $|X|, |A|$ and horizon $H$, which may be large in practical environments.
  • Tabular Restriction: The theoretical framework is developed for finite, tabular loop-free MDPs; generalizing this to large or continuous state-action spaces with function approximation remains an open challenge.
  • Empirical Validation: The work does not include empirical experiments demonstrating the wall-clock speedup or practical stability of FS-PODB over occupancy-measure methods.

Summary updated

Abstract

We study online learning in constrained Markov decision processes (CMDPs) in which rewards and constraints may be either stochastic or adversarial. In such settings, Stradi et al. (2024b) proposed the first best-of-both-worlds algorithm able to seamlessly handle stochastic and adversarial constraints, achieving optimal regret and constraint violation bounds in both cases. This algorithm suffers from two major drawbacks. First, it only works under full feedback, which severely limits its applicability in practice. Moreover, it relies on optimizing over the space of occupancy measures, which requires solving convex optimization problems, an highly inefficient task. In this paper, we provide the first best-of-both-worlds algorithm for CMDPs with bandit feedback. Specifically, when the constraints are stochastic, the algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and constraint violation, while, when they are adversarial, it attains $\widetilde{\mathcal{O}}(\sqrt{T})$ constraint violation and a tight fraction of the optimal reward. Moreover, our algorithm is based on a policy optimization approach, which is much more efficient than occupancy-measure-based methods.
BibTeX
@misc{stradi2024best,
  author = {Francesco Emanuele Stradi and Anna Lunghi and Matteo Castiglioni and Alberto Marchesi and Nicola Gatti},
  title = {{Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback}},
  year = {2024},
  eprint = {2410.02269},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.02269},
}
Figure