AI Glossary / Graphs and symbolic AI / Advanced

Bandit superprocess

Definition

A bandit superprocess is a sequential decision problem made from several independent Markov decision processes, with a shared restriction that only one process can be acted on at each step. The decision includes both which process to select and which action to take inside it.

What it means

An ordinary bandit model can be viewed as choosing among arms whose selected operation is fixed. A bandit superprocess gives each arm its own internal choices and state transitions. Selecting a project is therefore only part of the decision; the agent must also decide how to work on it.

In the standard rested formulation considered here, unselected processes remain in their current states. The processes are independent except for competition over the shared opportunity to act. A common discount factor makes the timing of rewards important.

Optimizing every process separately and then combining the resulting plans need not produce the best overall policy. An action that is attractive when one project is considered alone may delay rewards available elsewhere. That opportunity cost can change the preferred action within the project itself.

How it works

Each component has states, available actions, transition probabilities and rewards. The overall state records the current state of every component. At each step, the agent chooses a component-action pair, receives its reward and updates that component according to its transition model.

Planning evaluates present rewards together with discounted future rewards across the whole collection. Although the components are independent locally, the shared action limit couples their scheduling.

Research therefore studies bounds and structured planning methods that exploit the component organization. Classical index results for simpler bandit models do not automatically justify solving every component independently in this more general setting. Before applying the formulation, check whether idle projects truly remain unchanged and whether actions in one project affect the others. Deadlines, deterioration and shared materials may require a richer model.

Three practical examples

• A research simulation allocates one analysis step at a time among independent tasks, each offering several ways to progress.
• A planning team studies a portfolio of pauseable digital jobs whose internal processing choices affect future rewards.
• An educational decision model compares working briefly on one project with investing several steps before receiving its payoff.

Think of it this way

Think of several board games on separate tables, with permission to make only one move across all tables per turn. Each table offers different legal moves, and unattended games wait unchanged.

The analogy is bounded by that waiting assumption. Real projects may lose value, receive new information or consume resources while unattended. If that happens, the independent rested-process picture no longer captures the full decision problem.

Worked example

Why another project changes the preferred action

Use an invented infinite-horizon problem with discount factor 0.5. Project X offers two choices. “Quick” gives reward 5 immediately and ends X. “Invest” gives 0 now, then allows reward 12 on the next step before X ends. Alone, X prefers investing because 0.5 × 12 = 6, which exceeds 5.

Now add independent Project Y, which gives reward 4 whenever selected and can continue indefinitely. Selecting Y forever has value 4 + 2 + 1 + … = 8.

Taking Quick in X and then Y forever gives 5 + 0.5 × 8 = 9. Investing in X, collecting 12 next, and then using Y gives 0 + 0.5 × 12 + 0.25 × 8 = 8. Starting with Y and then the best X-first plan gives 4 + 0.5 × 9 = 8.5.

Thus Quick is preferable in the combined setting, even though Invest was preferable for X alone. The arithmetic illustrates opportunity cost under the stated model, not a general business investment rule.

Illustrative case study

Fictional case: Cedar Analysis schedules independent, pauseable data-processing jobs. Each job offers a quick approximate result or a longer refinement path. A prototype chooses each job's internally preferred path before deciding which job to run next.

Reviewers notice that this ignores the value delayed in other jobs. They build a small combined model and compare policies under explicit reward and discount assumptions. They also identify jobs whose data expire while waiting and exclude them from the simple rested formulation.

The lesson is twofold: local optimization may miss a shared-resource tradeoff, and a mathematically appropriate solution still depends on whether the component assumptions match the actual workflow.

Common misconceptions and mistakes

• It is just a larger ordinary bandit with no internal choices. Each component can offer multiple actions.
• Independent components can always be optimized separately. Their competition for action time affects global choices.
• Idle components evolve freely in the standard model. The rested formulation freezes unselected states.
• A familiar index policy is automatically optimal. Results for narrower bandit assumptions need not transfer.
• A reward function is an objective fact. It is a modeling choice that must reflect the intended task.

Business use

The concept helps business readers recognize a common planning error: evaluating projects as though each had exclusive access to attention or computation.

Use it where its assumptions are defensible, particularly for independent processes that can genuinely pause. Document the reward scale, timing preferences and shared action limit. Compare sensitivity to those choices before treating a policy as operational advice. If projects affect one another or change while idle, represent those effects rather than forcing them into an unsuitable model.

People also ask

Is a bandit superprocess necessarily about learning unknown rewards?

No. It can be a planning problem with known transition and reward models.

What distinguishes it from a restless bandit?

In a restless model, unselected components can change state; the standard rested superprocess described here leaves them unchanged.

Does it always permit only one active component?

That is the formulation used here. Related resource-allocation models can impose other limits, requiring their own analysis.

Check your understanding

A project has the best standalone plan. Does that prove the same internal actions are best when several projects share one worker?

Answer: No. Time spent on that plan delays other rewards, so the globally preferred internal action can differ.

Related terms

• Markov decision process
• Policy
• Discount factor
• Opportunity cost
• Dynamic programming
• multi-armed bandit
• restless bandit
• resource allocation

Learn next

Create two pauseable toy projects with alternative actions and explicit reward timings. Compare each project's standalone preference with the combined schedule. Change the discount factor and examine which decisions change. Study ordinary bandit models first, then identify exactly which additional choices create the superprocess.

• Discount factor

More in Graphs and symbolic AI

• Backtracking search - Backtracking search builds a candidate solution through a sequence of tentative choices.
• Backward-chaining - Backward chaining is a goal-directed inference method that starts with a question and works backward through rules that could establish its answer.
• Balance - Balance, in the fairness sense used by the source glossary, requires a classifier to have approximately equal false-positive rates and false-negative rates...
• Bang-bang control
• Baseline - Baseline has two important AI-related meanings in the supplied sources. In model evaluation, it is a reference method or result used for comparison.
• Batch inference - Batch inference is the use of a trained model to produce predictions for a collection of inputs together, typically outside an immediate user-request path.

Sources

Hadfield-Menell and Russell, Multitasking: Efficient Optimal Planning for Bandit Superprocesses, defines the model and explains why local and global policies can differ: https://aima.cs.berkeley.edu/~russell/papers/uai15-multi.pdf

AIMA glossary provides the source-list terminology: https://github.com/aimacode/aima-glossary/blob/master/glossary.md?plain=1

The two-project calculation and fictional scheduling case are original illustrations.

Previous: Banding Next: Bang-bang control