arXiv:2110.08704

A Q-Learning-based Approach for Distributed Beam Scheduling in mmWave Networks

Xiang Zhang, Shamik Sarkar, Arupjyoti Bhuyan, Sneha Kumar Kasera, Mingyue Ji

제출 2021-10-17

원문 초록

We consider the problem of distributed downlink beam scheduling and power allocation for millimeter-Wave (mmWave) cellular networks where multiple base stations (BSs) belonging to different service operators share the same unlicensed spectrum with no central coordination or cooperation among them. Our goal is to design efficient distributed beam scheduling and power allocation algorithms such that the network-level payoff, defined as the weighted sum of the total throughput and a power penalization term, can be maximized. To this end, we propose a distributed scheduling approach to power allocation and adaptation for efficient interference management over the shared spectrum by modeling each BS as an independent Q-learning agent. As a baseline, we compare the proposed approach to the state-of-the-art non-cooperative game-based approach which was previously developed for the same problem. We conduct extensive experiments under various scenarios to verify the effect of multiple factors on the performance of both approaches. Experiment results show that the proposed approach adapts well to different interference situations by learning from experience and can achieve higher payoff than the game-based approach. The proposed approach can also be integrated into our previously developed Lyapunov stochastic optimization framework for the purpose of network utility maximization with optimality guarantee. As a result, the weights in the payoff function can be automatically and optimally determined by the virtual queue values from the sub-problems derived from the Lyapunov optimization framework.

함께 살펴볼 논문

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

arXiv:2607.15229v1cs.LG공통 태그 Stochastic Optimization, Scheduling, Management

데이터 기반 블록 교체 스케줄링

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) 교체 사이의 구조적 비용 격차를 밝힌다.

arXiv:2608.23986v4math.OC공통 태그 Stochastic Optimization, Scheduling

지능의 그림자 가격: LLM 추론에서의 품질 저하와 재시도 피드백

The Shadow Price of Intelligence: Quality Degradation and Retry Feedback in LLM Inference

대규모 언어 모델 제공자는 연산 자원이 제약되어 있으며, 혼잡에 대한 일반적인 대응은 서비스를 저하시키는 것이다. 즉, 질의를 더 작은 모델로 라우팅하거나, 추론 예산을 줄이거나, 컨텍스트 윈도를 단축한다. 만족스럽지 못한 답을 받은 사용자는 재시도하여 시스템이 바쁜 동안 부하를 늘리거나, 이탈하여 잠재적으로 고객 이탈로 이어진다. 우리는 추론 서비스를 서비스 품질이 제공자의 의사결정인 제어 문제로 모델링한다. 재시도를 서비스율에 포함한 2국면 유체 근사는 닫힌 형태의 궤적과 교차 시간을 제공하므로, 품질 등급에 대한 동적 계획법에 시뮬레이션이 필요하지 않다. 우리는 더 약한 등급이 작업당 에너지는 덜 쓰지만 작업당 용량은 더 쓰는 영역을 규명하고, 유체 모델에서 그러한 등급으로의 반응적 스로틀링이 큐가 해소되지 못하게 할 수 있음을 보인다. 이질적인 고객이 있는 경우 이 문제는 재시도로 부풀려진 용량 계수를 갖는 수송 문제가 되며, 최적 라우팅은 $c\mu$ 유형의 지수를 따르고, 용량 제약의 쌍대는 클래스와 시간별로 질의 하나를 더 처리하는 한계 비용을 제공한다. 우리는 공개 벤치마크 데이터로 보정한 다섯 가지 사례에서 이 방법을 예시한다.

arXiv:2610.13923v1cs.NI공통 태그 Scheduling, Management

강화학습을 통한 심우주 통신용 목표 지향적 번들 관리 및 흐름 제어

Goal-Oriented Bundle Management and Flow Control for Deep-Space Communications via Reinforcement Learning

심우주 통신은 간헐적인 연결성, 긴 전파 지연, 중계 노드의 저장 용량 제약 하에서 동작합니다. 이러한 네트워크에서 번들 프로토콜(Bundle Protocol)은 저장-운반-전달(store-carry-forward) 통신을 가능하게 하며, 중계 노드가 제한된 저장 공간과 희소한 접촉 기회를 관리하도록 요구합니다. 중계기 측의 스케줄링 및 폐기(dropping) 결정은 본질적으로 목표 지향적입니다. 즉, 다운스트림 임무 목표에 가장 가치 있는 번들에 전송 자원이 할당되어야 합니다. FIFO와 같은 기존 스케줄러는 작업 효용을 명시적으로 최적화하지 못하며, 이기종 행성 소스 간에 불공정한 서비스를 제공할 수 있습니다. 본 논문에서는 달과 화성의 업데이트가 공유 버퍼 중계기를 통해 지구로 전달되는 접촉 기반 심우주 네트워크에서 중계기 측 번들 및 흐름 관리를 위한 폐루프 모델링 및 학습 프레임워크를 제시합니다. 목적지 측의 정보 신선도를 초과 수명(excess age) $Δ_i^e(t)=[Δ_i(t)-d_i(t)]^+$를 사용하여 정량화합니다. 여기서 $Δ_i(t)$는 소스 $i$의 정보 수명(Age of Information)을 나타내고 $d_i(t)$는 소스에 따른 지연 기준선입니다. 이 지표를 바탕으로 소스별 비선형 페널티를 지원하는 목표 지향적 손실을 정의하여 임무 관련성에 따른 우선순위 지정을 가능하게 합니다. 중계기 제어를 제약 조건이 있는 준 마르코프 결정 과정(CSMDP)으로 정식화하고, 마스킹된 라그랑주 근접 정책 최적화(PPO)를 사용하여 이를 해결합니다. 실행 가능성 인식 액션 마스킹은 남은 접촉 윈도우 내에 완료할 수 있는 번들로 전송을 제한합니다. DTNSim 시뮬레이션 결과, 기존 기준선 스케줄러 대비 수명 기반 효용 및 흐름 간 공정성이 향상됨을 보여줍니다. 제안된 프레임워크는 이기종 소스 간의 명시적인 공정성을 고려하면서 접촉 기반 역학 하에서 중계기 측 번들 스케줄링, 폐기 및 흐름 제어를 공동으로 최적화합니다.

arXiv:2610.02355v1cs.LG공통 태그 Stochastic Optimization, Scheduling

적응적 배치가 LLM 사전학습에 도움이 되는 이유는 무엇인가? 비유계 분산의 관점에서

Why Does Adaptive Batching Help LLM Pretraining? A Perspective from Unbounded Variance

학습 중 배치 크기를 늘리는 것은 대규모 언어 모델(LLM) 사전학습에서 흔히 사용되는 방법이지만, 그 성공 이면의 이론적 근거는 잘 이해되지 않고 있다. 확률적 최적화에 대한 분석은 흔히 균일하게 유계인 확률적 그래디언트 분산을 가정하지만, 최근의 증거들은 이 가정이 많은 실제 비convex 문제에서 성립하지 않음을 보여준다. Blum-Gladyshev(BG-0) 노이즈 모델은 분산이 초기화 지점으로부터의 거리에 따라 2차적으로 증가할 수 있도록 허용함으로써 이 가정을 완화하며, 이는 배치 크기 스케줄러가 학습 중 분산 증가를 제어함으로써 도움을 줄 수 있음을 시사한다. 그러나 이러한 증가는 실제로는 지나치게 보수적일 수 있다. 우리는 LLM 사전학습에서의 분산 증가를 실증적으로 조사하였으며, 조정 가능한 증가 지수를 갖는 일반화된 BG 모델이 실제 노이즈 거동을 더 정밀하게 설명한다는 것을 관찰하였다. 이러한 관찰에 기반하여, 우리는 유계 분산($a=0$)과 BG-0 노이즈($a=2$) 사이를 보간하는 일반화된 BG-$a$ 노이즈 모델을 도입한다. $L$-smoothness 하에서, 우리는 증가 지수에 의존하는 오라클 복잡도 $Ω(ε^{-(4+a)})$를 갖는 정보 이론적 하한을 도출하고, 반복(iterate)이 초기화 지점으로부터 멀어질 때 배치 크기를 증가시킴으로써 $ε$ 의존성 측면에서 이에 상응하는 상한을 확립한다. 마지막으로, 우리는 학습 중 동적인 배치 크기 조정을 통해 분산 증가를 제어하는 적응적 배치 스케줄러를 제안한다. C4 데이터셋에서 최대 10억 개 파라미터 규모의 OLMo2 모델을 사전학습하는 실험에서, 우리의 스케줄러는 동일한 토큰 예산 하에서 작은 배치 학습과 큰 배치 학습 모두보다 더 낮은 검증 손실을 달성하면서도, 작은 배치 학습 반복 횟수의 10% 미만만을 사용한다.

arXiv:2608.24471v2cs.AI공통 태그 Q-Learning, Scheduling

민첩 관측 위성을 활용한 해상 이동 표적 관측 스케줄링을 위한 암묵적 Q-러닝 기반 개미 군집 최적화

Implicit Q-learning-bootstrapped ant colony optimization for maritime moving-target observation scheduling with agile satellites

민첩 지구 관측 위성을 활용한 해상 이동 표적 관측 스케줄링은 동적이고 순서 의존적인 조합 최적화(combinatorial optimization) 문제입니다. 해수면 표적은 지속적으로 이동하므로, 표적의 움직임과 위성 궤도 기하 구조에 따라 관측 가능 윈도우가 가변적으로 변합니다. 따라서 스케줄러는 시간 윈도우, 자세 기동 및 탑재 자원 제약 조건 하에서 작업 선택, 위성 할당, 관측 윈도우 선택, 관측 순서를 공동으로 결정해야 합니다. 본 논문에서는 다중 위성 해상 이동 표적 관측 스케줄링을 위해 암묵적 Q-러닝(implicit Q-learning)을 부트스트랩한 개미 군집 최적화(ant colony optimization) 방법인 IQACO를 제안합니다. IQACO는 작업 선택 정책을 직접 학습하는 대신, 오프라인 암묵적 Q-러닝 모듈을 구성적 개미 군집 최적화에 임베딩하여 페로몬 요인, 휴리스틱 요인 및 증발률을 적응적으로 조절합니다. 압축된 탐색 상태 표현은 페로몬 분포, 현재 및 역대 최고 해의 품질, 반복(iteration) 진행 상황을 포착합니다. 온라인 스케줄링 중에는 개미 군집 최적화가 실행 가능한 관측 시퀀스를 구성하는 동시에, 학습된 정책이 현재 탐색 상태에 맞춰 탐색 동작을 조정합니다. 다양한 규모와 위성 구성을 가진 14개 시나리오에서의 실험 결과, IQACO는 비교 알고리즘들보다 지속적으로 우수한 성능을 보였으며 기존 개미 군집 최적화 대비 평균 목적 함수 값을 2.86%~9.41% 향상시켰습니다. 추가 비교 및 보완 실험은 다양한 스케줄링 조건과 문제 설정 전반에서 본 방법의 효과성과 강건성을 입증합니다. 이러한 결과는 오프라인 가치 학습이 제약이 있는 해상 이동 표적 관측 스케줄링을 위한 효과적인 적응형 탐색 제어 메커니즘을 제공함을 보여줍니다.

arXiv:2610.00234v1cs.AI공통 태그 Stochastic Optimization, Scheduling

상충하는 감독은 역량이 아닌 전념을 이동시킨다: 관례 무관 점수 하에서는 정확히 0이 되는 12.29σ의 배치 효과

Conflicting Supervision Moves Commitment, Not Capability: A 12.29σ arrangement effect that is exactly zero under a convention-agnostic score

둘 다 맞지만 서로 양립할 수 없는 두 가지 관례로 작성된 동일한 문제들로 모델을 학습(training)시키고, 이러한 데이터의 순서가 파라미터에 무엇을 새겨 넣는지 질문해 본다. 학습률 스케줄(learning-rate schedule)은 그 질문에 대한 배경 조건에 불과한 것이 아니다. 그것은 평균화 연산자(averaging operator)이며, 그 해답을 결정한다. 우리는 순서 효과에 배치와 스케줄이 서로 곱해지는 분리된 인수로 들어가는 경계를 증명한다. 배치는 오직 블록 주기(block period)로서만, 스케줄은 종점이 실행 과정의 특정 시점에 얼마나 많은 가중치를 둘 수 있는지로서만 관여한다. 감쇠하는 스케줄(decaying schedule)은 동일한 시점에 큰 보폭(step size)과 수축되지 않은 잔차를 동시에 둘 수 없지만, 상수 스케줄은 마지막 스텝에서 정확히 그렇게 한다. 감쇠가 순서 효과를 완화한다는 점은 사전학습(pre-training)에서 보고된 바 있으나, 그 메커니즘과 분리, 그리고 두 부분에 대한 통제된 측정은 본 연구의 성과이다. 하나의 말뭉치, 하나의 예산으로 경로 외의 모든 것을 고정한 채 10가지 순서로 lr_scheduler_type만 다르고 다른 것은 동일한 군(family) 하에서 두 번 실행하였다. 상수 학습률에서는 내부가 할당에서 0.2221, 11.63의 대비 하한을 차지하며 배치가 얼마나 블록화되어 있는지에 따라 단조성을 띤다. 기발표된 모든 실험군(arm)이 사용하는 단일 코사인 하에서는, 동일한 10개의 실험군이 자체 해상도로는 약 10개를 허용함에도 식별 가능한 2개의 상태를 차지한다. '순서가 중요하다'와 '순서가 중요하지 않다'는 하나의 조절 노브의 양쪽 끝에 해당한다. 경로가 새겨 넣는 것은 모델이 어느 관례에 전념(commit)하는지이며, 어떤 완전 일치(exact-match) 벤치마크도 이를 감지할 수 없다. 12개의 실험군 전반에서 acc_A+acc_B는 9.7% 이내로 일정한 반면 할당 비율은 0.04에서 0.87까지 변동하므로, 본 논문에서 측정하는 12.29-시그마 배치 전환은 관례 무관(convention-agnostic) 지표 하에서는 정확히 0이다. 이러한 보존 법칙은 감쇠군 전체에서 인용된 것으로, 상수 학습률군은 이를 확인하기에 더 노이즈가 많은 환경이다. 프롬프트에 관례를 명시하면 이러한 전환이 붕괴되어 합집합 상한(union ceiling)의 87.5%에 도달한다.

토론

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