Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version)

기술 요약: Do It for HER: 강화 학습에서의 1차 시간 논리 보상 명세

문제 정의

강화 학습(RL)은 에이전트의 행동을 유도하기 위해 보상 신호에 의존하지만, 보상 엔지니어링은 여전히 휴리스틱하고 노동 집약적인 과정으로 남아 있습니다. 중요한 과제는 작업 자체가 본질적으로 비마르코프적(non-Markovian)일 때 발생하며, 이 경우 표준 마르코프 보상 함수로는 효과적으로 포착할 수 없는 이력 의존적 보상이 필요합니다. 유한 궤적을 가진 선형 시간 논리(LTLf)가 이러한 작업을 명세하는 데 성공적으로 사용되어 왔으나, 이는 불리언 술어(Boolean predicates)로 제한된다는 한계가 있습니다. 이러한 제한은 연속적이거나 이질적인 상태 공간(예: 실수 좌표, 객체 ID, 무게)을 이산적인 명제 기호로 매핑하기 위한 수동 "레이블링 함수"를 필요로 합니다. 복잡한 로보틱스나 비즈니스 프로세스 관리와 같은 실제 시나리오에서 이러한 수동 인코딩은 취약하고 재사용이 불가능하며, 연속 데이터의 풍부한 구조를 활용하지 못합니다. 또한, 논리 기반 명세는 보상 형성(reward shaping)이나 히스턴 경험 재생(hindsight experience replay)과 같은 추가 메커니즘 없이는 학습을 어렵게 만드는 희소한 보상을 초래합니다.

방법론

저자들은 LTLf의 표현력 제한을 극복하기 위해 **유한 궤적에 대한 이론 모듈을 포함한 선형 시간 논리(LTLfMT)**를 활용하는 프레임워크를 제안합니다.

1. 이론적 프레임워크: LTLfMT

LTLf는 불리언 원자 대신, 임의의 이론(예: 비선형 실수 산술, 관계형 데이터베이스) 위에서 해석되는 1차 식을 사용합니다.

• 구문: 프레임워크는 원자적 명제가 변수, 상수 및 함수를 포함하는 1차 항과 술어($\alpha$)로 대체되는 문법을 정의합니다. 이들은 1차 논리($\lambda$)를 통해 결합된 후, 표준 LTLf와 유사하게 시간 연산자($\phi$)로 감싸집니다.
• 다루기 쉬운 파편(Tractable Fragment): 전체 LTLfMT가 결정 불가능(undecidable)하다는 점을 인식하여, 저자들은 RL에 적합한 특정 파편을 식별합니다. 그들은 데이터 수집에 대한 시간적 제약이 보상 명세에는 불필요하다고 주장하며, 텀 레이어에서 "미리 보기(lookahead)" 연산자($\bigcirc, \sim\bigcirc$)를 제거합니다. 이를 통해 결정 가능성은 오직 기저 이론에 의해서만 결정되도록 남겨둡니다.
• 오토마타로의 변환: 표준 RL을 가능하게 하기 위해, 저자들은 명제화 전략을 제안합니다. LTLfMT 파편 내의 공식 $\phi$는 1차 하위 공식들을 별도의 명제 문자로 대체함으로써 표준 LTLf 공식 $\phi'$로 변환됩니다. SMT(Satisfiability Modulo Theories) 솔버는 범용 레이블링 함수로서 역할을 수행하며, 각 타임 스텝에서 하위 공식의 참/거짓 여부를 평가하여 명제 문자의 진릿값을 결정합니다.
• 곱 MDP(Product MDP): 명제화된 공식은 결정적 유한 오토마타(DFA)로 변환됩니다. 이 DFA는 환경과 결합되어 곱 MDP를 형성하며, 여기서 상태 공간은 환경 상태와 오토마타 상태의 데카르트 곱입니다. 이는 비마르코프적 보상 문제를 표준 RL 알고리즘으로 해결 가능한 마르코프 문제로 변환합니다.

2. 보상 희소성 해결: CRM-HER

논리 기반 목표에서 발생하는 희소성을 해결하기 위해, 이 논문은 곱 MDP 프레임워크 내에서 두 가지 기술을 결합합니다:

• 보상 머신을 위한 반사실적 경험(Counterfactual Experiences for Reward Machines, CRM): 이 기술은 현재 DFA 상태를 오토마타 내의 도달 가능한 다른 상태로 교체함으로써 인공적인 전이를 생성하며, 이를 통해 "만약 ~했다면 어땠을까"라는 시나리오를 만들어 보상 신호를 밀집시킵 enough히 만듭니다.
• 히스턴 경험 재생(Hindsight Experience Replay, HER): HER는 실패한 궤적을 해당 에피소드 동안 실제로 달성된 목표로 재레이블링함으로써 샘플 효율성을 개선합니다.
• 통합: 저자들은 곱 MDP에 HER를 적용하기 위해, "목표"를 곱 공간의 특정 상태(수용 상태로의 전이를 트리거하는 상태)로 정의합니다. 이들은 CRM-HER라는 결합된 접근 방식을 제안하며, 여기서 HER는 실제 궤적과 CRM에 의해 생성된 반사실적 궤적 모두에 적용됩니다. 이는 구조화된 1차 목표를 활용하여 수동 개입 없이 자동으로 목표 명세를 생성합니다.

주요 기여

1. 보상 명세를 위한 LTLfMT: 본 논문은 LTLf를 LTLfMT로 확장하여, 1차 이론을 사용하여 연속적이고 이질적인 데이터 도메인에 대해 직접 보상 명세를 작성할 수 있게 함으로써 수동 레이블링 함수의 필요성을 제거하는 프레임워크를 도입합니다.
2. 다루기 쉬운 파편의 식별: 저자들은 결정 가능성 문제(기저 이론이 결정 가능하다는 가정하에)가 없는 특정 LFTfMT 파편을 정의하며, SMT 솔버를 통해 오토마타로의 효율적인 변환을 가능하게 합니다.
3. 통합된 CRM-HER 접근 방식: 논문은 LTLfMT로부터 유도된 곱 MDP 구조에 특화되어, 반사실적 경험과 히스턴 경험 재생을 결합하는 새로운 방법을 제시합니다.
4. 실증적 검증: 제안된 프레임워크는 비선형 실수 산술(NRA)을 사용하는 연속 제어 환경인 Parking 및 Reacher에서 평가되었습니다. 실험 결과, 제안된 방식(특히 CRM-HER 결합)이 복잡하고 희소한 목표를 가진 작업에서 베이스라인(표준 DDPG, CRM 전용, HER 전용)보다 우수한 성능을 보임을 입증했습니다.

결과

실험은 수정된 Parking 환경과 Reacher 환경에서 심층 결정적 정책 경사(DDPG)를 사용하여 수행되었습니다.

• 베이스라인 성능: 곱 MDP에 적용된 표준 DDPG는 보상 희소성 때문에 복잡한 작업(예: parking_1, parking_2)에서 성공적인 정책을 학습하는 데 큰 어려움을 겪었습니다.
• CRM vs. HER: CRM 단독으로는 오토마타 구조가 주요 병목인 작업에서 성능을 개선했으나, 목표 자체를 발견하기 어려운 경우에는 이점이 제한적이었습니다. HER 단독으로는 목표 발견 시나리오에서 잘 작동했으나 오토마타 구조를 충분히 활용하지 못했습니다.
• CRM-HER의 우월성: 결합된 CRM-HER 접근 방식은 모든 작업에서 가장 좋거나 그에 근접한 성능을 일관되게 달로 달성했습니다. 특히 가장 복잡한 작업(parking_2)에서 CRM-HER만이 성공적인 정책을 학습할 수 있는 유일한 방법이었습니다. 이 결과는 반사실적 추론(오토마타 구조 활용)과 히스턴 경험(목표 일반화 활용) 사이의 시너지가 연속 도메인의 복잡하고 희소한 보상 작업을 해결하는 데 필수적임을 시사합니다.

의의 및 주장

본 논문은 LTLfMT가 연속적이거나 이질적인 데이터 도메인에서 보상 명세를 위한 더 표현력 있고 재사용 가능한 대안을 제공한다고 주장합니다. 수동 레이블링 함수의 인코딩 복잡성을 오프더쉘(off-the-shelf) SMT 솔버로 전환함으로써, 이 프레임워크는 인간의 개입을 줄이고 새로운 작업을 정의하는 속도를 높입니다.

저자들은 제안된 방식이 논리 기반 RL에서 HER의 적용을 자연스럽게 촉진한다는 점을 강조합니다. 보상 명세가 1차 공식에 기반하므로, 공식에 사용된 변수는 HER의 목표 정의를 위한 기초로 직접 사용할 수 있으며, 이를 통해 임의적인 목표 엔지니어링을 피할 수 있습니다. 결론적으로, 이 논문은 심볼릭 로직, SMT 솔빙, 그리고 현대적 RL(CRM 및 HER)의 통합이 연속 제어 설정에서 복잡하고 비마르코프적인 행동을 명세하고 학습하는 강력한 경로를 제공하며, 이는 안전 제약 조건 및 멀티 태스크 학습을 위한 향후 연구의 토대가 됩니다.