PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributional Robustness and Regularization in Reinforcement Learning

Esther Derman, Shie Mannor

arXiv:2003.02894v2math.OCcs.LGstat.ML

TL;DR

RL strategies can suffer when transition models estimated from historical data do not match deployment conditions, and prior work had not connected regularization with robustness to parameter uncertainty. The paper introduces Wasserstein distributionally robust MDPs and a dual relation to regularized value functions, reporting out-of-sample guarantees and a lower-bound result.

  • Problem

    In RL, regularization and robustness to parameter uncertainty had not been connected, while strategies learned from historical data may degrade when deployed.

    Source: §1 · pp. 1–2

  • Method

    The paper introduces Wasserstein distributionally robust MDPs to establish a dual relation between robustness to model uncertainty and regularized value functions, extending the result to linear function approximation.

    Source: §1 · p. 2

  • Results

    Wasserstein distributionally robust MDPs have out-of-sample guarantees, and the regularized value function lower-bounds a distributionally robust value.

    Source: §1 · p. 2, §5 · p. 5

  • Takeaways & Limitations

    The authors present regularized value functions as a way to facilitate robust RL.

    Source: §5 · p. 5

    The tightness and asymptotic consistency of the approach remain for future analysis; extensions to nonlinear approximation and deep architectures are also future work.

    Source: §5 · p. 5

Abstract

from arXiv · show

Distributionally Robust Optimization (DRO) has enabled to prove the equivalence between robustness and regularization in classification and regression, thus providing an analytical reason why regularization generalizes well in statistical learning. Although DRO's extension to sequential decision-making overcomes $\textit{external uncertainty}$ through the robust Markov Decision Process (MDP) setting, the resulting formulation is hard to solve, especially on large domains. On the other hand, existing regularization methods in reinforcement learning only address $\textit{internal uncertainty}$ due to stochasticity. Our study aims to facilitate robust reinforcement learning by establishing a dual relation between robust MDPs and regularization. We introduce Wasserstein distributionally robust MDPs and prove that they hold out-of-sample performance guarantees. Then, we introduce a new regularizer for empirical value functions and show that it lower bounds the Wasserstein distributionally robust value function. We extend the result to linear value function approximation for large state spaces. Our approach provides an alternative formulation of robustness with guaranteed finite-sample performance. Moreover, it suggests using regularization as a practical tool for dealing with $\textit{external uncertainty}$ in reinforcement learning methods.

1. Introduction

Reinforcement learning faces external uncertainty from unknown model parameters, while existing regularization addresses internal stochasticity and robust MDPs remain difficult to solve. The paper connects robustness and regularization through Wasserstein distributionally robust MDPs and a regularizer for value functions.

1. Introduction

  • Unknown model parameters, limited data, and large state spaces can complicate deployment and policy evaluation in reinforcement learning.The paper notes that learned strategies may degrade when deployed and that value-function approximation introduces additional uncertainty.Source: §1 · p. 1
  • Prior equivalences between robustness and regularization in classification, regression, and maximum-likelihood estimation concern single-stage decision problems.Source: §1 · p. 2
  • Existing RL regularizers address internal stochasticity, whereas robust MDPs target external uncertainty but can be difficult to solve without excessive conservatism.Source: §1 · p. 2
  • The paper introduces Wasserstein distributionally robust MDPs, derives a dual relation to regularized value functions, extends it to linear function approximation, and establishes out-of-sample guarantees.Source: §1 · p. 2
  • The authors present their study as the first connection in RL between regularization and robustness to parameter uncertainty.Source: §1 · p. 2
  • Unlike distributional RL, which studies the internal distribution of cumulative reward, this work studies worst-case expectations under external uncertainty in MDP parameters.Source: §1 · p. 2

2. From MDPs to distributionally robust MDPs

The section moves from the MDP framework to robust and distributionally robust variants, then introduces Wasserstein ambiguity sets as a tractable basis for planning and later analysis.

2.1. Markov Decision Process

  • An MDP models sequential decisions with state and action spaces, a bounded deterministic reward function, and a transition model.Source: §2.1 · p. 2

2.2. Robust Markov Decision Process

  • Robust MDPs optimize worst-case policy performance over an uncertainty set; under rectangularity, robust dynamic programming can solve them efficiently.Source: §2.2 · p. 3

2.3. Distributionally Robust Markov Decision Process

  • A DRMDP treats the unknown transition model as a random variable governed by a distribution in an ambiguity set, whose properties affect tractability.Source: §2.3 · p. 3

2.4. Wasserstein Distributionally Robust Markov Decision Process

  • Wasserstein DRMDPs place distributions over each state's unknown transition model in Wasserstein balls around reference distributions, enabling standard planning algorithms through a contracting robust Bellman operator.Source: §2.4 · p. 3

3. Regularization and Wasserstein DRMDPs

The section builds empirical transition distributions from episode-level estimates and uses them to connect regularized value functions with Wasserstein distributionally robust MDPs. It extends this result to linear value-function approximation for large state spaces.

3.1. Empirical Value Function and Distribution

  • Tabular estimates use episode transition counts to form empirical models, whose distribution centers the Wasserstein ambiguity set.Source: §3.1 · pp. 3–4
  • For large state spaces, kernel averages approximate the empirical transition function.Source: §3.1 · p. 3

3.2. Robustification via Regularization

  • The regularized value function lower-bounds the Wasserstein distributionally robust value, with the gap controlled by Lγ,β,Rmaxα.Source: §3.2 · p. 4
  • Standard value iteration can estimate episode-specific values; subtracting Lγ,β,Rmaxα from their average yields distributional robustness.Source: §3.2 · p. 4
  • Under standard conditions, the tabular result generalizes to large MDPs using linear value-function approximation with linearly independent features.Source: §3.2 · p. 4

4. Out-of-Sample Performance Guarantees

The section gives finite-sample out-of-sample performance guarantees for WDRMDPs with carefully chosen Wasserstein-ball radii. With high probability, the optimal policy’s out-of-sample value is at least its certificate performance, and the regularized value function inherits the guarantee.

4. Out-of-Sample Performance Guarantees

  • With probability at least 1−ε, the WDRMDP optimal policy’s out-of-sample value is no lower than its certificate performance.The guarantee applies when the statewise Wasserstein-ball radii satisfy the theorem’s conditions.Source: §4 · p. 4
  • As the sample size grows, the Wasserstein-ball radius tends to zero, making the WDRMDP solution less conservative.When the sample size is below the stated threshold, the WDRMDP becomes a robust MDP with uncertainty set P_s.Source: §4 · p. 4
  • The regularized value function also satisfies the WDRMDP’s out-of-sample performance guarantee.The section states this follows from the guarantee for the distributionally robust value function.Source: §4 · p. 4
  • The m = 2 case is omitted, although the authors state that a comparable conclusion can be established.Source: §4 · p. 4

5. Discussion

The discussion presents the regularized value function as a lower bound on a distributionally robust value. It identifies tightness, asymptotic consistency, nonlinear approximation, deep architectures, and policy optimization as directions for future work.

5. Discussion

  • The study establishes the regularized value function as a lower bound of a distributionally robust value.Source: §5 · p. 5
  • Future work should analyze the approach’s tightness and asymptotic consistency as sample size increases.Source: §5 · p. 5
  • The discussion proposes extending the results to nonlinear function approximation, deep architectures, and regularized policy optimization.It also identifies connecting the regularized formulation to regularized policy search as a direction for future work.Source: §5 · p. 5

A. Preliminaries on Convex Analysis

The preliminaries define convex-analysis concepts used in the proofs, including proper and closed functions, convex closure, and conjugacy. They also establish that the convex closure of a proper closed function on a compact space is proper.

A. Preliminaries on Convex Analysis

B.1. Proof of Theorem 3.1

The proof establishes the regularized value function as a lower bound on the distributionally robust value, then bounds the regularization term to control the gap. It uses Wasserstein ambiguity-set structure and convex-analysis arguments, with continuity and Lipschitz properties supporting the derivation.

B.1. Proof of Theorem 3.1

  • The proof’s two steps are to establish a lower bound from the regularized value and then upper-bound the regularization term to bound the gap.Source: §B.1 · p. 8
  • The Wasserstein ambiguity constraint decomposes into statewise constraints requiring each transition-model distribution to lie within its state’s radius.The proof then reformulates the worst-case value using duality and auxiliary variables.Source: §B.1 · pp. 9–10
  • The proof uses convex closure and conjugacy arguments to reformulate the worst-case expectation under the Wasserstein constraint.It introduces a function later used to bound the gap between robust and regularized values.Source: §B.1 · pp. 9–10
  • The continuation function is shown to be Lipschitz in the transition function, and the proof establishes continuity of the Bellman operator with respect to transitions.Source: §B.1 · pp. 8, 11

B.2. Proof of Theorem 3.2

The proof establishes the linear-approximation result by expressing the robust value through worst-case transition laws and a convex-duality reformulation.

B.2. Proof of Theorem 3.2

  • The proof represents the worst-case distributionally robust value using constrained transition laws and a duality argument.It then considers the worst-case model and introduces auxiliary variables to reformulate the bound.Source: §B.2 · p. 12
  • Because the state space is finite, the relevant probability-measure set is compact and the infima in the first-line constraints are minima.Source: §B.2 · pp. 12–13
  • Linear independence of the feature vectors supports the convex-closure and dual-norm steps used to derive the lower-bound inequality.The proof then applies a support-function bound before stating the resulting inequality.Source: §B.2 · pp. 13–14

C.1. Proof of Theorem 4.1

The proof derives a finite-sample guarantee for a Wasserstein robust MDP from empirical Wasserstein concentration and convergence of a contracting Bellman operator.

C.1. Proof of Theorem 4.1

  • For m = |S| × |A|, the concentration lemma bounds deviations of each state's empirical distribution, with constants depending on m ≠ 2.The stated exponential term is b1(ns, βs) = exp(−c2ns · (βs)^(m∨2)).Source: §C.1 · p. 14
  • The proof builds on prior concentration results but addresses the MDP framework rather than the stochastic-control setting described in the cited work.Source: §C.1 · p. 14
  • The theorem gives a probabilistic guarantee for the optimal policy when each state's Wasserstein-ball radius satisfies the stated condition.Source: §C.1 · pp. 14–15
  • The proof uses contraction and induction to show that iterating the robust Bellman operator converges to the optimal policy's value.Source: §C.1 · p. 15

Related papers

Loading 2003.02894v2…