• Assume all-or-nothing problems
• Goal: Minimize expected delay for reaching
complete solutions
to challenges posed in the next period(s)
• Theorem: Idle-Time Partition
The optimal policy
is to spend available idle time solving future problems
completely, in order of their probability.
Minimizing
Computational Delay
p( I1
| E )
p( In
| E )
p( I2
| E )
p( I3
| E )
p( I n | E ) > p( I n+1 | E )
p( I1 | E )
p( I2 | E )
p( I3 | E )
p( In | E )
Eric Horvitz, April 5, 2003