Reinforcement Learning with Symbolic Reward Machines

이 논문은 환경의 표준 출력만 직접 처리하여 기존 보상 기계 (RMs) 의 수동 레이블링 의존성을 해결하고, 동시에 기존 방법과 동등한 성능과 해석 가능성을 제공하는 '상징적 보상 기계 (SRMs)'와 이를 학습하는 알고리즘을 제안합니다.

핵심

1. 문제 상황: "무슨 일이 일어났는지"를 모른 채 배우는 AI

기존의 AI(강화 학습) 는 마치 장난감 자동차처럼 생겼습니다.

• 상황: 자동차가 벽에 부딪히면 "아프다 (보상 -1)"라고 하고, 길을 잘 가면 "좋다 (보상 +1)"라고 합니다.
• 한계: 이 자동차는 지금 당장 부딪혔는지, 잘 갔는지만 봅니다. 과거의 기억을 가지고 있지 못합니다.
• 실제 문제: 현실 세계는 훨씬 복잡합니다. 예를 들어, "나무를 베어서 (1 단계), 나무를 트럭에 싣고 (2 단계), 공장으로 가져가라 (3 단계)"라는 미션을 줬을 때, AI 는 1 단계에서 나무를 베는 것만 보고 보상을 받으면, 2, 3 단계를 어떻게 해야 할지 모릅니다. 과거의 순서 (기억) 를 알지 못하면 미션을 완수할 수 없습니다.

2. 기존 해결책: "수동 라벨링"이라는 귀찮은 작업

기존의 해결책 (Reward Machines) 은 AI 에게 비서를 붙여주는 방식이었습니다.

• 비유: AI 가 "나무를 베었다"고 하면, 비서가 "아, 이건 1 단계 완료야!"라고 적어주면 AI 가 그걸 보고 다음 행동을 정합니다.
• 문제점: 이 비서를 만들려면 사람이 직접 모든 상황을 일일이 정의해줘야 합니다. "나무를 베는 순간 A 라는 라벨을 붙여라", "트럭에 싣는 순간 B 라벨을 붙여라"라고 말입니다.
• 결론: 환경이 조금만 바뀌어도 비서를 다시 만들어야 해서, 실제로 쓰기가 매우 번거롭고 비효율적이었습니다.

3. 이 논문의 혁신: "눈을 가진 AI" (Symbolic Reward Machines)

이 논문은 **"비서 없이도 AI 가 스스로 상황을 이해하게 하자"**는 아이디어를 제시합니다. 바로 **상징적 보상 기계 (SRM)**입니다.

🌟 핵심 비유: "수첩과 규칙"

기존 방식이 "사람이 말해주면 AI 가 따르는" 방식이었다면, 이 새로운 방식은 AI 가 스스로 수첩에 규칙을 적어두고 상황을 판단하는 방식입니다.

• 기존 (Reward Machine): "나무를 베면 'A'라고 소리쳐라." (사람이 A 라는 라벨을 만들어줘야 함)
• 새로운 방식 (SRM): "나무가 있는 좌표 (x, y) 가 5~10 사이면, '나무를 베었다'고 판단해라." (AI 가 환경의 숫자 자체를 보고 판단)

이 방식의 장점은 환경에 특별한 라벨을 붙일 필요가 없다는 것입니다. AI 는 환경이 주는 raw data(원시 데이터, 예: 좌표, 속도 등) 를 보고 **"이 숫자 범위에 들어오면 미션 1 단계 완료!"**라고 스스로 판단합니다.

4. 두 가지 새로운 학습 알고리즘

저자들은 이 SRM 을 활용하는 두 가지 방법을 개발했습니다.

① QSRM: "지도가 있는 여행"

• 상황: 사용자가 미션의 규칙 (지도) 을 이미 알고 있을 때.
• 방식: "나무를 베면 1 단계, 트럭에 싣면 2 단계"라는 규칙을 AI 에게 미리 알려줍니다. AI 는 이 규칙을 바탕으로 빠르게 미션을 완수합니다.
• 효과: 기존 방식과 똑같은 성능을 내면서, 환경 설정을 바꿀 필요 없이 표준적인 환경에서도 바로 작동합니다.

② LSRM: "스스로 지도를 그리는 탐험가" (가장 혁신적인 부분)

• 상황: 사용자가 미션의 규칙을 모를 때.
• 방식: AI 가 미션을 수행하다가 "아, 내가 나무를 베고 트럭에 싣는 순서대로 했을 때 보상을 받네?"라고 스스로 깨닫습니다.
  • AI 는 실수 (보상을 못 받은 경우) 를 기록합니다.
  • 그 기록을 분석해서 **"아, 내가 틀렸구나. 나무를 베기 전에 트럭에 싣는 건 안 되는구나"**라는 규칙 (수학적 공식) 을 스스로 만들어냅니다.
• 결과: 처음에는 아무것도 모르는 AI 가, 시행착오를 겪으며 미션의 숨겨진 규칙 (보상 구조) 을 스스로 찾아내고, 그 규칙을 사람에게도 보여줍니다.

5. 실험 결과: 얼마나 잘할까?

저자들은 '사무실 세계 (Office World)'와 '산차 (Mountain Car)' 같은 환경에서 실험했습니다.

1. 기존 AI vs 새로운 AI: 기존 AI 는 복잡한 순서 미션에서 실패하거나 매우 느리게 배웠지만, 새로운 SRM 방식은 빠르고 정확하게 미션을 완수했습니다.
2. 규칙 찾기 능력: LSRM 알고리즘은 사람이 규칙을 알려주지 않아도, **스스로 "나무를 먼저 베고 트럭에 싣자"는 논리 (규칙)**를 찾아냈습니다.
3. 해석 가능성: AI 가 배운 규칙을 사람이 읽을 수 있는 형태로 보여줍니다. "왜 AI 가 저렇게 행동했지?"라고 궁금해할 때, AI 가 만든 규칙을 보면 **"아, 나무를 먼저 베야 보상을 받기 때문이구나"**라고 이해할 수 있습니다.

6. 요약: 왜 이 연구가 중요한가?

이 논문은 AI 가 복잡한 미션을 수행할 때, 사람이 일일이 "이건 A 라벨, 저건 B 라벨"이라고 가르쳐 줄 필요를 없앴습니다.

• 기존: 사람이 AI 에게 "눈"을 만들어줘야 함 (귀찮고 비효율적).
• 새로운 방식: AI 가 스스로 환경의 숫자를 보고 "이건 미션 1 단계야!"라고 스스로 판단하게 함.
• 최고의 점: AI 가 스스로 미션의 규칙을 찾아내서 사람에게도 이해하기 쉬운 설명을 해줍니다.

마치 초보 운전자가 지도 없이도 길을 찾다가, 스스로 "이 길은 빨간불일 때 멈추고, 초록불일 때 가야 해"라는 규칙을 깨달아 운전 실력을 늘리는 것과 같습니다. 이제 AI 는 더 이상 사람의 손길을 덜 필요로 하고, 스스로 복잡한 일을 배울 수 있게 되었습니다.

기술 요약

1. 문제 정의 (Problem)

강화 학습 (RL) 에서 에이전트는 환경으로부터 상태 (관측치) 와 보상만 받으며 작업을 수행합니다. 전통적인 RL 은 보상이 현재 상태와 행동에만 의존하는 **마르코프성 (Markovian)**을 가정합니다. 그러나 실제 세계의 많은 작업 (예: 특정 순서로 여러 장소를 방문하거나, 자원을 수집한 후 기계에 넣는 작업) 은 비마르코프적 (Non-Markovian) 특성을 가집니다. 즉, 보상은 과거의 상태 히스토리 (trajectory) 에 의존합니다.

기존의 비마르코프적 보상 함수를 처리하는 주요 방법인 **보상 기계 (Reward Machines, RMs)**는 다음과 같은 한계가 있습니다:

1. 수동 라벨링 함수 필요: RMs 는 환경이 고수준의 이벤트 (라벨) 를 출력해야 작동합니다. 이를 위해 사용자는 환경의 각 상태에 대해 적절한 라벨을 생성하는 '라벨링 함수 (Labeling Function)'를 직접 설계하고 구현해야 합니다.
2. 표준 RL 프레임워크와의 비호환성: 대부분의 기존 RL 환경 (예: Gymnasium) 은 고수준 라벨을 출력하지 않으므로, RMs 를 적용하려면 환경 인터페이스를 수정하거나 추가적인 추상화 계층을 구축해야 합니다. 이는 적용성을 크게 떨어뜨립니다.
3. 유연성 부족: 라벨링 함수는 너무 일반적이거나 너무 구체적이어야 하는 딜레마에 직면하며, 모든 가능한 작업을 포괄하기 어렵습니다.

2. 제안 방법론 (Methodology)

저자들은 이러한 한계를 극복하기 위해 **상징적 보상 기계 (Symbolic Reward Machines, SRMs)**와 이를 학습하기 위한 두 가지 알고리즘 (QSRM, LSRM) 을 제안합니다.

2.1. 상징적 보상 기계 (SRM)

• 개념: SRM 은 기존 RM 의 구조를 유지하되, 입력을 고수준 라벨이 아닌 **환경의 원시 상태 (raw state)**로 직접 받습니다.
• 전환 조건 (Guard): 상태 전이는 논리식 (기호식, Symbolic Formulas) 으로 정의된 '가드 (Guard)'에 의해 결정됩니다. 예를 들어, $x \ge 5 \land y < 10$과 같은 선형 실수 산술 (LRA) 식을 사용하여 상태 공간의 특정 영역을 직접 식별합니다.
• 장점: 별도의 라벨링 함수가 불필요하며, 표준 MDP 정의와 호환됩니다. 또한, 학습된 기호식은 작업의 구조를 인간이 해석하기 쉽게 제공합니다.

2.2. 학습 알고리즘

1. QSRM (Given SRM):

   • 사용자가 SRM 구조를 미리 제공하는 경우 사용합니다.
   • 기존 QRM 알고리즘과 유사하게 각 SRM 상태에 대해 별도의 Q-테이블을 유지하며, 다중 업데이트 (multi-update) 전략을 통해 학습을 가속화합니다.
   • 환경과의 상호작용은 표준 RL 인터페이스 (상태, 행동, 보상) 만 사용하므로 기존 환경과 호환됩니다.
   • 수렴성: 표준 Q-Learning 과 동일한 조건 하에 최적 정책으로 수렴함이 증명되었습니다.

2. LSRM (Learning SRM):

   • SRM 구조를 미리 알지 못해도 학습 과정 중에 SRM 을 자동으로 추론하는 알고리즘입니다.
   • LSRM-GF (Given Formulas): 사용자가 가능한 가드 식의 집합 (Formula Set) 을 제공하는 경우.
   • LSRM-FT (Formula Templates): 사용자가 구체적인 식 대신 '식 템플릿' (예: $x \ge b_1 \land x < b_2$) 만 제공하고, 알고리즘이 템플릿 내의 변수 ($b_1, b_2$ 등) 를 학습하여 구체적인 가드를 생성하는 경우.
   • 동작 원리:
     1. 초기 가설 SRM (단일 상태) 로 시작합니다.
     2. (D)QSRM 을 통해 정책을 학습합니다.
     3. 환경의 실제 보상과 가설 SRM 이 예측한 보상이 불일치하는 경우 (Counterexample), 이를 기록합니다.
     4. 수집된 반례들을 제약 만족 문제 (CSP) 로 인코딩하여 SMT 솔버 (Z3) 를 통해 새로운 일관된 SRM 을 생성합니다.
     5. 생성된 SRM 으로 다시 학습을 반복합니다.

3. 주요 기여 (Key Contributions)

1. SRM 의 도입: 라벨링 함수 없이 환경의 원시 상태를 직접 처리하는 새로운 비마르코프적 보상 표현 방식인 SRM 을 제안했습니다.
2. 표준 RL 호환성: 기존 RL 프레임워크 (Gymnasium 등) 를 수정 없이 사용할 수 있게 하여, 비마르코프적 보상 함수를 가진 작업에 대한 RL 적용성을 크게 높였습니다.
3. 엔드 - 투 - 엔드 학습 (LSRM): 사용자가 보상 구조에 대한 사전 지식이 없어도, 환경과의 상호작용만으로 SRM 과 최적 정책을 동시에 학습할 수 있는 LSRM 알고리즘을 개발했습니다.
4. 해석 가능성 (Interpretability): 학습된 SRM 은 기호식 (기호적 논리식) 으로 표현되므로, 사용자가 에이전트가 어떤 조건에서 보상을 받는지, 작업의 단계가 무엇인지 직관적으로 이해할 수 있습니다.
5. 이론적 증명: QSRM 의 수렴성과 LSRM 이 거의 확실하게 (almost surely) 동등한 SRM 을 학습함을 수학적으로 증명했습니다.

4. 실험 결과 (Results)

저자들은 이산 (Discrete) 및 연속 (Continuous) 상태 공간 환경 (Office World, Mountain Car) 에서 실험을 수행했습니다.

• 기초 RL vs. SRM 기반 방법:
  • 기존 Q-Learning 과 DQN 은 비마르코프적 보상 구조를 학습하지 못해 성능이 낮았습니다.
  • QSRM과 기존 QRM은 동일한 최적 성능을 달성했습니다. 이는 SRM 이 라벨링 함수 없이도 RM 과 동등한 학습 능력을 가짐을 의미합니다.
• LSRM 의 성능:
  • LSRM-GF와 LSRM-FT는 모두 최적 정책에 수렴하거나 매우 높은 성능을 달성했습니다.
  • 특히 LSRM-FT는 추가적인 사용자 입력 없이도 환경에서 보상 구조를 성공적으로 추론하여 정책을 학습했습니다.
• 학습된 SRM 의 품질:
  • 학습된 SRM 은 환경의 실제 보상 기계와 구조적으로 유사하거나, 수행되는 모든 경로에서 동일한 보상을 생성하는 '거의 확실하게 동등 (almost surely equivalent)'한 것으로 확인되었습니다.
  • 연속 공간 환경에서는 수치적 오차로 인해 완벽한 동등성은 달성되지 않았으나, 실제 정책 성능에는 영향을 주지 않았습니다.

5. 의의 및 결론 (Significance)

이 논문은 강화 학습 분야에서 비마르코프적 보상 함수를 처리하는 방식을 혁신적으로 변화시켰습니다.

• 접근성 향상: 복잡한 라벨링 함수 설계라는 기술적 장벽을 제거하여, 다양한 표준 RL 환경에 비마르코프적 작업을 쉽게 적용할 수 있게 했습니다.
• 자동화 및 해석 가능성: LSRM 을 통해 보상 구조를 자동으로 학습하고, 그 결과를 인간이 이해할 수 있는 논리식으로 제공함으로써, '블랙박스'인 RL 에이전트의 의사결정 과정을 투명하게 만들었습니다.
• 실용성: 이론적 증명과 다양한 실험을 통해 제안된 방법론이 실제 적용 가능하고 효과적임을 입증했습니다.

결론적으로, 이 연구는 SRM 과 LSRM 을 통해 강화 학습의 적용 범위를 확장하고, 에이전트의 학습 과정을 더 투명하고 효율적으로 만드는 중요한 기여를 했습니다.