Robust partially observable decision processes reduced to partial observable games
Reward Objectives for Robust (PO)MDPs: A Law-Preserving Equivalence with (Partially Observable) Games
Artificial IntelligenceFormal Languages and Automata Theory
Summary
The paper looks at decision-making problems where an agent must act without full information, and the environment might be adversarial. The authors study four ways to measure risk or reward, like average gains or worst-case scenarios. They show these problems can be transformed into a kind of mathematical game where two players have partial information, preserving the key reward properties. This means techniques from game theory can now solve these decision problems, and it also clarifies how hard these problems are to compute.
What this means in practice
- •For robotic system designers: Model decision-making under uncertain and adversarial conditions with guarantees by converting robust POMDPs into equivalent games.
- •For autonomous vehicle engineers: Use the equivalence to partially observable games to analyze and design risk-sensitive planning algorithms under various reward and risk measures.
A theory result. No direct application yet.
Authors
Durgam Latha, Dion Reji, Dorde Zikelic, Shankaranarayanan Krishna
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.