딥러닝과 최적화의 만남: 조합적 행동 공간 문제를 해결하는 강화학습 알고리즘 SEQUOIA

릴리 쉬 등 연구진이 개발한 SEQUOIA 알고리즘은 조합적 행동 공간 문제를 해결하는 강화학습(RL) 알고리즘으로, 4가지 새로운 restless bandit 문제에 대한 실험에서 기존 방법보다 평균 26.4% 향상된 성능을 보였습니다. 이는 실세계의 복잡한 계획 문제 해결에 새로운 가능성을 제시합니다.

강화학습(Reinforcement Learning, RL)은 실세계의 복잡한 계획 문제를 해결하는 데 널리 활용되고 있습니다. 하지만, 많은 분야에서 RL 방법은 대규모 조합적 구조의 행동 공간을 효율적으로 처리하지 못하는 한계를 가지고 있습니다. 단일 단계에서 가능한 행동의 집합을 나타내는 것조차 복잡한 이산 최적화 문제가 필요할 수 있습니다.

릴리 쉬(Lily Xu)를 비롯한 연구진은 최근 발표한 논문 "Reinforcement learning with combinatorial actions for coupled restless bandits"에서 이러한 문제를 해결하기 위해 새로운 알고리즘 SEQUOIA를 제안했습니다. SEQUOIA는 훈련된 신경망을 최적화 문제에 통합하는 최신 기술을 활용하여 장기적인 보상을 최적화합니다. 핵심 아이디어는 Q-네트워크를 혼합정수계획법(mixed-integer program)에 통합하여 각 시간 단계에서 조합적 행동을 선택하는 것입니다.

연구진은 특히 restless bandits 문제에 초점을 맞췄습니다. restless bandits는 순차적 의사결정 문제의 많은 실제 사례를 포착하는 계획 문제의 한 종류입니다. 여기서 연구진은 coRMAB라는 새로운 restless bandits의 하위 문제를 소개합니다. coRMAB는 restless bandit의 각 팔(arm)을 분리할 수 없는 조합적 행동을 가진 문제로, 지수적으로 큰 공동 행동 공간에 대한 직접적인 해결책이 필요합니다.

SEQUOIA의 성능을 검증하기 위해 연구진은 4가지 새로운 restless bandit 문제를 고안했습니다. 각 문제는 다중 개입, 경로 제약, 이분 매칭, 용량 제약과 같은 조합적 제약 조건을 포함합니다. 실험 결과, SEQUOIA는 순차적 계획 및 조합적 선택을 동시에 처리할 수 없는 기존 방법보다 평균 26.4% 향상된 성능을 보였습니다. 이는 SEQUOIA가 실제 세계의 복잡한 문제 해결에 큰 잠재력을 가지고 있음을 시사합니다.

이 연구는 단순히 알고리즘 개발을 넘어, 실제 문제에 적용 가능한 새로운 restless bandit 문제를 제시하고, 기존 방법 대비 압도적인 성능 향상을 보여줌으로써, RL 분야에 중요한 기여를 했습니다. SEQUOIA는 앞으로 더욱 복잡한 실제 문제 해결에 활용될 것으로 기대됩니다. 특히, 자원 배분, 경로 계획, 네트워크 최적화 등 다양한 분야에서 SEQUOIA의 적용 가능성을 기대해볼 수 있습니다.