arXiv:2604.14908v2 cs.LG

조합 만족화 밴딧을 통한 다중 사용자 mmWave 빔 및 전송률 적응

Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits

Emre Özyıldırım, Barış Yaycı, Umut Eren Akturk, Cem Tekin

제출 2026-04-16

한국어 초록

본 논문에서는 유한 코드북 기반의 아날로그 빔포밍을 사용하는 다중 기지국(BS)이 이산 데이터 전송률과 사용자당 고유한 빔을 통해 다중 단일 안테나 사용자 단말(UE)을 지원하는 다중 사용자 mmWave MISO 시스템의 다운링크 빔 및 전송률 적응을 연구합니다. 기지국은 ACK/NACK 피드백을 기반으로 전송 성공 여부를 학습합니다. 서비스 목표를 반영하기 위해 만족화(satisficing) 처리량 임계값 $τ_r$을 도입하고, 결합 빔 및 전송률 적응 문제를 빔-전송률 튜플에 대한 조합 세미 밴딧(combinatorial semi-bandit) 문제로 정식화합니다. 이 프레임워크 내에서 보수적인 신뢰도 추정과 사후 표본추출(posterior sampling)을 결합하여, 단순한 최대화 대신 $τ_r$ 충족을 지향하도록 학습을 유도하는 경량의 임계값 인지 정책인 SAT-CTS를 제안합니다. 주요 이론적 기여로서 만족화 목표를 갖는 조합 세미 밴딧에 대한 최초의 유한 시간 후회(regret) 한계를 제시합니다. $τ_r$이 실현 가능할(realizable) 경우 목표 대비 누적 만족화 후회를 시간에 독립적인 상수로 상한을 설정하며, $τ_r$이 실현 불가능할 경우 SAT-CTS가 확정된 CTS 라운드 외에서는 유한한 기댓값의 과도 상태만을 겪고 이후 후회는 재시작된 CTS 라운드들의 후회 기여도 합에 의해 결정되어 $O((\log T)^2)$의 표준 후회 한계를 달성함을 보입니다. 실용적인 측면에서는 표준 후회 및 공정성과 더불어 $τ_r$에 대한 누적 만족화 후회를 통해 성능을 평가합니다. 시변 희소 다중경로 채널을 사용한 실험 결과, SAT-CTS는 만족화 후회를 일관되게 줄이고 경쟁력 있는 표준 후회를 유지하는 동시에 우수한 평균 처리량과 사용자 간 공정성을 달성함을 보여줍니다. 이는 채널 상태 정보 없이도 피드백 효율적인 학습을 통해 서비스 품질(QoS) 목표를 충족하도록 빔과 전송률을 공평하게 할당할 수 있음을 나타냅니다.

원문 초록

We study downlink beam and rate adaptation in a multi-user mmWave MISO system where multiple base stations (BSs), each using analog beamforming from finite codebooks, serve multiple single-antenna user equipments (UEs) with a unique beam per UE and discrete data transmission rates. BSs learn about transmission success based on ACK/NACK feedback. To encode service goals, we introduce a satisficing throughput threshold $τ_r$ and cast joint beam and rate adaptation as a combinatorial semi-bandit over beam-rate tuples. Within this framework, we propose SAT-CTS, a lightweight, threshold-aware policy that blends conservative confidence estimates with posterior sampling, steering learning toward meeting $τ_r$ rather than merely maximizing. Our main theoretical contribution provides the first finite-time regret bounds for combinatorial semi-bandits with satisficing objective: when $τ_r$ is realizable, we upper bound the cumulative satisficing regret to the target with a time-independent constant, and when $τ_r$ is non-realizable, we show that SAT-CTS incurs only a finite expected transient outside committed CTS rounds, after which its regret is governed by the sum of the regret contributions of restarted CTS rounds, yielding an $O((\log T)^2)$ standard regret bound. On the practical side, we evaluate the performance via cumulative satisficing regret to $τ_r$ alongside standard regret and fairness. Experiments with time-varying sparse multipath channels show that SAT-CTS consistently reduces satisficing regret and maintains competitive standard regret, while achieving favorable average throughput and fairness across users, indicating that feedback-efficient learning can equitably allocate beams and rates to meet QoS targets without channel state knowledge.

제출 이력

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

  1. arXiv:2604.14908v2

함께 살펴볼 논문

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

arXiv:2610.10974v1cs.LG공통 태그 Multi-Armed Bandits, Combinatorial Optimization

오프-정책 평가를 위한 예산 제약 다중 소스 반사실적 주석 달기

Budgeted Multi-Source Counterfactual Annotation for Off-Policy Evaluation

오프-정책(off-policy) 평가(OPE)는 기록된 데이터로부터 타깃 정책의 가치를 추정하지만, 행동 정책의 제한된 커버리지로 인해 높은 분산의 가중치 재조정이나 보상(reward) 모델(model) 외삽이 불가피할 수 있습니다. 반사실적(counterfactual) 주석(annotation)은 관측되지 않은 행동에 대한 증거를 추가할 수 있지만, 도메인 전문가나 대규모 언어 모델(LLM)을 포함한 실제 소스는 비용이 많이 들거나 편향되거나 노이즈가 있을 수 있습니다. 본 연구에서는 맥락적 밴딧(contextual-bandit) OPE를 위해 이러한 주석을 예산 제약 하에서 획득하는 문제를 연구합니다. 소스별 비용과 오류 프로필이 주어졌을 때, 주석 계획에 의존하는 추정량 분산 성분을 최소화하도록 맥락-행동 쌍과 주석 소스에 대한 정수 할당 문제를 정형화합니다. 또한 첫 번째 주석 임계값과 국소적 주석 가치 영역을 통해 주석이 언제 유용한지 규명합니다. 결합된 다중 소스 문제에 대해, 목적 함수를 단조적으로 개선하는 동적 계획법 서브루틴 기반의 주화-최소화(majorization-minimization) 알고리즘을 개발합니다. 합성 임상 및 LLM 주석 기반 교육 밴딧 실험에서 본 할당 방법은 주석이 없는 경우 대비 고정 프로필 평균 제곱 오차(MSE)를 각각 20.58% 및 10.77% 감소시킴을 보여줍니다.

arXiv:2610.11007v1cs.AI공통 태그 Multi-Armed Bandits, Combinatorial Optimization

LLM 에이전트를 위한 상시 로드 컨텍스트 큐레이션: 중도절단 피드백을 갖는 용량 제한 구색 모델

Curating Always-Loaded Context for LLM Agents: A Capacitated Assortment Model with Censored Feedback

모든 세션이 시작될 때, 대규모 언어 모델(LLM) 에이전트는 $\texttt{AGENTS.md}$와 같은 고정된 컨텍스트 파일을 로드합니다. 파일에 로드된 각 토큰은 세션의 후속 라운드마다 반복해서 비용이 청구되며, 이러한 파일은 크기가 커질수록 성능을 저하시킬 수 있습니다. 그러나 실제로는 사람 또는 자동화된 큐레이터가 대개 내용을 덧붙이는(append) 방식으로 이러한 파일의 크기를 늘립니다. 본 연구에서는 컨텍스트 큐레이션을 용량 제한 구색 문제(capacitated assortment problem)로 정식화합니다. 지시문은 유한한 어텐션 용량 내에서 토큰을 소모하며, 지시문을 추가하더라도 다른 지시문의 준수율이 결코 높아지지 않는 반면 유지되는 지시문은 세션당 설정 비용(setup cost)을 발생시킵니다. 본 논문에서는 사용 가능한 후보 지시문의 수와 관계없이 최적 파일 크기의 상한을 증명하며, 단독 가치가 양수인 모든 지시문을 단순히 덧붙이는 방식이 최적의 부분 집합을 선택하는 것에 비해 순가치(net value) 측면에서 임의로 크게 악화될 수 있음을 증명합니다. 또한 토큰 예산은 토큰 가격이 과소평가되었을 때의 손실을 제한합니다. 이어 과거 세션으로부터 무엇을 학습할 수 있는지, 그리고 이 정보가 지시문의 추가 또는 제거 결정을 어떻게 이끌 수 있는지 살펴봅니다. 피드백은 본질적으로 중도절단(censored)되어 있습니다. 로드된 지시문의 이점과 위해는 관찰 가능한 반면, 누락된 지시문은 그 부재가 위해를 초래할 때만 피드백을 생성합니다. 이러한 환경에서 에이전트가 무시한 지시문을 삭제하는 것은 유용한 지시문까지 필연적으로 제거할 수 있음을 보입니다. 또한 지시문을 추가하기 전에 수집해야 하는 근거의 양을 특성화합니다. 아울러 인간 검토자가 기간당 제한된 수의 수정 사항만 검토할 수 있을 때의 후회(regret) 한계를 제시합니다. 실증 실험을 통해서도 실제 컨텍스트 파일에서 추출한 무관한 규칙들이 언어 모델의 준수율을 낮춘다는 점을 추가로 보입니다.

arXiv:2610.03296v1cs.AI공통 태그 Multi-Armed Bandits, Combinatorial Optimization

JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증

JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs

복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.

arXiv:2607.24162v2cs.AI공통 태그 Multi-Armed Bandits, Combinatorial Optimization

Agent-UCT: 비용 인식 에이전트 워크플로 최적화를 위한 트리에 적용된 상한 신뢰 경계

Agent-UCT: Upper Confidence Bounds Applied to Trees for Agentic Workflow Optimization with Cost-Awareness

검색-증강 생성(RAG) 파이프라인과 같은 에이전트 워크플로의 최적화는 엄격한 평가 예산 하에서 이산적 구성 요소 선택의 조합 공간을 탐색해야 한다. 기존 접근법—휴리스틱 탐색, 블랙박스 최적화, 표준 트리 탐색 방법—은 이러한 워크플로의 구성적 구조를 명시적으로 활용하지 않아 중복 계산과 비효율적인 예산 배분을 초래한다. 우리는 Agent-UCT(Agent-based Cost-Aware Upper Confidence Bounds Applied to Trees)를 제안한다. 이는 이분 접두 문맥 재사용 그래프에서 유도된 재사용 인식 정규화 항으로 UCT를 확장한 트리 탐색 알고리즘이다. Agent-UCT는 이전에 구체화된 구성 접두 문맥을 활용하는 분기를 선호하도록 선택을 편향시켜, 효과적인 탐험을 유지하면서 중복 실행을 줄인다. 우리의 프레임워크 RAGSpace는 LongRAG, LightRAG, Self-RAG의 이질적 RAG 구성 요소를 5차원 구성 공간으로 통합하여 체계적인 프레임워크 간 재조합을 가능하게 한다. WTB(Workflow Test Bench)는 결정적 재생, 콘텐츠 주소 지정 캐싱, 트랜잭션 일관성을 제공하여 중간 상태가 한 번 구체화되어 탐색 전반에 재사용되도록 보장한다. HotpotQA와 UltraDomain에서의 실험은 Agent-UCT가 평가된 고정 프레임워크 프리셋 중에서 가장 높은 표본 외 성능을 갖는 구성을 식별함을 보여준다. 전체 풀 평가에서 이분 접두 문맥 재사용은 접두 공유 없음 비용 상한 대비 논리적 탐색 비용을 73.6% 줄인다. 전체 풀 평가와 비교하여, 샘플링 기반 평가는 추가로 wall-clock 기준 4.2배 속도 향상을 달성한다. Agent-UCT, RAGSpace, WTB는 함께 비용 인식적이고 재현 가능하며 구성적으로 효율적인 에이전트 워크플로 최적화를 위한 통합 프레임워크를 제공한다.

arXiv:2607.22935v1cs.LG공통 태그 Fairness, Multi-Armed Bandits

정적·시간 가변 노출 하한을 갖는 불일치 반올림 공정 밴딧

Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

최소 노출 제약은 추천, 콘텐츠 큐레이션, 규제된 할당에서 각 공급자, arm, 또는 그룹이 집계적으로만이 아니라 기간 내에 보장된 노출을 받아야 할 때 발생한다. 우리는 정확한 노출 하한을 갖는 확률적 밴딧(stochastic bandits)을 연구하고, 핵심 대상은 반올림 문제임을 보인다. 분수 공정 스케줄이 정수 pull로 실현되며, 노출 오차는 정확히 불일치 벡터(discrepancy vector)이다. 주요 기여는 시간 가변 하한을 갖는 블록 단위 모델이다. BDQ-UCB는 모든 블록 하한을 결정적으로 만족하며, horizon $T$가 아닌 비필수 예산 $R$에 의해 지배되는 공정 regret을 갖고, 높은 확률에서 regret $O(\sqrt{KR\log(KT)})$를 달성한다. MOSS 잔차(residual) 변형은 $O(\sqrt{KR})$를 달성하고, 일치하는 하한이 양의 필수 노출(mandatory exposure)에서도 minimax rate $Θ(\sqrt{KR})$를 제공한다. kl-UCB$^{++}$ 잔차 규칙은 instance-dependent 최적성을 추가한다. 이 정식화는 겹치는 그룹 하한에 필수적이다. arm별 반올림은 그룹 크기에 대해 $Ω(s)$만큼 그룹 제약을 위반할 수 있는 반면, Beck--Fiala 영공(null-space) 반올림은 블록 예산 내에서 모든 그룹 하한을 만족하며 위반을 arm degree $t$ 미만으로 유지하고, 동일한 $R$-매개변수 regret과 UCB를 결합한다. 학습된 그룹 계획에 대해, 우리는 disjoint system을 $\widetildeΘ(\sqrt{KT})$에서 닫고, 겹침 하에서 naive index 규칙이 실패하는 이유를 설명하는 이중 원장(dual-ledger) 분해를 제시하며, 초기 cover-slack 조건 하에서 pathwise feasible한 plan-sampling 규칙을 증명하고 조건부 $\widetilde O(\sqrt{KT})$ 보장을 달성하되, 조건 없는 겹침 rate는 열어둔다. 합성 하한, MovieLens-100k 장르 노출, 배포 스트레스 테스트에 대한 실험은 penalty tuning 없이 정확한 feasibility를 보여주며, tuned Lagrangian baseline과 경쟁력 있는 regret을 보인다.

arXiv:2607.24647v1cs.AI공통 태그 Multi-Armed Bandits, Combinatorial Optimization

자율 연구에서 효율성의 중요성

Efficiency Matters in Autonomous Research

AI 기반 자율 연구(autonomous research, AR) 시스템은 다양한 작업에서 점점 더 효과적이 되고 있다. 그러나 이들의 성능은 여전히 주로 최종 결과의 품질로 평가된다. 본 논문에서는 해 탐색(solution-search) 과정의 효율성이 동등하게 중요하지만 종종 간과되는 성능 차원임을 주장한다. 강력한 AR 시스템은 고품질 결과를 산출할 뿐만 아니라, 가능한 한 적은 예산으로 그 결과에 도달해야 한다. AR이 수학과 코딩처럼 검증 비용이 낮은 영역에서, 해 평가에 값비싼 물리적 실험이 필요할 수 있는 실제 과학 환경으로 확장됨에 따라 탐색 효율성은 점점 더 중요해질 것이다. 이 차원을 포착하기 위해, 우리는 최종 결과 품질과 함께 파레토 프론트(Pareto frontier)의 곡선 아래 면적(area under the curve, AUC)을 사용하여 AR 시스템을 평가하는 방법을 제안한다. 우리는 12개의 시스템 최적화(systems-optimization) 작업에 걸쳐 언덕 오르기(hill climbing), 빔 서치(beam search), 트리 서치(tree search), 진화적 탐색(evolutionary search)을 포함한 여러 계열의 탐색 알고리즘을 비교한다. 어떤 단일 탐색 구조도 일관되게 가장 효율적이지는 않음을 발견한다. 또한 탐색 효율성과 최종 결과 품질은 서로 다른 성능 차원임을 보인다. 궁극적으로 최상의 결과를 달성하는 방법이라도 개선 속도가 느리고, 그 결과에 도달하기 전에 훨씬 더 많은 평가 예산을 소모할 수 있다. 가장 효과적인 탐색 정책은 일반적으로 사전에 알려져 있지 않기 때문에, 우리는 고정된 평가 예산을 여러 탐색 프로세스에 동적으로 할당하기 위해 포트폴리오 밴딧(portfolio bandit)을 사용하는 적응형 절차인 fluid search를 도입한다. 평가된 작업 전반에 걸쳐 fluid search는 가장 높은 전반적인 탐색 효율성을 달성하며, 각 작업에 대해 최적의 탐색 구조가 사전에 주어진 작업별 오라클(per-task oracle)의 성능과 밀접하게 일치한다.

토론

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