obtained in the following rounds are multiplied by 1 - , , because a fraction of , , , of the tra ectories are sent to the penalty box. Using the induction hypothesis, we obtain the following upper bound for the performance of   k   ( Φ ) under   j for an arbitrary

perff( k (Q) j) + 1)
This completes the induction step. Hence, we proved that, for Φ    SSAT and for every the value of    k (Φ) is at most c +
Eventually, we have to fix the constants.  We choose   such that  c This guarantees that

$$\begin{array}{r l r l r l}{{\left(1\quad\quad\right)}}&{{\left(1\quad\quad-c\right)}}&{{}}&{{}}&{{-c}}\end{array}$$

Next, we choose   such that

$$\begin{array}{r l r l r l}{{\left(\left(1\right.\right.}&{{}\right)}}&{{\left(1\right.}&{{}\left.\left.-c\right)\right.}}&{{}}&{{}}&{{-c}}\end{array}$$

(~) be the POMDP that consists of   repetitions of   (~) as described above.

Let Because is linear in the number, i of variables of Φ and hence linear in the length of Φ ,
Ø can be transformed to    (Ø) in polynomial time. The above estimates guarantee that value of    ( Φ ) for Φ    SSAT

- + (1 (1
The right-hand side of this inequality is a lower bound for an -approximation of the value
(Î) for Î    SSAT. Hence, of

$$\begin{array}{l l l l l l}{{\mathrm{if~\Phi~}}}&{{\mathrm{~Ssat,~t h e n}}}&{{\widetilde{\ \ \ (\Phi)}\ \mathrm{has~value}}}&{{\ \ \ \ \ (1\ \ \ \ \ ^{-c}),\ \mathrm{and}}}\\ {{}}&{{}}&{{}}&{{}}\\ {{\mathrm{if~\Phi~}}}&{{\mathrm{~Ssat,~t h e n}}}&{{\ \ \ \ \ (\widetilde{\ \ \Phi)}\ \mathrm{has~value}}}&{{\ \ \ (1\ \ \ \ \ \ )}}&{{\ \ \ (1\ \ \ \ \ \ ^{-c}).}}\end{array}$$

Hence, a polynomial-time  -approximation of the value of   (Φ) shows whether Φ is in SSAT.

Concluding, let    be any set in PSPACE. There exists a polynomial-time function which maps every instance   of    to a bounded error stochastic formula   ( ) = Φ x with
-c and reduces    to SSAT.  Transform Φ x into the POMDP    (Φ x ).  Using the error approximate value of    ( Φ x ), one can answer   Φ x     SSAT?" and hence in polynomial time. This shows that    is in P, and consequently P = PSPACE.

□
1. The history-dependent value of POMDPs with general Corollary 4.12  Let rewards is  -approximable if and only if P = PSPACE.