Your bandit's exploration floor probably violates its own floor

Source: Dev.to

다중 armé 밴디트 / A-B 할당 시스템들은 최소 탐색 비중을 추가합니다: 각 팔은 적어도 예를 들어 5%의 트래픽을 받아야 하며, 변형이 완전히 소모되지 않게 하고 모든 arm에 데이터를 계속 수집할 수 있게 합니다. 이 보장은 간단해 보입니다 — p_i >= f for every arm — 그리고 구현도 간단해 보입니다: def clip_renorm(w, f): p = np.maximum(w, f) # raise anything below the floor up to it return p / p.sum() # renormalize so probabilities sum to 1

이것은 잘못되어 있으며 조용히 실패합니다. 재정규화 단계는 floored arms를 다시 floor 아래에 둡니다. 클리핑은 작은 가중치를 f까지 올리면서 총합이 1을 초과하게 합니다. 그 총합으로 나누면 이전에 f로 클리핑한 arm들도 다시 아래에 있게 되며, 광고한 floor와 실제 적용되는 floor가 달라집니다.

구체적인 예시 — 4개 팔, 확신을 가진 우승자, floor f = 0.10: w = [0.94, 0.02, 0.02, 0.02] floor = 0.10 clip-renorm -> [0.7581, 0.0806, 0.0806, 0.0806] min = 0.0806 ❌ (f exactly holds, total is nf + (1 - nf)*1 = 1 by construction — no renormalization needed, so nothing gets dragged back under the floor. It also preserves ordering and relative spacing of w (it’s affine), so you don’t distort the policy you learned. Same run: additive-simplex -> [0.664, 0.112, 0.112, 0.112] min = 0.112 ✅

같은 10만 개 벡터에 대해 floor가 위반된 비율은 0.00%였습니다.

이때 필요한 조건은 n * f = 1.0: return np.full(n, 1.0 / n) # floor가 불가능할 때 -> 균등 w = np.asarray(w, dtype=float) w = w / w.sum() return f + (1.0 - n * f) * w

이것이 전체 올바른 원시 함수입니다: 비음성 검사, 불가능한 floor fallback 로 균등, 그리고 아핀 믹스. 탐색 floor는 장식적인 것이 아닙니다.它是最악의 경우 후회를 제한하고 모든 arm에 데이터를 계속 수집하도록 보장합니다 — 많은 밴디트 후회 논증이 의존하는 특성이자, 공정성/SLA 요구사항이기도 합니다 (“어떤 변형도 X% 이하로 떨어지지 않음”). 7.7% 대신 10% 로 조용히 floor가 깨지면 이해관계자에게 보고한 보장이 무효화되고, 그 보호를 받는 모든 bound 도 적용되지 않습니다. 버그는 출력값이 여전히 1을 합하고 floor처럼 보이기 때문에 눈에 띄지 않지만, 가장 작은 숫자는 은밀히 너무 작습니다.

import numpy as np rng = np.random.default_rng(0) f, n, viol = 0.10, 4, 0 for _ in range(100_000): w = rng.dirichlet(np.ones(n) * 0.3) p = np.maximum(w, f); p = p / p.sum() # clip-renorm if p.min() < f - 1e-12: viol += 1 print(f”clip-renorm floor violations: {viol/100_000:.1%}”) # ~97%