Optimal strategies in Markov decision processes with finitely additive evaluations

이 논문은 무한 시간 Markov 결정 과정에서 확산 차분 (diffuse charge) 을 통한 보상 집계 방식이 시간 가치 원칙을 만족하지 않을 경우, 유한 상태 및 행동 공간을 가진 MDP 에서 순수 전략과 확률적 전략을 포함한 최적 전략이 존재하지 않을 수 있음을 반례를 통해 증명합니다.

핵심

1. 배경: "무한한 게임"과 "점수 계산기"

상상해 보세요. 여러분은 무한히 계속되는 보드게임에 참여하고 있습니다.

• 게임 규칙: 매 턱마다 여러분은 두 가지 행동 (A 또는 B) 중 하나를 선택해야 합니다.
• 보상: 행동에 따라 매 턱마다 '점수'를 받습니다. (예: A 를 하면 1 점, B 를 하면 0 점)
• 목표: 게임이 끝날 때 (무한히 오래 지속되지만), 총점을 가장 높게 만드는 전략을 찾는 것입니다.

여기서 중요한 것은 '총점'을 어떻게 계산하느냐입니다.
보통은 "지금 당장 받은 점수"가 중요하거나, "앞으로 받을 점수"를 할인해서 계산합니다. 하지만 이 논문에서는 아주 특별한 **'점수 계산기 (가중치)'**를 사용합니다. 이 계산기는 **"시간의 흐름에 따라 점수의 중요도가 변하지 않고, 모든 시점을 균등하게 고려하지만, 특정 시점 하나하나의 점수는 0 으로 취급한다"**는 이상한 규칙을 따릅니다.

수학자들은 이를 **'확산된 측도 (Diffuse Charge)'**라고 부르는데, 쉽게 말해 **"무한히 긴 시간 전체를 한 번에 훑어보아 평균을 내는 방식"**이라고 생각하면 됩니다.

---

2. 기존 통념: "좋은 계산기가 있으면 항상 최적 전략이 있다"

이전 연구 (Neyman, 2023) 에 따르면, 만약 이 '점수 계산기'가 **"시간 가치의 원칙"**을 따른다면, 플레이어는 반드시 최적의 전략을 가질 수 있다고 했습니다.

• 비유: 계산기가 "지금 당장 받은 점수도 중요하고, 나중에 받은 점수도 중요하게 여기되, 시간이 지나도 가치가 떨어지지 않는다"고 판단한다면, 플레이어는 "A 를 계속 하라"거나 "B 를 계속 하라"는 명확한 답을 찾을 수 있습니다.

하지만 논문 저자들은 의문을 품었습니다.

"만약 이 계산기가 아주 기괴하고 이상한 규칙을 가진다면? 그래도 항상 최적의 답이 있을까?"

---

3. 이 논문의 핵심 발견: "완벽한 답은 존재하지 않는다"

저자들은 **"아니요, 최적의 답이 없는 경우가 있다"**는 것을 증명했습니다. 이를 위해 아주 교묘하게 설계된 **'짝수 vs 홀수 게임'**을 만들었습니다.

🎮 게임 상황: "지금 vs 다음"의 딜레마

게임판에는 두 가지 행동이 있습니다.

• 행동 T (Top): 지금 1 점, 다음 턱 0 점.
• 행동 B (Bottom): 지금 0 점, 다음 턱 1 점.

여러분은 매 턱마다 "지금 1 점을 먹을지, 다음 턱 1 점을 먹을지" 선택해야 합니다.

🧠 교묘한 점수 계산기 (µ)

이 게임의 점수 계산기는 두 가지 성격을 동시에 가집니다.

1. 성격 A (홀수 턱 중시): 홀수 턱 (1, 3, 5...) 에 받은 점수를 아주 중요하게 여깁니다.
2. 성격 B (짝수 턱 중시): 짝수 턱 (2, 4, 6...) 에 받은 점수를 아주 중요하게 여깁니다.

이 계산기는 **"홀수 턱과 짝수 턱을 모두 50% 씩 중요하게 여기지만, 그중에서도 아주 특이한 규칙"**을 적용합니다.

🤯 왜 최적 전략이 없을까?

여러분이 이 게임에서 최선의 전략을 찾으려 노력해 보세요.

• 전략 1: T 를 계속 선택하자 (지금 1 점, 다음 0 점)

  • 홀수 턱에서는 1 점을 받아서 성격 A 에게는 좋습니다.
  • 하지만 짝수 턱에서는 0 점만 받아서 성격 B 에게는 치명적입니다.
  • 결과: 점수가 0.5 점 정도 됩니다.

• 전략 2: B 를 계속 선택하자 (지금 0 점, 다음 1 점)

  • 짝수 턱에서는 1 점을 받아서 성격 B 에게는 좋습니다.
  • 하지만 홀수 턱에서는 0 점만 받아서 성격 A 에게는 치명적입니다.
  • 결과: 점수가 0.5 점 정도 됩니다.

• 전략 3: T 와 B 를 번갈아 가며 선택하자 (1, 0, 1, 0...)

  • 홀수 턱과 짝수 턱 모두 1 점을 받습니다.
  • 하지만! 이 게임의 계산기는 아주 교묘하게 설계되어 있습니다. **"어떤 전략을 선택하든, 계산기가 원하는 '완벽한 1 점'을 달성할 수 없다"**는 것입니다.
  • 만약 여러분이 "지금 1 점"을 더 중요하게 여겨 T 를 자주 선택하면, 계산기의 다른 부분이 "그럼 너는 다음 턱을 망쳤네?"라고 점수를 깎아냅니다.
  • 반대로 "다음 1 점"을 위해 B 를 자주 선택하면, 또 다른 부분이 "그럼 지금 턱을 망쳤네?"라고 깎아냅니다.

💡 핵심 비유: "이동하는 목표선"

이 게임은 마치 달리는 화살표를 쫓는 것과 같습니다.

• 여러분이 "지금"을 잘 맞추려고 하면, 계산기는 "다음"을 더 중요하게 여깁니다.
• 여러분이 "다음"을 잘 맞추려고 하면, 계산기는 "지금"을 더 중요하게 여깁니다.
• 결국: 여러분이 어떤 전략을 선택하든, 계산기는 "아직 완벽하지 않아. 조금만 더 노력해 봐"라고 말하며 최적의 점수 (1 점) 에 도달하는 순간을 영원히 미루어 버립니다.

그래서 이 게임에서는 "무조건 이기는 전략"이 존재하지 않습니다. 확률적으로 섞어서 하든, 정해진 순서로 하든, 항상 "조금 더 좋은 전략"이 존재하기 때문에, 완벽한 최적 해답은 없습니다.

---

4. 결론 및 시사점

이 논문은 수학적으로 매우 정교한 증명을 통해 다음과 같은 사실을 밝혔습니다.

1. 우리가 생각하는 '최적'은 항상 존재하지 않는다: 우리가 일상에서 "가장 좋은 방법"을 찾으려 할 때, 환경 (점수 계산기) 이 너무 복잡하고 모순된 규칙을 가진다면, 완벽한 해답은 아예 존재하지 않을 수 있다는 것입니다.
2. 무작위성도 소용없다: 단순히 "랜덤으로 선택하자"고 해서 해결되지 않습니다. 계산기의 규칙이 너무 정교하게 설계되어 있어, 확률적 전략조차도 완벽하게 이길 수 없습니다.
3. 실생활의 교훈:
   • 우리가 인생에서 "지금의 행복"과 "미래의 행복" 사이에서 고민할 때, 만약 두 가치를 동시에 극대화하는 기준이 모순된다면, 완벽한 선택은 불가능할 수 있습니다.
   • 우리는 "최고의 선택"을 찾으려 애쓰지만, 사실은 "충분히 좋은 선택"을 하고 만족해야 할 수도 있다는 것을 수학적으로 보여줍니다.

한 줄 요약:

"아주 교묘하게 설계된 세상에서는, 어떤 전략을 쓰더라도 '완벽한 승리'를 보장받을 수 없으며, 우리는 항상 '조금 더 나은 선택'을 찾아 헤매게 될 뿐이다."

기술 요약

1. 문제 정의 (Problem Statement)

이 논문은 **무한 시간 범위 (infinite-horizon)**를 가진 마르코프 결정 과정 (MDP) 을 연구합니다. 기존의 MDP 연구는 주로 할인된 합 (discounted sum) 이나 장기 평균 보상 (long-term average reward) 을 기준으로 최적 전략을 찾는 데 초점을 맞추었습니다.

• 핵심 설정: 의사결정자는 각 단계에서 얻는 기대 보상의 무한한 흐름을 **확산 전하 (diffuse charge)**라고 불리는 유한 가산 확률 측도 (finitely additive probability measure) 를 통해 하나의 실수 (보상, payoff) 로 집계 (aggregation) 합니다.
• 확산 전하 (Diffuse Charge): 자연수 집합 $\mathbb{N}$ 위에 정의된 유한 가산 확률 측도 $\mu$로, 모든 단일점 $\{n\}$에 대해 $\mu(\{n\}) = 0$인 것을 의미합니다. 즉, 특정 시점 하나하나에 무게를 두지 않고 전체 흐름을 평가합니다.
• 연구 질문: Neyman [2023] 은 "시간 가치의 원칙 (time value of money principle)"을 만족하는 전하에 대해서는 항상 순수 최적 전략 (pure optimal strategy) 이 존재함을 보였습니다. 하지만 이 원칙을 만족하지 않는 일반적인 확산 전하에 대해서도 MDP 에서 항상 최적 전략 (순수 또는 무작위화 전략 포함) 이 존재하는가? 라는 질문이 제기되었습니다.

2. 방법론 (Methodology)

논문의 방법론은 다음과 같은 수학적 도구와 구성을 기반으로 합니다.

• 모델 설정:
  • 유한한 상태 공간 ($S$) 과 행동 공간 ($A$) 을 가진 MDP.
  • 보상 함수 $r(s, a)$와 전이 확률 $p(s' | s, a)$.
  • 전략 $\sigma$에 의해 유도된 기대 보상 시퀀스 $\{E_\sigma[r_t]\}_{t \in \mathbb{N}}$를 확산 전하 $\mu$에 대해 적분하여 보상을 정의합니다:
    $$u_\mu(\sigma) = \int_{t \in \mathbb{N}} E_\sigma[r_t] \, \mu(dt)$$
• 수학적 배경:
  • ZFC 공리계를 가정합니다.
  • 전하 (Charge) 의 위상: 전하들의 집합 $\Delta_f$에 **점별 수렴 위상 (topology of pointwise convergence)**을 부여합니다. 이 공간은 콤팩트 (compact) 이지만 거리화 가능 (metrizable) 하지는 않습니다.
  • Neyman [2023] 의 결과 재해석: 시간 가치 원칙을 만족하는 전하들은 "환자한 평가 (patient valuation)"와 대응되며, 이 경우 순수 정상 전략 (pure stationary strategy) 이 존재함을 상기시킵니다.
• 반례 구성 (Counterexample Construction):
  • 최적 전략이 존재하지 않는 구체적인 MDP 를 설계하기 위해 매우 정교하게 구성된 확산 전하를 도입합니다.
  • 이 전하는 두 가지 서로 다른 성질 (하나는 홀수 단계에 집중, 다른 하나는 짝수 단계의 특정 부분집합에 집중) 을 가진 전하들의 합으로 구성됩니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

논문의 가장 중요한 기여는 **최적 전략의 부재 (Non-existence of optimal strategies)**를 증명하는 반례를 제시한 것입니다.

A. 주요 정리 (Theorem 3)

• 결과: 결정론적 전이 (deterministic transitions) 를 가진 특정 MDP 와 정교하게 설계된 확산 전하 $\mu$가 존재하며, 이 경우 의사결정자는 순수 전략이든 무작위화 전략이든 최적 전략을 전혀 갖지 않습니다.
• MDP 구성 ("Even-or-Odd" MDP):
  • 상태: $\{1, 2, 3\}$. 초기 상태는 1.
  • 행동: 상태 1 에서 $T$(위) 또는 $B$(아래) 선택.
    • $T$: 즉시 보상 1, 다음 상태 2 (보상 0).
    • $B$: 즉시 보상 0, 다음 상태 3 (보상 1).
  • 상태 2 와 3 에서 상태 1 로 자동 복귀.
  • 핵심 메커니즘: 홀수 단계에서 의사결정자는 "지금 1 을 받고 다음에 0"($T$) 또는 "지금 0 을 받고 다음에 1"($B$) 사이에서 선택해야 합니다.
• 전하 $\mu$의 구성:
  • $\mu = \frac{1}{2}\mu_0 + \frac{1}{2}\mu^*$.
  • $\mu_0$: 홀수 단계 집합에 집중된 전하.
  • $\mu^*$: 점별 수렴 위상에서 수열 $\{\mu_n\}$의 축적점 (accumulation point) 으로 구성된 전하. $\mu_n$은 $2^n$의 배수 집합에 집중되지만,$\mu^*$는 모든$E_n$ 집합에 대해 측도 1 을 가집니다.
• 부재 증명 논리:
  1. 최대 가치 (Value) 는 1 임 (Claim 1): 임의의 $\epsilon > 0$에 대해 보상이 $1-\epsilon$에 근접하는 전략$\sigma_n$을 구성할 수 있음.
  2. 어떤 전략도 1 을 달성할 수 없음 (Claim 2): 만약 어떤 전략 $\sigma$가 보상이 1 이라면, 기대 보상이 $1/2$보다 큰 단계들의 집합$W$에 대해$\mu(W)=1$이어야 함.
     • 그러나 $W$가 $\mu_0$에 대해 측도 1 이려면 $T$를 거의 항상 선택해야 하고, $\mu^*$에 대해 측도 1 이려면 $B$를 일정 빈도로 선택해야 하는 모순이 발생함.
     • 구체적으로, $W$가 $\mu_n$에 대해 양의 측도를 가지면 $\mu_0(W) < 1$이 되고, 모든 $\mu_n$에 대해 0 이면 $\mu^*(W)=0$이 되어 모순이 발생함.
  • 결론: 상한 (supremum) 은 1 이지만, 이를 달성하는 전략은 존재하지 않음.

B. 추가적 통찰 (Concluding Remarks)

1. 정상 전략의 부재: 특정 전하 하에서는 순수 최적 전략이 존재할지라도, 그 중 **정상 전략 (stationary strategy)**은 최적일 수 없음 (Example 4).
2. 적분 순서: 보상 정의식에서 기대값과 전하 적분의 순서를 바꾸는 것은 항상 정의되지 않을 수 있음 (측도론적 문제).
3. 비확산 전하 (Non-diffuse charges):
   • 전하가 가산 가산적 (countably additive) 인 경우 (할인 모델 등) 는 최적 전략이 항상 존재함.
   • 하지만 가산 가산적 부분과 확산 부분의 혼합 (convex combination) 인 경우, Example 5 에서 보듯 최적 전략이 존재하지 않을 수 있음.

4. 의의 (Significance)

1. 이론적 한계의 규명: 기존 MDP 이론 (특히 Neyman [2023] 의 결과) 이 "시간 가치 원칙"이라는 조건 하에 최적 전략 존재를 보장하지만, 이 조건을 벗어난 일반적인 유한 가산적 평가 체계에서는 최적 전략이 존재하지 않을 수 있음을 최초로 명확히 증명했습니다.
2. 전략의 복잡성: 최적 전략이 존재하지 않는다는 결과는 단순히 "계산하기 어렵다"는 문제가 아니라, 전략 공간 자체가 최적점을 포함하지 않는 (open set-like) 구조일 수 있음을 시사합니다. 이는 무한 시간 범위에서의 의사결정 이론에 중요한 반례를 제공합니다.
3. 적용 가능성: 확산 전하는 장기 평균 보상을 일반화한 개념으로, 경제학, 게임 이론, 인공지능 (강화학습) 에서 장기적인 불확실한 환경 하의 의사결정 모델링 시, 최적 해가 존재하지 않는 상황을 예측하고 대안적 접근법 (예: $\epsilon$-optimal 전략) 을 모색하는 데 기초를 제공합니다.

요약

이 논문은 유한 가산적 측도를 사용하여 보상을 평가하는 MDP 에서, 특정 조건 (시간 가치 원칙) 을 만족하지 않는 전하를 사용할 경우 최적 전략이 아예 존재하지 않을 수 있음을 정교한 반례를 통해 증명했습니다. 이는 무한 시간 범위 의사결정 이론에서 최적성 (optimality) 의 존재가 보장되지 않는 중요한 경계 조건을 제시합니다.