🤖 machine learning

Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions

이 논문은 정적인 하위 최적 데이터셋으로부터 효과적인 작업 숍(Job Shop) 및 유연한 작업 숍(Flexible Job Shop) 스케줄링 정책을 학습하는 오프라인 강화 학습 알고리즘인 CDQAC를 소개하며, 높은 성능과 샘플 효율성을 위해서는 궤적의 품질보다 광범위한 상태-행동 커버리지가 더 중요하다는 것을 입증한다.

원저자: Jesse van Remmerden, Zaharah Bukhsh, Yingqian Zhang

게시일 2026-06-11

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Jesse van Remmerden, Zaharah Bukhsh, Yingqian Zhang

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

당신이 수많은 기계와 산더미 같은 작업들을 처리해야 하는 바쁜 공장의 관리자라고 상상해 보십시오. 당신의 목표는 모든 일을 최대한 빨리 끝내는 것입니다. 이것이 바로 **작업 숍 스케줄링 문제(Job Shop Scheduling Problem)**입니다.

전통적으로, 이를 효율적으로 수행하는 법을 배우기 위해, 당신은 '로봇 견습생'(AI)을 고용하여 다양한 스케줄을 시도하고, 실수하고, 그 결과로부터 배우며 연습하게 할 수 있습니다. 이것을 **온라인 강화 학습(Online Reinforcement Learning)**이라고 합니다. 하지만 여기에는 함정이 있습니다. 로봇이 숙련되기 위해서는 수백만 번의 연습이 필요하며, 이는 엄청난 시간과 컴퓨터 자원을 소모한다는 점입니다.

또 다른 방법으로는, 인간 전문가를 고용하여 그들의 최적 스케줄을 기록하게 한 뒤, 로봇이 단순히 그 기록을 복사하도록 가르칠 수 있습니다. 이것이 **모방 학습(Imitation Learning)**입니다. 하지만 로봇은 기록을 작성한 인간보다 결코 더 뛰어날 수 없습니다. 로봇은 그 수준에 갇히게 됩니다.

핵심 아이디어: "무작위적인" 실수로부터 배우기

이 논문은 CDQAC(Conservative Discrete Quantile Actor-Critic)라고 불리는 새로운 방법을 소개합니다. 이것은 **오프라인 강화 학습(Offline Reinforcement Learning)**을 사용합니다.

이렇게 생각해 보십시오. 로봇이 실제 공장에서 직접 연습하게 하는 대신(느리고 비용이 많이 듭니다), 혹은 전문가를 그대로 복사하도록 강요하는 대신(잠재력을 제한합니다), 연구진들은 로봇에게 단순한 규칙이나 유전 알고리즘, 심지어 순수한 무작위 확률로 생성된 오래되고, 엉망이고, 때로는 형편없는 스케줄들이 담긴 거대한 도서관을 제공했습니다.

놀라운 발견은 무엇이었을까요? 로봇은 "전문가" 데이터보다 무작위 데이터로부터 더 잘 배웠다는 것입니다.

왜 무작위 데이터가 승리했을까요? (퍼즐 비유)

보통 AI 학습에서는 고품질의 데이터를 원합니다. 누군가에게 운전을 가르친다면, 전문 운전자의 영상이 필요하지, 벽에 들이받는 사람들의 영상이 필요한 것이 아닙니다.

하지만 저자들은 스케줄링은 다르다고 주장합니다. 그들은 이 이유를 설명하기 위해 두 가지 주요 비유를 사용합니다.

"조밀한 보상(Dense Reward)" 신호:
많은 AI 게임(비디오 게임 등)에서는 게임이 끝나 승리하거나 패배했을 때만 보상(점수)을 받습니다. 그 사이 과정에서는 자신이 잘하고 있는지 알 수 없습니다.
하지만 스케일링에서는 매 동작마다 즉각적인 피드백이 주어집니다. 어떤 작업을 기계에 배치하면, 그것이 전체 시간을 얼마나 증가시켰는지 즉시 알 수 있습니다. 이것은 마치 춤 동작의 끝에서만 점수를 받는 것이 아니라, 매 단계마다 점수를 받는 것과 같습니다. 즉, "나쁜" 무작위 동작이라 할지라도 AI에게 그것이 얼마나 나빴는지를 정확히 알려주어, 모든 행동의 가치를 학습할 수 있게 합니다.
"퍼즐 조각" (커버리지 vs 품질):
거대한 직소 퍼즐을 맞추고 있다고 상상해 보십시오.
- 전문가 데이터는 퍼즐 조각 상자의 윗부분 모서리에서 온 조각들만 있는 것과 같습니다. 이 조각들은 완벽하고 고품질이지만, 이미지의 아주 작은 부분만을 보여줍니다. 나머지 부분이 없기 때문에 퍼즐 전체를 완성할 수 없습니다.
- 무작위 데이터는 퍼즐의 모든 곳에서 가져온 조각들이 담긴 가방과 같습니다. 어떤 조각은 뒤집혀 있고, 어떤 것은 하늘에서 왔고, 어떤 것은 풀밭에서 왔습니다. 개별적으로는 엉망이거나 "틀려" 보일 수 있지만, 함께 모이면 전체 그림을 모두 커버합니다.
이 논문의 AI는 이 조각들을 "꿰매는(stitch)" 데 능숙하기 때문에, 완벽한 조각을 갖는 것(품질)보다 넓은 범위를 확보하는 것(커버리지)이 더 중요합니다. 무작위 데이터는 문제의 더 넓은 "영역"을 커버했기에, AI가 전문가 데이터보다 더 나은 해결책을 찾을 수 있게 해주었습니다.

AI가 학습하는 법 ("꿰매기" 비유)

이 AI는 단순히 스케줄을 복사하는 것이 아닙니다. 그것은 낡고 찢어진 옷더미(무작위 스케줄)를 보는 숙련된 재단사처럼 행동합니다.

빨간 셔츠의 소매가 완벽하게 맞는 것을 봅니다.
파란 셔츠의 바지가 완벽하게 맞는 것을 봅니다.
초록색 셔츠의 칼라가 완벽하게 맞는 것을 봅니다.

비록 더미 속에 있는 단 하나의 셔츠도 완벽하지 않았지만, AI는 이 최상의 부분들을 꿰매어(stitch) 이전에 존재하지 않았던 완전히 새롭고 완벽한 의상을 만들어냅니다. AI는 수천 번의 과거 시도들, 심지어 실패한 시도들까지 분석함으로써 특정 "작업"에 가장 적합한 "기계"를 선택하는 법을 배웁니다.

결과: 빠르고, 저렴하며, 더 나은 성능

이 논문은 이 새로운 방식(CDQAC)이 다음과 같음을 보여줍니다:

온라인 학습을 능가함: CDQAC는 실제 공장을 한 번도 본 적이 없음에도 불구하고, 수백만 번 연습해야 했던 "로봇 견습생"을 이겼습니다.
전문가를 능가함: 학습에 사용된 "전문가" 데이터보다 더 나은 스케줄을 만들어냅니다.
매우 효율적임: 효과적으로 학습하는 데 필요한 데이터의 **1%에서 5%**만을 필요로 했습니다. 이는 마치 10,000마일을 운전하는 대신 매뉴얼 몇 페이지를 읽고 운전을 배우는 것과 같습니다.
훌륭한 일반화 능력: 작은 규모의 문제에서 학습한 후, 한 번도 본 적 없는 훨씬 크고 복잡한 문제들도 성공적으로 해결했습니다.

요약

이 논문은 공정 스케줄링을 위해 완벽한 스승이나 수백만 시간의 연습이 필요하지 않다고 주장합니다. 그저 과거의 시도들(심지어 무작위적인 것들까지)이 담긴 크고 엉망인 더미만 있으면 됩니다. 이 모델은 그 엉망인 시도들 속에서 모든 단계의 "가치"를 정교하게 분석하는 특수한 알고리즘을 사용하여, 원래의 "스승"들이 만들어낼 수 있는 것보다 더 빠르고 더 나은 완벽한 스케줄을 꿰매어 만들 수 있습니다.

기술 요약: 스케줄링을 위한 오프라인 강화 학습에서의 하위 최적성(Suboptimality) 극복 및 일반화

1. 문제 정의

본 논문은 **잡 숍 스케줄링 문제(JSP)**와 **유연한 잡 숍 스케줄링 문제(FJSP)**를 다룹니다. 목표는 가용 가능한 기계들에 작업(job) 세트를 할당하여 **메이크스팬(makespan, 마지막 작업의 완료 시간)**을 최소화하는 것입니다.

JSP: 각 작업(operation)은 반드시 특정 단일 기계에 의해 처리되어야 합니다.
FJSP: 각 작업은 호환 가능한 기계 집합 중 임의의 기계에 의해 처리될 수 있습니다.
과제: 제약 프로그래밍(Constraint Programming)과 같은 정밀 방법론은 최적성을 보장하지만 대규모 인스턴스에 대한 확장성이 부족합니다. 휴리스틱(예: 유전 알고리즘, 우선순위 디스패칭 규칙)은 확장성은 좋으나 하위 최적(suboptimal)입니다.
현재 RL의 한계: 온라인 딥 강화 학습(DRL) 방법론(예: L2D, DANIEL)은 강력한 성능을 달ей지만, 수렴을 위해 시뮬레이션 환경과의 광범위한 상호작용이 필요한 샘플 비효율성 문제를 겪습니다. 반면, 오프라인 RL 방법론은 스케줄링의 하위 최적 데이터로부터 학습하는 데 어려움을 겪어왔으며, 종종 준최적 전문가 데모에 의존하거나 데이터 분포를 넘어 일반화하는 데 실패합니다.

2. 방법론: 보수적 이산 분위수 액터-크리틱 (CDQAC)

저자들은 정적이고 하위 최적인 데이터셋(무작위 휴리스틱 등으로 생성된 데이터 포함)으로부터 환경과의 상호작용 없이 효과적인 스케줄링 정책을 직접 학습하도록 설계된 오프라인 RL 알고리즘인 CDQAC를 제안합니다.

핵심 구성 요소

분위수 크리틱과 듀얼링 아키텍처 (Quantile Critic with Dueling Architecture):
- CDQAC는 스칼라 기대 수익 $Q(s,a)$ 를 추정하는 대신, 분위수 회귀(quantile regression)를 사용하여 전체 수익 분포 $Z_\theta(s,a)$ 를 모델링합니다. 이는 단일 행동에 따른 결과의 분산을 포착하며, 이는 동일한 행동이 미래의 결정에 따라 매우 다른 메이크스팬을 초래할 수 있는 스케줄링 문제에서 매우 중요합니다.
- 상태 가치 스트림 $V_\theta(s)$ 와 어드밴티지(advantage) 스트림 $A_\theta(s,a)$ 를 분리하는 듀얼링 네트워크(Dueling Network) 아키텍처를 채택합니다.
- 독창성: 동일한 입력을 두 스트림에 전달하는 표준 듀얼링 네트워크와 달리, CDQAC는 분리된 입력을 사용합니다. $V_\theta$ 는 전역 상태 임베딩만을 받고, $A_\theta$ 는 작업, 기계 및 쌍(pair)별 임베딩을 받습니다. 이는 노이즈가 섞인 어드밴티지 추정치가 전역 상태 가치를 오염시키는 것을 방지하여 학습을 안정화합니다.
보수적 Q-러닝 (CQL) 규제:
- 오프라인 RL의 흔한 실패 모드인 분포 외(Out-of-Distribution, OOD) 행동의 과대평가를 방지하기 위해, CDQAC는 CQL 페널티를 통합합니다.
- 크리틱 손실은 TD 손실과 데이터셋에 존재하지 않는 행동의 과대평가를 억제하는 규제 항을 결합하여, 학습된 정책이 보지 못한 상태-행동 쌍에 대해 보수적으로 유지되도록 보장합니다.
지연된 정책 업데이트 (Delayed Policy Updates):
- 가변 크기의 행동 공간을 가진 오프라인 이산 RL에서는 초기 단계의 노이즈 섞인 크리틱 추정치가 부트스트랩된 타겟을 통해 오류를 전파할 수 있습니다.
- CDQAC는 $\eta$ 크리틱 단계마다(실험에서는 4로 설정) 정책 네트워크를 업데이트합니다. 이는 분위수 크리틱이 정책 개선에 사용되기 전에 수익 분포에 안정적으로 적합(fit)될 수 있도록 하여, 하위 최적의 지역 최적점(local optima)으로 조기 수렴하는 것을 방지합니다.
네트워크 아키텍처:
- 알고리즘은 스케줄링 인스턴스를 인코딩하기 위해 **이중 어텐션 네트워크(Dual Attention Network, DAN)**를 활용합니다. DAN은 작업과 기계를 별도의 어텐션 블록을 통해 처리하여 복잡한 선행 관계 및 자원 제약을 포착하고, 액터와 크리틱을 위한 임베딩을 생성합니다.

3. 주요 기여

알고리즘 혁신: JSP/FJSP를 위한 최초의 오프라인 RL 방법론으로서, 순수하게 하위 최적 데이터(무작위 정책 포함)로부터 효과적인 정책을 학습하며, 기존의 온라인 RL 베이스라인보다 뛰어난 성능을 보이는 CDQAC를 도입했습니다.
아키텍처 설계: 스케줄링 문제의 가변 크기, 이산적, 조합적 행동 공간을 처리하기 위해 특화된, 분리된 입력을 가진 새로운 듀얼링 분위수 크리틱과 지연된 정책 업데이트를 제시했습니다.
데이터 품질에 대한 이론적 통찰: 본 논문은 "노이즈가 섞인 전문가(noisy-expert)" 데이터가 무작위 데이터보다 우월하다는 기존의 오프라인 RL 패러다임에 도전합니다. 저자들은 스케줄링의 경우 성능을 결정짓는 핵심 요소가 데이터의 품질이 아니라 **상태-행동 커버리지(state-action coverage)**라고 주장합니다. 이는 스케줄링의 두 가지 구조적 특성 때문입니다:
- 조밀하고 목적에 부합하는 보상(Dense, Objective-Aligned Reward): 보상 신호(음수의 부분 메이크스팬 증가량)는 로보틱스의 희소한 보상과 달리 조밀하며 최적화 목적과 완벽하게 일치합니다.
- 동일한 길이의 궤적(Equal-Length Trajectories): 모든 구성적 휴리스틱(전문가 또는 무작위)은 작업 수와 동일한 동일한 길이의 궤적을 생성하므로, 전문가 데이터를 유리하게 만드는 궤적 길이 편향(trajectory-length bias)이 제거됩니다.
  따라서 무작위 정책은 가장 넓은 상태-행동 커버리지를 제공하며, 이는 이 도메인에서 오프라인 RL을 위한 최적의 훈련 소스가 됩니다.

4. 실험 결과

저자들은 표준 JSP (Taillard, Demirkol) 및 FJSP (Brandimarte, Hurink) 벤치마크와 생성된 인스턴스에 대해 CDQAC를 평가했습니다.

베이스라인 대비 성능:
- CDQAC는 무작위 데이터로 학습되었음에도 불구하고 JSP 및 FJSP 벤치마크 모두에서 온라인 RL 베이스라인(DANIEL, Residual, FJSP-DRL, L2D)보다 일관되게 높은 성능을 보였습니다.
- 또한 다른 오프라인 RL 방법론(Offline-LD, IQL, Behavioral Cloning) 및 데이터 생성에 사용된 휴리스틱보다 뛰어난 성능을 기록했습니다.
- 특히, 무작위 데이터로 학습된 CDQA가 유전 알고리즘(GA)이나 우선순위 디스패칭 규칙(PDR) 데이터로 학습된 모델보다 더 나은 결과를 얻었습니다.
샘플 효율성:
- CDQAC는 매우 높은 샘플 효율성을 보이며, 원본 데이터셋 크기의 1%에서 5% (예: 10~25개의 훈련 인스턴스)만으로도 고품질 정책을 학습할 수 있습니다.
- 작은 훈련 인스턴스(예: $10 \times 5$ )로부터 학습하여 더 큰 미지의 인스턴스(예: $40 \times 10$ )로 잘 일반화되며, 이러한 분포 외(out-of-distribution) 시나리오에서 온라인 베이스라인을 능가합니다.
절제 연구 (Ablation Studies):
- 지연된 정책 업데이트를 제거했을 때 성능이 크게 저하되었습니다( $20 \times 10$ 인스턴스에서 최대 112%의 격차 증가). 이는 대규모 행동 공간에서 안정성을 위한 해당 요소의 필요성을 확인시켜 줍니다.
- 분리된 입력을 가진 듀얼링 아키텍처 역시 인스턴스 크기가 커짐에 따라 중요한 역할을 함을 보여주었습니다.
- 수정된 보상 구조(희소 보상 또는 프록시 보상) 및 조기 종료 실험을 통해, "무작위 데이터가 가장 좋다"는 현상이 표준 스케줄링의 조밀한 보상 및 동일한 길이의 궤적 특성에 엄격히 의존함을 확인했습니다.

5. 의의 및 주장

본 논문은 CDQAC가 조합 최적화 문제(스케줄링 등)에 대한 오프라인 RL 접근 방식을 어떻게 변화시켜야 하는지에 대한 중요한 전환점을 제시한다고 주장합니다.

패러다임의 전환: 성공을 위해 고품질의 전문가 데이터가 필요하다는 기존의 오프라인 RL 가정이 스케줄링에서는 성립하지 않음을 입증했습니다. 대신, 넓은 커버리지가 핵심적인 제약 조건입니다.
실무적 적용 가능성: 무작위 또는 하위 최적 휴리스틱으로부터 학습함으로써, CDQAC는 (온라인 훈련을 위한) 값비싼 시뮬레이터나 (훈련 데이터를 생성하기 위한) 계산 집약적인 전문가 솔버(예: CP)의 필요성을 제거합니다. 이는 완벽한 시뮬레이터를 구축하는 것은 어렵지만 과거의 하위 최적 데이터는 존재하는 실제 스케줄링 환경에서 오프라인 RL을 실행 가능한, 확장 가능한 솔루션으로 만듭니다.
최첨단 성능 (State-of-the-Art): 저자들은 CDQAC가 오직 무작위 데이터만으로 학습하면서도 JSP/FJSP에서 온라인 RL을 능가하는 최초의 오프라인 RL 방법론임을 밝히며, 이 분야의 새로운 벤치마크를 설정했습니다.