Relating Reinforcement Learning to Dynamic Programming-Based Planning

이 논문은 최적 계획과 강화 학습 간의 간극을 해소하기 위해 강화 학습의 결정론적 변형을 개발하고, 비용 최소화 및 무한 시간 범위 조건 하에서 가치 반복 및 다익스트라 알고리즘과의 성능을 비교 분석하며, 할인 요인이 목표 달성에 미치는 영향과 진정한 비용 (truecost) 최적화의 중요성을 수학적으로 규명합니다.

핵심

1. 두 가지 다른 접근법: "지도 있는 여행" vs "실수하며 배우기"

이 논문의 핵심은 두 가지 방식의 차이를 명확히 하고, 이를 하나로 통합하려는 시도입니다.

• 전통적인 계획 (Planning): "완벽한 지도를 가진 여행가"

  • 상황: 로봇이 미로를 통과해야 한다고 칩시다. 전통적인 계획 알고리즘 (예: Dijkstra, A*) 은 미로의 완벽한 지도를 처음부터 가지고 있습니다.
  • 방식: 지도를 펼쳐놓고 "여기서 저기까지 가는 가장 짧은 길"을 계산기처럼 정확하게 계산합니다.
  • 목표: 비용 (Cost) 최소화. 예를 들어, "가장 적은 연료로", "가장 짧은 시간"에 도착하는 길을 찾습니다.
  • 특징: 목표에 도달하면 즉시 멈춥니다. (예: 목적지에 도착하면 여행 종료)

• 강화 학습 (RL): "실수하며 배우는 탐험가"

  • 상황: 로봇은 지도가 없습니다. 오직 "시도하고, 실수하고, 보상 (Reward) 을 받으며" 배웁니다.
  • 방식: 무작위로 움직이다가 좋은 결과를 얻으면 "아, 이 방향이 좋구나!"라고 기억합니다. (Q-learning 등)
  • 목표: 보상 (Reward) 최대화. "맛있는 간식을 많이 얻는 길"을 찾습니다.
  • 문제점: 미래의 보상을 현재보다 덜 중요하게 여기기 위해 **'할인율 (Discounting)'**이라는 장치를 씁니다. 마치 "내일 받을 1 만 원보다 오늘 받는 1 만 원이 더 소중하다"는 생각입니다.

2. 이 논문이 찾아낸 중요한 통찰들

저자들은 이 두 방식을 비교하며 세 가지 중요한 사실을 발견했습니다.

① "비용 최소화"와 "보상 최대화"는 사실 같은 말입니다.

• 비유: "가장 적은 돈을 쓰며 여행하기 (비용 최소화)"와 "가장 많은 보상을 받으며 여행하기 (보상 최대화)"는 사실 동전의 앞뒷면과 같습니다.
• 해석: 수학적으로 보면, 비용을 음수 (-) 로 바꾸고 최소화하는 것과, 보상을 양수로 두고 최대화하는 것은 완전히 같은 최적의 길을 찾아냅니다. 하지만 AI 연구자들은 종종 보상을 인위적으로 조작 (Reward Shaping) 해서 로봇이 원하는 대로 행동하게 만드는데, 이는 비효율적일 수 있습니다.

② "할인율 (Discounting)"의 위험성: "미래를 무시하는 함정"

• 비유: 할인율이 높은 사람은 "내일 받을 큰 상금보다 오늘 받을 작은 간식을 선택"합니다.
• 위험: 로봇이 목표 (예: 출구) 에 가려면 잠시 돌아가야 할 때가 있습니다. 하지만 할인율이 높으면 로봇은 "지금 당장 돌아가는 건 손해다"라고 생각해서 **목적지에 도달하지 못하고 같은 곳을 맴도는 함정 (Cycle)**에 빠질 수 있습니다.
• 결론: 목표가 명확한 로봇 공학에서는 **할인율을 쓰지 않는 것 (True Cost)**이 훨씬 안전하고 정확합니다.

③ "한 번의 여행"과 "무한한 반복"의 차이

• 비유:
  • 계획 (Planning): "한 번만 미로를 빠져나가면 끝!" (단일 에피소드)
  • RL: "매일 미로를 빠져나와서 다시 시작하고, 그 과정을 반복해 실력을 늘려라!" (무한 에피소드)
• 통찰: 두 방식은 수학적으로 조건만 맞으면 같은 결과를 낼 수 있습니다. 하지만 RL 에서 무한 반복을 시킬 때, 로봇이 "출구에 도착하면 다시 시작점 (초기 위치) 으로 순간이동"한다고 가정하면, 전통적인 계획 방식과 동일한 결과를 얻을 수 있습니다.

3. 실험 결과: 누가 더 빠르고 똑똑할까?

저자들은 다양한 미로 (그리드) 에서 두 방법을 비교 실험했습니다.

• 지도가 있을 때 (확정적 환경):

  • 전통적 계획 (Dijkstra 등): 압도적으로 빠릅니다. 지도를 보고 바로 계산하니까요.
  • 강화 학습: 지도가 없으므로 실수하며 길을 찾아야 해서 훨씬 느립니다. 특히 무작위 탐색 (Exploration) 을 많이 할수록 시간이 더 걸립니다.
  • 교훈: 로봇이 환경을 이미 알고 있다면, 굳이 강화 학습을 쓸 필요가 없습니다. 전통적인 계획 알고리즘이 훨씬 효율적입니다.

• 지도가 없을 때 (확률적/불확실한 환경):

  • 로봇이 움직일 때 바람에 밀리거나 바퀴가 미끄러지는 등 불확실성이 있다면, 강화 학습이 유용합니다.
  • 하지만 이때도 **학습률 (Learning Rate)**이라는 설정을 잘 조절해야 합니다. 너무 빨리 배우려 하면 (학습률 높음) 실수를 반복하고, 너무 천천히 배우면 (학습률 낮음) 시간이 너무 오래 걸립니다.

4. 결론: 무엇을 배워야 할까?

이 논문은 우리에게 다음과 같은 교훈을 줍니다.

1. 진짜 비용 (True Cost) 을 쓰자: 로봇이 물리적으로 움직이는 문제라면, 인위적인 '보상'을 조작하기보다 실제 소모되는 시간, 에너지, 비용을 그대로 계산하는 것이 더 안전하고 정확합니다.
2. 할인율은 조심하자: 목표가 명확한 문제에서는 미래를 할인하지 말고, 목표에 도달할 때까지의 총비용을 계산하는 것이 좋습니다. 그래야 로봇이 함정에 빠지지 않습니다.
3. 도구를 올바르게 선택하자:
   • 환경을 정확히 알고 있다면? → **전통적인 계획 알고리즘 (Dijkstra 등)**을 쓰세요. (가장 빠름)
   • 환경을 모르고, 불확실성이 많다면? → 강화 학습을 쓰되, 학습률과 탐험 (Exploration) 비율을 잘 조절해야 합니다.

한 줄 요약:

"로봇이 미로를 통과할 때, 지도가 있다면 계산기로 바로 길을 찾고, 지도가 없다면 실수하며 배우는 학생처럼 가르쳐야 합니다. 하지만 학생을 가르칠 때 '내일 받을 점수'를 너무 깎아주지 (할인율) 않도록 주의하고, 진짜로 필요한 '에너지 (비용)'를 기준으로 가르쳐야 합니다."

기술 요약

이 논문은 **강화 학습 (Reinforcement Learning, RL)**과 동적 계획법 (Dynamic Programming, DP) 기반의 최적 계획 (Optimal Planning) 사이의 간극을 메우기 위해 수행된 연구입니다. 저자들은 두 분야가 모두 벨만 (Bellman) 의 최적성 원리에 기반하고 있음에도 불구하고, 문제 설정 (결정론적 vs 확률론적), 목적 함수 (비용 최소화 vs 보상 최대화), 그리고 수렴 방식 등에서 큰 차이가 있어 서로의 관계를 명확히 이해하기 어렵다고 지적합니다.

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

---

1. 문제 정의 (Problem)

기존의 계획 (Planning) 알고리즘 (예: Dijkstra, Value Iteration) 은 주로 결정론적 (Deterministic) 환경에서 **비용 (Cost)**을 최소화하고, 목표 도달 시 종료하는 유한한 시간 (Finite-horizon) 또는 종료 행동을 가정합니다. 반면, 강화 학습 (RL) 은 확률론적 (Stochastic) 환경에서 **보상 (Reward)**을 최대화하며, **무한한 시간 (Infinite-horizon)**을 가정하고 **할인 계수 (Discount factor)**를 사용하여 목적 함수를 유한하게 만듭니다.

이러한 차이로 인해 RL 은 계획 문제에서 다음과 같은 문제점을 가질 수 있습니다:

• 할인 계수의 문제: 할인 계수는 미래 보상의 가치를 낮추어, 목표가 도달 가능한 경우에도 알고리즘이 목표를 피하고 무한히 순환하는 (Cycle) 행동을 최적해로 선택할 수 있게 만듭니다.
• 임의의 보상 설계: RL 은 종종 원하는 행동을 유도하기 위해 보상을 임의로 조정 (Reward Shaping) 하는데, 이는 물리적 비용 (시간, 에너지 등) 과의 직접적인 연결을 끊을 수 있습니다.
• 학습과 계획의 분리: 기존 DP 기반 계획은 모델을 알고 있는 상태에서 계산하지만, RL 은 모델을 모른 채 탐색하며 학습하는 과정이 섞여 있어 성능 비교가 어렵습니다.

2. 방법론 (Methodology)

저자들은 결정론적 환경과 확률론적 환경 모두에서 계획과 RL 을 비교 분석하기 위해 다음과 같은 접근법을 취했습니다.

• 확률화되지 않은 (Derandomized) Q-learning 개발:
  • 일반적인 Q-learning 은 확률적 업데이트와 탐험 (Exploration) 을 포함하지만, 저자들은 결정론적 시스템 ($\rho=1$, 학습률 1) 에서 Q-learning 을 적용하여 동적 계획법과 동등한 수렴 특성을 가진 알고리즘을 제안했습니다.
  • 이 알고리즘은 모든 상태 - 행동 쌍을 무한히 방문한다는 가정 하에, 비동기적 가치 반복 (Asynchronous Value Iteration) 과 동일한 수렴 속도를 가짐을 증명했습니다.
• 비용/보상 모델의 수학적 분석:
  • 비용 최소화 vs 보상 최대화: 비용 함수를 $-1$배하여 보상으로 변환하면 최적 정책이 동일함을 증명했습니다 (선형 연산자 조건 하).
  • 할인 계수의 위험성: 할인 계수를 사용하면 목표가 도달 가능한 경우에도, 목표에 도달하지 않는 순환 경로 (Cycle) 가 할인된 비용이 더 낮아져 최적해로 선택될 수 있음을 반례를 통해 보였습니다.
  • 에피소드적 등가성: 단일 시도 (Single-shot) 목표 도달 문제와 무한 시간의 에피소드적 문제 (목표 도달 후 초기 상태로 복귀) 가 특정 조건 (보너스 파라미터 $M$ 조정) 하에서 동일한 최적 정책을 가질 수 있음을 분석했습니다.
• 실험적 평가:
  • 다양한 그리드 기반 계획 문제 (결정론적 및 확률적) 에서 Q-learning (다양한 $\epsilon$-greedy 및 학습률 $\rho$ 설정) 과 모델 기반의 Dijkstra, Value Iteration 을 비교했습니다.
  • 확률적 환경에서는 예측 가능성 인자 ($\gamma$) 를 조절하여 시스템의 불확실성을 제어했습니다.

3. 주요 기여 (Key Contributions)

1. 결정론적 RL 의 정립: RL 알고리즘을 결정론적 환경에 적용했을 때, 동적 계획법 기반 알고리즘 (Dijkstra 등) 과 동등한 수렴성을 가진다는 것을 이론적으로 증명하고 실험적으로 검증했습니다.
2. 할인 계수 (Discounting) 에 대한 경고: 목표 지향적 (Goal-oriented) 작업에서 할인 계수를 사용하는 것이 목표 도달 실패나 무한 순환을 초래할 수 있음을 수학적으로 증명했습니다. 대신 True Cost(물리적 비용이나 실제 비용에 직접 대응되는 비용) 를 사용하는 것을 권장합니다.
3. 모델 간 등가성 확립: 비용 최소화 문제와 보상 최대화 문제, 그리고 단일 시도 계획과 에피소드적 RL 문제 사이의 수학적 등가 조건을 명확히 했습니다.
4. 성능 비교 데이터: 다양한 문제 설정 (결정론적/확률적, 다양한 $\gamma$ 및 $\rho$) 에서 RL 과 DP 기반 계획 알고리즘의 실행 시간, 수렴성, 최적 경로 발견 능력을 체계적으로 비교한 방대한 데이터셋을 제공합니다.

4. 실험 결과 (Results)

• 결정론적 환경:
  • 모델 기반 Dijkstra 알고리즘이 Q-learning 보다 약 130 배 이상 빠르며, 더 적은 행동 횟수로 최적 해를 찾았습니다.
  • Q-learning 에서 탐험률 ($\epsilon$) 이 낮을수록 (탐색이 적을수록) 초기 상태의 최적 비용 도달 시간이 빨라지지만, 전체 상태 공간의 수렴 확률은 낮아지는 경향이 있었습니다.
  • $\epsilon=0$ (순수 탐욕) 인 경우, 목표가 명확한 결정론적 환경에서는 가장 빠른 성능을 보였습니다.
• 확률론적 환경:
  • 불확실성 ($\gamma < 1$) 이 증가할수록 Q-learning 의 수렴이 어려워졌으며, 낮은 학습률 ($\rho$) 이 더 안정적인 수렴을 보였습니다.
  • DP 기반 알고리즘 (Stochastic Value Iteration) 은 RL 보다 약 2 차수 (orders of magnitude) 더 빠르게 수렴했습니다. 이는 "온더플라이 (on-the-fly)" 학습의 비용을 보여줍니다.
  • 높은 불확실성 ($\gamma=0.5$) 환경에서는 학습률 $\rho$를 점진적으로 감소시키는 적응형 전략이 전역 수렴에 필수적이었습니다.

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

이 논문은 RL 과 계획 (Planning) 분야가 서로 다른 용어와 가정을 사용하지만, 근본적으로 동일한 동적 계획법 원리에 기반하고 있음을 재조명했습니다.

• 실용적 시사점: 로봇 공학 및 물리적 시스템 제어와 같은 목표 지향적 작업 (Goal-oriented tasks) 에서는 임의의 할인 계수나 보상 설계보다는 **실제 물리적 비용 (True Cost)**을 기반으로 한 미할인 (Undiscounted) 모델을 사용하는 것이 목표 도달 실패를 방지하고 더 효율적인 계획을 수립하는 데 유리합니다.
• 이론적 기여: RL 알고리즘을 결정론적 환경에 적용할 때의 수렴성을 보장하고, 계획 알고리즘과의 성능 격차를 정량화함으로써, 두 분야의 융합을 위한 이론적 기반을 마련했습니다.
• 향후 과제: 비용 - 보상 등가성과 에피소드적 모델의 관계를 확률론적 시스템으로 확장하는 연구가 필요하다고 결론지었습니다.

요약하자면, 이 연구는 RL 이 단순히 "학습"의 도구가 아니라, 적절한 조건 (True Cost, Termination Action, 적절한 학습률) 하에서 전통적인 계획 알고리즘과 동등하거나 더 강력한 도구가 될 수 있음을 보여주며, 특히 목표 도달이 중요한 물리적 시스템에서는 할인 계수 사용을 경계해야 함을 강조합니다.