Neuer Algorithmus identifiziert effizient beste, zulässige Optionen

In der Welt der experimentellen Entscheidungsfindung strebt die Best‑Arm‑Identification (BAI) danach, den leistungsstärksten „Arm“ – also die beste Option – aus einer Menge von K Alternativen zu bestimmen. Doch in vielen praktischen Szenarien muss diese Wahl zusätzlich bestimmte Zulässigkeitskriterien erfüllen. Ein klassisches Beispiel ist die Wirkstoffentwicklung, bei der ein Medikament nicht nur wirksam, sondern auch innerhalb sicherer Toxizitäts‑ und Löslichkeitsgrenzen liegen muss.

Frühere Arbeiten zur BAI mit Zulässigkeitsbedingungen gingen davon aus, dass bei jedem Zug eines Arms gleichzeitig sowohl die Leistung als auch die Einhaltung aller Constraints beobachtet werden kann. Diese Annahme trifft selten zu: In der Wirkstoffforschung werden beispielsweise Toxizitätstests und Wirksamkeitstests oft getrennt voneinander durchgeführt. Daher ist ein neuer Ansatz erforderlich, der nicht nur entscheidet, welchen Arm man zieht, sondern auch, ob man die Leistung oder eine bestimmte Zulässigkeitsbedingung testen will.

Die vorgestellte Studie führt das Konzept der „feasibility‑BAI“ ein, bei dem der Entscheider ein Tupel (i, ℓ) wählen kann – i bezeichnet den Arm und ℓ bestimmt, ob die Leistung (ℓ = 0) oder eine der N Zulässigkeitsbedingungen (ℓ ∈ [N]) getestet wird. Im Fixed‑Confidence‑Setting soll mit einer Wahrscheinlichkeit von mindestens 1 − δ der zulässige Arm mit der höchsten Leistung identifiziert werden.

Der neue Algorithmus liefert eine effiziente Lösung, deren Stichprobenkomplexität theoretisch begrenzt ist. Er passt sich dynamisch an die Schwierigkeit des Problems an und eliminiert Arms entweder wegen schlechter Leistung oder wegen Nicht‑Zulässigkeit – je nachdem, welcher Weg schneller zum Ziel führt. Ergänzend dazu wird ein theoretischer Lower‑Bound präsentiert, der die Leistungsfähigkeit des Ansatzes bestätigt.