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.
Figures & tables
Figure 1: The forward construction. (a) An RPOMDP with states s1,s2,s3 ; action b is available only in s1 . The drawn distributions are generic points of the uncertainty polytopes, e.g., (p1,q1,r1)∈P(s1,a)=conv{v11,v12,v13} , (0,q2,r2)∈P(s2,a)=conv{v21,v22} , and P(s3,a)={v31} with v31=(0,q3,r3) . (b) The ac-POSG G(M) . Circles are max -states and rectangles are min -states (s,a) , whose actions are the vertices of P(s,a) . By randomizing over v11,v12,v13 with weights (α1,α2,α3) , min realizes the point α1v11+α2v12+α3v13 of P(s1,a) . For readability, dashed outcome edges are drawn for one vertex per min -state only.
Figure 2: The backward construction. (a) An ac-POSG G with max -states s1,s2 (circles) and min -states t1,t2 (rectangles); min can play x in t1 and x or y in t2 . (b) The RPOMDP R(G) ; dotted boxes are uncertainty sets. The sets U3=P((s1,τ),a) , U4=P((s1,τ),b) , and U5=P((s2,τ),a) are the singletons {δ^(s1,a)} , {δ^(s1,b)} , and {δ^(s2,a)} for every tag τ , and U2=P(dt1,⊤)={δt1,x′} is a singleton as well. The set U1=P(dt2,⊤)=conv{δt2,x′,δt2,y′} is a segment: choosing a point on it is choosing a mixed action of min in t2 , and the tag of the next state records which action was realized.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Example A.1 . (a) A game G with two min -states with the same observation. (b) Its chain compilation for k=2 . Both players observe the same along the two chains. The shaded rectangles are the slots where the real choice of min is made, the choice at the other slot is ignored (or recorded in the state). (c) The i -th reward of G is earned at the transition 2kj or 2kj+2k−1 of G′ ( i=2j or 2j+1 ).
Figure 4: Example A.2 . (a) The game G× for the game G of Figure 3 (a): both states of Co have the four actions (β1,β2)∈{l,r}2 , and ti uses only βi (an edge labelled (l,∗) stands for the two tuples with β1=l ). (b) The ordinary strategy π′ that plays the product of π(t1)=(41,43) and π(t2)=(21,21) on tuples; its marginals are the prescription π . (c) The timing is unchanged.
Robust POMDPs (RPOMDPs) generalize classical POMDPs to the setting where exact transition probabilities are not known -- rather, they are only known to belong to some uncertainty set of values. In this work, we study the problem of solving RPOMDPs with general omega-regular objectives, which subsume a broad class of objectives such as reachability, safety, and linear temporal logic (LTL) objectives. We show that, for (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, the problem of solving RPOMDPs under omega-regular objectives can be reduced to solving partially observable stochastic games (POSGs) under omega-regular objectives. Moreover, we show for the first time that reductions can be constructed in both directions, establishing the semantic equivalence between (s,a)-rectangular RPOMDPs with polytopic uncertainty sets and POSGs. This allows us to derive a range of new computational complexity results, including both upper and lower complexity bounds, on solving RPOMDPs with different omega-regular objectives. As a corollary, we also derive new computational complexity results for RMDPs.
Durgam Latha, Dion Reji, S. Akshay +2
Indian Institute of Technology Bombay Mumbai, India · Nanyang Technological University Singapore, Singapore
Partially Observable Markov Decision Processes (POMDPs) are systems in which one agent interacts with a stochastic environment, and receives only partial information about the current state. In a multi-environment POMDP (MEPOMDP), the initial state is unknown, and assumed to be adversarially chosen. In this work we focus on computing the optimal value and policy in MEPOMDPs with finite-horizon objectives. That problem is known to be PSPACE-complete in POMDPs. Our main results are as follows: (1) we establish that it is also PSPACE-complete in the more general setting of MEPOMDPs; (2) we present a practical algorithm and evaluate it on classical benchmarks, significantly outperforming the only previously known algorithm.
Léonard Brice, Filip Cano, Krishnendu Chatterjee +2
Robust Markov Decision Processes (RMDPs) generalize classical MDPs by allowing uncertainty in transition probabilities and optimizing against their worst-case realization. We consider (s,a)-rectangular RMDPs with linearly defined uncertainty sets and study parity objectives, which are a canonical representation of ω-regular objectives. An uncertainty set is linearly defined if it is described by linear inequalities over the transition distribution together with auxiliary variables, which capture the standard L1 and L∞ balls as well as general polytopic uncertainty sets. The quantitative value is the supremum, over all agent policies, of the satisfaction probability guaranteed against the adversarial environment. Previous work studied the qualitative analysis, namely the almost-sure (resp. positive) problem that asks whether a single agent policy guarantees satisfaction with probability one (resp. positive probability) against every environment policy. In this work, we solve the exact quantitative problem. Our contributions are threefold. First, we show that both the agent and the environment admit pure memoryless optimal policies. Second, we give a polynomial-time algorithm for quantitative parity on linearly defined robust Markov chains and use it as a subroutine in a policy-iteration algorithm for RMDPs. The algorithm combines quantitative one-step improvements with qualitative almost-sure improvements. Finally, we report experiments comparing our approach with the explicit reduction to stochastic games.
Ali Asadi, Krishnendu Chatterjee, Ehsan Kafshdar Goharshady +3