절댓값 섭동을 통한 선형 밴딧의 무작위 탐험
Randomized Exploration for Linear Bandits via Absolute Perturbations
한국어 초록
확률적 선형 밴딧(stochastic linear bandits)에서 표준적인 상한 신뢰 구간(UCB) 알고리즘은 간단한 빈도주의 후회(regret) 분석을 허용하지만 계산 비용이 클 수 있는 반면, 톰슨 샘플링(Thompson Sampling, TS)은 계산 효율이 높지만 낙관적이지 않은 특성으로 인해 분석이 일반적으로 더 어렵다. 본 논문에서는 부호 있는 탐험(exploration) 노이즈를 절댓값으로 대체함으로써 기댓값 측면에서 낙관성을 보장하는 TS의 간단한 변형인 절댓값 톰슨 샘플링(Absolute Thompson Sampling, ATS)을 제안한다. 이는 TS의 계산 효율성을 유지하면서 TS 분석에서 흔히 요구되는 기술적으로 복잡한 반집중(anti-concentration) 논증을 피할 수 있어, UCB 방식의 단순한 후회 분석이 가능하다. ATS가 $\tilde{O}(d^{3/2}\sqrt{K})$의 후회를 달성함을 보이며, 이는 선형 밴딧에서 TS에 대한 기존 경계와 일치한다. 나아가 앙상블(ensemble) 크기로 정규화(normalization)하여 여러 절댓값 섭동에 대한 최댓값을 취하는 앙상블 절댓값 톰슨 샘플링(Ensemble Absolute Thompson Sampling, EATS)을 도입한다. 앙상블 크기가 커질수록 EATS는 UCB 목적함수로 수렴하여 극한에서 UCB 동작을 회복한다. 실험 결과, 중간 크기의 앙상블만으로도 이미 강력한 성능을 발휘함을 보인다. 본 결과는 이론과 실제 모두에서 무작위 탐험과 결정론적 낙관주의 사이의 가교를 제시한다.
원문 초록
In stochastic linear bandits, the canonical Upper Confidence Bound (UCB) algorithm admits a simple frequentist regret analysis but can be computationally demanding, while Thompson Sampling (TS) is computationally attractive yet typically harder to analyze due to its non-optimistic nature. We propose Absolute Thompson Sampling (ATS), a simple modification of TS that ensures optimism in expectation by replacing the signed exploration noise with its absolute value. This preserves the computational efficiency of TS while avoiding the technically involved anti-concentration arguments common in TS analyses, enabling a simple UCB-style regret analysis. We show that ATS achieves $\tilde{O}(d^{3/2}\sqrt{K})$ regret, matching existing bounds for TS in linear bandits. We further introduce Ensemble Absolute Thompson Sampling (EATS), which takes the maximum over multiple absolute perturbations with normalization by the ensemble size. As the ensemble size grows, EATS converges to the UCB objective, recovering UCB behavior in the limit. Experiments show that moderate ensemble sizes already yield strong performance. Our results point to a bridge between randomized exploration and deterministic optimism both in theory and practice.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.28616v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
적응적 실험에서 정책 개선 가치에 대한 추론
Inference on the Value of Policy Improvement in Adaptive Experiments
본 논문에서는 적응적으로 수집된 데이터 환경에서 정책 개선 가치(VPI, Value of Policy Improvement)에 대한 점근적 정규 추정량(asymptotically normal estimator)을 개발합니다. 특정 군집 내 최적 처치 정책의 가치와 기준선(baseline) 정책 가치 간의 격차로 정의되는 이 값은 맞춤형 처치 정책을 도입할 가치가 있는지 여부를 측정합니다. VPI에 대한 추정량을 구축하는 것은 고정된 정책의 가치를 추정하는 것보다 본질적으로 더 어렵습니다. 이는 적응적 실험과 연관된 상관 데이터 및 감소하는 성향(decaying propensities)을 다루어야 할 뿐만 아니라, 최적 정책이 유일하지 않을 때 기저 피추정량(estimand)의 비정칙성(non-regularity) 또는 경로별 미분 불가능성(lack of pathwise differentiability)도 모든 추정량이 함께 처리해야 하기 때문입니다. 본 연구에서 제안하는 추정량은 과거 데이터에 대해 가중 경험적 후생 극대화(weighted empirical welfare maximizing) 정책을 순차적으로 적합한 후, 미래 샘플에 대해 역성향 가중치(inverse propensity weighting)를 적용하여 이를 평가하는 방식으로 작동합니다. 우리는 최적 정책이 유일하다고 가정하지 않으며, 기저의 이질적 처치 효과에 대한 마진(margin) 가정도 두지 않습니다. 추정량 분석의 핵심적인 난점은 정책 학습을 통해 발생하는 후회(regret)가 추정량의 표준 오차보다 점근적으로 작음을 보이는 것입니다. 우리는 감소하는 성향 조건 하에서 정책 학습의 더 빠른 후회율(regret rate)을 입증함으로써 이를 달성하였으며, 이는 독립적으로도 유의미한 가치를 지닐 수 있습니다. 합성 및 준합성 데이터의 혼합을 통해 추정량의 포함 확률(coverage)을 평가할 뿐만 아니라, Caria 등이 요르단에서 진행한 구직 지원 프로그램의 효과 평가 적응적 실험에서 VPI를 추정하는 데에도 이를 적용합니다. 본 연구의 추정치는 최적 정책이 유일하다고 가정한 이들의 계층적 베이지안(hierarchical Bayesian) 분석 결과보다는 전반적으로 보수적이지만, 여전히 시리아 난민 집단 내에서 개인화가 지닌 이점을 입증합니다.
지속적 후보 집합을 활용한 선형 밴딧 가속화
Accelerating Linear Bandits with Persistent Candidate Sets
행동의 수가 $K$개로 매우 큰 고정된 집합을 갖는 선형 밴딧(linear bandit)에서는 완전 낙관적 점수 산출(exhaustive optimistic scoring)로 인해 라운드당 $\mathcal{O}(K)$회의 점수 평가가 필요하여 행동 선택 비용이 커질 수 있습니다. 본 논문에서는 $k$개의 활성 행동을 유지하고 매 라운드마다 나머지 $K-k$개 행동 중에서 $q$개의 도전자(challenger)를 균등하게 표본추출하는 Persistent Candidate LinUCB(\textsc{PC-LinUCB})를 제안합니다. 이 $k+q$개의 후보에 대해서만 점수를 평가함으로써, \textsc{PC-LinUCB}는 라운드당 점수 평가 횟수를 $\mathcal{O}(k+q)$로 줄입니다. 고정된 신뢰 수준에서 표준 선형 밴딧 학습 항과 $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ 차수의 추가적 탐색 비용(discovery cost)으로 구성된 문제 독립적(problem-independent) 및 문제 의존적(problem-dependent) 고확률 후회 경계(regret bound)를 증명합니다. 특히, 이 추가 비용은 시간 지평(horizon)에 따라 증가하지 않습니다. 고정된 간격(gap)과 충분히 긴 시간 지평에 대해 균등 도전자 표본추출 조건 하에서 $\Omega\left((K-k)/q\right)$ 후회 하한을 도출하여, 부분 후보 접근 자체가 불가피한 후회 비용을 수반함을 보여줍니다. 실험 결과, \textsc{PC-LinUCB}는 유사한 수준의 후회를 유지하면서 LinUCB의 속도를 대폭 가속하며, 지속적 후보 메커니즘이 LinUCB를 넘어 다른 알고리즘으로도 확장될 수 있음을 보입니다.
정보 이론적 불확실성 분해의 구조적 한계
Structural Limits of the Information-Theoretic Uncertainty Decomposition
기계학습에서 불확실성 추정(uncertainty estimation)은 일반적으로 표준 정보 이론적 프레임워크를 사용하여 불확실성을 우연적 불확실성(aleatoric uncertainty, AU)과 인식론적 불확실성(epistemic uncertainty, EU)으로 분해합니다. 그러나 실제로는 두 가지 중대한 문제인 얽힘(entanglement, AU와 EU 간의 높은 상관관계)과 인식론적 붕괴(epistemic collapse, 모델 용량이 증가함에 따라 EU의 크기가 축소되는 현상)가 발생합니다. 본 연구는 이 프레임워크를 함수 수준에서 분석하여, 가정된 AU와 EU 범위의 상당 부분이 유한한 환경에서는 실현 불가능하며 어떠한 클래스 확률로도 도달할 수 없음을 발견했습니다. 우리는 이러한 실현 불가능한 영역이 클래스 수 및 몬테카를로 표본 수 $N$($N$개의 멤버를 가진 앙상블 등)에 따라 어떻게 스케일링되는지 특성화하며, 해당 영역이 $\text{AU} \leq \log(2)/N$으로 제한됨을 밝힙니다. 결정적으로, 이 실현 불가능한 영역의 경계는 인식론적 붕괴를 설명하는 데 도움이 됩니다. 즉, 모델 확신도가 높을 때 이러한 근본적인 구조적 한계로 인해 $\text{AU} > \text{EU}$가 필연적으로 보장됩니다. 우리의 연구 결과는 앙상블 크기를 늘리면 실현 불가능한 영역이 줄어들어 인식론적 붕괴가 완화됨을 보여줍니다. 마지막으로, $\text{AU} \leq \log(2)/N$일 때 AU와 EU가 결합(coupled)되어 있음을 증명하였으므로, 낮은 AU 영역에서 이 둘을 독립적인 양으로 해석하는 것에 주의를 당부합니다.
행동하기 전의 선택: 장기적 도구 사용 에이전트를 위한 비교 가치 추정
Choosing Before Acting: Comparative Value Estimation for Long-Horizon Tool-Use Agents
대규모 언어 모델(LLM)은 복잡한 작업을 수행하기 위해 장기적인(long-horizon) 도구 호출 시퀀스에 의존하며, 여기서 각 호출은 작업 상태를 변경하고 이후 결정의 조건이 됩니다. 장기적 도구 사용에서는 긴 상호작용 궤적 전반에 걸쳐 최종 결과 기반의 보상만으로는 취약한 신용 할당(credit assignment)을 제공할 수밖에 없습니다. 단계별(step-level) 보상은 더 구체적인 피드백을 제공할 수 있으나, 신뢰할 수 있는 단계별 지도(supervision)를 얻으려면 종종 사람이나 LLM의 판단, 또는 중간 결정의 후속 영향을 추정하기 위한 추가적인 롤아웃(rollout)이 필요합니다. 본 논문에서는 효과적인 도구 사용 에이전트(agent)가 가능한 다음 도구 호출을 실행하기 전에 그 장기적 가치를 추정해야 한다고 주장합니다. 이러한 목표를 달성하려면 동일한 문맥에서 대안적인 도구 호출들에 대한 비교 지도(comparative supervision)가 필요하지만, 기록된 궤적(logged trajectory)에는 실제로 수행된 호출만 포함되어 있습니다. 이에 따라 우리는 도구 사용 에이전트를 위한 비교 추론(Comparative Inference for Tool-use Agents, CITA)을 제안합니다. CITA는 관측된 도구 동작, 베이즈 도구 그래프 시뮬레이터로부터 얻은 확장 가능한 지도, 그리고 LLM 기반 비교를 통한 의미적 판단을 결합한 쌍(paired) 신호로부터 비교 추론 모델(Comparative Inference Model, CIM)을 학습합니다. 그 결과 CIM은 현재 문맥에서 가능한 다음 도구 호출이 최종 작업 성공에 기여할 가능성을 추정하도록 학습합니다. 세 가지 도구 사용 벤치마크와 다양한 백본 LLM 전반에서, CITA는 도구 F1 점수와 작업 성공률을 일관되게 향상시킵니다. 추가 분석을 통해 CIM이 비교 도구 선택에 대한 정확한 단계별 가치 추정치를 학습함을 보입니다.
FSPO: 예산 제약 기반 LLM 강화학습 사후 학습을 위한 정책 일관적 위험 및 파레토 실행 가능 제어
FSPO: Policy-Consistent Risk and Pareto-Feasible Control for Budgeted LLM RL Post-Training
적응형 대규모 언어 모델(LLM) 강화학습(RL) 사후 학습은 롤아웃(rollout) 온도, 그룹 크기, 클리핑, KL 정규화(regularization), 검증기(verifier) 할당, 업데이트 예산 등 여러 학습 제어 요소를 온라인으로 변경합니다. 그러나 세 가지 결합된 문제가 여전히 해결되지 않은 상태로 남아 있습니다. 행동 궤적(behavior trajectories)으로 학습된 미래 위험 모델은 실제로 배포될 제어기(controller)가 유발하는 위험을 정확히 추정하지 못할 수 있고, 기록된 상태-행동 쌍에서 보정(calibrated)된 점수는 선택적 행동 결정 후 보정 오차가 발생할 수 있으며, 자원별 독립적인 최소 비용만으로는 일반적으로 다중 자원에 걸친 실행 가능한 지속 경로를 보장하지 못합니다. 본 논문에서는 이러한 문제들을 종합적으로 해결하는 예산 제약 기반 LLM RL 사후 학습용 피드백 상태 제어기인 FSPO를 제안합니다. FSPO는 향후 결정에 사용되는 동일한 동결 제어기를 벨만 타깃(Bellman target)으로 따르는 정책 일관적(policy-consistent) 잔여 위험(risk-to-go) 모델을 장기 효용 모델과 함께 학습합니다. 또한 결정 조건부 궤적 보정(DCTC)은 임시 제어기가 선택한 행동으로 생성된 교차 적합(cross-fitted) 궤적에서 위험을 보정합니다. 파레토 자원 지속 보증(PRCC)은 잔여 구간(horizon) 동안 비지배(non-dominated) 누적 예약이 실행 가능할 때만 행동을 허용합니다. 동일한 GRPO 자원 범위 조건에서 FSPO는 66.11%의 홀드아웃(held-out) 정확도와 59.43%의 OOD(분포 외) 정확도를 달성하여, 평가된 가장 강력한 적응형 기준선(baseline)인 PB2의 64.47% 및 57.03%를 능가했습니다. 3개의 쌍체 학습 시드(paired training seeds) 기준 홀드아웃 및 OOD 평가에서 문맥 밴딧(contextual bandit) 대비 각각 +2.42 및 +3.19%p 향상되었습니다. 행동-배포 간 불일치가 큰 조건에서 정책 일관적 위험은 선택 결정 ECE를 0.108에서 0.053으로 낮췄고, DCTC는 동일 수락률 조건에서 이를 0.039에서 0.022로 낮췄으며, PRCC는 18개 행동 카탈로그에서 거짓 실행 가능 허용을 완전히 제거했습니다($0.197\rightarrow0.000$). 요인 제거 분석(factorial ablation)에서 세 요소를 모두 활성화했을 때 궤적 실패율은 0.181에서 0.083으로 감소했습니다.
움직임을 세고 목소리의 무게를 달다: 지속적 적대자가 존재하는 환경에서 보정된 다중 LLM 협의회를 위한 베이지안 변증법적 논증
Counting Moves, Weighing Voices: Bayesian Dialectical Argumentation for Calibrated Multi-LLM Councils under Persistent Adversaries
다중 대규모 언어 모델(multi-LLM) 협의회(council)는 여러 LLM이 질문에 대해 심의하고 신뢰도 추정치와 함께 답변을 반환하도록 합니다. 이러한 시스템이 추론에 점차 더 널리 사용됨에 따라, 해당 신뢰도는 보정된(calibrated) '정답일 확률'을 나타내야 하며, 일부 에이전트가 지속적으로 신뢰할 수 없는 경우에도 결정은 강건성을 유지해야 합니다. 기존의 협의회 집계(council aggregation) 방식은 두 가지 측면 모두에서 한계를 보입니다. 이들의 신뢰도 추정치는 정확성보다는 결단력을 측정하며, 지속적으로 신뢰할 수 없는 에이전트를 식별하거나 할인(discount)하지 못합니다. 본 논문에서는 협의회의 유형화된(typed) 움직임(누가 어떤 답변을 제안, 반박, 또는 양보했는지)을 에이전트별 신뢰도를 갖춘 고전적 주석자 모델의 관측값으로 취급하는 베이지안 변증법적 논증(Bayesian Dialectical Argumentation, BDA)을 소개합니다. 이러한 공식화는 다중 에이전트 심의를 신뢰도 추정 문제로 재구성하여, 지속적인 적대적 행동 하에서 심의 추적(deliberation trace)을 활용해 에이전트 신뢰도를 추론합니다. 추론된 에이전트 신뢰도에 따라 증거에 가중치를 부여함으로써, BDA는 후보 답변에 대해 보정된 사후 확률을 산출하는 동시에 지속적으로 신뢰할 수 없는 에이전트를 단순히 다수결로 배제하는 대신 반전(invert)할 수 있도록 합니다. 이진 및 다중 클래스 벤치마크 전반에서 BDA는 추가적인 LLM 호출 없이도 무비용(zero-cost) 협의회 집계 방식 중 최고의 보정 성능을 달성하며, 오염되지 않은 환경에서 경쟁력을 유지하면서도 지속적인 적대적 연합(coalition) 하에서 강건성을 향상시킵니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.