Multi-Environment POMDPs with Finite-Horizon Objectives

Technical Summary: Multi-Environment POMDPs with Finite-Horizon Objectives

Problem Statement
This work addresses the problem of computing optimal values and policies in Multi-Environment Partially Observable Markov Decision Processes (MEPOMDPs) with finite-horizon objectives. In a standard Partially Observable MDP (POMDP), an agent interacts with a stochastic environment receiving only partial state information. An MEPOMDP extends this by assuming the initial state is unknown and adversarially chosen from a set of $n$ possible initial states $\{s_1, \dots, s_n\}$. The agent must compute a single policy that maximizes the minimum expected reward across all possible initial environments. The objective is to maximize the sum of rewards over a finite horizon $k$.

The paper focuses on two computational problems:

1. The Value Problem: Computing the optimal value $v = \sup_{\sigma} \min_{i \in [n]} E^k_{s_i}(\sigma)$.
2. The Threshold Problem: Deciding whether $v \ge \lambda$ for a given rational threshold $\lambda$.

A critical theoretical nuance identified is that, unlike standard POMDPs where deterministic policies suffice for optimality, MEPOMDPs generally require randomized policies to achieve the optimal value, as deterministic strategies may fail to satisfy the worst-case initial state constraint.

Methodology and Algorithms
The authors develop both theoretical complexity bounds and practical algorithms to solve these problems.

• Complexity Analysis: The paper establishes that the threshold problem and its approximate version are PSPACE-complete. The lower bound is inherited from the known PSPACE-hardness of standard POMDPs (where $n=1$). The upper bound is proven via a non-deterministic algorithm that leverages Carathéodory's theorem. This theorem implies that if a policy exists achieving a certain value across $n$ environments, there exists a "mixture" of at most $n$ deterministic policies that achieves the same guarantee. This allows the search space to be reduced to combinations of a limited number of deterministic strategies.

• Space-Efficient Deterministic Algorithm (Algorithm 2): To avoid the exponential space requirements of standard determinization (e.g., via Savitch's theorem), the authors present a deterministic algorithm that operates within polynomial space. Instead of guessing entire policies, the algorithm enumerates possible multi-expected payoff values and verifies their achievability recursively. It constructs partial sums of the Bellman update equation, checking if a target value can be decomposed into valid sub-strategies. While theoretically optimal in space ($O(|S| \cdot |O| \cdot n \cdot k \cdot \pi(N))$), the authors note this approach is computationally infeasible for most practical instances due to imbricated loops.

• Practical Time-Efficient Algorithm (Algorithm 3): For empirical evaluation, the authors propose a bottom-up algorithm that computes the set of achievable multi-expected payoffs for increasing horizons. This method maintains a set of non-dominated payoff vectors (the "frontier"). At each step, it prunes vectors that are convexly dominated by others, as these correspond to policy families that do not need further exploration. While this algorithm may use exponential space in the worst case, it is designed for scalability in practice.

Key Contributions

1. Complexity Classification: The paper proves that computing values in MEPOMDPs with finite horizons is PSPACE-complete, matching the complexity of standard POMDPs despite the added adversarial initial state constraint.
2. Theoretical Insight: It demonstrates that optimal policies in MEPOMDPs can be represented as mixtures of at most $n$ deterministic policies, where $n$ is the number of initial environments.
3. Algorithmic Advancements:
   • A deterministic, polynomial-space algorithm (Algorithm 2) that provides a theoretical upper bound on space complexity.
   • A practical, time-efficient algorithm (Algorithm 3) that utilizes pruning of dominated payoff vectors.
4. Empirical Validation: The practical algorithm is evaluated against the only previously known exact algorithm (from Bovy et al. [1]) on three benchmark suites: Rock Sample, Robot Navigation, and Identification (Friend or Foe).

Results
Experimental results indicate that the proposed practical algorithm (Algorithm 3) significantly outperforms the state-of-the-art tool from [1].

• Performance: The new method solves instances with up to 574 states and horizons up to $k=7$ within reasonable timeframes, whereas the baseline tool frequently times out (3600s limit) on much smaller instances.
• Scalability: The computation time scales strongly with the horizon $k$, which is identified as the primary bottleneck for scalability. The number of states and initial environments has a less dominant effect on runtime compared to the horizon.
• Comparison: In the Rock Sample benchmarks, the proposed method solved instances where the baseline timed out, often achieving speedups of several orders of magnitude (e.g., solving a 574-state instance in ~784 seconds vs. a timeout for the baseline).

Significance and Limitations
The paper claims significance in providing the first tight complexity bounds for MEPOMDPs and offering a practical algorithm that substantially improves upon existing tools. The authors acknowledge a standard tradeoff between theoretical and practical performance: the space-efficient algorithm (Algorithm 2) is theoretically sound but practically slow, while the time-efficient algorithm (Algorithm 3) is fast in practice but lacks a polynomial space guarantee in the worst case.

The work is limited to finite-horizon objectives. The authors note that while the exact problem for discounted-sum objectives is undecidable for POMDPs, their algorithm could potentially be adapted for approximate discounted objectives by reducing them to finite-horizon problems, though this remains future work. The paper does not propose new applications beyond the standard benchmarks used for evaluation.