  We develop a framework for obtaining polynomial time approximation schemes
(PTAS) for a class of stochastic dynamic programs. Using our framework, we
obtain the first PTAS for the following stochastic combinatorial optimization
problems: \probemax: We are given a set of $n$ items, each item $i\in [n]$ has
a value $X_i$ which is an independent random variable with a known (discrete)
distribution $\pi_i$. We can {\em probe} a subset $P\subseteq [n]$ of items
sequentially. Each time after {probing} an item $i$, we observe its value
realization, which follows the distribution $\pi_i$. We can {\em adaptively}
probe at most $m$ items and each item can be probed at most once. The reward is
the maximum among the $m$ realized values. Our goal is to design an adaptive
probing policy such that the expected value of the reward is maximized. To the
best of our knowledge, the best known approximation ratio is $1-1/e$, due to
Asadpour \etal~\cite{asadpour2015maximizing}. We also obtain PTAS for some
generalizations and variants of the problem and some other problems.
