Learning in Markov Decision Processes with Exogenous Dynamics

이 논문은 에이전트의 행동과 무관하게 진화하는 외생적 상태 요소를 가진 구조화된 마르코프 의사결정 과정 (MDP) 을 연구하여, 이러한 구조를 활용하면 기존 방법보다 훨씬 우수한 학습 보장과 샘플 효율성을 달성할 수 있음을 이론적 하한선과 실증 실험을 통해 입증합니다.

핵심

1. 문제 상황: "날씨를 통제할 수 없는 조종사"

기존의 강화학습 AI 는 마치 **"날씨를 마음대로 바꿀 수 있는 마법사"**처럼 훈련됩니다.

• 기존 방식: AI 가 "왼쪽으로 날아가라"라고 명령하면, 그 명령이 비, 구름, 바람까지 모두 바꾸어 다음 상태를 결정한다고 가정합니다.
• 현실의 문제: 하지만 실제 세상에서는 그렇지 않습니다.
  • 주식 투자: 내가 "매수"를 해도 주식 가격은 시장 상황 (외부 요인) 에 따라 오르내립니다. 내 주문 하나로 가격을 움직일 수 없습니다.
  • 댐 관리: 내가 물을 방류해도 비가 오는지, 가뭄인지는 내가 통제할 수 없습니다.
  • 택시: 내가 어디로 가든, 길거리의 교통 체증 (외부 요인) 은 내가 통제할 수 없습니다.

이런 '내가 통제할 수 없는 외부 요인 (Exogenous Dynamics)' 때문에 AI 는 혼란에 빠집니다. "내가 잘못해서 실패했나? 아니면 그냥 운이 나빴나?"를 구분하기 어렵기 때문에, 좋은 전략을 찾기 위해 엄청난 양의 데이터 (시행착오) 가 필요합니다.

2. 해결책: "PCMDP"라는 새로운 지도

이 논문은 AI 에게 **"네가 통제할 수 있는 부분과 없는 부분을 명확히 구분해라"**라고 가르칩니다. 이를 **PCMDP (부분 제어 가능 마르코프 결정 과정)**라고 부릅니다.

• 비유: 비행기 조종사가 비행기 엔진과 조종간 (내부/통제 가능) 과 날씨 (외부/통제 불가) 를 구분해서 생각한다는 것입니다.
  • 내부 (Endogenous): 비행기 연료, 위치, 속도. (조종사가 바꿀 수 있음)
  • 외부 (Exogenous): 비, 바람, 구름. (조종사가 바꿀 수 없음, 그냥 관찰만 함)

이 두 가지를 섞어서 생각하지 않고 분리해서 생각하면 AI 는 훨씬 더 효율적으로 배울 수 있습니다.

3. 두 가지 새로운 알고리즘 (EXAVI 와 EXAQ)

저자들은 이 아이디어를 바탕으로 두 가지 새로운 학습 방법을 만들었습니다.

① EXAVI (모델 기반 학습): "예측 가능한 미래 시뮬레이션"

• 원리: AI 가 "날씨"는 이미 알고 있다고 가정하고, 오직 "날씨 변화 패턴"만 관찰해서 학습합니다.
• 비유: 조종사가 "비가 오는 날은 항상 시야가 나빠진다"는 사실은 이미 알고 있다고 칩시다. 그럼 AI 는 "비가 올 때 어떻게 비행해야 할지"만 집중해서 연습하면 됩니다. "비가 왜 오는지"를 다시 배울 필요도, "비가 오지 않게 하려고" 시도해 볼 필요도 없습니다.
• 효과: 기존 방식보다 수천 배 더 적은 데이터로 최적의 전략을 찾아냅니다.

② EXAQ (모델 없는 학습): "한 번의 경험으로 모든 경우를 학습"

• 원리: AI 가 한 번 "비"를 경험했을 때, 그 경험을 이용해 "비가 올 때의 모든 비행 상황"을 한꺼번에 업데이트합니다.
• 비유: 보통 AI 는 "비가 오면서 왼쪽으로 선회했을 때"라는 하나의 경우만 배웁니다. 하지만 이 방법은 "비가 왔으니, 왼쪽 선회뿐만 아니라 오른쪽 선회, 직진 등 모든 비행 상황에 대해 '날씨가 비일 때'의 지식을 업데이트한다"는 것입니다.
• 효과: 마치 한 번의 실험으로 모든 변수를 동시에 파악하는 것처럼, 데이터 효율이 극대화됩니다.

4. 실제 실험 결과: "택시와 주식 트레이딩"

연구팀은 이 방법을 실제 환경에 적용해 보았습니다.

• 택시 시뮬레이션: 길거리의 교통 체증 (외부 요인) 을 통제할 수 없는 상황에서 택시를 운전하게 했습니다.
  • 결과: 기존 AI 는 수천 번의 실수를 반복해야 좋은 경로를 찾았지만, 새로운 AI (EXAVI/EXAQ) 는 몇 번의 시도 만에 최적의 경로를 찾아냈습니다.
• 주식 자동 매매: 시장 가격 (외부 요인) 을 통제할 수 없는 상황에서 주식을 팔아야 했습니다.
  • 결과: 기존 AI 는 너무 급하게 주식을 다 팔거나 (공포 매도), 너무 느리게 팔았지만, 새로운 AI 는 시장 상황을 잘 파악하여 가장 수익이 나는 타이밍에 주식을 매도하는 전략을 빠르게 터득했습니다.

5. 결론: "불필요한 시도를 줄이자"

이 논문의 핵심 메시지는 **"통제할 수 없는 것에 에너지를 쓰지 마라"**입니다.

기존 AI 는 "내가 무엇을 하든 결과가 달라질까?"를 무작위로 시도하며 배웠지만, 이 새로운 방법은 **"내 행동이 결과에 영향을 주지 않는 부분은 그냥 관찰만 하고, 내 행동이 영향을 주는 부분에만 집중하자"**고 말합니다.

이처럼 현실 세계의 구조 (통제 가능 vs 통제 불가) 를 잘 이해하고 활용하면, AI 는 훨씬 더 적은 비용과 시간으로 현실적인 문제를 해결할 수 있게 됩니다. 이는 금융, 에너지 관리, 물류 등 다양한 분야에서 AI 를 실제로 쓸모 있게 만드는 중요한 첫걸음입니다.

기술 요약

이 논문은 **외생적 동역학 (Exogenous Dynamics) 을 가진 마르코프 결정 과정 (MDP)**에서의 강화 학습 (RL) 문제를 다루며, 이를 해결하기 위한 새로운 프레임워크와 알고리즘을 제안합니다. 저자들은 에이전트의 행동이 상태의 일부 변수에만 영향을 미치고, 나머지 변수는 에이전트와 무관하게 외부 요인에 의해 결정되는 실제 세계의 많은 시스템 (금융, 에너지 관리 등) 을 모델링하기 위해 **부분 제어 가능 마르코프 결정 과정 (PCMDP, Partially Controllable MDP)**을 정의했습니다.

다음은 이 논문의 기술적 요약입니다.

---

1. 문제 정의 (Problem Definition)

기존의 강화 학습 알고리즘은 일반적인 MDP 를 가정하며, 모든 상태 - 행동 쌍이 임의의 전이 분포를 가질 수 있다고 봅니다. 그러나 실제 응용 분야에서는 다음과 같은 한계가 존재합니다.

• 외생적 변수 (Exogenous Variables): 에이전트의 행동과 무관하게 확률적으로 진화하는 상태 변수들 (예: 주가, 날씨, 교통 체증).
• 내생적 변수 (Endogenous Variables): 에이전트의 행동에 의해 결정되거나 영향을 받는 상태 변수들 (예: 보유 자산, 수위, 택시 위치).
• 문제점: 표준 MDP 는 이러한 구조를 명시적으로 구분하지 않아 상태 공간의 복잡도가 불필요하게 증가하고, 에이전트가 통제할 수 없는 변수들에 대해 무의미한 탐색 (exploration) 을 수행하게 됩니다. 이는 신호 - 대 - 잡음비 (Signal-to-Noise Ratio) 를 낮추고, 최적 정책을 학습하는 데 필요한 샘플 수를 급격히 증가시킵니다.

2. 제안된 프레임워크: PCMDP

저자들은 상태 공간 $S$를 **제어 가능한 부분 ($S^\diamond$)**과 **통제 불가능한 부분 ($S^\bullet$)**으로 분해하는 PCMDP를 정의했습니다.

• 상태 분해: $S = S^\bullet \times S^\diamond$
  • $S^\bullet$ (외생적): 에이전트 행동과 무관하게 전이됨. 전이 확률 $p^\bullet_h$는 에이전트에게 미지수이나, 에이전트 행동에 의존하지 않음.
  • $S^\diamond$ (내생적): 에이전트 행동에 의해 결정됨. 전이 확률 $p^\diamond_h$는 에이전트가 완전히 알고 있다고 가정 (Assumption 1).
• 전이 함수:
  $$p_h(s_{h+1}|s_h, a_h) = p^\bullet_h(s^\bullet_{h+1}|s^\bullet_h, s^\diamond_h, a_h) \cdot p^\diamond_h(s^\diamond_{h+1}|s^\diamond_h)$$
  • 외생적 상태 $s^\bullet$의 전이는 에이전트 행동 $a_h$에 의존하지 않으며, 내생적 상태 $s^\diamond$의 전이는 에이전트 행동에 의존합니다.

3. 방법론 및 알고리즘 (Methodology & Algorithms)

이 프레임워크에 맞춰 모델 기반 (Model-based) 과 모델 프리 (Model-free) 두 가지 알고리즘을 제안했습니다. 핵심 아이디어는 외생적 동역학의 독립성을 활용하여 탐색 (exploration) 과 추정 (estimation) 의 복잡도를 줄이는 것입니다.

A. 모델 기반 접근: EXAVI (Exogenous-Aware Value Iteration)

• 개념: 기존 UCBVI (Upper Confidence Bound Value Iteration) 의 개선 버전입니다.
• 작동 원리:
  • 내생적 전이 $p^\diamond$는 이미 알려져 있으므로, 에이전트는 오직 외생적 전이 $p^\bullet$만 추정하면 됩니다.
  • 핵심 차별점: 외생적 상태는 에이전트 행동과 무관하게 자연스럽게 발생하므로, "적극적인 탐색 (Active Exploration)"이 불필요합니다. 따라서 탐색을 위한 오버시즘 (Optimism) 보너스 (Bonus term) 가 전혀 필요 없습니다.
  • 알고리즘은 관찰된 외생적 상태의 전이 데이터만을 사용하여 $p^\bullet$를 추정하고, 이를 알려진 $p^\diamond$와 결합하여 가치 반복 (Value Iteration) 을 수행합니다.

B. 모델 프리 접근: EXAQ (Exogenous-Aware Q-Learning)

• 개념: 기존 Q-Learning (QL) 의 확장 버전입니다.
• 작동 원리:
  • 전이 함수를 명시적으로 추정하지 않고 경험에서 직접 학습합니다.
  • 핵심 차별점: 일반적인 QL 은 방문한 특정 상태 - 행동 쌍 $(s, a)$에 대해서만 Q 값을 업데이트하지만, EXAQ 는 **동일한 외생적 상태 $s^\bullet$ 하에서 가능한 모든 내생적 상태 - 행동 쌍 $(s^\diamond, a)$에 대해 동시 업데이트 (Counterfactual Update)**를 수행합니다.
  • 이는 "가상적 추론 (Counterfactual Reasoning)"과 유사하게, 한 번의 외생적 관찰을 통해 해당 상황과 관련된 모든 내생적 시나리오에 대한 가치를 동시에 학습하게 하여 샘플 효율성을 극대화합니다.
  • 학습률 (Learning Rate) 은 상태 - 행동 쌍의 방문 횟수가 아닌, 외생적 상태 $s^\bullet$의 방문 횟수에 기반하여 설정됩니다.

4. 주요 기여 및 이론적 결과 (Key Contributions & Theoretical Results)

1. PCMDP 프레임워크 정립: 제어 가능/불가능 변수를 명시적으로 구분하는 새로운 MDP 변형을 정의했습니다.
2. 알고리즘 제안 및 regret bound 증명:
   • EXAVI와 EXAQ를 제안하고, 유한 시간 (Finite-horizon) 설정에서의 regret 상한을 증명했습니다.
   • Regret Bound: 기존 MDP 알고리즘의 regret 이 전체 상태 공간 크기 $S$와 행동 공간 $A$에 의존하는 반면, 제안된 알고리즘의 regret 은 외생적 상태 공간 크기 $S^\bullet$에만 의존합니다.
     • EXAVI: $\tilde{O}(H^2\sqrt{S^\bullet K} + H^3 (S^\bullet)^2)$
     • EXAQ: $\tilde{O}(\sqrt{H^5 S^\bullet K})$
     • 여기서 $S = S^\bullet \times S^\diamond$이므로, $S^\diamond$와 $A$가 크더라도 regret 에 미치는 영향이 로그 항으로만 남거나 사라집니다.
3. 정보 이론적 최적성 (Lower Bound): 외생적 상태 크기 $S^\bullet$에 대한 제곱근 ($\sqrt{S^\bullet}$) 의존성은 정보 이론적으로 피할 수 없는 하한 (Lower Bound) 임을 증명했습니다. 즉, 제안된 알고리즘이 최적의 성능을 가집니다.

5. 실험 결과 (Experimental Results)

세 가지 환경 (택시, 알고리즘 트레이딩, 엘리베이터) 에서 EXAVI/EXAQ를 기존 UCBVI/QL 및 PPO 와 비교했습니다.

• TaxiEnv (택시):
  • 결과: EXAVI 는 몇 개의 에피소드 내에서 최적 정책에 수렴한 반면, UCBVI 는 수천 에피소드가 필요했습니다.
  • 이유: UCBVI 는 전체 전이 행렬을 추정해야 하지만, EXAVI 는 알려진 내생적 동역학을 활용하여 외생적 교통 상황만 학습하면 되기 때문입니다.
• TradingEnv (알고리즘 트레이딩):
  • 결과: EXAQ 는 PPO 와 표준 QL 보다 월등히 빠른 샘플 효율성을 보였습니다. 특히 로그 스케일 그래프에서 초기 단계 (100~100 에피소드) 에서 빠르게 수렴하는 것을 확인했습니다.
  • 전략: EXAQ 는 TWAP(시간 가중 평균 가격) 전략과 PPO/QL 의 과도한 매도 (Panic Selling) 사이에서 균형을 잡은 최적의 청산 전략을 학습했습니다.
• ElevatorEnv (엘리베이터):
  • 결과: 모델 기반 및 모델 프리 모두에서 EXAVI/EXAQ 가 기존 방법론보다 훨씬 빠르게 최적 해를 찾았습니다.

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

• 샘플 효율성 극대화: 실제 세계의 많은 문제 (금융, 에너지, 물류 등) 는 통제 불가능한 외부 요인이 존재합니다. 이 논문은 이러한 구조를 명시적으로 모델링함으로써, 불필요한 탐색을 제거하고 샘플 효율성을 수백 배에서 수천 배까지 개선할 수 있음을 보였습니다.
• 이론적 엄밀성: 단순한 휴리스틱이 아닌, 엄격한 regret bound 와 하한 증명을 통해 알고리즘의 최적성을 수학적으로 입증했습니다.
• 실용적 적용: 알고리즘 트레이딩과 같은 복잡한 실세계 문제에 적용 가능함을 보여주었으며, 연속 상태 공간이나 부분 관측 문제 등으로의 확장 가능성을 제시했습니다.

요약하자면, 이 논문은 강화 학습이 통제 불가능한 환경 요인을 고려할 때, 해당 구조를 명시적으로 모델링하는 것이 학습 성능을 획기적으로 개선할 수 있음을 이론과 실험을 통해 입증한 중요한 연구입니다.