A PTAS for a Class of Stochastic Dynamic Programs

Hao Fu, Jian Li, Pan Xu

Abstract

In stochastic combinatorial optimization, sequential decision-making under uncertainty often leads to the "curse of dimensionality," where optimal policies are represented by decision trees of exponential size. This paper introduces a unified framework for creating Polynomial Time Approximation Schemes (PTAS) for a broad class of these stochastic dynamic programs. By leveraging a novel "block adaptive policy" approach, the authors provide the first-ever PTAS for several classic problems, including Probemax, Committed Pandora’s Box, and the Stochastic Blackjack Knapsack.

Introduction

Stochastic combinatorial optimization requires making a sequence of decisions where the outcome of each action is only revealed after it is taken. A classic example is the Probemax problem: an agent "probes" items to reveal their hidden values but can only retain the maximum value found within a fixed number of attempts.

The fundamental challenge in these problems is the exponential growth of the decision space. An optimal strategy, or policy, is typically a decision tree where every node represents a state and every branch represents a possible outcome. Because these trees grow exponentially with the number of items, finding an exact solution is often #P-hard or PSPACE-hard. Historically, researchers have relied on greedy heuristics or specific approximation ratios (such as the $1-1/e$ ratio for Probemax). This paper moves beyond these limitations by providing a general framework for near-optimal $(1-\epsilon)$ solutions.

The Block Adaptive Framework

The core contribution of this research is a framework that simplifies complex, exponential decision trees into a computationally manageable structure. This is achieved through three primary algorithmic pillars:

1. Block Adaptive Policies

Instead of evaluating the state of the system after every single item is processed—which leads to constant branching—the authors group items into "blocks" or batches. They prove a structural result: for any optimal policy, there exists a "block adaptive" version that achieves nearly the same expected profit but only requires a constant number of blocks on any root-to-leaf path. By committing to a batch of items and only re-evaluating the strategy after the entire block is processed, the decision space is drastically pruned.

2. Signatures and Discretization

To manage the variety of items within a block, the authors define a "signature." A signature is a compact vector that captures the approximate probability distribution of rewards for a specific batch. This allows the algorithm to treat different sets of items as equivalent if they share the same signature, preventing the need to check every possible subset. Furthermore, for problems with continuous or large value spaces, the authors utilize discretization techniques to reduce the state space to a constant size without significant loss of accuracy.

3. Dynamic Programming

With the number of blocks and possible signatures bounded by polynomials, the problem is reduced to a standard Dynamic Programming (DP) approach. The DP finds the optimal arrangement of blocks and items to maximize the expected reward, operating within polynomial time relative to the number of items $n$.

Key Results and Applications

The framework provides the first PTAS for four major stochastic problems:

  • Probemax: Improves the best-known approximation from $1-1/e \approx 0.632$ to a full $(1-\epsilon)$ PTAS.
  • Committed Pandora’s Box: Provides a PTAS for the version of the problem where the decision to keep an item must be made irrevocably immediately after opening its box.
  • Stochastic Target: Offers a bi-criteria PTAS to maximize the probability that the sum of items reaches a specific target $T$.
  • Stochastic Blackjack Knapsack: Provides the first bi-criteria PTAS for this "all-or-nothing" knapsack variant, where exceeding capacity results in zero reward.

For the "Target" and "Blackjack" problems, the PTAS is considered "bi-criteria" because it achieves a $(1-\epsilon)$ approximation of the optimal value while allowing for a slight $(1+\epsilon)$ relaxation of the original constraints (e.g., a slightly larger knapsack capacity).

Discussion and Limitations

While this framework represents a significant theoretical breakthrough, there are practical considerations for implementation. The computational complexity, while polynomial, involves an exponent of $O(\epsilon^{-3})$. For high-precision requirements (very small $\epsilon$), the runtime $n^{O(\epsilon^{-3})}$ may be too slow for real-time engineering applications.

Additionally, the requirement for constraint relaxation in bi-criteria approximations suggests that finding a "true" PTAS for the Stochastic Blackjack Knapsack without relaxing capacity remains an open challenge. Future research may also explore extending these results to more complex constraints, such as matroid constraints, which govern which subsets of items can be probed.

Summary updated

BibTeX
@inproceedings{fu2018ptas,
  author = {Hao Fu and Jian Li and Pan Xu},
  title = {{A PTAS for a Class of Stochastic Dynamic Programs}},
  booktitle = {ICALP},
  year = {2018},
  doi = {10.4230/lipics.icalp.2018.56},
}
Figure