Multitasking: Optimal Planning for Bandit Superprocesses

Dylan Hadfield-Menell, Stuart Russell

Abstract

This paper addresses the computational challenges of Bandit Superprocesses (BSPs), a class of multitasking problems where an agent must manage multiple independent tasks under a single-action constraint. We introduce Branch-and-Bound Value Iteration (BBVI), an algorithm that utilizes a novel "dominated relaxation" to compute tight upper bounds on task values. By transforming complex MDPs into simpler processes that satisfy the Whittle condition, BBVI enables optimal planning in state spaces as large as $10^{30}$, significantly outperforming traditional factored MDP solvers.

Introduction

In real-world scenarios, agents are frequently required to multitask—deciding, for instance, whether to answer an email, work on a research paper, or prepare a meal. Formally, these scenarios are modeled as Bandit Superprocesses (BSPs): a collection of independent Markov Decision Processes (MDPs) linked by a shared "budget" of time.

The primary challenge in solving BSPs is the exponential growth of the state space. For a set of 10 tasks each with 100 states, the combined state space reaches $10^{20}$, rendering standard solvers ineffective. Additionally, local optimality within a single task does not guarantee global optimality; because acting in one task delays rewards in others, the optimal strategy must account for the opportunity cost of time.

Methodology

The authors bridge the gap between simple multi-armed bandits and complex multitasking through three main contributions centered around the Branch-and-Bound Value Iteration (BBVI) algorithm.

Dominated Relaxation and the Whittle Integral

The core innovation is the dominated relaxation, a method to "relax" an MDP by adding specific durative actions. This transformation simplifies a complex MDP into a process that satisfies the "Whittle condition," allowing it to be treated like a standard multi-armed bandit. This provides a constructive way to calculate a tight upper bound on the value of the multitasking problem.

Figure 3: (a, b) Value function plots used to compute the Whittle integral; (c) Example of a dominated relaxation adding a durative action (dashed line).

Furthermore, the paper introduces a simplified algorithm to compute the Whittle integral—a theoretical value used to bound the superprocess—using any standard MDP solver as a black box.

Branch-and-Bound Value Iteration (BBVI)

BBVI maintains upper and lower bounds on action values. It employs a branch-and-bound approach to prune provably suboptimal actions and focuses computational resources on expanding the most promising parts of the state space (an "envelope" method).

Experimental Evaluation

The algorithm was evaluated on two synthetic but representative multitasking domains: Synthetic Grid Worlds and R&D Resource Allocation.

R&D Resource Allocation

In the R&D domain, an agent manages multiple product development tracks. For each product, the agent must choose between "Safe Research" (slow but reliable) and "Risky Research" (fast but prone to failure).

Figure 6: State-transition diagram for the R&D Resource Allocation domain, illustrating the trade-off between risky and safe research strategies.

Key Results

  • Massive Scalability: BBVI successfully computed optimal actions for problems with state spaces exceeding $10^{30}$.
  • Performance Edge: In the R&D domain, BBVI was approximately 5 orders of magnitude faster than SPUDD, a standard factored MDP solver.
  • Efficiency: Compared to Labeled Real-Time Dynamic Programming (LRTDP), BBVI converged significantly faster due to the tightness of its Whittle-based upper bounds.

Conclusion

The research demonstrates that for many practical multitasking problems, the complexity of finding the optimal action scales closer to linearly with the number of tasks rather than exponentially. By integrating dominated relaxations with branch-and-bound techniques, BBVI provides a powerful framework for high-dimensional optimal planning in independent subproblems. Future work may explore global resource constraints where agents can act in multiple tasks simultaneously.

Summary updated

BibTeX
@inproceedings{hadfieldmenell2015multitasking,
  author = {Dylan Hadfield-Menell and Stuart Russell},
  title = {{Multitasking: Optimal Planning for Bandit Superprocesses}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
}
Figure