A Fenchel-Moreau-Rockafellar type theorem on the Kantorovich-Wasserstein space with applications in partially observable Markov decision processes

Vaios Laschos, Klaus Obermayer, Yun Shen, Wilhelm StannatJournal of Mathematical Analysis and Applications 2019 · DOI · arXiv

Abstract

This paper establishes a fundamental duality theorem for convex functions defined on the space of probability measures equipped with the Wasserstein-1 metric. By leveraging the Arens-Eells space as a predual to Lipschitz functions, the authors extend the Fenchel-Moreau-Rockafellar theorem to this infinite-dimensional setting. This theoretical advancement provides a rigorous foundation for representing value functions in Partially Observable Markov Decision Processes (POMDPs) on continuous state spaces as suprema of linear functionals, generalizing classical results from finite-state systems.

1. Introduction

The intersection of convex analysis and optimal transport has long been a fertile ground for mathematical discovery. A central pillar of convex analysis is the Fenchel-Moreau theorem, which characterizes functions that are equal to their double conjugates. While this theory is well-developed for standard vector spaces, its application to the space of probability measures—specifically the Kantorovich-Wasserstein space—presents significant technical hurdles. This paper addresses these challenges, providing a general duality framework with direct implications for stochastic control and decision-making under uncertainty.

2. Theoretical Foundations: Duality in the $W_1$ Space

The primary theoretical contribution is the formulation of a Fenchel-Moreau-Rockafellar type theorem on the space of Borel probability measures $\mathcal{P}_1(X)$ equipped with the Wasserstein-1 distance ($W_1$).

2.1 The Arens-Eells Embedding

To treat the $W_1$ space within the framework of classical functional analysis, the authors utilize the Arens-Eells space. This space serves as a "predual" to the space of Lipschitz functions. By embedding probability measures into the Arens-Eells space, the $W_1$ distance is realized as a standard norm. This embedding is crucial because it allows the authors to apply Hahn-Banach type arguments that are otherwise difficult to formulate directly on the manifold of probability measures.

2.2 Theorem 1.1: The Core Duality

The authors prove that for any proper, lower-semicontinuous convex function $f$ defined on the $W_1$ space, $f$ is identical to its second conjugate $f^{**}$. This result, formalized as Theorem 1.1, ensures that such functions can be represented as the supremum of affine functionals. This is not merely a theoretical curiosity; it provides a mechanism to decompose complex, non-linear functions of measures into simpler, linear components.

3. Applications in POMDPs

Partially Observable Markov Decision Processes (POMDPs) provide a robust framework for sequential decision-making where the state of the system is not directly visible. Instead, the agent maintains a "belief"—a probability distribution over possible states.

3.1 From Finite to Continuous State Spaces

In the case of finite state spaces, the seminal work of Smallwood and Sondik (1973) demonstrated that the optimal value function is "piecewise linear and convex" (PWLC). However, extending this to continuous state spaces (e.g., a robot's coordinates in a physical environment) is non-trivial.

This paper provides the necessary theoretical bridge. Theorem 4.19 proves that the optimal value function for a POMDP on a Polish (complete, separable metric) space can be arbitrarily well-approximated by a convex function in dual form. This generalizes the "maximum of linear functions" intuition to infinite-dimensional belief spaces.

3.2 Set Iteration Algorithm

Beyond existence proofs, the authors propose Algorithm 4.18 (Set Iteration). Rather than performing traditional value iteration on the value function itself, the algorithm iterates on the "acceptance set"—the collection of Lipschitz functions that define the dual representation of the value function.

4. Unifying Variational Formulas

The utility of the proposed duality theorem extends into statistical physics and large deviations theory. The authors demonstrate that several well-known results are specific instances of their general theorem:

  • Donsker-Varadhan Variational Formula: A cornerstone of large deviations, shown here to be a consequence of the $W_1$ duality.
  • Bobkov-Götze Transportation Inequalities: These inequalities, which relate entropy and transport costs, emerge naturally from the conjugate duality framework.
  • Relative Entropy: The authors derive a new variational form for relative entropy that simplifies proofs in various statistical contexts.

5. Limitations and Future Directions

Despite the theoretical breakthrough, several challenges remain:

  • Computational Tractability: While the dual representation exists, the set of Lipschitz functions required may be uncountably infinite for continuous spaces. Practical implementation requires finding finite, representative subsets.
  • The $W_p$ Gap: The current results are strictly tied to the $W_1$ metric. Generalizing to $W_p$ for $p > 1$ remains an open problem, as the Arens-Eells construction does not have a straightforward $p$-version that preserves the required properties.
  • Neural Network Integration: The authors suggest that Wasserstein-based neural networks could potentially learn the "finite sets" of functions needed for the Set Iteration algorithm, offering a path toward scalable, point-based solvers for continuous POMDPs.

6. Conclusion

By reconciling the geometry of the Wasserstein space with the principles of convex duality, this work provides a rigorous foundation for both abstract analysis and practical stochastic control. It extends the reach of classical results like the Smallwood-Sondik theorem to the continuous domain, opening new avenues for approximating optimal policies in complex, uncertain environments.

Summary updated

BibTeX
@article{laschos2019fenchel,
  author = {Vaios Laschos and Klaus Obermayer and Yun Shen and Wilhelm Stannat},
  title = {{A Fenchel-Moreau-Rockafellar type theorem on the Kantorovich-Wasserstein space with applications in partially observable Markov decision processes}},
  journal = {Journal of Mathematical Analysis and Applications},
  year = {2019},
  doi = {10.1016/j.jmaa.2019.05.004},
}
Figure