Information Routing across Batch Boundaries: Memory--Batch Tradeoffs in Lipschitz Bandits

기술 요약: 리프시츠 밴딧(Lipschitz Bandits)에서의 배치 경계 간 정보 라우팅

문제 정의
본 논문은 확률적 리프시츠 밴딧(stochastic Lipschitz bandits)에서 상태 너비(상태 메모리, state width)와 업데이트 깊이(배치 적응성, update depth) 사이의 근본적인 트레이드오프를 조사한다. 설정은 학습자가 미지의 평균 보상 함수 $f: [0, 1]^d \to [0, 1]$(sup-norm에 대해 1-리프시츠)와 상호작용하는 상황이다. 학습자는 다음 두 가지 제약 조건을 동시에 적용받는다:

1. 메모리 ($W$): 매 풀(pull) 이후, 학습자는 보상에 의존하는 가변적 상태로서 최대 $W$ 비트의 정보만을 보유할 수 있다.
2. 배치 ($B$): 학습자의 행동은 최대 $B$ 개의 확정된 배치(committed batches)로 나뉜다. 배치 경계에서, 현재의 상태는 다음 경계와 해당 배치의 전체 행동 시퀀스를 확정(commit)한다. 보상은 배치 내에서 관찰되어 상태를 온라인으로 업데이트하지만, 이미 확정된 행동 테이프(action tape)를 변경할 수는 없다.

본 연구의 목적은 호라이즌 $T$, 차원 $d$, 메모리 예산 $W$, 그리고 배치 예산 $B$의 함수로서 미니맥스 기대 의사 후회(minimax expected pseudo-regert), $R_T(B, W)$를 규명하는 것이다.

방법론 및 기술적 접근
저자들은 두 가지 서로 다른 자원 병목 현상을 동시에 드러내는 "어려운 패밀리(hard family)"의 문제 인스턴스를 구축함으로써 미니맥스 프런티어를 설정한다:

1. 검증 예산(Verification Budget): 호라이즌 내에서 사용 가능한 총 샘플 수는 얼마나 많은 국소적 개선(local improvements)을 검증할 수 있는지를 제한한다.
2. 라우팅 예산(Routing Budget): 경계 상태(각 배치의 끝에 있는 상태)는 미래의 실험을 어디로 보낼지에 대한 지역적 결정(regional decisions)을 얼마나 많이 보존하고 전달할 수 있는지를 제한한다.

하한(Lower Bound) 구축:
하한은 스케일 $s$에서 분리된 $m \asxp s^{-d}$개의 영역 쌍을 포함하는 기하학적 구성을 기반으로 한다. 각 영역 내부에는 더 미세한 스케일 $r$에서의 $q \asxp (s/r)^d$개의 프로브(probe)가 존재한다. 잠재적인 라우팅 벡터 $V \in \{0, 1\}^m$는 각 쌍의 "좋은" 쪽을 선택한다.

• 정보 라우팅 제약: 낮은 후회를 달성하기 위해 학습자는 각 쌍의 올바른 쪽을 식별해야 한다. 이를 위해서는 확정된 행동 트랜스크립트(action transcript)가 $V$에 관한 $\Theta(s^{-d})$ 비트의 정보를 인코딩해야 한다.
• 엔트로피 병목: $B$ 개 배치에 걸친 경계 상태의 총 엔트로피는 $(B-1)W$로 제한된다. 저자들은 중단된 변화량 측정(stopped change-of-measure) 논법과 파노 부등식(Fano's inequality)을 사용하여, 만약 경계 상태 엔트로피 예산이 라우팅 결정을 인코딩하기에 불충분하다면, 학습자가 선택되지 않은 영역으로 검증 노력을 잘못 라우팅하게 되어 높은 후회를 입게 됨을 보여준다.
• 업데이트 깊이 장애: (Feng et al., 2024에서 채택된) 별도의 적응형 그리드(adaptive-grid) 구성은 $W$와 무관하게 $B$에만 의존하는 하한을 제공하며, 무한한 메모리가 있더라도 제한된 배치가 정밀화 속도를 어떻게 제한하는지 보여준다.

상한(Upper Bound) 구축:
이에 대응하는 상한은 안전한 활성 집합 마스크(safe active-set mask, 잠재적 극댓값을 포함하는 영역을 나타내는 이진 벡터)를 유지하면서, 스트리밍 방식으로 미세한 검증 통계량을 생성 및 삭제하는 정책을 사용한다.

• 정적 경계: 정책은 정적 배치 경계를 사용한다.
• 직렬화 vs 계층 구조:
  • 활성 집합 마스크가 메모리에 들어가는 경우($W$가 큰 경우), 학습자는 모든 좌표를 동시에 업데이트하기 위해 인메모리 계층적 정밀화(in-memory hierarchical refinement)를 사용한다.
  • 마스크가 메모리를 초과하는 경우, 학습자는 직렬화된 구성(serialized construction)을 사용한다. 학습자는 마스크의 메모리 크기 조각들을 재생성하고, 이를 사용하여 대응하는 자식 프로브들을 확정하며, 전역 최적 자식(global best-child) 기록을 업데이트한 뒤 해당 조각을 삭제한다. 이를 통해 학습자는 $W$ 비트 제한을 초과하지 않으면서 조각 단위로 활성 집합을 처리할 수 있다.
• 핵심 메커니즘: 검증 통계량은 온라인으로 누적되고, 상주하는 최적 팔(best-arm) 기록과 비교된 후 즉시 삭제된다. 오직 활성 집합 마스크(또는 그 조각들)와 로그 제어 기록만이 경계를 넘어 지속된다.

주요 결과
본 논문은 로그 인자를 제외한 미니맥스 후회를 규명한다. 후회는 다음 세 가지 장벽 중 최악의 값에 의해 결정된다:

1. 순차적 추정(Sequential Estimation): $T^{(d+1)/(d+2)}$ (표준 리프시츠 밴딧 비율).
2. 배치 깊이(Batch Depth): 적응형 그리드 제한에서 유도된 $B$에 의존하는 항.
3. 너비-깊이 상호작용(Width–Depth Interaction): 새로운 항으로, 다음과 같은 결합 제약을 포착한다:
   $$T^{\frac{d+2}{d+3}} \left(1 + (B-1)W\right)^{-\frac{1}{d(d+3)}}$$

공식 프런티어 (정리 3.4):
$W \gtrsim_d \log(eT)$일 때, 미니맥스 후율은 다음과 같다:
$$R_T(B, W) \asymp \max \left( T^{\frac{d+1}{d+2}}, \frac{T^{\beta_{d,B}}}{B^2}, T^{\frac{d+2}{d+3}} (1 + (B-1)W)^{-\frac{1}{d(d+3)}} \right)$$
여기서 $\beta_{d,B} = \frac{d+1}{d+2} \frac{1}{1 - (d+2)^{-B}}$ 이다.

특수 사례 및 시사점:

• 제한 없는 메모리 ($W \to \infty$): 결과는 Feng et al. (2024)에서 확립된 전체 차원의 최악 사례 배치 전용 프런티어를 회복한다.
• 완전 순차적 ($B=T$): 결과는 로그 메모리($W \asxp \log T$)를 갖는 순차적 미니맥스 후회를 회복한다(Zhu and Huang, 2025와 일치).
• 비상호교환성(Non-Interchangeability): 곱 $(B-1)W$가 지수에 등장하며, 이는 상태 너비와 업데이트 깊이가 대체재가 아닌 보완재임을 증명한다. 단일한 넓은 상태가 일반적으로 탐색의 각 라운드 사이에 재계산되는 일련의 좁은 상태들을 대체할 수 없다.
• 배치 복잡도: 순차적 후회에 근접하기 위해서는 (충분한 $W$가 있을 때) 배치 수 $B$가 $\log \log T$로 스케일링되어야 하며, 경계 상태 엔트로피 $(B-1)W$는 $T^{d/(d+2)}$로 스케일링되어야 한다.

의의 및 주장
본 논문은 메모리와 적응성이 어떻게 공동으로 비매개변수 최적화(nonparametric optimization)의 성능을 결정하는지에 대한 구조적 질문을 해결한다고 주장한다.

• 정보 라우팅: 저자들은 "정보 라우팅"이라는 개념을 도입하며, 여기서 보상에 의존하는 결정이 배치 경계를 가로질러 인과적으로 운송되는 과정이 핵심적인 제한 요소가 된다. 경계 상태는 이러한 결정들의 엔트로피를 위한 병목 역할을 한다.
• 최적성: 로그 인자를 제외하고 일치하는 상한 및 하한은 정적 배치 경계가 최악의 차수를 달성하기에 충분함을 보여준다. 즉, 예측 가능한 적응형 경계가 최악의 경우의 차수를 개선하지는 못한다.
• 통합적 관점: 이 프레임워크는 배치 전용 모델과 유한 메모리 순차 모델을 통합하여, "프런티어"가 검증을 위한 샘플, 지역 라우팅을 위한 상태, 적응형 정밀화를 위한 깊이라는 세 가지 원시 자원에 의해 제어되는 단일 곡면임을 보여준다.

저자들은 로그 손실을 제거하는 것, 서브 로그(sub-logarithmic) 메모리 영역을 규명하는 것, 그리고 사례 의존적(instance-dependent) 유사물을 얻는 것이 여전히 미해결 과제로 남아 있다고 언급한다.