action

$$\alpha_{i+1}^{a}(s)=\rho(\,s,a\,)+\gamma\sum_{o\,\in\,\Theta}\operatorname*{max}_{\alpha_{i}\,\in\Gamma_{i}}\sum_{s^{l}\,\in\,S}P(\,s^{l},o|s,a\,)\alpha_{i}(\,s^{l}\,).$$

The H F I B update is efficient and can be computed in O ( | A || S | 2 | Θ || Γ i |) time.  As the method always outputs |A| linear functions, the computation can be done in O(|A|2|S|2|O|) time, when many H FIB updates are strung together. This is a significant complexity reduction compared to the exact approach: the latter can lead to a function consisting of | A || Γ i || Θ l linear functions, which is exponential in the number of observations and in the worst case takes O(|A||S|²|Г¦||©|) time.

As H F I B updates are of polynomial complexity one can find the approximation for the finite-horizon case efficiently. The open issue remains the problem of finding the solution for the infinite-horizon discounted case and its complexity. To address it we establish the following theorem. Theorem 8  A solution for the fast informed bound approximation can be found by solving an MDP with |S||A||O| states, |A| actions and the same discount factor γ .

The full proof of the theorem is deferred to the Appendix. The key part of the proof is the construction of an equivalent MDP with | S || A || Θ | states representing H F1 B updates. Since a finite-state MDP can be solved through linear program conversion, the fixed-point solution for the fast informed bound update is computable efficiently.

4.2.1  FAST INFORMED  BOUND  VERSUS  FULLY-OBSERVABLE  MDP  APPROXIMATIONS
The fast informed update upper-bounds the exact update and is tighter than both the MDP
and the QMDP approximation updates.

Theorem 9 Let Vi corresponds to a piecewise linear convex value function defined by Fi linear functions. Then HVi ≤ HFIBVi ≤ HQMDPVi ≤ HMDPVi The key trick in deriving the above result is to swap max and sum operators (the proof is in the Appendix) and thus obtain both to the upper-bound inequalities and the subsequent reduction in the complexity of update rules compared to the exact update. This is also shown in Figure 15. The UMDP approximation, also included in Figure 15, is discussed later in Section 4.3. Thus, the difference among the methods boils down to simple mathematical manipulations. Note that the same inequality relations as derived for updates hold also for their fixed-point solutions (through Theorem 6).

Figure 13a illustrates the improvement of the bound over MDP-based approximations on the Maze20 problem. Note, however, that this improvement is paid for by the increased running-time complexity (Figure 13b).

## 4.2.2 Control

The fast informed bound always outputs a piecewise linear and convex function, with one linear function per action.  This allows us to build a POMDP controller that selects an action associated with the best (highest value) linear function directly. Figure 14 compares the control performance of the direct and the lookahead controllers to the MDP and the QMDP
controllers. We see that the fast informed bound leads not only to tighter bounds but also