관측 불가 상태와 제약된 결정 시점을 갖는 마르코프 밴딧에서의 학습
Learning in Markovian bandits with non-observable states and constrained decision epochs
한국어 초록
이 논문은 관측 불가 상태(non-observable states)와 잠재적으로 제약된(constrained) 결정 시점(decision epochs)을 갖는 마르코프 밴딧(Markovian bandits)에서 후회(regret) 최소화 문제를 연구한다. 초점은 학습 알고리즘의 성능을 최선의 순수 정책(pure policy)과 비교하는 '순수' 후회 벤치마크에 제한된다. 이 순수 정책은 확률적 밴딧(stochastic bandits)의 최적 정책과 유사하게, 시작부터 끝까지 암을 전환하지 않고 최적 암을 선택한다. rested 마르코프 밴딧의 일반화인 자기 열화(self-degrading) 마르코프 밴딧을 도입하는데, 여기서 순수 정책은 항상 asymptotic하게 최적이다. 기저 밴딧에 대한 사전 지식이 없으면, 암을 드물게 전환하는 알고리즘의 후회는 모든 밴딧에 대해 초로그 스케일, 즉 학습 구간 T에 대해 ω(log(T))로 증가한다. 로그 영역에 도달할 수 없음에도 불구하고, UCB에 영감을 받은 낙관적 알고리즘 UCB-NOM을 설계하여 그 후회는 거의 로그 스케일이다. 마지막으로, 마르코프 밴딧 각 암의 바이어스 함수에 대한 bound 형태의 사전 지식이 주어지면, UCB-NOM의 적절한 인스턴스화가 O(log(T)) 후회를 달성함을 보인다. 또한 이 사전 지식은 UCB-NOM에 대해 O(√T log(T)) 최악 경우 후회 bound를 허용함을 보인다. 특히 우리의 후회 bound는 기저 마르코프 체인의 상태 수에 의존하지 않는다. 우리의 결과는 관측 불가 상태가 자기 열화 마르코프 밴딧에서 경미한 제약임을 시사한다.
원문 초록
This paper studies the problem of regret minimization in Markovian bandits with \emph{non-observable states} and possibly \emph{constrained} decision epochs. The focus is restricted to a ``pure'' regret benchmark, that compares the performance of the learning algorithm to the best \emph{pure policy} which -- akin to optimal policies of stochastic bandits -- picks the optimal arm from start to finish without ever switching. We introduce a generalization of rested Markovian bandits, \emph{self-degrading Markovian bandits}, for which pure policies are always asymptotically optimal.We show that without prior knowledge on the underlying bandit, the regret of algorithms that switch arms rarely necessarily scales super-logarithmically for every bandit, i.e., as $ω(\log(T))$, where $T$ is the learning horizon. Despite the unreachability of the logarithmic regime, we design UCB-NOM, an optimistic algorithm inspired by UCB, of which the regret is nearly logarithmic. Lastly, we show that given prior knowledge on the Markovian bandit in the form of a bound on the bias functions of its arm, a proper instantiation of UCB-NOM achieves $O(\log(T))$ regret. We further show that this prior knowledge allows for a $O(\sqrt{T \log(T)})$ worst-case regret bound for UCB-NOM. Notably, our regret bounds do not depend on the number of states of the underlying Markov chains. Our findings suggest that the non-observability of states is a mild inconvenience in self-degrading Markovian bandits.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.27448v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
데이터 기반 블록 교체 스케줄링
Data Driven Block Replacement Scheduling
우리는 \textit{블록 교체 정책(block replacement policy)} 하에서 $N$대의 독립 동형 기계를 유지·관리하기 위한 데이터 기반 알고리즘을 개발한다. 이 정책에서는 각 기계가 고장 시 교체되고, 모든 기계가 길이 $k$의 정규 간격으로 일괄 교체된다. 수명 분포가 알려지지 않은 경우 운영 데이터로부터 비용을 최소화하는 간격 $k^*$를 학습하는 것이 목표이다. 각 의사결정 시점마다 운영자는 $k \in \{1, 2, \ldots, K\}$를 선택하고, 그 결과 고장 이력(완전 수명과 우측 검열(right-censored) 수명의 혼합)을 관측하며, 갱신 함수(renewal function)에 의해 결정되는 단위 시간당 비용을 부담한다. 이를 확률적 다중 팔 밴딧(stochastic multi-armed bandit)으로 형식화하고, $O(K \log T)$ 후회(regret)를 달성하는 Hoeffding 및 Bernstein 기반 하한 신뢰 구간(lower-confidence-bound) 알고리즘을 제안하며, 이는 Lai--Robbins 하한과 일치한다. 블록 교체에 고유한 중첩 관측(nested observation) 성질을 활용한 상관 변형(correlated variants)은 $O((K-k^*)\log T)$ 후회를 달성하고, 차선 arm $k < k^*$에 대한 직접 pull은 $O(1)$번만 필요하다. 보완적으로 Kaplan--Meier 갱신 알고리즘은 검열 데이터로부터 수명 분포를 비모수적으로 추정하여, 거의 확실(almost-sure)한 정책 일관성을 달성하고 장기 구간에서 실증적으로 거의 0에 가까운 추가 후회를 보인다. 또한 평균 비용 MDP 두 가지를 분석한다. 경과 시간(time-elapsed) 형식화는 임의의 수명 분포에 대해 블록 교체가 해당 정책 클래스 내에서 최적임을 보이고, 연령 벡터(age-vector) 형식화는 증가하는 고장률(increasing failure rate) 분포 하에서 단조 임계값(monotone threshold) 구조를 증명하며 gold-standard 비용 벤치마크를 제공한다. 수치 실험은 이론적 순서를 확인하고, 최적 블록 교체와 연령 의존(age-dependent) 교체 사이의 구조적 비용 격차를 밝힌다.
LLM 라우팅을 위한 대리 보상 기반 상관관계 인식 문맥적 밴딧
Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing
우리는 기계 학습 모델이 생성하는 대리 보상(surrogate reward) 신호에 접근 가능하고 상관된 암(arm)을 갖는 문맥적 밴딧(contextual bandit) 문제를 연구하며, 대규모 언어 모델(LLM) 라우팅과 같은 응용에서 동기를 얻었다. 밴딧 피드백에만 의존하고 암 간 조건부 독립성을 가정하는 고전적 문맥적 밴딧과 달리, 우리의 설정은 문맥 의존적인 암 간 상관관계와 잡음이 있거나 잘못 명세될 수 있는 보조 보상 정보를 허용한다. 우리는 두 가지 상보적 설계를 통해 이러한 대리 보상을 활용하는 알고리즘을 제안한다. 결합 보상 혼합(coupled reward-mixing) 방식은 대리 신호가 신뢰할 수 있을 때 학습을 가속화하기 위해 실제 보상과 대리 보상을 통합하며, 분리 예측 혼합(decoupled prediction-mixing) 방식은 밴딧 피드백과 대리 보상에 대한 별도의 추정기를 유지하고 그 예측을 적응적으로 결합한다. 이러한 분리는 대리 보상의 잘못된 명세에 대한 견고성을 제공하여 최악의 경우 보상만 사용하는 밴딧 방법에 필적하는 후회(regret) 보장을 회복하면서, 대리 예측이 충분히 유익한 경우 개선된 후회를 달성한다. 우리는 두 방식에 대한 이론적 후회 분석을 제공하고, 다양한 정확도 대 비용 트레이드오프 하에서 LLM 라우팅 벤치마크를 대상으로 평가한다. 결과는 표준 문맥적 밴딧 기준선 및 강력한 정적 라우팅 방법과 비교하여 향상된 샘플 효율성과 일관되게 더 나은 정확도-비용 트레이드오프를 보여준다.
일반 함수 근사 하에서의 최적·효율적 문맥적 조합 세미-밴딧
Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation
적응적 실험에서 정책 개선 가치에 대한 추론
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를 넘어 다른 알고리즘으로도 확장될 수 있음을 보입니다.
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으로 감소했습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.