Duality between density function and value function with applications in constrained optimal control and Markov Decision Process

Yuxiao Chen, Aaron D. AmesarXiv 2019 · OpenReview

Abstract

Density function describes the density of states in the state space of a dynamic system or a Markov Decision Process (MDP). Its evolution follows the Liouville equation. We show that the density function is the dual of the value function in the optimal control problems. By utilizing the duality, constraints that are hard to enforce in the primal value function optimization such as safety constraints in robot navigation, traffic capacity constraints in traffic flow control can be posed on the density function, and the constrained optimal control problem can be solved with a primal-dual algorithm that alternates between the primal and dual optimization. The primal optimization follows the standard optimal control algorithm with a perturbation term generated by the density constraint, and the dual problem solves the Liouville equation to get the density function under a fixed control strategy and updates the perturbation term. Moreover, the proposed method can be extended to the case with exogenous disturbance, and guarantee robust safety under the worst-case disturbance. We apply the proposed method to three examples, a robot navigation problem and a traffic control problem in sim, and a segway control problem with experiment.

Introduction

In classical optimal control, the objective is typically to find a control strategy that minimizes a cost-to-go, represented by a value function derived from the Hamilton-Jacobi-Bellman (HJB) equation. While effective for minimizing costs, this framework struggles with state-space constraints—such as ensuring a robot never enters a "danger zone" or maintaining traffic density below a saturation point. Enforcing these constraints directly on the value function is often mathematically intractable.

This research addresses this gap by establishing a formal duality between the value function and the density function, which measures the distribution of states over time. By shifting constraints to the density domain, the authors provide a robust framework for constrained optimal control and Markov Decision Processes (MDPs).

Theoretical Framework: The Duality of Flow

The core contribution of this work is the proof that the Liouville equation (governing density evolution) is the functional dual of the HJB equation (governing value evolution). In this paradigm, value flows "backward" from a goal state to determine optimal actions, while density flows "forward" from initial conditions to describe the system's presence in the state space.

This duality allows state-space constraints to be expressed naturally as limits on density. For instance, a safety constraint is simply a requirement that the density in a forbidden region remains zero. In the context of MDPs, this duality reveals that optimal policies under constraints may become stochastic to "split" density and satisfy capacity limits, even if the unconstrained problem is deterministic.

The Primal-Dual Algorithm

To solve these constrained problems, the authors propose an iterative primal-dual algorithm. The process alternates between optimizing the control strategy and updating a "perturbation" term (a Lagrange multiplier) that penalizes constraint violations.

Algorithm 1: The iterative primal-dual process for solving constrained optimal control problems.

As shown in Algorithm 1, the method involves:

  1. Primal Step: Solving for the optimal control $u^*$ given the current Lagrange multiplier $\sigma[j]$.
  2. Robust Extension: Identifying the worst-case disturbance $d^*$ to ensure safety under external noise.
  3. Dual Step: Computing the stationary density $\rho_s$ under the current strategy.
  4. Update: Adjusting the multiplier $\sigma$ based on where the density exceeds the allowed threshold $\rho^{\text{max}}$.

To overcome the "curse of dimensionality" in continuous systems, the authors utilize Kernel Density Estimation (KDE) with Epanechnikov kernels, allowing the density function to be estimated from simulations rather than requiring the direct solution of complex partial differential equations.

Experimental Validation

The framework was validated across three distinct domains:

  • 2D Robot Navigation: In simulations with disturbances half as strong as the control authority, the algorithm maintained zero density in danger zones, demonstrating robust safety.
  • Segway Obstacle Avoidance: Real-world experiments showed the algorithm converging in 223 iterations. The resulting controller enabled a Segway to tilt its body to avoid obstacles that standard Linear Quadratic Regulator (LQR) controllers would have struck.
  • Macroscopic Traffic Control: Applied to a 7-region urban traffic model, the algorithm successfully diverted traffic to prevent gridlock in a central bottleneck. While this increased total system cost by approximately 11%, it successfully kept density below critical thresholds.

Conclusion

By leveraging the duality between density and value, this work provides a principled way to handle complex state-space constraints in control and MDPs. The resulting "bump" in the value function around constrained regions acts as a virtual barrier, naturally steering the system toward safety. Future work aims to integrate this density-based approach with Reinforcement Learning, using the density function as a "safety critic" to provide formal guarantees during the learning process.

Summary updated

Abstract

Density function describes the density of states in the state space of a dynamic system or a Markov Decision Process (MDP). Its evolution follows the Liouville equation. We show that the density function is the dual of the value function in the optimal control problems. By utilizing the duality, constraints that are hard to enforce in the primal value function optimization such as safety constraints in robot navigation, traffic capacity constraints in traffic flow control can be posed on the density function, and the constrained optimal control problem can be solved with a primal-dual algorithm that alternates between the primal and dual optimization. The primal optimization follows the standard optimal control algorithm with a perturbation term generated by the density constraint, and the dual problem solves the Liouville equation to get the density function under a fixed control strategy and updates the perturbation term. Moreover, the proposed method can be extended to the case with exogenous disturbance, and guarantee robust safety under the worst-case disturbance. We apply the proposed method to three examples, a robot navigation problem and a traffic control problem in sim, and a segway control problem with experiment.
BibTeX
@misc{chen2019duality,
  author = {Yuxiao Chen and Aaron D. Ames},
  title = {{Duality between density function and value function with applications in constrained optimal control and Markov Decision Process}},
  year = {2019},
  eprint = {1902.09583},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.09583},
}
Figure