Theorem 5.1 (Completeness). When T < ∞ or |S| < ∞, any θ-admissible search π, γ¯ ≤ θ starting with a θ-admissible heuristic is complete.

Corollary 5.1 When T < ∞ or |S| < ∞, any γ¯-admissible search π starting with a γ¯-admissible heuristic is complete.

Consequently, in the rest of the paper, we will implicitly assume that θ ≥ γ¯ so that the search π is θadmissible. This assumption can always be satisfied by increasing θ to γ¯ if necessary.

## 5.1 Exponential Solution Cost

The amount of backtracking an agent performs is determined by inaccuracies of the initial heuristic as well as the learning quota control parameter (T). Is there a relation between T and solution cost produced by an algorithm? Bulitko and Lee (2006) showed that LRTS that prunes out duplicate states on its solution stack has a solution cost linear in T (cf. Section 6 for more discussion). Until now, it was not known whether this upper bound is specific to LRTS. In this section we show that any θ-admissible search has an upper bound on the solution cost exponential in T. We then show that the bound is tight by demonstrating an example in which the the bound is achieved.

Theorem 5.2 (Exponential upper-bound). There exists a positive integer ∆ such that for any θ-admissible search π and any start state s0 the solution cost is upper-bounded by:

$$\left(2\theta\operatorname{dist}(s_{0},S_{g})+{\frac{\Delta\varepsilon}{\ln2}}\right)2^{\frac{T}{\Delta\varepsilon}}.$$

Theorem 5.3 (Example of exponential cost). There exists a search problem G and a 1-admissible search π, T = 12m, γ¯ = 1 where m is a positive integer such that the solution cost is 9 · 2 m+1 −5 (i.e., exponential in T).

## 5.2 Linear Solution Cost

In this section we define a subclass of the exponential class whose members have solution cost linear in T.

We then demonstrate that this class is non-empty by constructively defining two families of policies that belong to the linear subclass (Figure 5.1).

![0_image_0.png](0_image_0.png)

