arXiv:2602.06014v2 cs.LG

Optimism Stabilizes Thompson Sampling for Adaptive Inference

Shunxing Yan, Han Zhong

제출 2026-02-05

한국어 초록

톰슨 샘플링(TS)은 확률적 다중 슬롯머신(multi-armed bandit) 문제에 널리 활용되지만, 적응적 데이터 수집 환경에서의 추론 특성은 미묘하다. 표본 평균에 대한 고전적 점근 이론은 각 팔(arm)별 표본 크기가 확률적이며 행동 선택 규칙을 통해 보상과 결합되어 있기 때문에 실패할 수 있다. 본 연구에서는 독립적인 준가우시안(sub-Gaussian) 보상 잡음을 갖는 $K$-팔 확률적 다중 슬롯머신에서 가우시안 무작위 인덱스를 사용하는 톰슨 샘플링의 적응적 추론을 연구하고, 각 팔의 선택 횟수가 결정론적 척도 주변에 집중되는 \emph{안정성}을 회복하는 핵심 메커니즘으로 \emph{낙관주의(optimism)}를 규명한다. 이 안정성은 적응적 샘플링에도 불구하고 점근적으로 유효한 왈드(Wald) 추론을 가능하게 한다. 첫째, 여러 팔이 최적인 도전적인 체제를 포함하여 임의의 $K \ge 2$에 대해 분산 팽창 TS가 안정적임을 증명하며, 최적 팔들에 대한 점근적으로 균일한 할당과 준최적 팔들에 대한 날카로운 로그 선택 횟수 점근론을 도출한다. 이는 새로운 승자 맵(winner-map) 및 리아푸노프 드리프트(Lyapunov-drift) 기법을 활용하여 여러 최적 팔 간의 할당을 제어함으로써 \citet{halder2025stable}이 제기한 $K$-팔 확장 문제를 해결한다. 둘째, 가우시안 인덱스 분산은 유지하되 인덱스 중심에 명시적인 평균 보너스를 추가하는 대안적인 낙관적 수정을 분석하고, 유사한 안정성 결론을 도출한다. 요약하면, 적절하게 구현된 낙관주의는 톰슨 샘플링을 안정화하고 다중 슬롯머신 문제에서 점근적으로 유효한 왈드 추론을 가능하게 하며, 단지 완만한 추가적인 후회(regret) 비용만을 수반한다.

원문 초록

Thompson sampling (TS) is widely used for stochastic multi-armed bandits, yet its inferential properties under adaptive data collection are subtle. Classical asymptotic theory for sample means can fail because arm-specific sample sizes are random and coupled with the rewards through the action-selection rule. We study adaptive inference for Thompson sampling with Gaussian randomized indices in $K$-armed stochastic bandits with independent sub-Gaussian reward noises, and identify \emph{optimism} as a key mechanism for restoring \emph{stability}, meaning that each arm's pull count concentrates around a deterministic scale. This stability yields asymptotically valid Wald inference despite adaptive sampling. First, we prove that variance-inflated TS is stable for any $K \ge 2$, including the challenging regime where multiple arms are optimal, with asymptotically uniform allocation over optimal arms and sharp logarithmic pull-count asymptotics for suboptimal arms. This resolves the $K$-armed extension question raised by \citet{halder2025stable}, using new winner-map and Lyapunov-drift techniques to control allocation among multiple optimal arms. Second, we analyze an alternative optimistic modification that keeps the Gaussian index variance unchanged but adds an explicit mean bonus to the index center, and establish a similar stability conclusion. In summary, suitably implemented optimism stabilizes Thompson sampling and enables asymptotically valid Wald inference in multi-armed bandits, while incurring only a mild additional regret cost.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2602.06014v2제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2610.15789v1stat.ML공통 태그 Multi-Armed Bandits, Sequential Decision Making

적응적 실험에서 정책 개선 가치에 대한 추론

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) 분석 결과보다는 전반적으로 보수적이지만, 여전히 시리아 난민 집단 내에서 개인화가 지닌 이점을 입증합니다.

arXiv:2610.13407v1cs.LG공통 태그 Multi-Armed Bandits, Sequential Decision Making

지속적 후보 집합을 활용한 선형 밴딧 가속화

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를 넘어 다른 알고리즘으로도 확장될 수 있음을 보입니다.

arXiv:2610.02330v1cs.AI공통 태그 Bayesian Inference, Sequential Decision Making

행동하기 전의 선택: 장기적 도구 사용 에이전트를 위한 비교 가치 추정

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이 비교 도구 선택에 대한 정확한 단계별 가치 추정치를 학습함을 보입니다.

arXiv:2610.02828v1cs.AI공통 태그 Multi-Armed Bandits, Sequential Decision Making

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으로 감소했습니다.

arXiv:2609.27594v1cs.LG공통 태그 Multi-Armed Bandits, Sequential Decision Making

클러스터 인식 스케칭을 통한 효율적인 선형 밴딧

Efficient Linear Bandits via Cluster-Aware Sketching

본 논문에서는 유한한 아암 집합(finite arm set)을 갖는 고차원 환경에서 선형 밴딧(linear bandit)의 계산 효율성 문제를 연구합니다. 선형 밴딧에서는 특징(feature) 벡터의 차원 $d$가 증가함에 따라 매 업데이트 라운드마다 $O(d^2)$의 계산 비용이 증가하게 됩니다. SOFUL과 같은 전통적인 스케칭(sketching) 기반 방법들은 고정된 크기의 행렬 스케칭을 통해 계산량을 줄이지만, 데이터의 스펙트럼 꼬리(spectral tail)가 두껍고 스케치 크기가 적절히 선택되지 않을 때 무의미한 선형 후회(linear regret)를 초래할 위험이 있습니다. 후회 수렴(convergence)을 보장하고 계산 비용을 효과적으로 줄이기 위해, 우리는 클러스터링 메커니즘을 도입하고 클러스터 스케치 선형 밴딧(CS-LB) 알고리즘을 제안합니다. 제안하는 방법은 스펙트럼 꼬리 취약점 없이 강건한 서브리니어 후회(sublinear regret)를 보장하도록 각 클러스터 내에서 전체 공분산 정보를 보존하고, 각 클러스터에 센티널(sentinel)을 할당하여 클러스터 전환을 수행하며, 조정 가능한 스케치 크기 $l<d$를 통해 라운드당 업데이트 계산량을 $O(l^2d)$로 줄입니다. 합성 데이터셋에 대한 실험은 제안된 방법이 효율성과 후회 간의 유리한 절충(trade-off)을 일관되게 유지함을 보여줍니다.

arXiv:2609.24876v1cs.AI공통 태그 Bayesian Inference, Sequential Decision Making

사회적 능동 추론에서의 파트너별 정서적 정밀도

Partner-Specific Affective Precision in Social Active Inference

다중 에이전트 사회적 맥락에서는 관계마다 모델 신뢰성이 달라진다. 타인이 무엇을 할지 추론하는 것을 넘어, 에이전트는 그 추론이 각 관계에 대해 정책 선택을 얼마나 확신 있게 이끌어야 하는지 보정해야 한다. 한 파트너에 대해서는 잘 검증된 모델을, 다른 파트너에 대해서는 취약한 모델을, 또 다른 파트너에 대해서는 수정 중인 모델을 유지할 수 있으며, 이를 단일 신뢰도 추정으로 묶으면 정책 선택에 관련된 정보가 사라진다. 따라서 우리는 정서적 정밀도를 현재 파트너 모델에 대한 신뢰의 관계 특이적 메타인지적 추정으로 형식화한다. 각 파트너의 행동 증거는 국소 신뢰도 추정을 갱신하고, 이는 선택 시 정책 정밀도를 조절하여 그 신념의 내용을 바꾸기보다는 정책에서 현재 신념이 얼마나 강하게 표현되는지를 조절한다. 다중 파트너 등급 신뢰 게임에서의 시뮬레이션은 파트너 국소 정서적 정밀도가 행동에 주로 파트너 상태 추론의 직접적 개선보다는 정책 확약을 통해 영향을 미침을 보여준다. 이 메커니즘이 실현된 보상이 아니라 파트너 반응의 예측 가능성을 추적하기 때문에, 더 큰 신뢰는 반드시 더 높은 보상을 낳지 않으면서도 더 날카로운 정책 확약을 만든다. 사회적 행동의 급격한 변화 아래에서는 이전에 신뢰할 만했던 예측에서 축적된 신뢰가 관계가 바뀐 뒤에도 행동적으로 활성 상태로 남을 수 있어, 신뢰 수정이 사회적 변화 뒤처질 수 있음을 보여준다. 마지막으로 정밀도 이득과 사전분포를 달리하면 서로 다른 신뢰 보정 역학이 나타나, 신뢰의 축적과 수정이 모델 매개변수에 어떻게 의존하는지를 보여준다. 종합하면, 이러한 결과는 관계 특이적 정서적 정밀도가 사회적 예측과 사회적 정책 확약을 어떻게 구분할 수 있는지를 보여준다.

토론

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