observation, memory state  pair to a pair  action, memory state .  The set of memory can be seen as a finite scratch" memory.

states Free finite memory policies can also simulate stationary policies; all hardness results for stationary policies apply to free finite memory policies as well. Because one can consider a free finite memory policy to be a stationary policy over the state space upper bounds (complexity class membership results) for stationary policies hold for free finite memory policies as well. The advantages of free finite memory policies appear in the constants of the algorithms, and in special, probably large, subclasses of POMDPs, where a finite amount of memory suffices for an optimal policy. The maze instances such as McCallum's maze (McCallum, 199 ; Littman, 1994) are such examples: McCallum's maze requires only 1 bit of memory to find an optimal policy.

Let
= (
) be a POMDP.

A trajectory   of length    for     is a sequence of states l
) which starts with the initial state of    , i.e.     =         We use   k( ) to denote the sset of length- tra ectories which end in state .

The expected reward obtained in state   after exactly   steps under policy is the reward obtained in   by taking the action specified by   , weighted by the probability that is actually reached after   steps,

$\}$ = ( ( ( ))) $\sum\limits_{\sigma_{0}\,....,\sigma_{k}\,\in T_{k}\,\,s}\prod_{i}^{k}$  y,  $\}$ = ( ( ( ) )) $\sum\limits_{\sigma_{0}\,....,\sigma_{k}\,\in T_{k}\,\,s}\prod_{i}^{k}$
$${\left(\begin{array}{l l}{(}&{i-}\end{array}\right)}\end{array}\right)}$$
( i-    ( ( i- )), if   is a stationary policy,
_ 

time-dependent policy, and  $\begin{array}{llllllll}\text{(}&\text{)}=&\sum\limits_{\sigma_k\dots\sigma_k\in\Upsilon_k}\text{(}&\text{(}&\text{(}&\text{)}&\text{(}&\text{)}\end{array}))\prod_i^k\text{(}&\text{(}&\text{(}&\text{)}&\text{(}&\text{)}\end{array})\quad i),$  if $\quad$ is a history-dependent policy. 
A POMDP may behave differently under optimal policies for each type of policy. The quality of a policy is determined by its performance, i.e. by the expected rewards accrued by it. We distinguish between different performance metrics for POMDPs that run for a finite number of steps and those that run indefinitely.

The finite-horizon performance of a policy   for POMDP     is the expected sum of rewards received during the first       steps by following the policy   , i.e., perff(
) =
||
). (Other work assumes that the horizon is poly (    ), instead of Lses (
. This does not change the complexity of any of our problems.)
The infinite-horizon total discounted performance gives rewards obtained earlier in the process a higher weight than those obtained later.  For 1, the total
-discounted reward is defined as perfid(
) = ∑ ∞ ∑ s ∈ s The infinite-horizon average performance is the limit of all rewards obtained within steps divided by   , for   going to infinity:  perfav (
) = limn →∞ = perff(