Strategic Concealment of Environment Representations in Competitive Games

논문 요약: 경쟁적 게임에서의 환경 표현 전략적 은폐

이 논문은 경쟁적 게임 환경에서 에이전트 (특히 공격자) 가 자신의 환경 표현 (Environment Representation) 을 전략적으로 은폐하고, 방어자가 이를 추론하여 대응하는 문제를 다룹니다. 불완전 정보 하에서 공격자가 자신의 내부 표현 구조를 숨김으로써 방어자의 추론을 교란하고, 궁극적으로 게임에서 전략적 이점을 얻는 메커니즘을 Bayesian 게임 프레임워크를 통해 분석합니다.

1. 문제 정의 (Problem Formulation)

• 배경: 현대 자율 시스템은 계산 한계와 센서 제약으로 인해 세계의 완전한 표현 대신 축소된 (coarse) 환경 표현을 사용합니다. 단일 에이전트 환경에서는 이러한 축소가 허용되지만, 다중 에이전트 환경에서는 축소된 표현이 노출될 경우 적에게 구조적 약점을 노출시켜 악용당할 수 있습니다.
• 게임 설정:
  • 환경: 유한 그리드 환경.
  • 참가자:
    • 공격자 (Attacker): 목표 지점에 도달해야 하며, 자신에게 할당된 비공개 환경 표현 (Superstate 로의 분할) 을 기반으로 경로를 계획합니다.
    • 방어자 (Defender): 공격자의 표현을 알지 못하며, 공격자의 행동 궤적 (Trajectory) 을 관찰하여 표현 유형을 추론하고, 특정 시점 $T$ 에서 장애물 (Barrier) 을 배치하여 공격자의 진행을 지연시킵니다.
  • 구속 조건 (SAD Constraint): 공격자의 표현은 상태를 '초상태 (Superstate)'로 분할하며, 동일한 초상태 내의 모든 상태는 동일한 행동 분포 (Same-Action-Distribution, SAD) 를 가져야 합니다. 이는 공격자의 전략 유연성을 제한합니다.
• 게임 단계:
  1. 1 단계 (Phase I, $t=0 \sim T$): 공격자가 목표에 도달하기 위해 이동하며, 방어자는 이를 관찰합니다. 공격자는 자신의 표현 유형을 숨기기 위해 의도적으로 비최적의 행동을 취할 수 있습니다.
  2. 장애물 선택 (Barrier Selection, $t=T$): 방어자는 관찰된 궤적에 기반하여 공격자의 표현 유형에 대한 신념 (Belief) 을 업데이트하고, 가장 효과적인 장애물 구성을 선택합니다.
  3. 2 단계 (Phase II, $t=T+1 \sim T_f$): 장애물이 배치된 환경에서 공격자가 목표에 도달합니다.

2. 방법론 (Methodology)

이 연구는 완전 베이지안 스택버그 균형 (Perfect Bayesian Stackelberg Equilibrium, PBSE) 을 찾는 것을 목표로 합니다.

• 게임 모델:
  • 스택버그 게임: 공격자 (리더) 가 먼저 전략을Commit 하고, 방어자 (팔로워) 가 이에 대한 최적 반응 (Best Response) 을 취합니다.
  • 비대칭 정보: 공격자의 표현 유형 ($\theta$) 은 공격자의 사적 정보이며, 방어자는 사전 확률 분포 (Prior) 만 알고 있습니다.
• 수학적 접근:
  • 2 단계 역산 (Backward Induction):
    1. 2 단계 (MDP): 주어진 장애물과 공격자 유형에 대해 SAD 제약이 있는 마르코프 의사결정 과정 (MDP) 을 풉니다. 이는 이선형 계획법 (Bilinear Program) 으로 공식화됩니다. (SAD 제약으로 인해 선형 계획법으로 단순화되지 않음).
    2. 1 단계 (Bayesian Game): 2 단계의 최적 가치 함수를 말단 보상 (Terminal Reward) 으로 사용하여, 공격자의 경로 계획과 방어자의 신념 업데이트를 통합한 최적화 문제를 풉니다.
  • 신념 조작 (Belief Manipulation): 공격자는 방어자의 신념을 조작하기 위해 자신의 궤적을 무작위화 (Randomization) 합니다. 이는 방어자가 공격자의 유형을 오인하게 하여 비최적의 장애물을 선택하도록 유도합니다.
  • 최적화 알고리즘:
    • 공격자의 전략은 게임 트리 상의 궤적 분포를 최적화하는 문제로 변환됩니다.
    • SAD 제약과 베이지안 업데이트를 결합하여 이선형 계획법 (Bilinear Program) 을 구성합니다.
    • 이 문제를 통해 공격자가 방어자의 신념을 어떻게 조작할지, 그리고 방어자가 어떻게 대응할지 계산합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 베이지안 게임 프레임워크 제안: 공격자가 자신의 환경 표현을 은폐하고 방어자가 이를 추론하는 공격 - 방어 시나리오를 정형화했습니다.
2. 의도적 은폐 (Purposeful Concealment) 의 발견: 공격자가 단순히 불확실성을 최대화하는 것이 아니라, 자신의 성능을 향상시키기 위해 전략적으로 표현을 은폐한다는 것을 증명했습니다. 공격자는 특정 구간에서 무작위 행동을 통해 방어자의 신념을 왜곡시킵니다.
3. 이선형 계획법을 통한 균형 해법: 베이지안 추론, 전략적 계획, 신념 조작을 통합한 이선형 계획법 (Bilinear Program) 을 제시하여 PBSE 를 계산 가능한 형태로 도출했습니다.
4. 성능 향상 입증: 시뮬레이션을 통해 표현을 완전히 공개하는 최적 경로 대신, 전략적 은폐를 통해 공격자의 기대 보상이 유의미하게 증가함을 보였습니다.

4. 실험 결과 (Results)

• 시나리오: 2 가지 유형의 표현 (Type 1: 목표 부근 해상도 낮음, Type 2: 목표 부근 해상도 높음) 과 2 가지 장애물 옵션을 가진 그리드 환경에서 시뮬레이션 수행.
• 관찰:
  • Type 1 공격자: 목표 부근의 해상도가 낮아 장애물을 우회하기 어려울 때, 방어자가 Type 2 로 오인하게 하기 위해 특정 지점에서 행동을 무작위화 (Up/Right 확률 분포) 합니다.
  • 방어자의 반응: 무작위화된 궤적을 관찰한 방어자는 공격자가 Type 2 일 확률이 높다고 판단하여 Type 1 에게 불리한 장애물 (Barrier 2) 을 선택할 가능성이 높아집니다.
  • 성능 비교:
    • 완전 정보 (Full Information): 방어자가 공격자 유형을 알 때 공격자의 기대 보상은 -0.978입니다.
    • 비대칭 정보 (Strategic Concealment): 공격자가 전략적으로 은폐할 때 기대 보상은 -0.841로 상승합니다.
    • 개선율: 전체 게임 기준 14% 향상, 2 단계 (장애물 배치 후) 만 고려할 경우 30.5% 의 상대적 성능 향상을 보였습니다.
• 신념 교란 효과: 공격자의 무작위 행동은 방어자의 신념을 [0.26, 0.74] 와 같이 불확실한 상태로 유지시켜, 방어자가 어떤 장애물을 선택해도 공격자에게 유리한 상황을 만듭니다.

5. 의의 및 결론 (Significance & Conclusion)

• 전략적 은폐의 자연스러운 발생: 에이전트가 자신의 표현 구조를 숨기는 것이 단순한 기만이 아니라, 경쟁적 환경에서 성능을 극대화하기 위한 합리적인 전략적 선택임을 수학적으로 증명했습니다.
• 자율 시스템 설계에 대한 시사점: 다중 에이전트 시스템에서 에이전트가 자신의 내부 표현 (Representation) 을 어떻게 설계하고, 언제 이를 공개하거나 은폐해야 하는지에 대한 새로운 설계 원칙을 제시합니다.
• 향후 연구 방향: 양측 모두 비공개 표현을 사용하는 확장, 그리고 의미 있는 표현 클래스와 사전 분포를 자동으로 생성하는 방법론 개발이 필요하다고 제안합니다.

이 논문은 자율 시스템의 보안과 전략적 의사결정 분야에서, "어떻게 정보를 숨길 것인가"에 대한 정량적이고 수학적인 해법을 제시했다는 점에서 중요한 의의를 가집니다.