Neue Grenzwerte für Sample-Komplexität bei Best-Arm-Identifikation trotz Bias

Mit zunehmender Suchtiefe wächst der Kandidatenaktionsraum exponentiell, was die Rechenressourcen stark beansprucht. Heuristische Pruningschemen, die häufig eingesetzt werden, bieten jedoch keine formalen Sicherheitsgarantien, wenn die zugrunde liegenden Surrogatmodelle – etwa große Sprachmodelle – systematische Bewertungsbias aufweisen.

In dem vorliegenden Beitrag wird der Prozess der Knotenerweiterung als lokales Best-Arm-Identifikationsproblem (BAI) über dynamische Frontiers betrachtet, wobei ein begrenzter systematischer Bias L berücksichtigt wird. Durch die Umkehrung der Lambert‑W‑Funktion wird eine additive Sample‑Komplexität von O((Δ – 4L)–2) nachgewiesen. Das bedeutet, dass ein sicherer Knotenausschluss nur möglich ist, wenn die beobachtete Belohnungslücke Δ größer als 4L ist.

Zusätzlich liefert die Arbeit einen informations­theoretischen unteren Grenzwert von Ω((Δ – 2L)–2), der die strukturellen Grenzen eines bias‑geprägten Suchprozesses bestätigt. In Experimenten mit synthetischen Bäumen und komplexen Denkaufgaben zeigt sich, dass die Einhaltung dieser lokalen Sicherheitsgrenze optimale Pfade bewahrt und gleichzeitig die Zuweisung von Stichproben effizient maximiert.