Open-Ended Task Discovery via Bayesian Optimization

Motivation

• Known: 기존 BO는 drug discovery, materials science 등에서 주어진 고정된 task(objective function과 domain)를 최적화하는 sample-efficient black-box optimizer로 널리 활용되어 왔으며, 최근 LLM 기반 automatic task generation(evolutionary LLM, Stanley & Lehman 등) 연구도 진행되고 있다.
• Gap: 기존 BO 및 LLM 기반 optimizer는 "무엇을 최적화할지"라는 task 자체의 불확실성을 사전에 고정된 것으로 취급하며, task가 evidence 축적에 따라 진화할 수 있다는 점과 유한한 실험 예산(budget) 내에서 achievability를 판단하며 task를 발견·검증하는 문제를 다루지 않았다.
• Why: 신물질이나 알고리즘이 발견되어도 최적의 응용 분야(task)를 찾는 것 자체가 어려운 경우가 많으며(예: 연간 약 12,000개 발견되는 결정 중 극소수만 산업적으로 활용), 유한 예산 하에서 유망하면서도 달성 가능한 task를 자동으로 탐색·검증하는 능력은 신물질 개발, 화학 합성, 특허 재활용 등 실제 과학 워크플로우에 직접적 영향을 미친다.
• Approach: GSR은 task 생성과 task 최적화를 두 개의 loop(task-refinement loop와 within-task BO loop)로 구성하여 번갈아 수행하며, task-UCB 기반 selection과 coarse-to-fine mutation 기반 refinement를 결합한 open-ended BO 프레임워크를 제안한다.

Achievement

Figure 5. Real-world experiments. Top row: planning tasks—(a) new product development and (b) synthesis scaling. Bottom

1. 이론적 regret bound 제시: GSR이 asymptotically 최적 task에 평가를 집중시키며, single-task BO 대비 logarithmic regret overhead만 발생함을 증명(Theorem 및 Lemma 기반).
2. Task-UCB 기반 selection과 coarse-to-fine refinement 알고리즘 설계: utility UCB와 optimization gap을 결합한 confidence interval을 통해 promising하면서도 achievable한 task를 선별하고 unpromising task를 early-stop.
3. 다양한 실제 도메인 적용: new product development, chemical synthesis scaling, algorithm analysis, patent repurposing 등 4개 실제 응용에 적용하여 기존 LLM 기반 optimizer 대비 우수한 성능을 입증.

How

Figure 2. Alg. 1: (a) Select chooses the next task it and anchor

• Task를 domain X(i)와 objective f(i)로 정의하고, GP-UCB를 이용해 각 task 내에서 noisy oracle 관측을 통해 최적화 gap ϵf_s를 계산.
• Scale-invariant utility function u(i)를 도입해 서로 다른 task 간 비교가 가능하도록 long-run value U(i)를 정의하고, 유한 budget T 하에서 achievable한 ϵU-optimal task 개념(Definition 2.2, Condition 2.3)을 정식화.
• Task selection: utility UCB(U̅(i)_s)와 optimization gap(Lϵf_s)을 결합한 confidence interval을 통해 task-UCB policy로 다음 task it을 선택(Line 4, Alg.1).
• Task refinement: 가장 유망하면서도(promising) 불확실성이 threshold 이하인 anchor task를 선정(Eq.4)하고, 이를 LLM으로 mutate하여 coarse-to-fine 방식으로 새로운 task batch를 생성(Gen 함수, Line 8-10, Alg.1).
• LLM 기반 evolutionary task generation 패러다임(Novikov et al., Lange et al.)을 채택하여 구체적으로 구현.

Originality

• Task 자체의 불확실성(무엇을 최적화할지)을 BO의 일급 대상으로 명시적으로 formalize한 최초의 open-ended BO 프레임워크.
• Task generation(LLM 기반)과 task optimization(GP-UCB)을 규제된 regret bound 하에서 통합한 two-loop(task-refinement loop, within-task BO loop) 구조 제안.
• Utility UCB와 optimization gap을 결합한 confidence interval을 이용해 coarse-to-fine anchor 선택 및 refinement scheduling을 이론적으로 정당화한 점이 기존 evolutionary LLM 접근과 차별됨.

Limitation & Further Study

• Utility function u(i)이 rankable하고 monotone·Lipschitz하다는 가정(Definition 2.1)에 의존하므로, task 간 비교가 불가능하거나 utility 정의 자체가 모호한 경우 적용이 제한될 수 있음.
• Regret bound는 GP-UCB의 no-regret 성질 및 Condition 2.3(BO-comparable target resolution)과 같은 이론적 가정에 의존하므로, 실제 LLM 기반 task generation의 품질(coverage, diversity)에 따라 실질적 성능이 크게 좌우될 가능성이 있음.
• 발췌된 본문에서는 4개 실제 응용 도메인에 대한 정량적 비교 결과(baseline 대비 개선 폭, 통계적 유의성)가 충분히 제시되지 않아 실증적 강건성 평가가 제한적임.
• 후속 연구로 utility function 자동 발견, 더 일반적인 task space(비-rankable, multi-objective) 확장, 대규모 실험 budget에서의 scalability 검증이 필요.

Evaluation

총평: Task 자체의 불확실성을 다루는 open-ended BO라는 새로운 문제를 정식화하고 이론적 regret 보장을 갖춘 GSR 프레임워크를 제안한 참신하고 의미 있는 연구이나, 발췌된 본문만으로는 실증 결과의 구체적 강건성과 LLM 의존성에 대한 충분한 검증이 아쉽다.