Take It or Leave It II: A Game Show for Computers
Groovy $713337 $817829 $818227

Bootstrap code:

class Instance {
    List values = new ArrayList(1..10000); {
        Collections.shuffle(values)
    }
    int i = 0
    int value = 0
    int max = 0
    int nextOracle = 0

    def pass() {
        if (i &gt;= 10000)
            throw new NoSuchElementException()
        i++
    }

    def take() {
        if (i &gt;= 10000)
            throw new NoSuchElementException()
        int v = values[i]
        if (v &gt; max) {
            max = v
            value += v
        }
        i++
    }

    double oracle(int m) {
        if (m &lt;= 0 || i &lt; nextOracle || i + m &gt;= 10000)
            throw new NoSuchElementException()

        nextOracle = i + m
        values.subList(i + 1, i + m + 1).stream().reduce { l, r -&gt; r+l }.get() / m
    }

    int read() {
        if (i &gt;= 10000)
            throw new NoSuchElementException()
        values[i]
    }
}


Algorithm

double square(double v) { v * v }
final double factor = Math.pow(1.5, 1.1)
int attempts = 5000
(1..attempts).stream().parallel().mapToLong {
    def puzzle = new Instance()

    int[] memory = 1..10000 // We will remember every envelope
    int memStart = 0

    while (memStart &lt; 10000 - 3) {
        int value = puzzle.read()
        int i = Arrays.binarySearch(memory, memStart, 10000, value) - memStart
        if (i &lt; 0) { // We can't use the money
            puzzle.pass()
            continue
        }
        if (i == 0) { // Of course we take the lowest
            puzzle.take()
            memStart++
            continue
        }
        int remaining = Arrays.stream(memory, i + 1 + memStart, 10000).sum() // Money we could win if taken
        int losing = Arrays.stream(memory, memStart, memStart + i).sum() // Money we cna't win if taken
        if (value &gt; losing) { // If we pass, we lose money automatically
            puzzle.take()
            memStart += i + 1
        } else if ((losing - value * 16 / 7) * square(Math.log(i)) &gt; remaining / factor) {
            System.arraycopy(memory, memStart, memory, ++memStart, i)
            puzzle.pass()
        } else {
            puzzle.take()
            memStart += i + 1
        }
    }

    // It's broken down to last three elements
    List values = Arrays.copyOfRange(memory, 10000 - 3, 10000)
    while (!values.contains(puzzle.read())) // Skip values we can't use
        puzzle.pass()
    int value1 = puzzle.read()
    int value2 = puzzle.oracle(1)
    if (value1 == values.max() &amp;&amp; (
            values.contains(value2)
            ? (value1 * 2 &lt; values.sum() &amp;&amp; values.min() == value2)
            : (value1 &lt; values.min() / 2 + (values - [value1]).max())
            )) {
        puzzle.pass()
    }

    // Finish it
    while (puzzle.i &lt; puzzle.values.size()) {
        puzzle.take()
    }

    puzzle.value as Long
}.sum() / attempts // Sum runs and average


I compare remaining values with possible values. This script is not fast (takes 1-minute per 1000x simulations)... but it will perform the simulations simultaneously.

I have no idea why my algorithm works, but it was just trial and error: lumping mathematical operations together and manipulating the constants. I ran it 5000x for the current score, in an attempt to reduce the score's fluctuations (it's +/- $4000 depending on iteration count).

Even without the oracle at the end, it should still be (barely) beating @orlp's solution for the prior puzzle.