🤖 machine learning

Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attacks

본 논문은 은닉된 비잔틴 공격(hidden Byzantine attacks)에 직면한 온라인 협력 다중 에이전트 시스템을 위한 이론적 한계를 규명하고 강건한 학습 알고리즘을 제안하며, 보안 후회(security regret)가 구별 불가능한 공격 시나리오 사이의 정보 이론적 격차에 의해 근본적으로 결정됨을 입증하고, 제안된 학습기에 대해 $\widetilde{\mathcal O}(H^2S\sqrt{AK})$ 의 후회 상한을 제공한다.

원저자: Ximing Sun, Yue Wang

게시일 2026-08-10

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Ximing Sun, Yue Wang

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

로봇 팀, 자율주행 자동차, 혹은 AI 비서들이 함께 협력하여 패키지를 배달하거나 전력망을 관리하는 것과 같은 거대한 문제들을 해결하는 세상을 상상해 보십시오. 이상적인 세상에서는 팀의 모든 구성원이 계획을 완벽하게 따릅니다. 하지만 현실에서는 문제가 발생합니다. 때로는 로봇이 고장 나기도 하고, 더 심각하게는 "배신자"가 팀에 몰래 잠입하기도 합니다. 컴퓨터 과학에서 우리는 이러한 배신자를 "비잔틴(Byzantine)" 에이전트라고 부릅니다. 이는 마치 스파이 영화 속의 스파이와 같습니다. 그들은 단순히 탈퇴하는 것이 아니라, 팀 안에 머물며 도움이 되는 척하면서도 실행 직전에 팀의 지침을 비밀리에 변경합니다. 만약 드론 팀이 원을 그리며 비행할 계획이라면, 스파이는 한 드론에게 "사실은 벽을 향해 똑바로 날아가"라고 속삭일 수 있고, 그 드론은 그대로 실행하여 충돌을 일으킵니다. 무서운 점은 다른 팀원들이 스파이가 그곳에 있다는 사실을 모르며, 계획을 바꾼 그 비밀스러운 속삭임을 볼 수도 없다는 것입니다. 그들은 오직 최종 결과인 '충돌'만을 보게 됩니다.

이 논문은 팀이 누가 스파이인지, 혹은 스파이가 무엇을 하고 있는지조차 모르는 상태에서 어떻게 안전하게 협력하는 법을 배울 수 있는가라는 까다로운 질문을 다룹니다. 이것은 누군가 계속해서 파트너의 동작을 비밀리에 바꾸고 있는 상황에서 댄스 루틴을 배우는 것과 같습니다. 연구자들은 다음과 같은 질문을 던집s습니다: 팀이 최악의 시나리오(스파이가 모든 것을 망치려고 온 힘을 다하는 상황)에서도 잘 작동하는 전략을 학습할 수 있는가? 그들은 "보안 보장(security guarantee)"을 찾고 있습니다. 즉, 스파이가 계획을 어떻게 망치더라도 팀이 여전히 준수하게 수행할 것이라는 약속입니다. 이 논문은 단순히 추측하는 것이 아니라, 헤비 매스(heavy math)를 사용하여 무엇이 가능하고 무엇이 불가능한지를 정확히 증명함으로써, 적의 손을 볼 수 없을 때 학습의 한계가 어디까지인지를 보여줍니다.

기계 속의 스파이

이야기는 협동 게임을 배우려는 에이전트 팀으로부터 시작됩니다. 그들에게는 계획이 있지만, 함정이 하나 있습니다. 숨겨진 "비잔틴" 에이전트(스파이들)가 팀의 계획을 보고 실행 전에 자신의 몫을 비밀리에 덮어쓸 수 있다는 점입니다. 친구들이 강도 사건을 계획한다고 상상해 보십시오. 그들은 경로를 합의했습니다. 하지만 실제로는 스파이인 한 친구가 그 경로를 보고, 그룹 전체를 곤경에 빠뜨리기 위해 자신의 움직임을 바꾸기로 결심합니다. 나머지 팀원들은 자신들이 만들었다고 믿었던 계획과 최종 결과(보물을 얻었는지 아닌지?)만을 볼 뿐, 스파이의 비밀스러운 변경이나 스파이가 실제로 행한 움직임은 결코 볼 수 없습니다.

연구자들은 물었습니다: 팀이 안전하게 학습할 수 있을까? 그들은 "보안"을 스파이가 할 수 있는 최악의 행동에 맞서서 가능한 한 잘 해내는 것으로 정의했습니다. 만약 팀이 스파이가 그들을 무너뜨리기 위해 온 힘을 다하더라도 좋은 점수를 보장하는 정책을 학습한다면, 그것은 승리입니다.

스파이의 비밀스러운 힘

이 논문은 스파이의 힘이 전적으로 스파이가 무엇을 아느냐에 달려 있다는 놀라운 사실을 발견했습니다.

만약 스파이가 계획을 변경하기 전에 팀의 계획을 볼 수 있다면(마치 팀이 출발하기 전에 지도를 읽는 스파이처럼), 이 문제는 **(s, a)-직사각형 강건 MDP((s, a)-rectangular robust MDP)**라는 특정 유형의 수학 퍼즐이 됩니다. 쉬운 말로, 이는 스파이가 팀이 세우는 모든 개별적인 계획에 대해 최악의 결과를 선택할 수 있음을 의미합니다. 이는 당신이 어떤 움직임을 취하든 스파이가 그 정확한 움직임에 대한 최악의 대응책을 고를 수 있는 게임과 같습니다.

하지만 만약 스파이가 팀의 계획을 보지 못하고 추측해야 하는 "눈먼" 상태라면(마치 팀이 계획을 작성하기도 전에 변화를 외쳐야 하는 스파이처럼), 수학적 구조가 바뀝니다. 이 문제는 **s-직사각형 모델(s-rectangular model)**이 됩니다. 여기서 스파이는 모든 가능한 계획에 동시에 대응하는 전략을 골라야 하므로, 팀이 다루기에 실제로는 조금 더 쉽습니다. 왜냐하면 스파이가 각기 구체적인 계획에 맞춰 맞춤형 방해를 할 수 없기 때문입니다.

피할 수 없는 사각지대

여기서 가장 놀라운 부분이 나옵니다. 연구자들은 결과만을 관찰하여 학습하는 데에는 근본적인 한계가 있음을 증명했습니다.

두 가지 서로 다른 세계를 상상해 보십시오. 세계 A에서는 스파이가 형편없어서 팀이 훌륭하게 수행합니다. 세계 B에서는 스파이가 천재라서 팀이 형편없이 수행합니다. 연구자들은 이 두 세계를 설정했을 때 팀이 정확히 똑같은 결과를 보게 만들 수 있음을 보여주었습니다. 그들은 똑같은 계획, 똑같은 보상, 똑같은 결과를 봅니다. 데이터가 동일하기 때문에, 팀은 자신이 어느 세계에 있는지 구분할 수 없습니다.

이는 다음과 같은 냉혹한 진실로 이어집니다: 결과만을 보고는 스파이가 얼마나 "나빴는지"를 항상 알 수는 없다. 팀은 "와, 우리 정말 잘했어, 그러니까 스파이는 약했을 거야!"라고 생각할 수도 있습니다. 하지만 실제로는 스파이가 그날 선택할 수 있었던 최악의 움직임을 선택하지 않았을 뿐, 운이 좋았던 것일 수도 있습니다. 논문은 "실제로 일어난 일"과 "일어날 수 있었던 최악의 일" 사이의 간극을 **반응 간극(response gap)**이라고 부릅니다.

저자들은 이 간극이 불가피하다는 것을 증명했습니다. 학습 알고리즘이 아무리 똑똑하더라도, 스파이가 예측 불가능하게 행동하도록 허용된다면, 팀은 자신이 100% 안전하다는 확신을 가질 수 없습니다. 그들은 단지 스파이의 실제 움직임에 대해서는 잘 해냈다고 확신할 수 있을 뿐, 스파이의 최악의 가능한 움직임에 대해서까지 확신할 수는 없습니다.

새로운 학습 전략

그렇다면 스파이를 완벽히 볼 수 없다면, 어떻게 학습해야 할까요? 이 논문은 **단계 결합 강건 추정-의사결정 학습자(stage-tied robust estimation-to-decisions learner)**라는 새로운 학습 방법을 소개합니다.

이것은 스파이를 직접 잡으려 하지 않는 탐정과 같습니다. 대신, 탐정은 게임의 각 단계마다 "안전망"을 구축합니다.

안전망: 학습자는 스파이의 정체나 비밀스러운 움직임을 추측하는 대신, 발생할 수 있는 모든 "나쁜 결과"의 모델을 구축합니다.
단계 결합 기술: 보통의 학습 알고리즘은 모든 가능한 상태와 행동을 각각 따로 확인해야 하는데, 이는 거대한 바닥의 모든 타일을 하나씩 검사하는 것과 같아 느리고 비효율적입니다. 새로운 방법은 이러한 확인 과정을 "단계(stage, 또는 시간 단계)"별로 그룹화합니다. 이는 타일을 하나씩 체크하는 대신 줄 단위로 바닥 전체를 훑는 것과 같습니다. 이 방식은 학습 과정을 훨씬 빠르고 효율적으로 만듭니다.
결과: 팀은 보장된 성능을 내는 전략을 학습합니다. 논문은 팀의 "후회(regret, 완벽한 안전 전략과 비교했을 때 얼마나 못했는가)"가 게임을 더 많이 수행할수록 매우 느리게 증가한다는 것을 증명합니다. 구체적으로, 오차는 게임 횟수의 제곱근과 관련된 속도로 증가하며, 이는 학습 알고리즘 세계에서 매우 좋은 결과입니다.

핵심 요약

이 논문은 단순히 "여기에 멋진 새 알고리즘이 있다"라고 말하는 데 그치지 않습니다. 명확한 선을 긋습니다. 우리는 숨겨진 배신자에 맞서 강건해지는 법을 배울 수 있지만, 스파이가 매일 얼마나 "나빴는지"에 대한 불확실성을 완전히 제거할 수는 없다는 것을 증명합니다. "반응 간극"은 이 게임의 영구적인 특징입니다.

그러나 이 논문은 우리에게 희망을 줍니다. 이 새로운 "단계 결합" 방법을 사용함으로써, 우리는 스파이가 누구인지 혹은 무엇을 하고 있는지 모르는 상태에서도, 증명 가능한 수준으로 안전하고 효율적인 전략을 학습할 수 있습니다. 이는 배신을 견뎌낼 수 있는 팀을 구축하기 위한 청사진이며, 스파이가 계획을 망치려 해도 팀이 여전히 성공할 수 있도록 보장합니다. 수학적 근거는 탄탄하며, 증명은 엄격합니다. 결론은 명확합니다: 우리는 안전해지는 법을 배울 수 있지만, 스파이의 손을 완전히 볼 수는 없다는 사실을 받아들여야 합니다.

기술 요약: 은닉된 바이잔틴 공격 하의 협력적 다중 에이전트 시스템에서의 온라인 보안 학습

문제 정식화
본 논문은 바이잔틴 공격(Byzantine attacks)을 받는 다중 에이전트 시스템(MAS)에서의 온라인 협력 제어 문제를 다룹니다. 구체적으로, $B^\star$ 로 표기되는 미지의 고정된 에이전트 부분 집합이 침해된 유한 시계(finite-horizon) 협력 팀 마르코프 결정 과정(MDP)을 고려합니다. 이 바이잔틴 에이전트들은 실행 전 팀의 계획된 공동 행동을 관찰하며, 자신의 행동 좌표를 은밀하게 덮어쓸(overwrite) 수 있습니다.

학습 에이전트("학습자")는 공용 상태, 계획된 공동 행동, 공용 보상, 그리고 다음 공용 상태를 관찰합니다. 결정적으로, 학습자는 침해된 에이전트의 정체( $B^\star$ ), 특정 덮어쓰기 행동( $u$ ), 또는 최종 실행된 공동 행동을 관찰하지 못합니다. 목표는 **보안(security)**입니다. 즉, 최악의 경우의 덮어쓰기에 대해 팀의 성능을 최적화하고, 가능한 모든 실행 가능한 덮어쓰기 전략에 대해 보장되는 최대 수익인 최적 보안 가치(optimal security value)를 달하는 것입니다.

방법론 및 이론적 프레임워크

기하학적 축소 및 직사각형성 (Geometric Reduction and Rectangularity):
저자들은 공격자의 정보 패턴이 강건한 결정 문제(robust decision problem)의 기하학적 구조를 어떻게 결정하는지 먼저 규명합니다.

인사이더 모델 (계획을 관찰하는 경우): 코리션(coalition)이 덮어쓰기 전 계획된 행동을 관찰할 때, 문제는 정확히 $(s, a)$ -직사각형 강건 MDP로 축소됩니다. 각 상태-행동 쌍에 대한 불확실성 집합은 실행 가능한 덮어쓰기에 의해 유도된 공용 결과 법칙(public-outcome laws)의 볼록 껍질(convex hull)입니다. 이 설정에서는 학습자와 최악의 대응 모두에게 결정론적 비정상 마르코프 정책(deterministic nonstationary Markov policies)이 충분합니다.
블라인드 모델 (계획을 관찰하지 못하는 경우): 코리션이 현재의 계획을 알 수 없는 경우, 유도된 모델은 상태 내에서 행동들이 결합되는 $s$ -직사각형 모델입니다. 여기서 최적성을 위해서는 확률적 마르코프 정책(randomized Markov policies)이 필요합니다.

정보 이론적 한계 (반응 격차, The Response Gap):
본 논문의 핵심적인 이론적 기여는 **보안 후회(security regret, $Reg^{sec}_K$ )**를 두 가지 구성 요소로 분해하는 것입니다:
$Reg^{sec}_K = Reg_K + D_K$

$Reg_K$ : **수익 후회(return regret)**로, 최적 가치와 실제 데이터를 생성한 대응(response) 사이의 격차를 측정합니다.
$D_K$ : **누적 반응 격차(cumulative response gap)**로, 실제 대응과 최악의 대응 사이의 차이를 측정합니다.

저자들은 하한 구축(Theorem 4.1)을 통해 $D_K$ 가 정보 이론적으로 필수적임을 증명합니다. 동일한 공용 트랜스크립트를 가지더라도, 실현된 대응이 최악의 경우가 아니라면 두 개의 서로 다른 기저 MDP가 제로 수익 후회를 가지면서도 선형 보안 후회를 발생시킬 수 있습니다. 따라서, 제한 없는 실현된 공격에 대해 공용 피드백만으로 보안을 인증할 수 있는 알고리즘은 이 격차를 고려하지 않고서는 존재할 수 없습니다.

알고리즘: 단계별 결합 강건 추정-결정 (Stage-Tied Robust Estimation-to-Decisions, E2D):
저자들은 이 특정 위협 모델에 맞게 조정된 추정-결정(E2D) 프레임워크 [17, 18]를 기반으로 하는 온라인 학습 알고리즘을 제안합니다.

사적 코딩 (Private Coding): 전체 이력 피드백과 유계된 보상을 처리하기 위해, 학습자는 보상을 호라이즌 $H$ 에 의해 스케일링된 베르누이 변수로 사적으로 변환하여 "코딩된" 관측 공간을 생성합니다.
단계별 결합 추정기 (Stage-Tied Estimator): 모든 이전 상태(predecessor state)마다 별도의 인증서를 유지하여 추정 예산이 $\tilde{O}(HS^2)$ 에 달하는 표준 상태별 추정기와 달리, 제안된 알고리즘은 각 단계(layer)당 단일 연속 벡터(continuation vector)와 캘리브레이션 증인(calibration witness)을 유지합니다. 이를 통해 추정 예산을 $\tilde{O}(HS)$ 로 줄입니다.
결정 오라클 (Decision Oracle): 알고리즘은 추정 손실에 의해 정의된 신뢰 집합 내에서 최악의 후회를 최소화하는 정책을 선택하기 위해 근사 결정 오라클을 활용합니다.

주요 결과 및 후회 경계 (Regret Bounds)

후회 보장: 근사 E2D 결정 오라클을 가정할 때, 제안된 학습자는 다음과 같은 기대 보안 후회 경계를 달성합니다:
$E[Reg^{sec}_K] \leq \tilde{O}\left(H^2 S \sqrt{AK}\right) + E[D_K]$
여기서 $H$ 는 호라이즌, $S$ 는 공용 상태의 수, $A$ 는 공동 행동의 수, $K$ 는 에피소드의 수입니다.
베이스라인 대비 개선: 기존 강건 RL 방법의 직접적인 상태별 적응 방식이 $\tilde{O}(H^2 S^{3/2} \sqrt{AK})$ 를 보이는 것과 비교하여, 선행 항에서 $\sqrt{S}$ 만큼의 개선을 이루었으며, 이는 전적으로 단계별 결합 추정기 덕분입니다.
마르코프 정책의 최적성: 저자들은 인사이더 모델의 경우, 학습자를 결정론적 비정상 마르코프 정책으로 제한하는 것이 최적 보안 가치를 달성하기에 충분하며, 최악의 대응 또한 결정론적 마르코프 정책으로 취해질 수 있음을 증명합니다.

의의 및 주장

본 논문은 바이잔틴 행동 덮어쓰기 상황에서 신뢰할 수 있는 다중 에이전트 시스템을 위한 포괄적인 이론적 및 알고리즘적 토대를 제공한다고 주장합니다. 그 의의는 다음 세 가지 측면에 있습니다:

정확한 축소: 운영상의 바이잔틴 상호작용이 특정 클래스의 강건 MDP(직사각형 모델)와 정확히 동일함을 입증하여, 적대적 행동 조작과 강건 제어 이론 사이의 간극을 메웠습니다.
근본적 한계: **반응 격차( $D_K$ )**를 피할 수 없는 정보 이론적 장벽으로 식별하고 정량화했습니다. 본 논문은 추가적인 가정 없이는 공용 피드백만으로 온건한 실현과 최악의 실현을 구분할 수 없음을 명확히 하며, 통계적 학습 비용( $Reg_K$ )과 보안 인증 비용( $D_K$ )의 분리가 왜 필수적인지를 설명합니다.
알고리즘 효율성: 단계별 결합 추정기를 도입함으로써, 본 연구는 강건 학습이 상태 공간 크기( $S$ )의 제곱이 아닌 선형 스케일로 확장되는 샘플 복잡도로 달성될 수 있음을 보여주며, 보다 효율적인 보안 다중 에이전트 협력 경로를 제시합니다.

저자들은 미니맥스 최적 후회 경계를 결정하는 것이 향후 연구 과제로 남아 있음을 명시하며, 현재 경계의 타이트함(tightness)에 대해 겸허한 입장을 유지하고 있습니다.

기계 속의 스파이

스파이의 비밀스러운 힘

피할 수 없는 사각지대

새로운 학습 전략

핵심 요약

유사한 논문