Draw samples from distribitions in the neighborhood of a fixed distribution Disclaimer
Sorry in advance for vagueness. I'm still trying to get my ideas right on this one.
Setup
So, let $P$ be a distribution on a Euclidean space $X$ with an $\ell_p$ metric, and let $P_\epsilon$ be another distribution on $X$ whose Wasserstein distance (or KL diverence, for simplicity and as a starting point) from $P$ is at most $\epsilon$.
Question


*

*What is an effective way for sampling from $P_\epsilon$ given that sampling from $P$ is easy ? Alternative, how to compute expectations w.r.t $P_\epsilon$, i.e computing things like $\mathbb E_{x \sim P_\epsilon}[f(x)]$, or $\max_{P_\epsilon} \mathbb E_{x \sim P_\epsilon}[f(x)]$ for a smooth function $f$ ?

*Is this problem linked to another well-studied problem ?
 A: E.g., for the Wasserstein distance $W_1(P,Q)$ between two probability measures $P$ and $Q$ one has the following duality formula: 
\begin{equation}
 W_1(P,Q)=\sup\Big\{\Big|\int f\,dP-\int f\,dQ\Big|\colon \text{Lip}(f)\le1\Big\}, 
\end{equation}
where Lip$(f)$ is the Lipschitz constant for a function $f$. It then trivially follows that $|\int f\,dP_\epsilon-\int f\,dP|\le\epsilon$ for any $1$-Lipschitz function $f$ if $W_1(P_\epsilon,P)\le\epsilon$. (Of course, $\int f\,dP$ -- or simply $Pf$ or $P(f)$ -- is a simpler and better notation for what people in some research fields write as $\mathbb E_{x \sim P}[f(x)]$. If a  probability measure $\mathbb P$ is fixed, then it may be better to write $\mathbb Ef$ instead of $\int f\,d\mathbb P$.)
A: Maybe to add to the point of calculating $\max_{P_\varepsilon} \mathbb{E}_{P_\varepsilon}[f]$: I will write this a bit more in line with the literature I will refer to. Let $(X, d)$ be some polish space and a probability measure $\bar{\nu} \in \mathcal{P}(X)$ fix. Then the problem is
\begin{equation}
\Phi(f) :=\sup_{\nu \in \mathcal{P}(X):\\ W_1(\bar{\nu},\nu) \leq \varepsilon} \int f d\nu
\end{equation}
This problem is well studied, even for more general "transport distances" (Wasserstein distances but with more general cost functions, not just metrices).
More or less, one has a dual representation, which for the above example reads
\begin{equation}
\Phi(f) = \inf_{\lambda \geq 0}\left( \lambda \varepsilon + \int_{X} \sup_{y \in X} \left(f(y) - \lambda d(x,y)\right) \bar{\nu}(dx)\right).
\end{equation}
Aside from the fact that this can be numerically solved in some cases (see first source below), it also has a kind of sampling interpretation (This isn't in the literature I think, and more of a personal viewpoint):
To evaluate $\int f d\bar\nu$ one could of course simple sample points $x\sim \bar\nu$ and take as sample value $f(x)$.
To evaluate $\sup_{\nu \in \mathcal{P}(X):\\ W_1(\bar{\nu},\nu) \leq \varepsilon} \int f d\nu$, the duality formula motivates a similar scheme. Pretending that $\lambda$ is fix, one can sample points $x \sim \bar{\nu}$ and points $y_{x,1},...,y_{x,N}$ in a neighborhood of $x$ and take as one sample value $\sup_{i=1,...,N} f(y_{x,i}) - \lambda d(x,y_{x,i})$. (Finding $\lambda$ and including the term $\lambda \varepsilon$ must be done as well of course)
Sources:
https://link.springer.com/article/10.1007/s10107-017-1172-1 (first paper in this respect afaik, but not quite so general. Includes a linear programming formulation for the dual in case that $\bar\nu$ is sum of diracs) 
https://arxiv.org/pdf/1604.01446.pdf (more general duality, see Theorem 1)
An interesting extension is studied in https://arxiv.org/pdf/1706.10186.pdf (See Theorem 2.4 for the duality) which includes problems of the form
\begin{equation}
\sup_{\nu \in \mathcal{P}(X)} \int f d\nu - \varphi(W_1(\bar\nu,\nu))
\end{equation}
which reduces to $\Phi(f)$ if $\varphi(x) = \infty$ for $x \geq \varepsilon$ and $\varphi(x) = 0$, else.
