Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

기술 요약: 비단조 포함 관계를 통한 비볼록 희소 강화학습

문제 정의
강화학습(RL)은 고차원 상태 공간에서 Q-함수를 근사할 때 흔히 "차원의 저주" 문제에 직면한다. 선형 함수 근사는 표준적인 해결책이지만, 근사 정확도와 계산 복잡도 사이의 트레이드오프를 수반한다. 희소 모델링을 통한 특징 선택(feature selection)은 이를 완화하기 위한 일반적인 전략이지만, 기존의 $\ell_1$-노름 정규화(예: LARS-TD, $\ell_1$을 적용한 LSTD)에 의존하는 방식들은 추정 편향(estimation bias) 문제를 겪으며, 대진폭 성분을 체계적으로 과소평가하는 경향이 있다. 또한, 데이터가 고정되어 있고 잠재적으로 노이즈가 존재하는 배치(batch) RL 환경에서는 무관한 특징 및 이상치에 대한 강건성(robustness)이 매우 중요하다. 비록 비볼록 패널티인 미니맥스 컨케이브(Minimax Concave, MC) 패널티가 희소 회귀(sparse regression)에서 편향을 줄이기 위해 제안된 바 있으나, 이로 인해 발생하는 비볼록성이 최적화 문제의 단조성 가정을 깨뜨려 연산 분할(operator splitting) 방법의 수렴 보장을 어렵게 만들기 때문에 RL에 대한 적용은 아직 탐구되지 않은 영역으로 남아 있다.

방법론
본 논문은 비볼록 Projective Minimax Concave (PMC) 패널티를 Least-Squares Temporal-Difference (LSTD) 공식에 통합하는 새로운 배치 알고리즘을 제안한다.

1. 문제 재구성: 저자들은 정책 평가 문제를 $\ell_1$-정규화된 최소제곱 시간 차이(least-squares temporal-difference) 오차를 최소화하는 고정점(fixed point)을 찾는 문제로 공식화한다. 표준 LSTD와 달리, 이 목적 함수는 비볼록(non-convex)이다.
2. 연산자 분할(Operator Splitting): PMC 패널티의 약한 볼록성(weak convexity)을 활용하여, 이 고정점 문제를 두 연산자(하나의 모노톤 리프시츠 연산자와 하나의 하이포모톤 연산자)의 합의 영점(zero)을 찾는 문제로 재구성한다. 이는 문제를 비단조 포함(non-monotone inclusions) 클래스 내에 위치시킨다.
3. 알고리즘 솔루션: 저자들은 이 포함 문제를 해결하기 위해 전방-반사-후방 분할(Forward-Reflected-Backward Splitting, FRBS) 방법을 채택한다. 이 연구의 핵심적인 기술적 기여는 소프트-슈링크지(soft-shrinkage) 연산자를 포함하는 하이포모톤 부분의 레졸번트(resolvent)에 대한 폐쇄형 표현식을 유도한 것이며, 이를 통해 보조 변수 없이도 알고리즘을 실행 가능하게(tractable) 만들었다.
4. 하이퍼파라미터 튜닝: 본 방법은 PMC 패널티의 디바이어싱(debiasing) 효과가 국한되는 부분 공간 $M$을 제어하는 튜너블 하이퍼파라미터 $q$를 도입한다. 이는 원래의 PMC 정의를 일반화하여, 입력 그람 행렬(Gram matrix)의 양의 고윳값이 매우 작은 상황에서도 패널티의 성능을 최적화할 수 있게 한다.

주요 기여
본 논문의 주요 기여는 다음과 같이 네 가지로 요약된다:

• RL 알고리즘: LSTD에 비볼록 PMC 패널티를 결합한 효율적인 배치 특징 선택 RL 알고리즘을 도입한다. 이는 $\ell_1$-정규화된 방법들이 가진 추정 편향 문제를 해결한다.
• 이론적 확장: FRBS 방법의 수렴 분석을 더 넓은 범위의 비단조 포함 문제로 확장한다. 구체적으로 다음을 입증하였다:
  • 리아푸노프 안정성(Lyapunov Stability): 완만한 조건 하에서, 반복값(iterates)들이 준-페예르 단조성(quasi-Fejér monotone)을 가짐을 보여, 극한점(limit point)의 존재와 안정성을 보장한다.
  • 정확한 수렴: 약한 민티 변분 부등식(weak Minty Variational Inequality, MVI) 가정 하에서, 시퀀스가 해(solution)로 정확히 수렴함을 증명한다.
• 일반화된 PMC 패널티: $M$을 영공간의 직교 여집합으로 고정하는 대신 튜너블 파라미터 $q$에 의해 제어할 수 있도록 하여 PMC 패널티를 일반화하였다. 이는 조건이 나쁜(ill-conditioned) 설정에서 성능 저하를 방지한다.
• 오차 경계(Error Bounds): 제안된 근사 정책 반복(Approximate Policy Iteration, API) 스킴에 의해 생성된 정책의 오차 경계를 제공하며, 근사 오차와 Q-함수 추정 오차 사이의 관계를 규명한다.

결과
수치 실험은 세 가지 벤치마크 RL 작업인 50-상태 체인 워크(chain walk), 마운틴 카(mountain car), 아크로봇(acrobot)에서 수행되었다. 제안된 방법은 LSTD, LARS-TD, Basis Pursuit Denoising (BPDN)을 포함한 최신 배치 특징 선택 방법들과 비교되었다.

• 성능: 제안된 방법은 특히 노이즈가 많거나 무관한 특징이 많은 시나리오에서 경쟁 방법들을 실질적으로 압도했다. 마운틴 카와 아크로봇 작업에서 제안된 방법은 가장 높은 성공률과 가장 적은 평균 목표 도달 단계를 달 기록했다.
• 편향 완화: 실험 결과, 제안된 방법이 $\ell_1$-노름 정규화와 관련된 추정 편향을 효과적으로 완화하여 더 정확한 Q-함수 추정치를 제공함을 입증하였다.
• 하이퍼파라미터 민감도: 50-상태 체인 워크 실험을 통해 하이퍼파라미터 $q$가 성능에 유의미한 영향을 미침을 보여주었다. 적절한 범위의 $q$ 값이 가장 낮은 정규화 평균 제곱 오차(NMSE)를 나타냈으며, 극단적인 값은 디바이어싱이 충분하지 않거나 패널티가 편향된 $\ell_1$ 노름을 근사하도록 강제함으로써 성능을 저하시켰다.

의의
본 논문은 수렴 문제로 인해 이러한 방법들의 적용이 기피되었던 분야인 강화학습에 비볼록 패널티를 적용하기 위한 엄격한 이론적 토대를 제공한다고 주장한다. FRBS를 비단조 설정으로 확장함으로써, 본 연구는 비볼록 희소 모델링 이론과 실제 RL 응용 사이의 간극을 메운다. 저자들은 자신들의 접근 방식이 이론적 수렴 보장을 희생하지 않으면서도, 우수한 특징 선택과 정책 성능을 전달하는 견고한 대안을 제공한다고 강조한다. 본 연구는 약한 MVI 가정 하에서의 완전한 수렴 증명과 광범가한 수치적 검증을 제공함으로써 예비 컨퍼런스 버전을 확장하였다.