Apprenticeship learning with prior beliefs using inverse optimization

이 논문은 마르코프 결정 과정에서 역강화학습과 역최적화 간의 관계를 재조명하고, 비용 함수의 구조에 대한 사전 믿음을 정규화 항으로 도입하여 역강화학습의 비제약적 문제를 해결하고 확률적 미러 강하법을 통해 수렴성을 보장하는 새로운 학습 프레임워크를 제안합니다.

핵심

🍳 비유: 요리 레시피를 배우는 상황

이 논문의 핵심을 요리사 (전문가) 의 레시피를 배우는 상황으로 상상해 보세요.

1. 문제 상황 (기존 방식의 한계):

   • 당신은 훌륭한 요리사 (전문가) 가 만든 요리를 맛보고, "이 요리를 어떻게 만들었지?"라고 궁금해합니다.
   • 하지만 요리사는 "소금 1g, 설탕 2g" 같은 정확한 레시피를 알려주지 않습니다. 그저 "맛있게 먹어봐"라고만 합니다.
   • 기존 연구들은 이 요리사가 완벽한 레시피를 가지고 있다고 가정하고 레시피를 추측했습니다. 하지만 현실에서는 요리사도 실수를 하거나, "오늘은 소금이 좀 부족했어"라고 생각할 수도 있습니다.
   • 또한, 레시피를 유추하려면 "소금, 설탕, 후추" 같은 기존에 정해진 재료들 (특징) 만 쓸 수 있다고 가정하는 경우가 많았습니다. 만약 요리사가 "신비한 향신료 X"를 썼는데, 우리가 그걸 모르면 레시피를 맞출 수 없습니다.

2. 이 논문이 제안하는 새로운 방식 (우리의 방법):

   • 가상 레시피 (Prior Belief): 우리는 요리사의 행동을 보기 전에, "아마도 이 요리는 소금과 설탕의 비율이 1:2 일 거야"라고 우리의 추측 (사전 믿음) 을 가지고 시작합니다. 이 추측이 100% 맞을 필요는 없습니다.
   • 실수하는 요리사 (Suboptimal Expert): 우리는 요리사가 완벽하지 않을 수 있다고 인정합니다. 그가 만든 요리가 조금 싱거울 수도 있죠.
   • 밸런스 잡기 (Regularization): 우리는 두 가지 정보를 섞습니다.
     1. 요리사가 실제로 한 행동 (데이터).
     2. 우리가 가진 추측 (가상 레시피).
   • 이 두 가지를 적절히 섞어서 "가장 그럴듯한 레시피" 를 찾아냅니다. 만약 요리사가 실수했다면, 우리의 추측이 그 실수를 보정해 줍니다.

---

🧩 핵심 개념 3 가지

1. "왜?"를 찾아내는 과정 (역강화학습 & 역최적화)

• 기존: "이 요리사가 이 행동을 한 이유는 뭘까?"라고 묻고, 정답이 하나만 있다고 믿었습니다.
• 이 논문: "이 요리사의 행동은 여러 가지 이유 (레시피) 로 설명될 수 있어. 그중에서 우리가 가진 추측과 가장 비슷하면서도, 요리사의 행동을 가장 잘 설명하는 레시피를 찾아보자"라고 접근합니다.
• 비유: 요리사가 "소금 1g"을 넣었는데, 우리가 "아마도 1.2g 이었을 거야"라고 추측했다면, 그 사이 어딘가에서 가장 논리적인 값을 찾아내는 것입니다.

2. "실수하는 전문가"를 위한 안전장치 (정규화)

• 전문가가 완벽하지 않을 때, 그의 행동만 보고 레시피를 만들면 엉망이 될 수 있습니다.
• 이 논문은 $\alpha$(알파) 라는 조절 장치를 도입했습니다.
  • $\alpha$가 작을 때: 요리사의 행동을 100% 따라 합니다. (요리사가 실수하면 우리도 실수합니다.)
  • $\alpha$가 클 때: 우리의 추측 (가상 레시피) 을 더 믿습니다. 요리사의 실수를 보정해 줍니다.
• 효과: 요리사가 실수하더라도, 우리가 가진 지식을 섞어주면 요리사보다 더 맛있는 요리 (더 좋은 정책) 를 만들어낼 수 있습니다.

3. "기존 재료"에 얽매이지 않기 (자유로운 탐색)

• 기존 연구들은 "레시피는 소금, 설탕, 후추 세 가지의 조합으로만 만들어져야 해"라고 제한했습니다.
• 이 논문은 "아니야, 레시피는 어떤 조합이든 될 수 있어. 우리가 가진 추측을 기준으로 찾아보자" 라고 합니다.
• 비유: 요리사가 "신비한 향신료 X"를 썼을 때, 기존 방식은 그걸 못 찾지만, 이 방식은 그 향신료의 존재를 자연스럽게 찾아낼 수 있습니다.

---

🚀 이 방법이 왜 중요한가요? (실제 효과)

논문의 실험 결과 (재고 관리 문제, 미로 찾기 게임 등) 에서 다음과 같은 놀라운 일이 일어났습니다.

1. 실수하는 전문가를 이기다: 전문가가 실수해서 엉뚱한 행동을 하더라도, 우리의 추측 (사전 정보) 을 섞으면 전문가보다 더 똑똑한 행동을 할 수 있는 로봇 (학습된 정책) 을 만들 수 있었습니다.
2. 정확한 레시피 복원: 전문가가 어떤 재료를 얼마나 썼는지 정확히 모를 때, 우리의 추측을 통해 진짜 레시피에 가장 가까운 값을 찾아냈습니다.
3. 유연함: 복잡한 환경 (큰 미로) 에서도, 미리 정해진 재료 목록이 없어도 잘 작동했습니다.

📝 한 줄 요약

"전문가가 완벽하지 않을지라도, 우리가 가진 '추측'을 적절히 섞어주면, 전문가보다 더 똑똑하고 정확한 행동 방식을 배울 수 있다."

이 연구는 인공지능이 인간의 행동을 모방할 때, 단순히 따라 하는 것을 넘어 인간의 실수를 보정하고 더 나은 목표를 찾아내는 방법을 제시했다는 점에서 매우 의미 있습니다.

기술 요약

이 논문은 마르코프 결정 과정 (MDP) 에서 역강화학습 (IRL), 역최적화 (IO), 그리고 견습 학습 (Apprenticeship Learning, AL) 간의 관계를 재조명하고, 비용 함수의 구조에 대한 **사전 신념 (prior beliefs)**을 통합한 새로운 프레임워크를 제안합니다. 특히 전문가가 최적 (optimal) 이 아닌 **비최적 (suboptimal)**인 상황을 가정하여, 역최적화 기법을 활용한 정규화된 학습 문제를 제시하고 이를 해결하기 위한 확률적 미러 강하 (Stochastic Mirror Descent, SMD) 알고리즘을 개발했습니다.

다음은 논문의 상세한 기술적 요약입니다.

---

1. 문제 정의 (Problem Statement)

• 배경: 강화학습 (RL) 은 보통 비용 함수가 알려져 있다고 가정하지만, 실제 환경에서는 비용 함수를 설계하기 어렵고 잘못된 설계는 에이전트의 행동에 치명적인 영향을 미칠 수 있습니다.
• 역강화학습 (IRL) 의 한계: IRL 은 전문가의 행동을 관찰하여 그 행동을 최적화하는 비용 함수를 추론하는 문제입니다. 그러나 IRL 문제는 본질적으로 **잘못된 문제 (ill-posed)**입니다. 즉, 하나의 전문가 행동에 대해 여러 개의 비용 함수가 존재할 수 있기 때문입니다.
• 기존 접근법의 제약: 기존의 견습 학습 (AL) 은 비용 함수가 미리 정의된 기저 함수들의 볼록 결합 (convex hull) 에 속한다고 가정합니다. 이는 특징 공학 (feature engineering) 이 어렵고, 전문가가 최적 행동을 하지 않는 (suboptimal) 경우를 다루기 어렵습니다.
• 본 논문이 해결하려는 핵심 문제:
  1. 비용 함수의 구조에 대한 **사전 정보 (proxy cost vector $\hat{c}$)**를如何利用하여 IRL 의 ill-posed 성을 완화할 것인가?
  2. 전문가가 최적 행동을 하지 않는 **비최적 전문가 (suboptimal expert)**의 행동으로부터 유의미한 비용 함수와 정책을 학습할 수 있는가?

2. 방법론 (Methodology)

2.1 역최적화 관점에서의 프레임워크 재정의

저자는 IRL 문제를 역최적화 (Inverse Optimization, IO) 의 관점에서 재해석합니다.

• IRL-IO: 전문가의 정책 $\pi_E$가 최적임을 가정할 때, 전문가의 행동과 일치하는 비용 함수 집합 (inverse-feasible set, $\Theta_{inv}$) 을 정의합니다.
• 사전 신념 통합 (IRL-IO$\hat{c}$): $\Theta_{inv}$ 내에서 사전 비용 벡터 $\hat{c}$와 가장 가까운 비용 함수를 찾는 문제를 설정합니다. 이는 $\hat{c}$를 $\Theta_{inv}$로 투영하는 문제와 동일합니다.
• 비최적 전문가 대응 (IO-AL$\alpha$): 전문가가 최적이지 않을 경우, 상보적 여유 조건 (complementary slackness) 을 완화합니다. 이를 위해 **정규화 항 (regularization term)**을 도입하여 다음과 같은 문제를 정의합니다:
  $$\min_{c, u} \alpha \|c - \hat{c}\|^2_2 + \langle \mu_{\pi_E}, c - T_\gamma^\top u \rangle$$
  여기서 $\alpha$는 사전 신념 ($\hat{c}$) 과 전문가의 행동 ($\mu_{\pi_E}$) 사이의 균형을 조절하는 파라미터입니다.

2.2 Min-Max 형식화 및 알고리즘

• 라그랑주 듀얼리티 활용: 위 문제를 제약 조건이 없는 볼록 - 오목 Min-Max 문제로 변환합니다.
  $$\min_{(c, u) \in \mathcal{B}} \max_{\mu \in \Delta} \left( \alpha \|c - \hat{c}\|^2_2 + \langle \mu_{\pi_E} - \mu, c - T_\gamma^\top u \rangle \right)$$
  이는 기존 Kamoutsi et al. (2021) 의 AL 공식화를 정규화 항이 추가된 일반화된 형태로 확장한 것입니다.
• SMD-RLfD 알고리즘:
  • Stochastic Mirror Descent (SMD): Jin & Sidford (2020) 의 MDP 해결 알고리즘을 본 문제에 적응화했습니다.
  • Gradient Estimators: 전이 확률과 전문가의 점유 측정 (occupancy measure) 에 대한 오라클 (oracle) 을 사용하여 무편향 (unbiased) 그라디언트 추정자를 설계했습니다.
  • 수렴성: 제안된 알고리즘이 $\epsilon$-근사 해를 찾기 위해 필요한 반복 횟수에 대한 이론적 상한을 증명했습니다.

3. 주요 기여 (Key Contributions)

1. IRL 과 AL 의 통합적 관점: 역최적화 (IO) 프레임워크를 통해 IRL 과 AL 을 통합적으로 설명하고, 기존 AL 공식화 (Kamoutsi et al., 2021) 가 본 프레임워크의 특수한 경우 (정규화 항이 0 인 경우) 임을 증명했습니다.
2. 비최적 전문가를 위한 새로운 공식화 (IO-AL$\alpha$): 전문가가 최적 행동을 하지 않는 상황을 가정하고, 사전 신념을 활용한 정규화 항을 도입하여 ill-posed 문제를 해결하는 새로운 문제를 제안했습니다.
3. 알고리즘 및 이론적 보장: SMD 기반의 SMD-RLfD 알고리즘을 제안하고, 이 알고리즘이 생성하는 해와 최적 해 사이의 관계를 이론적으로 규명했습니다.
4. 정규화의 역할 규명: 수치 실험을 통해 정규화 파라미터 $\alpha$가 비용 함수 학습의 정확도와 정책의 성능에 결정적인 역할을 함을 입증했습니다.

4. 실험 결과 (Numerical Experiments)

두 가지 시나리오 (단일 제품 재고 관리, Gridworld) 를 통해 실험을 수행했습니다.

• 재고 관리 문제 (Inventory Control):

  • 사전 신념 오차 (Misspecification): $\hat{c}$가 실제 비용과 다를 때, $\alpha$를 조절하면 학습된 비용 벡터가 실제 값에 얼마나 근접하는지 분석했습니다.
  • 비최적 전문가: 전문가가 비최적일 때, 올바른 사전 신념 ($\hat{c}$) 을 사용하면 $\alpha$가 증가함에 따라 학습된 비용 벡터와 정책이 실제 최적 값에 더 가까워짐을 확인했습니다.
  • 볼록 껍질 (Convex Hull) vs. 박스 (Box): 기존 방법 (볼록 껍질 가정) 과 비교 시, 제안된 방법 (일반적인 볼록 클래스) 은 차원이 커질수록 더 우수한 성능을 보였습니다.

• Gridworld 문제:

  • 고차원 환경: 특징 공학이 어려운 고차원 환경에서 제안된 방법의 유연성을 입증했습니다.
  • 정규화의 영향: $\alpha$가 클수록 학습된 비용 벡터가 실제 환경 구조 (장애물, 목표 등) 를 더 잘 반영하지만, 너무 크면 학습 데이터에 없는 영역의 비용을 무시할 수 있음을 보여주었습니다.
  • 수렴 속도: $\alpha$가 클수록 비용 벡터 $c$의 수렴은 빨라지지만, 듀얼리티 갭 (duality gap) 의 수렴은 느려지는 트레이드오프가 관찰되었습니다.

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

• 이론적 통합: IRL, AL, IO 를 하나의 통일된 수학적 프레임워크로 통합하여, 기존 AL 의 제약 (기저 함수 필요, 전문가 최적성 가정) 을 완화했습니다.
• 실용적 가치: 실제 세계에서는 전문가가 항상 최적의 행동을 하지 않으며, 정확한 비용 함수를 알기 어렵습니다. 이 논문은 **사전 지식 (proxy cost)**과 비최적 데이터를 결합하여 더 강건한 (robust) 정책을 학습할 수 있는 방법을 제공합니다.
• 정규화의 중요성: 역강화학습의 ill-posed 성을 해결하고, 학습된 비용 함수가 실제 환경과 일치하도록 유도하는 데 정규화 항이 필수적임을 강조했습니다.

결론적으로, 이 연구는 역최적화 도구를 활용하여 사전 신념을 통합한 새로운 견습 학습 프레임워크를 제시함으로써, 불완전한 전문가 데이터와 불확실한 환경 하에서도 효과적인 의사결정 정책을 학습할 수 있는 이론적, 실증적 기반을 마련했습니다.