Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes
arXiv:2604.02196v1 [eess.SY] 2 Apr 2026
Jiping Luo and Nikolaos Pappas 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.
I. I NTRODUCTION Achieving a desired trade-off among multiple conflicting objectives is fundamental in many communication and control systems [1]–[4]. In practice, there is rarely a free lunch: performance improvements are often achieved at the expense of increased resource consumption. Many such problems are cast as Markov decision processes (MDPs). An MDP is a controlled Markov chain with state process {Xt }t≥1 evolving on a state space X, action process {Ut }t≥1 taking values in an action set U, and one-stage cost c(Xt , Ut ) incurred at time t. At each time t, an action Ut is taken according to a decision rule Ut ∼ πt (·|It ), where It = {X1:t , U1:t−1 } denotes the history prior to decision epoch t. The γ-discounted optimal control problem seeks a policy π = {πt }t≥1 that minimizes the objective function ∞ X Jβγ (π) := γ t−1 Eπ c(Xt , Ut ) | X1 ∼ β , (1) t=1
where γ ∈ (0, 1) is the discount factor, and β is the initial state distribution. In many applications [5]–[8], the averagecost criterion is more appropriate T 1 X π Jβ (π) := lim sup E c(Xt , Ut ) | X1 ∼ β . T →∞ T t=1
The main conceptual difficulty is that, because the objectives may be conflicting, there typically does not exist a single policy that minimizes all components of J β (π). Instead, optimality is defined in the Pareto sense. A policy π ∗ is Pareto optimal if there does not exist any other policy π such that Jβ,k (π) ≤ Jβ,k (π ∗ ) for all k = 1, . . . , K,
and Jβ,i (π) < Jβ,i (π ) for at least one index i. The complete solution to an MOMDP is the set of all Pareto optimal policies, whose objective vectors form the Pareto front. Much of the literature operates under the view that computing the exact Pareto front is computationally intractable except for very small problems [9]–[13]. Most studies approximate the front using linear scalarization methods [12]. Let w = (w1 , . . . , wK ) denote a weight vector representing the user’s preference over the objectives. This method seeks to minimize Jβ (π; w) = ⟨w, J β (π)⟩, (5) P where ⟨a, b⟩ = i ai bi denotes the inner product. Clearly, the scalarized problem is a single-objective MDP with additive cost cw (x, u) = ⟨w, c(x, u)⟩. This makes the approach particularly attractive, as it allows standard dynamic programming (DP) or reinforcement learning (RL) techniques to generate some representative Pareto-optimal policies. However, this method has two main limitations. First, traversing all weight vectors is neither tractable nor sufficient to construct the entire Pareto front [14]. Second, many applications exhibit nonlinear relationships among the objectives [12]. For example, increasing communication frequency accelerates hardware aging superlinearly [7], resulting in additional maintenance costs or reduced equipment longevity that cannot be adequately captured by linear weights. Let f : RK → R denote a nonlinear scalarization function. The nonlinear scalarized problem seeks to minimize Jβ (π; f ) = f (J β (π)).
(2)
A multi-objective MDP (MOMDP) considers multiple costs. Let c(Xt , Ut ) = (c1 (Xt , Ut ), . . . , cK (Xt , Ut )) denote the one-stage cost vector, and let Jβ,k (π) denote the kth objective. The goal is to minimize the objective vector J β (π) = Jβ,1 (π), . . . , Jβ,K (π) . (3) This work has been supported by ELLIIT, CUGS, and 6G-LEADER. J. Luo and N. Pappas are with the Department of Computer and Information Science, Linköping University, Linköping 58183, Sweden. Emails: [email protected] and [email protected].
(4)
∗
(6)
Classical DP methods cannot handle such nonlinear scalarized MDPs because nonlinear scalarization breaks the additivity required by the Bellman equation [12]. This work studies the exact Pareto front in MOMDPs. The recent papers [14] and [15] investigate related problems in different settings; [14] analyzes an average-cost bi-objective MDP via DP and Pareto analysis, while [15] studies a γdiscounted MOMDP using linear scalarization and DP. In contrast, we focus on average-cost MOMDPs using occupancy measures and linear programming (LP). Our main contributions are as follows.
(1) We characterize the geometry of the Pareto front in average-cost MOMDPs. Under standard assumptions, the set of achievable objective vectors forms a convex polytope, and the Pareto front is a continuous, piecewise linear surface lying on the boundary of this polytope. Each vertex of the polytope corresponds to a deterministic policy, and policies at adjacent vertices differ in exactly one state. Each edge is realized by a convex combination of the policies at its endpoints, and the mixing coefficient is given in closed form. (2) We show that for nonlinear scalarized MDPs, if the scalarization function f is strictly increasing, the optimal solution lies on the Pareto front and can be realized as a convex combination of at most K deterministic policies. (3) We apply these results to a remote state estimation problem, in which each vertex on the Pareto front corresponds to a threshold policy. We show that the exact Pareto front and the optimal solution to the nonlinear scalarized MDP can be obtained without explicitly solving any MDP. Organization: Section II presents preliminaries on MDPs and occupancy measures. Our main results are summarized in Section III, and a remote estimation example is examined in Section IV. Proofs are provided in the Appendix. II. P RELIMINARIES A. MDP An average-cost MOMDP is a tuple (X, U, P, c, β), where X and U denote the state and action spaces, β is the initial state distribution, and c(x, u) = (c1 (x, u), . . . , cK (x, u)) is the cost vector. The transition kernel P governs the evolution of the state process, where P(x, u, x′ ) is the probability of transitioning from state x to x′ given action u. The objective vector under a policy π, J β (π), is defined in (2)–(3). A linear scalarized MDP with weight vector w is described by the tuple (X, U, P, cw , β), where cw (x, u) = ⟨w, c(x, u)⟩. Next, we introduce several policy classes that will be used throughout the paper. Let Π denote the set of all admissible policies, which may be history-dependent and non-stationary. We define the following subclasses: • ΠM : Markov policies; π ∈ ΠM if it depends on the history It only through Xt , i.e., Ut ∼ πt (·|Xt ). • ΠS : Markov stationary policies; π ∈ ΠS if it uses the same rule at all times, i.e., Ut ∼ π(·|Xt ). • ΠD : Markov stationary deterministic policies; π ∈ ΠD if it selects an action with certainty, i.e., Ut = π(Xt ). Clearly, ΠD ⊂ ΠS ⊂ ΠM ⊂ Π. For clarity, we refer to policies in ΠS as stationary and those in ΠD as deterministic. Moreover, two deterministic policies π1 , π2 ∈ ΠD are said to be adjacent if they differ in exactly one state; that is, there exists a state i0 ∈ X such that π1 (x) = π2 (x) for all x ̸= i0 and π1 (i0 ) ̸= π2 (i0 ). For any Π̄ ⊆ Π, let JβΠ̄ := {J β (π) : π ∈ Π̄}
(7)
denote the set of objective vectors achievable by Π̄. Definition 1: P is unichain if for P every π ∈ ΠS , {Xt } governed by Pπ , where Pπ (x, x′ ) = u π(u|x)P(x, u, x′ ), forms a Markov chain with a single recurrent class.
Unless otherwise stated, it is assumed in this paper that Assumption 1: X and U are finite sets and P is unichain. We now introduce a class of mixing policies that will play an important role in our analysis. Definition 2: Let α ∈ (0, 1) and π1 , π2 ∈ ΠS . Then π = απ1 + (1 − α)π2 ∈ ΠS is called a mixing policy. It is called a simple mixing policy if π1 , π2 ∈ ΠD and they are adjacent. For any simple mixing policy, randomization occurs only at state i0 (where π1 and π2 differ). As a result, {Xt } forms a regeneration process with regeneration events defined by the successive returns to i0 . The sample path can therefore be decomposed into i.i.d. cycles, the expected length of which is determined by the selected policy. B. Occupancy Measure For any policy π and initial distribution β, define the stateaction frequency up to time t by t
1X π P (Xn = x, Un = u), (8) t n=1 β P t and the state frequency by µtβ,π (x) := u∈U µβ,π (x, u). t t The vector µβ,π = (µβ,π (x, u) : x ∈ X, u ∈ U) is called the finite-horizon occupancy measure. We define the (limiting) occupancy measure under π and β as the set of all subsequential limits of {µtβ,π }, i.e., n Γπβ := lim µtβ,π : {tn } ⊆ N with tn → ∞ . (9) µtβ,π (x, u) :=
n→∞
The limits are defined componentwise. Subsequential limits are used because the ordinary limit limt→∞ µtβ,π need not exist for non-stationary policies. When the limit does exist, we denote it by µβ,π . For any Π̄ ⊆ Π, the set of occupancy measures achievable under policies in Π̄ is denoted by [ ΓΠ̄ Γπβ . (10) β := π∈Π̄
For brevity, we denote the full set as Γβ = ΓΠ β. The following lemma characterizes the existence of the ordinary limit (see, e.g., [16, Ch. 3.4]). Lemma 1: Γπβ is non-empty for all π ∈ Π. The largest and smallest subsequential limits are sup(Γπβ ) = lim sup µtβ,π and inf(Γπβ ) = lim inf µtβ,π . t→∞
t→∞
Moreover, the ordinary limit limt→∞ µtβ,π exists if and only if Γπβ is a singleton, i.e., sup(Γπβ ) = inf(Γπβ ) = µβ,π . For stationary policies, we have the following property. Lemma 2: For any π ∈ ΠS , Γπβ = {µπ } for all β, where µπ (x, u) = νπ (x)π(u|x),
(11)
and νπ is the stationary distribution of {Xt } under π. Lemma 2 implies that under any stationary policy π ∈ ΠS , each objective Jβ,k (π) is independent of β and can be expressed linearly via the occupancy measure µπ as X Jk (π) = ⟨µπ , ck ⟩ := µπ (x, u)ck (x, u). (12) x,u
For a general non-stationary policy π, the sequence {µtβ,π } may not converge, and Γπβ is not a singleton. As a result, the average cost satisfies Jβ,k (π) ≥ ⟨µ, ck ⟩ for all µ ∈ Γπβ . III. P ROPERTIES OF THE PARETO F RONT A. Geometric Results This section establishes geometric properties of the set of occupancy measures and the set of objective vectors. We begin by introducing an auxiliary set Φ ⊂ R|X||U| , which underpins our subsequent analysis. The set Φ is defined as ϕ(x, u) : (x, u) ∈ X × U, X X ′ ′ ′ ϕ(x , u)= ϕ(x, u)P(x, u, x ), x ∈ X, Φ:= (13) u x,u X ϕ(x, u)=1, ϕ(x, u) ≥ 0, (x, u) ∈ X × U x,u
P We write the marginal over states as ϕ(x) = u ϕ(x, u). A useful property of Φ is the following. Lemma 3: Φ is a convex polytope. The following standard definitions are needed. Definition 3: Let P ⊂ RD denote a D-dimensional polytope defined by the intersection of a finite number of linear constraints. A point p ∈ P is a vertex (or extreme point) of P if it cannot be expressed as a convex combination of two other points in P; that is, there do not exist p1 , p2 ∈ P, p1 ̸= p2 , and α ∈ (0, 1) such that p = αp1 + (1 − α)p2 . Let V(P) denote the set of vertices of P. Each vertex corresponds to at least D active constraints, among which D are linearly independent. Two vertices are adjacent if there exists a set of D − 1 linearly independent constraints that are active at both vertices. For any v ∈ V(P), let N (v) ⊂ V(P) denote the set of vertices adjacent to v. For any v ′ ∈ N (v), the line segment joining v and v ′ is an edge of P, denoted by G(v, v ′ ). A subset F ⊂ P is a face of P if there exists a c ∈ RD such that F = arg minp∈P ⟨c, p⟩. Any proper face of P has dimension 0 ≤ d ≤ D − 1. A 0-dimensional, 1dimensional, and (D − 1)-dimensional face is a vertex, an edge, and a facet, respectively. The boundary of P is the union of all its proper faces. The operation conv(S) denotes the convex hull of a set of points S ⊆ P. A main result of this section follows. Theorem 1(a) establishes the equivalence between the set of occupancy measures Γβ and the auxiliary set Φ. Theorem 1(b)–(d) further elucidate the relationships between deterministic policies and the vertices, adjacent vertices, and edges of Φ. Theorem 1: Γβ and Φ have the following properties: ΠD S (a) For all β, Γβ = ΓΠ β = conv(Γβ ) = Φ. Each µ ∈ Γβ is realizable by a stationary policy πµ ∈ ΠS , where ( µ(x, u)/µ(x), µ(x) > 0, πµ (u|x) = (14) arbitrary, µ(x) = 0. D (b) V(Φ) = ΓΠ for any β. β (c) Any two adjacent vertices of Φ differ in one state.
(d) Let ϕ1 , ϕ2 ∈ V(Φ) be adjacent vertices differing in state i0 , and let πϕ1 , πϕ2 ∈ ΠD denote the corresponding deterministic policies. Each ϕ ∈ G(ϕ1 , ϕ2 ), i.e., ϕ = bϕ1 + (1 − b)ϕ2 for b ∈ (0, 1), can be realized by a simple mixing policy π = απϕ1 + (1 − α)πϕ2 , where bνπϕ1 (i0 ) . (15) bνπϕ1 (i0 ) + (1 − b)νπϕ2 (i0 ) Note that Theorem 1(a) does not imply a one-to-one correspondence between the set of policies Π and the set of occupancy measures Φ. While each stationary policy π ∈ ΠS produces a unique occupancy measure µπ ∈ Φ, some history-dependent non-stationary policies may yield the same occupancy measure. Conversely, every occupancy measure µ ∈ Φ can be realized by some stationary policy πµ ∈ ΠS defined by (14), though the choice is not unique. Theorem 1(a) implies that there is no loss of optimality in restricting attention to stationary policies. Consequently, solving the (MO)MDP over the full policy space Π is equivalent to solving an (MO)LP over the convex polytope Φ. Formally, a linear scalarized MDP is equivalent to the LP α=
min J(ϕ; w) = ⟨ϕ, cw ⟩. ϕ∈Φ
(16)
An MOMDP can be expressed as the MOLP min J (ϕ) = J1 (ϕ), . . . , JK (ϕ) , ϕ∈Φ
(17)
where Jk (ϕ) = ⟨ϕ, ck ⟩. We will write J(ϕ; w) = ⟨w, J (ϕ)⟩. Lemma 4: J : Φ → RK is a linear mapping. Let J Φ = {J(ϕ) : ϕ ∈ Φ} denote the set of achievable objective vectors. We denote by V ∗ (Φ) ⊆ V(Φ) the set of Pareto optimal vertices, and by N ∗ (ϕ) = N (ϕ) ∩ V ∗ (Φ) the set of Pareto optimal vertices adjacent to vertex ϕ ∈ V(Φ). The following result summarizes the key structural properties of J Φ and the Pareto front. Theorem 2(a) implies that any vertex of J Φ is induced by a vertex of Φ, but the converse may not hold. Theorem 2(c)–(f) establish that the Pareto front is a continuous, piecewise linear surface that lies on the boundary of the convex polytope J Φ . Theorem 2: The Pareto front has the following properties: (a) J Φ is a convex polytope in RK and V(J Φ ) ⊆ J V(Φ) . (b) For all β, JβΠ = JβΠS = conv(JβΠD ) = J Φ . (c) The Pareto front lies on the boundary of J Φ . (d) Each ϕ ∈ V ∗ (Φ) minimizes J(ϕ; w) for some w ≻ 0. (e) Each ϕ ∈ V ∗ (Φ) has at least one adjacent Pareto optimal vertex, i.e., 1 ≤ |N ∗ (ϕ)| ≤ |X|(|U| − 1). (f) Let ϕ, ϕ′ ∈ V ∗ (Φ) be adjacent Pareto optimal vertices. Then the edge G(ϕ, ϕ′ ) lies on the Pareto front. The vertices and edges constitute the 1-skeleton of the Pareto front. Crucially, policies on this skeleton are quasideterministic: any point on an edge can be realized by a simple mixing policy that randomizes in at most a single state, and the mixing coefficient is given in closed form. Although the full front consists of higher-dimensional faces, the skeleton provides a sufficient representative solution set because (i) the associated policies are easy to compute and implement; (ii) any optimal solution to a linear scalarized
Process
Fig. 1.
Zt
Ẑtloc
Sensor
Channel
Receiver
Ẑt
Remote state estimation of a linear Gaussian process.
MDP is attained at a vertex; and (iii) every point on the Pareto front is a convex combination of these vertices. We show in the next subsection, however, that an optimal solution for a general nonlinear scalarized MDP may reside within the interior of a face. In such cases, the optimal policy may require randomizing in up to K states, necessitating a more comprehensive search over the full Pareto front. B. Scalarized MDPs In general, the scalarization function f is assumed to be strictly increasing (but not necessarily convex). The intuition is that the user’s preference improves if the cost of one objective decreases while the other objective values remain unchanged. Definition 4: The scalarization function f is said to be strictly increasing if for any objective vectors J , J ′ ∈ J Φ such that J ⪯ J ′ and J ̸= J ′ , it holds that f (J ) < f (J ′ ). The next theorem shows that we can restrict attention to the Pareto front when solving nonlinear scalarized MDPs. Theorem 3: Let f be strictly increasing and let π ∗ be an optimal policy for the scalarized MDP. Then π ∗ is Pareto optimal and can be represented as a convex combination of at most K Pareto-optimal deterministic policies. Proof: Suppose π ∗ is not Pareto optimal. Then there exists an objective vector J β (π) that strictly dominates J β (π ∗ ), i.e., J β (π) ⪯ J β (π ∗ ) and J β (π) ̸= J β (π ∗ ). Since f is strictly increasing, we have f (J β (π)) < f (J β (π ∗ )). This contradicts the optimality of π ∗ for the scalarized problem. Thus, π ∗ is Pareto optimal. Recall from Theorem 2 that the Pareto front lies on the boundary of the K-dimensional convex polytope J Φ . Each face of J Φ has dimension d ≤ K − 1. By Carathéodory’s theorem [17, Sec. 17], any point in a d-dimensional face can be expressed as a convex combination of at most d + 1 vertices of that face. Since each vertex of J Φ corresponds to a deterministic policy, π ∗ can be represented as a mixture of at most K Pareto-optimal deterministic policies. IV. C ASE S TUDY: R EMOTE E STIMATION OF L INEAR G AUSSIAN P ROCESSES A. Problem Description In this section, we apply our structural results to a remote estimation problem, e.g., [5]–[7]. Consider a point-to-point communication system depicted in Figure 1, where a sensor observes a linear Gaussian process Zt+1 = AZt + Wt , where Zt ∈ Rn is the system state at time t, A ∈ Rn×n is the state transition matrix, and Wt ∈ Rn is zero-mean Gaussian process noise with covariance Q ⪰ 0. The sensor measurements are given by Yt = CZt + Vt , where C ∈
Rm×n is the measurement matrix and Vt ∈ Rm is zeromean Gaussian measurement noise with covariance R ≻ 0. The sensor employs a steady-state Kalman filter to produce a local estimate Ẑtloc with a constant error covariance K̄. Due to energy constraints, the sensor can transmit only intermittently. Let Ut ∈ {0, 1} denote the sensor’s action: the sensor sends the local estimate Ẑtloc to the receiver when Ut = 1 and remains silent when Ut = 0. We assume an i.i.d. packet-dropping channel {Ht }, where each transmitted packet is successfully delivered with probability E[Ht ] = ps . The sensor is aware of the channel outcome through a feedback link. The receiver’s estimate then evolves as Ẑt = Ut Ht Ẑtloc + (1 − Ut Ht )AẐt−1 . Let Xt := t − max{τ ≤ t : Uτ = 1} denote the time elapsed since the last successful status update. To avoid technicalities, we impose Xt = min{Xt , Xmax }. The error covariance at the receiver is then given by Kt = Ut Ht K̄ + (1 − Ut Ht )(AKt−1 A⊤ + Q). Moreover, we can write Tr(Kt ) = η(Xt ), where η : N → R is an increasing function parametrized by K̄, A, and Q. The goal is to find a communication policy π that balances the average estimation error J1 (π) and the average communication rate J2 (π), where J1 (π) := lim sup T →∞
J2 (π) := lim sup T →∞
T 1 X π E η(Xt ) | X1 = 0 , T t=1 T 1 X π E Ut | X1 = 0 . T t=1
A common approach to characterize this trade-off is linear scalarization [6], [7], i.e., min J(π; λ) = J1 (π) + λJ2 (π), π∈Π
where λ > 0 denotes the cost per transmission. Lemma 5 ([6]): Let ∥A∥2 (1 − ps ) < 1. Then the optimal policy π ∗ for the linear scalarized MDP is a threshold policy; that is, π ∗ (x) = 1 if x ≥ xth and π ∗ (x) = 0 otherwise. However, this approach has two key limitations: it yields only a single policy for each preference configuration and fails to capture nonlinear operational costs. For instance, frequent communication may accelerate hardware aging and reduce link reliability. We therefore study two alternative formulations. The first is the MOMDP min J (π) = J1 (π), J2 (π) . π∈Π
The second is a nonlinear scalarization min f (J (π)) = J1 (π) + ρ(J2 (π)), π∈Π
where ρ : [0, 1] → R is a strictly increasing function.
350
120 ps = 0.3 ps = 0.6 ps = 0.9
80 60 40 λ=178.1 λ=108.7 xth = 4 xth = 3
20 0 0.0
0.2
0.4
0.6
0.8
ps = 0.3 ps = 0.6 ps = 0.9
300
Total cost J1 + ρ(J2)
Estimation error J1
100
250 200
Optimal
150 100 50 0 0.0
1.0
0.2
Fig. 2.
Pareto front of the estimation system.
B. Analysis and Numerical Results From Theorem 2, the Pareto front is a piecewise linear, convex curve in the 2D objective plane. Each vertex corresponds to a deterministic policy that solves the linear scalarized MDP for some λ > 0. Lemma 5 implies that, although each vertex has Xmax adjacent policies, only two neighboring threshold policies need to be evaluated. Hence, the Pareto front forms a directed path along the boundary of the polytope and can be computed without solving any MDP. These results are illustrated using the following example. Consider the pendubot system in [18], where 1.0058 0.0150 −0.0016 0.0000 0.7808 1.0058 −0.2105 −0.0016 , A= −0.0060 0.0000 1.0077 0.0150 −0.7962 −0.0060 1.0294 1.0077 1 0 0 0 C= , Q = qq ⊤ , R = 0.001 × I, 0 0 1 0 ⊤ q = 0.003 1 −0.005 −2.150 . Figure 2 illustrates the Pareto front of the above system. The absolute slope (λ) reflects the value of communication: its marginal benefit diminishes at high communication rates, while careful calibration is critical when communication is scarce. For ps = 0.3 and λ ∈ (108.7, 178.1), a single vertex (filled black square) attains the global optimum for all λ in this interval. This highlights that linear scalarization is inefficient, as it requires sweeping over a wide range of weights to recover different parts of the front. Moreover, any point on an edge can be obtained by mixing two adjacent threshold policies. Figure 3 shows the total cost on the Pareto front with a sigmoid penalty ρ(J2 ) = 200/(1 + exp(−17(x − 0.6))). The optimal policy is found at an edge of the Pareto front. A PPENDIX I P ROOF OF L EMMA 2 Let π ∈ ΠS be a stationary policy. Then the state process {Xt } governed by Pπ forms a time-homogeneous Markov chain. By the Chapman-Kolmogorov equations, Pπ (Xn = x|X1 = i) = Pn−1 (x|i). π
0.4
0.6
0.8
1.0
Communication rate J2
Communication rate J2 Fig. 3.
Achievable total cost for the nonlinear scalarized problem.
We may write the finite-horizon state-action frequency as t
µtβ,π (x, u) =
1 XX β(i)Pπ (Xn = x, Un = u|X1 = i) t n=1 i∈X
=
t 1 XX
t n=1
β(i)π(u|x)Pn−1 (x|i). π
i∈X
For any finite Markov chain, the Cesàro limit t
1 X n−1 lim Pπ (x|i) = P∗π (x|i) t→∞ t n=1 always exists. Thus, the occupancy measure converges to X µβ,π (x, u) = β(i)π(u|x)P∗π (x|i). (18) i∈X
Since the ordinary limit exists, Γπβ = {µβ,π } is a singleton. Under the unichain assumption, we have P∗π (x|i) = νπ (x) for all i ∈ X, where νπ is the unique stationary distribution. Substituting this into (18) gives µβ,π (x, u) = π(u|x)νπ (x),
(19)
which is independent of β. This establishes the result. A PPENDIX II P ROOF OF T HEOREM 1 We classify the constraints in (13) as follows: • A set of |X| balance constraints X X ϕ(x′ , u) = ϕ(x, u)P(x, u, x′ ), x′ ∈ X. u •
x,u
A set of |X||U| nonnegativity constraints
ϕ(x, u) ≥ 0, (x, u) ∈ X × U. P • One normalization constraint x,u ϕ(x, u) = 1. Moreover, there are |X| − 1 linearly independent balance constraints, which are also independent of the normalization constraint. Thus, the rank of the equality constraints is |X|. Since a vertex requires |X||U| active linearly independent constraints [19, Theorem 2.3], at least |X|(|U| − 1) nonnegativity constraints must be active at any vertex of Φ. Moreover, two vertices are adjacent if and only if they share |X||U| − 1 linearly independent active constraints.
A. Proof of Theorem 1(a) Theorem 1(a) establishes the equivalence between the set of occupancy measures Γβ and the auxiliary set Φ. The following lemma is a key step in the proof, which holds without the unichain assumption. ΠD S Lemma 6: Γβ = conv(ΓΠ β ) = conv(Γβ ). ΠD ΠS Proof: Clearly, for any β, Γβ ⊂ Γβ ⊂ Γβ . The proof is then divided into three parts. ΠD Part i): Γβ ⊃ conv(Γ Pm β ). Let ΠD = {π1 , . . . , πm }. For some α ⪰ 0 with i=1 αi = 1, let π̂ ∈ ΠM be an initial mixing policy which selects αi with probability αi at t = 1 and follows it thereafter. Then, for all n ≥ 1, m X Pπ̂β (Xn = x, Un = u) = αi Pπβi (Xn = x, Un = u). i=1
t
=
x,u
for all t ≥ 1. For any x ∈ X, the state frequency satisfies t
µtβ,π (x′ ) =
m
1 XX αi Pπβi (Xn = x, Un = u) t n=1 i=1 m X
=
i=1
Since each πi is stationary, the sequence {µtβ,πi (x, u)} converges to µβ,πi (x, u), which gives that m X i=1
the hyperplane separation theorem [17, Sec. 11], there exists D a hyperplane that separates {µ′ } from conv(ΓΠ β ); that is, there exists a nonzero vector c̃ ∈ R|X||U| such that inf
Π
⟨µ, c̃⟩.
(20)
µ∈conv(Γβ D )
Consider an MDP described by (X, U, P, c̃, β). It is known (e.g., Puterman [20, Ch. 8]) that there exists an optimal deterministic policy π ∗ ∈ ΠD for this MDP. This implies that ′
⟨µπ∗ , c̃⟩ = inf ⟨µ, c̃⟩ ≤ inf ⟨µ, c̃⟩ ≤ ⟨µ , c̃⟩, Π
µ∈Γβ D
µ∈Γβ
1 t
t X X
Pπβ (Xn′ = x, Un′ = u)P(x, u, x′ )
n′ =1 x,u ′
P π ′ β(x ) x,u Pβ (Xt = x, Ut = u)P(x, u, x ) + − t X t = µtβ,π (x, u)P(x, u, x′ ) x,u
αi µβ,πi (x, u).
D Hence, conv(ΓΠ β ) ⊂ Γβ . This proves Part (i). D Part ii): Γβ ⊂ conv(ΓΠ β ). Suppose, to the contrary, that ΠD ′ D there exists µ ∈ Γβ such that µ′ ∈ / conv(ΓΠ β ). Since Γβ = {µπ : π ∈ ΠD } is finite, its convex hull is compact. By
⟨µ′ , c̃⟩ <
1h X X π P (Xn−1 = x, Un−1 = u)P(x, u, x′ ) t n=2 x,u β i X + β(x′ ) − Pπβ (Xt = x, Ut = u)P(x, u, x′ ) x,u
αi µtβ,πi (x, u).
µβ,π̂ (x, u) =
1X π P (Xn = x′ ) t n=1 β
t+1
=
The finite-horizon state-action frequency µtβ,π̂ satisfies µtβ,π̂ (x, u) =
Π S Lemma 7: For all β, ΓΠ β = Φ. Each µ ∈ Γβ is realizable by a stationary policy defined by (14). Proof: We establish the equivalence in two steps. ΠS S Part i): ΓΠ β ⊂ Φ. That is, for each µπ ∈ Γβ induced by some stationary policy π ∈ ΠS , we show that µπ ∈ Φ. The finite-horizon state-action frequency µtβ,π satisfies the normalization and non-negativity conditions X µtβ,π (x, u) = 1 and µtβ,π (x, u) ≥ 0 (22)
(21)
which contradicts (20). This establishes Part (ii). ΠD ΠD S S Part iii): conv(ΓΠ ⊂ ΓΠ β ) = conv(Γβ ). Since Γβ β , ΠD ΠS we have conv(Γβ ) ⊂ conv(Γβ ). Conversely, from Part ΠD S (ii), ΓΠ β ⊂ Γβ ⊂ conv(Γβ ). Taking convex hulls yields ΠD ΠD S conv(ΓΠ β ) ⊂ conv conv(Γβ ) = conv(Γβ ). This proves the lemma. S Returning to Theorem 1(a), it remains to show that ΓΠ β = Φ. This equivalence, combined with the fact that Φ is a convex polytope, establishes this assertion. This part is formalized in the following lemma.
P ′ π β(x′ ) x,u Pβ (Xt = x, Ut = u)P(x, u, x ) − . (23) + t t From Lemma 2, the limit µπ (x, u) = limt→∞ µtβ,π (x, u) exists. Taking limits at both sides of (23) gives X X µπ (x′ , u) = µπ (x, u)P(x, u, x′ ). (24) u
x,u
S This, together with (22), implies µπ ∈ Φ. Hence, ΓΠ β ⊂ Φ. ΠS Part ii): Γβ ⊃ Φ. That is, for each ϕ ∈ Φ, there exists S some stationary policy πϕ ∈ ΠS such that µπϕ ∈ ΓΠ β . For any ϕ ∈ Φ, define the stationary policy πϕ ∈ ΠS as ( ϕ(x, u)/ϕ(x), ϕ(x) > 0, πϕ (u|x) = arbitrary, ϕ(x) = 0.
From the definition of Φ, we have X ϕ(x′ ) = ϕ(x, u)P(x, u, x′ ) x,u
= =
X x X
ϕ(x)
X
πϕ (u|x)P(x, u, x′ )
u
ϕ(x)Pπϕ (x, x′ ).
(25)
x
Under the unichain assumption, {Xt } under πϕ has a unique stationary distribution P νπϕ that satisfies (25). Since ϕ(x) satisfies (25) and x ϕ(x) = 1, this implies that ϕ(x) = νπϕ (x) for all x. It follows from Lemma 2 that µπϕ (x, u) = νπϕ (x)πϕ (u|x) = ϕ(x, u). S This confirms that ϕ is realizable by πϕ , hence Φ ⊂ ΓΠ β .
B. Proof of Theorem 1(b) Theorem 1(b) states that: (i) any deterministic policy produces an occupancy measure that is a vertex of Φ; and (ii) any vertex of Φ corresponds to a deterministic policy. D Part i): ΓΠ ⊂ V(Φ). Let π ∈ ΠD . Suppose that µπ ∈ / β V(Φ). Then there exist two distinct vectors µ1 , µ2 ∈ Φ and a scalar α ∈ (0, 1) such that µπ = αµ1 + (1 − α)µ2 . Since π ∈ ΠD , its occupancy measure satisfies ( νπ (x), u = π(x), µπ (x, u) = 0, u ̸= π(x).
αµπ1 (x, u)Eπ1 [Tc ] + (1 − α)µπ2 (x, u)Eπ2 [Tc ] αEπ1 [Tc ] + (1 − α)Eπ2 [Tc ] = bµπ1 (x, u) + (1 − b)µπ2 (x, u), (27)
=
where b=
ανπ2 (i0 ) . ανπ2 (i0 ) + (1 − α)νπ1 (i0 )
(28)
Thus, µπ is a convex combination of distinct points in Φ and cannot be a vertex. This establishes the result. C. Proof of Theorem 1(c)
Because µi (x, u) ≥ 0, it follows that µ1 (x, u) = µ2 (x, u) = 0 for all x ∈ X and u ̸= π(x). This activates |X|(|U|−1) nonnegativity constraints at µπ , and these constraints are linearly independent. In addition, there are |X| linearly independent equality constraints active at µπ . Therefore, µπ is a vertex of Φ, which contradicts the assumption. Hence, we conclude D that ΓΠ β ⊂ V(Φ). D Part ii): V(Φ) ⊂ ΓΠ β . Suppose, to the contrary, that there exists a randomized policy π ∈ / ΠD such that µπ ∈ V(Φ). Then there exists at least one state i0 ∈ X for which π(·|i0 ) is not a Dirac measure. Consequently, there exist two distinct distributions ψ1 , ψ2 and a scalar α ∈ (0, 1) such that
Let µ1 , µ2 be two distinct vertices, and let π1 , π2 ∈ ΠD denote their corresponding deterministic policies. Two vertices are adjacent if and only if they share |X||U| − 1 independent active constraints. Under any deterministic policy, each state with positive occupancy contributes |U| − 1 linearly independent active nonnegativity constraints, while a transient state (with zero occupancy) contributes |U| active constraints, of which |U| − 1 are linearly independent. Sufficiency: Suppose that µ1 and µ2 differ only in state i0 . Since µ1 ̸= µ2 , the actions prescribed at i0 are different, and at least one of the corresponding policies assigns positive occupancy to this state. Both vertices satisfy the same |X| equality constraints. For each x ̸= i0 , the policies are identical and thus share |U|−1 active nonnegativity constraints. At x = i0 , they share |U| − 2 active nonnegativity constraints. The number of shared independent active constraints is
π(u|i0 ) = αψ1 (u) + (1 − α)ψ2 (u).
|X| + (|X| − 1)(|U| − 1) + |U| − 2 = |X||U| − 1.
Hence, for all x ∈ X and all u ̸= π(x), we have αµ1 (x, u) + (1 − α)µ2 (x, u) = 0.
Define two stationary policies πi , i = 1, 2, by ( π(u|x), x ̸= i0 , πi (u|x) = ψi (u), x = i0 .
(26)
That is, π1 and π2 differ only in state i0 . Then the mixing policy π = απ1 + (1 − α)π2 behaves as follows: whenever the system returns to state i0 , it selects π1 with probability α and π2 with probability 1 − α, and follows the selected policy until the next visit to i0 . Similar to the simple mixing policy in Definition 2, {Xt } induced by π forms a regeneration process. Let Tc denote the regeneration cycle length (i.e., the time between successive visits to i0 ), and let Nc (x, u) denote the number of times action u is taken in state x during one regeneration cycle. Because the choice between π1 and π2 is made only at regeneration epochs, conditioning on this choice yields π1
π2
E [Nc (x, u)] = αE [Nc (x, u)] + (1 − α)E [Nc (x, u)]. Since {Xt } induced by π and πi , i = 1, 2, contain a single recurrent class, their stationary distributions satisfy µπ (x, u) =
Eπi [Nc (x, u)] Eπ [Nc (x, u)] , µ (x, u) = . π i Eπ [Tc ] Eπi [Tc ] π
πi
In particular, νπ (i0 ) = 1/E [Tc ] and νπi (i0 ) = 1/E [Tc ]. Then we may write µπ (x, u) =
|X| + (|X| − ℓ)(|U| − 1) + ℓ(|U| − 2) = |X||U| − ℓ. Since ℓ > 1, this number is strictly less than |X||U| − 1. Hence, µ1 and µ2 cannot be adjacent. D. Proof of Theorem 1(d) Let ϕ1 , ϕ2 ∈ V(Φ) be adjacent vertices differing in state i0 , and let πϕ1 , πϕ2 ∈ ΠD denote the corresponding deterministic policies. Define a simple mixing policy π = απϕ1 + (1 − α)πϕ2 ,
Eπ [Tc ] = αEπ1 [Tc ] + (1 − α)Eπ2 [Tc ], π
Hence, µ1 and µ2 are adjacent. Necessity: Suppose µ1 and µ2 differ in ℓ > 1 states where at least one of the policies assigns positive occupancy. At each of these ℓ states, they share |U| − 2 active nonnegativity constraints. Therefore, the total number of shared linearly independent active constraints is
αEπ1 [Nc (x, u)] + (1 − α)Eπ2 [Nc (x, u)] αEπ1 [Tc ] + (1 − α)Eπ2 [Tc ]
which selects πϕ1 with probability α and πϕ2 with probability 1 − α whenever state i0 is visited. Following the regeneration argument in Appendix II-B, the occupancy measure induced by π satisfies µπ = bϕ1 + (1 − b)ϕ2 ∈ G(ϕ1 , ϕ2 ), where b is given by (28). Since the mapping α 7→ b is continuous and strictly monotone, every point on the edge G(ϕ1 , ϕ2 ) can be realized by a suitable choice of α. This establishes the result.
A PPENDIX III P ROOF OF T HEOREM 2 Part (a): Let V(Φ) = {v1 , . . . , vm }. Since Φ is a convex polytope, any point ϕ ∈ Φ can be written as ϕ=
m X
λi vi , where λi ≥ 0 and
i=1
m X
λi = 1.
i=1
By the linearity of the operator J , we have J (ϕ) = J
m X
m X λ i vi = λi J (vi ).
i=1
i=1
(29)
This shows that every objective vector J (ϕ) ∈ J Φ is a convex combination of the points in J V(Φ) = {J (vi ) : vi ∈ V(Φ)}. Hence, J Φ = conv(J V(Φ) ) is a convex polytope, and its vertex set satisfies V(J Φ ) ⊆ J V(Φ) . Part (b): From Theorem 1(a), we have Jβ = JβΠS = J Φ . It follows from (29) that D conv(JβΠD ) = conv({J (ϕ) : ϕ ∈ ΓΠ β })
= conv({J (ϕ) : ϕ ∈ V(Φ)}) = {J (ϕ) : ϕ ∈ conv(V(Φ))} = {J (ϕ) : ϕ ∈ Φ} = J Φ ,
(30)
which yields the result. Part (c): Let ϕ∗ ∈ Φ be a Pareto optimal vertex. Suppose that J (ϕ∗ ) lies in the interior of J Φ . Then there exists an open ball Bσ (J (ϕ∗ )) of radius σ > 0 such that Bσ (J (ϕ∗ )) ⊂ J Φ . We can then choose a unit vector d = √1K [1, . . . , 1]⊤ and a sufficiently small scalar ϵ > 0 such that the point y = J (ϕ∗ ) − ϵd lies within Bσ (J (ϕ∗ )). Since Bσ (J (ϕ∗ )) ⊂ J Φ , there exists some ϕ ∈ Φ such that J (ϕ) = y. It follows that J (ϕ) ≺ J (ϕ∗ ), which contradicts the Pareto optimality of ϕ∗ . Thus, J (ϕ∗ ) must lie on the boundary of J Φ . Part (d): Since Φ is a convex polytope and J is a linear mapping, there exists a vertex ϕ∗ ∈ V(Φ) and a nonzero vector w ⪰ 0 such that ϕ∗ ∈ arg min ⟨w, J (ϕ)⟩.
(31)
ϕ∈Φ
The set of minimizers is given by Φ∗ := {ϕ ∈ Φ : ⟨w, J (ϕ)⟩ = g ∗ },
(32)
where g ∗ = ⟨w, J (ϕ∗ )⟩. Clearly, Φ∗ is a face of Φ. We next show that if w ≻ 0, then ϕ∗ is Pareto optimal. Suppose that ϕ∗ is not Pareto optimal. Then there exists some ϕ′ ∈ Φ such that J (ϕ′ ) ⪯ J (ϕ∗ ) and J (ϕ′ ) ̸= J (ϕ∗ ). Since w is strictly positive in all components, we obtain J(ϕ′ ; w) = ⟨w, J (ϕ′ )⟩ < ⟨w, J (ϕ∗ )⟩ = g ∗ ,
(33)
contradicting (31). This implies that ϕ∗ is Pareto optimal. Part (e): Let ϕ∗ ∈ V ∗ (Φ) be a Pareto optimal vertex. From Part (d), ϕ∗ is a minimizer of the linear functional J(ϕ; w) for some w ≻ 0. The set of all such minimizers, Φ∗ , is a d-dimensional Pareto optimal face of Φ.
We first argue that there exists some w ≻ 0 such that d ≥ 1. Suppose, to the contrary, that Φ∗ = {ϕ∗ } for all w ≻ 0. This would imply that ϕ∗ is the unique global optimum for every individual objective Jk , which contradicts the assumption that the objectives are in conflict. Since Φ∗ has dimension d ≥ 1, the vertex ϕ∗ ∈ Φ∗ must be incident to at least one edge G(ϕ∗ , ϕ′ ) ⊆ Φ∗ . It follows from Part (d) that ϕ′ ∈ N ∗ (ϕ∗ ), and hence |N ∗ (ϕ∗ )| ≥ 1. The upper bound |N ∗ (ϕ∗ )| ≤ |X|(|U|−1) follows because each vertex of Φ corresponds to a deterministic policy, and there are at most |X|(|U| − 1) adjacent deterministic policies. Part (f): Let ϕ, ϕ′ ∈ V ∗ (Φ) be two adjacent Pareto optimal vertices. From Part (e), there exists a w ≻ 0 such that G(ϕ, ϕ′ ) is contained in the Pareto optimal face Φ∗ . R EFERENCES [1] J. Baillieul and P. J. Antsaklis, “Control and communication challenges in networked real-time systems,” Proc. IEEE, vol. 95, no. 1, Jan. 2007. [2] P. Park, S. Coleri Ergen, C. Fischione, C. Lu, and K. H. Johansson, “Wireless network design for control systems: A survey,” IEEE Commun. Surveys Tuts., vol. 20, no. 2, 2nd Quart. 2018. [3] M. Kountouris and N. Pappas, “Semantics-empowered communication for networked intelligent systems,” IEEE Commun. Mag., vol. 59, no. 6, Jun. 2021. [4] J. Luo and N. Pappas, “Semantic-aware remote estimation of multiple markov sources under constraints,” IEEE Trans. Commun., vol. 73, no. 11, 2025. [5] L. Schenato, “Optimal estimation in networked control systems subject to random delay and packet drop,” IEEE Trans. Autom. Control, vol. 53, no. 5, June 2008. [6] A. S. Leong, S. Dey, and D. E. Quevedo, “Sensor scheduling in variance based event triggered estimation with packet drops,” IEEE Trans. Autom. Control, vol. 62, no. 4, Apr. 2017. [7] J. Luo, G. Stamatakis, O. Simeone, and N. Pappas, “Remote state estimation over a wearing channel: Information freshness vs. channel aging,” arXiv preprint arXiv:2501.17473, 2025. [8] J. Luo and N. Pappas, “On the cost of consecutive estimation error: Significance-aware non-linear aging,” IEEE Trans. Inf. Theory, vol. 71, no. 10, Oct. 2025. [9] D. White, “Multi-objective infinite-horizon discounted Markov decision processes,” J. Math. Anal. Appl., vol. 89, no. 2, Oct. 1982. [10] K. Chatterjee, R. Majumdar, and T. A. Henzinger, “Markov decision processes with multiple objectives,” in Proc. 23rd Annu. Symp. Theor. Aspects Comput. Sci., Feb. 2006. [11] M. A. Wiering and E. D. de Jong, “Computing optimal stationary policies for multi-objective Markov decision processes,” in Proc. IEEE Symp. Approx. Dyn. Program. Reinforc. Learn., Apr. 2007. [12] D. M. Roijers, P. Vamplew, S. Whiteson, and R. Dazeley, “A survey of multi-objective sequential decision-making,” J. Artif. Intell. Res., vol. 48, Oct. 2013. [13] K. V. Moffaert and A. Nowé, “Multi-objective reinforcement learning using sets of pareto dominating policies,” J. Mach. Learn. Res., vol. 15, no. 107, Nov. 2014. [14] J. Luo, B. Li, and N. Pappas, “Value of communication in goaloriented semantic communications: A Pareto analysis,” arXiv preprint arXiv:2512.01454, 2025. [15] Y. Li, P. Ju, and B. N. Shroff, “How to find the exact pareto front for multi-objective MDPs?” in Proc. 13th ICLR, Apr. 2025. [16] R. G. Bartle and D. R. Sherbert, Introduction to Real Analysis, 4th ed. Hoboken, NJ, USA: Wiley, 2011. [17] R. T. Rockafellar, Convex Analysis. Princeton, NJ, USA: Princeton Univ. Press, 1970. [18] L. Schenato, B. Sinopoli, M. Franceschetti, K. Poolla, and S. S. Sastry, “Foundations of control and estimation over lossy networks,” Proc. IEEE, vol. 95, no. 1, Jan. 2007. [19] D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization. Belmont, MA, USA: Athena Scientific, 1997. [20] M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. Hoboken, NJ, USA: Wiley, 1994.