Learning the Uncertainty Set in Robust Markov Decision Process

Navdeep Kumar, Kaixin Wang, Uri Gadot, Kfir Yehuda Levy, Shie MannorICLR 2024 · OpenReview

Introduction

In standard Reinforcement Learning (RL), agents typically assume perfect knowledge of the environment's rewards and transition dynamics. However, real-world applications are rarely so pristine. Robust Markov Decision Processes (MDPs) account for this messiness by optimizing against an "uncertainty set"—a collection of possible models or environments the agent might actually face.

The critical challenge in Robust RL is determining the size of this uncertainty set, which is often assumed to be fixed and given by the designer. This leads to a classic "Goldilocks" problem:

  1. Too Big: If the set is too large, the agent prepares for unrealistic "worst-case scenarios," leading to overly conservative, timid, and sub-optimal behavior.
  2. Too Small: If the set is too restricted, the agent's policy isn't genuinely robust and may fail catastrophically if the environment shifts even slightly outside the expected bounds.

This paper introduces a novel, data-driven method to automatically learn the optimal size (specifically, the radius) of reward uncertainty sets. By grounding the uncertainty set in actual data, the authors ensure agents remain robust enough to handle variations without sacrificing performance to unnecessary conservativeness.

Methodology: A Data-Driven Radius

The authors focus specifically on Reward Uncertainty Sets, which they model geometrically as a "ball" surrounding a nominal reward function. The core contribution of the paper is a theoretical framework and an accompanying algorithm to estimate the minimal radius ($\alpha$) of this ball.

Theoretical Foundations

The paper establishes that the radius of the smallest uncertainty set containing a group of reward models can be calculated using two primary components:

  • Returns: The difference in total accumulated reward across different models.
  • Occupation Measure: A metric defining how often an agent visits specific state-action pairs.

Sample-Based Learning Algorithm

To translate this theory into practice, the authors propose a sample-based learning algorithm. Instead of manually tuning the uncertainty bounds, the algorithm observes how much rewards vary across different sample trajectories and sets the boundaries accordingly.

Algorithm for sample-based learning of the uncertainty radius

As detailed in Algorithm 1, given sample trajectories from different reward models, the process involves:

  1. Bootstrapping the occupancy measure iteratively using a contraction operator.
  2. Tracking the highest and lowest returns ($\rho$) across the different observed models.
  3. Computing the minimal radius $\alpha$ based on the maximum difference in returns scaled by the occupancy measure.

Key Insights and Theoretical Results

While this is a theoretical paper without empirical benchmark evaluations (e.g., MuJoCo or Atari), it provides several strong mathematical guarantees:

  • The Geometry of Robustness: By treating uncertainty as a geometric problem—finding the "smallest ball" that encompasses all observed reward models—the authors mathematically define the exact threshold where robustness meets efficiency.
  • Concrete Radius Formula: The paper provides a definitive formula for $\alpha$ based on the $L_p$ norm of reward differences, moving away from heuristic guessing.
  • Theoretical Lower Bound: The authors establish a strict lower bound for the uncertainty radius. They prove that any uncertainty set smaller than their calculated $\alpha$ would inherently fail to cover the underlying models implied by the training data.
  • Algorithmic Feasibility: The paper demonstrates that the occupancy measure, traditionally a complex variable to pin down, can be estimated efficiently from sample trajectories using standard RL bootstrapping techniques.

Limitations and Future Directions

As a foundational theoretical work, the paper outlines several avenues for future expansion:

  • Beyond Rewards: The current framework focuses exclusively on reward uncertainty. In many complex RL environments, transition uncertainty (how the state of the world changes in response to actions) is equally, if not more, critical to model.
  • Online Learning Integration: The proposed method assumes access to an offline dataset of transitions from several reward models. Adapting this into an "online" setting—where the agent dynamically learns and updates the uncertainty set while actively trying to solve the task—is a vital next step.
  • Empirical Validation: The natural progression for this research is to deploy Algorithm 1 in complex, high-stakes simulations (such as robotics or autonomous driving) to empirically measure its performance against manually tuned, fixed uncertainty sets.

Summary updated

Abstract

In robust Markov Decision Processes (MDPs), the uncertainty set is often assumed to be fixed and given. However, the size of the uncertainty set is crucial due to the inherent trade-off between robustness and conservatives: a larger uncertainty set fosters a more robust solution but tends towards increased conservativeness, while a smaller set may sacrifice robustness for higher performance. In this work, we introduce a novel method to learn the size of reward uncertainty set from data. Such a data-driven approach ensures that the learned uncertainty set is large enough to cover the underlying models implied by the data while being compact to minimize conservativeness.
BibTeX
@inproceedings{kumar2024learning,
  author = {Navdeep Kumar and Kaixin Wang and Uri Gadot and Kfir Yehuda Levy and Shie Mannor},
  title = {{Learning the Uncertainty Set in Robust Markov Decision Process}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=viHuAGGjqK},
}
Figure