Safely Optimal: Pure Exploration in Bandits with Unknown Linear Constraints

Motivation

• Known: 기존 연구는 known constraints 하에서의 safely optimal policy 식별(Carlsson et al., 2024), 단일 unknown constraint 하에서의 best-arm identification(Lardy et al., 2025), 그리고 선형 프로그램의 feasibility testing(Gangrade et al., 2024b) 등을 개별적으로 다루어 왔다.
• Gap: 그러나 다수의 unknown linear constraints 하에서 policy(단일 arm이 아닌 arm들의 mixture) 수준의 safely optimal 식별에 대한 하한과 asymptotically optimal 알고리즘은 알려져 있지 않았으며, Lardy et al.(2025)은 d>1 제약 처리가 지수적 복잡도를 요구할 것이라 추측했고, Das & Basu(2026)의 Lagrangian relaxation 접근은 조건수(condition number)로 인해 샘플 복잡도가 부풀려지는 한계가 있었다.
• Why: 적응형 임상시험, 추천시스템 사용자 연구, 에너지 배분, 포트폴리오 구성 등 실세계 순차적 의사결정 문제에서는 제약(안전성·자원)이 사전에 정확히 알려지지 않은 채 보상과 비용이 상관되어 관측되는 경우가 많아, 이런 상황에서 통계적으로 정확하고 계산적으로 효율적인 안전-최적 정책 식별 알고리즘을 마련하는 것이 실용적으로 중요하다.
• Approach: 저자들은 먼저 정확한 safely optimal policy(SOP) 식별이 tight constraint가 있을 때 통계적으로 불가능함을 보이고, 이를 ε-optimal 식별로 완화한 뒤 unstructured/linear bandit 각각에 대해 정보이론적 하한을 유도하고, 이 하한을 순차적으로 추정된 reward-cost 평균으로 근사·최적화하여 샘플링 전략을 결정하고 두 가지 새로운 정지 규칙(stopping rule)으로 정책을 출력하는 PRUNE 프레임워크를 설계한다.

Achievement

1. 통계적 불안정성 증명(Lemma 1): 최적 정책 p⋆(ν)가 하나 이상의 tight constraint를 가질 때, 임의의 δ-correct 알고리즘에 대해 기대 정지 시간 Eν[τδ]가 무한대로 발산함을 보여 정확한 식별이 통계적으로 불가능함을 증명한다.
2. 새로운 정보이론적 하한 유도: unstructured bandit(Theorem 1)과 linear bandit(Theorem 2) 각각에 대해 d개의 unknown linear constraints 하에서 ε-optimal 안전 정책 식별의 기대 정지 시간에 대한 tight lower bound를 유도하고, feasibility pressure와 optimality pressure 간의 trade-off를 규명하며, 기존 여러 특수 사례(Carlsson et al. 2024, Lardy et al. 2025, Soare 2015)의 하한을 특수해로 회복한다.
3. PRUNE 알고리즘 설계(Algorithm 1): Frank-Wolfe 기반 allocation player, 두 개의 새로운 Chernoff stopping rule, 그리고 추천 규칙(recommendation rule)을 결합한 알고리즘 프레임워크를 제안하고, 이를 e-value 및 sequential testing 문헌과 연결한다.
4. 점근적 최적성 및 계산 효율성 증명(Theorem 3): PRUNE이 unstructured와 linear bandit 두 설정 모두에서 asymptotically optimal함을 증명하고, non-asymptotic 샘플 복잡도 및 라운드당 다항식 시간 계산 복잡도(O(K max{K,d}), O(d_lin² max{K,d_lin,d}))를 도출하여 Lardy et al.(2025)의 지수적 복잡도 추측을 반박한다.

How

• 정확 식별의 불안정성: 제약이 tight한 경우 변화 측정(change-of-measure) 논증을 통해 정지 시간의 발산을 보임(Lemma 1).
• 하한 유도: transportation/change-of-measure 기법을 확장하여 unstructured bandit(Theorem 1)과 linear bandit(Theorem 2)에 대한 정보이론적 하한을 각각 유도하고, jointly multivariate Gaussian 및 단일 제약 linear bandit에 대한 closed-form 표현(Corollary 1, 2)을 제시.
• 알고리즘 구성: Frank-Wolfe allocation player(Wang et al., 2021a)를 사용해 경험적 reward-cost 통계량을 하한식에 대입하고 sampling simplex 상에서 최적화하며, minimum operator로 인한 이중 비매끄러움(double non-smoothness)을 다루기 위한 sub-differential set(Equation 8)을 구성하고 gradient·curvature의 유계성을 증명.
• 정지 규칙: mixture-martingale 기법(Kaufmann & Koolen, 2021)에 기반한 두 가지 Chernoff stopping rule(Lemma 2)을 multivariate Gaussian 및 linear bandit 설정에 맞게 설계하고, 모든 t에 대해 유효한 threshold를 도출.
• 추천 규칙: 정지 시점의 추정된 (SOP) 또는 (SOP-lin)을 풀어 정책을 추천.
• 점근적 최적성 증명: 위 요소들을 결합하여 PRUNE의 기대 정지 시간이 유도된 하한에 점근적으로 수렴함을 증명(Theorem 3)하고, 비점근적 샘플 복잡도 및 연산 복잡도를 부록에서 도출.

Originality

• 단일 arm 식별이 아닌 policy(mixture over arms) 수준에서, 다수의(d개) unknown linear constraint를 동시에 다루는 최초의 하한 및 asymptotically optimal 알고리즘 제시.
• 보상과 비용 신호 간의 상관관계(joint covariance)를 명시적으로 반영한 하한 유도로 feasibility pressure와 optimality pressure의 이원적 trade-off를 규명.
• Lardy et al.(2025)이 제기한 "d>1 제약 처리는 지수적 복잡도가 필요하다"는 추측을 다항식 시간 알고리즘으로 반박.
• Frank-Wolfe 기반 allocation과 minimum operator의 이중 비매끄러움을 처리하는 sub-differential set 구성이라는 새로운 최적화 기법 도입.
• GLR 기반 stopping rule을 정규화하여 e-value로 해석함으로써 sequential testing 문헌과의 연결고리를 제공.

Limitation & Further Study

• 본 논문은 워크숍 발췌본으로, 실제 실험적 검증(empirical evaluation)에 대한 상세 결과가 abstract/본문 발췌에 명시되어 있지 않아, 이론적 결과의 실용적 성능(유한 샘플 환경에서의 실제 sample complexity)에 대한 검증이 부족해 보인다.
• Assumption 1(bounded domains, ∥Bj∥2≤1)과 같은 정규화 가정이 실제 응용(임상시험, 에너지 배분 등)에서 얼마나 현실적인지에 대한 논의가 제한적이다.
• Frank-Wolfe allocation player의 수렴 속도 및 계산 복잡도가 이론적으로는 다항식이지만, 큰 K, d, d_lin에서 실제 스케일링 성능에 대한 추가 검증이 필요하다.
• 후속 연구로 비선형 제약이나 non-Gaussian noise, 그리고 constraint matrix B와 reward parameter θ 간의 더 복잡한 의존성을 다루는 확장이 가능할 것으로 보인다.

Evaluation

총평: unknown linear constraints 하에서 policy 수준의 safely optimal identification 문제에 대해 하한과 asymptotically optimal 알고리즘을 최초로 제시한 이론적으로 탄탄하고 중요한 기여이나, 실험적 검증과 실용성에 대한 추가 논의가 보완되면 더욱 완성도가 높아질 것이다.