Policy Stability for Measuring Operational Performance in Task Assignment with Time-Windows Under Internal Adversarial Influence

기술 요약: 내부 적대적 영향 하에서의 시간 창(Time-Windows)을 가진 작업 할당 시 운영 성능 측정을 위한 정책 안정성

문제 정의
본 논문은 자율적인 픽업 및 전달 시스템이 내부의 적대적 에이전트에 의해 노출되는 취약성을 다룹니다. 이러한 시스템에서 중앙 집중식 스케줄러는 가용 에이전트를 서비스 요청에 매칭합니다. 그러나 함대 내의 침해되거나 전략적인 에이전트는 작업 할당을 가로채기 위해 보고된 위치를 속일 수 있으며, 의도적으로 해당 요청을 처리되지 않은 상태로 남겨둘 수 있습니다. 이러한 행동은 스케줄러를 교란하여 지연, 요청 취소 및 비효율적인 자원 활용을 초래합니다.

핵심적인 과제는 이러한 적대적 환경에서 "정책 안정성(policy stability)"을 정의하는 것입니다. 전통적인 안정성 정의는 다음 사항들에 의존합니다:

1. 대기 이론적 워크로드(Queueing-theoretic workloads): 이는 에이전트별 경로 실행을 분석해야 하는데, 에이전트가 임의로 이탈하거나 요청 처리에 실패할 경우 분석이 불가능합니다.
2. 할인 강화 학습(Discounted RL) 비용: 이는 할인 계수에 의존하며, 장기적인 성능 저하를 과소평가하거나 누적된 적대적 효과를 은폐할 수 있습니다.
3. 백로그 전용 메트릭(Backlog-only metrics): 이는 과도한 지연 후에 결국 처리된 요청과, 수용 가능한 시간 창 내에 전혀 처리되지 않은 요청을 구분하지 못합니다.

저자들은 비협조적인 에이전트가 할당된 경로에서 임의로 이탈하는 적대적 설정에서는 기존의 기준들이 부적합하다고 주장합니다.

방법론
저자들은 에이전트 수준의 행동을 추론하는 대신, 관찰 가능한 시스템 수준의 신호에 기반하여 안정성을 분석하는 새로운 프레임워크를 제안합니다.

• 새로운 안정성 정식화: 본 논문은 두 가지 관찰 가능한 양량에 의해 정의되는 **평균 비용 안정성 기준(average-cost stability criterion)**을 도입합니다:

  1. 미처리 요청 수 ($O_t$).
  2. 누적 취소 요청 수 ($C_t$).
     단계 비용은 $g = O_t + C_t$로 정의됩니다. 정책은 무한한 시계(infinite horizon) 동안 기대 평균 비용이 유한할 때 안정적입니다.

• 이론적 분석:

  • 가정: 분석은 유계된(bounded) 요청 도착과 유한한 요청 시간 창(요청이 특정 기간 내에 처리되지 않으면 만료됨)을 가정합니다.
  • 핵심 정리: 이러한 가정 하에서, 미처리 요청 수는 시간이 지남에 따라 균등하게 유계됩니다 (Remark 1). 결과적으로, 본 논문은 제안된 평균 비용 기준에 따른 안정성이 기대 누적 취소 요청 수를 시간에 따라 균등하게 유계하는 것과 **동치(equivalent)**임을 증명합니다 (Theorem 1).
  • 퇴행적 안정성(Degenerate Stability): 저자들은 "퇴행적 안정성"이라 불리는 병리적 레짐을 규명합니다. 시간 창이 없다면, 시스템은 고전적인 백로그 기반 안정성 기준을 충족하면서도 운영상 수용 불가능한 수준의 지연된 백로그를 유지할 수 있습니다. 유한한 시간 창은 과도한 대기를 관찰 가능한 취소로 전환함으로써, 이러한 퇴행적 레짐을 배제합니다.

• 적대적 모델 및 할당 정책:

  • 적대적 지식: 정보 가용성에 따라 세 가지 모델을 정의합니다: 요청 전용(Request-Only) (제한된 정보), 팀 정보(Team-Information) (적대자 간의 협력), 전지전능(Omnipotent) (전체 시스템 인지 및 스케줄러 알고리즘에 대한 완전한 지식).
  • 할당 정책: 세 가지 정책을 연구합니다: 그리디(Greedy) (국소 최근접 이웃), 순간 할당(Instantaneous Assignment, IA) (전역 최적 매칭 및 확정), 재할당을 포함한 순간 할당(IA-RA) (픽업 전 재할당이 가능한 전역 매칭).
  • 실행 가능성을 고려한 할당: 매칭을 시간 창 만료 전 제약 조건을 충족할 수 있는 에이전트-요청 쌍으로 제한하는 할당 메커니즘을 도입합니다.

주요 기여

1. 관찰 가능한 평균 비용 안정성: 에이전트 수준의 경로 실행을 재구성할 필요 없이 시스템 수준의 신호(미처리 및 취소 요청)에 기반한 안정성 정식화를 제공하여, 협조적 및 적대적 설정 모두에 적용 가능하게 합니다.
2. 동치 정리: 유계된 도착 및 유한한 시간 창 조건 하에서, 안정성이 기대 누적 취소 요청 수를 유계하는 것과 동치임을 보여주는 증명을 제시합니다.
3. 퇴행적 안정성의 규명: 백로그 기반 기준이 실제로는 낮은 서비스 품질에도 불구하고 안정적이라고 잘못 분류하는 퇴행적 레짐을 규명하여, 시간 창과 취소 페널티의 필요성을 입증합니다.
4. 적대적 프레임워크: 전략적 인지 및 협력 수준을 포착하는 실행 가능성 인식 할당 절차와 적대적 지식 모델을 개발합니다.
5. 경험적 평가: 제안된 프레임워크를 평가하기 위해 실제 샌프란시스코 모빌리티 온 디맨드 택시 데이터를 사용한 사례 연구를 수행합니다.

결과
실제 샌프란시스코 도로 네트워크와 실제 수요 데이터를 사용하여 수행된 경험적 연구는 다음과 같은 결과를 도출했습니다:

• 함대 교정: 기존의 대기 이론적 베이스라인으로부터 도출된 협조적 함대 규모가 유한한 시간 창 하에서 안정적인 동작을 생성함을 확인했습니다.
• 퇴행적 안정성 검증: 요청 만료가 없는 설정에서는 미처리 요청 수가 정체되어, 고전적인 백로그 메트릭이 상당한 지연에도 불구하고 시스템을 안정적이라고 분류했습니다. 이는 퇴행적 안정성의 존재를 확인시켜 주었습니다.
• 적대적 영향: 유한한 시간 창 하에서, 제안된 평균 비용 메트릭은 요청 취소로 인한 지속적인 정책 비용 증가를 통해 불안정성을 정확히 식별했습니다.
  • 불안정성은 적대적 에이전트의 비율이 높아질수록 증가했습니다.
  • 전지전능한 적대자가 가장 심각한 저하를 일으켰으며, 그 뒤를 팀 정보 모델이 이었습니다.
  • IA-RA 정책은 IA나 Greedy보다 더 취약한 것으로 나타났는데, 이는 재할당 메커니즘이 적대자가 협조적 에이전트를 반복적으로 재지시하도록 허용하여 혼란을 증폭시키기 때문입니다.
• 메트릭 비교: 제안된 메트릭(백로그 + 취소)은 백로그 전용 메트릭이 놓친 불안정 레짐을 식별해 냈으며, 이는 백로그만으로는 시간 민감한 적대적 시스템의 서비스 품질을 평가하기에 불충분함을 입증합니다.

의의
본 논문의 주요 의의는 안정성의 정의를 이론적 워크로드가 아닌 운영상의 서비스 실패(취소)와 직접 연결했다는 점에 있습니다. 안정성을 취소된 요청의 유계성과 연결함으로써, 지연이 허용되지 않는 시간 민감형 라우팅 시스템에 의미 있는 메트릭을 제공합니다.

저자들은 유한한 요청 시간 창이 단순한 모델링의 세부 사항이 아니라, 시스템이 안정적으로 보이지만 실제로는 요청을 제대로 처리하지 못하는 "퇴행적 안정성" 레짐을 구별하는 데 필수적임을 강조합니다. 이 연구는 라우팅 안정성 분석, 내부 스푸핑에 대한 보안, 그리고 시간 창이 있는 서비스의 실질적 제약 사이의 간극을 메우며, 에이전트가 규정된 행동에서 벗어나더라도 견고하게 유지되는 프레임워크를 제공합니다.