Schedules and Prioritization: A Behavioral Foundation for Multi-Armed Bandits and Stopping Problems

Technical Summary: Schedules and Prioritization: A Behavioral Foundation for Multi-Armed Bandits and Stopping Problems

Problem Statement
Standard economic formulations of multi-armed bandits (MAB) and optimal stopping problems typically begin with exogenous primitives: a collection of arms governed by known Markov processes, state spaces, reward structures, and transition rules. The decision maker is then presented with these objects and asked to derive an optimal policy. This paper argues that such formulations skip a crucial behavioral step. In many economic contexts, decision makers do not face pre-specified "machines" or "arms." Instead, they face "strands of responsibility" (e.g., work projects, family obligations, experiments) that unfold in their own internal time. The fundamental economic problem is to fit these distinct, locally evolving strands into a single, scarce calendar. The paper seeks to provide a behavioral foundation for bandit problems by deriving the bandit structure from preferences over these local strands, rather than assuming the bandit structure as a primitive.

Methodology
The paper employs an axiomatic approach rooted in revealed preference theory and recursive decision theory. The methodology proceeds in three distinct stages:

1. Primitive Domain Definition: The primitive objects are defined as local contingent schedules. A schedule is a map from local histories (internal time) to consequences, terminating at a finite date along every branch. These schedules represent the possible unfoldings of a single responsibility strand before it is placed into a common calendar.
2. Single-Strand Representation (Stopping): The authors impose behavioral axioms on preferences over a single schedule to characterize a recursive stopping representation.
   • Deterministic-stream axioms (D1–D8): These establish a common utility scale for current consequences and a geometric discount factor over local time, ensuring stationarity and independence for deterministic flows.
   • Recursive one-step axioms (R1–R6): These govern the trade-off between a current consequence and a contingent folder of future continuations. They ensure that equivalent continuations can be substituted, branchwise improvements are respected, and current/future trade-offs are stable.
   • Result: These axioms yield a generalized recursive stopping representation where the value of a schedule is the current utility plus a discounted aggregator of continuation values.
3. Multi-Strand Integration (Bandit): To move from a single strand to a multi-strand problem, the paper introduces a scarcity constraint: the elapsed-calendar constraint. Only one local clock can advance per calendar period.
   • Common-Tail Compensation Axiom (R7): A critical behavioral restriction is introduced to ensure that scalar changes in continuation values remain scalar after aggregation. This "cash additivity" property allows a scalar shadow price of calendar time to be defined consistently across different strands, even when continuation evaluation is nonlinear (e.g., under ambiguity or rank dependence).
   • Result: Combining the recursive representation with the calendar constraint yields a rested generalized multi-armed bandit.

Key Contributions and Results

• Derivation of the Bandit Structure: The paper demonstrates that a multi-armed bandit is not a primitive object but a representation derived from preferences over stopped local schedules subject to a calendar constraint. The "arms" are not exogenous Markov machines but represented responsibility strands.
• Generalized Recursive Stopping Representation: Theorem 1 establishes that preferences over stopped schedules are equivalent to a recursive evaluation involving a current utility, local discounting, and a broad continuation aggregator. This aggregator is not restricted to expected utility; it can accommodate ambiguity, robustness, and rank dependence.
• Index Optimality via Shadow Prices: The central result (Theorem 2) proves that the optimal policy for the elapsed-calendar constrained problem is an index policy.
  • The index for a strand is defined as the critical shadow price of calendar time at which the decision maker is indifferent between advancing the strand and putting it on hold indefinitely.
  • The "common-tail compensation" axiom is shown to be the necessary condition for this scalar shadow price to be well-defined and for the index policy to be optimal.
  • The optimal rule is to advance the strand with the highest current index.
• Unification of Special Cases: The framework recovers familiar models as special cases by imposing additional restrictions on the schedule domain or the continuation aggregator:
  • Subjective Expected Utility (SEU): Imposing independence on continuation schedules yields a linear aggregator (subjective transition kernel), recovering the classical Gittins–Jones index.
  • Learning: Beliefs are treated as local states. Advancing a strand updates the belief (local state), while resting it freezes the belief. This recovers Bayesian learning bandits.
  • Variational and Max–Min Preferences: By allowing the aggregator to be a variational or max-min operator, the paper derives robust indices that account for dynamic ambiguity without linking uncertainty across distinct strands.
  • Rank-Dependent and Choquet Preferences: These allow for non-additive evaluation of branches, capturing "fear of missing out" on salient future outcomes.
  • Pandora's Problem: By restricting the schedule domain such that uncertainty is resolved in a single step (opening a box), the general index reduces to a reservation value, recovering Weitzman's rule.

Significance and Claims
The paper claims to provide a foundational behavioral justification for bandit models, analogous to how consumer theory derives demand from preferences over bundles rather than assuming demand curves.

• Foundational Shift: The paper argues that transition laws, ambiguity sets, and reservation values are not starting points but emerge from restrictions on preferences or the schedule domain. The "arm" is a represented responsibility strand, and the "bandit" is a prioritization problem for local advancement under a scarce calendar.
• Role of the Index: The index is not an external ranking rule imposed by the analyst but is derived as the Lagrange multiplier (shadow price) of the calendar constraint. A high index signifies that a strand's next step is valuable even when calendar time is expensive.
• Flexibility: The framework is designed to be broad, accommodating various attitudes toward uncertainty (ambiguity, robustness, rank dependence) within individual strands while maintaining the product structure of the multi-strand problem. This contrasts with robust bandit literature that often places ambiguity on the joint environment, potentially linking otherwise independent projects.
• Scope: The paper explicitly limits its scope to "rested" bandits (strands do not evolve while unattended) and a single calendar. It notes that extensions to "restless" bandits or multiple scarce inputs are natural but left for future work.

In summary, the paper establishes that the complex machinery of dynamic resource allocation under uncertainty can be built from the same ingredients as static choice: a primitive domain of alternatives, behavioral restrictions yielding a representation, and a scarcity constraint.