💻 computer science

Robust Restless Multi-Armed Bandit for Data Center Flexibility Services Through Virtual Machine Scheduling

본 논문은 데이터 센터가 불확실한 자원 활용도 및 서비스 품질 제약을 효과적으로 처리하면서도 전력망에 유연한 부하 감축 서비스를 제공할 수 있도록, 휘틀 지수 정책과 글로벌 상한 신뢰 구간 전략을 결합한 강건한 불안정 다중 암 밴딧 프레임워크를 제안한다.

원저자: Yifu Ding, Zixi Chen, Thomas Magnanti

게시일 2026-05-20

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yifu Ding, Zixi Chen, Thomas Magnanti

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

수천 개의 컴퓨터 작업이 데이터 센터 내부에서 실행되는, 사람 대신 컴퓨터 작업으로 진행되는 거대하고 고위험의"음악 의자"게임을 상상해 보세요.

이 논문의 이야기를 단순한 개념으로 나누어 설명합니다:

큰 문제: 전력망은 갈증에 시달립니다

전력망을 거대한 수도관으로 생각해 보세요. 때로는 관이 너무 가득 차게 됩니다 (수요가 너무 많음). 터지지 않도록 빠르게 물을 빼내야 합니다. 데이터 센터는 전기를 폭식하는 거대한 공장들입니다. 전력망이 스트레스를 받으면, 이 공장들에게 몇 분 동안"수도꼭지를 잠그라"고 요청합니다.

하지만 함정이 하나 있습니다: 전력망 운영자 (물 공급을 줄여달라고 요청하는 사람) 는 공장 내부에서 정확히 무슨 일이 일어나는지 알지 못합니다. 모든 개별 기계나 작업을 볼 수 없습니다. 그들은"큰 그림"(예:"공장 A 가 지금 전기를 많이 사용하고 있다") 만 볼 뿐입니다. 공장 관리자가 전력을 절약하기 위해 작업을 이동시키려 할 때, 실수로 고객의 영상 통화를 늦추거나 파일 업로드를 지연시킬 수 있습니다. 이것이"서비스 품질"(QoS) 손실입니다. 공장은 자신이 작업을 어떻게 이동시키는지 전력망 운영자에게 정확히 알려주고 싶어 하지 않습니다. 그것이 그들의 비밀 레시피이기 때문입니다.

해결책: 똑똑한"슬롯 머신"게임

저자들은**불안정한 다중 암 밴딧 (Restless Multi-Armed Bandit, RMAB)**이라는 개념을 사용하여 이 게임을 하는 새로운 방식을 제안합니다.

비유: 10 개의 다른 슬롯 머신 (데이터 센터) 이 있는 카지노에 있다고 상상해 보세요. 한 번에 3 개의 레버를 당길 (3 개의 데이터 센터에 전력 감축을 요청할) 만큼의 동전만 있습니다.
반전: 이 기계들은"불안정합니다". 당신이 레버를 당기지 않더라도 계속 변합니다. 한 기계가"뜨거웠던"(전력을 쉽게 줄일 수 있었던) 상태가, 내부의 작업이 변했을 뿐인데"차가워진"(전력을 줄이기 어려운) 상태로 바뀔 수 있습니다.
목표: 기계 (고객에게 너무 많은 지연을 초래하는 것) 를 망가뜨리지 않고 가장 많은 전력 절약을 얻기 위해, 지금어떤 3 개의 기계에 레버를 당겨야 하는지 알아내야 합니다.

도전 과제: 어둠 속에서 배우기

전력망 운영자는 슬롯 머신의 규칙을 알지 못합니다. 그들은 플레이하면서 규칙을 배워야 합니다.

옛 방식 (Thompson-Whittle): 이는 모든 기계의 규칙을 오랫동안 관찰하며 외우려 하는 학생과 같습니다. 똑똑하지만, 시작 부분에서는 학생이 막연히 추측하며 실수를 저지릅니다.
문제: 학생이 초기에 잘못 추측하면, 알아내기 전에 많은"동전"(돈/전력) 을 잃게 됩니다. 또한, 그들이 얻는 정보가"노이즈"(나쁜 라디오 신호와 같음) 로 가득 차 있다면 쉽게 혼란에 빠집니다.

새로운 트릭:"신뢰 혼합"전략

저자들은TM-TW(Trust-Mixed Thompson-Whittle)라는 새로운 플레이어를 만들었습니다. 이 플레이어를하이브리드 운전사로 생각해 보세요:

1 단계: 신중한 탐험가 (초반): 운전사가 막 시작할 때, 복잡한 지도 (배운 규칙) 를 아직 신뢰하지 않습니다. 대신, 큰 그림 (Global UCB) 과 즉각적인 교통 상황 (Local UCB) 을 보는"GPS"에 의존합니다. 그들은 지금볼 수 있는 것에 기반하여 안전하고 현명한 도박을 합니다.
2 단계: 점진적인 전환: 운전사가 더 많은 경험을 쌓고 지도가 더 명확해짐에 따라, GPS 에 의존하는 것을 서서히 멈추고 스스로 배운 지도를 신뢰하기 시작합니다.
3 단계: 전문가 (후반): 결국 운전사는 가장 효율적인 플레이 방식인 복잡한 배운 지도 (Whittle Index) 에 전적으로 의존하게 됩니다.

왜 이것이 멋진가요? 이는 초보자의 안전성과 전문가의 효율성을 결합합니다. 완벽한 상태가 될 때까지 기다리지 않고 좋은 움직임을 시작합니다.

결과가 보여주는 것

저자들은 마이크로소프트의 Azure 클라우드에서 나온 실제 데이터 (수천 개의 실제 컴퓨터 작업) 를 사용하여 이를 테스트했습니다.

경쟁자 격파: 그들의 새로운"하이브리드 운전사"(TM-TW) 는 기존의"학생"(TW) 과 단순한 추측자 (ST) 보다 일관되게 더 많은"동전"(전력 절감) 을 벌었습니다.
노이즈 처리: 데이터가 지저분하거나"노이즈"(나쁜 연결과 같음) 가 많을 때, 기존 방법들은 혼란을 겪고 나쁜 선택을 했습니다. 새로운 방법은 차분함을 유지하며 잘 수행했습니다. 왜냐하면 그것은 오직 지저분한 데이터에만 의존하지 않고 더 큰 그림도 보았기 때문입니다.
"블랙박스"격파: 그들은 유명한 AI 전략인 EXP4(리스트의 전문가들 중 가장 좋은 성과를 내는 사람을 선택하는 방식) 와 그들의 방법을 비교했습니다. 그들의 방법은 더 빠르게 학습했고, 누가 이겼는지에 대한 역사뿐만 아니라 문제의 구조를 이해했기 때문에 더 좋은 결과로 끝났습니다.

결론

이 논문은 전력망이 데이터 센터의 비밀 내부 레시피를 알 필요 없이, 데이터 센터에 에너지를 절약하도록 요청하는 똑똑하고 적응적인 방식을 제시합니다."신뢰 혼합"학습 전략을 사용하여, 이 시스템은 빠르게 학습하고 지저분한 데이터를 잘 처리하며 이전 방법들보다 더 많은 에너지를 절약하면서도 데이터 센터의 내부 운영을 비공개로 유지합니다.

저자들은 심지어 다른 사람들이 직접 시도하고 결과를 볼 수 있도록 코드 (RACER) 를 공유하기도 했습니다.

기술 요약: 데이터센터 유연성 서비스를 위한 강건한 비정지형 다중 암 밴딧

문제 정의
본 논문은 전력망의 공급과 수요 균형을 맞추기 위해 데이터센터의 수요 반응 (DR) 을 조정하는 과제를 다룹니다. 데이터센터 내에서 가상 머신 (VM) 작업을 재조정하는 것은 부하 감소를 위한 메커니즘을 제공하지만, 실시간 구현은 두 가지 요인으로 인해 방해받습니다: (1) 변동하는 자원 활용도의 불확실성, 그리고 (2) 프라이버시 우려로 인한 제공자가 상세한 작업 재조정 절차를 공개하기를 꺼리는 점. 결과적으로 그리드 운영자는 세분화된 작업 단위 데이터에 접근할 수 없으며, 집계된 배치 단위 정보 (예: 평균 전력 소비량 및 유연성 등급) 만 보유하고 있습니다. 핵심 문제는 그리드 운영자가 내부 상태 전이 또는 상세한 재조정 논리를 관찰하지 않고도 부하 감소를 위해 활성화할 데이터센터의 제한된 부분집합을 선택해야 하는 불확실성 하의 순차적 의사결정 과제로 공식화됩니다.

방법론
저자들은 이 상호작용을 모델링하기 위해 맥락적 비정지형 다중 암 밴딧 (RMAB) 프레임워크를 제안합니다.

MDP 공식화: 각 데이터센터는 마르코프 의사결정 과정 (MDP) 에서 "암 (arm)"으로 모델링됩니다. 상태는 순환 작업 큐 내의 위치를 나타내며, 행동은 활성화 (부하 감소 요청) 또는 수동 상태를 유지하는 이진 결정입니다. 보상은 재조정의 순 편익 (전력 절감량 마이너스 서비스 품질 패널티) 입니다.
인덱스화 가능성의 도전: $N$ 개의 데이터센터에 대한 결합 최적화를 해결하는 것은 결합 상태 공간 ( $|S|^N$ ) 의 기하급수적 성장으로 인해 계산적으로 처리 불가능합니다. 이를 해결하기 위해 저자들은 수동 보조금 하에서 문제를 독립적인 단일 암 하위 문제로 분해하는 Whittle 인덱스 정책을 활용합니다.
불확실성 하의 학습: 보상 및 전이 함수가 알려지지 않았으므로, 프레임워크는 Thompson Sampling을 사용하여 근본적인 동역학을 학습합니다.
- Thompson-Whittle (TW): 이 알고리즘은 각각 가우시안 및 디리클레 - 카테고리 사전 분포를 통해 모델링된 보상 및 전이 함수의 사후 분포에서 샘플링하여 Whittle 인덱스를 계산합니다.
- Trust-Mixed Thompson-Whittle (TM-TW): TW 는 큰 상태 공간에서 노이즈가 많은 전이 모델로 인해 초기 단계에서 변동성이 크고 학습이 느린 문제를 겪는다는 점을 인식하여, 저자들은 혼합 전략을 도입합니다. 이 접근법은 학습된 Whittle 점수와 **전역 및 국소 상한 신뢰 구간 (UCB)**에서 파생된 탐욕적이며 불확실성을 인지하는 점수를 혼합합니다. 신뢰 계수 ( $\tau_t$ ) 는 시간에 따라 선형적으로 감소하여, 모델이 신뢰할 수 있게 됨에 따라 관측 가능한 보상에 의존하는 탐욕적 탐색 단계에서 순수한 Whittle 활용 단계로 정책을 전환합니다.

주요 기여

프라이버시 보호 프레임워크: 본 논문은 프라이버시를 존중하면서 실제 VM 데이터셋을 사용하여 유연한 수요 반응을 가능하게 하는 맥락적 RMAB 프레임워크를 개발합니다. 그리드 운영자는 상세한 작업 단위 데이터 대신 집계된 배치 단위 특성만 활용합니다.
향상된 학습 정책: 저자들은 표준 Thompson-Whittle 인덱스 정책을 보완적인 UCB 전략으로 강화한 TM-TW 알고리즘을 제안합니다. 이 하이브리드 접근법은 특히 큰 상태 공간 설정에서 초기 학습 단계 동안 성능을 크게 향상시킵니다.
강건성 검증: 본 연구는 제안된 알고리즘이 다양한 상태 공간 크기와 노이즈가 있는 맥락 정보 전반에 걸쳐 강건성을 유지하며, 순수 Thompson-Whittle 과 최첨단 EXP4 프레임워크 모두를 능가함을 입증합니다.

결과
저자들은 Microsoft Azure VM 데이터셋을 사용하여 다양한 수의 데이터센터 (3 개에서 10 개) 및 활성화 예산을 가진 광범위한 시뮬레이션을 수행했습니다.

성능: TM-TW 전략은 다양한 구성에서 순수 TW 알고리즘보다 0.19% 에서 2.14% 까지 높은 누적 보상을 달성하여 일관되게 최고 성적을 거두었으며, 맥락적 밴딧 (ST) 기준선보다 훨씬 우수한 성과를 보였습니다.
EXP4 와의 비교: 제거 실험에서 TM-TW 는 이론적 오라클 Whittle 벤치마크의 95.82% 를 달성한 반면, 정책들을 블랙박스 전문가로 취급하는 EXP4 프레임워크는 79.40% 에 그쳤습니다. TM-TW 는 우수한 안정성을 보인 반면, EXP4 는 더 일찍 정체되었습니다.
민감도 분석:
- 상태 공간 크기: VM 작업 수가 증가함에 따라 (상태 공간이 확장됨) TM-TW 는 TW 및 ST 보다 성능 우위를 유지했으나, 인덱스 기반 정책의 계산 시간은 이차적으로 증가했습니다.
- 노이즈 강건성: 상태 관찰이 가우시안 노이즈 (최대 40% 오류 확률) 로 오염되었을 때, TM-TW 는 가장 강력한 강건성을 보여주었습니다. 특히 0.15 를 초과하는 노이즈 수준에서 TM-TW 는 완벽한 상태 지식을 기반으로 하지만 손상된 인덱스 조회로 고통받는 오라클 Whittle 정책을 능가했는데, 이는 손상된 맥락 정보를 완화하는 능력 있는 탐욕적 UCB 구성 요소에 기인합니다.

의의 및 주장
본 논문은 제안된 TM-TW 알고리즘이 상세한 내부 데이터가 unavailable 한 상황에서 데이터센터 유연성 서비스를 조정하기 위한 실용적인 솔루션을 제공한다고 주장합니다. Whittle 인덱스의 장기 최적성과 UCB 탐색의 단기 신뢰성을 결합함으로써, 이 방법은 학습 기반 RMAB 에 내재된 "차원의 저주"와 "콜드 스타트" 문제를 극복합니다. 저자들은 알고리즘이 강력한 경험적 성능과 강건성을 보이지만, 완전한 보장을 이해하기 위해서는 추가적인 이론적 후회 분석이 필요하다고 지적하며, 이를 향후 과제로 규정합니다. 프레임워크 (RACER) 의 코드는 재현성을 보장하기 위해 오픈소스로 제공됩니다.