Newest papers

Reward Objectives for Robust (PO)MDPs: A Law-Preserving Equivalence with (Partially Observable) Games

Durgam Latha, Dion Reji, Dorde Zikelic, Shankara Narayanan Krishna · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.26568 · cited by 0 works (OpenAlex) · open-access PDF

Vietnamese

POSward là một mô hình các quá trình quyết định của Markov có thể quan sát được một phần trong khi môi trường đối phương giải quyết sự không chắc chắn trong xác suất chuyển đổi. Các mục tiêu thưởng như giảm giá, trung bình chạy dài và phần thưởng tích lũy dưới chân trời hữu hạn và vô hạn cho phép định lượng lợi ích của một tác nhân. Chúng tôi xem xét vấn đề giải quyết RPOMDP dưới cả bốn mục tiêu phần thưởng (VaPO), trong đó mục tiêu là quyết định liệu giá trị của một biện pháp rủi ro liên quan đến một mục tiêu phần thưởng có vượt quá một ngưỡng nhất định hay không. Chúng tôi xem xét các biện pháp rủi ro khác nhau, chẳng hạn như (1)~ giá trị dự kiến, (2)~sự thay đổi trung bình (MV), (3)~sự thay đổi hợp lệ giữa các biện pháp giá trị-rủi ro (VaPO), và (4)

Machine translation (Meta M2M100); the English original follows.

Abstract

Robust partially observable Markov decision processes model agents that act under partial observability while adversarial environment resolves uncertainty in the transition probabilities. Reward objectives such as discounted-sum, long-run average and cumulative reward under finite and infinite horizons allow quantifying the utility of an agent. We consider the problem of solving RPOMDPs under all four reward objectives, where the goal is to decide whether the value of a risk measure with respect to a reward objective exceeds a given threshold. We consider different risk measures, such as (1)~expected value, (2)~mean-variance (MV), (3)~conditional value-at-risk (CVaR), and (4)~entropic risk (ERisk). Our results can be summarized as follows. First, we formalize the class of law-invariant risk measures, that subsume all four risk measures above. Second, we propose a unified framework for solving RPOMDPs with discounted-sum, long-run average and cumulative reward objectives under any law-invariant risk measure, by reducing the problem to solving partially observable stochastic games (POSGs). Our unified framework applies to (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, which we show to be {\em equivalent} to POSGs, for each of the four reward objectives and any law-invariant risk measure. We prove equivalence by designing logspace reductions between the RPOMDP and POSG models, that map strategies to strategies and preserve the distribution of the reward objective, up to a constant rescaling factor. Third, as a corollary, we derive new computational complexity results for R(PO)MDPs and POSGs. In particular, we show that solving (s,a)-rectangular RMDPs is as hard as solving simple stochastic games.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Equivalence (formal languages), Observability, Markov decision process, Mathematics, Markov process, Mathematical optimization

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange