Calculating Probability of Discovery
I have a planner that can evaluate N arbitrary states, and calculate their fitness. The domains it evaluates have no explicit "end state", so it has an infinite horizon.

What are good methods for calculating when it should stop evaluating states?

My current approach is to estimate the probability of the next evaluation being the next "best" state, and to stop if this probability falls below a certain threshold.

e.g. After evaluating each state, I increment a counter, and after a new best fitness if found, I reset that counter, resulting in a sequence like:

    steps = [0, 1, 2, 0, 1, 2, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4]

I can then iterate over this and form a simple discrete probability of each step preceding the next best fitness:

    from collections import defaultdict
    counts = defaultdict(int)
    totals = defaultdict(int)
    for step,next in zip(steps, steps[1:]):
        counts[step] += next == 0
        totals[step] += 1
    for k in sorted(counts.keys()):
        print k,counts[k],totals[k],'%.2f' % (counts[k]/float(totals[k]),)

resulting in:

    0 0.43
    1 0.00
    2 0.50
    3 0.00
    4 0.00
    5 0.00
    6 0.00
    7 0.00
    8 0.00
    9 0.00
    10 1.00

How do I take these discrete probabilities and form a general approximation for the probability of P(next step is the best | current step since last best) given an arbitrary step integer (especially for high step counts I may not have reached)?

Calculating Probability of Discovery
===

I have a planner that can evaluate N arbitrary states, and calculate their fitness. The domains it evaluates have no explicit "end state", so it has an infinite horizon.

What are good methods for calculating when it should stop evaluating states?

My current approach is to estimate the probability of the next evaluation being the next "best" state, and to stop if this probability falls below a certain threshold.

e.g. After evaluating each state, I increment a counter, and after a new best fitness if found, I reset that counter, resulting in a sequence like:

    steps = [0, 1, 2, 0, 1, 2, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4]

I can then iterate over this and form a simple discrete probability of each step preceding the next best fitness:

    from collections import defaultdict
    counts = defaultdict(int)
    totals = defaultdict(int)
    for step,next in zip(steps, steps[1:]):
        counts[step] += next == 0
        totals[step] += 1
    for k in sorted(counts.keys()):
        print k,counts[k],totals[k],'%.2f' % (counts[k]/float(totals[k]),)

resulting in:

    0 0.43
    1 0.00
    2 0.50
    3 0.00
    4 0.00
    5 0.00
    6 0.00
    7 0.00
    8 0.00
    9 0.00
    10 1.00

How do I take these discrete probabilities and form a general approximation for the probability of P(next step is the best | current step since last best) given an arbitrary step integer (especially for high step counts I may not have reached)?
