본 논문은 강화 학습(RL)을 위한 비 마르코프 보상 함수를 인코딩하는 오토마타 구조인 보상 머신(RM)의 확장인 푸시다운 보상 머신(pdRM)을 제시합니다. pdRM은 결정적 문맥 자유 언어로 표현 가능한 시간적으로 확장된 동작을 인식하고 보상할 수 있으며, RM보다 더 표현력이 좋습니다. 본 논문에서는 pdRM 스택 전체에 접근할 수 있는 정책과 스택의 상위 k개 심볼에만 접근할 수 있는 정책, 두 가지 pdRM 기반 정책 변형을 소개합니다. 또한, 두 가지 정책이 동일한 최적 상태 값을 달성하는 시점을 확인하는 절차를 제안하고, pdRM의 표현력과 제안된 학습 문제의 공간 복잡성에 대한 이론적 결과를 제공합니다. 마지막으로, pdRM을 사용한 반사실적 경험을 활용하는 오프 정책 RL 알고리즘 접근 방식을 제안하고, 실험 결과를 통해 pdRM을 사용하여 결정적 문맥 자유 언어로 표현 가능한 작업을 수행하도록 에이전트를 훈련시킬 수 있음을 보여줍니다.
