구글 맵스에서의 월드 스케일 역강화 학습

October 1, 2023
1353 Views

날짜: 2023년 9월 12일

작성자: Matt Barnes, 소프트웨어 엔지니어, Google Research

요약:

이 블로그 글은 구글 맵스에서의 월드 스케일 역강화 학습에 대한 내용을 다루고 있습니다. 구글 맵스의 경로 탐색은 여전히 가장 유용하고 자주 사용되는 기능 중 하나입니다. A에서 B까지의 최적 경로를 결정하기 위해서는 예상 도착 시간, 톨비, 직선성, 도로 표면 조건(포장된 도로 또는 포장되지 않은 도로 등) 및 사용자 선호도와 같은 다양한 요소들 간의 복잡한 균형을 맞춰야 합니다. 이러한 사용자 선호도를 파악하기 위해 실제 여행 패턴을 분석하는 것이 자연스러운 방법입니다.

역강화 학습(Inverse Reinforcement Learning, IRL)은 관찰된 순차적 의사 결정 행동에서 선호도를 학습하는 전형적인 응용 분야입니다. 도로 네트워크의 형식화된 의사 결정 과정(Markov Decision Process, MDP)와 일련의 데모 경로(이동한 경로)가 주어졌을 때, IRL의 목표는 사용자의 잠재적 보상 함수를 복구하는 것입니다. 과거의 연구에서는 점점 일반적인 IRL 솔루션들이 개발되어 왔지만, 이러한 솔루션들은 월드 스케일 MDP에 대해서는 성공적으로 적용되지 못했습니다. IRL 알고리즘의 확장은 일반적으로 각 업데이트 단계에서 강화 학습 서브루틴을 해결해야 하는 도전적인 과제입니다. 보통은 성능을 향상시키기 위해 월드 스케일 MDP를 메모리에 맞춰 계산하는 것이 필요한데, 도로 세그먼트의 수가 많고 제한된 대역폭 메모리가 있는 경우에는 이러한 접근 방식이 현실적으로 불가능해 보입니다. 경로 탐색에 IRL을 적용할 때에는 각 데모 출발지와 도착지 사이의 모든 합리적인 경로를 고려해야 합니다. 이는 월드 스케일 MDP를 더 작은 구성 요소로 나누는 시도가 메트로폴리탄 지역보다 작은 구성요소를 고려할 수 없다는 것을 의미합니다.

이를 위해 "Massively Scalable Inverse Reinforcement Learning in Google Maps"에서는 Google Research, Maps 및 Google DeepMind의 다년간의 협력 결과를 공유하고 있습니다. 이 연구에서는 이 공간의 고전적인 알고리즘을 재방문하고, 그래프 압축 및 병렬화에 대한 개선 사항을 소개하며, 성능 균형에 대한 세밀한 제어를 제공하는 새로운 IRL 알고리즘인 Receding Horizon Inverse Planning (RHIP)을 소개합니다. 최종 RHIP 정책은 Google Maps에서 제안된 경로와 일치하는 비식별화된 이동 경로의 비율을 16-24% 상대적으로 향상시킵니다. 우리의 최신 정보에 따르면, 이는 현재까지 실제 세계 환경에서의 IRL의 가장 큰 적용 사례입니다.

IRL의 이점은 무엇일까요?

경로 탐색 문제에 대한 미묘하지만 중요한 세부 사항은 목적에 따라 달라지는 것입니다. 즉, 각 목적지 상태는 약간 다른 MDP(특정하게는 목적지는 터미널이며 보상이 없는 상태)를 유발합니다. IRL 접근 방식은 이러한 유형의 문제에 적합합니다. 학습된 보상 함수는 MDP 간에 전이되기 때문에, 목적지 상태만 수정하면 됩니다. 이는 일반적으로 정책을 직접 학습하는 접근 방식과는 대조적입니다. 후자는 보통 MDP 상태의 S배수의 추가 매개 변수가 필요합니다.

IRL을 통해 보상 함수를 배운 후, 우리는 강력한 추론 시간 트릭을 활용합니다. 먼저, 오프라인 일괄 설정에서 전체 그래프의 보상을 한 번 평가합니다. 이 계산은 개별 여행에 대한 액세스 없이 서버에서 완전히 수행되며, 그래프의 도로 세그먼트 일괄 처리에만 작동합니다. 그런 다음 결과를 인메모리 데이터베이스에 저장하고, 빠른 온라인 그래프 검색 알고리즘을 사용하여 모든 출발지와 목적지 사이의 가장 높은 보상 경로를 찾습니다. 이를 통해 깊이 매개화된 모델이나 정책의 온라인 추론을 수행할 필요가 없어지며, 서비스 비용과 대기 시간이 크게 개선됩니다.

Receding Horizon Inverse Planning (RHIP)

IRL을 월드 MDP에 확장하기 위해 우리는 그래프를 압축하고 지리적 영역에 기반한 희소한 전문가 모델의 혼합(Mixture of Experts, MoE)을 사용하여 전역 MDP를 분할합니다. 그런 다음 전통적인 IRL 알고리즘을 적용하여 로컬 MDP를 해결하고 손실을 추정하며, 그라디언트를 MoE로 보냅니다. 전 세계적인 보상 그래프는 최종 MoE 보상 모델을 압축 해제하여 계산됩니다. 성능 특성을 더욱 제어하기 위해, 우리는 Receding Horizon Inverse Planning (RHIP)이라는 새로운 일반화된 IRL 알고리즘을 소개합니다.

RHIP는 사람들이 광범위한 지역적 계획을 수행하면서도 근본적으로 비싼 확률적 정책을 사용하고 오래된 계획에 대해서는 저렴한 결정론적 계획을 사용하는 경향을 반영한 것입니다. 이 통찰력을 활용하기 위해, RHIP는 국부 경로 주변에서 강력하지만 비싼 확률적 정책을 따르고, 어느 정도의 지평선 이상에서는 더 저렴한 결정론적 계획을 따릅니다. 지평선 H를 조정함으로해 근사적인 관찰을 통해 MDP를 경계로 나눔으로써 RHIP는 전역 MDP에서도 효과적으로 작동합니다. 이러한 방식으로 RHIP는 월드 스케일 역강화 학습에 대한 새로운 접근법을 제시합니다.

구글 맵스에서의 월드 스케일 역강화 학습은 사용자의 선호도를 파악하여 경로 탐색을 개선하는 데 중요한 역할을 합니다. 이를 통해 보다 정확하고 맞춤화된 경로를 제공할 수 있으며, 서비스의 비용과 대기 시간을 줄일 수 있습니다. Google Research, Maps 및 Google DeepMind의 협력으로 개발된 RHIP 알고리즘은 일반화된 IRL 알고리즘으로서 월드 스케일 MDP에 대한 효과적인 해결책을 제공합니다.

이러한 연구는 현재까지 실제 세계 환경에서의 역강화 학습의 가장 큰 적용 사례로 알려져 있으며, 구글 맵스 사용자들에게 보다 뛰어난 경로 탐색 기능을 제공하기 위해 계속 발전하고 있습니다.

원문을 확인하려면 여기를 클릭하세요.