What Do We Care About in Bandits with Noncompliance? BRACE: Bandits with Recommendations, Abstention, and Certified Effects

Die Arbeit führt BRACE ein, einen parameterfreien Algorithmus für Banditen mit Nichtkonformität, der durch eine klare Unterscheidung zwischen Empfehlungswohlfahrt und Behandlungseffekten sowie durch zertifizierte Intervalle sowohl die optimale Empfehlungsstrategie als auch die strukturell optimale Behandlungsstrategie unter Unsicherheit und schwacher Identifikation zuverlässig ermittelt.

Das Wesentliche

Stell dir vor, du bist ein Koch, der in einem Restaurant arbeitet. Deine Aufgabe ist es, den Gästen die besten Gerichte zu empfehlen. Aber hier ist der Haken: Du hast keine direkte Kontrolle darüber, was auf den Teller kommt.

• Du (der Lerner): Du sagst dem Kellner: „Gast A, nimm bitte das Steak!"
• Der Kellner (die Compliance): Der Kellner hört zu, aber vielleicht denkt er: „Der Gast sieht heute sehr müde aus, ich bringe ihm lieber eine Suppe." Oder der Gast selbst sagt: „Nein, ich will Fisch."

In der klassischen Welt des „Bandit-Problems" (eine Art mathematisches Glücksspiel, bei dem man lernt, welche Aktion die beste Belohnung bringt) würde man einfach annehmen: Du sagst Steak, der Gast bekommt Steak. Aber in der realen Welt ist das oft nicht so.

Diese neue Forschung (das Papier „BRACE") fragt sich: Was genau wollen wir eigentlich erreichen? Und die Antwort ist: Es kommt darauf an!

Hier ist die einfache Erklärung der drei Ziele, die das Papier unterscheidet:

1. Das Ziel „Empfehlung" (REC) – Der aktuelle Chef

Stell dir vor, das Restaurant bleibt genau so, wie es ist. Der Kellner darf immer noch entscheiden, ob er deine Empfehlung umsetzt oder nicht.

• Die Frage: Welche Empfehlung sollte ich geben, damit die Gäste jetzt gerade am glücklichsten sind, unter Berücksichtigung des Kellners?
• Die Analogie: Du lernst, welche Gerichte du empfehlen musst, damit der Kellner sie trotzdem serviert (oder der Gast sie annimmt). Vielleicht ist das Steak gar nicht die beste Empfehlung, weil der Kellner es immer ablehnt. Vielleicht ist die Suppe die bessere Empfehlung, weil der Kellner sie gerne serviert und die Gäste sie mögen.
• Warum das wichtig ist: Wenn du nur die Suppe empfiehlst, weil du weißt, dass der Kellner sie bringt, hast du den aktuellen Prozess optimiert.

2. Das Ziel „Behandlung" (TRT) – Der zukünftige Chef

Stell dir vor, das Restaurant wird umgebaut. In der Zukunft gibt es keinen Kellner mehr, der entscheidet. Du drückst einen Knopf, und die Küche serviert genau das, was du willst.

• Die Frage: Welches Gericht ist wirklich das beste für den Gast, wenn wir den Kellner umgehen könnten?
• Die Analogie: Vielleicht ist das Steak das absolut beste Gericht für den Gast. Aber weil der Kellner es oft ablehnt, hast du in der Vergangenheit nur Suppe empfohlen. Wenn du jetzt lernst, dass das Steak das Beste ist, kannst du das für die Zukunft wissen. Aber: Wenn du das Steak jetzt empfiehlst, wird der Kellner es vielleicht ablehnen, und der Gast bekommt wieder Suppe.
• Der Konflikt: Das beste Gericht für die Zukunft (Steak) ist vielleicht nicht die beste Empfehlung für die Gegenwart (Suppe).

3. Das Ziel „Sicherheit" (INF) – Der Versicherungsmakler

Manchmal ist man sich nicht sicher, ob man genug Daten hat, um eine Entscheidung zu treffen.

• Die Frage: Können wir mit Sicherheit sagen, was das Beste ist? Oder sind wir uns noch zu unsicher?
• Die Analogie: Wenn der Kellner sehr unberechenbar ist (manchmal nimmt er das Steak, manchmal die Suppe, ohne dass man den Grund sieht), ist es gefährlich, eine feste Regel zu erstellen. Das Papier sagt: „Wenn wir unsicher sind, sollten wir lieber nichts tun oder sehr breite Unsicherheitsbereiche angeben, anstatt eine falsche Regel zu erfinden."

---

Das Problem: Warum verwechseln wir das?

In der Vergangenheit haben Forscher oft nur auf das „Steak" (die Behandlung) geschaut. Sie dachten: „Wenn wir herausfinden, dass Steak das Beste ist, ist das die Lösung."
Aber das Papier zeigt: Das ist falsch, wenn ein Kellner dazwischengeschaltet ist.

Es gibt Situationen, in denen die beste Empfehlung (Suppe) den Gast jetzt glücklicher macht als die beste Behandlung (Steak), einfach weil der Kellner das Steak blockiert. Wenn man nur auf das Steak schaut, verpasst man die Chance, den Gast heute glücklich zu machen.

Die Lösung: BRACE (Der kluge Koch-Assistent)

Die Forscher haben einen neuen Algorithmus namens BRACE entwickelt. Stell dir das wie einen sehr vorsichtigen, aber cleveren Koch-Assistenten vor:

1. Er fragt zuerst: „Was wollen wir? Den aktuellen Prozess verbessern (Empfehlung) oder die Zukunft planen (Behandlung)?"
2. Er testet vorsichtig: Er probiert verschiedene Gerichte aus, aber nur so lange, bis er sicher ist.
3. Er hat einen „Notfall-Plan" (Zertifizierung): Wenn der Kellner zu unberechenbar ist (die Daten sind zu verrauscht), sagt der Assistent: „Ich traue mir nicht zu, eine Regel für das Steak aufzustellen. Ich empfehle lieber gar nichts oder sage: 'Wir wissen es noch nicht genau'."
4. Er unterscheidet: Er kann gleichzeitig sagen: „Für heute empfehle ich Suppe (weil der Kellner sie bringt), aber für die Zukunft wissen wir, dass Steak das Beste ist."

Was lernen wir daraus?

Das Wichtigste an diesem Papier ist die Erkenntnis: Es gibt nicht „das eine" Ziel.

• Wenn du ein Arzt bist und ein Patient die Medikamente ablehnt, willst du vielleicht wissen, wie du den Patienten heute am besten berätst (Empfehlung), damit er die Pillen nimmt.
• Wenn du ein Forscher bist, der ein neues Medikament entwickelt, willst du wissen, ob das Medikament wirklich wirkt, wenn der Patient es nimmt (Behandlung).

Früher hat man diese Dinge oft vermischt. Dieses Papier sagt: „Haltet die Ziele sauber getrennt! Sonst macht ihr Fehler."

Zusammenfassend:
Stell dir vor, du versuchst, einen Zug zu steuern, aber du hast nur einen Hebel, der einen anderen Hebel bewegt, der dann den Zug bewegt.

• REC fragt: „Wie bewege ich meinen Hebel, damit der Zug jetzt fährt?"
• TRT fragt: „Wie müsste der Zug wirklich aussehen, wenn ich ihn direkt steuern könnte?"
• BRACE ist der Mechaniker, der dir sagt: „Wenn du den Hebel nicht sicher bewegen kannst, sag ich dir lieber, dass ich unsicher bin, anstatt den Zug in die falsche Richtung zu schieben."

Es geht also darum, genau zu wissen, was man eigentlich erreichen will, bevor man mit dem Lernen beginnt.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „BRACE: Bandits with Recommendations, Abstention, and Certified Effects" von Nicolás Della Penna auf Deutsch.

1. Problemstellung: Bandits mit Nicht-Compliance

Das klassische stochastische Bandit-Problem geht davon aus, dass die vom Lerner gewählte Aktion direkt die Behandlung (Treatment) darstellt, die dem Subjekt verabreicht wird. In vielen realen Anwendungen (z. B. medizinische Empfehlungen, algorithmische Vorschläge in der Lieferkette) ist dies jedoch nicht der Fall. Der Lerner wählt eine Empfehlung $Z$ (Instrument), aber die tatsächlich verabreichte Behandlung $X$ wird durch downstream-Akteure (z. B. Patienten, Ärzte, Moderatoren) bestimmt, die ihre eigenen privaten Informationen oder Präferenzen nutzen.

Dies führt zu einem Phänomen der Nicht-Compliance (Nicht-Befolgung). Die zentrale These des Papers ist, dass diese Trennung nicht nur das Feedback-Modell ändert, sondern fundamentale Auswirkungen auf das Lernziel hat. Es müssen drei unterschiedliche Ziele unterschieden werden, die nicht notwendigerweise übereinstimmen:

1. REC (Operational Recommendation Welfare): Maximierung des Wohlergehens unter dem aktuellen Empfehlungskanal, inklusive aller downstream-Übersteuerungen. Dies ist relevant, wenn der aktuelle Workflow beibehalten wird.
2. TRT (Structural Treatment Welfare): Lernen der besten Behandlungsregel für ein zukünftiges Regime mit direkter Behandlungskontrolle (ohne Empfehlungsschicht). Dies ist relevant für wissenschaftliche Aussagen über die Behandlung selbst.
3. INF (Scientific Inference): Bereitstellung valider Unsicherheitsintervalle (Confidence Sequences) für eines der oben genannten Ziele unter adaptiver Stichprobennahme und adaptivem Stoppen.

Das Paper argumentiert, dass diese Ziele oft divergieren. Ein Beispiel zeigt, dass eine Empfehlungspolitik, die private Informationen von downstream-Akteuren nutzt, strikt besser sein kann als jede direkt messbare Behandlungsregel des Lerners.

2. Methodik: Der BRACE-Algorithmus

Für den Fall endlicher Kontexte ($W = \{1, \dots, S\}$) und quadratischer Instrumente ($Z = X = [K]$) wird der BRACE-Algorithmus (Bandits with Recommendations, Abstention, and Certified Effects) vorgestellt.

Kernkomponenten:

• Phasen-Verdopplung (Phase Doubling): Der Algorithmus läuft in Phasen $r = 0, 1, 2, \dots$, wobei die Phase $r$ bei Zeit $t_r = 2^r$ endet.
• Uniforme Exploration: In jeder Phase werden Empfehlungen $Z_t$ gleichverteilt über den Aktionsraum gewählt, um konsistente Schätzer für Compliance-Matrizen und Erwartungswerte zu erhalten.
• Empirische Schätzung:
  • Schätzung der Compliance-Matrix $P(w)$ (Wahrscheinlichkeit, dass Empfehlung $z$ zu Behandlung $x$ führt).
  • Schätzung der operativen Mittelwerte $g(w)$ (Erwarteter Reward bei Empfehlung $z$).
• Matrix-Zertifizierung (Matrix Certification): Dies ist der entscheidende Sicherheitsmechanismus.
  • Der Algorithmus versucht, die strukturellen Mittelwerte $\mu(w)$ durch Inversion der geschätzten Compliance-Matrix zu berechnen: $\hat{\mu} = \hat{P}^{-1}\hat{g}$.
  • Eine Inversion wird nur durchgeführt, wenn die Matrix $\hat{P}(w)$ invertierbar ist und eine Norm-Bedingung erfüllt ist: $\|\hat{P}(w)^{-1}\|_\infty \cdot a_r(w) \leq 1/2$. Hierbei ist $a_r(w)$ ein Konfidenzradius für den Schätzfehler.
  • Wenn diese Bedingung nicht erfüllt ist (z. B. bei schwacher Identifikation oder schlechter Datenlage), wird die Inversion abgebrochen (Abstention). Stattdessen werden breite, aber ehrliche Intervalle zurückgegeben.
• Ziel-spezifische Intervalle:
  • Für REC werden direkte Intervalle um die operativen Mittelwerte gebildet.
  • Für TRT werden Intervalle um die strukturellen Mittelwerte gebildet, die nur gültig sind, wenn die Zertifizierung bestanden hat.
• Stop-Regel: Der Algorithmus stoppt die Exploration und commitet sich einer Politik, sobald ein strikter Gap zwischen dem unteren Konfidenzintervall der besten Politik und den oberen Intervallen aller anderen Politiken besteht.

3. Wichtige Beiträge

1. Formalisierung der Zielwahl: Das Paper definiert formal die Trennung zwischen operativer Empfehlungsoptimierung (REC) und struktureller Behandlungsoptimierung (TRT). Es zeigt, dass in mediatisierten Umgebungen die beste Empfehlungspolitik strikt besser sein kann als jede direkt messbare Behandlungsregel (Proposition 3.2).
2. BRACE-Algorithmus: Entwicklung eines parametrischen, zielorientierten Algorithmus, der Matrix-Zertifizierung verwendet, um Instabilitäten bei der IV-Inversion (Instrumental Variable) zu vermeiden.
3. Theoretische Garantien:
   • Gleichzeitige Gültigkeit: Mit Wahrscheinlichkeit $1-\delta$ liegen die wahren Werte innerhalb der berechneten Intervalle für alle Phasen.
   • Identifikation: BRACE identifiziert die optimale operative Politik (REC) und die optimale strukturelle Politik (TRT) mit fester Lücke (Fixed-Gap), sofern die Homogenitätsannahme gilt.
   • Sichere Abstention: Bei schwacher Identifikation oder fehlender Zertifizierung verweigert der Algorithmus eine strukturelle Aussage, anstatt falsche Schlüsse zu ziehen.
4. Empirischer Benchmark: Ein umfassender Test über 11 Szenarien, der direkte Kontrolle, schwache IVs, Homogenitätsverletzungen und rechteckige Überidentifikation abdeckt.
5. Roadmap für reiche Kontexte: Herleitung eines orthogonalen Scores für semiparametrische IV-Inferenz in kontinuierlichen Kontexten, der die Bias-Struktur in Fehler des Compliance-Modells und des Outcome-Modells faktorisiert.

4. Ergebnisse und Experimente

Die empirischen Studien bestätigen die theoretischen Vorhersagen und verdeutlichen die Bedeutung der Zielwahl:

• Direkte Kontrolle vs. Mediation: In Szenarien, in denen Empfehlungen und Behandlungen identisch sind, fallen REC und TRT zusammen. Sobald jedoch private Informationen oder downstream-Discretion ins Spiel kommen, trennen sich die Ziele.
• Schwache Identifikation (Weak IV): Unsichere Baseline-Algorithmen (z. B. Standard-UCB oder 2SLS-Varianten) liefern bei schwacher Instrumentierung oft falsche, aber scheinbar präzise Ergebnisse (hohe Fehlerrate bei der Behandlung). BRACE verweigert hier die Ausgabe einer strukturellen Politik (Abstention) und liefert stattdessen breite, valide Intervalle.
• Homogenitätsverletzung: Wenn die Annahme der strukturellen Homogenität verletzt ist, ist eine punktuelle Identifikation von TRT unmöglich. BRACE erkennt dies und empfiehlt stattdessen, sich auf das REC-Ziel zu konzentrieren, das auch ohne Homogenität definiert und lernbar bleibt.
• Rechteckige Überidentifikation: Durch Hinzufügen zusätzlicher Instrumente (rechtereckige Matrix) kann die strukturelle Unsicherheit drastisch reduziert werden, was in manchen Fällen eine korrekte strukturelle Deployment ermöglicht, wo die quadratische Version abstinent bleibt.
• Trade-off: In Szenarien mit „Workflow-Redesign" kann die beste zukünftige Behandlungsregel (TRT) deutlich besser sein als die beste aktuelle Empfehlung (REC). Der Algorithmus kann beide Werte parallel schätzen, aber nur diejenige bereitstellen, die dem gewählten Ziel entspricht.

5. Bedeutung und Fazit

Das Paper leistet einen wesentlichen Beitrag zur Theorie adaptiver Experimente und Bandit-Probleme, indem es die Zielwahl als primäre Designentscheidung etabliert, die vor dem Algorithmus getroffen werden muss.

• Paradigmenwechsel: Es bricht mit der historischen Norm, in klinischen Studien und Experimenten automatisch die „Behandlung" als primäres Ziel zu betrachten. In mediatisierten Systemen ist die Empfehlung oft der eigentliche Eingriff.
• Sicherheit durch Zertifizierung: BRACE führt das Konzept der „Zertifizierung" in Bandit-Algorithmen ein. Anstatt bei unsicheren Daten riskante Entscheidungen zu treffen, erlaubt der Algorithmus eine bewusste Nicht-Entscheidung (Abstention), was für kritische Anwendungen (Medizin, Politik) essenziell ist.
• Praktische Relevanz: Die Ergebnisse zeigen, dass die Wahl zwischen REC und TRT keine technische Nuance ist, sondern eine Frage der Stakeholder-Interessen (aktuelle Patienten vs. zukünftige Patienten/Regulierungsbehörden) und der gewünschten Robustheit gegenüber Modellannahmen.

Zusammenfassend bietet BRACE einen Rahmen, der sowohl operative Effizienz als auch strukturelle wissenschaftliche Integrität sicherstellt, indem er Unsicherheit explizit modelliert und bei fehlender Evidenz für strukturelle Kausalität auf konservative, aber valide Aussagen zurückgreift.