Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes

• URL: http://arxiv.org/abs/2604.02196v1
• Date: Thu, 02 Apr 2026 15:51:31 GMT
• Title: Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes
• Abstract summary: Many communication and control problems are cast as multi-objective decision processes (MOMDPs)<n>We show that the front is a continuous, piecewise-linear surface on the boundary of a convex polytope.
• Score: 6.760219793153785
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many communication and control problems are cast as multi-objective Markov decision processes (MOMDPs). The complete solution to an MOMDP is the Pareto front. Much of the literature approximates this front via scalarization into single-objective MDPs. Recent work has begun to characterize the full front in discounted or simple bi-objective settings by exploiting its geometry. In this work, we characterize the exact front in average-cost MOMDPs. We show that the front is a continuous, piecewise-linear surface lying on the boundary of a convex polytope. Each vertex corresponds to a deterministic policy, and adjacent vertices differ in exactly one state. Each edge is realized as a convex combination of the policies at its endpoints, with the mixing coefficient given in closed form. We apply these results to a remote state estimation problem, where each vertex on the front corresponds to a threshold policy. The exact Pareto front and solutions to certain non-convex MDPs can be obtained without explicitly solving any MDP.

Related papers

• A Single Deep Preference-Conditioned Policy for Learning Pareto Coverage Sets [0.4369550829556578]
  We study the uniqueness and continuity of the preference-to-solution correspondence under nonlinear scalarization.<n>We use smooth Tchebycheff scalarization as a monotone utility to solve the problem.<n>We show that each update is equivalent to solving a Kullback-Leibler-regularized MDP with the previous policy as reference.
  arXiv  Detail & Related papers  (2026-05-09T13:35:50Z)
• Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing [51.30643063554434]
  A leading technique for upper bounds, the three-point method, reduces the problem to solving large, high-precision semidefinite programs (SDPs)<n>We formulate SDP construction as a sequential decision process, the SDP game, in which a policy assembles SDP formulations from a set of admissible components.<n>We obtain new state-of-the-art upper bounds in dimensions $4-16$, showing that model-based search can advance computational progress in longstanding geometric problems.
  arXiv  Detail & Related papers  (2025-12-04T14:11:52Z)
• Scalable Policy-Based RL Algorithms for POMDPs [6.2229686397601585]
  We consider an approach that solves a Partially Observable Reinforcement Learning (PORL) problem by approximating a POMDP model into a finite-state Markov Decision Process (MDP)<n>We show that the approximation error decreases exponentially with the length of this history.<n>To the best of our knowledge, our finite-time bounds are the first to explicitly quantify the error introduced when applying standard TD learning to a setting where the true dynamics are not Markovian.
  arXiv  Detail & Related papers  (2025-10-08T00:33:38Z)
• How to Find the Exact Pareto Front for Multi-Objective MDPs? [28.70863169250383]
  Multi-Objective Markov Decision Processes (MO-MDPs) are receiving increasing attention, as real-world decision-making problems often involve conflicting objectives that cannot be addressed by a single-objective MDP.<n>In this work, we address the challenge of efficiently discovering the Pareto front.<n>By investigating the geometric structure of the Pareto front in MO-MDPs, we uncover a key property.<n>This insight transforms the global comparison across all policies into a localized search among deterministic policies that differ by only one state-action pair.
  arXiv  Detail & Related papers  (2024-10-21T01:03:54Z)
• Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form [26.01796404477275]
  This paper presents the first algorithm guaranteed to identify a near-optimal policy in a robust constrained MDP (RCMDP)<n>An optimal policy minimizes cumulative cost while satisfying constraints in the worst-case scenario across a set of environments.
  arXiv  Detail & Related papers  (2024-08-29T06:37:16Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours.<n>We focus on the case of linear utility functions parametrised by weight vectors w.<n>We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
  We present the first finite time global convergence analysis of policy gradient in the context of average reward Markov decision processes (MDPs) Our analysis shows that the policy gradient iterates converge to the optimal policy at a sublinear rate of $Oleft(frac1Tright),$ which translates to $Oleft(log(T)right)$ regret, where $T$ represents the number of iterations.
  arXiv  Detail & Related papers  (2024-03-11T15:25:03Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  We study the problem of computing an optimal policy of an infinite-horizon discounted Markov decision process (constrained MDP) We develop two single-time-scale policy-based primal-dual algorithms with non-asymptotic convergence of their policy iterates to an optimal constrained policy. To the best of our knowledge, this work appears to be the first non-asymptotic policy last-iterate convergence result for single-time-scale algorithms in constrained MDPs.
  arXiv  Detail & Related papers  (2023-06-20T17:27:31Z)
• First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
  We consider the problem of solving robust Markov decision process (MDP) MDP involves a set of discounted, finite state, finite action space MDPs with uncertain transition kernels. For $(mathbfs,mathbfa)$-rectangular uncertainty sets, we establish several structural observations on the robust objective.
  arXiv  Detail & Related papers  (2022-09-21T18:10:28Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  We consider the optimal expected total reward to reach a goal state in a partially observable Markov decision process (POMDP) We use mixed-integer linear programming (MILP) to find such minimal probability shifts and experimentally show that our techniques scale quite well.
  arXiv  Detail & Related papers  (2022-01-21T16:43:03Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  We derive a novel problem-dependent lower-bound for regret in finite-horizon Markov Decision Processes (MDPs) We show that our lower-bound is considerably smaller than in the general case and it does not scale with the minimum action gap at all. We show that this last result is attainable (up to $poly(H)$ terms, where $H$ is the horizon) by providing a regret upper-bound based on policy gaps for an optimistic algorithm.
  arXiv  Detail & Related papers  (2021-06-24T13:46:09Z)
• Reward is enough for convex MDPs [30.478950691312715]
  We study convex MDPs in which goals are expressed as convex functions of the stationary distribution. We propose a meta-algorithm for solving this problem and show that it unifies many existing algorithms in the literature.
  arXiv  Detail & Related papers  (2021-06-01T17:46:25Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.