arXiv:2007.01980

Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design

Yufei Ruan, Jiaqi Yang, Yuan Zhou

제출 2020-07-04

원문 초록

Motivated by practical needs such as large-scale learning, we study the impact of adaptivity constraints to linear contextual bandits, a central problem in online active learning. We consider two popular limited adaptivity models in literature: batch learning and rare policy switches. We show that, when the context vectors are adversarially chosen in $d$-dimensional linear contextual bandits, the learner needs $O(d \log d \log T)$ policy switches to achieve the minimax-optimal regret, and this is optimal up to $\mathrm{poly}(\log d, \log \log T)$ factors; for stochastic context vectors, even in the more restricted batch learning model, only $O(\log \log T)$ batches are needed to achieve the optimal regret. Together with the known results in literature, our results present a complete picture about the adaptivity constraints in linear contextual bandits. Along the way, we propose the distributional optimal design, a natural extension of the optimal experiment design, and provide a both statistically and computationally efficient learning algorithm for the problem, which may be of independent interest.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.00906v1cs.AI공통 태그 Active Learning, Multi-Armed Bandits

ActiveSaddler: 에이전트 하네스 최적화를 위한 자동 커리큘럼 학습

ActiveSaddler: Automated Curriculum Learning for Agent Harness Optimization

자동화된 하네스 최적화(harness optimization)는 실행 피드백을 바탕으로 프롬프트, 도구 인터페이스, 제어 로직을 반복적으로 업데이트함으로써 대규모 언어 모델(LLM) 에이전트를 크게 향상시킬 수 있습니다. 그러나 기존 방법들은 하네스가 업데이트되는 방식을 최적화하는 데 주로 집중하며, 이러한 업데이트를 이끄는 피드백을 생성하는 학습 시나리오를 대체로 고정해 둡니다. 하네스가 진화함에 따라 추가 최적화에 가장 유용한 시나리오도 변할 수 있으며, 이는 학습 커리큘럼 자체가 하네스와 함께 적응해야 함을 시사합니다. 본 논문에서는 하네스 최적화에서 결여되었던 이러한 차원을 자동 커리큘럼 학습(automated curriculum learning) 문제로 정식화하고 ActiveSaddler를 소개합니다. ActiveSaddler는 진화하는 커리큘럼을 동적으로 인스턴스화되는 최적화 대상을 갖춘 비정상 밴딧(non-stationary bandit)으로 모델링합니다. 이 방법은 반복되는 실패를 재사용 가능한 실패 패턴 암(arm)으로 추상화하고, 각 패턴을 추가로 목표 삼았을 때 얻을 수 있는 잠재적 학습 진행도를 추정하며, 알려진 약점을 다시 탐색하는 것과 새로운 약점을 찾기 위해 미확인 시나리오를 탐색하는 것 사이의 균형을 적응적으로 맞춥니다. 최적화 결과는 발견된 실패 패턴 집합과 그 우선순위를 지속적으로 업데이트하여 커리큘럼이 하네스와 함께 공동 진화할 수 있도록 합니다. GAIA2 및 Terminal-Bench 2.0에 대한 실험 결과, ActiveSaddler는 지속적으로 더 강력한 하네스를 발견하여 최적화 전에 고정된 시나리오 순서를 사용하는 동일한 하네스 옵티마이저 대비 테스트 Pass@1을 각각 4.4%p 및 7.5%p 향상시키는 것으로 나타났습니다. 추가 절제 연구(ablation study)는 이러한 향상이 최적화 대상을 동적으로 구성하고, 진화하는 유용성을 추정하며, 지속적인 최적화와 새로운 실패 발견 간의 균형을 맞추는 데 기인함을 보여줍니다. 종합적으로 이러한 결과는 자동 커리큘럼 학습이 하네스 최적화를 위한 핵심적인 새로운 최적화 차원임을 입증합니다.

arXiv:2607.23696v1cs.AI공통 태그 Active Learning, Multi-Armed Bandits

생성 모델과 적응형 테스트를 활용한 오프라인-투-온라인 크리에이티브 최적화

Offline-to-Online Creative Optimization with Generative Models and Adaptive Testing

광고 크리에이티브 최적화는 생성보다 평가에 의해 점점 더 제약을 받고 있다. 생성 모델은 많은 그럴듯한 크리에이티브를 만들 수 있지만, 신뢰할 수 있는 평가를 위해서는 온라인 실험이 필요하며, 그 실험에서는 제한된 후보 목록만 테스트할 수 있다. 우리는 과거 A/B 테스트 데이터를 사용하여 해당 후보 목록의 후보를 생성하고 선정하는 방법을 연구한다. 우리는 추론(inference) 시점의 critic으로 예측 모델을 사용해 크리에이티브 생성을 안내하는 성과 중심의 오프라인-투-온라인 워크플로를 개발하고 배포했다. 오프라인 단계에서는 과거 실험으로 학습(training)된 예측 모델을 사용해 생성 모델이 만든 변형들을 순위화하고 개선한다. 그다음 최종 테스트 후보 목록을 온라인 적응형 실험에 배포한다. 50-arm 현장 실험에서, 이 방법으로 생성된 최고의 크리에이티브가 최고의 인간 작성 크리에이티브보다 45.1% 더 높은 참여(engagement)를 보였다. 두 추가 실험에서도 동일한 상위 꼬리(upper-tail) 패턴이 나타났으며, 향상(lift)은 각각 46.7%와 36.2%였다. 예측 모델이 오프라인에서 최고의 크리에이티브를 직접 식별하기에는 너무 노이즈가 많음에도 불구하고, 생성 모델이 적응형 실험에서 효율적으로 평가할 수 있는 강력한 후보를 만들도록 효과적으로 안내한다는 것을 발견했다. 결과는 생성 모델을 활용한 크리에이티브 최적화를 위한 설계 원칙을 시사한다: 테스트할 후보 목록 생성을 예측 모델로 안내하고, 실행 가능한 테스트 규모에서 고성능 후보를 포함하는지 여부로 후보 목록을 판단하며, 약한 arm에 소실되는 트래픽을 제한하면서 적응형 실험으로 후보 간 선택을 수행한다.

arXiv:2607.11720v1cs.LG공통 태그 Active Learning, Multi-Armed Bandits

능동적 오프라인-온라인 강화학습

Active Offline-to-Online Reinforcement Learning

배경: 오프라인 강화학습(RL)은 대규모의 사전 수집된 데이터셋으로부터 효과적인 정책을 학습하고, 이후 제한된 온라인 상호작용을 통해 성능을 개선할 수 있게 한다. 이러한 오프라인-온라인 강화학습(O2O-RL) 패러다임은 상호작용 비용이 높거나 잠재적으로 위험한 비정상(nonstationary) 도메인에서 특히 유망하다. 표준 O2O-RL 파이프라인은 여러 후보 정책을 오프라인으로 학습하고, 오프-정책(off-policy) 또는 온라인 평가를 통해 이를 평가한 뒤, 추정 가치가 가장 높은 정책을 배포하여 미세조정(fine-tuning)한다. 그러나 오프라인 사전학습과 마찬가지로, 미세조정 성능은 알고리즘과 하이퍼파라미터 선택에 매우 민감하여 단일 정책으로 확정하는 것은 위험을 수반한다. 목적: 본 연구는 O2O-RL 환경에서 제한된 상호작용 예산 내에 미세조정을 위한 능동적 정책 선택 문제를 다룬다. 이는 해당 문제를 다룬 최초의 연구이다. 방법: 온라인 상호작용을 정책 평가에 할당하는 것(고성능 정책 식별에 기여)과 미세조정에 할당하는 것(정책 성능 향상에 기여) 사이의 근본적인 트레이드오프를 규명하여 문제를 정식화한다. 이후 온라인 평가를 통해 획득한 관측값에 피팅된 국소 선형 성능 예측(locally linear performance forecasts)으로부터 도출된 미래 성능의 상한 신뢰 구간(upper-confidence bounds)에 기반하여 미세조정할 정책을 능동적으로 선택함으로써 이 트레이드오프를 균형 있게 조정하는 방법을 제안한다. 결과: 다양한 실험에 걸쳐 제안된 방법은 기존 O2O-RL 베이스라인을 일관되게 능가한다. 결론: 정책을 능동적으로 선택하고 미세조정하는 방식은 단일 정책으로 확정하거나 예산을 모든 정책에 균등하게 배분하는 방식보다 제한된 온라인 상호작용 예산을 더 효과적으로 활용한다. 또한 본 프레임워크는 온라인 상호작용이 비용이 높거나 위험한 실제 시스템에서의 실용적 배포를 향해 오프라인 강화학습을 진전시킨다.

arXiv:2607.08979v1cs.LG공통 태그 Active Learning, Multi-Armed Bandits

쌍별 비교로부터의 최적 상위-$k$ 식별

Optimal Top-$k$ Identification from Pairwise Comparisons

우리는 잡음이 있는 쌍별 비교로부터의 고정 신뢰도 기반 상위-$k$ 식별이라는 능동 학습 문제를 연구한다. 이 문제에서 알고리즘은 비교할 아이템 쌍을 순차적으로 선택하고 결과를 관찰하며, 오류 확률이 최대 $δ$인 상태에서 상위-$k$ 아이템 집합을 반환할 수 있을 때 멈춘다. 목표는 기대 비교 횟수(샘플 복잡도)를 최소화하는 $δ$-정확 절차를 설계하는 것이다. 이 문제는 밴딧 모델에서의 고정 신뢰도 순수 탐험(pure exploration)에 관한 광범위한 문헌에 속하며, 공통적인 목표는 점근적 최적성이다: $δ\to 0$일 때 알고리즘의 기대 샘플 복잡도가 정보이론적 하한과 일치한다. 점근적으로 최적인 절차가 다양한 고정 신뢰도 순수 탐험 문제에 대해 개발되어 왔으나, 우리가 아는 한 잠재 효용 모델 하에서 쌍별 비교를 통한 상위-$1$ 또는 더 일반적으로 상위-$k$ 식별에 대한 점근적 최적 알고리즘은 아직 확립되지 않았다. 이 설정에서 우리는 그러한 알고리즘을 개발한다. 우리는 하한의 구조를 분석하고 이를 안장점(saddle-point) 문제로 정식화한다. 이 구조를 통해 온라인으로 점근적 최적 비교 할당을 학습하는 계산 효율적인 프라이멀-듀얼 절차가 가능해진다. 이후 프라이멀-듀얼 절차가 학습한 할당을 추적하는 적응적 비교 할당 알고리즘을 구성하고, 이 알고리즘이 점근적으로 최적임을 증명한다.

arXiv:2603.05361v2cs.AI공통 태그 Active Learning, Multi-Armed Bandits

PACE: 9-1-1 신고 접수원 교육을 위한 개인화 적응형 커리큘럼 엔진

PACE: A Personalized Adaptive Curriculum Engine for 9-1-1 Call-taker Training

9-1-1 신고 접수 교육은 다양한 사건 유형과 프로토콜별 세부 사항을 아우르는 천 가지 이상의 상호의존적 기술의 숙달을 요구합니다. 전국적인 인력 부족은 이미 교육 역량에 부담을 주고 있지만, 효과적인 교수를 위해서는 여전히 교관이 각 교육생의 변화하는 역량에 맞춰 목표를 조정해야 합니다. 이러한 개인화 부담은 현재의 방식으로는 확장이 불가능합니다. 메트로 내슈빌 비상 통신국(MNDEC)과의 협력을 통해, 우리는 PACE(Personalized Adaptive Curriculum Engine)를 제안합니다. PACE는 (1) 교육생의 기술 상태에 대한 확률적 신념 유지, (2) 개인별 학습 및 망각 역학 모델링, (3) 새로운 역량 습득과 기존 역량 유지의 균형을 맞추는 훈련 시나리오 추천을 통해 교관의 의사결정을 보조하는 코파일럿 시스템입니다. PACE는 구조화된 기술 그래프에 걸쳐 증거를 전파하여 진단 커버리지를 가속화하고, 컨텍스트 밴딧(contextual bandits)을 적용하여 교육생이 해결할 준비가 된 격차를 목표로 하는 시나리오를 선택합니다. 실험 결과, PACE는 최신 프레임워크 대비 역량 달성 시간을 19.50% 단축하고 최종 숙달도를 10.95% 향상시키는 것으로 나타났습니다. 현직 교육 담당관과의 코파일럿 연구에서는 실제 사례에 대한 PACE와 전문가의 교육학적 판단 간 95.45%의 일치율을 추가로 입증했습니다. 추정 측면에서 PACE는 처리 소요 시간을 11.58분에서 단 34초로 단축하여 최대 95.08%의 감소를 달성합니다.

arXiv:2606.29203v1cs.LG공통 태그 Active Learning, Multi-Armed Bandits

기권이 있는 베이지안 최적 팔 식별: 다항식-지수 위상 전이

Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition

본 연구에서는 학습자가 최종 추천을 기권할 수 있는 베이지안 고정 예산 최적 팔 식별(best-arm identification) 문제를 다룬다. 기권 예산 $α$를 제약으로 두고, 기권 없이 열등한 팔을 추천할 위험인 미탐지 오류 확률을 분석한다. 핵심 발견은 기권이 위상 전이를 유발한다는 점이다. 기권이 없을 경우 오류 확률은 샘플링 예산 $T$에 대해 다항식적으로 감소하지만, 임의의 작은 양의 기권 예산을 도입하면 지수적 감소로 전환된다. 가우시안 사전 분포(prior)와 보상에 대해, $T\to\infty$ 후 $α\downarrow0$인 체제에서 최적 오류 지수에 대한 정보이론적 하한과 알고리즘 상한을 정확하게 일치시켜 도출하며, 이 지수는 $\exp(-\frac{α^{2}T}{8κ_ν^{2}})$ 형태를 취한다. 난이도 매개변수 $κ_ν$는 상위 두 팔 간 격차가 0에서의 사전 밀도를 나타내며, 거의 동점인 인스턴스가 근본적인 오류를 유발함을 부각한다. 우리는 통계적으로 모호한 인스턴스에 기권 예산을 집중 투입하여 이 최적 지수를 달성하는 적응형 알고리즘 PGWS를 제안한다. 나아가 이 다항식-지수 개선이 베이지안 현상에 국한됨을 입증한다. 빈도주의(frequentist) 환경에서는 기권이 하위 차수의 지수 항에만 영향을 미친다. 또한 가우시안 모델을 넘어 결과를 확장한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.