본 논문은 강화학습(Reinforcement Learning, RL)에서 보상 함수가 부분모듈러(submodular) 함수인 경우를 다룬다. 기존 RL에서는 보상 함수가 가산적이라고 가정하지만, 경로 계획이나 적용 제어 등 실제 문제에서는 감소 수익(diminishing return)을 보이는 부분모듈러 함수로 모델링하는 것이 더 적절하다. 본 논문에서는 부분모듈러 보상 함수를 갖는 RL 문제에 대해, 부분모듈러 그래프 기반의 가지치기(pruned) 기법을 제안한다. 이 기법은 계산 가능한 시간 내에 근사적인 최적 정책을 찾는다는 것을 증명하고, 시간 및 공간 복잡도와 성능 보장을 분석한다. 기존 연구에서 사용된 벤치마크 환경을 이용한 실험 결과, 제안된 기법이 기존 방법들보다 더 높은 보상을 얻는 것을 확인하였다.
