精确刻画平均代价多目标MDP的帕累托前沿，揭示其几何结构。
Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes
- 基于凸多面体边界构造连续分段线性前沿
- 前沿顶点对应确定性策略，边为端点策略的闭式混合
- 适用于远程状态估计等非凸问题求解
许多通信与控制问题可建模为多目标马尔可夫决策过程（MOMDP）。MOMDP的完整解是帕累托前沿。现有研究通常通过标量化方法近似该前沿。近期工作开始利用几何特性刻画折扣或简单双目标情形下的完整前沿。本文首次在平均代价多目标MDP中刻画了精确前沿：其为位于凸多面体边界上的连续分段线性曲面。每个顶点对应一个确定性策略，相邻顶点仅在一个状态上不同；每条边由端点策略的凸组合实现，混合系数具闭式表达。我们将该结果应用于远程状态估计问题，发现前沿上每个顶点对应一个阈值策略。无需显式求解任何MDP，即可获得精确帕累托前沿及某些非凸MDP的解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。