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

Sintesi Tecnica: Programmazioni e Prioritizzazione: Una Fondazione Comportamentale per i Multi-Armed Bandits e i Problemi di Arresto

Enunciato del Problema
Le formulazioni economiche standard dei multi-armed bandits (MAB) e dei problemi di arresto ottimale (optimal stopping) iniziano tipicamente con primitivi esogeni: una collezione di bracci governati da processi markoviani, spazi di stato, strutture di ricompensa e regole di transizione noti. Al decisore viene quindi presentato questo insieme di oggetti e gli si chiede di derivare una politica ottimale. Questo articolo sostiene che tali formulazioni saltino un passaggio comportamentale cruciale. In molti contesti economici, i decisori non affrontano "macchine" o "bracci" pre-specificati. Affrontano invece "filamenti di responsabilità" (ad esempio, progetti lavorativi, obblighi familiari, esperimenti) che si sviluppano nel proprio tempo interno. Il problema economico fondamentale è quello di inserire questi distinti filamenti, che evolvono localmente, in un unico calendario scarso. L'articolo mira a fornire una fondazione comportamentale ai problemi di bandit derivando la struttura del bandit dalle preferenze su questi filamenti locali, piuttosto che assumere la struttura del bandit come un primitivo.

Metodologia
L'articolo impiega un approccio assiomatico radicato nella teoria delle preferenze rivelate e nella teoria decisionale ricorsiva. La metodologia procede attraverso tre fasi distinte:

1. Definizione del Dominio Primitivo: Gli oggetti primitivi sono definiti come programmazioni contingenti locali. Una programmazione è una mappa da storie locali (tempo interno) a conseguenze, che termina in una data finita lungo ogni ramo. Queste programmazzioni rappresentano i possibili sviluppi di un singolo filamento di responsabilità prima che venga inserito in un calendario comune.
2. Rappresentazione a Singolo Filamento (Arresto): Gli autori impongono assiomi comportamentali sulle preferenze relative a una singola programmazione per caratterizzare una rappresentazione di arresto ricorsiva.
   • Assi di flusso deterministico (D1–D8): Questi stabiliscono una scala di utilità comune per le conseguenze correnti e un fattore di sconto geometrico sul tempo locale, garantendo stazionarietà e indipendenza per i flussi deterministici.
   • Assi ricorsivi a un passo (R1–R6): Questi governano il compromesso tra una conseguenza corrente e un insieme contingente di continuazioni future. Garantiscono che continuazioni equivalenti possano essere sostituite, che i miglioramenti per ramo siano rispettati e che i trade-off tra presente e futuro siano stabili.
   • Risultato: Questi assi producono una rappresentazione di arresto ricorsiva generalizzata in cui il valore di una programmazione è l'utilità corrente più un aggregatore scontato dei valori di continuazione.
3. Integrazione Multi-Filamento (Bandit): Per passare da un singolo filamento a un problema multi-filamento, l'articolo introduce un vincolo di scarsità: il vincolo del calendario trascorso. Solo un orologio locale può avanzare per periodo di calendario.
   • Assioma di Compensazione della Coda Comune (R7): Viene introdotta una restrizione comportamentale critica per garantire che i cambiamenti scalari nei valori di continuazione rimangano scalari dopo l'aggregazione. Questa proprietà di "additività del contante" permette di definire coerentemente un prezzo ombra scalare del tempo di calendario tra i diversi filamenti, anche quando la valutazione delle continuazioni è non lineare (ad esempio, sotto ambiguità o dipendenza dal rango).
   • Risultato: Combinando la rappresentazione ricorsiva con il vincolo del calendario, si ottiene un bandit generalizzato "riposato" (rested).

Contributi Chiave e Risultati

• Derivazione della Struttura del Bandit: L'articolo dimostra che un multi-armed bandit non è un oggetto primitivo, ma una rappresentazione derivata da preferenze su programmazioni locali interrotte soggette a un vincolo di calendario. I "bracci" non sono macchine markoviane esogene, ma rappresentano filamenti di responsabilità.
• Rappresentazione di Arresto Ricorsiva Generalizzata: Il Teorema 1 stabilisce che le preferenze sulle programmazioni interrotte sono equivalenti a una valutazione ricorsiva che coinvolge un'utilità corrente, uno sconto locale e un ampio aggregatore di continuazione. Questo aggregatore non è limitato all'utilità attesa; può ospitare ambiguità, robustezza e dipendenza dal rango.
• Ottimalità dell'Indice tramite Prezzi Ombra: Il risultato centrale (Teorema 2) prova che la politica ottimale per il problema con vincolo di calendario trascorso è una politica di indice.
  • L'indice per un filamento è definito come il prezzo ombra critico del tempo di calendario al quale il decisore è indifferente tra far avanzare il filamento e metterlo in pausa indefinitamente.
  • Si dimostra che l'assioma di "compensazione della coda comune" è la condizione necessaria affinché tale prezzo ombra scalare sia ben definito e affinché la politica di indice sia ottimale.
  • La regola ottimale è far avanzare il filamento con l'indice corrente più elevato.
• Unificazione dei Casi Speciali: Il framework recupera modelli familiari come casi speciali imponendo restrizioni aggiuntive sul dominio delle programmazioni o sull'aggregatore di continuazione:
  • Utilità Attesa Soggettiva (SEU): Imponendo l'indipendenza sulle programmazioni di continuazione, si ottiene un aggregatore lineare (kernel di transizione soggettivo), recuperando il classico indice di Gittins–Jones.
  • Apprendimento (Learning): Le credenze sono trattate come stati locali. Far avanzare un filamento aggiorna la credenza (stato locale), mentre metterlo in pausa la congela. Questo recupera i bandit di apprendimento bayesiano.
  • Preferenze Variazionali e Max–Min: Consentendo all'aggregatore di essere un operatore variazionale o max-min, l'articolo deriva indici robusti che tengono conto dell'ambiguità dinamica senza collegare l'incertezza tra distinti filamenti.
  • Preferenze Rank-Dependent e di Choquet: Queste permettono una valutazione non additiva dei rami, catturando la "paura di perdere un'opportunità" (fear of missing out) derivante da esiti futuri salienti.
  • Problema di Pandora: Restringendo il dominio delle programmazioni in modo che l'incertezza si risolva in un singolo passaggio (aprire una scatola), l'indice generale si riduce a un valore di riserva, recuperando la regola di Weitzman.

Significatività e Rivendicazioni
L'articolo sostiene di fornire una giustificazione comportamentale fondamentale per i modelli di bandit, analogamente a come la teoria del consumatore deriva la domanda da preferenze su panieri piuttosto che assumere curve di domanda.

• Spostamento Fondativo: L'articolo sostiene che le leggi di transizione, gli insiemi di ambiguità e i valori di riserva non sono punti di partenza, ma emergono da restrizioni sulle preferenze o sul dominio delle programmazioni. Il "braccio" è un filamento di responsabilità rappresentato, e il "bandit" è un problema di prioritizzazione per l'avanzamento locale sotto un calendario scarso.
• Ruolo dell'Indice: L'indice non è una regola di classificazione esterna imposta dall'analista, ma è derivato come moltiplicatore di Lagrange (prezzo ombra) del vincolo di calendario. Un indice elevato significa che il passo successivo di un filamento è prezioso anche quando il tempo di calendario è costoso.
• Flessibilità: Il framework è progettato per essere ampio, accogliendo vari atteggiamenti verso l'incertezza (ambiguità, robustezza, dipendenza dal rango) all'interno dei singoli filamenti, pur mantenendo la struttura di prodotto del problema multi-filamento. Ciò contrasta con la letteratura sui bandit robusti che spesso pone l'ambiguità sull'ambiente congiunto, potenzialmente collegando progetti altrimenti indipendenti.
• Ambito: L'articolo limita esplicitamente il suo ambito ai bandit "riposati" (i filamenti non evolvono mentre sono trascurati) e a un singolo calendario. Nota che le estensioni ai bandit "instabili" (restless) o a molteplici input scarsi sono naturali ma lasciate come lavoro futuro.

In sintesi, l'articolo stabilisce che la complessa macchina dell'allocazione delle risorse sotto incertezza può essere costruita partendo dagli stessi ingredienti della scelta statica: un dominio primitivo di alternative, restrizioni comportamentali che portano a una rappresentazione e un vincolo di scarsità.