Dissimilarity-Based Markov Decision Processes for Stabilizing State Distributions

AI summary

Overview

Research area: Reinforcement learning and control theory for stochastic dynamical systems, specifically the stability of state distributions rather than expected returns.

Technical level: Advanced. The paper relies on measure-theoretic MDPs, class-𝒦 functions, Lyapunov stability, dissipativity, and cost rotation; it is aimed at readers comfortable with control-theoretic stability analysis.

Scope: The paper formulates a Dissimilarity-based Markov Decision Process (DMDP) in which the policy acts on the current state distribution, establishes conditions under which optimal and learned policies drive that distribution asymptotically to a target, and illustrates the framework on a linear system and a HalfCheetah task.

What This Paper Is About

Standard reinforcement learning maximizes expected cumulative reward, but an optimal expected return does not guarantee that the distribution of visited states converges to, or stays near, a desired distribution — two different distributions can share the same expected cost while the closed-loop distribution keeps oscillating. The authors therefore make the state distribution itself the decision state: the policy maps a probability measure to an action, and the cost measures dissimilarity (e.g., KL divergence or Wasserstein distance) to a target distribution. The goal is to characterize when the resulting optimal policy — and, crucially, policies learned from finite data — makes that target distribution asymptotically stable.

Key Contributions

1. Distribution-level formulation and optimal-policy stability. The paper defines the DMDP over the space of probability measures M(𝒮), with a stage cost such as 𝔻(ρ_k ‖ ρ*), and proves (Theorem 1, for γ = 1) sufficient conditions under which an optimal policy renders the target distribution 𝔻-asymptotically stable. Appendix B.1.2 shows the formulation recovers norm-based distributional stabilization whenever the corresponding distribution dynamics are representable by an admissible DMDP policy.

2. Transfer of Lyapunov certificates from parameters to distributions. A finite-dimensional parameterization ω ↦ ρ_ω (Assumption 1) reduces the problem to deterministic parameter dynamics ω_{k+1} = f(ω_k, a_k), and a "𝔻-compatible parameterization" condition (Assumption 2) bounds distributional dissimilarity between two class-𝒦 functions of parameter distance. Lemma 1 is a policy-independent certificate: any Lyapunov decrease in parameter space transfers to asymptotic stability of the induced distributions. Theorem 2 shows that, for the undiscounted problem, a dissipativity-based cost rotation makes the rotated optimal value U*^R a valid Lyapunov function.

3. Error-dependent certificates for learned policies. Theorems 3–5 extend the guarantee to policies learned offline with an approximate model, to their deployment using estimated distribution parameters, and to policies learned from transition data via an estimated Lyapunov decrease. Under high-probability uniform error bounds, the results quantify how approximation and estimation errors enter the Lyapunov decrease and determine residual sets; Proposition 1 establishes asymptotic recovery of the ideal optimizers as the data size N → ∞.

4. Computable illustration and empirical evaluation. Appendix D works out a linear-system example that numerically evaluates the certificates' error terms and residual sets. Section 4.5 combines sliding-window distribution estimates and target-dependent rewards with PPO (Schulman et al., 2017) and SAC (Haarnoja et al., 2018), with and without a safety-cost constraint, and Section 5 evaluates the approach on a HalfCheetah task.

Main Findings

• Optimal policies can be certified stable. Under Theorem 1's conditions — the optimal policy attains the optimal value for every initial distribution in the set 𝒫, 𝒫 is forward invariant under the closed loop, ρ* is a fixed point, and the stage cost and optimal value are bounded below/above by class-𝒦 functions of 𝔻(ρ_k ‖ ρ*) — the DMDP under the optimal policy is 𝔻-asymptotically stable for any initial distribution in 𝒫. The forward-invariance requirement is described as a mild well-posedness condition, e.g., a compact subset of M(𝒮) on which the closed-loop transition is well defined and positively invariant.

• Cost rotation preserves optimality. For γ = 1, subtracting ℓ₀ and adding the storage-function terms λ(ω) − λ(f(ω, a)) changes the undiscounted objective only by the initial storage term (a telescoping identity), so the set of optimal policies is unchanged while the rotated stage cost becomes a usable Lyapunov decrease.

• The rotated optimal value is a Lyapunov function. Theorem 2 shows that if U*^R is finite, nonnegative, continuous, satisfies the rotated Bellman identity, and meets the class-𝒦 bounds, then the optimal policy of the parameterized problem renders the induced distributions 𝔻-asymptotically stable. For the representative cost ℓ(ω, a) = 𝔻(ρ_ω ‖ ρ*), one has ℓ₀ = 0, so the storage function λ = 0 already works.

• Errors enter as an additive residual. The learned-policy guarantees take the form W(ω_{k+1}) − W(ω_k) ≤ −σ(‖ω_k − ω*‖) + Δ̄, where W is a Lyapunov function, σ a class-𝒦 decrease margin and Δ̄ collects error bounds. Asymptotic stability survives when the residual is zero or when state-dependent errors leave a strictly positive decrease margin away from the target; with a nonzero uniform residual, the guarantee degrades to a Lyapunov decrease outside an explicitly characterized residual set.

• The framework is the only one meeting all six comparison criteria. Table 1 rates approaches on distribution cost, distribution feedback, distributional stability, certified learned policies, nonlinear dynamics and infinite horizon. DMDP is the only row marked ✓ on all six; measure-functional MDPs lack certified learned policies, mean-field MDPs and belief-state MDPs lack distributional stability, and finite-horizon distribution steering lacks distribution feedback and an infinite horizon.

• Exactness of the parameterization is special, not general. The parameter dynamics are exact when the family is closed under the controlled transition — as with linear dynamics with additive Gaussian noise and a Gaussian family in Appendix D — but not, for example, for the product of uniform families under the HalfCheetah dynamics in Appendix E.

• HalfCheetah results are empirical only. The experiments provide evidence that distribution feedback and explicit target matching improve regulation toward a desired velocity distribution. The paper states explicitly that the Lyapunov certificates are examined only in the scalar example and are not established for the learned HalfCheetah policies. Specific numerical scores from Section 5 are not reported in the available text.

Methodology in Plain English

The authors start from an observation about randomness: in a stochastic system the realized state s_k is just one sample, while the distribution ρ_k is what the dynamics actually determine. So they build an MDP whose "state" is that distribution, whose "action" is chosen by looking at the distribution, and whose cost measures how far the distribution is from a target. Stability is then defined the Lyapunov way — small initial dissimilarity implies bounded dissimilarity forever, plus convergence to zero.

Two obstacles block direct use: the space of distributions is infinite-dimensional, and neither the distributions nor their evolution are known in practice. The authors handle the first by describing each distribution with a finite parameter vector (obtainable via kernel density estimation, Gaussian mixtures, normalizing flows, or neural density estimators) and the second by analyzing what happens when that description and the dynamics are estimated from finite trajectory data. A compatibility condition — parameter distance and distributional dissimilarity bound each other — is the bridge that lets a decrease proven in parameter space certify stability of the actual distributions.

For the undiscounted problem they borrow a trick from economic model predictive control: rotate the stage cost by a storage function so the rotated optimal value behaves like a Lyapunov function without changing which policies are optimal. Learned policies are then analyzed by writing the Lyapunov decrease as "guaranteed decrease minus an error term," which tells you exactly where the certificate still holds and where it lapses into a residual set. Practical agents are built by estimating the state distribution in a sliding window, forming target-dependent rewards, and training with PPO or SAC.

Why This Matters

Impact on research. The paper connects three strands that usually stay separate — measure-valued MDPs, dissipativity/turnpike theory extended to probability measures, and Lyapunov-based safe learning — and adds the missing piece: certificates that survive learning and estimation error. It reframes "did the policy work?" as "did the closed-loop distribution converge, and by how much can finite data and model error erode that guarantee?" Table 1 positions this as a gap no prior approach fills across all six criteria.

Real-world applications:

• Robotics locomotion and velocity regulation. The paper's motivating example: a robot's mean velocity says nothing about how often it exceeds a prescribed velocity limit — a distribution-level spec does.
• Safety-constrained control. The HalfCheetah experiments are run with and without a safety-cost constraint, pointing to settings where the frequency of constraint violations, not just the average cost, must be controlled.
• Manufacturing and process control, where repeatable behavior means the distribution of operating states concentrates in a high-quality region across runs.
• Simulation-to-reality deployment, where policies trained on approximate models must retain guarantees when the true dynamics and estimated distribution parameters differ.

Industry relevance. For companies deploying RL in physical systems, the value is a quantitative account of how model approximation and distribution-estimation error weaken a stability claim — the kind of statement needed before a learned controller is trusted outside simulation.

Future Directions

• Certifying learned policies on nonlinear benchmarks. The Lyapunov certificates are verified only on the linear scalar example; extending and empirically checking them for the HalfCheetah policies is an open step.
• Handling non-closed distribution families. The parameter dynamics are exact only when the family is closed under the controlled transition (true for Gaussian families under linear dynamics, not for uniform-product families under HalfCheetah), so bounding and reducing this closure error is a natural target.
• Tighter residual characterization. The current guarantees degrade to decrease outside a residual set when a uniform error residual is nonzero; sharpening these bounds or designing policies whose margins dominate realistic error levels would strengthen deployment claims.
• Scaling the parameterization. The theory is agnostic about how ρ_ω is represented (kernel density estimation, Gaussian mixtures, normalizing flows, neural density estimators), leaving open which representations best balance expressiveness, closure error, and compatibility with the 𝔻-compatibility condition.

Target Audience

Researchers and graduate students in reinforcement learning, optimal control, and stochastic stability who want distribution-level guarantees rather than expected-return guarantees; control engineers interested in Lyapunov and dissipativity arguments extended to probability measures; and practitioners working on safety-critical or repeatability-critical deployments who need to reason about how estimation and model error erode a learned policy's stability certificate. Readers without a control-theory background will find the theory sections demanding, though the problem motivation and the HalfCheetah setup are accessible.

Authors’ 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.