Dissimilarity-Based Markov Decision Processes for Stabilizing State Distributions

Xun Shen; Yuepeng Wang; Daniyal Sajedi-Hosseini; Akifumi Wachi; Ken Kawano; Yoshihiko Fujisawa; Mehrshad Sadria; Sébastien Gros

cs.LGOct 21, 2026

Dissimilarity-Based Markov Decision Processes for Stabilizing State Distributions

Authors: Xun Shen, Yuepeng Wang, Daniyal Sajedi-Hosseini, Akifumi Wachi, Ken Kawano, Yoshihiko Fujisawa, Mehrshad Sadria, Sébastien Gros,

Organizations: Tokyo University of Agriculture and Technology, Japan · LY Corporation, Japan · Institute of Science Tokyo, Japan · University of Waterloo, Canada ·

Abstract

Reinforcement learning for stochastic systems typically optimizes expected cumulative rewards, while reliable and repeatable behavior also depends on how the state distribution evolves over time. Optimizing expected return alone does not guarantee that this distribution converges to a desired target or remains stable. This paper develops a theoretical framework for learning policies that stabilize state distributions. We formulate the problem as a Dissimilarity-based Markov Decision Process (DMDP), in which the policy acts on the current state distribution and the objective measures its dissimilarity to a target distribution. We establish sufficient conditions under which the optimal policy makes the target distribution asymptotically stable. To support policy learning, we introduce a finite-dimensional representation of distributions and show how stability guarantees for its parameter dynamics extend to the underlying state distributions. We further develop certificates for the learned policies, including their deployment using estimated distribution parameters. These results quantify how learning and estimation errors affect the guarantees and identify conditions under which learned policies retain asymptotic stability. For practical implementation, we combine distribution estimates and target-dependent rewards with PPO and SAC. A computable example on a linear system illustrates the proposed theoretical certificates. Furthermore, experiments on a HalfCheetah task demonstrate the benefits of distribution feedback and explicit target matching for regulating the velocity distribution.

Figures & tables

Approach	Distribution cost	Distribution feedback	Distributional stability	Certified learned policies	Nonlinear dynamics	Infinite horizon
Norm-based MDPs ( Puterman, 1994 ; Sutton & Barto, 2018 )	✗	✗	✗	✗	✓	✓
Lyapunov-based learning control ( Perkins & Barto, 2002 ; Berkenkamp et al., 2017 ; Chang et al., 2019 )	✗	✗	✗	✓	✓	✓
Measure-functional MDPs ( Gros & Zanon, 2022 ; Kordabad & Gros, 2022 )	✓	( ✓ )	✓	✗	✓	✓
Mean-field MDPs and control ( Motte & Pham, 2022 ; Bäuerle, 2023 ; Carmona et al., 2023 )	✓	✓	✗	✗	✓	✓
Finite-horizon distribution steering ( Chen et al., 2016 ; Balci & Bakolas, 2021 )	✓	✗	✗	✗	✗	✗
Belief-state MDPs ( Kaelbling et al., 1998 )	✗	✓	✗	✗	✓	✓

Table 1: Comparison with related approaches ( ✓ : yes; ( ✓ ): not adopted but not excluded by the theory; ✗ : no).

Panel of Figure 1 — Figure 1: Norm-based MDP (a) and DMDP (b).

Panel of Figure 2 — Figure 2: Roadmap of the theoretical development.

Method	$\eta$	return $r^{\mathsf{eva}}_{t}$ $\uparrow$	cost $\downarrow$	$\mathbb{D}(\rho_{k}\\|\hat{\rho})$ $k<200$ $\downarrow$	$\mathbb{D}(\rho_{k}\\|\hat{\rho})$ $k\geq 500$ $\downarrow$	$\mathbb{D}(\hat{\rho}\\|\rho^{v}_{\star})$ $\downarrow$	$\mathbb{P}[\mathbb{D}(\bar{\rho}_{t}\\|\rho_{\star})$ $\leq\mathbb{D}_{\mathsf{thr}}]$ $\uparrow$
SAC	$0$	$461\pm 565$	$218.9\pm 126.1$	$0.47\pm 0.08$	$0.301\pm 0.065$	$0.98\pm 0.17$	$0.01\pm 0.01$
	$0.2$	$526\pm 616$	$205.4\pm 130.0$	$0.37\pm 0.07$	$0.197\pm 0.021$	$1.06\pm 0.17$	$0.02\pm 0.02$
SAC-Lag	$0$	$3802\pm 1920$	$6.8\pm 3.7$	$0.26\pm 0.02$	$0.155\pm 0.022$	$0.73\pm 0.23$	$0.23\pm 0.17$
	$0.2$	$3467\pm 1929$	$\bm{4.9\pm 2.2}$	$0.26\pm 0.03$	$0.155\pm 0.033$	$0.81\pm 0.24$	$0.21\pm 0.18$
Distributional	$0$	$819\pm 141$	$108.7\pm 48.7$	$0.36\pm 0.04$	$0.233\pm 0.026$	$0.96\pm 0.14$	$0.00\pm 0.00$
SAC	$0.2$	$837\pm 103$	$85.9\pm 35.3$	$0.33\pm 0.03$	$0.205\pm 0.018$	$1.03\pm 0.13$	$0.00\pm 0.00$

Table 2: Evaluation results with SAC.

Figure 3: Stable velocity distributions with SAC.

	end of training		evaluation, $\eta=0$		evaluation, $\eta=0.2$
Method	$\mathbb{P}[R\geq R_{\mathsf{Thr}}]$ $\uparrow$	10–90% range $\downarrow$	$\mathbb{P}[R\geq R_{\mathsf{Thr}}]$ $\uparrow$	10–90% range $\downarrow$	$\mathbb{P}[R\geq R_{\mathsf{Thr}}]$ $\uparrow$	10–90% range $\downarrow$
SAC	$0.00\pm 0.00$	$2231$	$0.00\pm 0.00$	$2154$	$0.00\pm 0.00$	$2373$
SAC-Lag	$0.00\pm 0.00$	$1303$	$0.00\pm 0.00$	$1365$	$0.00\pm 0.00$	$1310$
Distributional SAC	$0.00\pm 0.00$	$911$	$0.00\pm 0.00$	$1197$	$0.00\pm 0.00$	$957$
Distributional SAC-Lag	$0.00\pm 0.00$	$\bm{589}$	$0.00\pm 0.00$	$672$	$0.00\pm 0.00$	$\bm{586}$
Implicit DMDP (SAC)	$0.00\pm 0.00$	$1248$	$0.00\pm 0.00$	$685$	$0.00\pm 0.00$	$1104$

Table 3: Reliability of the return with SAC.

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: Counterexample for a point reflection.

Result	Hypothesis	Status	Evidence
All	closure; $\mathbb{D}$ -compatibility with $\alpha_{1}(r)=\alpha_{2}(r)=r^{2}$	exact	Gaussian AR(1); $\mathbb{D}=W_{2}^{2}=r^{2}$
All	$\Omega_{\mathsf{com}}$ compact and positively invariant under every closed loop	exact; for $\widehat{F}_{\mathsf{off}}$ by construction	Lemma 2 ; $\hat{f}_{\mathsf{off}}$ projected
Thm. 2	optimal $\phi_{\star}$ ; $U_{\star}^{\mathsf{R}}$ finite, continuous, Bellman identity; $F_{\phi_{\star}}(\omega_{\star})=\omega_{\star}$ ; $\kappa_{1}(r)=r^{2}$ , $\kappa_{2}(r)=2.56\,r^{2}$	exact	Lemma 2 ; $\max\tilde{U}/\mathbb{D}=1.57$
Thms. 3 – 5	$U_{\star}^{\mathsf{R}}$ and the sups over $\Omega_{\mathsf{com}}$	numerical	$\tilde{U}$ with $\varepsilon_{\mathrm{num}}=1.4\times 10^{-3}$ ; maxima over 11,822 points (20,016 for $e_{f}$ ); 80,000 independent points change $\Delta$ , $\hat{c}$ , $\Delta_{\mathsf{dec},n}$ of the deployed run by at most $1.9\%$
Thm. 3	$F_{\mathsf{off}}(\omega_{\star})=\omega_{\star}$	fails	offset $>0$ ; not used by ( 21 )
Thm. 3	learned margin with $\sigma(r)=0.75\,r^{2}$ ; $\Delta\leq\bar{\Delta}$ with probability $\geq 0.9$	computed; fails at $n_{\mathsf{tr}}=100$	per run; maximum of 49 runs, confidence $0.994$

Appendix

Table 4: Hypotheses in the example.

Data	$e_{f}$ or $\Delta_{\mathsf{dec},n}$ (median)	$\bar{\Delta}$ or $\bar{\Delta}_{\mathsf{dec},n}$	$\Delta_{\mathsf{on}}$ or $\Delta_{\omega,n}$	residual radius $\bar{r}$	smallest residual	limit distance	failed
Thm. 3 , offline
$n_{\mathsf{tr}}=100$	$0.22$	$\infty$	–	$\infty$	$1.0\times 10^{-3}$	$0.032$	5/50
$n_{\mathsf{tr}}=200$	$0.089$	$1.3$	–	$1.3$	$1.9\times 10^{-5}$	$4.2\times 10^{-3}$	0/50
$n_{\mathsf{tr}}=400$	$0.036$	$0.56$	–	$0.86$	$1.2\times 10^{-6}$	$1.0\times 10^{-3}$	0/50
$n_{\mathsf{tr}}=800$	$0.014$	$0.20$	–	$0.52$	$1.0\times 10^{-6}$	$9.2\times 10^{-4}$	0/50
Thm. 4 , online plug-in

Appendix

Table 5: Certificates of the learned policies.

Panel of Figure 7 — Figure 7: Practical implementation of DMDP.

Method	Policy input	Reward	Reward critic	Target
PPO / SAC	$\bm{\mathrm{o}}_{t}$	$r^{\mathsf{b}}_{t}$	expected return	–
PPO-Lag / SAC-Lag	$\bm{\mathrm{o}}_{t}$	$r^{\mathsf{b}}_{t}-\lambda c_{t}$	expected return	–
Distributional PPO / SAC	$\bm{\mathrm{o}}_{t}$	$r^{\mathsf{b}}_{t}$	$32$ quantiles of the return	–
Distributional PPO-Lag / SAC-Lag	$\bm{\mathrm{o}}_{t}$	$r^{\mathsf{b}}_{t}-\lambda c_{t}$	$32$ quantiles of the return	–
Implicit DMDP (PPO/SAC)	$\hat{\omega}_{t}$ and $\bm{\mathrm{o}}_{t}$	$r^{\mathsf{b}}_{t}$	$32$ quantiles of the return	–
Implicit DMDP-Lag (PPO/SAC)	$\hat{\omega}_{t}$ and $\bm{\mathrm{o}}_{t}$	$r^{\mathsf{b}}_{t}-\lambda c_{t}$	$32$ quantiles of the return	–

Appendix

Table 6: Compared methods.

Environment	SafetyHalfCheetahVelocity-v1 ( Ji et al., 2023 ) , MuJoCo ( Todorov et al., 2012 ) ; $H=1000$
$\bm{\mathrm{y}}_{t}$ , $\bm{\mathrm{a}}_{t}$	$\bm{\mathrm{y}}_{t}\in\mathbb{R}^{17}$ ; $\bm{\mathrm{a}}_{t}\in[-1,1]^{6}$
$v_{t}$ , $\theta_{t}$	torso velocity from $\bm{\mathrm{s}}_{t}$ to $\bm{\mathrm{s}}_{t+1}$ ; torso pitch of $\bm{\mathrm{s}}_{t+1}$ in $(-\pi,\pi]$
$r^{\mathsf{b}}_{t}$ , $c_{t}$	$v_{t}-0.1\\|\bm{\mathrm{a}}_{t}\\|^{2}$ ; $\mathbf{1}[v_{t}>v_{\mathsf{lim}}]$ , $v_{\mathsf{lim}}=3.2096$
$\rho_{\star}$	$U[0.70\,v_{\mathsf{lim}},0.95\,v_{\mathsf{lim}}]\otimes U[-0.2,0.2]$ ; $\omega_{\star}\approx(2.65,0.23,0,0.12)$
$\xi_{t,i}$ , $\eta$	i.i.d. $\tfrac{1}{2}\mathcal{N}(-0.8,0.6^{2})+\tfrac{1}{2}\mathcal{N}(0.8,0.6^{2})$ ; training: $\eta\sim U[0,0.3]$ per episode
$n_{\mathsf{w}}$	$10$

Appendix

Table 7: Task.

Figure 8: The HalfCheetah robot.

	PPO	SAC
Steps	$1464\times 8\times 256\approx 3\cdot 10^{6}$	$10^{6}$ ; $4$ envs; $1$ update/step; $5000$ random
Batches	$10$ epochs $\times$ $32$ minibatches	buffer $10^{6}$ ; minibatch $256$
Networks	$2\times 64$ , $\tanh$ ; normalized inputs	$2\times 256$ , ReLU
Policy	Gaussian, $\log\sigma_{0}=-1$	$\tanh$ -Gaussian, $\log\sigma\in[-5,2]$
Critics	$V_{r}$ , $V_{c}$ ; GAE $0.95$ ( Schulman et al., 2016 )	$Q_{1}$ , $Q_{2}$ , $Q_{c}$ ; Polyak $0.005$
Actor	clip $0.2$ on $\frac{\hat{A}^{r}_{t}-\lambda\hat{A}^{c}_{t}}{1+\lambda}$ ( Schulman et al., 2017 ; Ray et al., 2019 )	$\frac{\alpha\log\pi-\min_{i}Q_{i}+\lambda Q_{c}}{1+\lambda}$ ( Ha et al., 2021 )

Appendix

Table 8: Hyperparameters.

	$\mathbb{D}(\hat{\rho}_{\eta}\\|\hat{\rho}_{0})$ $\downarrow$
Method	$\eta=0.1$	$\eta=0.2$	$\eta=0.3$	$\eta=0.4$	$\eta=0.5$
SAC	$0.04\pm 0.01$	$0.12\pm 0.03$	$0.21\pm 0.03$	$0.48\pm 0.13$	$0.80\pm 0.26$
SAC-Lag	$0.04\pm 0.02$	$0.11\pm 0.03$	$0.21\pm 0.06$	$0.37\pm 0.08$	$0.57\pm 0.11$
Distributional SAC	$0.05\pm 0.02$	$0.13\pm 0.05$	$0.28\pm 0.11$	$0.40\pm 0.15$	$0.56\pm 0.19$
Distributional SAC-Lag	$\bm{0.03\pm 0.01}$	$\bm{0.09\pm 0.03}$	$\bm{0.17\pm 0.05}$	$\bm{0.27\pm 0.08}$	$\bm{0.39\pm 0.10}$
Implicit DMDP (SAC)	$0.20\pm 0.07$	$0.52\pm 0.15$	$0.89\pm 0.19$	$1.37\pm 0.22$	$2.10\pm 0.16$

Appendix

Table 9: Shift of the stable distribution under sensor noise with SAC.

with PPO
Method	$\eta=0$	$\eta=0.1$	$\eta=0.2$	$\eta=0.3$	$\eta=0.4$	$\eta=0.5$
PPO	$1.32$	$1.05$	$1.12$	$1.05$	$1.00$	$1.02$
PPO-Lag	$1.62$	$1.26$	$1.04$	$1.05$	$1.02$	$1.00$
Distributional PPO	$1.10$	$1.03$	$1.04$	$1.07$	$1.04$	$1.03$
Distributional PPO-Lag	$1.27$	$1.05$	$1.04$	$1.05$	$1.04$	$1.04$
Implicit DMDP (PPO)	$1.37$	$1.32$	$1.10$	$1.09$	$1.03$	$1.06$

Appendix

Table 10: Ratio to the stationary reference value.

Method	$\eta$	return $r^{\mathsf{eva}}_{t}$ $\uparrow$	cost $\downarrow$	$\mathbb{D}(\rho_{k}\\|\hat{\rho})$ $k<200$ $\downarrow$	$\mathbb{D}(\rho_{k}\\|\hat{\rho})$ $k\geq 500$ $\downarrow$	$\mathbb{D}(\hat{\rho}\\|\rho^{v}_{\star})$ $\downarrow$	$\mathbb{P}[\mathbb{D}(\bar{\rho}_{t}\\|\rho_{\star})$ $\leq\mathbb{D}_{\mathsf{thr}}]$ $\uparrow$
PPO	$0$	$-2207\pm 468$	$788.2\pm 93.6$	$0.92\pm 0.07$	$0.355\pm 0.113$	$1.86\pm 0.32$	$0.00\pm 0.00$
	$0.2$	$-454\pm 445$	$397.7\pm 109.9$	$0.92\pm 0.19$	$0.331\pm 0.033$	$1.33\pm 0.24$	$0.01\pm 0.00$
PPO-Lag	$0$	$9856\pm 1966$	$\bm{1.9\pm 1.4}$	$0.49\pm 0.03$	$0.174\pm 0.055$	$0.21\pm 0.02$	$0.78\pm 0.19$
	$0.2$	$6122\pm 1340$	$10.0\pm 2.2$	$\bm{0.46\pm 0.03}$	$0.205\pm 0.058$	$0.52\pm 0.13$	$0.45\pm 0.13$
Distributional	$0$	$-2293\pm 550$	$813.5\pm 113.6$	$1.08\pm 0.13$	$0.293\pm 0.038$	$1.93\pm 0.29$	$0.00\pm 0.00$
PPO	$0.2$	$-898\pm 450$	$448.4\pm 106.1$	$1.29\pm 0.21$	$0.504\pm 0.044$	$1.68\pm 0.18$	$0.00\pm 0.00$

Appendix

Table 11: Evaluation results with PPO.

Figure 10: Stable velocity distributions with PPO.

	end of training		evaluation, $\eta=0$		evaluation, $\eta=0.2$
Method	$\mathbb{P}[R\geq R_{\mathsf{Thr}}]$ $\uparrow$	10–90% range $\downarrow$	$\mathbb{P}[R\geq R_{\mathsf{Thr}}]$ $\uparrow$	10–90% range $\downarrow$	$\mathbb{P}[R\geq R_{\mathsf{Thr}}]$ $\uparrow$	10–90% range $\downarrow$
PPO	$0.00\pm 0.00$	$3653$	$0.00\pm 0.00$	$2150$	$0.00\pm 0.00$	$2828$
PPO-Lag	$0.00\pm 0.00$	$\bm{1402}$	$0.00\pm 0.00$	$592$	$0.00\pm 0.00$	$\bm{1129}$
Distributional PPO	$0.00\pm 0.00$	$3846$	$0.00\pm 0.00$	$2437$	$0.00\pm 0.00$	$3249$
Distributional PPO-Lag	$0.00\pm 0.00$	$1535$	$0.00\pm 0.00$	$\bm{383}$	$0.00\pm 0.00$	$1496$
Implicit DMDP (PPO)	$0.00\pm 0.00$	$3795$	$0.02\pm 0.02$	$753$	$0.00\pm 0.00$	$3140$

Appendix

Table 12: Reliability of the return with PPO.

	$\mathbb{D}(\hat{\rho}_{\eta}\\|\hat{\rho}_{0})$ $\downarrow$
Method	$\eta=0.1$	$\eta=0.2$	$\eta=0.3$	$\eta=0.4$	$\eta=0.5$
PPO	$0.58\pm 0.12$	$1.85\pm 0.20$	$2.71\pm 0.21$	$3.23\pm 0.29$	$3.56\pm 0.37$
PPO-Lag	$\bm{0.09\pm 0.01}$	$\bm{0.53\pm 0.10}$	$\bm{1.32\pm 0.19}$	$\bm{1.82\pm 0.20}$	$\bm{2.05\pm 0.14}$
Distributional PPO	$0.95\pm 0.27$	$2.15\pm 0.59$	$2.94\pm 0.52$	$3.46\pm 0.48$	$3.70\pm 0.47$
Distributional PPO-Lag	$0.12\pm 0.06$	$0.57\pm 0.18$	$1.42\pm 0.18$	$2.11\pm 0.11$	$2.34\pm 0.08$
Implicit DMDP (PPO)	$0.94\pm 0.32$	$2.96\pm 0.06$	$3.82\pm 0.18$	$3.96\pm 0.20$	$4.12\pm 0.17$

Appendix

Table 13: Shift of the stable distribution under sensor noise with PPO.

RL Control

Reinforcement learning control uses reward-driven learning to make decisions in dynamic systems, from robots and vehicles to energy and infrastructure.

See all 276 papers

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
Aug 6, 2026Yuepeng Yang, Yuxin Chen, Yuejie ChiRobust Markov Decision Processes Average-Reward RL
*Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.
On Distributional Reinforcement Learning in Chaotic Dynamical Systems
May 28, 2026James Rudd-Jones, Mirco Musolesi, María Pérez-OrtizDistributional RL Reinforcement Learning
Centre for Artificial Intelligence Department of Computer Science University College London London, UK · Department of Computer Science and Engineering, University of Bologna Bologna, Italy
Path-Coupled Bellman Flows for Distributional Reinforcement Learning
May 7, 2026Boyang Xu, Qing Zou, Siqin Yang +1Distributional RL Flow Matching
School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ, USA

Aug 6, 2026J/K move · Enter open · S save

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Yuepeng Yang, Yuxin Chen, Yuejie Chi

*Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.

Robust Markov Decision Processes Average-Reward RL Markov Models Minimax Estimation Distributionally Robust RL Sample-Efficient RL

Open paper AskPDF arXiv

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an

\varepsilon

-optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over

(s,a)

-rectangular total-variation uncertainty sets of radius at most

σ

. Let

H_0

and

H_σ

denote the nominal and robust optimal bias spans, respectively. We identify

σH_0

as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is

NSA \asymp \frac{SA}{\varepsilon^2}\begin{cases} \min\{H_0,H_σ\}, & \varepsilon\gtrsimσH_0,\\ \min\{H_0,H_σ\}+σH_σ^2, & \varepsilon\lesssimσH_0. \end{cases}

Here

S

and

A

are the numbers of states and actions, and

N

is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.

Abstract

RL Control

Explore similar work

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

On Distributional Reinforcement Learning in Chaotic Dynamical Systems

Path-Coupled Bellman Flows for Distributional Reinforcement Learning